SIMPLIFY.C

Go to the documentation of this file.

/* --
OpenFX version 2.0 - Modelling, Animation and Rendering Package
Copyright (C) 2000 -  OpenFX Development Team

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.

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.

You may contact the OpenFX development team via elecronic mail
at core@openfx.org, or visit our website at http://openfx.org for
further information and support details.
-- */

/*  SIMPLIFY.C  */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <windows.h>

#include "struct.h"
#include "dstruct.h"

#include "simplify.h"

static HWND      hParent;
static HINSTANCE hThisInstance;

#if __WATCOMC__
int APIENTRY LibMain(HANDLE hDLL, DWORD dwReason, LPVOID lpReserved){
#else
BOOL WINAPI DllMain(HANDLE hDLL, DWORD dwReason, LPVOID lpReserved){
#endif
  switch (dwReason) {
    case DLL_PROCESS_ATTACH: {
      hThisInstance=hDLL;
      if(hDLL == NULL)MessageBox( GetFocus()," NULL instance",NULL, MB_OK);
      break;
    }
    case DLL_PROCESS_DETACH:
      break;
  }
  return TRUE;
}

BOOL _Xmodeler
 (HWND parent_window,HWND info_window,X__STRUCTURE *lpevi){
 HCURSOR hSave;
 static struct bp {long iter; double ean,fan;} d;
 double fan=5.0,ean=5.0;
 long   nloop=5;
 lpEVI=lpevi;
 hParent=parent_window;
 d.iter=nloop; d.fan=fan; d.ean=ean;
 if(DialogBoxParam(hThisInstance,MAKEINTRESOURCE(DLG_SIM),hParent,
             (DLGPROC)SimplifyDlgProc,(LPARAM)&d) == FALSE)return FALSE;
 nloop=d.iter; ean=d.ean; fan=d.fan;
 hSave=SetCursor(LoadCursor(NULL,IDC_WAIT));
 SimplifyObject(nloop,fan,ean);
 SetCursor(hSave);
 return TRUE;
}

static BOOL CALLBACK SimplifyDlgProc(HWND hwnd, UINT msg,
                             WPARAM wparam, LPARAM lparam){
 BOOL err;
 int i;
 static struct bp {long iter; double ean,fan;} *dp;
 double angle;
 char str[32];
 switch( msg ) {
   case WM_INITDIALOG:
     dp=(struct bp *)lparam;
     SetDlgItemInt(hwnd,DLG_SIM_ITER,dp->iter,FALSE);
     sprintf(str,"%.2lf",dp->fan);
     SetDlgItemText(hwnd,DLG_SIM_FACE,(LPCTSTR)str);
     SendDlgItemMessage(hwnd,DLG_SIM_FACE,EM_LIMITTEXT,(WPARAM)12,0);
     sprintf(str,"%.2lf",dp->ean);
     SetDlgItemText(hwnd,DLG_SIM_EDGE,(LPCTSTR)str);
     SendDlgItemMessage(hwnd,DLG_SIM_EDGE,EM_LIMITTEXT,(WPARAM)12,0);
     CentreDlgOnS(hwnd);
     return (TRUE);
   case WM_COMMAND:
      switch(LOWORD(wparam)){
        case IDCANCEL:
          EndDialog(hwnd,FALSE);
          return(TRUE);
        case IDOK:
          if(GetDlgItemText(hwnd,DLG_SIM_FACE,str,10) == 0){
            EndDialog(hwnd,FAIL);
            return TRUE;
          }
          angle=atof(str);
          if(angle < 0.1 || angle > 45.0){
            EndDialog(hwnd,FAIL);
            return TRUE;
          }
          dp->fan=angle;
          if(GetDlgItemText(hwnd,DLG_SIM_EDGE,str,10) == 0){
            EndDialog(hwnd,FAIL);
            return TRUE;
          }
          angle=atof(str);
          if(angle < 0.1 || angle > 45.0){
            EndDialog(hwnd,FAIL);
            return TRUE;
          }
          dp->ean=angle;
          i=GetDlgItemInt(hwnd,DLG_SIM_ITER,&err,FALSE);
          if(err)dp->iter=i;
          EndDialog(hwnd,TRUE);
          return(TRUE);
        default:
          break;
      }
      break;
    default: break;
 }
 return(FALSE);
}

static vtyadj *ListAdjFaces(selectedface *wf, long nf,
                            selectededge *we, long ne, long *nvll){
 edge *e;
 face *f;
 vertex *vp;
 vtyadj *vl=NULL;
 long c,nvl=0;
 long *fl,i,j,k,id,id0,id1,id2,fjd,fkd,n,m,kk,nl[3],ml[3];
 vp=MainVp; for(c=0;c<Nvert;c++){
   if(vp->status == DESELECTED){ /* work vertex */
     vp->id=nvl;
     nvl++;
   }
   else vp->id = -10;
   vp++;
 }
 if((vl=(vtyadj *)X__Malloc(nvl*sizeof(vtyadj))) == NULL)return 0;
 for(i=0;i<nvl;i++){
   vl[i].nf=0; vl[i].ne=0;
   vl[i].flist=NULL; vl[i].elist=NULL;
 }
 i=0; vp=MainVp; for(c=0;c<Nvert;c++){
   if(vp->status == DESELECTED){
     vl[i].v=c;
     i++;
   }
   vp++;
 }
 for(i=0;i<nf;i++){ /* make list of work faces attached to each vertex */
   f=(MainFp+wf[i].f);
   for(j=0;j<3;j++){
     id=(MainVp+(f->V[j]))->id;
     fl=vl[id].flist;
     n=vl[id].nf;
     if(fl == NULL){
       if((fl=(long *)X__Malloc(sizeof(long))) == NULL)return NULL;
     }
     else{
       if((fl=(long *)X__Realloc(fl,(n+1)*sizeof(long))) == NULL)return NULL;
     }
     fl[n]=i;
     vl[id].flist=fl;
     vl[id].nf=n+1;
   }
 }
 for(i=0;i<nf;i++){ /* find faces that are adjacent to face i */
   f=(MainFp+wf[i].f);
   id0=(MainVp+(f->V[0]))->id;
   id1=(MainVp+(f->V[1]))->id;
   id2=(MainVp+(f->V[2]))->id;
   nl[0]=id0; ml[0]=id1;
   nl[1]=id1; ml[1]=id2;
   nl[2]=id2; ml[2]=id0;
   for(kk=0;kk<3;kk++){
     wf[i].fa[kk] = -1;
     if((n=vl[nl[kk]].nf) > 0 && (m=vl[ml[kk]].nf) > 0){
       for(j=0;j<n;j++){
         fjd=vl[nl[kk]].flist[j];
         for(k=0;k<m;k++){
           fkd=vl[ml[kk]].flist[k];
           if(fkd == fjd && fkd != i){
             wf[i].fa[kk]=fkd;
             goto ENDF;
           }
         }
       }
     }
     ENDF:;
   }
 }
 for(i=0;i<ne;i++){ /* find faces that are adjacent to edge i */
   e=(MainEp+we[i].e);
   id0=(MainVp+(e->V[0]))->id; id1=(MainVp+(e->V[1]))->id;
   kk=0; we[i].ea[0] = we[i].ea[1] = -1;
   if((n=vl[id0].nf) > 0 && (m=vl[id1].nf) > 0){
     for(j=0;j<n;j++){
       fjd=vl[id0].flist[j];
       for(k=0;k<m;k++){
         fkd=vl[id1].flist[k];
         if(fkd == fjd){
           we[i].ea[kk]=fkd;
           kk++;
           if(kk == 2)goto ENDEE;  /* terminate when we have two */
         }
       }
     }
     ENDEE:;
   }
 }
 for(i=0;i<ne;i++){ /* make list of work edges attached to each vertex */
   e=(MainEp+we[i].e);
   for(j=0;j<2;j++){
     id=(MainVp+(e->V[j]))->id;
     fl=vl[id].elist;
     n=vl[id].ne;
     if(fl == NULL){
       if((fl=(long *)X__Malloc(sizeof(long))) == NULL)return NULL;
     }
     else {
       if((fl=(long *)X__Realloc(fl,(n+1)*sizeof(long))) == NULL)return NULL;
     }
     fl[n]=i;
     vl[id].elist=fl;
     vl[id].ne=n+1;
   }
 }
 for(i=0;i<nf;i++){ /* find edges that are adjacent to face i */
   f=(MainFp+wf[i].f);
   id0=(MainVp+(f->V[0]))->id;
   id1=(MainVp+(f->V[1]))->id;
   id2=(MainVp+(f->V[2]))->id;
   nl[0]=id0; ml[0]=id1;
   nl[1]=id1; ml[1]=id2;
   nl[2]=id2; ml[2]=id0;
   for(kk=0;kk<3;kk++){
     wf[i].ea[kk] = -1;
     if((n=vl[nl[kk]].ne) > 0 && (m=vl[ml[kk]].ne) > 0){
       for(j=0;j<n;j++){
         fjd=vl[nl[kk]].elist[j];
         for(k=0;k<m;k++){
           fkd=vl[ml[kk]].elist[k];
           if(fkd == fjd){
             wf[i].ea[kk]=fkd;
             goto ENDE;
           }
         }
       }
     }
     ENDE:;
   }
 }
 *nvll=nvl;
 return vl;
}

static void FreeAdjFaces(vtyadj *vl,long nvl){
 int i;
 if(vl != NULL && nvl > 0){
   for(i=0;i<nvl;i++){
     if(vl[i].flist != NULL)X__Free(vl[i].flist);
     if(vl[i].elist != NULL)X__Free(vl[i].elist);
   }
   X__Free(vl);
 }
}

static void SimplifyObject(long nloop, double fan, double ean){
 selectededge *we;
 selectedface *w;
 face *f;
 vertex *vp,*v0,*v1,*v2;
 edge *e;
 vector du,dv,n,p0,p1,p2;
 long c,i,loop,n_work_face,n_work_edge,phase,nvl;
 vtyadj *vl;
 if(NvertSelect == 0)return;
 if(NvertSelect > 32000)return;
 if(MainFp == NULL)return;
 fan=cos(fan*0.0174532);
 ean=cos(ean*0.0174532);
 vp=MainVp; for(i=0;i<Nvert;i++){
   if(vp->status == SELECTED){
     vp->status=DESELECTED;
     NvertSelect--; NvertDeselect++;
   }
   else if(vp->status == DESELECTED){
     vp->status=INEDITOR;
   }
   vp->id=0;
   vp++;
 }
 phase=0;
 PHASE:
 n_work_face=0,n_work_edge=0;
 w=NULL; we=NULL;
 f=MainFp; for(c=0;c<Nface;c++){
  v0=(MainVp+f->V[0]); v1=(MainVp+f->V[1]); v2=(MainVp+f->V[2]);
  if(v0->status == DESELECTED &&
     v1->status == DESELECTED &&
     v1->status == DESELECTED)n_work_face++;
  f++;
 }
 e=MainEp; for(c=0;c<Nedge;c++){ /* get all tool edges */
   v0=(MainVp+e->V[0]); v1=(MainVp+e->V[1]);
   if(v0->status == DESELECTED && v1->status == DESELECTED)n_work_edge++;
   e++;
 }
 if((w=(selectedface *)X__Malloc((n_work_face+1)*(long)sizeof(selectedface)))
    == NULL)goto BERR;
 if((we=(selectededge *)X__Malloc((n_work_edge+1)*(long)sizeof(selectededge)))
    == NULL)goto BERR;
 n_work_face=0; n_work_edge=0;
 f=MainFp; for(c=0;c<Nface;c++){
  v0=(MainVp+f->V[0]); v1=(MainVp+f->V[1]); v2=(MainVp+f->V[2]);
  POINT2VECTOR(v0->xyz,p0)
  POINT2VECTOR(v1->xyz,p1)
  POINT2VECTOR(v2->xyz,p2)
  VECSUB(p1,p0,dv)
  VECSUB(p2,p0,du)
  if(v0->status == DESELECTED &&
     v1->status == DESELECTED &&
     v2->status == DESELECTED){
    w[n_work_face].f=c;
    w[n_work_face].del=0;
    for(i=0;i<3;i++){
      w[n_work_face].fa[i] = -1;
      w[n_work_face].ea[i] = -1;
    }
    CROSS(dv,du,n)
    if(O_normalize(n) == FAIL){
      VECSUB(p0,p1,dv)
      VECSUB(p2,p1,du)
      CROSS(dv,du,n)
      if(O_normalize(n) == FAIL){
        VECSUB(p0,p2,dv)
        VECSUB(p1,p2,du)
        CROSS(dv,du,n)
        if(O_normalize(n) == FAIL)goto BERR2;
      }
    }
    VECCOPY(n,w[n_work_face].n)
    n_work_face++;
  }
  f++;
 }
 e=MainEp; for(c=0;c<Nedge;c++){ /* get all tool edges */
   v0=(MainVp+e->V[0]); v1=(MainVp+e->V[1]);
   if(v0->status == DESELECTED && v1->status == DESELECTED){
     we[n_work_edge].e=c;    /* are the original selectedface edges, pass 1 */
     we[n_work_edge].ea[0] = we[n_work_edge].ea[1] = -1;
     n_work_edge++;
   }
   e++;
 }
 if(n_work_face == 0)goto QUIT;
 vl=ListAdjFaces(w,n_work_face,we,n_work_edge,&nvl);
 /* simplify straight edges */
 if(phase == 0)for(loop=0;loop<nloop;loop++){
   if(!Simplify1(vl,nvl,w,n_work_face,we,n_work_edge,fan,ean))break;
 }
 /*  try to delete tesselated vertices */
 if(phase == 1)for(loop=0;loop<nloop;loop++){
   if(!DeTesselate(vl,nvl,w,n_work_face,we,n_work_edge,fan))break;
 }

 EraseVertex(1);
 FreeAdjFaces(vl,nvl);
 goto QUIT;
 BERR2:
 MessageBox(NULL,"Normal - Problem",NULL,MB_OK); goto QUIT;
 goto QUIT;
 BERR:
 MessageBox(NULL,"Memory Error",NULL,MB_OK);
 QUIT:
 if(w != NULL)X__Free(w);
 if(we != NULL)X__Free(we);
 if(phase == 0){phase=1; goto PHASE;}
 vp=MainVp; for(c=0;c<Nvert;c++){
   if(vp->status == INEDITOR)vp->status=DESELECTED;
   vp++;
 }
 return;
}

static int co_attrib(long if1, long if2){
 int i;
 face *f1,*f2;
 f1=(MainFp+if1); f2=(MainFp+if2);
 if(f1->material != f2->material)return 0;
 if(f1->imagemap != f2->imagemap)return 0;
 return 1;
}

static int co_planar(vector n1, vector n2, double angle){
 if(fabs(DOT(n1,n2)) > angle)return 1; /* if planar */
 return 0;
}

static int co_linear(long e1, long e2, selectededge *we, double angle){
 vertex *v0,*v1;
 vector a,b;
 edge *ep;
 if(e1 < 0 || e2 < 0){
   return 0;
 }
 ep=(MainEp+we[e1].e);
 v0=(MainVp+ep->V[0]); v1=(MainVp+ep->V[1]);
 VECSUB((double)v0->xyz,(double)v1->xyz,a)
 if(O_normalize(a) == FAIL)return 0;
 ep=(MainEp+we[e2].e);
 v0=(MainVp+ep->V[0]); v1=(MainVp+ep->V[1]);
 VECSUB((double)v0->xyz,(double)v1->xyz,b)
 if(O_normalize(b) == FAIL)return 0;
 if(fabs(DOT(a,b)) > angle)return 1;
 return 0;
}

static void IdentifyGeometry(long i, long j,
                             long *f0, long *f1, long *f2,
                             long *e0, long *e1, long *e2,
                             long *fx, long *ex,
                             long *fxx, long *exx,
                             long *fxxx, long *exxx,
                             long *v0, long *v1, long *v2,
                             long *vll, long *vlll,
                             selectedface *wf,selectededge *we){
 face *f;
 long va,vb;
 long k,l,ll,e,m[3]={1,2,0},n[3]={2,0,1};
 *f0=wf[i].fa[j]; *f1=wf[i].fa[m[j]]; *f2=wf[i].fa[n[j]];
 *e0=wf[i].ea[j]; *e1=wf[i].ea[m[j]]; *e2=wf[i].ea[n[j]];
 f=(MainFp+wf[i].f);
 *v0 = f->V[j]; *v1 = f->V[m[j]]; *v2=f->V[n[j]];
 *fx = -1; *ex = -1; *fxx = -1; *exx = -1; *vll = -1;
 *fxxx = -1; *exxx = -1; *vlll = -1;
 if(*f1 >= 0){
   for(k=0;k<3;k++){
    if(wf[*f1].fa[k] != i){
      e=wf[*f1].ea[k]; if(e < 0)return;
      va=(MainEp+(we[e].e))->V[0]; vb=(MainEp+(we[e].e))->V[1];
      if(*v1 == va || *v1 == vb){
        *ex=e; *fx=wf[*f1].fa[k];
        if(*fx < 0 || e < 0)return;
        if((MainEp+(we[e].e))->V[0] != *v1) *vll = (MainEp+(we[e].e))->V[0];
        else                                *vll = (MainEp+(we[e].e))->V[1];
        for(l=0;l<3;l++){
          if(wf[*fx].fa[l] != *f1){
            e=wf[*fx].ea[l];
            if(e >= 0){
              va=(MainEp+(we[e].e))->V[0]; vb=(MainEp+(we[e].e))->V[1];
              if(*v1 == va || *v1 == vb){
                if(e != *e0){
                  *exx=e; *fxx=wf[*fx].fa[l];
                  if(*fxx < 0 || e < 0)return;
                  if((MainEp+(we[e].e))->V[0] != *v1)
                    *vlll = (MainEp+(we[e].e))->V[0];
                  else
                    *vlll = (MainEp+(we[e].e))->V[1];
                  for(ll=0;ll<3;ll++){
                    if(wf[*fxx].fa[ll] != *f1){
                      e=wf[*fxx].ea[ll];
                      if(e >= 0){
                        va=(MainEp+(we[e].e))->V[0];
                        vb=(MainEp+(we[e].e))->V[1];
                        if(*v1 == va || *v1 == vb){
                          if(e != *e0){
                            *exxx=e; *fxxx=wf[*fxx].fa[ll];
                            return;
                          }
                        }
                      }
                    }
                  }
                  return;
                }
              }
            }
          }
        }
        return;
      }
    }
   }
 }
 return;
}

static void IdentifyAdjacent(long i,long f0, long v0, long v1,
                             long *fl, long *el, long *fn, long *en,
                             long  *fnn, long *vn, long *vnn,
                             selectedface *wf,selectededge *we){
 long k,l;
 face *f;
 edge *e;
 *vn = -1; *vnn = -1;
 *fl = *fn = *el = *en = *fnn = -1;
 for(k=0;k<3;k++){
   f=(MainFp+wf[f0].f);
   if(f->V[k] != v0 && f->V[k] != v1)*vn=f->V[k];
   if((l=wf[f0].fa[k]) != i){
     if(l >= 0){
       f=(MainFp+wf[l].f);
       if(f->V[0] == v0 || f->V[1] == v0 || f->V[2] == v0) *fl = l;
       if(f->V[0] == v1 || f->V[1] == v1 || f->V[2] == v1) *fn = l;
     }
     if(wf[f0].ea[k] >= 0){
       e=(MainEp+we[wf[f0].ea[k]].e);
       if(e->V[0] == v0 || e->V[1] == v0) *el = wf[f0].ea[k];
       if(e->V[0] == v1 || e->V[1] == v1) *en = wf[f0].ea[k];
     }
   }
 }
 if(*fn >= 0){
   for(k=0;k<3;k++){
     f=(MainFp+wf[*fn].f);
     if(f->V[k] != v1 && f->V[k] != *vn)*vnn=f->V[k];
     if((l=wf[*fn].fa[k]) != f0){
       if(l >= 0){
         f=(MainFp+wf[l].f);
         if(f->V[0] == v1 || f->V[1] == v1 || f->V[2] == v1) *fnn = l;
       }
     }
   }
 }
}

static int BadAngle(long iv0, long iv1, long ivn, long ivnn){
 vector a,b,c;
 double c1,c2;
 vertex *v0,*v1,*vn,*vnn;
 if(iv0 < 0 || iv1 < 0 || ivn < 0 || ivnn < 0)return 1;
 v0=(MainVp+iv0);  v1=(MainVp+iv1); vn=(MainVp+ivn); vnn=(MainVp+ivnn);
 if(v0 == NULL || v1 == NULL || vn == NULL || vnn == NULL)return 1;
 VECSUB((double)vnn->xyz,(double)vn->xyz,a)
 VECSUB((double)v1->xyz,(double)vn->xyz,b)
 VECSUB((double)v0->xyz,(double)vn->xyz,c)
 if(O_normalize(a) == FAIL)return 1;    /* angle v0->vn-vnn (inc v1) > PI */
 if(O_normalize(b) == FAIL)return 1;
 if(O_normalize(c) == FAIL)return 1;
 if(acos(DOT(b,a))+acos(DOT(b,c)) > PI - 0.1)return 1;
 return 0;
}

static int Simplify1(vtyadj *vl, long nvl,
                        selectedface *w, long nf,
                        selectededge *we, long ne,
                        double fan, double ean){
 face *ff;
 edge *ee;
 long f,e;
 long vp,v0,v1,v2,vn,vnn,vll,vlll;
 long c,h,i,j,k,l,m,n,second_type=0;
 long f0,f1,f2,e0,e1,e2,fx,ex,fxx,exx,fxxx,exxx,fl,fn,el,en,fnn,ev;
 int reduc;
 reduc=0;
 for(i=0;i<nf;i++){
   if(w[i].del)continue;  /* face is gone */
   for(h=0;h<2;h++){/* reverse direction of face */
     for(j=0;j<3;j++){
       IdentifyGeometry(i,j,&f0,&f1,&f2,&e0,&e1,&e2,
                            &fx,&ex,&fxx,&exx,&fxxx,&exxx,
                            &v0,&v1,&v2,&vll,&vlll,
                            w,we);
       if(f1 >= 0){                         /* possible reduction         */
         if(co_planar(w[i].n,w[f1].n,fan) &&
            co_attrib(w[i].f,w[f1].f)){     /* faces i + f1 planar        */
           if(co_linear(e0,ex,we,ean)){     /* edge e0                    */
             second_type=0;
             SECONDTYPE:
             if(f0 < 0 && fx >= 0)goto LOOP;    /* can't do these         */
             if(f0 >= 0 && fx < 0)goto LOOP;    /* either                 */
             if(f0 >= 0){
               IdentifyAdjacent(i,f0,v0,v1,&fl,&el,&fn,&en,&fnn,&vn,&vnn,w,we);
               if(fn == fx)fnn = -1;
               else if(BadAngle(v0,v1,vn,vnn))goto LOOP;/* test angle v0-vn-vnn */
               if(fn != fx && fnn != fx)goto LOOP;
               if(fn < 0)goto LOOP;
               if(!co_attrib(w[f0].f,w[fn].f))goto LOOP;
               if(fnn >= 0 && !co_attrib(w[fn].f,w[fnn].f))goto LOOP;
             }
             w[i].del=1;
             if(e2 < 0)goto LOOP;
             for(k=0;k<2;k++){
               if(we[e2].ea[k] == i)we[e2].ea[k]=f1;
             }
             for(k=0;k<3;k++){
               if(w[f1].fa[k] ==  i)w[f1].fa[k]=f2;
               if(w[f1].ea[k] == e1)w[f1].ea[k]=e2;
               if(f2 >= 0){ /* fix up adjacent to i */
                 if(w[f2].fa[k] ==  i)w[f2].fa[k]=f1;
               }
             }
             /* label vertex for deletion                             */
             /* re-vector faces and edges away from deleted vector    */
             /* leave attached any edge or face that is to be deleted */
             /* then EraseVertex will take care of it                 */
             f=w[f1].f; ff=(MainFp+f);
             for(k=0;k<3;k++){
               if(ff->V[k] == v1)ff->V[k]=v0;
             }
             e=we[ex].e; ee=(MainEp+e);
             for(k=0;k<2;k++){
               if(ee->V[k] == v1)ee->V[k]=v0;
             }
             (MainVp+v1)->status=SELECTED;
             NvertSelect++; NvertDeselect--; reduc=1;
             if(second_type > 0){
               f=w[fxx].f; ff=(MainFp+f);
               for(k=0;k<3;k++){
                 if(ff->V[k] == v1)ff->V[k]=v0;
               }
               e=we[exx].e; ee=(MainEp+e);
               for(k=0;k<2;k++){
                 if(ee->V[k] == v1)ee->V[k]=v0;
               }
               if(second_type > 1){
                 f=w[fxxx].f; ff=(MainFp+f);
                 for(k=0;k<3;k++){
                   if(ff->V[k] == v1)ff->V[k]=v0;
                 }
                 e=we[exxx].e; ee=(MainEp+e);
                 for(k=0;k<2;k++){
                   if(ee->V[k] == v1)ee->V[k]=v0;
                 }
               }
             }
             /* reset faces adjacent to f0/en which will also disappear */
             /* any faces and edges pointing to v1 should be revectored */
             /* or left attached for deletion                           */
             if(f0 >= 0){ /* delete adjacent faces  */
               w[f0].del=1;
               f=w[fn].f; ff=(MainFp+f);
               for(k=0;k<3;k++){
                 if(fl >= 0)if(w[fl].fa[k] == f0)w[fl].fa[k]=fn;
                 if(fn >= 0)if(w[fn].fa[k] == f0)w[fn].fa[k]=fl;
                 if(fn >= 0)if(w[fn].ea[k] == en)w[fn].ea[k]=el;
                 if(ff->V[k] == v1)ff->V[k]=v0;
               }
               for(k=0;k<2;k++){
                 if(we[el].ea[k] == f0)we[el].ea[k]=fn;
               }
               if(fnn >= 0){
                 f=w[fnn].f; ff=(MainFp+f);
                 for(k=0;k<3;k++){
                   if((l=w[fnn].ea[k]) >= 0){
                     e=we[l].e; ee=(MainEp+e);
                     if(ee->V[0] == v1)ee->V[0]=v0;
                     if(ee->V[1] == v1)ee->V[1]=v0;
                   }
                   if(ff->V[k] == v1)ff->V[k]=v0;
                 }
               }
             }
             goto BREAKOUT;
           }
           else{ /* Try for case with exx linear with e0 */
             if(fx >= 0 && ex >= 0 && e0 >= 0 && exx >= 0 && vll >= 0){
               if(co_planar(w[i].n,w[fx].n,fan) &&
                  co_attrib(w[i].f,w[fx].f) &&
                  !BadAngle(v0,v1,v2,vll)){ /* test angle v0-v2-vll */
                 if(co_linear(e0,exx,we,ean)){
                   m=fx; fx=fxx;  fxx=m;
                   m=ex; ex=exx;  exx=m;
                   second_type=1;
                   goto SECONDTYPE;
                 }
                 else if(fxx >= 0 && exxx >= 0 && vlll >= 0){
                   if(co_planar(w[i].n,w[fxx].n,fan) &&
                      co_attrib(w[i].f,w[fxx].f) &&
                      !BadAngle(v2,v1,vll,vlll) &&
                      co_linear(e0,exxx,we,ean)){
                     m=fx; fx=fxxx;  n=fxx; fxx=m;  fxxx=n;
                     m=ex; ex=exxx;  n=exx; exx=m;  exxx=n;
                     second_type=2;
                     goto SECONDTYPE;
                   }
                 }
               }
             }
           }
         }
       }
       LOOP:;
     } /* try other orientation */
     f=w[i].f; ff=(MainFp+f);
     vp=ff->V[0]; ff->V[0]=ff->V[2]; ff->V[2]=vp;
     k=w[i].fa[0]; w[i].fa[0]=w[i].fa[1]; w[i].fa[1]=k;
     k=w[i].ea[0]; w[i].ea[0]=w[i].ea[1]; w[i].ea[1]=k;
   }
   BREAKOUT:;
 }
 return reduc;
}


static int VertexAdj(vtyadj vl, selectedface *wf, selectededge *we,
                     long *f0, long *f1, long *f2,
                     long *e0, long *e1, long *e2){
  face *f;
  edge *e;
  long i,j,l,nf=0,ne=0;
  *f0 = *f1 = *f2 = *e0 = *e1 =*e2 = -1;
  if((MainVp+(vl.v))->status == SELECTED)goto XXIT;
  if(vl.nf < 3 || vl.ne < 3)goto XXIT;
  for(i=0;i<vl.nf;i++){
    l=vl.flist[i];  f=(MainFp+wf[l].f);
    for(j=0;j<3;j++){  /* don't count any selected vertex */
      if((MainVp+f->V[j])->status == SELECTED)goto JUMPIT;
    }
    if(l == *f0 || l == *f1 || l == *f2)goto JUMPIT; /* don't count same faces */
    if(nf == 0) *f0 = l;   /* same faces will occur in second interations */
    if(nf == 1) *f1 = l;
    if(nf == 2) *f2 = l;
    nf++;
    JUMPIT:
    if(nf > 3)goto XXIT;
  }
  for(i=0;i<vl.ne;i++){
    l=vl.elist[i];  e=(MainEp+we[l].e);
    if((MainVp+e->V[0])->status == DESELECTED &&
       (MainVp+e->V[1])->status == DESELECTED){
      if(ne == 0) *e0 = l;
      if(ne == 1) *e1 = l;
      if(ne == 2) *e2 = l;
      ne++;
      if(ne > 3){ nf=0; goto XXIT; }
    }
  }
  XXIT:
  return nf;
}

static void GetOppositeFaceEdge(long v, long f, selectedface *wf,
                                long *fo, long *eo){
 long i,m[3]={1,2,0};
 face *ff;
 *fo = *eo = -1;
 ff= (MainFp+wf[f].f);
 for(i=0;i<3;i++){
   if(ff->V[i] == v){
     *fo = wf[f].fa[m[i]];
     *eo = wf[f].ea[m[i]];
   }
 }
 return;
}


static long GetCommonVertex(long v, long f1, long f2){
 long i,j;
 long vp;
 for(i=0;i<3;i++){
   vp=(MainFp+f1)->V[i];
   for(j=0;j<3;j++){
     if((MainFp+f2)->V[j] == vp){
       if(vp != v)return vp;
     }
   }
 }
 return -1;
}

static int DeTesselate(vtyadj *vl, long nvl,
                        selectedface *wf, long nf,
                        selectededge *we, long ne,
                        double angle){
 int reduc=0;
 long i,j,k,l;
 long f0,f1,f2,e0,e1,e2,fo1,fo2,eo1,eo2;
 long v,vid;
 face *f;
 for(i=0;i<nvl;i++){
   if(VertexAdj(vl[i],wf,we,&f0,&f1,&f2,&e0,&e1,&e2) == 3 &&   /* case 3 */
      co_planar(wf[f0].n,wf[f1].n,angle) && co_attrib(wf[f0].f,wf[f1].f) &&
      co_planar(wf[f0].n,wf[f2].n,angle) && co_attrib(wf[f0].f,wf[f2].f)){
     v=vl[i].v;
     (MainVp+v)->status=SELECTED; NvertSelect++; NvertDeselect--; reduc=1;
     GetOppositeFaceEdge(v,f1,wf,&fo1,&eo1);
     GetOppositeFaceEdge(v,f2,wf,&fo2,&eo2);
     if((vid=GetCommonVertex(v,wf[f1].f,wf[f2].f)) < 0)return 0;
     f=(MainFp+wf[f0].f);
     wf[f1].del=1;
     wf[f2].del=1;
     for(j=0;j<3;j++){
       /* fix up vertex adjacency */
       l=(long)((MainVp+(MainFp+(wf[f1].f))->V[j])->id);
       for(k=0;k<vl[l].nf;k++){
         if(vl[l].flist[k] == f1 || vl[l].flist[k] == f2)vl[l].flist[k]=f0;
       }
       l=(long)((MainVp+(MainFp+(wf[f2].f))->V[j])->id);
       for(k=0;k<vl[l].nf;k++){
         if(vl[l].flist[k] == f1 || vl[l].flist[k] == f2)vl[l].flist[k]=f0;
       }
       /* set adjacency in f0 */
       if(wf[f0].fa[j] == f1){
         wf[f0].fa[j]=fo1;
         wf[f0].ea[j]=eo1;
       }
       if(wf[f0].fa[j] == f2){
         wf[f0].fa[j]=fo2;
         wf[f0].ea[j]=eo2;
       }
       /* fix up face adjacency */
       if(f->V[j] == v)f->V[j]=vid;
       if((l=wf[f1].fa[j]) >= 0 && l != f0 && l != f1 && l != f2){
         for(k=0;k<3;k++)if(wf[l].fa[k] == f1)wf[l].fa[k]=f0;
       }
       if((l=wf[f2].fa[j]) >= 0 && l != f0 && l != f1 && l != f2){
         for(k=0;k<3;k++)if(wf[l].fa[k] == f2)wf[l].fa[k]=f0;
       }
     }
     for(j=0;j<2;j++){
       if(we[eo1].ea[j] == f1)we[eo1].ea[j]=f0;
       if(we[eo2].ea[j] == f2)we[eo2].ea[j]=f0;
     }
   }
 }
 return reduc;
}