JOINS.C

Go to the documentation of this file.

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

/***************************************************************************\

 Join a series of curves together. The algorithm works by joining groups of
 two. Find the first two curves and join them. Then get another curve and
 join that one to the closest of the first two. Repeat this process.
 The curves do not have to have the same number of vertices.

 For each group of two curves repeat the following.

1) Make a list of all vertices in path 1 and path 2 (called va1 and va2)
   numbers being Npath1 and Npath2.  (paths must be closed)

2) Find vertices in va1 and va2 that are closest together, these are vf1
   and vf2.

3) Re-make the list of vertices in the two paths so that vf1 and vf2 are
   the first vertices in the list. (this is the step that requires the
   paths to be closed).

4) We require that path 1 has the fewest number of vertices so if path 2 has
   fewer vertices then swap the paths.

*  We are now basically ready to go - but we need a direction that is the
*  same for paths one and two.

5) Compare the spacing between the second vertices in the curves
   (call it x)  with the spacing between the second vertex in curve 1
   and the last vertex in curve 2 (call it y).
   If x > y then the curves are going in the wrong the direction and so one
   must be reversed. Reverse curve two.

   ---2---1---0---n......   curve 2     The right way round
              |
              |
    ----1-----0----m....    curve 1

   ------ n---0---1--2...   curve 2     The wrong way round
              |
              |
    ----1-----0----m....    curve 1


   In the second case the distance  1 - 1 is > the distance  1- n. Getting the
   curves the right way round allows us to follow both curves in assending
   vertex order and basically join them up vertex 1 to 1, 2 to 2 etc.
   There will be a little bit of messing because curve 2 may contain more
   vertices than curve 1 but thats relatively easy to sort out. (as we shall
   see).

6) Now proceed in two passes round path 1.
   First;

   For each vertex in path 1 find the closest vertex in path 2 that does NOT
   have a vertex further along the curve already connected to a
   vertex in path 1. (Remember - path 2 may have more vertices than path 1).
   Add an edge for each of these connections.

   While doing this record for each vertex in path 1 the identity of the
   vertex in path 2 to which it is attached.

   before ...

   path 2     --- 0 ---- 1 ---- 2  ---- 3 ---- 4 -----


   path 1     --- 0 ----------- 1 ------ 2 - 3 -------

   after ...

   path 2     --- 0 ---- 1 ---- 2  ---- 3 ---- 4 -----
                  !      !             !!
                  !       !           !  !
                  !        !          !  !
                  !         !         !   !
   path 1     --- 0 -------- 1 ------ 2 - 3 -------


   After this step every vertex in path 1 will be connected to a vertex in
   path 2. There may still be some vertices in path 2 not connected and
   faces need to be created but we have a basic framework that gives
   a reasonable geometry and has no overlapping edges.

   In the example above the vertices in path 1 will record that they are
   attached,
             0 attached to 0 in curve 2.
             1             1
             2             3
             3             3
             etc.

7) Second - Go around path 1 again.
   (Most of this steps complexity is in creating the appropriate faces).
   Two markers "vactive" and "vcurrent" identity the vertices from the
   path lists so that edges and faces can be created.
   (There is a bit of fixing up to to at the ends of the curves)

   For each vertex in curve 1 do the following.

   Set k0 equal to the identity of vertex in curve 2 to which it is
   attached.
   If we are not at the end of curve 1 set k1 equal to the vertex
   in curve 2 that the next vertex in curve 1 is attached to,
   otherwise set k1 to point to beyond the end of curve2

   Now; if k1 = k0 then the next vertex in curve 1 is connected to
        the same vertex (in curve 2) and only a face need be added.

        eg   ----- n -----   Path 2
                  ! !
                 !   !     <--- Add one face
                !     !
            --- m --- l ----  Path 1

    Otherwise;
         if k1 = k0+1  then we have to add two faces and one edge

       this;
    Path 2  ------- n ------ n+1 ------          ------- n ---- n+1 ----
                    !         !                          !    .  !
                    !         !         becomes          !   .   !
                    !         !                          ! .     !
    Path 1  ------- j ------ j+1  ------         --------j ---- j+1 ---


         if k1 > k0+1  we have to add a variable number of edges and
         faces that is -;    for(j=k0+1;j<k1;j++)

            For example before this step may have something like

            ---- 3 ---- 4 ---- 5 ----- 6 ------
                  .                   .
                   .                 .
                    .               .
                     .             .
              ------- 2 --------- 3 ---------


           with edges  3 -> 2 and 3 -> 6 created in step 6.
           Faces and edge are added to build up the triangular mesh.

            ---- 3 ---- 4 ---- 5 ----- 6 ------ Path 2
                  .    .     . .      .
                   .   .   .    .    .
                    .  . .       .  .
                     . .           .
              ------- 2 ---------- 3 ---------  Path 1

           The order doesn't really matter, it could be edges,
               2 -> 4   2 -> 5   2 -> 6
           or  2 -> 4   2 -> 5   3 -> 5  (*)
           or  2 -> 4   3 -> 4   3 -> 5

           In my implementation I attach vertex 2 (path 1) to all the
           vertices in curve 2 until one of them gets closer to vertex 3
           then I attach the rest to vertex 3.
           This results in the pattern labelled (*) above.

8) Tidy up the ends where the end of the curves meet back on themselves.

\***************************************************************************/

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

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

#include "joins.h"

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

static HWND      hParent;
static HINSTANCE hThisInstance;

static void JoinCurves(void);

#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;
}

#if __SC__
#pragma startaddress(DllMain)
#endif

static BOOL CALLBACK JoinCurvesDlgProc(HWND hwnd, UINT msg,
                             WPARAM wparam, LPARAM lparam){
 switch( msg ) {
   case WM_INITDIALOG:
     CentreDlgOnS(hwnd);
     return (TRUE);
   case WM_COMMAND:
      switch(LOWORD(wparam)){
        case IDCANCEL:
          EndDialog(hwnd,FALSE);
          return(TRUE);
        case IDOK:
          EndDialog(hwnd,TRUE);
          return(TRUE);
        default:
          break;
      }
      break;
    default: break;
 }
 return(FALSE);
}

BOOL _Xmodeler
 (HWND parent_window,HWND info_window,X__STRUCTURE *lpevi){
 HCURSOR hSave;
 lpEVI=lpevi;
 hParent=parent_window;
 if(DialogBox(hThisInstance,MAKEINTRESOURCE(DLG_JOIN),hParent,
             (DLGPROC)JoinCurvesDlgProc) == FALSE)return FALSE;
 hSave=SetCursor(LoadCursor(NULL,IDC_WAIT));
 JoinCurves();
 SetCursor(hSave);
 return TRUE;
}

static double dspacing(long Va1, long Va2){
 vertex *va1,*va2;
 double d;
 va1=(MainVp+Va1); va2=(MainVp+Va2);
 d=(double)(va1->xyz[0] - va2->xyz[0]) *
   (double)(va1->xyz[0] - va2->xyz[0]) +
   (double)(va1->xyz[1] - va2->xyz[1]) *
   (double)(va1->xyz[1] - va2->xyz[1]) +
   (double)(va1->xyz[2] - va2->xyz[2]) *
   (double)(va1->xyz[2] - va2->xyz[2]);
 return sqrt(d);
}

static long get_next_closest(long vf1){
 vertex *vp;
 long i,vf;
 double dmin,d;
 dmin=1.e30;
 vf = -1;
 if((vp=MainVp) != NULL)for(i=0;i<Nvert;i++){
   if(vp->status == SELECTED){
     d=(double)(vp->xyz[0]-(MainVp+vf1)->xyz[0])*
       (double)(vp->xyz[0]-(MainVp+vf1)->xyz[0])
      +(double)(vp->xyz[1]-(MainVp+vf1)->xyz[1])*
       (double)(vp->xyz[1]-(MainVp+vf1)->xyz[1])
      +(double)(vp->xyz[2]-(MainVp+vf1)->xyz[2])*
       (double)(vp->xyz[2]-(MainVp+vf1)->xyz[2]);
     if(d < dmin){
       dmin=d;
       vf=i;
     }
   }
   vp++;
 }
 return vf;
}

static void JoinCurves(void){
 BOOL bSwapped;
 vertex *Vp;
 long vp,vf1,vf2,*va1,*va2,*tempva,tempv,vactive,vnext,vcurrent;
 double d,dmin=1e32;
 long Npath1,Npath2,i,j,k0,k1,k2,flag,lc;
 if(NvertSelect<6){MessageBeep(MB_OK); return; }
 if(NvertSelect > 32000){ MessageBeep(MB_OK); return; }
 vf1=vf2=-1;
 if((vf1=get_closest_vertex()) < 0){
   MessageBeep(MB_OK); goto GETOUT;
 }
 lc=0;
 /* */
 /* Loop over pairs of curves - curves are identified by making them  */
 /* selected/deselected                                               */
 /* */
 MAINLOOP:
 vp=0; while(vp < Nvert){ Vp=(MainVp+vp); Vp->id=0;  vp++; }
 va1=va2=NULL;
 if((va1=(long *)X__Malloc(NvertSelect*sizeof(long))) == NULL){
   MessageBeep(MB_OK);
   goto GETOUT;
 }
 Npath1=0; va1[0]=vf1; (MainVp+va1[0])->id=1;
 (MainVp+vf1)->status=DESELECTED; NvertSelect--; NvertDeselect++;
 vp=0; while(vp < Nvert){
   Vp=(MainVp+vp);
   if(Vp->status == SELECTED && Vp->id == 0 && Connected(va1[Npath1],vp)){
     Npath1++;
     va1[Npath1]=vp;
     Vp->id=1;   /* flag so not used again also indicates in path */
     Vp->status=DESELECTED;
     NvertSelect--; NvertDeselect++;
     vp=0;
   }
   else vp++;
 }
 if((vf2=get_next_closest(vf1)) < 0){
   MessageBeep(MB_OK);
   X__Free(va1);
   goto GETOUT;
 }
 if((va2=(long *)X__Malloc(NvertSelect*sizeof(long))) == NULL){
   MessageBeep(MB_OK);
   X__Free(va1);
   goto GETOUT;
 }
 Npath2=0; va2[0]=vf2; (MainVp+va2[0])->id=2;
 (MainVp+vf2)->status=DESELECTED; NvertSelect--; NvertDeselect++;
 vp=0; while(vp < Nvert){
   Vp=(MainVp+vp);
   if(Vp->status == SELECTED && Vp->id == 0 && Connected(va2[Npath2],vp)){
     Npath2++;
     va2[Npath2]=vp;
     Vp->id=2;
     Vp->status=DESELECTED;
     NvertSelect--; NvertDeselect++;
     vp=0;
   }
   else vp++;
 }
 Npath1++; Npath2++;
 /* */
 /* At this point two curves to be joined have been identified and  */
 /* lists have been make of the vertices in each curve              */
 /* */
 if(Npath1 < 3 || Npath2 < 3){
   MessageBeep(MB_OK);
   X__Free(va1);
   X__Free(va2);
   goto GETOUT;
 }
 /* */
 /* Find the vertices in curve 1 and 2 that is closest together      */
 /* */
 for(i=0;i<Npath1;i++)
   for(j=0;j<Npath2;j++){
     if((d=dspacing(va1[i],va2[j])) < dmin){
       dmin=d; vf1=va1[i]; vf2=va2[j];
     }
 }
 /* */
 /*  Re-make the curves so that vf1 and vf2 are at the start of the list */
 /* */
 Npath1=0; va1[0]=vf1; (MainVp+va1[0])->id=0;
 vp=0; while(vp < Nvert){
   Vp=(MainVp+vp);
   if(Vp->id == 1 && Connected(va1[Npath1],vp)){
     Npath1++;
     va1[Npath1]=vp;
     Vp->id=0;
     vp=0;
   }
   else vp++;
 }
 Npath2=0; va2[0]=vf2; (MainVp+va2[0])->id=0;
 vp=0; while(vp < Nvert){
   Vp=(MainVp+vp);
   if(Vp->id == 2 && Connected(va2[Npath2],vp)){
     Npath2++;
     va2[Npath2]=vp;
     Vp->id=0;
     vp=0;
   }
   else vp++;
 }
 /* */
 /* Curves re-made */
 /* */
 if(Npath1 == 0 || Npath2 == 0){
   MessageBox(NULL,"Fatal Fail",NULL,MB_OK);
   goto GETOUT;
 }
 /* */
 /* Make curve 1 the curve with the fewest number of vertices */
 /* */
 Npath1++; Npath2++;
 if(Npath2 < Npath1){
   tempv=vf1; vf1=vf2; vf2=tempv;
   tempva=va1; va1=va2; va2=tempva;
   i=Npath1; Npath1=Npath2; Npath2=i;
   bSwapped=TRUE;
 }
 else bSwapped=FALSE;
 /* *\
 If necessary reverse the order of vertices along curve 2
 \* */
 if(dspacing(va1[1],va2[1]) > dspacing(va1[1],va2[Npath2-1])){
   for(i=1;i<=(Npath2-1)/2;i++){
     tempv=va2[i];
     va2[i]=va2[Npath2-i];
     va2[Npath2-i]=tempv;
   }
 }
 if(!UpdateEdgeHeap(Nedge+2*(Npath1+Npath2+1)))goto UPDATE_HEAP;
 if(!UpdateFaceHeap(Nface+2*(Npath1+Npath2+4)))goto UPDATE_HEAP;
 k0=1;
 /* *\
 Join each vertex in curve 1 to nearest vertex in curve 2 (Step 6 above)
 \* */
 CreateEdge(va1[0],va2[0]);
 (MainVp+va1[0])->id=0;
 for(i=1;i<Npath1;i++){
   dmin=1e32; k1= -1;
   if(k0 < Npath2)for(j=k0;j<Npath2;j++){
     if((d=dspacing(va1[i],va2[j])) < dmin){dmin=d; k1=j;}
   }
   if(k1 >= 0){
     k0=k1;
     (MainVp+va1[i])->id=k0;
     CreateEdge(va1[i],va2[k0]);
   }
 }
 /* *\
 Step 7
 \* */
 for(i=0;i<Npath1;i++){
   flag=0;
   vactive=va1[i];
   k0=(long)((MainVp+va1[i])->id);
   vcurrent=va2[k0];
   if(i < Npath1-1){
     vnext=va1[i+1];
     k1=(long)((MainVp+va1[i+1])->id);
     k2=k1;
   }
   else{
     vnext=va1[0]; k1=Npath2; k2=0;
   }
   if(k1 > k0){           /* must add at least 1 edge and 2 faces  */
     if(k1 > k0+1){       /* must add at least 2 edges and 3 faces */
       for(j=k0+1;j<k1;j++){
         vcurrent=va2[j];
         if(flag == 0){
           CreateEdge(vcurrent,vactive);
           CreateFace(vactive,vcurrent,va2[j-1]);
           if(dspacing(vcurrent,va2[k0]) > dspacing(vcurrent,va2[k2])){
             CreateEdge(vcurrent,vnext);
             CreateFace(vactive,vcurrent,vnext);
             flag=1;
           }
         }
         else{
           CreateEdge(vcurrent,vnext);
           CreateFace(va2[j-1],vnext,vcurrent);
         }
       }
     }
     if(flag == 0){
       CreateEdge(vcurrent,vnext);
       CreateFace(vactive,vnext,vcurrent);
     }
     CreateFace(vcurrent,vnext,va2[k2]);
   }
   else{  /* no edges required only one face - edge make in step 6 */
     CreateFace(vactive,vcurrent,vnext);
   }
 }
 /* *\
 End of step 7 - now get the next two curves in the sequence, curve 1
 will become the current curve 2
 \* */
 if(NvertSelect > 3){ /* move onto next curve - select the old curve */
   if(bSwapped){
     for(i=0;i<Npath1;i++){
       (MainVp+va1[i])->status = SELECTED;
       NvertSelect++; NvertDeselect--;
     }
   }
   else{
     vf1=vf2;
     for(i=0;i<Npath2;i++){
       (MainVp+va2[i])->status = SELECTED;
       NvertSelect++; NvertDeselect--;
     }
   }
   if(va1 != NULL)X__Free(va1); va1=NULL;
   if(va2 != NULL)X__Free(va2); va2=NULL;
   lc++;
   goto MAINLOOP;
 }
 UPDATE_HEAP:
 UpdateFaceHeap(Nface);
 UpdateEdgeHeap(Nedge);
 if(va1 != NULL)X__Free(va1);
 if(va2 != NULL)X__Free(va2);
 GETOUT:
 return;
}