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.8 by gwlarson, Mon Dec 28 18:07:34 1998 UTC vs.
Revision 3.14 by greg, Wed Apr 23 00:52:34 2003 UTC

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

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines