SUBDIV.CPP

Go to the documentation of this file.

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

/* SUBDIV.C  */

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

#ifdef __cplusplus
extern "C" {
#endif

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

#ifdef __cplusplus
}
#endif

#include "subdiv.h"

#define DESELECTED 0
#define SELECTED   1
#define FAIL      -1
#define OK         1


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=(HINSTANCE)hDLL;
      if(hDLL == NULL)MessageBox ( GetFocus()," NULL instance",NULL, MB_OK);
      break;
    }
    case DLL_PROCESS_DETACH:
      break;
  }
  return TRUE;
}

#if __SC__
#pragma startaddress(DllMain)
#endif

static int BuildNormals(long down_to_f, long down_to_e);
static int Subdivide(long down_to_f, long down_to_e);

extern "C" BOOL _Xmodeler
 (HWND parent_window,HWND info_window,X__STRUCTURE *lpevi){
 lpEVI=lpevi;
 hParent=parent_window;
// if(MessageBox(hParent,"Subdivide selected faces ?","Subdivide",MB_OKCANCEL)
//               == IDCANCEL)return FALSE;
// else
 {
   HCURSOR hSave;
   if(NvertSelect == 0 || NvertSelect > 32000)return FALSE;
   hSave=SetCursor(LoadCursor(NULL,IDC_WAIT));
   OrientateSelectedFaces();
   Subdivide(0,0);
//   BuildNormals(0,0);
   SetCursor(hSave);
 }
 return TRUE;
}

#define VECCOPY(a,b)    { b[0] = a[0]; b[1] = a[1]; b[2] = a[2]; }
#define VECSUB(a,b,c)   { c[0]=a[0]-b[0]; c[1]=a[1]-b[1]; c[2]=a[2]-b[2];}
#define VECSUM(a,b,c)   { c[0]=a[0]+b[0]; c[1]=a[1]+b[1]; c[2]=a[2]+b[2];}
#define VECSCALE(a,b,c) { c[0]=(a)*b[0]; c[1]=(a)*b[1]; c[2]=(a)*b[2];}
#define DOT(a,b)        ( (a[0]*b[0]) + (a[1]*b[1]) + (a[2]*b[2]) )
#define CROSS(v1,v2,r)  { \
                          r[0] = (v1[1]*v2[2]) - (v2[1]*v1[2]);  \
                          r[1] = (v1[2]*v2[0]) - (v1[0]*v2[2]);  \
                          r[2] = (v1[0]*v2[1]) - (v2[0]*v1[1]);  \
                         }

typedef struct tagVERTEXVERTEX{
 long vl,vr;
} VERTEXVERTEX;

typedef struct tagFACEEXTRA{
 long extra,xxtra;
} FACEEXTRA;

typedef struct tagVERTEXNORMAL{
 BOOL set;
 vector n;
} VERTEXNORMAL;


static BOOL GetFaceNormal(vertex *V0, vertex *V1, vertex *V2,
                          vector n){
  vector u,v;
  VECSUB((double)V1->xyz,(double)V0->xyz,u)
  VECSUB((double)V2->xyz,(double)V0->xyz,v)
  CROSS(u,v,n);
  if(oNormalize(n) == FAIL)return FALSE;
  return TRUE;
}

static void  SetNewVertexPosition(vertex *Vn, long vl, long vr,
                                  VERTEXNORMAL *MainPp, long Pmax){
 double l,dot;
 vertex *V0, *V1;
 vector p,dp,dl;
 V0=(MainVp+vl);
 V1=(MainVp+vr);
 if(vl >= Pmax || vr >= Pmax || !((MainPp+vl)->set) || !((MainPp+vr)->set)){
   Vn->xyz[0]=(V0->xyz[0] + V1->xyz[0])/2;
   Vn->xyz[1]=(V0->xyz[1] + V1->xyz[1])/2;
   Vn->xyz[2]=(V0->xyz[2] + V1->xyz[2])/2;
   return;
 }
 l=sqrt((double)(V1->xyz[0] - V0->xyz[0])*(double)(V1->xyz[0] - V0->xyz[0])+
        (double)(V1->xyz[1] - V0->xyz[1])*(double)(V1->xyz[1] - V0->xyz[1])+
        (double)(V1->xyz[2] - V0->xyz[2])*(double)(V1->xyz[2] - V0->xyz[2]));
 VECSUM((MainPp+vl)->n,(MainPp+vr)->n,dp)
 VECSUB((double)V1->xyz,(double)V0->xyz,dl)
 oNormalize(dp);
 oNormalize(dl);
 p[0]=(double)(V0->xyz[0] + V1->xyz[0])/2;
 p[1]=(double)(V0->xyz[1] + V1->xyz[1])/2;
 p[2]=(double)(V0->xyz[2] + V1->xyz[2])/2;
 dot=DOT((MainPp+vl)->n,(MainPp+vr)->n);
 l *= (1.0-dot)*0.20710678;  // (root 2 - 1)/2
 l *= 2;
 vector d,r;
 CROSS((MainPp+vl)->n,(MainPp+vr)->n,d)
 CROSS(dl,d,r)
 if(DOT(r,(MainPp+vl)->n) < 0.0)l *= -1;
 Vn->xyz[0]=(long)(p[0]+l*dp[0]);
 Vn->xyz[1]=(long)(p[1]+l*dp[1]);
 Vn->xyz[2]=(long)(p[2]+l*dp[2]);
 return;
}

/* making list of vertices adjacent to new vertices improves effiency     */
/* it uses the vertex ID to store index to array giving adjacent vertices */
/* effient could be further improved by making a list of relevant faces   */

static int Subdivide(long down_to_f, long down_to_e){
 vector face_normal;
 face *fp;
 edge *ep;
 vertex *vp,*V0,*V1,*V2;
 long i,j,vl,vr,id,nf=0,ne=0,n,Nedge1,Nface1,Nv1,Nnormals;
 VERTEXVERTEX *vlist=NULL;
 FACEEXTRA    *MainLp=NULL,*lp;
 VERTEXNORMAL *MainPp=NULL,*pp;
 HCURSOR hSave;
 /* get upper bound for number of faces selected */
 if(down_to_f < Nface){
   if((MainLp=(FACEEXTRA *)X__Malloc(Nface*sizeof(FACEEXTRA))) == NULL){
     return FAIL;
   }
   Nnormals=Nvert;
   if((MainPp=(VERTEXNORMAL *)X__Malloc(Nvert*sizeof(VERTEXNORMAL))) == NULL){
     if(MainLp != NULL)X__Free(MainLp);
     return FAIL;
   }
   for(i=0,pp=MainPp;i<Nnormals;i++,pp++){
     pp->set=FALSE;
     pp->n[0] = pp->n[1] = pp->n[2] = 0.0;
   }
   fp=(MainFp+down_to_f); lp=(MainLp+down_to_f); nf=0;
   for(i=down_to_f;i<Nface;i++){
     lp->extra = -1;
     lp->xxtra = -1;
     V0=(MainVp+fp->V[0]); V1=(MainVp+fp->V[1]); V2=(MainVp+fp->V[2]);
     if((V0->status == SELECTED && V1->status == SELECTED) ||
        (V1->status == SELECTED && V2->status == SELECTED) ||
        (V2->status == SELECTED && V0->status == SELECTED)){
        if(GetFaceNormal(V0,V1,V2,face_normal)){
          VECSUM((MainPp+fp->V[0])->n,face_normal,(MainPp+fp->V[0])->n)
          VECSUM((MainPp+fp->V[1])->n,face_normal,(MainPp+fp->V[1])->n)
          VECSUM((MainPp+fp->V[2])->n,face_normal,(MainPp+fp->V[2])->n)
          (MainPp+fp->V[0])->set=TRUE;
          (MainPp+fp->V[1])->set=TRUE;
          (MainPp+fp->V[2])->set=TRUE;
        }
        nf++;
     }
     fp++; lp++;
   }
 }
 for(i=0,pp=MainPp;i<Nnormals;i++,pp++){
   if(pp->set){
     if(oNormalize(pp->n) == FAIL)pp->set=FALSE;
   }
 }
 for(ep=(MainEp+down_to_e),ne=0,i=down_to_e;i<Nedge;i++){
   if((MainVp+ep->V[0])->status == SELECTED &&
      (MainVp+ep->V[1])->status == SELECTED)ne++; // number of edges to be divided
   ep++;
 }
 if(ne == 0){
   if(MainLp != NULL)X__Free(MainLp);
   if(MainPp != NULL)X__Free(MainPp);
   return FAIL;
 }
 /* extend the Vertices Edges and Faces arrays to their upper bounds */
 if((vlist=(VERTEXVERTEX *)X__Malloc(ne*sizeof(VERTEXVERTEX))) == NULL){
   if(MainPp != NULL)X__Free(MainPp);
   if(MainLp != NULL)X__Free(MainLp);
   return FAIL;
 }
 if(!UpdateVertexHeap(Nvert+ne))goto EP1;
 if(!UpdateEdgeHeap(Nedge+ne+nf*3))goto EP1;
 if(!UpdateFaceHeap(Nface+nf*3))goto EP1;
 Nface1=Nface; Nedge1=Nedge;
 ep=(MainEp+down_to_e); n=0;
 for(i=down_to_e;i<Nedge1;i++){
   vl=ep->V[0]; V0=(MainVp+vl); vr=ep->V[1]; V1=(MainVp+vr);
   if(V0->status == SELECTED && V1->status == SELECTED){
     CreateVertex(); Nv1=Nvert-1;
     vlist[n].vl=vl; vlist[n].vr=vr; (MainVp+Nv1)->id=n; n++;
     SetNewVertexPosition((MainVp+Nv1),vl,vr,MainPp,Nnormals);
     CreateEdge(Nv1,ep->V[1]);
     ep->V[1]=Nv1;
     if(down_to_f < Nface1){
       fp=(MainFp+down_to_f); lp=(MainLp+down_to_f);
       for(j=down_to_f;j<Nface1;j++){
        id=0;
        if     ((fp->V[0] == vl && fp->V[1] == vr) ||
                (fp->V[0] == vr && fp->V[1] == vl) )id=1;
        else if((fp->V[1] == vl && fp->V[2] == vr) ||
                (fp->V[1] == vr && fp->V[2] == vl) )id=2;
        else if((fp->V[2] == vl && fp->V[0] == vr) ||
                (fp->V[2] == vr && fp->V[0] == vl) )id=3;
        if(id != 0){
          if(lp->extra < 0)lp->extra=Nv1;
          else{
            if(lp->xxtra < 0)lp->xxtra=Nv1;
            else{
               CreateEdge(Nv1,lp->extra);
               CreateEdge(Nv1,lp->xxtra);
               CreateEdge(lp->extra,lp->xxtra);
               if     (id == 1){
                 if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                             fp->V[2],lp->xxtra,lp->extra))
                   CreateFace(fp->V[2],lp->xxtra,lp->extra);
                 else
                   CreateFace(fp->V[2],lp->extra,lp->xxtra);
                 CopyFaceProp(fp,(MainFp+Nface-1));
                 if(vlist[(MainVp+lp->extra)->id].vl == fp->V[0] ||
                    vlist[(MainVp+lp->extra)->id].vr == fp->V[0]){
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[0],Nv1,lp->extra))
                     CreateFace(fp->V[0],Nv1,lp->extra);
                   else
                     CreateFace(fp->V[0],lp->extra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[1],Nv1,lp->xxtra))
                     CreateFace(fp->V[1],Nv1,lp->xxtra);
                   else
                     CreateFace(fp->V[1],lp->xxtra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                 }
                 else{
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[1],Nv1,lp->extra))
                     CreateFace(fp->V[1],Nv1,lp->extra);
                   else
                     CreateFace(fp->V[1],lp->extra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[0],Nv1,lp->xxtra))
                     CreateFace(fp->V[0],Nv1,lp->xxtra);
                   else
                     CreateFace(fp->V[0],lp->xxtra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                 }
               }
               else if(id == 2){
                 if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                             fp->V[0],lp->xxtra,lp->extra))
                   CreateFace(fp->V[0],lp->xxtra,lp->extra);
                 else
                   CreateFace(fp->V[0],lp->extra,lp->xxtra);
                 CopyFaceProp(fp,(MainFp+Nface-1));
                 if(vlist[(MainVp+lp->extra)->id].vl == fp->V[1] ||
                    vlist[(MainVp+lp->extra)->id].vr == fp->V[1]){
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[1],Nv1,lp->extra))
                     CreateFace(fp->V[1],Nv1,lp->extra);
                   else
                     CreateFace(fp->V[1],lp->extra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[2],Nv1,lp->xxtra))
                     CreateFace(fp->V[2],Nv1,lp->xxtra);
                   else
                     CreateFace(fp->V[2],lp->xxtra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                 }
                 else{
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[2],Nv1,lp->extra))
                     CreateFace(fp->V[2],Nv1,lp->extra);
                   else
                     CreateFace(fp->V[2],lp->extra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[1],Nv1,lp->xxtra))
                     CreateFace(fp->V[1],Nv1,lp->xxtra);
                   else
                     CreateFace(fp->V[1],lp->xxtra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                 }
               }
               else if(id == 3){
                 if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                             fp->V[1],lp->xxtra,lp->extra))
                   CreateFace(fp->V[1],lp->xxtra,lp->extra);
                 else
                   CreateFace(fp->V[1],lp->extra,lp->xxtra);
                 CopyFaceProp(fp,(MainFp+Nface-1));
                 if(vlist[(MainVp+lp->extra)->id].vl == fp->V[2] ||
                    vlist[(MainVp+lp->extra)->id].vr == fp->V[2]){
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[2],Nv1,lp->extra))
                     CreateFace(fp->V[2],Nv1,lp->extra);
                   else
                     CreateFace(fp->V[2],lp->extra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[0],Nv1,lp->xxtra))
                     CreateFace(fp->V[0],Nv1,lp->xxtra);
                   else
                     CreateFace(fp->V[0],lp->xxtra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                 }
                 else{
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[0],Nv1,lp->extra))
                     CreateFace(fp->V[0],Nv1,lp->extra);
                   else
                    CreateFace(fp->V[0],lp->extra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                   if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                               fp->V[2],Nv1,lp->xxtra))
                     CreateFace(fp->V[2],Nv1,lp->xxtra);
                   else
                     CreateFace(fp->V[2],lp->xxtra,Nv1);
                   CopyFaceProp(fp,(MainFp+Nface-1));
                 }
               }
               if(IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                          lp->xxtra,lp->extra,Nv1)){
                 fp->V[0]=lp->xxtra;
                 fp->V[1]=lp->extra;
                 fp->V[2]=Nv1;
               }
               else{
                 fp->V[0]=lp->xxtra;
                 fp->V[1]=Nv1;
                 fp->V[2]=lp->extra;
               }
               lp->extra = -1;
               lp->xxtra = -1;
            }
          }
        }
        fp++; lp++;
       }
     }
   }
   ep++;
 }
 if(down_to_f < Nface1){
   fp=(MainFp+down_to_f); lp=(MainLp+down_to_f);
   for(i=down_to_f;i<Nface1;i++){
     V0=(MainVp+fp->V[0]);
     V1=(MainVp+fp->V[1]);
     V2=(MainVp+fp->V[2]);
     if(lp->extra >= 0){
       if(V0->status == DESELECTED){
         if( IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                      fp->V[0],lp->extra,fp->V[2]))
           CreateFace(fp->V[0],lp->extra,fp->V[2]);
         else
           CreateFace(fp->V[0],fp->V[2],lp->extra);
         CopyFaceProp(fp,(MainFp+Nface-1));
         CreateEdge(fp->V[0],lp->extra);
         fp->V[2] = lp->extra;
       }
       else if(V1->status == DESELECTED){
         if( IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                      fp->V[1],lp->extra,fp->V[0]))
           CreateFace(fp->V[1],lp->extra,fp->V[0]);
         else
           CreateFace(fp->V[1],fp->V[0],lp->extra);
         CopyFaceProp(fp,(MainFp+Nface-1));
         CreateEdge(fp->V[1],lp->extra);
         fp->V[0] = lp->extra;
       }
       else if(V2->status == DESELECTED){
         if( IsFOSame(fp->V[0],fp->V[1],fp->V[2],
                      fp->V[2],lp->extra,fp->V[1]))
           CreateFace(fp->V[2],lp->extra,fp->V[1]);
         else
           CreateFace(fp->V[2],fp->V[1],lp->extra);
         CopyFaceProp(fp,(MainFp+Nface-1));
         CreateEdge(fp->V[2],lp->extra);
         fp->V[1] = lp->extra;
       }
     }
     fp++; lp++;
   }
 }
 X__Free(vlist);
 if(MainLp != NULL)X__Free(MainLp);
 if(MainPp != NULL)X__Free(MainPp);
 return OK;
 EP1:
 if(MainLp != NULL)X__Free(MainLp);
 if(MainPp != NULL)X__Free(MainPp);
 X__Free(vlist);
 return FAIL;
}

static void  SetVertexNormalPosition(vertex *Vn, long vc,
                                  VERTEXNORMAL *MainPp, long Pmax){
 double l;
 vertex *V0;
 vector p,dp;
 V0=(MainVp+vc);
 if(vc >= Pmax  || !((MainPp+vc)->set) ){
   Vn->xyz[0]=V0->xyz[0];
   Vn->xyz[1]=V0->xyz[1];
   Vn->xyz[2]=V0->xyz[2];
   return;
 }
 l=(double)TVsizeX/10;
 VECCOPY((MainPp+vc)->n,dp)
 VECCOPY((double)V0->xyz,p)
 Vn->xyz[0]=(long)(p[0]+l*dp[0]);
 Vn->xyz[1]=(long)(p[1]+l*dp[1]);
 Vn->xyz[2]=(long)(p[2]+l*dp[2]);
 return;
}

static int BuildNormals(long down_to_f, long down_to_e){
 vector face_normal;
 vertex *vp,*V0,*V1,*V2;
 face *fp;
 long i,Nv1,Nv,Nnormals;
 VERTEXNORMAL *MainPp=NULL,*pp;
 /* get upper bound for number of faces selected */
 if(down_to_f < Nface){
   Nnormals=Nvert;
   if((MainPp=(VERTEXNORMAL *)X__Malloc(Nvert*sizeof(VERTEXNORMAL))) == NULL){
     return FAIL;
   }
   for(i=0,pp=MainPp;i<Nnormals;i++,pp++){
     pp->set=FALSE;
     pp->n[0] = pp->n[1] = pp->n[2] = 0.0;
   }
   fp=(MainFp+down_to_f);
   for(i=down_to_f;i<Nface;i++){
     V0=(MainVp+fp->V[0]); V1=(MainVp+fp->V[1]); V2=(MainVp+fp->V[2]);
     if((V0->status == SELECTED && V1->status == SELECTED) ||
        (V1->status == SELECTED && V2->status == SELECTED) ||
        (V2->status == SELECTED && V0->status == SELECTED)){
        if(GetFaceNormal(V0,V1,V2,face_normal)){
          VECSUM((MainPp+fp->V[0])->n,face_normal,(MainPp+fp->V[0])->n)
          VECSUM((MainPp+fp->V[1])->n,face_normal,(MainPp+fp->V[1])->n)
          VECSUM((MainPp+fp->V[2])->n,face_normal,(MainPp+fp->V[2])->n)
          (MainPp+fp->V[0])->set=TRUE;
          (MainPp+fp->V[1])->set=TRUE;
          (MainPp+fp->V[2])->set=TRUE;
        }
     }
     fp++;
   }
 }
 for(i=0,pp=MainPp;i<Nnormals;i++,pp++){
   if(pp->set){
     if(oNormalize(pp->n) == FAIL)pp->set=FALSE;
   }
 }
 if(!UpdateVertexHeap(Nvert+NvertSelect))goto EP1;
 if(!UpdateEdgeHeap(Nedge+NvertSelect))goto EP1;
 Nv=Nvert;
 for(i=0,vp=MainVp;i<Nv;i++,vp++){
   if(vp->status == SELECTED){
     CreateVertex(); Nv1=Nvert-1;
     SetVertexNormalPosition((MainVp+Nv1),i,MainPp,Nnormals);
     CreateEdge(Nv1,i);
   }
 }
 if(MainPp != NULL)X__Free(MainPp);
 return OK;
 EP1:
 if(MainPp != NULL)X__Free(MainPp);
 return FAIL;
}