Logo Search packages:      
Sourcecode: blender version File versions

editmesh_tools.c

/**
 * $Id: 
 *
 * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version. The Blender
 * Foundation also sells licenses for use in proprietary software under
 * the Blender License.  See http://www.blender.org/BL/ for information
 * about this.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * The Original Code is Copyright (C) 2004 by NaN Holding BV.
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL/BL DUAL LICENSE BLOCK *****
 */

/*

editmesh_tool.c: UI called tools for editmesh, geometry changes here, otherwise in mods.c

*/

#include <stdlib.h>
#include <string.h>
#include <math.h>

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#ifdef WIN32
#include "BLI_winstuff.h"
#endif
#include "MEM_guardedalloc.h"


#include "DNA_mesh_types.h"
#include "DNA_material_types.h"
#include "DNA_meshdata_types.h"
#include "DNA_object_types.h"
#include "DNA_scene_types.h"
#include "DNA_screen_types.h"
#include "DNA_view3d_types.h"

#include "BLI_blenlib.h"
#include "BLI_arithb.h"
#include "BLI_editVert.h"
#include "BLI_rand.h"

#include "BKE_displist.h"
#include "BKE_global.h"
#include "BKE_library.h"
#include "BKE_mesh.h"
#include "BKE_object.h"
#include "BKE_utildefines.h"

#include "BIF_cursors.h"
#include "BIF_editmesh.h"
#include "BIF_gl.h"
#include "BIF_graphics.h"
#include "BIF_interface.h"
#include "BIF_mywindow.h"
#include "BIF_screen.h"
#include "BIF_space.h"
#include "BIF_resources.h"
#include "BIF_toolbox.h"

#include "BDR_drawobject.h"
#include "BDR_editobject.h"

#include "BSE_view.h"
#include "BSE_edit.h"

#include "mydevice.h"
#include "blendef.h"

#include "editmesh.h"


/********* qsort routines *********/


00099 struct xvertsort {
      float x;
      EditVert *v1;
};

static int vergxco(const void *v1, const void *v2)
{
      const struct xvertsort *x1=v1, *x2=v2;

      if( x1->x > x2->x ) return 1;
      else if( x1->x < x2->x) return -1;
      return 0;
}

struct facesort {
      long x;
      struct EditFace *efa;
};


static int vergface(const void *v1, const void *v2)
{
      const struct facesort *x1=v1, *x2=v2;
      
      if( x1->x > x2->x ) return 1;
      else if( x1->x < x2->x) return -1;
      return 0;
}


/* *********************************** */

void convert_to_triface(int all)
{
      EditMesh *em = G.editMesh;
      EditFace *efa, *efan, *next;
      
      efa= em->faces.last;
      while(efa) {
            next= efa->prev;
            if(efa->v4) {
                  if(all || (efa->f & SELECT) ) {
                        
                        efan= addfacelist(efa->v1, efa->v2, efa->v3, 0, efa, NULL);
                        if(efa->f & SELECT) EM_select_face(efan, 1);
                        efan= addfacelist(efa->v1, efa->v3, efa->v4, 0, efa, NULL);
                        if(efa->f & SELECT) EM_select_face(efan, 1);

                        efan->tf.uv[1][0]= efan->tf.uv[2][0];
                        efan->tf.uv[1][1]= efan->tf.uv[2][1];
                        efan->tf.uv[2][0]= efan->tf.uv[3][0];
                        efan->tf.uv[2][1]= efan->tf.uv[3][1];
                        
                        efan->tf.col[1]= efan->tf.col[2];
                        efan->tf.col[2]= efan->tf.col[3];
                        
                        BLI_remlink(&em->faces, efa);
                        free_editface(efa);
                  }
            }
            efa= next;
      }
      
      EM_fgon_flags();  // redo flags and indices for fgons
      BIF_undo_push("Convert Quads to Triangles");
      
}


int removedoublesflag(short flag, float limit)        /* return amount */
{
      EditMesh *em = G.editMesh;
      /* all verts with (flag & 'flag') are being evaluated */
      EditVert *eve, *v1, *nextve;
      EditEdge *eed, *e1, *nexted;
      EditFace *efa, *nextvl;
      struct xvertsort *sortblock, *sb, *sb1;
      struct facesort *vlsortblock, *vsb, *vsb1;
      float dist;
      int a, b, test, amount;

      /* flag 128 is cleared, count */
      eve= em->verts.first;
      amount= 0;
      while(eve) {
            eve->f &= ~128;
            if(eve->f & flag) amount++;
            eve= eve->next;
      }
      if(amount==0) return 0;

      /* allocate memory and qsort */
      sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
      eve= em->verts.first;
      while(eve) {
            if(eve->f & flag) {
                  sb->x= eve->co[0]+eve->co[1]+eve->co[2];
                  sb->v1= eve;
                  sb++;
            }
            eve= eve->next;
      }
      qsort(sortblock, amount, sizeof(struct xvertsort), vergxco);

      /* test for doubles */
      sb= sortblock;
      for(a=0; a<amount; a++) {
            eve= sb->v1;
            if( (eve->f & 128)==0 ) {
                  sb1= sb+1;
                  for(b=a+1; b<amount; b++) {
                        /* first test: simpel dist */
                        dist= sb1->x - sb->x;
                        if(dist > limit) break;
                        
                        /* second test: is vertex allowed */
                        v1= sb1->v1;
                        if( (v1->f & 128)==0 ) {
                              
                              dist= fabs(v1->co[0]-eve->co[0]);
                              if(dist<=limit) {
                                    dist= fabs(v1->co[1]-eve->co[1]);
                                    if(dist<=limit) {
                                          dist= fabs(v1->co[2]-eve->co[2]);
                                          if(dist<=limit) {
                                                v1->f|= 128;
                                                v1->vn= eve;
                                          }
                                    }
                              }
                        }
                        sb1++;
                  }
            }
            sb++;
      }
      MEM_freeN(sortblock);

      /* test edges and insert again */
      eed= em->edges.first;
      while(eed) {
            eed->f2= 0;
            eed= eed->next;
      }
      eed= em->edges.last;
      while(eed) {
            nexted= eed->prev;

            if(eed->f2==0) {
                  if( (eed->v1->f & 128) || (eed->v2->f & 128) ) {
                        remedge(eed);

                        if(eed->v1->f & 128) eed->v1= eed->v1->vn;
                        if(eed->v2->f & 128) eed->v2= eed->v2->vn;
                        e1= addedgelist(eed->v1, eed->v2, eed);
                        
                        if(e1) e1->f2= 1;
                        if(e1!=eed) free_editedge(eed);
                  }
            }
            eed= nexted;
      }

      /* first count amount of test faces */
      efa= (struct EditFace *)em->faces.first;
      amount= 0;
      while(efa) {
            efa->f1= 0;
            if(efa->v1->f & 128) efa->f1= 1;
            else if(efa->v2->f & 128) efa->f1= 1;
            else if(efa->v3->f & 128) efa->f1= 1;
            else if(efa->v4 && (efa->v4->f & 128)) efa->f1= 1;
            
            if(efa->f1==1) amount++;
            efa= efa->next;
      }

      /* test faces for double vertices, and if needed remove them */
      efa= (struct EditFace *)em->faces.first;
      while(efa) {
            nextvl= efa->next;
            if(efa->f1==1) {
                  
                  if(efa->v1->f & 128) efa->v1= efa->v1->vn;
                  if(efa->v2->f & 128) efa->v2= efa->v2->vn;
                  if(efa->v3->f & 128) efa->v3= efa->v3->vn;
                  if(efa->v4 && (efa->v4->f & 128)) efa->v4= efa->v4->vn;
            
                  test= 0;
                  if(efa->v1==efa->v2) test+=1;
                  if(efa->v2==efa->v3) test+=2;
                  if(efa->v3==efa->v1) test+=4;
                  if(efa->v4==efa->v1) test+=8;
                  if(efa->v3==efa->v4) test+=16;
                  if(efa->v2==efa->v4) test+=32;
                  
                  if(test) {
                        if(efa->v4) {
                              if(test==1 || test==2) {
                                    efa->v2= efa->v3;
                                    efa->v3= efa->v4;
                                    efa->v4= 0;
                                    test= 0;
                              }
                              else if(test==8 || test==16) {
                                    efa->v4= 0;
                                    test= 0;
                              }
                              else {
                                    BLI_remlink(&em->faces, efa);
                                    free_editface(efa);
                                    amount--;
                              }
                        }
                        else {
                              BLI_remlink(&em->faces, efa);
                              free_editface(efa);
                              amount--;
                        }
                  }
                  
                  if(test==0) {
                        /* set edge pointers */
                        efa->e1= findedgelist(efa->v1, efa->v2);
                        efa->e2= findedgelist(efa->v2, efa->v3);
                        if(efa->v4==0) {
                              efa->e3= findedgelist(efa->v3, efa->v1);
                              efa->e4= 0;
                        }
                        else {
                              efa->e3= findedgelist(efa->v3, efa->v4);
                              efa->e4= findedgelist(efa->v4, efa->v1);
                        }
                  }
            }
            efa= nextvl;
      }

      /* double faces: sort block */
      /* count again, now all selected faces */
      amount= 0;
      efa= em->faces.first;
      while(efa) {
            efa->f1= 0;
            if(faceselectedAND(efa, 1)) {
                  efa->f1= 1;
                  amount++;
            }
            efa= efa->next;
      }

      if(amount) {
            /* double faces: sort block */
            vsb= vlsortblock= MEM_mallocN(sizeof(struct facesort)*amount, "sortremovedoub");
            efa= em->faces.first;
            while(efa) {
                  if(efa->f1 & 1) {
                        if(efa->v4) vsb->x= (long) MIN4( (long)efa->v1, (long)efa->v2, (long)efa->v3, (long)efa->v4);
                        else vsb->x= (long) MIN3( (long)efa->v1, (long)efa->v2, (long)efa->v3);

                        vsb->efa= efa;
                        vsb++;
                  }
                  efa= efa->next;
            }
            
            qsort(vlsortblock, amount, sizeof(struct facesort), vergface);
                  
            vsb= vlsortblock;
            for(a=0; a<amount; a++) {
                  efa= vsb->efa;
                  if( (efa->f1 & 128)==0 ) {
                        vsb1= vsb+1;

                        for(b=a+1; b<amount; b++) {
                        
                              /* first test: same pointer? */
                              if(vsb->x != vsb1->x) break;
                              
                              /* second test: is test permitted? */
                              efa= vsb1->efa;
                              if( (efa->f1 & 128)==0 ) {
                                    if( compareface(efa, vsb->efa)) efa->f1 |= 128;
                                    
                              }
                              vsb1++;
                        }
                  }
                  vsb++;
            }
            
            MEM_freeN(vlsortblock);
            
            /* remove double faces */
            efa= (struct EditFace *)em->faces.first;
            while(efa) {
                  nextvl= efa->next;
                  if(efa->f1 & 128) {
                        BLI_remlink(&em->faces, efa);
                        free_editface(efa);
                  }
                  efa= nextvl;
            }
      }
      
      /* remove double vertices */
      a= 0;
      eve= (struct EditVert *)em->verts.first;
      while(eve) {
            nextve= eve->next;
            if(eve->f & flag) {
                  if(eve->f & 128) {
                        a++;
                        BLI_remlink(&em->verts, eve);
                        free_editvert(eve);
                  }
            }
            eve= nextve;
      }

      return a;   /* amount */
}

/* called from buttons */
void xsortvert_flag(int flag)
{
      EditMesh *em = G.editMesh;
      /* all verts with (flag & 'flag') are sorted */
      EditVert *eve;
      struct xvertsort *sortblock, *sb;
      ListBase tbase;
      int amount;
      
      /* count */
      eve= em->verts.first;
      amount= 0;
      while(eve) {
            if(eve->f & flag) amount++;
            eve= eve->next;
      }
      if(amount==0) return;

      /* allocate memory and sort */
      sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
      eve= em->verts.first;
      while(eve) {
            if(eve->f & flag) {
                  sb->x= eve->xs;
                  sb->v1= eve;
                  sb++;
            }
            eve= eve->next;
      }
      qsort(sortblock, amount, sizeof(struct xvertsort), vergxco);
      
      /* make temporal listbase */
      tbase.first= tbase.last= 0;
      sb= sortblock;
      while(amount--) {
            eve= sb->v1;
            BLI_remlink(&em->verts, eve);
            BLI_addtail(&tbase, eve);
            sb++;
      }
      
      addlisttolist(&em->verts, &tbase);
      
      MEM_freeN(sortblock);
      BIF_undo_push("Xsort");
      
}

/* called from buttons */
void hashvert_flag(int flag)
{
      /* switch vertex order using hash table */
      EditMesh *em = G.editMesh;
      EditVert *eve;
      struct xvertsort *sortblock, *sb, onth, *newsort;
      ListBase tbase;
      int amount, a, b;
      
      /* count */
      eve= em->verts.first;
      amount= 0;
      while(eve) {
            if(eve->f & flag) amount++;
            eve= eve->next;
      }
      if(amount==0) return;
      
      /* allocate memory */
      sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
      eve= em->verts.first;
      while(eve) {
            if(eve->f & flag) {
                  sb->v1= eve;
                  sb++;
            }
            eve= eve->next;
      }

      BLI_srand(1);
      
      sb= sortblock;
      for(a=0; a<amount; a++, sb++) {
            b= amount*BLI_drand();
            if(b>=0 && b<amount) {
                  newsort= sortblock+b;
                  onth= *sb;
                  *sb= *newsort;
                  *newsort= onth;
            }
      }

      /* make temporal listbase */
      tbase.first= tbase.last= 0;
      sb= sortblock;
      while(amount--) {
            eve= sb->v1;
            BLI_remlink(&em->verts, eve);
            BLI_addtail(&tbase, eve);
            sb++;
      }
      
      addlisttolist(&em->verts, &tbase);
      
      MEM_freeN(sortblock);
      BIF_undo_push("Hash");

}

void extrude_mesh(void)
{
      short nr, xmode= 0;

      TEST_EDITMESH
      
      if(G.scene->selectmode & SCE_SELECT_VERTEX)
            nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3|Only Vertices%x4");
      else if(G.scene->selectmode & SCE_SELECT_EDGE)
            nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3");
      else
            nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2");
            
      if(nr<1) return;

      if(nr==1)  xmode= extrudeflag(SELECT);
      else if(nr==4) xmode= extrudeflag_verts_indiv(SELECT);
      else if(nr==3) xmode= extrudeflag_edges_indiv(SELECT);
      else xmode= extrudeflag_face_indiv(SELECT);
      
      if(xmode==0) {
            error("No valid selection");
      }
      else {
            EM_fgon_flags();
            countall(); 
            transform(xmode);
      }

}

void split_mesh(void)
{

      TEST_EDITMESH

      if(okee(" Split ")==0) return;

      waitcursor(1);

      /* make duplicate first */
      adduplicateflag(SELECT);
      /* old faces have flag 128 set, delete them */
      delfaceflag(128);

      waitcursor(0);

      countall();
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      BIF_undo_push("Split");

}

void extrude_repeat_mesh(int steps, float offs)
{
      float dvec[3], tmat[3][3], bmat[3][3];
      short a,ok;

      TEST_EDITMESH
      waitcursor(1);
      
      /* dvec */
      dvec[0]= G.vd->persinv[2][0];
      dvec[1]= G.vd->persinv[2][1];
      dvec[2]= G.vd->persinv[2][2];
      Normalise(dvec);
      dvec[0]*= offs;
      dvec[1]*= offs;
      dvec[2]*= offs;

      /* base correction */
      Mat3CpyMat4(bmat, G.obedit->obmat);
      Mat3Inv(tmat, bmat);
      Mat3MulVecfl(tmat, dvec);

      for(a=0;a<steps;a++) {
            ok= extrudeflag(SELECT);
            if(ok==0) {
                  error("No valid vertices are selected");
                  break;
            }
            translateflag(SELECT, dvec);
      }
      
      EM_fgon_flags();
      countall();
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      waitcursor(0);
      BIF_undo_push("Extrude Repeat");

}

void spin_mesh(int steps,int degr,float *dvec, int mode)
{
      extern short editbutflag;
      EditMesh *em = G.editMesh;
      EditVert *eve,*nextve;
      float *curs, si,n[3],q[4],cmat[3][3],imat[3][3], tmat[3][3];
      float cent[3],bmat[3][3];
      float phi;
      short a,ok;

      TEST_EDITMESH
      
      waitcursor(1);
      
      /* imat and centre and size */
      Mat3CpyMat4(bmat, G.obedit->obmat);
      Mat3Inv(imat,bmat);

      curs= give_cursor();
      VECCOPY(cent, curs);
      cent[0]-= G.obedit->obmat[3][0];
      cent[1]-= G.obedit->obmat[3][1];
      cent[2]-= G.obedit->obmat[3][2];
      Mat3MulVecfl(imat, cent);

      phi= degr*M_PI/360.0;
      phi/= steps;
      if(editbutflag & B_CLOCKWISE) phi= -phi;

      if(dvec) {
            n[0]=n[1]= 0.0;
            n[2]= 1.0;
      } else {
            n[0]= G.vd->viewinv[2][0];
            n[1]= G.vd->viewinv[2][1];
            n[2]= G.vd->viewinv[2][2];
            Normalise(n);
      }

      q[0]= cos(phi);
      si= sin(phi);
      q[1]= n[0]*si;
      q[2]= n[1]*si;
      q[3]= n[2]*si;
      QuatToMat3(q, cmat);

      Mat3MulMat3(tmat,cmat,bmat);
      Mat3MulMat3(bmat,imat,tmat);

      if(mode==0) if(editbutflag & B_KEEPORIG) adduplicateflag(1);
      ok= 1;

      for(a=0;a<steps;a++) {
            if(mode==0) ok= extrudeflag(SELECT);
            else adduplicateflag(SELECT);
            if(ok==0) {
                  error("No valid vertices are selected");
                  break;
            }
            rotateflag(SELECT, cent, bmat);
            if(dvec) {
                  Mat3MulVecfl(bmat,dvec);
                  translateflag(SELECT, dvec);
            }
      }

      waitcursor(0);
      if(ok==0) {
            /* no vertices or only loose ones selected, remove duplicates */
            eve= em->verts.first;
            while(eve) {
                  nextve= eve->next;
                  if(eve->f & SELECT) {
                        BLI_remlink(&em->verts,eve);
                        free_editvert(eve);
                  }
                  eve= nextve;
            }
      }
      
      EM_fgon_flags();
      countall();
      recalc_editnormals();
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      
      if(dvec==NULL) BIF_undo_push("Spin");
}

void screw_mesh(int steps,int turns)
{
      EditMesh *em = G.editMesh;
      EditVert *eve,*v1=0,*v2=0;
      EditEdge *eed;
      float dvec[3], nor[3];

      TEST_EDITMESH

      /* first condition: we need frontview! */
      if(G.vd->view!=1) {
            error("Must be in Front View");
            return;
      }
      
      /* clear flags */
      eve= em->verts.first;
      while(eve) {
            eve->f1= 0;
            eve= eve->next;
      }
      /* edges set flags in verts */
      eed= em->edges.first;
      while(eed) {
            if(eed->v1->f & SELECT) {
                  if(eed->v2->f & SELECT) {
                        /* watch: f1 is a byte */
                        if(eed->v1->f1<2) eed->v1->f1++;
                        if(eed->v2->f1<2) eed->v2->f1++;
                  }
            }
            eed= eed->next;
      }
      /* find two vertices with eve->f1==1, more or less is wrong */
      eve= em->verts.first;
      while(eve) {
            if(eve->f1==1) {
                  if(v1==0) v1= eve;
                  else if(v2==0) v2= eve;
                  else {
                        v1=0;
                        break;
                  }
            }
            eve= eve->next;
      }
      if(v1==0 || v2==0) {
            error("No curve is selected");
            return;
      }

      /* calculate dvec */
      dvec[0]= ( (v1->co[0]- v2->co[0]) )/(steps);
      dvec[1]= ( (v1->co[1]- v2->co[1]) )/(steps);
      dvec[2]= ( (v1->co[2]- v2->co[2]) )/(steps);

      VECCOPY(nor, G.obedit->obmat[2]);

      if(nor[0]*dvec[0]+nor[1]*dvec[1]+nor[2]*dvec[2]>0.000) {
            dvec[0]= -dvec[0];
            dvec[1]= -dvec[1];
            dvec[2]= -dvec[2];
      }

      spin_mesh(turns*steps, turns*360, dvec, 0);

      BIF_undo_push("Spin");
}


static void erase_edges(ListBase *l)
{
      EditEdge *ed, *nexted;
      
      ed = (EditEdge *) l->first;
      while(ed) {
            nexted= ed->next;
            if( (ed->v1->f & SELECT) || (ed->v2->f & SELECT) ) {
                  remedge(ed);
                  free_editedge(ed);
            }
            ed= nexted;
      }
}

static void erase_faces(ListBase *l)
{
      EditFace *f, *nextf;

      f = (EditFace *) l->first;

      while(f) {
            nextf= f->next;
            if( faceselectedOR(f, SELECT) ) {
                  BLI_remlink(l, f);
                  free_editface(f);
            }
            f = nextf;
      }
}     

static void erase_vertices(ListBase *l)
{
      EditVert *v, *nextv;

      v = (EditVert *) l->first;
      while(v) {
            nextv= v->next;
            if(v->f & 1) {
                  BLI_remlink(l, v);
                  free_editvert(v);
            }
            v = nextv;
      }
}

void delete_mesh(void)
{
      EditMesh *em = G.editMesh;
      EditFace *efa, *nextvl;
      EditVert *eve,*nextve;
      EditEdge *eed,*nexted;
      short event;
      int count;
      char *str="Erase";

      TEST_EDITMESH
      
      event= pupmenu("Erase %t|Vertices%x10|Edges%x1|Faces%x2|All%x3|Edges & Faces%x4|Only Faces%x5");
      if(event<1) return;

      if(event==10 ) {
            str= "Erase Vertices";
            erase_edges(&em->edges);
            erase_faces(&em->faces);
            erase_vertices(&em->verts);
      } 
      else if(event==4) {
            str= "Erase Edges & Faces";
            efa= em->faces.first;
            while(efa) {
                  nextvl= efa->next;
                  /* delete only faces with 1 or more edges selected */
                  count= 0;
                  if(efa->e1->f & SELECT) count++;
                  if(efa->e2->f & SELECT) count++;
                  if(efa->e3->f & SELECT) count++;
                  if(efa->e4 && (efa->e4->f & SELECT)) count++;
                  if(count) {
                        BLI_remlink(&em->faces, efa);
                        free_editface(efa);
                  }
                  efa= nextvl;
            }
            eed= em->edges.first;
            while(eed) {
                  nexted= eed->next;
                  if(eed->f & SELECT) {
                        remedge(eed);
                        free_editedge(eed);
                  }
                  eed= nexted;
            }
            efa= em->faces.first;
            while(efa) {
                  nextvl= efa->next;
                  event=0;
                  if( efa->v1->f & SELECT) event++;
                  if( efa->v2->f & SELECT) event++;
                  if( efa->v3->f & SELECT) event++;
                  if(efa->v4 && (efa->v4->f & SELECT)) event++;
                  
                  if(event>1) {
                        BLI_remlink(&em->faces, efa);
                        free_editface(efa);
                  }
                  efa= nextvl;
            }
      } 
      else if(event==1) {
            str= "Erase Edges";
            // faces first
            efa= em->faces.first;
            while(efa) {
                  nextvl= efa->next;
                  event=0;
                  if( efa->e1->f & SELECT) event++;
                  if( efa->e2->f & SELECT) event++;
                  if( efa->e3->f & SELECT) event++;
                  if(efa->e4 && (efa->e4->f & SELECT)) event++;
                  
                  if(event) {
                        BLI_remlink(&em->faces, efa);
                        free_editface(efa);
                  }
                  efa= nextvl;
            }
            eed= em->edges.first;
            while(eed) {
                  nexted= eed->next;
                  if(eed->f & SELECT) {
                        remedge(eed);
                        free_editedge(eed);
                  }
                  eed= nexted;
            }
            /* to remove loose vertices: */
            eed= em->edges.first;
            while(eed) {
                  if( eed->v1->f & SELECT) eed->v1->f-=SELECT;
                  if( eed->v2->f & SELECT) eed->v2->f-=SELECT;
                  eed= eed->next;
            }
            eve= em->verts.first;
            while(eve) {
                  nextve= eve->next;
                  if(eve->f & SELECT) {
                        BLI_remlink(&em->verts,eve);
                        free_editvert(eve);
                  }
                  eve= nextve;
            }

      }
      else if(event==2) {
            str="Erase Faces";
            delfaceflag(SELECT);
      }
      else if(event==3) {
            str= "Erase All";
            if(em->verts.first) free_vertlist(&em->verts);
            if(em->edges.first) free_edgelist(&em->edges);
            if(em->faces.first) free_facelist(&em->faces);
      }
      else if(event==5) {
            str= "Erase Only Faces";
            efa= em->faces.first;
            while(efa) {
                  nextvl= efa->next;
                  if(efa->f & SELECT) {
                        BLI_remlink(&em->faces, efa);
                        free_editface(efa);
                  }
                  efa= nextvl;
            }
      }

      EM_fgon_flags();  // redo flags and indices for fgons

      countall();
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      BIF_undo_push(str);
}


/* Got this from scanfill.c. You will need to juggle around the
 * callbacks for the scanfill.c code a bit for this to work. */
void fill_mesh(void)
{
      EditMesh *em = G.editMesh;
      EditVert *eve,*v1;
      EditEdge *eed,*e1,*nexted;
      EditFace *efa,*nextvl, *efan;
      short ok;

      if(G.obedit==0 || (G.obedit->type!=OB_MESH)) return;

      waitcursor(1);

      /* copy all selected vertices */
      eve= em->verts.first;
      while(eve) {
            if(eve->f & SELECT) {
                  v1= BLI_addfillvert(eve->co);
                  eve->vn= v1;
                  v1->vn= eve;
                  v1->h= 0;
            }
            eve= eve->next;
      }
      /* copy all selected edges */
      eed= em->edges.first;
      while(eed) {
            if( (eed->v1->f & SELECT) && (eed->v2->f & SELECT) ) {
                  e1= BLI_addfilledge(eed->v1->vn, eed->v2->vn);
                  e1->v1->h++; 
                  e1->v2->h++;
            }
            eed= eed->next;
      }
      /* from all selected faces: remove vertices and edges to prevent doubles */
      /* all edges add values, faces subtract,
         then remove edges with vertices ->h<2 */
      efa= em->faces.first;
      ok= 0;
      while(efa) {
            nextvl= efa->next;
            if( faceselectedAND(efa, 1) ) {
                  efa->v1->vn->h--;
                  efa->v2->vn->h--;
                  efa->v3->vn->h--;
                  if(efa->v4) efa->v4->vn->h--;
                  ok= 1;
                  
            }
            efa= nextvl;
      }
      if(ok) {    /* there are faces selected */
            eed= filledgebase.first;
            while(eed) {
                  nexted= eed->next;
                  if(eed->v1->h<2 || eed->v2->h<2) {
                        BLI_remlink(&filledgebase,eed);
                  }
                  eed= nexted;
            }
      }

      /* to make edgefill work */
      BLI_setScanFillObjectRef(G.obedit);
      BLI_setScanFillColourRef(&G.obedit->actcol);

      ok= BLI_edgefill(0);

      /* printf("time: %d\n",(clock()-tijd)/1000); */

      if(ok) {
            efa= fillfacebase.first;
            while(efa) {
                  efan= addfacelist(efa->v3->vn, efa->v2->vn, efa->v1->vn, 0, NULL, NULL); // normals default pointing up
                  EM_select_face(efan, 1);
                  efa= efa->next;
            }
      }
      /* else printf("fill error\n"); */

      BLI_end_edgefill();

      waitcursor(0);
      EM_select_flush();
      countall();
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      BIF_undo_push("Fill");
}



/* ******************** SUBDIVIDE ********************************** */


static unsigned int cpack_fact(unsigned int col1, unsigned int col2, float fact)
{
      char *cp1, *cp2, *cp;
      unsigned int col=0;
      float fact1;
      
      fact1=1-fact; /*result is fact% col1 and (1-fact) % col2 */
            
      cp1= (char *)&col1;
      cp2= (char *)&col2;
      cp=  (char *)&col;
      
      cp[0]= fact*cp1[0]+fact1*cp2[0];
      cp[1]= fact*cp1[1]+fact1*cp2[1];
      cp[2]= fact*cp1[2]+fact1*cp2[2];
      cp[3]= fact*cp1[3]+fact1*cp2[3];
      
      return col;
}


static void uv_half(float *uv, float *uv1, float *uv2)
{
      uv[0]= (uv1[0]+uv2[0])/2.0;
      uv[1]= (uv1[1]+uv2[1])/2.0;
      
}

static void uv_quart(float *uv, float *uv1)
{
      uv[0]= (uv1[0]+uv1[2]+uv1[4]+uv1[6])/4.0;
      uv[1]= (uv1[1]+uv1[3]+uv1[5]+uv1[7])/4.0;
}

static void face_pin_vertex(EditFace *efa, EditVert *vertex)
{
      if(efa->v1 == vertex) efa->tf.unwrap |= TF_PIN1;
      else if(efa->v2 == vertex) efa->tf.unwrap |= TF_PIN2;
      else if(efa->v3 == vertex) efa->tf.unwrap |= TF_PIN3;
      else if(efa->v4 && vertex && efa->v4 == vertex) efa->tf.unwrap |= TF_PIN4;
}

static void set_wuv(int tot, EditFace *efa, int v1, int v2, int v3, int v4, EditFace *efapin)
{
      /* this weird function only to be used for subdivide, the 'w' in the name has no meaning! */
      float *uv, uvo[4][2];
      unsigned int *col, colo[4], col1, col2;
      int a, v;

      /* recover pinning */
      if(efapin){
            efa->tf.unwrap= 0;
            if(efapin->tf.unwrap & TF_PIN1) face_pin_vertex(efa, efapin->v1);
            if(efapin->tf.unwrap & TF_PIN2) face_pin_vertex(efa, efapin->v2);
            if(efapin->tf.unwrap & TF_PIN3) face_pin_vertex(efa, efapin->v3);
            if(efapin->tf.unwrap & TF_PIN4) face_pin_vertex(efa, efapin->v4);
      }

                                    /* Numbers corespond to verts (corner points),  */
                                    /* edge->vn's (center edges), the Center  */
      memcpy(uvo, efa->tf.uv, sizeof(uvo));     /* And the quincunx points of a face            */
      uv= efa->tf.uv[0];                            /* as shown here:                           */
                                                    /*           2         5          1   */
      memcpy(colo, efa->tf.col, sizeof(colo));      /*               10         13        */
      col= efa->tf.col;                             /*           6         9          8   */
                                                  /*               11         12        */
      if(tot==4) {                                  /*           3         7          4   */
            for(a=0; a<4; a++, uv+=2, col++) {
                  if(a==0) v= v1;
                  else if(a==1) v= v2;
                  else if(a==2) v= v3;
                  else v= v4;
                  
                  if(a==3 && v4==0) break;
                  
                  if(v<=4) {
                        uv[0]= uvo[v-1][0];
                        uv[1]= uvo[v-1][1];
                        *col= colo[v-1];
                  }
                  else if(v==8) {
                        uv_half(uv, uvo[3], uvo[0]);
                        *col= cpack_fact(colo[3], colo[0], 0.5);
                  }
                  else if(v==9) {
                        uv_quart(uv, uvo[0]);
                        col1= cpack_fact(colo[1], colo[0], 0.5);
                        col2= cpack_fact(colo[2], colo[3], 0.5);
                        *col= cpack_fact(col1, col2, 0.5);
                  }
                  /* Cases for adjacent edge square subdivide  Real voodoo */
                  /* 1/2 closest corner + 1/4 adjacent corners */
                  else if (v==10){ /* case test==3 in subdivideflag() */      
                        uv[0]=(2*uvo[1][0]+uvo[0][0]+uvo[2][0])/4;
                        uv[1]=(2*uvo[1][1]+uvo[0][1]+uvo[2][1])/4;
                        col1= cpack_fact(colo[1], colo[0], 0.75);
                        col2= cpack_fact(colo[2], colo[3], 0.75);
                        *col= cpack_fact(col1, col2, 0.75); 
                  }
                  else if (v==11) { /* case of test==6 */
                        uv[0]=(2*uvo[2][0]+uvo[1][0]+uvo[3][0])/4;
                        uv[1]=(2*uvo[2][1]+uvo[1][1]+uvo[3][1])/4;
                        col1= cpack_fact(colo[1], colo[0], 0.75);
                        col2= cpack_fact(colo[2], colo[3], 0.75);
                        *col= cpack_fact(col1, col2, 0.25); 
                  }
                  else if (v==12) { /* case of test==12 */
                        uv[0]=(2*uvo[3][0]+uvo[2][0]+uvo[0][0])/4;
                        uv[1]=(2*uvo[3][1]+uvo[2][1]+uvo[0][1])/4;
                        col1= cpack_fact(colo[1], colo[0], 0.25);
                        col2= cpack_fact(colo[2], colo[3], 0.25);
                        *col= cpack_fact(col1, col2, 0.25);
                  }
                  else if (v==13) { /* case of test==9 */
                        uv[0]=(2*uvo[0][0]+uvo[1][0]+uvo[3][0])/4;
                        uv[1]=(2*uvo[0][1]+uvo[1][1]+uvo[3][1])/4;
                        col1= cpack_fact(colo[1], colo[0], 0.25);
                        col2= cpack_fact(colo[2], colo[3], 0.25);
                        *col= cpack_fact(col1, col2, 0.75);
                  }
                  /* default for consecutive verts*/
                  else { 
                        uv_half(uv, uvo[v-5], uvo[v-4]);
                        *col= cpack_fact(colo[v-5], colo[v-4], 0.5);
                  }
            }
      }
      else {
            for(a=0; a<3; a++, uv+=2, col++) {
                  if(a==0) v= v1;
                  else if(a==1) v= v2;
                  else v= v3;
            
                  if(v<=4) {
                        uv[0]= uvo[v-1][0];
                        uv[1]= uvo[v-1][1];
                        *col= colo[v-1];
                  }
                  else if(v==7) {
                        uv_half(uv, uvo[2], uvo[0]);
                        *col= cpack_fact(colo[2], colo[0], 0.5);
                  }
                  else {
                        uv_half(uv, uvo[v-5], uvo[v-4]);
                        *col= cpack_fact(colo[v-5], colo[v-4], 0.5);
                  }
            }
      }
}

static EditVert *vert_from_number(EditFace *efa, int nr)
{
      switch(nr) {
      case 0:
            return 0;
      case 1:
            return efa->v1;
      case 2:
            return efa->v2;
      case 3:
            return efa->v3;
      case 4:
            return efa->v4;
      case 5:
            return efa->e1->vn;
      case 6:
            return efa->e2->vn;
      case 7:
            return efa->e3->vn;
      case 8:
            return efa->e4->vn;
      }
      
      return NULL;
}

static void addface_subdiv(EditFace *efa, int val1, int val2, int val3, int val4, EditVert *eve, EditFace *efapin)
{
      EditFace *w;
      EditVert *v1, *v2, *v3, *v4;
      
      if(val1>=9) v1= eve;
      else v1= vert_from_number(efa, val1);
      
      if(val2>=9) v2= eve;
      else v2= vert_from_number(efa, val2);

      if(val3>=9) v3= eve;
      else v3= vert_from_number(efa, val3);

      if(val4>=9) v4= eve;
      else v4= vert_from_number(efa, val4);
      
      w= addfacelist(v1, v2, v3, v4, efa, NULL);
      if(w) {
            if(efa->v4) set_wuv(4, w, val1, val2, val3, val4, efapin);
            else set_wuv(3, w, val1, val2, val3, val4, efapin);
      }
}

static float smoothperc= 0.0;

static void smooth_subdiv_vec(float *v1, float *v2, float *n1, float *n2, float *vec)
{
      float len, fac, nor[3], nor1[3], nor2[3];
      
      VecSubf(nor, v1, v2);
      len= 0.5*Normalise(nor);

      VECCOPY(nor1, n1);
      VECCOPY(nor2, n2);

      /* cosine angle */
      fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
      
      vec[0]= fac*nor1[0];
      vec[1]= fac*nor1[1];
      vec[2]= fac*nor1[2];

      /* cosine angle */
      fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
      
      vec[0]+= fac*nor2[0];
      vec[1]+= fac*nor2[1];
      vec[2]+= fac*nor2[2];

      vec[0]*= smoothperc*len;
      vec[1]*= smoothperc*len;
      vec[2]*= smoothperc*len;
}

static void smooth_subdiv_quad(EditFace *efa, float *vec)
{
      
      float nor1[3], nor2[3];
      float vec1[3], vec2[3];
      float cent[3];
      
      /* vlr->e1->vn is new vertex inbetween v1 / v2 */
      
      VecMidf(nor1, efa->v1->no, efa->v2->no);
      Normalise(nor1);
      VecMidf(nor2, efa->v3->no, efa->v4->no);
      Normalise(nor2);

      smooth_subdiv_vec( efa->e1->vn->co, efa->e3->vn->co, nor1, nor2, vec1);

      VecMidf(nor1, efa->v2->no, efa->v3->no);
      Normalise(nor1);
      VecMidf(nor2, efa->v4->no, efa->v1->no);
      Normalise(nor2);

      smooth_subdiv_vec( efa->e2->vn->co, efa->e4->vn->co, nor1, nor2, vec2);

      VecAddf(vec1, vec1, vec2);

      CalcCent4f(cent, efa->v1->co,  efa->v2->co,  efa->v3->co,  efa->v4->co);
      VecAddf(vec, cent, vec1);
}

void subdivideflag(int flag, float rad, int beauty)
{
      EditMesh *em = G.editMesh;
      /* subdivide all with (vertflag & flag) */
      /* if rad>0.0 it's a 'sphere' subdivide */
      /* if rad<0.0 it's a fractal subdivide */
      extern float doublimit;
      EditVert *eve;
      EditEdge *eed, *e1, *e2, *e3, *e4, *nexted;
      EditFace *efa, efapin;
      float fac, vec[3], vec1[3], len1, len2, len3, percent;
      short test;
      
      if(beauty & B_SMOOTH) {
            short perc= 100;

            if(button(&perc, 10, 500, "Percentage:")==0) return;
            
            smoothperc= 0.292*perc/100.0;
      }

      /* edgeflags */
      if((beauty & B_KNIFE)==0) {         // knife option sets own flags
            eed= em->edges.first;
            while(eed) {      
                  if( (eed->v1->f & flag) && (eed->v2->f & flag) ) eed->f2= flag;
                  else eed->f2= 0;  
                  eed= eed->next;
            }
      }
      
      /* if beauty: test for area and clear edge flags of 'ugly' edges */
      if(beauty & B_BEAUTY) {
            efa= em->faces.first;
            while(efa) {
                  if( faceselectedAND(efa, flag) ) {
                        if(efa->v4) {
                        
                              /* area */
                              len1= AreaQ3Dfl(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
                              if(len1 <= doublimit) {
                                    efa->e1->f2 = 0;
                                    efa->e2->f2 = 0;
                                    efa->e3->f2 = 0;
                                    efa->e4->f2 = 0;
                              }
                              else {
                                    len1= VecLenf(efa->v1->co, efa->v2->co) + VecLenf(efa->v3->co, efa->v4->co);
                                    len2= VecLenf(efa->v2->co, efa->v3->co) + VecLenf(efa->v1->co, efa->v4->co);
                                    
                                    if(len1 < len2) {
                                          efa->e1->f2 = 0;
                                          efa->e3->f2 = 0;
                                    }
                                    else if(len1 > len2) {
                                          efa->e2->f2 = 0;
                                          efa->e4->f2 = 0;
                                    }
                              }
                        }
                        else {
                              /* area */
                              len1= AreaT3Dfl(efa->v1->co, efa->v2->co, efa->v3->co);
                              if(len1 <= doublimit) {
                                    efa->e1->f2 = 0;
                                    efa->e2->f2 = 0;
                                    efa->e3->f2 = 0;
                              }
                              else {
                                    len1= VecLenf(efa->v1->co, efa->v2->co) ;
                                    len2= VecLenf(efa->v2->co, efa->v3->co) ;
                                    len3= VecLenf(efa->v3->co, efa->v1->co) ;
                                    
                                    if(len1<len2 && len1<len3) {
                                          efa->e1->f2 = 0;
                                    }
                                    else if(len2<len3 && len2<len1) {
                                          efa->e2->f2 = 0;
                                    }
                                    else if(len3<len2 && len3<len1) {
                                          efa->e3->f2 = 0;
                                    }
                              }
                        }
                  }
                  efa= efa->next;
            }
      }

      if(beauty & B_SMOOTH) {
            
            vertexnormals(0);       /* no1*/
                  
      }
      
      /* make new normal and put in edge, clear flag! needed for face creation part below */
      eed= em->edges.first;
      while(eed) {
            if(eed->f2 & flag) {
                  /* for now */
                  eed->h &= ~EM_FGON;
            
                  /* Subdivide percentage is stored in 1/32768ths in eed->f1 */
                  if (beauty & B_PERCENTSUBD) percent=(float)(eed->f1)/32768.0;
                  else percent=0.5;
                  
                  vec[0]= (1-percent)*eed->v1->co[0] + percent*eed->v2->co[0];
                  vec[1]= (1-percent)*eed->v1->co[1] + percent*eed->v2->co[1];
                  vec[2]= (1-percent)*eed->v1->co[2] + percent*eed->v2->co[2];

                  if(rad > 0.0) {   /* subdivide sphere */
                        Normalise(vec);
                        vec[0]*= rad;
                        vec[1]*= rad;
                        vec[2]*= rad;
                  }
                  else if(rad< 0.0) {  /* fractal subdivide */
                        fac= rad* VecLenf(eed->v1->co, eed->v2->co);
                        vec1[0]= fac*(0.5-BLI_drand());
                        vec1[1]= fac*(0.5-BLI_drand());
                        vec1[2]= fac*(0.5-BLI_drand());
                        VecAddf(vec, vec, vec1);
                  }
                  
                  if(beauty & B_SMOOTH) {
                        smooth_subdiv_vec(eed->v1->co, eed->v2->co, eed->v1->no, eed->v2->no, vec1);
                        VecAddf(vec, vec, vec1);
                  }
                  
                  eed->vn= addvertlist(vec);
                  eed->vn->f= eed->v1->f;

            }
            else eed->vn= 0;
            
            eed->f2= 0; /* needed! */
            
            eed= eed->next;
      }

      /* test all faces for subdivide edges, there are 8 or 16 cases (ugh)! */

      efa= em->faces.last;
      while(efa) {

            efapin= *efa; /* make a copy of efa to recover uv pinning later */

            if( faceselectedOR(efa, flag) ) {
                  /* for now */
                  efa->fgonf= 0;
                  
                  e1= efa->e1;
                  e2= efa->e2;
                  e3= efa->e3;
                  e4= efa->e4;

                  test= 0;
                  if(e1 && e1->vn) { 
                        test+= 1;
                        e1->f2= 1;
                        /* add edges here, to copy correct edge data */
                        eed= addedgelist(e1->v1, e1->vn, e1);
                        eed= addedgelist(e1->vn, e1->v2, e1);
                  }
                  if(e2 && e2->vn) {
                        test+= 2;
                        e2->f2= 1;
                        /* add edges here, to copy correct edge data */
                        eed= addedgelist(e2->v1, e2->vn, e2);
                        eed= addedgelist(e2->vn, e2->v2, e2);
                  }
                  if(e3 && e3->vn) {
                        test+= 4;
                        e3->f2= 1;
                        /* add edges here, to copy correct edge data */
                        eed= addedgelist(e3->v1, e3->vn, e3);
                        eed= addedgelist(e3->vn, e3->v2, e3);
                  }
                  if(e4 && e4->vn) {
                        test+= 8;
                        e4->f2= 1;
                        /* add edges here, to copy correct edge data */
                        eed= addedgelist(e4->v1, e4->vn, e4);
                        eed= addedgelist(e4->vn, e4->v2, e4);
                  }
                  if(test) {
                        if(efa->v4==0) {  /* All the permutations of 3 edges*/
                              if((test & 3)==3) addface_subdiv(efa, 2, 2+4, 1+4, 0, 0, &efapin);
                              if((test & 6)==6) addface_subdiv(efa, 3, 3+4, 2+4, 0, 0, &efapin);
                              if((test & 5)==5) addface_subdiv(efa, 1, 1+4, 3+4, 0, 0, &efapin);

                              if(test==7) {  /* four new faces, old face renews */
                                    efa->v1= e1->vn;
                                    efa->v2= e2->vn;
                                    efa->v3= e3->vn;
                                    set_wuv(3, efa, 1+4, 2+4, 3+4, 0, &efapin);
                              }
                              else if(test==3) {
                                    addface_subdiv(efa, 1+4, 2+4, 3, 0, 0, &efapin);
                                    efa->v2= e1->vn;
                                    set_wuv(3, efa, 1, 1+4, 3, 0, &efapin);
                              }
                              else if(test==6) {
                                    addface_subdiv(efa, 2+4, 3+4, 1, 0, 0, &efapin);
                                    efa->v3= e2->vn;
                                    set_wuv(3, efa, 1, 2, 2+4, 0, &efapin);
                              }
                              else if(test==5) {
                                    addface_subdiv(efa, 3+4, 1+4, 2, 0, 0, &efapin);
                                    efa->v1= e3->vn;
                                    set_wuv(3, efa, 3+4, 2, 3, 0, &efapin);
                              }
                              else if(test==1) {
                                    addface_subdiv(efa, 1+4, 2, 3, 0, 0, &efapin);
                                    efa->v2= e1->vn;
                                    set_wuv(3, efa, 1, 1+4, 3, 0, &efapin);
                              }
                              else if(test==2) {
                                    addface_subdiv(efa, 2+4, 3, 1, 0, 0, &efapin);
                                    efa->v3= e2->vn;
                                    set_wuv(3, efa, 1, 2, 2+4, 0, &efapin);
                              }
                              else if(test==4) {
                                    addface_subdiv(efa, 3+4, 1, 2, 0, 0, &efapin);
                                    efa->v1= e3->vn;
                                    set_wuv(3, efa, 3+4, 2, 3, 0, &efapin);
                              }
                              efa->e1= addedgelist(efa->v1, efa->v2, NULL);
                              efa->e2= addedgelist(efa->v2, efa->v3, NULL);
                              efa->e3= addedgelist(efa->v3, efa->v1, NULL);

                        }
                        else {  /* All the permutations of 4 faces */
                              if(test==15) {
                                    /* add a new point in center */
                                    CalcCent4f(vec, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
                                    
                                    if(beauty & B_SMOOTH) {
                                          smooth_subdiv_quad(efa, vec); /* adds */
                                    }
                                    eve= addvertlist(vec);
                                    
                                    eve->f |= flag;

                                    addface_subdiv(efa, 2, 2+4, 9, 1+4, eve, &efapin);
                                    addface_subdiv(efa, 3, 3+4, 9, 2+4, eve, &efapin);
                                    addface_subdiv(efa, 4, 4+4, 9, 3+4, eve, &efapin);

                                    efa->v2= e1->vn;
                                    efa->v3= eve;
                                    efa->v4= e4->vn;
                                    set_wuv(4, efa, 1, 1+4, 9, 4+4, &efapin);
                              }
                              else {
                                    if(((test & 3)==3)&&(test!=3)) addface_subdiv(efa, 1+4, 2, 2+4, 0, 0, &efapin);
                                    if(((test & 6)==6)&&(test!=6)) addface_subdiv(efa, 2+4, 3, 3+4, 0, 0, &efapin);
                                    if(((test & 12)==12)&&(test!=12)) addface_subdiv(efa, 3+4, 4, 4+4, 0, 0, &efapin);
                                    if(((test & 9)==9)&&(test!=9)) addface_subdiv(efa, 4+4, 1, 1+4, 0, 0, &efapin);

                                    if(test==1) { /* Edge 1 has new vert */
                                          addface_subdiv(efa, 1+4, 2, 3, 0, 0, &efapin);
                                          addface_subdiv(efa, 1+4, 3, 4, 0, 0, &efapin);
                                          efa->v2= e1->vn;
                                          efa->v3= efa->v4;
                                          efa->v4= 0;
                                          set_wuv(4, efa, 1, 1+4, 4, 0, &efapin);
                                    }
                                    else if(test==2) { /* Edge 2 has new vert */
                                          addface_subdiv(efa, 2+4, 3, 4, 0, 0, &efapin);
                                          addface_subdiv(efa, 2+4, 4, 1, 0, 0, &efapin);
                                          efa->v3= e2->vn;
                                          efa->v4= 0;
                                          set_wuv(4, efa, 1, 2, 2+4, 0, &efapin);
                                    }
                                    else if(test==4) { /* Edge 3 has new vert */
                                          addface_subdiv(efa, 3+4, 4, 1, 0, 0, &efapin);
                                          addface_subdiv(efa, 3+4, 1, 2, 0, 0, &efapin);
                                          efa->v1= efa->v2;
                                          efa->v2= efa->v3;
                                          efa->v3= e3->vn;
                                          efa->v4= 0;
                                          set_wuv(4, efa, 2, 3, 3+4, 0, &efapin);
                                    }
                                    else if(test==8) { /* Edge 4 has new vert */
                                          addface_subdiv(efa, 4+4, 1, 2, 0, 0, &efapin);
                                          addface_subdiv(efa, 4+4, 2, 3, 0, 0, &efapin);
                                          efa->v1= efa->v3;
                                          efa->v2= efa->v4;
                                          efa->v3= e4->vn;
                                          efa->v4= 0;
                                          set_wuv(4, efa, 3, 4, 4+4, 0, &efapin);
                                    }
                                    else if(test==3) { /*edge 1&2 */
                                          /* make new vert in center of new edge */
                                          vec[0]=(e1->vn->co[0]+e2->vn->co[0])/2;
                                          vec[1]=(e1->vn->co[1]+e2->vn->co[1])/2;
                                          vec[2]=(e1->vn->co[2]+e2->vn->co[2])/2;
                                          eve= addvertlist(vec);
                                          eve->f |= flag;
                                          /* Add new faces */
                                          addface_subdiv(efa, 4, 10, 2+4, 3, eve, &efapin);
                                          addface_subdiv(efa, 4, 1, 1+4, 10, eve, &efapin);
                                          /* orig face becomes small corner */
                                          efa->v1=e1->vn;
                                          //efa->v2=efa->v2;
                                          efa->v3=e2->vn;
                                          efa->v4=eve;

                                          set_wuv(4, efa, 1+4, 2, 2+4, 10, &efapin);
                                    }
                                    else if(test==6) { /* 2&3 */
                                          /* make new vert in center of new edge */
                                          vec[0]=(e2->vn->co[0]+e3->vn->co[0])/2;
                                          vec[1]=(e2->vn->co[1]+e3->vn->co[1])/2;
                                          vec[2]=(e2->vn->co[2]+e3->vn->co[2])/2;
                                          eve= addvertlist(vec);
                                          eve->f |= flag;
                                          /*New faces*/
                                          addface_subdiv(efa, 1, 11, 3+4, 4, eve, &efapin);
                                          addface_subdiv(efa, 1, 2, 2+4, 11, eve, &efapin);
                                          /* orig face becomes small corner */
                                          efa->v1=e2->vn;
                                          efa->v2=efa->v3;
                                          efa->v3=e3->vn;
                                          efa->v4=eve;

                                          set_wuv(4, efa, 2+4, 3, 3+4, 11, &efapin);
                                    }
                                    else if(test==12) { /* 3&4 */
                                          /* make new vert in center of new edge */
                                          vec[0]=(e3->vn->co[0]+e4->vn->co[0])/2;
                                          vec[1]=(e3->vn->co[1]+e4->vn->co[1])/2;
                                          vec[2]=(e3->vn->co[2]+e4->vn->co[2])/2;
                                          eve= addvertlist(vec);
                                          eve->f |= flag;
                                          /*New Faces*/
                                          addface_subdiv(efa, 2, 12, 4+4, 1, eve, &efapin);
                                          addface_subdiv(efa, 2, 3, 3+4, 12, eve, &efapin);
                                          /* orig face becomes small corner */
                                          efa->v1=e3->vn;
                                          efa->v2=efa->v4;
                                          efa->v3=e4->vn;
                                          efa->v4=eve;

                                          set_wuv(4, efa, 3+4, 4, 4+4, 12, &efapin);
                                    }
                                    else if(test==9) { /* 4&1 */
                                          /* make new vert in center of new edge */
                                          vec[0]=(e1->vn->co[0]+e4->vn->co[0])/2;
                                          vec[1]=(e1->vn->co[1]+e4->vn->co[1])/2;
                                          vec[2]=(e1->vn->co[2]+e4->vn->co[2])/2;
                                          eve= addvertlist(vec);
                                          eve->f |= flag;
                                          /*New Faces*/
                                          addface_subdiv(efa, 3, 13, 1+4, 2, eve, &efapin);
                                          addface_subdiv(efa, 3, 4,  4+4,13, eve, &efapin);
                                          /* orig face becomes small corner */
                                          efa->v2=efa->v1;
                                          efa->v1=e4->vn;
                                          efa->v3=e1->vn;
                                          efa->v4=eve;

                                          set_wuv(4, efa, 4+4, 1, 1+4, 13, &efapin);
                                    }
                                    else if(test==5) { /* 1&3 */
                                          addface_subdiv(efa, 1+4, 2, 3, 3+4, 0, &efapin);
                                          efa->v2= e1->vn;
                                          efa->v3= e3->vn;
                                          set_wuv(4, efa, 1, 1+4, 3+4, 4, &efapin);
                                    }
                                    else if(test==10) { /* 2&4 */
                                          addface_subdiv(efa, 2+4, 3, 4, 4+4, 0, &efapin);
                                          efa->v3= e2->vn;
                                          efa->v4= e4->vn;
                                          set_wuv(4, efa, 1, 2, 2+4, 4+4, &efapin);
                                    }/* Unfortunately, there is no way to avoid tris on 1 or 3 edges*/
                                    else if(test==7) { /*1,2&3 */
                                          addface_subdiv(efa, 1+4, 2+4, 3+4, 0, 0, &efapin);
                                          efa->v2= e1->vn;
                                          efa->v3= e3->vn;
                                          set_wuv(4, efa, 1, 1+4, 3+4, 4, &efapin);
                                    }
                                    
                                    else if(test==14) { /* 2,3&4 */
                                          addface_subdiv(efa, 2+4, 3+4, 4+4, 0, 0, &efapin);
                                          efa->v3= e2->vn;
                                          efa->v4= e4->vn;
                                          set_wuv(4, efa, 1, 2, 2+4, 4+4, &efapin);
                                    }
                                    else if(test==13) {/* 1,3&4 */
                                          addface_subdiv(efa, 3+4, 4+4, 1+4, 0, 0, &efapin);
                                          efa->v4= e3->vn;
                                          efa->v1= e1->vn;
                                          set_wuv(4, efa, 1+4, 3, 3, 3+4, &efapin);
                                    }
                                    else if(test==11) { /* 1,2,&4 */
                                          addface_subdiv(efa, 4+4, 1+4, 2+4, 0, 0, &efapin);
                                          efa->v1= e4->vn;
                                          efa->v2= e2->vn;
                                          set_wuv(4, efa, 4+4, 2+4, 3, 4, &efapin);
                                    }
                              }
                              efa->e1= addedgelist(efa->v1, efa->v2, NULL);
                              efa->e2= addedgelist(efa->v2, efa->v3, NULL);
                              if(efa->v4) efa->e3= addedgelist(efa->v3, efa->v4, NULL);
                              else efa->e3= addedgelist(efa->v3, efa->v1, NULL);
                              if(efa->v4) efa->e4= addedgelist(efa->v4, efa->v1, NULL);
                              else efa->e4= NULL;
                        }
                  }
            }
            efa= efa->prev;
      }

      /* remove all old edges, if needed make new ones */
      eed= em->edges.first;
      while(eed) {
            nexted= eed->next;
            if( eed->vn ) {
                  eed->vn->f |= 16;             
                  if(eed->f2==0) {  /* not used in face */                    
                        addedgelist(eed->v1, eed->vn, eed);
                        addedgelist(eed->vn, eed->v2, eed);
                  }                                   
                  remedge(eed);
                  free_editedge(eed);
            }
            eed= nexted;
      }
      
      /* since this is all on vertex level, flush vertex selection */
      EM_select_flush();
      recalc_editnormals();
      
      countall();
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
}

static int count_selected_edges(EditEdge *ed)
{
      int totedge = 0;
      while(ed) {
            ed->vn= 0;
            if( ed->f & SELECT ) totedge++;
            ed= ed->next;
      }
      return totedge;
}

/* hurms, as if this makes code readable! It's pointerpointer hiding... (ton) */
typedef EditFace *EVPtr;
typedef EVPtr EVPTuple[2];

/** builds EVPTuple array efaa of face tuples (in fact pointers to EditFaces)
    sharing one edge.
      arguments: selected edge list, face list.
      Edges will also be tagged accordingly (see eed->f2)          */

static int collect_quadedges(EVPTuple *efaa, EditEdge *eed, EditFace *efa)
{
      int i = 0;
      EditEdge *e1, *e2, *e3;
      EVPtr *evp;

      /* run through edges, if selected, set pointer edge-> facearray */
      while(eed) {
            eed->f2= 0;
            eed->f1= 0;
            if( eed->f & SELECT ) {
                  eed->vn= (EditVert *) (&efaa[i]);
                  i++;
            }
            eed= eed->next;
      }
            
      
      /* find edges pointing to 2 faces by procedure:
      
      - run through faces and their edges, increase
        face counter e->f1 for each face 
      */

      while(efa) {
            efa->f1= 0;
            if(efa->v4==0) {  /* if triangle */
                  if(efa->f & SELECT) {
                        
                        e1= efa->e1;
                        e2= efa->e2;
                        e3= efa->e3;
                        if(e1->f2<3) {
                              if(e1->f2<2) {
                                    evp= (EVPtr *) e1->vn;
                                    evp[(int)e1->f2]= efa;
                              }
                              e1->f2+= 1;
                        }
                        if(e2->f2<3) {
                              if(e2->f2<2) {
                                    evp= (EVPtr *) e2->vn;
                                    evp[(int)e2->f2]= efa;
                              }
                              e2->f2+= 1;
                        }
                        if(e3->f2<3) {
                              if(e3->f2<2) {
                                    evp= (EVPtr *) e3->vn;
                                    evp[(int)e3->f2]= efa;
                              }
                              e3->f2+= 1;
                        }
                  }
            }
            efa= efa->next;
      }
      return i;
}


/* returns vertices of two adjacent triangles forming a quad 
   - can be righthand or lefthand

                  4-----3
                  |\    |
                  | \ 2 | <- efa1
                  |  \  | 
        efa-> | 1 \ | 
                  |    \| 
                  1-----2

*/
#define VTEST(face, num, other) \
      (face->v##num != other->v1 && face->v##num != other->v2 && face->v##num != other->v3) 

static void givequadverts(EditFace *efa, EditFace *efa1, EditVert **v1, EditVert **v2, EditVert **v3, EditVert **v4, float **uv, unsigned int *col)
{
      if VTEST(efa, 1, efa1) {
      //if(efa->v1!=efa1->v1 && efa->v1!=efa1->v2 && efa->v1!=efa1->v3) {
            *v1= efa->v1;
            *v2= efa->v2;
            uv[0] = efa->tf.uv[0];
            uv[1] = efa->tf.uv[1];
            col[0] = efa->tf.col[0];
            col[1] = efa->tf.col[1];
      }
      else if VTEST(efa, 2, efa1) {
      //else if(efa->v2!=efa1->v1 && efa->v2!=efa1->v2 && efa->v2!=efa1->v3) {
            *v1= efa->v2;
            *v2= efa->v3;
            uv[0] = efa->tf.uv[1];
            uv[1] = efa->tf.uv[2];
            col[0] = efa->tf.col[1];
            col[1] = efa->tf.col[2];
      }
      else if VTEST(efa, 3, efa1) {
      // else if(efa->v3!=efa1->v1 && efa->v3!=efa1->v2 && efa->v3!=efa1->v3) {
            *v1= efa->v3;
            *v2= efa->v1;
            uv[0] = efa->tf.uv[2];
            uv[1] = efa->tf.uv[0];
            col[0] = efa->tf.col[2];
            col[1] = efa->tf.col[0];
      }
      
      if VTEST(efa1, 1, efa) {
      // if(efa1->v1!=efa->v1 && efa1->v1!=efa->v2 && efa1->v1!=efa->v3) {
            *v3= efa1->v1;
            uv[2] = efa1->tf.uv[0];
            col[2] = efa1->tf.col[0];

            *v4= efa1->v2;
            uv[3] = efa1->tf.uv[1];
            col[3] = efa1->tf.col[1];
/*
if(efa1->v2== *v2) {
                  *v4= efa1->v3;
                  uv[3] = efa1->tf.uv[2];
            } else {
                  *v4= efa1->v2;
                  uv[3] = efa1->tf.uv[1];
            }     
            */
      }
      else if VTEST(efa1, 2, efa) {
      // else if(efa1->v2!=efa->v1 && efa1->v2!=efa->v2 && efa1->v2!=efa->v3) {
            *v3= efa1->v2;
            uv[2] = efa1->tf.uv[1];
            col[2] = efa1->tf.col[1];

            *v4= efa1->v3;
            uv[3] = efa1->tf.uv[2];
            col[3] = efa1->tf.col[2];
/*
if(efa1->v3== *v2) {
                  *v4= efa1->v1;
                  uv[3] = efa1->tf.uv[0];
            } else {    
                  *v4= efa1->v3;
                  uv[3] = efa1->tf.uv[2];
            }     
            */
      }
      else if VTEST(efa1, 3, efa) {
      // else if(efa1->v3!=efa->v1 && efa1->v3!=efa->v2 && efa1->v3!=efa->v3) {
            *v3= efa1->v3;
            uv[2] = efa1->tf.uv[2];
            col[2] = efa1->tf.col[2];

            *v4= efa1->v1;
            uv[3] = efa1->tf.uv[0];
            col[3] = efa1->tf.col[0];
/*
if(efa1->v1== *v2) {
                  *v4= efa1->v2;
                  uv[3] = efa1->tf.uv[3];
            } else {    
                  *v4= efa1->v1;
                  uv[3] = efa1->tf.uv[0];
            }     
            */
      }
      else {
            *v3= *v4= NULL;
            
            printf("error in givequadverts()\n");
            return;
      }
      
}

/* Helper functions for edge/quad edit features*/

static void untag_edges(EditFace *f)
{
      f->e1->f2 = 0;
      f->e2->f2 = 0;
      if (f->e3) f->e3->f2 = 0;
      if (f->e4) f->e4->f2 = 0;
}

/** remove and free list of tagged edges */
static void free_tagged_edgelist(EditEdge *eed)
{
      EditEdge *nexted;

      while(eed) {
            nexted= eed->next;
            if(eed->f1) {
                  remedge(eed);
                  free_editedge(eed);
            }
            eed= nexted;
      }     
}     
/** remove and free list of tagged faces */

static void free_tagged_facelist(EditFace *efa)
{     
      EditMesh *em = G.editMesh;
      EditFace *nextvl;

      while(efa) {
            nextvl= efa->next;
            if(efa->f1) {
                  BLI_remlink(&em->faces, efa);
                  free_editface(efa);
            }
            efa= nextvl;
      }
}     


void beauty_fill(void)
{
    EditMesh *em = G.editMesh;
    EditVert *v1, *v2, *v3, *v4;
    EditEdge *eed, *nexted;
    EditEdge dia1, dia2;
    EditFace *efa, *w;
    // void **efaar, **efaa;
    EVPTuple *efaar;
    EVPtr *efaa;
    float *uv[4];
    unsigned int col[4];
    float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
    int totedge, ok, notbeauty=8, onedone;

      /* - all selected edges with two faces
            * - find the faces: store them in edges (using datablock)
            * - per edge: - test convex
            *                    - test edge: flip?
            *               - if true: remedge,  addedge, all edges at the edge get new face pointers
            */
      
      EM_selectmode_flush();  // makes sure in selectmode 'face' the edges of selected faces are selected too 

    totedge = count_selected_edges(em->edges.first);
    if(totedge==0) return;

    if(okee("Beautify fill")==0) return;
    
    /* temp block with face pointers */
    efaar= (EVPTuple *) MEM_callocN(totedge * sizeof(EVPTuple), "beautyfill");

    while (notbeauty) {
        notbeauty--;

        ok = collect_quadedges(efaar, em->edges.first, em->faces.first);

        /* there we go */
        onedone= 0;

        eed= em->edges.first;
        while(eed) {
            nexted= eed->next;

            if(eed->f2==2) {

                efaa = (EVPtr *) eed->vn;

                /* none of the faces should be treated before */
                ok= 1;
                efa= efaa[0];
                if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
                efa= efaa[1];
                if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;

                if(ok) {
                    /* test convex */
                    givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, uv, col);
                    if( convex(v1->co, v2->co, v3->co, v4->co) ) {

                        /* test edges */
                        if( ((long)v1) > ((long)v3) ) {
                            dia1.v1= v3;
                            dia1.v2= v1;
                        }
                        else {
                            dia1.v1= v1;
                            dia1.v2= v3;
                        }

                        if( ((long)v2) > ((long)v4) ) {
                            dia2.v1= v4;
                            dia2.v2= v2;
                        }
                        else {
                            dia2.v1= v2;
                            dia2.v2= v4;
                        }

                        /* testing rule:
                         * the area divided by the total edge lengths
                         */

                        len1= VecLenf(v1->co, v2->co);
                        len2= VecLenf(v2->co, v3->co);
                        len3= VecLenf(v3->co, v4->co);
                        len4= VecLenf(v4->co, v1->co);
                        len5= VecLenf(v1->co, v3->co);
                        len6= VecLenf(v2->co, v4->co);

                        opp1= AreaT3Dfl(v1->co, v2->co, v3->co);
                        opp2= AreaT3Dfl(v1->co, v3->co, v4->co);

                        fac1= opp1/(len1+len2+len5) + opp2/(len3+len4+len5);

                        opp1= AreaT3Dfl(v2->co, v3->co, v4->co);
                        opp2= AreaT3Dfl(v2->co, v4->co, v1->co);

                        fac2= opp1/(len2+len3+len6) + opp2/(len4+len1+len6);

                        ok= 0;
                        if(fac1 > fac2) {
                            if(dia2.v1==eed->v1 && dia2.v2==eed->v2) {
                                eed->f1= 1;
                                efa= efaa[0];
                                efa->f1= 1;
                                efa= efaa[1];
                                efa->f1= 1;

                                w= addfacelist(v1, v2, v3, 0, efa, NULL);

                                                UVCOPY(w->tf.uv[0], uv[0]);
                                                UVCOPY(w->tf.uv[1], uv[1]);
                                                UVCOPY(w->tf.uv[2], uv[2]);

                                w->tf.col[0] = col[0]; w->tf.col[1] = col[1]; w->tf.col[2] = col[2];
                                w= addfacelist(v1, v3, v4, 0, efa, NULL);

                                                UVCOPY(w->tf.uv[0], uv[0]);
                                                UVCOPY(w->tf.uv[1], uv[2]);
                                                UVCOPY(w->tf.uv[2], uv[3]);

                                w->tf.col[0] = col[0]; w->tf.col[1] = col[2]; w->tf.col[2] = col[3];

                                onedone= 1;
                            }
                        }
                        else if(fac1 < fac2) {
                            if(dia1.v1==eed->v1 && dia1.v2==eed->v2) {
                                eed->f1= 1;
                                efa= efaa[0];
                                efa->f1= 1;
                                efa= efaa[1];
                                efa->f1= 1;

                                w= addfacelist(v2, v3, v4, 0, efa, NULL);

                                                UVCOPY(w->tf.uv[0], uv[1]);
                                                UVCOPY(w->tf.uv[1], uv[3]);
                                                UVCOPY(w->tf.uv[2], uv[4]);

                                w= addfacelist(v1, v2, v4, 0, efa, NULL);

                                                UVCOPY(w->tf.uv[0], uv[0]);
                                                UVCOPY(w->tf.uv[1], uv[1]);
                                                UVCOPY(w->tf.uv[2], uv[3]);

                                onedone= 1;
                            }
                        }
                    }
                }

            }
            eed= nexted;
        }

        free_tagged_edgelist(em->edges.first);
        free_tagged_facelist(em->faces.first);

        if(onedone==0) break;
    }

    MEM_freeN(efaar);

      EM_select_flush();
      
    allqueue(REDRAWVIEW3D, 0);
    makeDispList(G.obedit);
      BIF_undo_push("Beauty Fill");
}


/* ******************** FLIP EDGE ************************************* */


#define FACE_MARKCLEAR(f) (f->f1 = 1)

void join_triangles(void)
{
      EditMesh *em = G.editMesh;
      EditVert *v1, *v2, *v3, *v4;
      EditFace *efa, *w;
      EVPTuple *efaar;
      EVPtr *efaa;
      EditEdge *eed, *nexted;
      int totedge, ok;
      float *uv[4];
      unsigned int col[4];

      EM_selectmode_flush();  // makes sure in selectmode 'face' the edges of selected faces are selected too 
      
      totedge = count_selected_edges(em->edges.first);
      if(totedge==0) return;

      efaar= (EVPTuple *) MEM_callocN(totedge * sizeof(EVPTuple), "jointris");

      ok = collect_quadedges(efaar, em->edges.first, em->faces.first);
      if (G.f & G_DEBUG) {
            printf("Edges selected: %d\n", ok);
      }     

      eed= em->edges.first;
      while(eed) {
            nexted= eed->next;
            
            if(eed->f2==2) {  /* points to 2 faces */
                  
                  efaa= (EVPtr *) eed->vn;
                  
                  /* don't do it if flagged */

                  ok= 1;
                  efa= efaa[0];
                  if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
                  efa= efaa[1];
                  if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
                  
                  if(ok) {
                        /* test convex */
                        givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, uv, col);

/*
            4-----3        4-----3
            |\    |        |     |
            | \ 1 |        |     |
            |  \  |  ->    |     |  
            | 0 \ |        |     | 
            |    \|        |     |
            1-----2        1-----2
*/
                        /* make new faces */
                        if( convex(v1->co, v2->co, v3->co, v4->co) ) {
                              if(exist_face(v1, v2, v3, v4)==0) {
                                    w = addfacelist(v1, v2, v3, v4, efaa[0], NULL); /* seam edge may get broken */
                                    w->f= efaa[0]->f; /* copy selection flag */
                                    untag_edges(w);

                                    UVCOPY(w->tf.uv[0], uv[0]);
                                    UVCOPY(w->tf.uv[1], uv[1]);
                                    UVCOPY(w->tf.uv[2], uv[2]);
                                    UVCOPY(w->tf.uv[3], uv[3]);

                                    memcpy(w->tf.col, col, sizeof(w->tf.col));
                              }
                              /* tag as to-be-removed */
                              FACE_MARKCLEAR(efaa[0]);
                              FACE_MARKCLEAR(efaa[1]);
                              eed->f1 = 1; 
                        } /* endif test convex */
                  }
            }
            eed= nexted;
      }
      free_tagged_edgelist(em->edges.first);
      free_tagged_facelist(em->faces.first);

      MEM_freeN(efaar);
      
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      BIF_undo_push("Convert Triangles to Quads");
}

/* quick hack, basically a copy of beauty_fill */
void edge_flip(void)
{
      EditMesh *em = G.editMesh;
      EditVert *v1, *v2, *v3, *v4;
      EditEdge *eed, *nexted;
      EditFace *efa, *w;
      //void **efaar, **efaa;
      EVPTuple *efaar;
      EVPtr *efaa;

      float *uv[4];
      unsigned int col[4];

      int totedge, ok;
      
      /* - all selected edges with two faces
       * - find the faces: store them in edges (using datablock)
       * - per edge: - test convex
       *                   - test edge: flip?
                                    - if true: remedge,  addedge, all edges at the edge get new face pointers
       */

      EM_selectmode_flush();  // makes sure in selectmode 'face' the edges of selected faces are selected too 

      totedge = count_selected_edges(em->edges.first);
      if(totedge==0) return;

      /* temporary array for : edge -> face[1], face[2] */
      efaar= (EVPTuple *) MEM_callocN(totedge * sizeof(EVPTuple), "edgeflip");

      ok = collect_quadedges(efaar, em->edges.first, em->faces.first);
      
      eed= em->edges.first;
      while(eed) {
            nexted= eed->next;
            
            if(eed->f2==2) {  /* points to 2 faces */
                  
                  efaa= (EVPtr *) eed->vn;
                  
                  /* don't do it if flagged */

                  ok= 1;
                  efa= efaa[0];
                  if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
                  efa= efaa[1];
                  if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
                  
                  if(ok) {
                        /* test convex */
                        givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, uv, col);

/*
            4-----3        4-----3
            |\    |        |    /|
            | \ 1 |        | 1 / |
            |  \  |  ->    |  /  |  
            | 0 \ |        | / 0 | 
            |    \|        |/    |
            1-----2        1-----2
*/
                        /* make new faces */
                        if (v1 && v2 && v3){
                              if( convex(v1->co, v2->co, v3->co, v4->co) ) {
                                    if(exist_face(v1, v2, v3, v4)==0) {
                                          w = addfacelist(v1, v2, v3, 0, efaa[1], NULL); /* outch this may break seams */ 
                                          EM_select_face(w, 1);
                                          untag_edges(w);

                                          UVCOPY(w->tf.uv[0], uv[0]);
                                          UVCOPY(w->tf.uv[1], uv[1]);
                                          UVCOPY(w->tf.uv[2], uv[2]);

                                          w->tf.col[0] = col[0]; w->tf.col[1] = col[1]; w->tf.col[2] = col[2]; 
                                          
                                          w = addfacelist(v1, v3, v4, 0, efaa[1], NULL); /* outch this may break seams */
                                          EM_select_face(w, 1);
                                          untag_edges(w);

                                          UVCOPY(w->tf.uv[0], uv[0]);
                                          UVCOPY(w->tf.uv[1], uv[2]);
                                          UVCOPY(w->tf.uv[2], uv[3]);

                                          w->tf.col[0] = col[0]; w->tf.col[1] = col[2]; w->tf.col[2] = col[3]; 
                                          
                                          /* erase old faces and edge */
                                    }
                                    /* tag as to-be-removed */
                                    FACE_MARKCLEAR(efaa[1]);
                                    FACE_MARKCLEAR(efaa[0]);
                                    eed->f1 = 1; 
                                    
                              } /* endif test convex */
                        }
                  }
            }
            eed= nexted;
      }

      /* clear tagged edges and faces: */
      free_tagged_edgelist(em->edges.first);
      free_tagged_facelist(em->faces.first);
      
      MEM_freeN(efaar);
      
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      BIF_undo_push("Flip Triangle Edges");
      
}

static void edge_rotate(EditEdge *eed)
{
      EditMesh *em = G.editMesh;
      EditFace *face[2], *efa, *newFace[2];
      EditVert *faces[2][4],*v1,*v2,*v3,*v4,*vtemp;
      short facecount=0, p1=0,p2=0,p3=0,p4=0,fac1=4,fac2=4,i,j;

      /* check to make sure that the edge is only part of 2 faces */
      for(efa = em->faces.first;efa;efa = efa->next){
            if((efa->e1 == eed || efa->e2 == eed) || (efa->e3 == eed || efa->e4 == eed)){
                  if(facecount == 2){
                        return;
                  }
                  if(facecount < 2)
                        face[facecount] = efa;
                  facecount++;
            }
      }
 
      if(facecount < 2){
            return;
      }

      /* how many edges does each face have */
      if(face[0]->e4 == NULL)
            fac1=3;
      else
            fac1=4;
      if(face[1]->e4 == NULL)
            fac2=3;
      else
            fac2=4;
      
      /*store the face info in a handy array */             
      faces[0][0] =  face[0]->v1;
      faces[0][1] =  face[0]->v2;
      faces[0][2] =  face[0]->v3;
      if(face[0]->e4 != NULL)
            faces[0][3] =  face[0]->v4;
      else
            faces[0][3] = NULL;
                  
      faces[1][0] =  face[1]->v1;
      faces[1][1] =  face[1]->v2;
      faces[1][2] =  face[1]->v3;
      if(face[1]->e4 != NULL)
            faces[1][3] =  face[1]->v4;
      else
            faces[1][3] = NULL;
      

      /* we don't want to rotate edges between faces that share more than one edge */
      
      j=0;
      if(face[0]->e1 == face[1]->e1 ||
         face[0]->e1 == face[1]->e2 ||
         face[0]->e1 == face[1]->e3 ||
         ((face[1]->e4) && face[0]->e1 == face[1]->e4) )
         j++;
         
      if(face[0]->e2 == face[1]->e1 ||
         face[0]->e2 == face[1]->e2 ||
         face[0]->e2 == face[1]->e3 ||
         ((face[1]->e4) && face[0]->e2 == face[1]->e4) )
         j++;
         
      if(face[0]->e3 == face[1]->e1 ||
         face[0]->e3 == face[1]->e2 ||
         face[0]->e3 == face[1]->e3 ||
         ((face[1]->e4) && face[0]->e3 == face[1]->e4) )
         j++;        

      if(face[0]->e4){
            if(face[0]->e4 == face[1]->e1 ||
               face[0]->e4 == face[1]->e2 ||
               face[0]->e4 == face[1]->e3 ||
               ((face[1]->e4) && face[0]->e4 == face[1]->e4) )
                     j++;     
       }             
      if(j > 1){
            return;
      }
      
      /* Coplaner Faces Only Please */
      if(Inpf(face[0]->n,face[1]->n) <= 0.000001){    
            return;
      }
      
      /*get the edges verts */
      v1 = eed->v1;
      v2 = eed->v2;
      v3 = eed->v1;
      v4 = eed->v2;

      /*figure out where the edges verts lie one the 2 faces */
      for(i=0;i<4;i++){
            if(v1 == faces[0][i])
                  p1 = i;
            if(v2 == faces[0][i])
                  p2 = i;
            if(v1 == faces[1][i])
                  p3 = i;
            if(v2 == faces[1][i])
                  p4 = i;
      }
      
      /*make sure the verts are in the correct order */
      if((p1+1)%fac1 == p2){
            vtemp = v2;
            v2 = v1;
            v1 = vtemp;
            
            i = p1;
            p1 = p2;
            p2 = i;
      }
      if((p3+1)%fac2 == p4){
            vtemp = v4;
            v4 = v3;
            v3 = vtemp;
            
            i = p3;
            p3 = p4;
            p4 = i;     
      }     

                              
                                          
      /* create the 2 new faces */                                                  
      if(fac1 == 3 && fac2 == 3){
            newFace[0] = addfacelist(faces[0][(p1+1)%3],faces[0][(p1+2)%3],faces[1][(p3+1)%3],NULL,NULL,NULL);
            newFace[1] = addfacelist(faces[1][(p3+1)%3],faces[1][(p3+2)%3],faces[0][(p1+1)%3],NULL,NULL,NULL);
      
            newFace[0]->tf.col[0] = face[0]->tf.col[(p1+1)%3];
            newFace[0]->tf.col[1] = face[0]->tf.col[(p1+2)%3];
            newFace[0]->tf.col[2] = face[1]->tf.col[(p3+1)%3];
            newFace[1]->tf.col[0] = face[1]->tf.col[(p3+1)%3];
            newFace[1]->tf.col[1] = face[1]->tf.col[(p3+2)%3];
            newFace[1]->tf.col[2] = face[0]->tf.col[(p1+1)%3];
      
            UVCOPY(newFace[0]->tf.uv[0],face[0]->tf.uv[(p1+1)%3]);
            UVCOPY(newFace[0]->tf.uv[1],face[0]->tf.uv[(p1+2)%3]);      
            UVCOPY(newFace[0]->tf.uv[2],face[1]->tf.uv[(p3+1)%3]);
            UVCOPY(newFace[1]->tf.uv[0],face[1]->tf.uv[(p3+1)%3]);
            UVCOPY(newFace[1]->tf.uv[1],face[1]->tf.uv[(p3+2)%3]);
            UVCOPY(newFace[1]->tf.uv[2],face[0]->tf.uv[(p1+1)%3]);
      }
      else if(fac1 == 4 && fac2 == 3){
            newFace[0] = addfacelist(faces[0][(p1+1)%4],faces[0][(p1+2)%4],faces[0][(p1+3)%4],faces[1][(p3+1)%3],NULL,NULL);
            newFace[1] = addfacelist(faces[1][(p3+1)%3],faces[1][(p3+2)%3],faces[0][(p1+1)%4],NULL,NULL,NULL);

            newFace[0]->tf.col[0] = face[0]->tf.col[(p1+1)%4];
            newFace[0]->tf.col[1] = face[0]->tf.col[(p1+2)%4];
            newFace[0]->tf.col[2] = face[0]->tf.col[(p1+3)%4];
            newFace[0]->tf.col[3] = face[1]->tf.col[(p3+1)%3];
            newFace[1]->tf.col[0] = face[1]->tf.col[(p3+1)%3];
            newFace[1]->tf.col[1] = face[1]->tf.col[(p3+2)%3];
            newFace[1]->tf.col[2] = face[0]->tf.col[(p1+1)%4];

            UVCOPY(newFace[0]->tf.uv[0],face[0]->tf.uv[(p1+1)%4]);
            UVCOPY(newFace[0]->tf.uv[1],face[0]->tf.uv[(p1+2)%4]);      
            UVCOPY(newFace[0]->tf.uv[2],face[0]->tf.uv[(p1+3)%4]);            
            UVCOPY(newFace[0]->tf.uv[3],face[1]->tf.uv[(p3+1)%3]);
            UVCOPY(newFace[1]->tf.uv[0],face[1]->tf.uv[(p3+1)%3]);
            UVCOPY(newFace[1]->tf.uv[1],face[1]->tf.uv[(p3+2)%3]);
            UVCOPY(newFace[1]->tf.uv[2],face[0]->tf.uv[(p1+1)%4]);      
      }

      else if(fac1 == 3 && fac2 == 4){
            newFace[0] = addfacelist(faces[0][(p1+1)%3],faces[0][(p1+2)%3],faces[1][(p3+1)%4],NULL,NULL,NULL);
            newFace[1] = addfacelist(faces[1][(p3+1)%4],faces[1][(p3+2)%4],faces[1][(p3+3)%4],faces[0][(p1+1)%3],NULL,NULL);

            newFace[0]->tf.col[0] = face[0]->tf.col[(p1+1)%3];
            newFace[0]->tf.col[1] = face[0]->tf.col[(p1+2)%3];
            newFace[0]->tf.col[2] = face[1]->tf.col[(p3+1)%4];
            newFace[1]->tf.col[0] = face[1]->tf.col[(p3+1)%4];
            newFace[1]->tf.col[1] = face[1]->tf.col[(p3+2)%4];
            newFace[1]->tf.col[2] = face[1]->tf.col[(p3+3)%4];          
            newFace[1]->tf.col[3] = face[0]->tf.col[(p1+1)%3];

            UVCOPY(newFace[0]->tf.uv[0],face[0]->tf.uv[(p1+1)%3]);
            UVCOPY(newFace[0]->tf.uv[1],face[0]->tf.uv[(p1+2)%3]);      
            UVCOPY(newFace[0]->tf.uv[2],face[1]->tf.uv[(p3+1)%4]);
            UVCOPY(newFace[1]->tf.uv[0],face[1]->tf.uv[(p3+1)%4]);
            UVCOPY(newFace[1]->tf.uv[1],face[1]->tf.uv[(p3+2)%4]);
            UVCOPY(newFace[1]->tf.uv[2],face[1]->tf.uv[(p3+3)%4]);
            UVCOPY(newFace[1]->tf.uv[3],face[0]->tf.uv[(p1+1)%3]);
      
      }
      
      else if(fac1 == 4 && fac2 == 4){
            newFace[0] = addfacelist(faces[0][(p1+1)%4],faces[0][(p1+2)%4],faces[0][(p1+3)%4],faces[1][(p3+1)%4],NULL,NULL);
            newFace[1] = addfacelist(faces[1][(p3+1)%4],faces[1][(p3+2)%4],faces[1][(p3+3)%4],faces[0][(p1+1)%4],NULL,NULL);

            newFace[0]->tf.col[0] = face[0]->tf.col[(p1+1)%4];
            newFace[0]->tf.col[1] = face[0]->tf.col[(p1+2)%4];
            newFace[0]->tf.col[2] = face[0]->tf.col[(p1+3)%4];
            newFace[0]->tf.col[3] = face[1]->tf.col[(p3+1)%4];
            newFace[1]->tf.col[0] = face[1]->tf.col[(p3+1)%4];
            newFace[1]->tf.col[1] = face[1]->tf.col[(p3+2)%4];
            newFace[1]->tf.col[2] = face[1]->tf.col[(p3+3)%4];          
            newFace[1]->tf.col[3] = face[0]->tf.col[(p1+1)%4];
                                                
            UVCOPY(newFace[0]->tf.uv[0],face[0]->tf.uv[(p1+1)%4]);
            UVCOPY(newFace[0]->tf.uv[1],face[0]->tf.uv[(p1+2)%4]);      
            UVCOPY(newFace[0]->tf.uv[2],face[0]->tf.uv[(p1+3)%4]);            
            UVCOPY(newFace[0]->tf.uv[3],face[1]->tf.uv[(p3+1)%4]);
            UVCOPY(newFace[1]->tf.uv[0],face[1]->tf.uv[(p3+1)%4]);
            UVCOPY(newFace[1]->tf.uv[1],face[1]->tf.uv[(p3+2)%4]);
            UVCOPY(newFace[1]->tf.uv[2],face[1]->tf.uv[(p3+3)%4]);
            UVCOPY(newFace[1]->tf.uv[3],face[0]->tf.uv[(p1+1)%4]);      
      }           
      else{
            /*This should never happen*/
            return;
      }
      
      /* copy flags and material */
      newFace[0]->flag= face[0]->flag;
      newFace[1]->flag= face[1]->flag;
      newFace[0]->mat_nr= face[0]->mat_nr;
      newFace[1]->mat_nr= face[1]->mat_nr;

      /* redo the vertex selection */
      faces[0][(p1+1)%fac1]->f |= SELECT;
      faces[1][(p3+1)%fac2]->f |= SELECT; 
      
      /* get rid of the old edge and faces*/
      remedge(eed);
      free_editedge(eed);     
      BLI_remlink(&em->faces, face[0]);
      free_editface(face[0]); 
      BLI_remlink(&em->faces, face[1]);
      free_editface(face[1]); 
      
      return;                                                                                                                                                                                                                                                                                                                                                                                   
}                                   

/* only accepts 1 selected edge, or 2 selected faces */
void edge_rotate_selected()
{
      EditEdge *eed;
      EditFace *efa;
      short edgeCount = 0;
      
      /*clear new flag for new edges, count selected edges */
      for(eed= G.editMesh->edges.first; eed; eed= eed->next){
            eed->f1= 0;
            eed->f2 &= ~2;
            if(eed->f & SELECT) edgeCount++;    
      }
      
      if(edgeCount>1) {
            /* more selected edges, check faces */
            for(efa= G.editMesh->faces.first; efa; efa= efa->next) {
                  if(efa->f & SELECT) {
                        efa->e1->f1++;
                        efa->e2->f1++;
                        efa->e3->f1++;
                        if(efa->e4) efa->e4->f1++;
                  }
            }
            edgeCount= 0;
            for(eed= G.editMesh->edges.first; eed; eed= eed->next) {
                  if(eed->f1==2) edgeCount++;
            }
            if(edgeCount==1) {
                  for(eed= G.editMesh->edges.first; eed; eed= eed->next) {
                        if(eed->f1==2) {
                              edge_rotate(eed);
                              break;
                        }
                  }
            }
            else error("Select one edge or two adjacent faces");
      }
      else if(edgeCount==1) {
            for(eed= G.editMesh->edges.first; eed; eed= eed->next) {
                  if(eed->f & SELECT) {
                        EM_select_edge(eed, 0);
                        edge_rotate(eed);
                        break;
                  }
            }
      }
      else error("Select one edge or two adjacent faces");
      

      /* flush selected vertices (again) to edges/faces */
      EM_select_flush();
      
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      
      BIF_undo_push("Rotate Edge"); 
}

/******************* BEVEL CODE STARTS HERE ********************/

void bevel_displace_vec(float *midvec, float *v1, float *v2, float *v3, float d, float no[3])
{
      float a[3], c[3], n_a[3], n_c[3], mid[3], ac, ac2, fac;

      VecSubf(a, v1, v2);
      VecSubf(c, v3, v2);

      Crossf(n_a, a, no);
      Normalise(n_a);
      Crossf(n_c, no, c);
      Normalise(n_c);

      Normalise(a);
      Normalise(c);
      ac = Inpf(a, c);

      if (ac == 1 || ac == -1) {
            midvec[0] = midvec[1] = midvec[2] = 0;
            return;
      }
      ac2 = ac * ac;
      fac = sqrt((ac2 + 2*ac + 1)/(1 - ac2) + 1);
      VecAddf(mid, n_c, n_a);
      Normalise(mid);
      VecMulf(mid, d * fac);
      VecAddf(mid, mid, v2);
      VecCopyf(midvec, mid);
}

/*    Finds the new point using the sinus law to extrapolate a triangle
      Lots of sqrts which would not be good for a real time algo
      Using the mid  point of the extrapolation of both sides 
      Useless for coplanar quads, but that doesn't happen too often */
void fix_bevel_wrap(float *midvec, float *v1, float *v2, float *v3, float *v4, float d, float no[3]) 
{
      float a[3], b[3], c[3], l_a, l_b, l_c, s_a, s_b, s_c, Pos1[3], Pos2[3], Dir[3];

      VecSubf(a, v3, v2);
      l_a = Normalise(a);
      VecSubf(b, v4, v3);
      Normalise(b);
      VecSubf(c, v1, v2);
      Normalise(c);

      s_b = Inpf(a, c);
      s_b = sqrt(1 - (s_b * s_b));
      s_a = Inpf(b, c);
      s_a = sqrt(1 - (s_a * s_a));
      VecMulf(a, -1);
      s_c = Inpf(a, b);
      s_c = sqrt(1 - (s_c * s_c));

      l_b = s_b * l_a / s_a;
      l_c = s_c * l_a / s_a;

      VecMulf(b, l_b);
      VecMulf(c, l_c);

      VecAddf(Pos1, v2, c);
      VecAddf(Pos2, v3, b);

      VecAddf(Dir, Pos1, Pos2);
      VecMulf(Dir, 0.5);

      bevel_displace_vec(midvec, v3, Dir, v2, d, no);

}


char detect_wrap(float *o_v1, float *o_v2, float *v1, float *v2, float *no) 
{
      float o_a[3], a[3], o_c[3], c[3];

      VecSubf(o_a, o_v1, o_v2);
      VecSubf(a, v1, v2);

      Crossf(o_c, o_a, no);
      Crossf(c, a, no);

      if (Inpf(c, o_c) <= 0)
            return 1;
      else
            return 0;
}

// Detects and fix a quad wrapping after the resize
// Arguments are the orginal verts followed by the final verts and then the bevel size and the normal
void fix_bevel_quad_wrap(float *o_v1, float *o_v2, float *o_v3, float *o_v4, float *v1, float *v2, float *v3, float *v4, float d, float *no) 
{
      float vec[3];
      char wrap[4];
      
      // Quads can wrap partially. Watch out
      wrap[0] = detect_wrap(o_v1, o_v2, v1, v2, no); // Edge 1-2
      wrap[1] = detect_wrap(o_v2, o_v3, v2, v3, no); // Edge 2-3
      wrap[2] = detect_wrap(o_v3, o_v4, v3, v4, no); // Edge 3-4
      wrap[3] = detect_wrap(o_v4, o_v1, v4, v1, no); // Edge 4-1

      // Edge 1 inverted
      if (wrap[0] == 1 && wrap[1] == 0 && wrap[2] == 0 && wrap[3] == 0) {
            fix_bevel_wrap(vec, o_v2, o_v3, o_v4, o_v1, d, no);
            VECCOPY(v1, vec);
            VECCOPY(v2, vec);
      }
      // Edge 2 inverted
      else if (wrap[0] == 0 && wrap[1] == 1 && wrap[2] == 0 && wrap[3] == 0) {
            fix_bevel_wrap(vec, o_v3, o_v4, o_v1, o_v2, d, no);
            VECCOPY(v2, vec);
            VECCOPY(v3, vec);
      }
      // Edge 3 inverted
      else if (wrap[0] == 0 && wrap[1] == 0 && wrap[2] == 1 && wrap[3] == 0) {
            fix_bevel_wrap(vec, o_v4, o_v1, o_v2, o_v3, d, no);
            VECCOPY(v3, vec);
            VECCOPY(v4, vec);
      }
      // Edge 4 inverted
      else if (wrap[0] == 0 && wrap[1] == 0 && wrap[2] == 0 && wrap[3] == 1) {
            fix_bevel_wrap(vec, o_v1, o_v2, o_v3, o_v4, d, no);
            VECCOPY(v4, vec);
            VECCOPY(v1, vec);
      }
      // Edge 2 and 4 inverted
      else if (wrap[0] == 0 && wrap[1] == 1 && wrap[2] == 0 && wrap[3] == 1) {
            VecAddf(vec, v2, v3);
            VecMulf(vec, 0.5);
            VECCOPY(v2, vec);
            VECCOPY(v3, vec);
            VecAddf(vec, v1, v4);
            VecMulf(vec, 0.5);
            VECCOPY(v1, vec);
            VECCOPY(v4, vec);
      }
      // Edge 1 and 3 inverted
      else if (wrap[0] == 1 && wrap[1] == 0 && wrap[2] == 1 && wrap[3] == 0) {
            VecAddf(vec, v1, v2);
            VecMulf(vec, 0.5);
            VECCOPY(v1, vec);
            VECCOPY(v2, vec);
            VecAddf(vec, v3, v4);
            VecMulf(vec, 0.5);
            VECCOPY(v3, vec);
            VECCOPY(v4, vec);
      }
      // Totally inverted
      else if (wrap[0] == 1 && wrap[1] == 1 && wrap[2] == 1 && wrap[3] == 1) {
            VecAddf(vec, v1, v2);
            VecAddf(vec, vec, v3);
            VecAddf(vec, vec, v4);
            VecMulf(vec, 0.25);
            VECCOPY(v1, vec);
            VECCOPY(v2, vec);
            VECCOPY(v3, vec);
            VECCOPY(v4, vec);
      }

}

// Detects and fix a tri wrapping after the resize
// Arguments are the orginal verts followed by the final verts and the normal
// Triangles cannot wrap partially (not in this situation
void fix_bevel_tri_wrap(float *o_v1, float *o_v2, float *o_v3, float *v1, float *v2, float *v3, float *no) 
{
      if (detect_wrap(o_v1, o_v2, v1, v2, no)) {
            float vec[3];
            VecAddf(vec, o_v1, o_v2);
            VecAddf(vec, vec, o_v3);
            VecMulf(vec, 1.0/3.0);
            VECCOPY(v1, vec);
            VECCOPY(v2, vec);
            VECCOPY(v3, vec);
      }
}

void bevel_shrink_faces(float d, int flag)
{
      EditMesh *em = G.editMesh;
      EditFace *efa;
      float vec[3], no[3], v1[3], v2[3], v3[3], v4[3];

      /* move edges of all faces with efa->f1 & flag closer towards their centres */
      efa= em->faces.first;
      while (efa) {
            if (efa->f1 & flag) {
                  VECCOPY(v1, efa->v1->co);
                  VECCOPY(v2, efa->v2->co);                 
                  VECCOPY(v3, efa->v3->co);     
                  VECCOPY(no, efa->n);
                  if (efa->v4 == NULL) {
                        bevel_displace_vec(vec, v1, v2, v3, d, no);
                        VECCOPY(efa->v2->co, vec);
                        bevel_displace_vec(vec, v2, v3, v1, d, no);
                        VECCOPY(efa->v3->co, vec);          
                        bevel_displace_vec(vec, v3, v1, v2, d, no);
                        VECCOPY(efa->v1->co, vec);

                        fix_bevel_tri_wrap(v1, v2, v3, efa->v1->co, efa->v2->co, efa->v3->co, no);
                  } else {
                        VECCOPY(v4, efa->v4->co);
                        bevel_displace_vec(vec, v1, v2, v3, d, no);
                        VECCOPY(efa->v2->co, vec);
                        bevel_displace_vec(vec, v2, v3, v4, d, no);
                        VECCOPY(efa->v3->co, vec);          
                        bevel_displace_vec(vec, v3, v4, v1, d, no);
                        VECCOPY(efa->v4->co, vec);          
                        bevel_displace_vec(vec, v4, v1, v2, d, no);
                        VECCOPY(efa->v1->co, vec);

                        fix_bevel_quad_wrap(v1, v2, v3, v4, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, d, no);
                  }
            }
            efa= efa->next;
      }     
}

void bevel_shrink_draw(float d, int flag)
{
      EditMesh *em = G.editMesh;
      EditFace *efa;
      float vec[3], no[3], v1[3], v2[3], v3[3], v4[3], fv1[3], fv2[3], fv3[3], fv4[3];

      /* move edges of all faces with efa->f1 & flag closer towards their centres */
      efa= em->faces.first;
      while (efa) {
            VECCOPY(v1, efa->v1->co);
            VECCOPY(v2, efa->v2->co);                 
            VECCOPY(v3, efa->v3->co);     
            VECCOPY(no, efa->n);
            if (efa->v4 == NULL) {
                  bevel_displace_vec(vec, v1, v2, v3, d, no);
                  VECCOPY(fv2, vec);
                  bevel_displace_vec(vec, v2, v3, v1, d, no);
                  VECCOPY(fv3, vec);            
                  bevel_displace_vec(vec, v3, v1, v2, d, no);
                  VECCOPY(fv1, vec);

                  fix_bevel_tri_wrap(v1, v2, v3, fv1, fv2, fv3, no);

                  glBegin(GL_LINES);
                  glVertex3fv(fv1);
                  glVertex3fv(fv2);
                  glEnd();                                  
                  glBegin(GL_LINES);
                  glVertex3fv(fv2);
                  glVertex3fv(fv3);
                  glEnd();                                  
                  glBegin(GL_LINES);
                  glVertex3fv(fv1);
                  glVertex3fv(fv3);
                  glEnd();                                  
            } else {
                  VECCOPY(v4, efa->v4->co);
                  bevel_displace_vec(vec, v4, v1, v2, d, no);
                  VECCOPY(fv1, vec);
                  bevel_displace_vec(vec, v1, v2, v3, d, no);
                  VECCOPY(fv2, vec);
                  bevel_displace_vec(vec, v2, v3, v4, d, no);
                  VECCOPY(fv3, vec);            
                  bevel_displace_vec(vec, v3, v4, v1, d, no);
                  VECCOPY(fv4, vec);            

                  fix_bevel_quad_wrap(v1, v2, v3, v4, fv1, fv2, fv3, fv4, d, no);

                  glBegin(GL_LINES);
                  glVertex3fv(fv1);
                  glVertex3fv(fv2);
                  glEnd();                                  
                  glBegin(GL_LINES);
                  glVertex3fv(fv2);
                  glVertex3fv(fv3);
                  glEnd();                                  
                  glBegin(GL_LINES);
                  glVertex3fv(fv3);
                  glVertex3fv(fv4);
                  glEnd();                                  
                  glBegin(GL_LINES);
                  glVertex3fv(fv1);
                  glVertex3fv(fv4);
                  glEnd();                                  
            }
            efa= efa->next;
      }     
}

void bevel_mesh(float bsize, int allfaces)
{
      EditMesh *em = G.editMesh;
//#define BEV_DEBUG
/* Enables debug printfs and assigns material indices: */
/* 2 = edge quad                                       */
/* 3 = fill polygon (vertex clusters)                  */

      EditFace *efa, *example; //, *nextvl;
      EditEdge *eed, *eed2;
      EditVert *neweve[1024], *eve, *eve2, *eve3, *v1, *v2, *v3, *v4; //, *eve4;
      //short found4,  search;
      //float f1, f2, f3, f4;
      float cent[3], min[3], max[3];
      int a, b, c;
      float limit= 0.001;

      waitcursor(1);

      removedoublesflag(1, limit);

      /* tag all original faces */
      efa= em->faces.first;
      while (efa) {
            efa->f1= 0;
            if (faceselectedAND(efa, 1)||allfaces) {
                  efa->f1= 1;
                  efa->v1->f |= 128;
                  efa->v2->f |= 128;
                  efa->v3->f |= 128;
                  if (efa->v4) efa->v4->f |= 128;                 
            }
            efa->v1->f &= ~64;
            efa->v2->f &= ~64;
            efa->v3->f &= ~64;
            if (efa->v4) efa->v4->f &= ~64;           

            efa= efa->next;
      }

#ifdef BEV_DEBUG
      fprintf(stderr,"bevel_mesh: split\n");
#endif
      
      efa= em->faces.first;
      while (efa) {
            if (efa->f1 & 1) {
                  efa->f1-= 1;
                  v1= addvertlist(efa->v1->co);
                  v1->f= efa->v1->f & ~128;
                  efa->v1->vn= v1;
#ifdef __NLA
                  v1->totweight = efa->v1->totweight;
                  if (efa->v1->totweight){
                        v1->dw = MEM_mallocN (efa->v1->totweight * sizeof(MDeformWeight), "deformWeight");
                        memcpy (v1->dw, efa->v1->dw, efa->v1->totweight * sizeof(MDeformWeight));
                  }
                  else
                        v1->dw=NULL;
#endif
                  v1= addvertlist(efa->v2->co);
                  v1->f= efa->v2->f & ~128;
                  efa->v2->vn= v1;
#ifdef __NLA
                  v1->totweight = efa->v2->totweight;
                  if (efa->v2->totweight){
                        v1->dw = MEM_mallocN (efa->v2->totweight * sizeof(MDeformWeight), "deformWeight");
                        memcpy (v1->dw, efa->v2->dw, efa->v2->totweight * sizeof(MDeformWeight));
                  }
                  else
                        v1->dw=NULL;
#endif
                  v1= addvertlist(efa->v3->co);
                  v1->f= efa->v3->f & ~128;
                  efa->v3->vn= v1;
#ifdef __NLA
                  v1->totweight = efa->v3->totweight;
                  if (efa->v3->totweight){
                        v1->dw = MEM_mallocN (efa->v3->totweight * sizeof(MDeformWeight), "deformWeight");
                        memcpy (v1->dw, efa->v3->dw, efa->v3->totweight * sizeof(MDeformWeight));
                  }
                  else
                        v1->dw=NULL;
#endif
                  if (efa->v4) {
                        v1= addvertlist(efa->v4->co);
                        v1->f= efa->v4->f & ~128;
                        efa->v4->vn= v1;
#ifdef __NLA
                        v1->totweight = efa->v4->totweight;
                        if (efa->v4->totweight){
                              v1->dw = MEM_mallocN (efa->v4->totweight * sizeof(MDeformWeight), "deformWeight");
                              memcpy (v1->dw, efa->v4->dw, efa->v4->totweight * sizeof(MDeformWeight));
                        }
                        else
                              v1->dw=NULL;
#endif
                  }

                  /* Needs better adaption of creases? */
                  addedgelist(efa->e1->v1->vn, efa->e1->v2->vn, efa->e1);
                  addedgelist(efa->e2->v1->vn,efa->e2->v2->vn, efa->e2);                  
                  addedgelist(efa->e3->v1->vn,efa->e3->v2->vn, efa->e3);                  
                  if (efa->e4) addedgelist(efa->e4->v1->vn,efa->e4->v2->vn, efa->e4);  

                  if(efa->v4) {
                        v1= efa->v1->vn;
                        v2= efa->v2->vn;
                        v3= efa->v3->vn;
                        v4= efa->v4->vn;
                        addfacelist(v1, v2, v3, v4, efa,NULL);
                  } else {
                        v1= efa->v1->vn;
                        v2= efa->v2->vn;
                        v3= efa->v3->vn;
                        addfacelist(v1, v2, v3, 0, efa,NULL);
                  }

                  efa= efa-> next;
            } else {
                  efa= efa->next;
            }
      }
      
      for(efa= em->faces.first; efa; efa= efa->next) {
            if( (efa->v1->f & 128) && (efa->v2->f & 128) && (efa->v3->f & 128) ) {
                  if(efa->v4==NULL || (efa->v4->f & 128)) efa->f |= 128;
            }
      }

      delfaceflag(128); // works with face flag now

      /* tag all faces for shrink*/
      efa= em->faces.first;
      while (efa) {
            if (faceselectedAND(efa, 1)||allfaces) {
                  efa->f1= 2;
            }
            efa= efa->next;
      }

#ifdef BEV_DEBUG
      fprintf(stderr,"bevel_mesh: make edge quads\n");
#endif

      /* find edges that are on each other and make quads between them */

      eed= em->edges.first;
      while(eed) {
            eed->f2= eed->f1= 0;
            if ( ((eed->v1->f & eed->v2->f) & 1) || allfaces) eed->f1 |= 4;   /* original edges */
            eed->vn= 0;
            eed= eed->next;
      }

      eed= em->edges.first;
      while (eed) {
            if ( ((eed->f1 & 2)==0) && (eed->f1 & 4) ) {
                  eed2= em->edges.first;
                  while (eed2) {
                        if ( (eed2 != eed) && ((eed2->f1 & 2)==0) && (eed->f1 & 4) ) {
                              if (
                                 (eed->v1 != eed2->v1) &&
                                 (eed->v1 != eed2->v2) &&                              
                                 (eed->v2 != eed2->v1) &&
                                 (eed->v2 != eed2->v2) &&   (
                                 ( VecCompare(eed->v1->co, eed2->v1->co, limit) &&
                                     VecCompare(eed->v2->co, eed2->v2->co, limit) ) ||
                                 ( VecCompare(eed->v1->co, eed2->v2->co, limit) &&
                                     VecCompare(eed->v2->co, eed2->v1->co, limit) ) ) )
                                    {
                                    
#ifdef BEV_DEBUG                                
                                    fprintf(stderr, "bevel_mesh: edge quad\n");
#endif                                    
                                    
                                    eed->f1 |= 2;     /* these edges are finished */
                                    eed2->f1 |= 2;
                                    
                                    example= NULL;
                                    efa= em->faces.first;   /* search example face (for mat_nr, ME_SMOOTH, ...) */
                                    while (efa) {
                                          if ( (efa->e1 == eed) ||
                                               (efa->e2 == eed) ||
                                               (efa->e3 == eed) ||
                                               (efa->e4 && (efa->e4 == eed)) ) {
                                              example= efa;
                                                efa= NULL;
                                          }
                                          if (efa) efa= efa->next;
                                    }
                                    
                                    neweve[0]= eed->v1; neweve[1]= eed->v2;
                                    neweve[2]= eed2->v1; neweve[3]= eed2->v2;
                                    
                                    if(exist_face(neweve[0], neweve[1], neweve[2], neweve[3])==0) {
                                          efa= NULL;

                                          if (VecCompare(eed->v1->co, eed2->v2->co, limit)) {
                                                efa= addfacelist(neweve[0], neweve[1], neweve[2], neweve[3], example,NULL);
                                          } else {
                                                efa= addfacelist(neweve[0], neweve[2], neweve[3], neweve[1], example,NULL);
                                          }
                                    
                                          if(efa) {
                                                float inp;  
                                                CalcNormFloat(efa->v1->co, efa->v2->co, efa->v3->co, efa->n);
                                                inp= efa->n[0]*G.vd->viewmat[0][2] + efa->n[1]*G.vd->viewmat[1][2] + efa->n[2]*G.vd->viewmat[2][2];
                                                if(inp < 0.0) flipface(efa);
#ifdef BEV_DEBUG
                                                efa->mat_nr= 1;
#endif
                                          } else fprintf(stderr,"bevel_mesh: error creating face\n");
                                    }
                                    eed2= NULL;
                              }
                        }
                        if (eed2) eed2= eed2->next;
                  }
            }
            eed= eed->next;
      }

      eed= em->edges.first;
      while(eed) {
            eed->f2= eed->f1= 0;
            eed->f1= 0;
            eed->v1->f1 &= ~1;
            eed->v2->f1 &= ~1;            
            eed->vn= 0;
            eed= eed->next;
      }

#ifdef BEV_DEBUG
      fprintf(stderr,"bevel_mesh: find clusters\n");
#endif      

      /* Look for vertex clusters */

      eve= em->verts.first;
      while (eve) {
            eve->f &= ~(64|128);
            eve->vn= NULL;
            eve= eve->next;
      }
      
      /* eve->f: 128: first vertex in a list (->vn) */
      /*          64: vertex is in a list */
      
      eve= em->verts.first;
      while (eve) {
            eve2= em->verts.first;
            eve3= NULL;
            while (eve2) {
                  if ((eve2 != eve) && ((eve2->f & (64|128))==0)) {
                        if (VecCompare(eve->co, eve2->co, limit)) {
                              if ((eve->f & (128|64)) == 0) {
                                    /* fprintf(stderr,"Found vertex cluster:\n  *\n  *\n"); */
                                    eve->f |= 128;
                                    eve->vn= eve2;
                                    eve3= eve2;
                              } else if ((eve->f & 64) == 0) {
                                    /* fprintf(stderr,"  *\n"); */
                                    if (eve3) eve3->vn= eve2;
                                    eve2->f |= 64;
                                    eve3= eve2;
                              }
                        }
                  }
                  eve2= eve2->next;
                  if (!eve2) {
                        if (eve3) eve3->vn= NULL;
                  }
            }
            eve= eve->next;
      }

#ifdef BEV_DEBUG
      fprintf(stderr,"bevel_mesh: shrink faces\n");
#endif      

      bevel_shrink_faces(bsize, 2);

#ifdef BEV_DEBUG
      fprintf(stderr,"bevel_mesh: fill clusters\n");
#endif
      
      /* Make former vertex clusters faces */

      eve= em->verts.first;
      while (eve) {
            eve->f &= ~64;
            eve= eve->next;
      }

      eve= em->verts.first;
      while (eve) {
            if (eve->f & 128) {
                  eve->f &= ~128;
                  a= 0;
                  neweve[a]= eve;
                  eve2= eve->vn;
                  while (eve2) {
                        a++;
                        neweve[a]= eve2;
                        eve2= eve2->vn;
                  }
                  a++;
                  efa= NULL;
                  if (a>=3) {
                        example= NULL;
                        efa= em->faces.first;   /* search example face */
                        while (efa) {
                              if ( (efa->v1 == neweve[0]) ||
                                   (efa->v2 == neweve[0]) ||
                                   (efa->v3 == neweve[0]) ||
                                   (efa->v4 && (efa->v4 == neweve[0])) ) {
                                  example= efa;
                                    efa= NULL;
                              }
                              if (efa) efa= efa->next;
                        }
#ifdef BEV_DEBUG                    
                        fprintf(stderr,"bevel_mesh: Making %d-gon\n", a);
#endif                        
                        if (a>4) {
                              cent[0]= cent[1]= cent[2]= 0.0;                       
                              INIT_MINMAX(min, max);                    
                              for (b=0; b<a; b++) {
                                    VecAddf(cent, cent, neweve[b]->co);
                                    DO_MINMAX(neweve[b]->co, min, max);
                              }
                              cent[0]= (min[0]+max[0])/2;
                              cent[1]= (min[1]+max[1])/2;
                              cent[2]= (min[2]+max[2])/2;
                              eve2= addvertlist(cent);
                              eve2->f |= 1;
                              eed= em->edges.first;
                              while (eed) {
                                    c= 0;
                                    for (b=0; b<a; b++) 
                                          if ((neweve[b]==eed->v1) || (neweve[b]==eed->v2)) c++;
                                    if (c==2) {
                                          if(exist_face(eed->v1, eed->v2, eve2, 0)==0) {
                                                efa= addfacelist(eed->v1, eed->v2, eve2, 0, example,NULL);
#ifdef BEV_DEBUG
                                                efa->mat_nr= 2;
#endif                                                
                                          }
                                    }
                                    eed= eed->next;
                              }
                        } else if (a==4) {
                              if(exist_face(neweve[0], neweve[1], neweve[2], neweve[3])==0) {
                                    /* the order of vertices can be anything, three cases to check */
                                    if( convex(neweve[0]->co, neweve[1]->co, neweve[2]->co, neweve[3]->co) ) {
                                          efa= addfacelist(neweve[0], neweve[1], neweve[2], neweve[3], NULL, NULL);
                                    }
                                    else if( convex(neweve[0]->co, neweve[2]->co, neweve[3]->co, neweve[1]->co) ) {
                                          efa= addfacelist(neweve[0], neweve[2], neweve[3], neweve[1], NULL, NULL);
                                    }
                                    else if( convex(neweve[0]->co, neweve[2]->co, neweve[1]->co, neweve[3]->co) ) {
                                          efa= addfacelist(neweve[0], neweve[2], neweve[1], neweve[3], NULL, NULL);
                                    }
                              }                       
                        }
                        else if (a==3) {
                              if(exist_face(neweve[0], neweve[1], neweve[2], 0)==0)
                                    efa= addfacelist(neweve[0], neweve[1], neweve[2], 0, example, NULL);
                        }
                        if(efa) {
                              float inp;  
                              CalcNormFloat(neweve[0]->co, neweve[1]->co, neweve[2]->co, efa->n);
                              inp= efa->n[0]*G.vd->viewmat[0][2] + efa->n[1]*G.vd->viewmat[1][2] + efa->n[2]*G.vd->viewmat[2][2];
                              if(inp < 0.0) flipface(efa);
#ifdef BEV_DEBUG
                                    efa->mat_nr= 2;
#endif                                                                        
                        }                       
                  }
            }
            eve= eve->next;
      }

      eve= em->verts.first;
      while (eve) {
            eve->f1= 0;
            eve->f &= ~(128|64);
            eve->vn= NULL;
            eve= eve->next;
      }
      
      recalc_editnormals();
      waitcursor(0);
      countall();
      allqueue(REDRAWVIEW3D, 0);
      makeDispList(G.obedit);
      
      removedoublesflag(1, limit);

      /* flush selected vertices to edges/faces */
      EM_select_flush();

#undef BEV_DEBUG
}

void bevel_mesh_recurs(float bsize, short recurs, int allfaces) 
{
      float d;
      short nr;

      d= bsize;
      for (nr=0; nr<recurs; nr++) {
            bevel_mesh(d, allfaces);
            if (nr==0) d /= 3; else d /= 2;
      }
}

void bevel_menu()
{
      char Finished = 0, Canceled = 0, str[100], Recalc = 0;
      short mval[2], oval[2], curval[2], event = 0, recurs = 1, nr;
      float vec[3], d, drawd=0.0, centre[3], fac = 1;

      getmouseco_areawin(mval);
      oval[0] = mval[0]; oval[1] = mval[1];

      // Silly hackish code to initialise the variable (warning if not done)
      // while still drawing in the first iteration (and without using another variable)
      curval[0] = mval[0] + 1; curval[1] = mval[1] + 1;

      window_to_3d(centre, mval[0], mval[1]);

      if(button(&recurs, 1, 4, "Recursion:")==0) return;

      for (nr=0; nr<recurs-1; nr++) {
            if (nr==0) fac += 1.0/3.0; else fac += 1.0/(3 * nr * 2.0);
      }

      SetBlenderCursor(SYSCURSOR);

      while (Finished == 0)
      {
            getmouseco_areawin(mval);
            if (mval[0] != curval[0] || mval[1] != curval[1] || (Recalc == 1))
            {
                  Recalc = 0;
                  curval[0] = mval[0];
                  curval[1] = mval[1];

                  window_to_3d(vec, mval[0]-oval[0], mval[1]-oval[1]);
                  d = Normalise(vec) / 10;


                  drawd = d * fac;
                  if (G.qual & LR_CTRLKEY)
                        drawd = (float) floor(drawd * 10.0)/10.0;
                  if (G.qual & LR_SHIFTKEY)
                        drawd /= 10;

                  /*------------- Preview lines--------------- */
                  
                  /* uses callback mechanism to draw it all in current area */
                  scrarea_do_windraw(curarea);              
                  
                  /* set window matrix to perspective, default an area returns with buttons transform */
                  persp(PERSP_VIEW);
                  /* make a copy, for safety */
                  glPushMatrix();
                  /* multiply with the object transformation */
                  mymultmatrix(G.obedit->obmat);
                  
                  glColor3ub(255, 255, 0);

                  // PREVIEW CODE GOES HERE
                  bevel_shrink_draw(drawd, 2);

                  /* restore matrix transform */
                  glPopMatrix();
                  
                  sprintf(str, "Bevel Size: %.4f        LMB to confirm, RMB to cancel, SPACE to input directly.", drawd);
                  headerprint(str);

                  /* this also verifies other area/windows for clean swap */
                  screen_swapbuffers();

                  persp(PERSP_WIN);
                  
                  glDrawBuffer(GL_FRONT);
                  
                  BIF_ThemeColor(TH_WIRE);

                  setlinestyle(3);
                  glBegin(GL_LINE_STRIP); 
                        glVertex2sv(mval); 
                        glVertex2sv(oval); 
                  glEnd();
                  setlinestyle(0);
                  
                  persp(PERSP_VIEW);
                  glFlush(); // flush display for frontbuffer
                  glDrawBuffer(GL_BACK);
            }
            while(qtest()) {
                  unsigned short val=0;               
                  event= extern_qread(&val);    // extern_qread stores important events for the mainloop to handle 

                  /* val==0 on key-release event */
                  if(val && (event==ESCKEY || event==RIGHTMOUSE || event==LEFTMOUSE || event==RETKEY || event==ESCKEY)){
                        if (event==RIGHTMOUSE || event==ESCKEY)
                              Canceled = 1;
                        Finished = 1;
                  }
                  else if (val && event==SPACEKEY) {
                        if (fbutton(&d, 0.000, 10.000, 10, 0, "Width:")!=0) {
                              drawd = d * fac;
                              Finished = 1;
                        }
                  }
                  else if (val) {
                        /* On any other keyboard event, recalc */
                        Recalc = 1;
                  }

            }     
      }
      if (Canceled==0) {
            SetBlenderCursor(BC_WAITCURSOR);
            bevel_mesh_recurs(drawd/fac, recurs, 1);
            righthandfaces(1);
            SetBlenderCursor(SYSCURSOR);
            BIF_undo_push("Bevel");
      }
}

/* *********** END BEVEL *********/



Generated by  Doxygen 1.6.0   Back to index