ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_del.c
(Generate patch)

Comparing ray/src/hd/sm_del.c (file contents):
Revision 3.7 by gwlarson, Wed Nov 11 12:05:38 1998 UTC vs.
Revision 3.12 by gwlarson, Thu Jun 10 15:22:22 1999 UTC

# Line 11 | Line 11 | static char SCCSid[] = "$SunId$ SGI";
11   #include "sm_flag.h"
12   #include "sm_list.h"
13   #include "sm_geom.h"
14 #include "sm_qtree.h"
15 #include "sm_stree.h"
14   #include "sm.h"
15  
16 < static int Max_edges=200;
16 > #define MAX_EDGE_INIT 100
17 > static int Max_edges= MAX_EDGE_INIT;
18   static EDGE *Edges=NULL;
19   static int Ecnt=0;
20  
21 < #define remove_tri_compress remove_tri
23 < remove_tri(qtptr,fptr,tptr)
24 <   QUADTREE *qtptr;
25 <   int *fptr;
26 <   int *tptr;
27 < {
28 <    int n;
29 <
30 <    if(QT_IS_EMPTY(*qtptr))
31 <      return;
32 <    if(QT_LEAF_IS_FLAG(*qtptr))
33 <      return;
34 <
35 <    n = QT_SET_CNT(qtqueryset(*qtptr))-1;
36 <    *qtptr = qtdelelem(*qtptr,*tptr);
37 <    if(n  == 0)
38 <      (*fptr) |= QT_COMPRESS;
39 <    if(!QT_FLAG_FILL_TRI(*fptr))
40 <      (*fptr)++;
41 < }
42 <
43 <
44 < smLocator_remove_tri(sm,t_id,v0_id,v1_id,v2_id)
21 > smFree_tri(sm,id,t)
22   SM *sm;
46 int t_id;
47 int v0_id,v1_id,v2_id;
48 {
49  STREE *st;
50  FVECT v0,v1,v2;
51  
52  st = SM_LOCATOR(sm);
53
54  VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm));
55  VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm));
56  VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm));
57
58  qtClearAllFlags();
59  
60  stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,&t_id);
61
62 }
63
64 smFree_tri(sm,id)
65 SM *sm;
23   int id;
24 + TRI *t;
25   {
68  TRI *tri;
69
70  tri = SM_NTH_TRI(sm,id);
26    /* Add to the free_list */
27 <  T_NEXT_FREE(tri) = SM_FREE_TRIS(sm);
27 >  T_NEXT_FREE(t) = SM_FREE_TRIS(sm);
28    SM_FREE_TRIS(sm) = id;
29 <  T_VALID_FLAG(tri) = -1;
29 > #ifdef DEBUG
30 >  T_VALID_FLAG(t) = INVALID;
31 > #endif
32   }
33  
34   /* Assumes mesh pointers have been cleaned up appropriately: just deletes from
35     Point location and triangle data structure
36   */
37 < smDelete_tri(sm,t_id)
37 > smDelete_tri(sm,t_id,t)
38   SM *sm;
39   int t_id;
40 + TRI *t;
41   {
42  
43    /* NOTE: Assumes that a new triangle adjacent to each vertex
# Line 88 | Line 46 | int t_id;
46       to id because the vertices can no longer
47       point to tri id as being the first triangle pointer
48    */
49 <  if(!SM_IS_NTH_T_BASE(sm,t_id))
50 <  {
93 <    SM_SAMPLE_TRIS(sm)--;
94 <    if(SM_IS_NTH_T_NEW(sm,t_id))
95 <      smNew_tri_cnt--;
96 <  }
97 <  smClear_tri_flags(sm,t_id);
49 >  SM_CLR_NTH_T_ACTIVE(sm,t_id);
50 >  smFree_tri(sm,t_id,t);
51  
99  smFree_tri(sm,t_id);
52   }
53  
102
54   int
55   eNew_edge()
56   {
# Line 109 | Line 60 | eNew_edge()
60  
61    if(Ecnt >= Max_edges)
62      {
63 + #ifdef DEBUG
64        if(Max_edges > 10000)
65          error(CONSISTENCY,"Too many edges in vertex loop\n");
66 + #endif
67        Max_edges += 100;
68        if(!(Edges = (EDGE *)realloc(Edges,(Max_edges+1)*sizeof(EDGE))))
69          goto memerr;
70      }
71 + #ifdef DEBUG
72 +  SET_E_NTH_TRI(Ecnt+1,0,INVALID);
73 +  SET_E_NTH_TRI(Ecnt+1,1,INVALID);
74 + #endif
75    return(++Ecnt);
76  
77   memerr:
78 <  error(SYSTEM,"eNew_edge(): Unable to allocate memory");
78 >  error(SYSTEM,"eNew_edge): Unable to allocate memory");
79   }
80  
81   /* Return list of edges defining polygon formed by boundary of triangles
82   adjacent to id. Return set of triangles adjacent to id to delete in delptr
83   */
84   LIST
85 < *smVertexPolygon(sm,id,delptr)
85 > *smVertexStar(sm,id)
86   SM *sm;
87   int id;
131 QUADTREE *delptr;
88   {
89      TRI *tri,*t_next;
90      LIST *elist,*end;
91 <    int e,t_id,v_next,t_next_id,b_id,v_id;
136 <    OBJECT del_set[2];
91 >    int e,t_id,v_next,t_next_id,b_id,v_id,t_last_id;
92  
138    eClear_edges();
93      elist = end =  NULL;
94  
95      /* Get the first triangle adjacent to vertex id */
# Line 150 | Line 104 | QUADTREE *delptr;
104      SET_E_NTH_VERT(e,0,T_NTH_V(tri,b_id));
105      SET_E_NTH_TRI(e,0,INVALID);
106      SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_id));
107 <    v_next = T_NTH_V(tri,(b_id+1)%3);
107 >     v_next = T_NTH_V(tri,(b_id+1)%3);
108      SET_E_NTH_VERT(e,1,v_next);
109 +  
110      elist = add_data_to_circular_list(elist,&end,e);
111      t_next_id = t_id;
112      t_next = tri;
113 <
113 >    t_last_id = -1;
114 >
115      /* Create a set to hold all of the triangles for deletion later */
160    del_set[0] = 1; del_set[1] = t_id;
161    *delptr = qtnewleaf(del_set);
116  
117      while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id)
118      {
119        e = eNew_edge();
120 +      if(t_last_id != -1)
121 +      {
122 +        smDelete_tri(sm,t_last_id,t_next);
123 +      }
124        t_next = SM_NTH_TRI(sm,t_next_id);
125 +      t_last_id = t_next_id;
126        SET_E_NTH_VERT(e,0,v_next);
127        SET_E_NTH_TRI(e,0,INVALID);
128        v_id = T_WHICH_V(t_next,id);
# Line 172 | Line 131 | QUADTREE *delptr;
131        v_next = T_NTH_V(t_next,(b_id+1)%3);
132        SET_E_NTH_VERT(e,1,v_next);
133        elist = add_data_to_circular_list(elist,&end,e);
134 <      qtaddelem(*delptr,t_next_id);
134 >
135      }
136 <    return(elist);
136 >    smDelete_tri(sm,t_last_id,t_next);
137 >    smDelete_tri(sm,t_id,tri);
138 >   return(elist);
139   }
140  
180
141   int
142   smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr)
143   SM *sm;
144   int id0,id1,id2,e0,e1,*e2ptr;
145   {
146 <  int t_id;
147 <  int e2;
146 >  int t_id,e2;
147 >  TRI *t;
148  
149 < #ifdef DEBUG
190 <  if(id0 == INVALID || id1==INVALID || id2==INVALID)
191 <    error(CONSISTENCY,"bad id- smTriangulate_add_tri()\n");
192 < #endif
193 <  t_id = smAdd_tri(sm,id0,id1,id2);
149 >  t_id = smAdd_tri(sm,id0,id1,id2,&t);
150    if(*e2ptr == 0)
151    {
152      e2 = eNew_edge();
# Line 203 | Line 159 | int id0,id1,id2,e0,e1,*e2ptr;
159    SET_E_NTH_TRI(e0,0,t_id);
160    SET_E_NTH_TRI(e1,0,t_id);
161    SET_E_NTH_TRI(e2,0,t_id);
162 <
162 > #ifdef DEBUG
163 > #if DEBUG > 1
164 >  if(E_NTH_TRI(e0,1) == E_NTH_TRI(e0,0) ||
165 >     E_NTH_TRI(e1,1) == E_NTH_TRI(e1,0) ||
166 >     E_NTH_TRI(e2,1) == E_NTH_TRI(e2,0))
167 >    error(CONSISTENCY,"Non manifold\n");
168 > #endif
169 > #endif
170    *e2ptr = e2;
171    return(t_id);
172 +
173   }
174  
175 < int
176 < smTriangulateConvex(sm,plist,add_ptr)
177 < SM *sm;
178 < LIST *plist,**add_ptr;
175 > int
176 > smTriangulate_quad(sm,l)
177 >     SM *sm;
178 >     LIST *l;
179   {
180 <    int t_id,e_id0,e_id1,e_id2;
181 <    int v_id0,v_id1,v_id2;
182 <    LIST *lptr;
180 >  int e1,e2,e3,e4,e,t_id,id0,id1,id2,id3;
181 >  FVECT v0,v1,v2,v3,n;
182 >  double dp;
183 >  TRI *tri;
184 >  LIST *lptr;
185  
186 <    lptr = plist;
187 <    e_id0 = (int)LIST_DATA(lptr);
188 <    v_id0 = E_NTH_VERT(e_id0,0);
189 <    lptr = LIST_NEXT(lptr);
190 <    while(LIST_NEXT(lptr) != plist)
191 <    {
192 <        e_id1 = (int)LIST_DATA(lptr);
193 <        v_id1 = E_NTH_VERT(e_id1,0);
194 <        v_id2 = E_NTH_VERT(e_id1,1);
195 <        lptr = LIST_NEXT(lptr);
186 > #ifdef DEBUG
187 >  if(LIST_NEXT(LIST_NEXT(LIST_NEXT(LIST_NEXT(l)))) != l)
188 >  {
189 >    eputs("smTriangulate_quad(): not a quadrilateral\n");
190 >    return(FALSE);
191 >  }
192 >    eputs("smTriangulate_quad():\n");
193 > #endif
194 >  lptr=l;
195 >  e1 = (int)LIST_DATA(l);
196 >  id0 = E_NTH_VERT(e1,0);
197 >  id1 = E_NTH_VERT(e1,1);
198 >  VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm));
199 >  VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm));  
200 >  /* Get v2 */
201 >  l = LIST_NEXT(l);
202 >  e2 = (int)LIST_DATA(l);
203 >  id2 = E_NTH_VERT(e2,1);
204 >  VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
205 >  /* Get v3 */
206 >  l = LIST_NEXT(l);
207 >  e3 = (int)LIST_DATA(l);
208 >  id3 = E_NTH_VERT(e3,1);
209 >  VSUB(v3,SM_NTH_WV(sm,id3),SM_VIEW_CENTER(sm));
210 >  l = LIST_NEXT(l);
211 >  e4 = (int)LIST_DATA(l);
212 >  free_list(lptr);
213  
214 <        if(LIST_NEXT(lptr) != plist)    
215 <          e_id2 = 0;
216 <        else
217 <           e_id2 = (int)LIST_DATA(lptr);
218 <        t_id = smTriangulate_add_tri(sm,v_id0,v_id1,v_id2,e_id0,e_id1,&e_id2);
219 <        *add_ptr = push_data(*add_ptr,t_id);
220 <        e_id0 = -e_id2;
214 >  VCROSS(n,v0,v2);
215 >  normalize(n);
216 >  normalize(v1);
217 >  dp = DOT(n,v1);
218 >  e = 0;
219 >  if(dp > 0)
220 >  {
221 >    if(dp  >= EV_EPS)
222 >    {
223 >      normalize(v3);
224 >      if(DOT(n,v3) < 0)
225 >      {
226 >        t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&e);
227 >        e *= -1;
228 >        t_id = smTriangulate_add_tri(sm,id2,id3,id0,e3,e4,&e);
229 >        return(TRUE);
230 >      }
231      }
232 <    free_list(plist);
233 <    return(TRUE);
234 < }
235 < #ifdef TEST_DRIVER
236 < FVECT Norm[500],B_V[500];
237 < int Ncnt,Bcnt,Del=0;
232 >
233 >  }
234 > #ifdef DEBUG
235 > #if DEBUG > 1
236 >  VCROSS(n,v1,v3);
237 >  normalize(n);
238 >  normalize(v0);
239 >  normalize(v2);
240 >  dp = DOT(n,v2);
241 >  if((dp < 0) || (dp < EV_EPS) || (DOT(n,v0) >= 0.0))  
242 >    error(CONSISTENCY,"smTriangulate_quad: cannot triangulate\n");
243   #endif
244 + #endif
245 +  t_id = smTriangulate_add_tri(sm,id1,id2,id3,e2,e3,&e);
246 +  e *= -1;
247 +  t_id = smTriangulate_add_tri(sm,id3,id0,id1,e4,e1,&e);
248 +  return(TRUE);
249 + }
250  
247
251   /* Triangulate the polygon defined by plist, and generating vertex p_id.
252     Return list of added triangles in list add_ptr. Returns TRUE if
253     successful, FALSE otherwise. This is NOT a general triangulation routine,
# Line 252 | Line 255 | int Ncnt,Bcnt,Del=0;
255   */
256  
257   int
258 < smTriangulate(sm,id,plist,add_ptr)
258 > smTriangulate(sm,id,plist)
259   SM *sm;
260   int id;
261 < LIST *plist,**add_ptr;
261 > LIST *plist;
262   {
263      LIST *l,*prev,*t;
264      FVECT v0,v1,v2,n,p;
265 <    int is_tri,is_convex,cut,t_id,id0,id1,id2,e2,e1,enew;
266 <    double dp;
265 >    int is_tri,cut,t_id,id0,id1,id2,e2,e1,enew;
266 >    double dp1,dp2;
267  
268      VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
269 <    enew = 0;
270 <    is_convex = TRUE;
268 <    cut = is_tri= FALSE;
269 <    l = prev = plist;
269 >    normalize(p);
270 >    l = plist;
271  
272 +    enew = 0;
273 +    cut = is_tri=  FALSE;
274 +    prev = l;
275      /* get v0,v1 */
276      e1 = (int)LIST_DATA(l);
277      id0 = E_NTH_VERT(e1,0);
278      id1 = E_NTH_VERT(e1,1);
279      VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm));
280 +    normalize(v0);
281      VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm));  
282 < #ifdef TEST_DRIVER
278 <    Del = TRUE;
279 <    VCOPY(B_V[0],v0);
280 <    VCOPY(B_V[1],v1);
281 <    Bcnt = 2;
282 <    Ncnt = 0;
283 < #endif
282 >    normalize(v1);
283      while(l)
284      {
285        l = LIST_NEXT(l);
# Line 288 | Line 287 | LIST *plist,**add_ptr;
287        e2 = (int)LIST_DATA(l);
288        id2 = E_NTH_VERT(e2,1);
289        VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
290 < #ifdef TEST_DRIVER
292 <      VCOPY(B_V[Bcnt++],v2);
293 < #endif
290 >      normalize(v2);
291        if(LIST_NEXT(LIST_NEXT(l)) == prev)
292        {/* Check if have a triangle */
293             is_tri = TRUE;      
294             break;
295        }
299
296        /* determine if v0-v1-v2 is convex:defined clockwise on the sphere-
297         so switch orientation
298         */
299 <      if(convex_angle(v2,v1,v0))
299 >      VCROSS(n,v0,v2);
300 >      normalize(n);
301 >      dp1 = DOT(n,p);      
302 >      if(dp1  <= 0.0)
303        {
304            /* test if safe to cut off v0-v1-v2 by testing if p lies outside of
305           triangle v0-v1-v2: if so, because plist is the star polygon around p,
306            the new edge v2-v0 cannot intersect any existing edges
307          */
308 <        VCROSS(n,v0,v2);
309 <        dp = DOT(n,p);
310 <        if(dp  <= 0.0)
311 <        {
308 >        dp1 = DOT(n,v1);
309 >        /* Distance from point s to plane is d = |N.p0s|/||N|| */
310 >        /* sp1 = s-p0 for point on plane p0, a.(b+c) = a.b + a.c */
311 >        if(dp1 >= EV_EPS)
312 >        {
313              /* remove edges e1,e2 and add triangle id0,id1,id2 */
314 <          enew = 0;
315 <          t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
316 <          cut = TRUE;
317 <          *add_ptr = push_data(*add_ptr,t_id);
318 <           /* Insert edge enew into the list, reuse prev list element */
319 <          LIST_NEXT(prev) = LIST_NEXT(l);
320 <          LIST_DATA(prev) = e1 = -enew;
321 <           /* If removing head of list- reset plist pointer */
322 <          if(l== plist)
323 <            plist = prev;
324 <          /* free list element for e2 */
325 <          LIST_NEXT(l)=NULL;
326 <          free_list(l);
327 <          l = prev;
328 <          VCOPY(v1,v2);
329 <          id1 = id2;
330 <          continue;
314 >            enew = 0;
315 >            t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
316 >            cut = TRUE;
317 >            /* Insert edge enew into the list, reuse prev list element */
318 >            LIST_NEXT(prev) = LIST_NEXT(l);
319 >            LIST_DATA(prev) = e1 = -enew;
320 >            /* If removing head of list- reset plist pointer */
321 >            if(l== plist)
322 >              plist = prev;
323 >            /* free list element for e2 */
324 >            LIST_NEXT(l)=NULL;
325 >            free_list(l);
326 >            l = prev;
327 >            VCOPY(v1,v2);
328 >            id1 = id2;
329 >            continue;
330          }
331        }
333      else
334        is_convex = FALSE;
332        VCOPY(v0,v1);
333        VCOPY(v1,v2);
334        id0 = id1;
# Line 346 | Line 343 | LIST *plist,**add_ptr;
343              is_tri = TRUE;      
344              break;
345            }
349
350        if(is_convex)
351          break;
346          if(!cut)
347 <        {
354 < #ifdef DEBUG
355 <          eputs("smTriangulate():Unable to triangulate\n");
356 < #endif
357 <          free_list(l);
358 <          while(*add_ptr)
359 <          {
360 <            t_id = pop_list(add_ptr);
361 <            smDelete_tri(sm,t_id);
362 <          }
363 <          return(FALSE);
364 <        }
347 >          break;
348          cut = FALSE;
366        is_convex = TRUE;
349        }
350        prev = l;
351      }
# Line 372 | Line 354 | LIST *plist,**add_ptr;
354        l = LIST_NEXT(l);
355        enew = (int)LIST_DATA(l);
356        t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
375      *add_ptr = push_data(*add_ptr,t_id);
357        free_list(l);
358      }
359      else
360 <      if(!smTriangulateConvex(sm,l,add_ptr))
361 <        return(FALSE);
360 >      if(!smTriangulate_quad(sm,l))
361 >        goto Terror;
362 > #if 0
363 > {int i;
364 >    eputs("\n\n");
365 >    for(i=1;i<=Ecnt;i++)
366 >      fprintf(stderr,"%d verts %d %d tris  %d %d\n",
367 >              i,Edges[i].verts[0],Edges[i].verts[1],
368 >              Edges[i].tris[0],Edges[i].tris[1]);
369 > }
370 > #endif
371  
372      /* Set triangle adjacencies based on edge adjacencies */
373      FOR_ALL_EDGES(enew)
# Line 391 | Line 381 | LIST *plist,**add_ptr;
381        e2 = (T_WHICH_V(SM_NTH_TRI(sm,id1),E_NTH_VERT(enew,1))+2)%3;
382        T_NTH_NBR(SM_NTH_TRI(sm,id1),e2) = id0;
383      }
384 + #if 0
385 + {int i;
386 +    eputs("\n\n");
387 +    for(i=1;i<=Ecnt;i++)
388 +      fprintf(stderr,"%d verts %d %d tris  %d %d\n",
389 +              i,Edges[i].verts[0],Edges[i].verts[1],
390 +              Edges[i].tris[0],Edges[i].tris[1]);
391 + }
392 + #endif
393 +
394 + #ifdef DEBUG
395 + #if DEBUG > 1
396 +    {
397 +      TRI *t0,*t1,*n;
398 +
399 +    FOR_ALL_EDGES(enew)
400 +    {
401 +      id0 = E_NTH_TRI(enew,0);
402 +      id1 = E_NTH_TRI(enew,1);
403 +      t0 = SM_NTH_TRI(sm,id0);
404 +      t1 = SM_NTH_TRI(sm,id1);
405 +      if(T_NTH_NBR(t0,0) == T_NTH_NBR(t0,1)  ||
406 +       T_NTH_NBR(t0,1) == T_NTH_NBR(t0,2)  ||
407 +       T_NTH_NBR(t0,0) == T_NTH_NBR(t0,2))
408 +      error(CONSISTENCY,"Invalid topology\n");
409 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,0))) ||
410 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,1))) ||
411 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,2))))
412 +      error(CONSISTENCY,"Invalid topology\n");
413 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t0,0));
414 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
415 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
416 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
417 +      error(CONSISTENCY,"Invalid topology\n");
418 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
419 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
420 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
421 +      error(CONSISTENCY,"Invalid topology\n");
422 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t0,1));
423 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
424 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
425 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
426 +      error(CONSISTENCY,"Invalid topology\n");
427 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
428 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
429 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
430 +      error(CONSISTENCY,"Invalid topology\n");
431 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t0,2));
432 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
433 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
434 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
435 +      error(CONSISTENCY,"Invalid topology\n");
436 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
437 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
438 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
439 +      error(CONSISTENCY,"Invalid topology\n");
440 +
441 +      if(T_NTH_NBR(t1,0) == T_NTH_NBR(t1,1)  ||
442 +       T_NTH_NBR(t1,1) == T_NTH_NBR(t1,2)  ||
443 +       T_NTH_NBR(t1,0) == T_NTH_NBR(t1,2))
444 +      error(CONSISTENCY,"Invalid topology\n");
445 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,0))) ||
446 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,1))) ||
447 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,2))))
448 +      error(CONSISTENCY,"Invalid topology\n");
449 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t1,0));
450 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
451 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
452 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
453 +      error(CONSISTENCY,"Invalid topology\n");
454 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
455 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
456 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
457 +      error(CONSISTENCY,"Invalid topology\n");
458 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t1,1));
459 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
460 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
461 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
462 +      error(CONSISTENCY,"Invalid topology\n");
463 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
464 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
465 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
466 +      error(CONSISTENCY,"Invalid topology\n");
467 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t1,2));
468 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
469 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
470 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
471 +      error(CONSISTENCY,"Invalid topology\n");
472 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
473 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
474 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
475 +      error(CONSISTENCY,"Invalid topology\n");
476 +    }
477 +    }
478 + #endif
479 + #endif
480      return(TRUE);
481 +
482 + Terror:  
483 + #ifdef DEBUG
484 +          error(CONSISTENCY,"smTriangulate():Unable to triangulate\n");
485 + #endif
486   }
487  
488   eIn_tri(e,t)
# Line 410 | Line 501 | TRI *t;
501    return(FALSE);
502   }
503  
504 +
505 + void
506 + smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
507 +   SM *sm;
508 +   int t_id,t1_id;
509 +   int e,e1;
510 +   int *tn_id,*tn1_id;
511 + {
512 +    int verts[3],enext,eprev,e1next,e1prev;
513 +    TRI *n,*ta,*tb,*t,*t1;
514 +    FVECT p1,p2,p3;
515 +    int ta_id,tb_id;
516 +    /* form new diagonal (e relative to t, and e1 relative to t1)
517 +      defined by quadrilateral formed by t,t1- swap for the opposite diagonal
518 +   */
519 +    t = SM_NTH_TRI(sm,t_id);
520 +    t1 = SM_NTH_TRI(sm,t1_id);
521 +    enext = (e+1)%3;
522 +    eprev = (e+2)%3;
523 +    e1next = (e1+1)%3;
524 +    e1prev = (e1+2)%3;
525 +    verts[e] = T_NTH_V(t,e);
526 +    verts[enext] = T_NTH_V(t,enext);
527 +    verts[eprev] = T_NTH_V(t1,e1);
528 +    ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&ta);
529 + #if 0
530 +  fprintf(stderr,"Added tri %d %d %d %d\n",ta_id,T_NTH_V(ta,0),
531 +          T_NTH_V(ta,1), T_NTH_V(ta,2));
532 + #endif
533 +    verts[e1] = T_NTH_V(t1,e1);
534 +    verts[e1next] = T_NTH_V(t1,e1next);
535 +    verts[e1prev] = T_NTH_V(t,e);
536 +    tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&tb);
537 + #if 0
538 +  fprintf(stderr,"Added tri %d %d %d %d\n",tb_id,T_NTH_V(tb,0),
539 +          T_NTH_V(tb,1), T_NTH_V(tb,2));
540 + #endif
541 +    /* set the neighbors */
542 +    T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next);
543 +    T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext);
544 +    T_NTH_NBR(ta,enext)= tb_id;
545 +    T_NTH_NBR(tb,e1next)= ta_id;
546 +    T_NTH_NBR(ta,eprev)=T_NTH_NBR(t,eprev);
547 +    T_NTH_NBR(tb,e1prev)=T_NTH_NBR(t1,e1prev);    
548 +
549 +    /* Reset neighbor pointers of original neighbors */
550 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext));
551 +    T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = tb_id;
552 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t,eprev));
553 +    T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = ta_id;
554 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1next));
555 +    T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = ta_id;
556 +    n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1prev));
557 +    T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id;
558 +
559 +    smDelete_tri(sm,t_id,t);
560 +    smDelete_tri(sm,t1_id,t1);
561 +
562 + #ifdef DEBUG
563 + #if DEBUG > 1
564 +    if(T_NTH_NBR(ta,0) == T_NTH_NBR(ta,1)  ||
565 +       T_NTH_NBR(ta,1) == T_NTH_NBR(ta,2)  ||
566 +       T_NTH_NBR(ta,0) == T_NTH_NBR(ta,2))
567 +      error(CONSISTENCY,"Invalid topology\n");
568 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))) ||
569 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,1))) ||
570 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,2))))
571 +      error(CONSISTENCY,"Invalid topology\n");
572 +    n = SM_NTH_TRI(sm,T_NTH_NBR(ta,0));
573 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
574 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
575 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
576 +      error(CONSISTENCY,"Invalid topology\n");
577 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
578 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
579 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
580 +      error(CONSISTENCY,"Invalid topology\n");
581 +    n = SM_NTH_TRI(sm,T_NTH_NBR(ta,1));
582 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
583 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
584 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
585 +      error(CONSISTENCY,"Invalid topology\n");
586 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
587 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
588 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
589 +      error(CONSISTENCY,"Invalid topology\n");
590 +    n = SM_NTH_TRI(sm,T_NTH_NBR(ta,2));
591 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
592 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
593 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
594 +      error(CONSISTENCY,"Invalid topology\n");
595 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
596 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
597 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
598 +      error(CONSISTENCY,"Invalid topology\n");
599 +    if(T_NTH_NBR(ta,0) == T_NTH_NBR(ta,1)  ||
600 +       T_NTH_NBR(ta,1) == T_NTH_NBR(ta,2)  ||
601 +       T_NTH_NBR(ta,0) == T_NTH_NBR(ta,2))
602 +      error(CONSISTENCY,"Invalid topology\n");
603 +
604 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,0))) ||
605 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,1))) ||
606 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,2))))
607 +      error(CONSISTENCY,"Invalid topology\n");
608 +    n = SM_NTH_TRI(sm,T_NTH_NBR(tb,0));
609 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
610 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
611 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
612 +      error(CONSISTENCY,"Invalid topology\n");
613 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
614 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
615 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
616 +      error(CONSISTENCY,"Invalid topology\n");
617 +    n = SM_NTH_TRI(sm,T_NTH_NBR(tb,1));
618 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
619 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
620 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
621 +      error(CONSISTENCY,"Invalid topology\n");
622 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
623 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
624 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
625 +      error(CONSISTENCY,"Invalid topology\n");
626 +    n = SM_NTH_TRI(sm,T_NTH_NBR(tb,2));
627 +    if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1)  ||
628 +       T_NTH_NBR(n,1) == T_NTH_NBR(n,2)  ||
629 +       T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
630 +      error(CONSISTENCY,"Invalid topology\n");
631 +    if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
632 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
633 +       !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
634 +      error(CONSISTENCY,"Invalid topology\n");
635 + #endif
636 + #endif
637 +    *tn_id = ta_id;
638 +    *tn1_id = tb_id;
639 +    
640 +    return;
641 + }
642 +
643   /* Test the new set of triangles for Delaunay condition. 'Edges' contains
644     all of the new edges added. The CCW triangle assoc with each edge is
645     tested against the opposite vertex of the CW triangle. If the vertex
646     lies inside the circle defined by the CCW triangle- the edge is swapped
647     for the opposite diagonal
648   */
649 < smFixEdges(sm,add_list,delptr)
649 > smFixEdges(sm)
650     SM *sm;
421   LIST *add_list;
422   QUADTREE *delptr;
423
651   {
652      int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next;
653      int i,v0_id,v1_id,v2_id,p_id,t0_nid,t1_nid;
# Line 431 | Line 658 | smFixEdges(sm,add_list,delptr)
658      {
659          t0_id = E_NTH_TRI(e,0);
660          t1_id = E_NTH_TRI(e,1);
434        if((t0_id==INVALID) || (t1_id==INVALID))
435        {
661   #ifdef DEBUG
662 <            error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n");
662 >        if((t0_id==INVALID) || (t1_id==INVALID))
663 >          error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n");
664   #endif
439        }
665          t0 = SM_NTH_TRI(sm,t0_id);
666          t1 = SM_NTH_TRI(sm,t1_id);
667          e0 = T_NTH_NBR_PTR(t1_id,t0);
# Line 447 | Line 672 | smFixEdges(sm,add_list,delptr)
672          v2_id = T_NTH_V(t0,e0);
673          p_id = T_NTH_V(t1,e1);
674  
675 <        smDir_in_cone(sm,v0,v0_id);
676 <        smDir_in_cone(sm,v1,v1_id);
677 <        smDir_in_cone(sm,v2,v2_id);
675 >        smDir(sm,v0,v0_id);
676 >        smDir(sm,v1,v1_id);
677 >        smDir(sm,v2,v2_id);
678          
679 <        VCOPY(p,SM_NTH_WV(sm,p_id));    
680 <        VSUB(p,p,SM_VIEW_CENTER(sm));
681 <        if(point_in_cone(p,v0,v1,v2))
679 >        VSUB(p,SM_NTH_WV(sm,p_id),SM_VIEW_CENTER(sm));
680 >        normalize(p);
681 >        if(pt_in_cone(p,v2,v1,v0))
682          {
683 <           smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list,
459 <                            delptr);
460 <            
683 >           smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid);
684             /* Adjust the triangle pointers of the remaining edges to be
685                processed
686              */
# Line 478 | Line 701 | smFixEdges(sm,add_list,delptr)
701                  else
702                    SET_E_NTH_TRI(i,1,t1_nid);
703                }
704 + #ifdef DEBUG
705 +              if(E_NTH_TRI(i,1) == E_NTH_TRI(i,0) )
706 +                error(CONSISTENCY,"invalid edge\n");
707 + #endif
708              }
709              t0_id = t0_nid;
710              t1_id = t1_nid;
# Line 486 | Line 713 | smFixEdges(sm,add_list,delptr)
713              SET_E_NTH_VERT(e_new,1,v2_id);
714              SET_E_NTH_TRI(e_new,0,t0_id);
715              SET_E_NTH_TRI(e_new,1,t1_id);
716 + #ifdef DEBUG
717 +              if(E_NTH_TRI(i,1) == E_NTH_TRI(i,0) )
718 +                error(CONSISTENCY,"invalid edge\n");
719 + #endif
720          }
721      }
491    /* Add/Delete the appropriate triangles from the stree */
492    smUpdate_locator(sm,add_list,qtqueryset(*delptr));
493
722   }
723  
724 +
725 + smDelete_samp(sm,s_id)
726 + SM *sm;
727 + int s_id;
728 + {
729 +  QUADTREE qt;
730 +  OBJECT *os;
731 +
732 +  /* Mark as free */
733 +  smUnalloc_samp(sm,s_id);
734 +
735 + #ifdef DEBUG  
736 +  SM_NTH_VERT(sm,s_id) = INVALID;
737 +  /* fprintf(stderr,"deleting sample %d\n",s_id); */
738 + #endif
739 +  /* remove from its set */
740 +  qt = SM_S_NTH_QT(sm,s_id);
741 +  os = qtqueryset(qt);
742 +  deletuelem(os, s_id); /* delete obj from unsorted os, no questions */
743 + }
744   /* Remove vertex "id" from the mesh- and retriangulate the resulting
745     hole: Returns TRUE if successful, FALSE otherwise.
746   */
# Line 501 | Line 749 | smRemoveVertex(sm,id)
749     SM *sm;
750     int id;
751   {
752 <    LIST *b_list,*add_list;
505 <    QUADTREE delnode=-1;
506 <    int t_id;
507 <
752 >    LIST *b_list;
753      /* generate list of edges that form the boundary of the
754 <       polygon formed by the triangles adjacent to vertex 'id'
755 <     */
756 <    b_list = smVertexPolygon(sm,id,&delnode);
754 >       polygon formed by the triangles adjacent to vertex 'id'*/
755 >    b_list = smVertexStar(sm,id);
756 > #if 0
757 > {int i;
758 >    eputs("\n\n");
759 >    for(i=1;i<=Ecnt;i++)
760 >      fprintf(stderr,"%d verts %d %d tris  %d %d\n",
761 >              i,Edges[i].verts[0],Edges[i].verts[1],
762 >              Edges[i].tris[0],Edges[i].tris[1]);
763 > }
764 > #endif
765  
513    add_list = NULL;
766      /* Triangulate polygonal hole  */
767 <    if(!smTriangulate(sm,id,b_list,&add_list))
768 <    {
769 <      qtfreeleaf(delnode);
518 <      return(FALSE);
519 <    }
520 <    /* Fix up new triangles to be Delaunay-delnode contains set of
521 <     triangles to delete,add_list is the set of new triangles to add
522 <     */
523 <    smFixEdges(sm,add_list,&delnode);
767 >    smTriangulate(sm,id,b_list);
768 >    
769 >    /* Fix up new triangles to be Delaunay*/
770  
771 <
772 <    qtfreeleaf(delnode);
771 >    smFixEdges(sm);
772 >    smDelete_samp(sm,id);
773 >    eClear_edges();
774      return(TRUE);
775   }
776    
777  
778  
779 <
779 >
780  
781  
782  

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines