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.6 by gwlarson, Tue Oct 6 18:16:53 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 < *smVertex_star_polygon(sm,id,delptr)
85 > *smVertexStar(sm,id)
86   SM *sm;
87   int id;
128 – QUADTREE *delptr;
88   {
89      TRI *tri,*t_next;
90      LIST *elist,*end;
91 <    int t_id,v_next,t_next_id;
133 <    int e;
134 <    OBJECT del_set[2];
91 >    int e,t_id,v_next,t_next_id,b_id,v_id,t_last_id;
92  
93      elist = end =  NULL;
94 +
95      /* Get the first triangle adjacent to vertex id */
96      t_id = SM_NTH_VERT(sm,id);
97      tri = SM_NTH_TRI(sm,t_id);
98  
99 <    if((e = eNew_edge()) == INVALID)
100 <      return(NULL);
101 <
102 <    v_next = (T_WHICH_V(tri,id)+1)%3;
103 <    SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next));
99 >    e = eNew_edge();
100 >    /* Get the  next vertex on the polygon boundary */
101 >    v_id = T_WHICH_V(tri,id);
102 >    b_id = (v_id + 1)%3;
103 >    /* Create an edge */
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_next));
107 <    v_next = (T_WHICH_V(tri,id)+2)%3;
108 <    SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next));
106 >    SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_id));
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);
151 –
111      t_next_id = t_id;
112      t_next = tri;
113 +    t_last_id = -1;
114 +
115 +    /* Create a set to hold all of the triangles for deletion later */
116  
117 <    del_set[0] =1; del_set[1] = t_id;
118 <    *delptr = qtnewleaf(del_set);
119 <
120 <    while((t_next_id = T_NTH_NBR(t_next,v_next)) != t_id)
121 <    {  
122 <      if((e = eNew_edge()) == INVALID)
123 <        return(NULL);
162 <
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 <      v_next = (T_WHICH_V(t_next,id)+1)%3;
126 <
166 <      SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next));
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 <      SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next));
129 <      v_next = (T_WHICH_V(t_next,id)+2)%3;
130 <      SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next));
128 >      v_id = T_WHICH_V(t_next,id);
129 >      b_id = (v_id + 1)%3;
130 >      SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_id));
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  
173 –
174 –      if(qtinset(*delptr,t_next_id))
175 –        {
176 – #ifdef DEBUG
177 –          eputs("smVertex_star_polygon(): id already in set\n");
178 – #endif    
179 –          free_list(elist);
180 –          return(NULL);
181 –        }
182 –      else
183 –        qtaddelem(*delptr,t_next_id);
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  
141   int
189 – smEdge_intersect_polygon(sm,v0,v1,l)
190 – SM *sm;
191 – FVECT v0,v1;
192 – LIST *l;
193 – {
194 –    FVECT e0,e1;
195 –    int e,id_e0,id_e1;
196 –    LIST *el,*eptr;
197 –    
198 –    /* Test the edges in l against v0v1 to see if v0v1 intersects
199 –       any other edges
200 –     */
201 –    
202 –    el = l;
203 –
204 –    while(el)
205 –    {
206 –      e = (int)LIST_DATA(el);
207 –      id_e0 = E_NTH_VERT(e,0);
208 –      id_e1 = E_NTH_VERT(e,1);
209 –
210 –      VSUB(e0,SM_NTH_WV(sm,id_e0),SM_VIEW_CENTER(sm));
211 –      VSUB(e1,SM_NTH_WV(sm,id_e1),SM_VIEW_CENTER(sm));
212 –      if(sedge_intersect(v0,v1,e0,e1))
213 –        return(TRUE);
214 –
215 –      el = LIST_NEXT(el);
216 –      if(el == l)
217 –        break;
218 –    }
219 –    return(FALSE);
220 – }
221 –
222 – int
223 – smFind_next_convex_vertex(sm,id0,id1,v0,v1,l)
224 –   SM *sm;
225 –   int id0,id1;
226 –   FVECT v0,v1;
227 –   LIST *l;
228 – {
229 –    int e,id;
230 –    LIST *el;
231 –    FVECT v;
232 –
233 –    /* starting with the end of edge at head of l, search sequentially for
234 –      vertex v such that v0v1v is a convex angle, and the edge v1v does
235 –      not intersect any other edges
236 –   */
237 –    id = INVALID;
238 –    el = l;
239 –    while(id != id0)
240 –    {
241 –        e = (int)LIST_DATA(el);
242 –        id = E_NTH_VERT(e,1);
243 –
244 –        smDir(sm,v,id);
245 –
246 –        if(convex_angle(v0,v1,v) && !smEdge_intersect_polygon(sm,v1,v,l))
247 –           return(id);
248 –              
249 –        el = LIST_NEXT(el);
250 –        if(el == l)
251 –           break;
252 –    }
253 –    return(INVALID);
254 – }
255 –
256 – int
257 – split_edge_list(id0,id_new,l,lnew)
258 – int id0,id_new;
259 – LIST **l,**lnew;
260 – {
261 –    LIST *list,*lptr,*end;
262 –    int e,e1,e2,new_e;
263 –
264 –    e2 = INVALID;
265 –    list = lptr = *l;
266 –
267 –    if((new_e = eNew_edge())==INVALID)
268 –     {
269 – #ifdef DEBUG
270 –            eputs("split_edge_list():Too many edges\n");
271 – #endif
272 –         return(FALSE);
273 –     }
274 –    SET_E_NTH_VERT(new_e,0,id0);
275 –    SET_E_NTH_VERT(new_e,1,id_new);
276 –    SET_E_NTH_TRI(new_e,0,INVALID);
277 –    SET_E_NTH_TRI(new_e,1,INVALID);
278 –    
279 –    while(e2 != id_new)
280 –    {
281 –        lptr = LIST_NEXT(lptr);
282 –        e = (int)LIST_DATA(lptr);
283 –        e2 = E_NTH_VERT(e,1);
284 –        if(lptr == list)
285 –        {
286 – #ifdef DEBUG        
287 –          eputs("split_edge_list():cant find vertex\n");
288 – #endif
289 –          *lnew = NULL;
290 –          return(FALSE);
291 –        }
292 –
293 –    }
294 –    end = lptr;
295 –    lptr =  LIST_NEXT(lptr);
296 –    list = add_data_to_circular_list(list,&end,-new_e);
297 –    *lnew = list;
298 –
299 –    /* now follow other cycle */
300 –
301 –    list = lptr;
302 –    e2 = INVALID;
303 –    while(e2 != id0)
304 –    {
305 –        lptr = LIST_NEXT(lptr);
306 –        e = (int)LIST_DATA(lptr);
307 –        e2 = E_NTH_VERT(e,1);
308 –        if(lptr == list)
309 –        {
310 – #ifdef DEBUG        
311 –          eputs("split_edge_list():cant find intial vertex\n");
312 – #endif
313 –          *l = NULL;
314 –          return(FALSE);
315 –        }
316 –
317 –    }
318 –    end = lptr;
319 –    list = add_data_to_circular_list(list,&end,new_e);
320 –    *l = list;
321 –    return(TRUE);
322 – }
323 –
324 –
325 – int
326 – smTriangulate_convex(sm,plist,add_ptr)
327 – SM *sm;
328 – LIST *plist,**add_ptr;
329 – {
330 –    int t_id,e_id0,e_id1,e_id2;
331 –    int v_id0,v_id1,v_id2;
332 –    LIST *lptr;
333 –    int cnt;
334 –
335 –    lptr = plist;
336 –    e_id0 = (int)LIST_DATA(lptr);
337 –    v_id0 = E_NTH_VERT(e_id0,0);
338 –    lptr = LIST_NEXT(lptr);
339 –    while(LIST_NEXT(lptr) != plist)
340 –    {
341 –        e_id1 = (int)LIST_DATA(lptr);
342 –        v_id1 = E_NTH_VERT(e_id1,0);
343 –        v_id2 = E_NTH_VERT(e_id1,1);
344 –        /* form a triangle for each triple of with v0 as base of star */
345 –        t_id = smAdd_tri(sm,v_id0,v_id1,v_id2);
346 –        *add_ptr = push_data(*add_ptr,t_id);
347 –
348 –        /* add which pointer?*/
349 –
350 –        lptr = LIST_NEXT(lptr);
351 –
352 –        if(LIST_NEXT(lptr) != plist)
353 –        {
354 –            e_id2 = eNew_edge();
355 –            SET_E_NTH_VERT(e_id2,0,v_id2);
356 –            SET_E_NTH_VERT(e_id2,1,v_id0);
357 –        }
358 –        else
359 –           e_id2 = (int)LIST_DATA(lptr);
360 –        
361 –        /* set appropriate tri for each edge*/
362 –        SET_E_NTH_TRI(e_id0,0,t_id);
363 –        SET_E_NTH_TRI(e_id1,0,t_id);
364 –        SET_E_NTH_TRI(e_id2,0,t_id);
365 –
366 –        e_id0 = -e_id2;
367 –    }
368 –    free_list(plist);
369 –    return(TRUE);
370 – }
371 – int
372 – smTriangulate_elist(sm,plist,add_ptr)
373 – SM *sm;
374 – LIST *plist,**add_ptr;
375 – {
376 –    LIST *l,*el1;
377 –    FVECT v0,v1,v2;
378 –    int id0,id1,id2,e,id_next;
379 –    char flipped;
380 –    int done;
381 –
382 –    l = plist;
383 –    
384 –    while(l)
385 –    {
386 –        /* get v0,v1,v2 */
387 –      e = (int)LIST_DATA(l);
388 –      id0 = E_NTH_VERT(e,0);
389 –      id1 = E_NTH_VERT(e,1);
390 –      l = LIST_NEXT(l);
391 –      e = (int)LIST_DATA(l);
392 –      id2 = E_NTH_VERT(e,1);
393 –
394 –      smDir(sm,v0,id0);
395 –      smDir(sm,v1,id1);
396 –      smDir(sm,v2,id2);
397 –      /* determine if convex (left turn), or concave(right turn) angle */
398 –      if(convex_angle(v0,v1,v2))
399 –      {
400 –        if(l == plist)
401 –          break;
402 –        else
403 –          continue;
404 –      }
405 –      /* if concave: add edge and recurse on two sub polygons */
406 –      id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l));
407 –      if(id_next == INVALID)
408 –      {
409 – #ifdef DEBUG
410 –          eputs("smTriangulate_elist():Unable to find convex vertex\n");
411 – #endif
412 –          return(FALSE);
413 –      }
414 –      /* add edge */
415 –      el1 = NULL;
416 –      /* Split edge list l into two lists: one from id1-id_next-id1,
417 –         and the next from id2-id_next-id2
418 –      */
419 –      split_edge_list(id1,id_next,&l,&el1);
420 –      /* Recurse and triangulate the two edge lists */
421 –      done = smTriangulate_elist(sm,l,add_ptr);
422 –      if(done)
423 –        done = smTriangulate_elist(sm,el1,add_ptr);
424 –      return(done);
425 –    }
426 –    done = smTriangulate_convex(sm,plist,add_ptr);
427 –    return(done);
428 – }
429 –
430 – 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 <  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 448 | 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 + smTriangulate_quad(sm,l)
177 +     SM *sm;
178 +     LIST *l;
179 + {
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 + #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 +  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 +
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 +
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,
254 +   assumes polygon star relative to id
255 + */
256 +
257   int
258 < smTriangulate_elist_new(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,loop,t_id,id0,id1,id2,e2,eprev,enext;
266 <    double dp;
265 >    int is_tri,cut,t_id,id0,id1,id2,e2,e1,enew;
266 >    double dp1,dp2;
267  
268 <    smDir(sm,p,id);
269 <    enext=0;
270 <    is_tri= loop = FALSE;
271 <    l = prev = plist;
272 <    /* get v0,v1,v2 */
273 <    eprev = (int)LIST_DATA(l);
274 <    id0 = E_NTH_VERT(eprev,0);
275 <    id1 = E_NTH_VERT(eprev,1);
276 <    smDir(sm,v0,id0);
277 <    smDir(sm,v1,id1);  
268 >    VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
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 >    normalize(v1);
283      while(l)
284      {
285        l = LIST_NEXT(l);
286 +      /* Get v2 */
287        e2 = (int)LIST_DATA(l);
288        id2 = E_NTH_VERT(e2,1);
289 <      /* Check if have a triangle */
289 >      VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
290 >      normalize(v2);
291        if(LIST_NEXT(LIST_NEXT(l)) == prev)
292 <      {
293 <        is_tri = TRUE;
294 <        break;
292 >      {/* Check if have a triangle */
293 >           is_tri = TRUE;      
294 >           break;
295        }
296 <      if(LIST_NEXT(l) == plist)
297 <      {
298 <        if(!loop)
490 <          loop = 1;
491 <        else
492 <          loop++;
493 <        if(loop > 3)
494 <          break;
495 <      }
496 <      smDir(sm,v2,id2);
497 <      /* determine if convex (left turn), or concave(right turn) angle */
498 <      if(!convex_angle(v0,v1,v2))
499 <      {
500 <        VCOPY(v0,v1);
501 <        VCOPY(v1,v2);
502 <        id0 = id1;
503 <        id1 = id2;
504 <        prev = l;
505 <        eprev = e2;
506 <        continue;
507 <      }
296 >      /* determine if v0-v1-v2 is convex:defined clockwise on the sphere-
297 >       so switch orientation
298 >       */
299        VCROSS(n,v0,v2);
300 <      dp = DOT(n,p);
301 <      if(loop <=1 && (!ZERO(dp) && dp  < 0.0))
300 >      normalize(n);
301 >      dp1 = DOT(n,p);      
302 >      if(dp1  <= 0.0)
303        {
304 <        VCOPY(v0,v1);
305 <        VCOPY(v1,v2);
306 <        id0 = id1;
307 <        id1 = id2;
308 <        eprev = e2;
309 <        prev = l;
310 <        continue;
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 >        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 >            /* 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        }
332 <      loop = FALSE;
521 <
522 <      enext = 0;
523 <      t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext);
524 <      *add_ptr = push_data(*add_ptr,t_id);
525 <
526 <      LIST_NEXT(prev) = LIST_NEXT(l);
527 <      LIST_DATA(prev) = eprev = -enext;
528 <      LIST_NEXT(l)=NULL;
529 <      if(l== plist)
530 <        plist = prev;
531 <      free_list(l);
532 <      l = prev;
332 >      VCOPY(v0,v1);
333        VCOPY(v1,v2);
334 +      id0 = id1;
335        id1 = id2;
336 +      e1 = e2;  
337 +      /* check if gone around circular list without adding any
338 +         triangles: prevent infinite loop */
339 +      if(l == plist)
340 +      {
341 +        if(LIST_NEXT(LIST_NEXT(l)) == prev)
342 +          {/* Check if have a triangle */
343 +            is_tri = TRUE;      
344 +            break;
345 +          }
346 +        if(!cut)
347 +          break;
348 +        cut = FALSE;
349 +      }
350 +      prev = l;
351      }
352      if(is_tri)
353      {
354        l = LIST_NEXT(l);
355 <      enext = (int)LIST_DATA(l);
356 <      t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext);
541 <      *add_ptr = push_data(*add_ptr,t_id);
355 >      enew = (int)LIST_DATA(l);
356 >      t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
357        free_list(l);
358 <     }
358 >    }
359      else
360 <      {
361 < #ifdef DEBUG      
362 <        eputs("smTriangulate_elist()Unable to triangulate\n");
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
549 –        return(FALSE);
550 –      }
551 –    return(TRUE);
552 – }
371  
372 < int
373 < smTriangulate(sm,p_id,plist,add_ptr)
374 < SM *sm;
375 < int p_id;
376 < LIST *plist,**add_ptr;
377 < {
378 <    int e,id_t0,id_t1,e0,e1;
379 <    int test;
380 <
381 <    test = smTriangulate_elist_new(sm,p_id,plist,add_ptr);
372 >    /* Set triangle adjacencies based on edge adjacencies */
373 >    FOR_ALL_EDGES(enew)
374 >    {
375 >      id0 = E_NTH_TRI(enew,0);
376 >      id1 = E_NTH_TRI(enew,1);
377 >        
378 >      e1 = (T_WHICH_V(SM_NTH_TRI(sm,id0),E_NTH_VERT(enew,0))+2)%3;
379 >      T_NTH_NBR(SM_NTH_TRI(sm,id0),e1) = id1;
380 >      
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 <    test = smTriangulate_elist(sm,plist,add_ptr);
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 <    if(!test)
395 <       return(test);
394 > #ifdef DEBUG
395 > #if DEBUG > 1
396 >    {
397 >      TRI *t0,*t1,*n;
398  
399 <    FOR_ALL_EDGES(e)
399 >    FOR_ALL_EDGES(enew)
400      {
401 <        id_t0 = E_NTH_TRI(e,0);
402 <        id_t1 = E_NTH_TRI(e,1);
403 <        if((id_t0==INVALID) || (id_t1==INVALID))
404 <        {
405 < #ifdef DEBUG
406 <           eputs("smTriangulate(): Unassigned edge neighbor\n");
407 < #endif
408 <            continue;
409 <        }
410 <        
411 <        e0 = T_WHICH_V(SM_NTH_TRI(sm,id_t0),E_NTH_VERT(e,0));
412 <        T_NTH_NBR(SM_NTH_TRI(sm,id_t0),e0) = id_t1;
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 <        e1 = T_WHICH_V(SM_NTH_TRI(sm,id_t1),E_NTH_VERT(e,1));
442 <        T_NTH_NBR(SM_NTH_TRI(sm,id_t1),e1) = id_t0;
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 <    return(test);
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 601 | Line 497 | TRI *t;
497        return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1));
498      else if(T_NTH_V(t,2)==E_NTH_VERT(e,0))
499        return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1));
500 +
501    return(FALSE);
502   }
503  
504 < smFix_edges(sm,add_list,delptr)
504 >
505 > void
506 > smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
507     SM *sm;
508 <   LIST *add_list;
509 <   QUADTREE *delptr;
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)
650 +   SM *sm;
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;
654      FVECT v0,v1,v2,p,np,v;
655 +    TRI *t0,*t1;
656  
657      FOR_ALL_EDGES(e)
658      {
659          t0_id = E_NTH_TRI(e,0);
660          t1_id = E_NTH_TRI(e,1);
621 –        if((t0_id==INVALID) || (t1_id==INVALID))
622 –        {
661   #ifdef DEBUG
662 <            eputs("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
665 <            continue;
666 <        }
667 <        e0 = T_WHICH_V(SM_NTH_TRI(sm,t0_id),E_NTH_VERT(e,0));
668 <        e1 = T_WHICH_V(SM_NTH_TRI(sm,t1_id),E_NTH_VERT(-e,0));
669 <        e0_next = (e0+2)%3;
631 <        e1_next = (e1+2)%3;
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);
668 >        e1 = T_NTH_NBR_PTR(t0_id,t1);
669 >
670          v0_id = E_NTH_VERT(e,0);
671          v1_id = E_NTH_VERT(e,1);
672 <        v2_id = T_NTH_V(SM_NTH_TRI(sm,t0_id),e0_next);
673 <        p_id = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1_next);
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,
684 <                            delptr);
685 <            
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 >            */
687              FOR_ALL_EDGES_FROM(e,i)
688              {
689                if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id)
# Line 662 | Line 701 | smFix_edges(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 670 | Line 713 | smFix_edges(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      }
675 –    smUpdate_locator(sm,add_list,qtqueryset(*delptr));
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 + */
747   int
748 < smMesh_remove_vertex(sm,id)
748 > smRemoveVertex(sm,id)
749     SM *sm;
750     int id;
751   {
752 <    int t_id;
753 <    LIST *elist,*add_list;
754 <    int cnt,debug;
755 <    QUADTREE delnode;
756 <    /* generate list of vertices that form the boundary of the
757 <       star polygon formed by vertex id and all of its adjacent
758 <       triangles
759 <     */
760 <    eClear_edges();
761 <    elist = smVertex_star_polygon(sm,id,&delnode);
762 <
763 <    if(!elist)
695 <    {
696 < #ifdef DEBUG
697 <      eputs("smMesh_remove_vertex(): Unable to remove vertex");
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 >    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
699 –      qtfreeleaf(delnode);
700 –      return(FALSE);
701 –    }
702 –    add_list = NULL;
703 –    /* Triangulate spherical polygon */
704 –    if(!smTriangulate(sm,id,elist,&add_list))
705 –    {
706 –      while(add_list)
707 –      {
708 –        t_id = pop_list(&add_list);
709 –        smDelete_tri(sm,t_id);
710 –      }
711 –      qtfreeleaf(delnode);
712 –      return(FALSE);
713 –    }
714 –    /* Fix up new triangles to be Delaunay */
715 –    smFix_edges(sm,add_list,&delnode);
765  
766 <    qtfreeleaf(delnode);
766 >    /* Triangulate polygonal hole  */
767 >    smTriangulate(sm,id,b_list);
768 >    
769 >    /* Fix up new triangles to be Delaunay*/
770 >
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