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.3 by gwlarson, Fri Sep 11 11:52:25 1998 UTC vs.
Revision 3.9 by gwlarson, Tue Jan 5 16:52:37 1999 UTC

# Line 8 | Line 8 | static char SCCSid[] = "$SunId$ SGI";
8   *  sm_del.c
9   */
10   #include "standard.h"
11 <
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"
16   #include "sm.h"
17  
18 < static EDGE Edges[MAX_EDGES];
18 > static int Max_edges=200;
19 > static EDGE *Edges=NULL;
20   static int Ecnt=0;
21  
19 – int
20 – remove_tri(qtptr,fptr,t_id)
21 –   QUADTREE *qtptr;
22 –   int *fptr;
23 –   int t_id;
24 – {
25 –    OBJECT tset[QT_MAXSET+1];  
26 –    int n;
27 –
28 –   if(QT_IS_EMPTY(*qtptr))
29 –     return(FALSE);
30 –   /* remove id from set */
31 –      else
32 –      {
33 –         if(!qtinset(*qtptr,t_id))
34 –           return(FALSE);
35 –         n = QT_SET_CNT(qtqueryset(*qtptr))-1;
36 –         *qtptr = qtdelelem(*qtptr,t_id);
37 –          if(n  == 0)
38 –             (*fptr) |= QT_COMPRESS;
39 –        if(!QT_FLAG_FILL_TRI(*fptr))
40 –          (*fptr)++;
41 –      }
42 –    return(TRUE);
43 – }
44 –
45 – int
46 – remove_tri_compress(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id)
47 – QUADTREE *qtptr;
48 – FVECT q0,q1,q2;
49 – FVECT t0,t1,t2;
50 – int n;
51 – int *arg;
52 – int t_id;
53 – {
54 –    int f = 0;
55 –    /* NOTE compress */
56 –    return(remove_tri(qtptr,&f,t_id));
57 – }
58 –
59 –
60 –
61 – int
62 – stDelete_tri(st,t_id,t0,t1,t2)
63 –   STREE *st;
64 –   int t_id;
65 –   FVECT t0,t1,t2;
66 – {
67 –    int f;
68 –    FVECT dir;
69 –    
70 –  /* First add all of the leaf cells lying on the triangle perimeter:
71 –     mark all cells seen on the way
72 –   */
73 –    ST_CLEAR_FLAGS(st);
74 –    f = 0;
75 –    VSUB(dir,t1,t0);
76 –    stTrace_edge(st,t0,dir,1.0,remove_tri,&f,t_id);
77 –    VSUB(dir,t2,t1);
78 –    stTrace_edge(st,t1,dir,1.0,remove_tri,&f,t_id);
79 –    VSUB(dir,t0,t2);
80 –    stTrace_edge(st,t2,dir,1.0,remove_tri,&f,t_id);
81 –    /* Now visit interior */
82 –    if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f))
83 –       stVisit_tri_interior(st,t0,t1,t2,remove_tri_compress,&f,t_id);
84 – }
85 –
86 –
87 – smLocator_remove_tri(sm,t_id)
88 – SM *sm;
89 – int t_id;
90 – {
91 –  STREE *st;
92 –  char found;
93 –  TRI *t;
94 –  FVECT v0,v1,v2;
95 –
96 –  st = SM_LOCATOR(sm);
97 –
98 –  t = SM_NTH_TRI(sm,t_id);
99 –
100 –  VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm));
101 –  VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm));
102 –  VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm));
103 –  found = stUpdate_tri(st,t_id,v0,v1,v2,remove_tri,remove_tri_compress);
104 –  return(found);
105 – }
106 –
22   smFree_tri(sm,id)
23   SM *sm;
24   int id;
25   {
26 <  TRI *tri;
26 >  TRI *tri,*t;
27  
28    tri = SM_NTH_TRI(sm,id);
29    /* Add to the free_list */
30 +
31    T_NEXT_FREE(tri) = SM_FREE_TRIS(sm);
32    SM_FREE_TRIS(sm) = id;
33    T_VALID_FLAG(tri) = -1;
# Line 125 | Line 41 | SM *sm;
41   int t_id;
42   {
43  
128 –
44    /* NOTE: Assumes that a new triangle adjacent to each vertex
45       has been added- before the deletion: replacing
46       the old tri- and therefore dont need to dereference any pointers
47       to id because the vertices can no longer
48       point to tri id as being the first triangle pointer
49    */
50 +  SM_SAMPLE_TRIS(sm)--;
51    if(!SM_IS_NTH_T_BASE(sm,t_id))
52    {
53 <    SM_NUM_TRIS(sm)--;
53 >
54 > #if 0
55      if(SM_IS_NTH_T_NEW(sm,t_id))
56        smNew_tri_cnt--;
57 + #endif
58    }
59    smClear_tri_flags(sm,t_id);
60  
61    smFree_tri(sm,t_id);
144 –
62   }
63  
64  
65 + int
66 + eNew_edge()
67 + {
68 +  if(!Edges)
69 +    if(!(Edges = (EDGE *)realloc(NULL,(Max_edges+1)*sizeof(EDGE))))
70 +      goto memerr;
71  
72 < LIST
73 < *smVertex_star_polygon(sm,id)
72 >  if(Ecnt >= Max_edges)
73 >    {
74 >      if(Max_edges > 10000)
75 >        error(CONSISTENCY,"Too many edges in vertex loop\n");
76 >      Max_edges += 100;
77 >      if(!(Edges = (EDGE *)realloc(Edges,(Max_edges+1)*sizeof(EDGE))))
78 >        goto memerr;
79 >    }
80 >  return(++Ecnt);
81 >
82 > memerr:
83 >  error(SYSTEM,"eNew_edge(): Unable to allocate memory");
84 > }
85 >
86 > /* Return list of edges defining polygon formed by boundary of triangles
87 > adjacent to id. Return set of triangles adjacent to id to delete in delptr
88 > */
89 > LIST
90 > *smVertexPolygon(sm,id,del_ptr)
91   SM *sm;
92   int id;
93 + LIST **del_ptr;
94   {
95      TRI *tri,*t_next;
96 <    LIST *elist,*end,*tlist;
97 <    int t_id,v_next,t_next_id;
157 <    int e;
96 >    LIST *elist,*end;
97 >    int e,t_id,v_next,t_next_id,b_id,v_id;
98  
99 +    eClear_edges();
100      elist = end =  NULL;
101 +
102      /* Get the first triangle adjacent to vertex id */
103      t_id = SM_NTH_VERT(sm,id);
104      tri = SM_NTH_TRI(sm,t_id);
105  
106 <    
107 <    if((e = eNew_edge()) == SM_INVALID)
108 <    {
109 < #ifdef DEBUG
110 <        eputs("smVertex_star_polygon():Too many edges\n");
111 < #endif
112 <        return(NULL);
113 <    }
106 >    e = eNew_edge();
107 >    /* Get the  next vertex on the polygon boundary */
108 >    v_id = T_WHICH_V(tri,id);
109 >    b_id = (v_id + 1)%3;
110 >    /* Create an edge */
111 >    SET_E_NTH_VERT(e,0,T_NTH_V(tri,b_id));
112 >    SET_E_NTH_TRI(e,0,INVALID);
113 >    SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_id));
114 >    v_next = T_NTH_V(tri,(b_id+1)%3);
115 >    SET_E_NTH_VERT(e,1,v_next);
116      elist = add_data_to_circular_list(elist,&end,e);
173 –    v_next = (T_WHICH_V(tri,id)+1)%3;
174 –    SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next));
175 –    SET_E_NTH_TRI(e,0,SM_INVALID);
176 –    SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next));
177 –    v_next = (T_WHICH_V(tri,id)+2)%3;
178 –    SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next));
179 –
180 –    
117      t_next_id = t_id;
118      t_next = tri;
119  
120 <    tlist = push_data(NULL,t_id);
120 >    *del_ptr = push_data(*del_ptr,t_id);
121 >    /* Create a set to hold all of the triangles for deletion later */
122  
123 <    while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id)
187 <    {  
188 <        if((e = eNew_edge()) == SM_INVALID)
189 <        {
190 < #ifdef DEBUG
191 <            eputs("smVertex_star_polygon():Too many edges\n");
192 < #endif
193 <            return(NULL);
194 <        }
195 <        elist = add_data_to_circular_list(elist,&end,e);
196 <        t_next = SM_NTH_TRI(sm,t_next_id);
197 <        v_next = (T_WHICH_V(t_next,id)+1)%3;
198 <        SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next));
199 <        SET_E_NTH_TRI(e,0,SM_INVALID);
200 <        SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next));
201 <        v_next = (T_WHICH_V(t_next,id)+2)%3;
202 <        SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next));
203 <        tlist = push_data(tlist,t_next_id);
204 <    }
205 <    while(tlist)
123 >    while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id)
124      {
125 <        t_id = (int)pop_list(&tlist);
126 <        /* first remove from point location structure */
127 <        smLocator_remove_tri(sm,t_id);
128 <        smDelete_tri(sm,t_id);
125 >      e = eNew_edge();
126 >      t_next = SM_NTH_TRI(sm,t_next_id);
127 >      SET_E_NTH_VERT(e,0,v_next);
128 >      SET_E_NTH_TRI(e,0,INVALID);
129 >      v_id = T_WHICH_V(t_next,id);
130 >      b_id = (v_id + 1)%3;
131 >      SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_id));
132 >      v_next = T_NTH_V(t_next,(b_id+1)%3);
133 >      SET_E_NTH_VERT(e,1,v_next);
134 >      elist = add_data_to_circular_list(elist,&end,e);
135 >      *del_ptr = push_data(*del_ptr,t_next_id);
136      }
137      return(elist);
138   }
139  
140 +
141   int
142 < smEdge_intersect_polygon(sm,v0,v1,l)
142 > smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr)
143   SM *sm;
144 < FVECT v0,v1;
219 < LIST *l;
144 > int id0,id1,id2,e0,e1,*e2ptr;
145   {
146 <    FVECT e0,e1;
147 <    int e,id_e0,id_e1;
223 <    LIST *el,*eptr;
224 <    
225 <    /* Test the edges in l against v0v1 to see if v0v1 intersects
226 <       any other edges
227 <     */
228 <    
229 <    el = l;
146 >  int t_id;
147 >  int e2;
148  
149 <    while(el)
150 <    {
151 <      e = (int)LIST_DATA(el);
234 <      id_e0 = E_NTH_VERT(e,0);
235 <      id_e1 = E_NTH_VERT(e,1);
236 <      /* NOTE: DO these need to be normalized? Just subtract center? */
237 <      smDir(sm,e0,id_e0);
238 <      smDir(sm,e1,id_e1);
239 <      if(sedge_intersect(v0,v1,e0,e1))
240 <        return(TRUE);
241 <
242 <      el = LIST_NEXT(el);
243 <      if(el == l)
244 <        break;
245 <    }
246 <    return(FALSE);
247 < }
248 <
249 < int
250 < smFind_next_convex_vertex(sm,id0,id1,v0,v1,l)
251 <   SM *sm;
252 <   int id0,id1;
253 <   FVECT v0,v1;
254 <   LIST *l;
255 < {
256 <    int e,id;
257 <    LIST *el;
258 <    FVECT v;
259 <
260 <    /* starting with the end of edge at head of l, search sequentially for
261 <      vertex v such that v0v1v is a convex angle, and the edge v1v does
262 <      not intersect any other edges
263 <   */
264 <    id = SM_INVALID;
265 <    el = l;
266 <    while(id != id0)
267 <    {
268 <        e = (int)LIST_DATA(el);
269 <        id = E_NTH_VERT(e,1);
270 <
271 <        smDir(sm,v,id);
272 <
273 <        if(convex_angle(v0,v1,v) && !smEdge_intersect_polygon(sm,v1,v,l))
274 <           return(id);
275 <              
276 <        el = LIST_NEXT(el);
277 <        if(el == l)
278 <           break;
279 <    }
280 <    return(SM_INVALID);
281 < }
282 <
283 < int
284 < split_edge_list(id0,id_new,l,lnew)
285 < int id0,id_new;
286 < LIST **l,**lnew;
287 < {
288 <    LIST *list,*lptr,*end;
289 <    int e,e1,e2,new_e;
290 <
291 <    e2 = SM_INVALID;
292 <    list = lptr = *l;
293 <
294 <    if((new_e = eNew_edge())==SM_INVALID)
295 <     {
296 < #ifdef DEBUG
297 <            eputs("split_edge_list():Too many edges\n");
149 > #ifdef DEBUG
150 >  if(id0 == INVALID || id1==INVALID || id2==INVALID)
151 >    error(CONSISTENCY,"bad id- smTriangulate_add_tri()\n");
152   #endif
153 <         return(FALSE);
154 <     }
155 <    SET_E_NTH_VERT(new_e,0,id0);
156 <    SET_E_NTH_VERT(new_e,1,id_new);
157 <    SET_E_NTH_TRI(new_e,0,SM_INVALID);
158 <    SET_E_NTH_TRI(new_e,1,SM_INVALID);
159 <    
160 <    while(e2 != id_new)
161 <    {
162 <        lptr = LIST_NEXT(lptr);
163 <        e = (int)LIST_DATA(lptr);
164 <        e2 = E_NTH_VERT(e,1);
165 <        if(lptr == list)
312 <        {
313 < #ifdef DEBUG        
314 <          eputs("split_edge_list():cant find vertex\n");
315 < #endif
316 <          *lnew = NULL;
317 <          return(FALSE);
318 <        }
153 >  t_id = smAdd_tri(sm,id0,id1,id2);
154 >  if(*e2ptr == 0)
155 >  {
156 >    e2 = eNew_edge();
157 >    SET_E_NTH_VERT(e2,0,id2);
158 >    SET_E_NTH_VERT(e2,1,id0);
159 >  }
160 >  else
161 >    e2 = *e2ptr;
162 >  /* set appropriate tri for each edge*/
163 >  SET_E_NTH_TRI(e0,0,t_id);
164 >  SET_E_NTH_TRI(e1,0,t_id);
165 >  SET_E_NTH_TRI(e2,0,t_id);
166  
167 <    }
168 <    end = lptr;
322 <    lptr =  LIST_NEXT(lptr);
323 <    list = add_data_to_circular_list(list,&end,-new_e);
324 <    *lnew = list;
325 <
326 <    /* now follow other cycle */
327 <
328 <    list = lptr;
329 <    e2 = SM_INVALID;
330 <    while(e2 != id0)
331 <    {
332 <        lptr = LIST_NEXT(lptr);
333 <        e = (int)LIST_DATA(lptr);
334 <        e2 = E_NTH_VERT(e,1);
335 <        if(lptr == list)
336 <        {
337 < #ifdef DEBUG        
338 <          eputs("split_edge_list():cant find intial vertex\n");
339 < #endif
340 <          *l = NULL;
341 <          return(FALSE);
342 <        }
343 <
344 <    }
345 <    end = lptr;
346 <    list = add_data_to_circular_list(list,&end,new_e);
347 <    *l = list;
348 <    return(TRUE);
167 >  *e2ptr = e2;
168 >  return(t_id);
169   }
170  
351 –
171   int
172 < smTriangulate_convex(sm,plist)
172 > smTriangulateConvex(sm,plist,add_ptr)
173   SM *sm;
174 < LIST *plist;
174 > LIST *plist,**add_ptr;
175   {
357 –    TRI *tri;
176      int t_id,e_id0,e_id1,e_id2;
177      int v_id0,v_id1,v_id2;
178      LIST *lptr;
361 –    int cnt;
179  
180      lptr = plist;
181      e_id0 = (int)LIST_DATA(lptr);
# Line 369 | Line 186 | LIST *plist;
186          e_id1 = (int)LIST_DATA(lptr);
187          v_id1 = E_NTH_VERT(e_id1,0);
188          v_id2 = E_NTH_VERT(e_id1,1);
372 –        /* form a triangle for each triple of with v0 as base of star */
373 –        t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri);
374 –        smLocator_add_tri(sm,t_id,v_id0,v_id1,v_id2);
375 –        /* add which pointer?*/
376 –
189          lptr = LIST_NEXT(lptr);
190  
191 <        if(LIST_NEXT(lptr) != plist)
192 <        {
381 <            e_id2 = eNew_edge();
382 <            SET_E_NTH_VERT(e_id2,0,v_id2);
383 <            SET_E_NTH_VERT(e_id2,1,v_id0);
384 <        }
191 >        if(LIST_NEXT(lptr) != plist)    
192 >          e_id2 = 0;
193          else
194             e_id2 = (int)LIST_DATA(lptr);
195 <        
196 <        /* set appropriate tri for each edge*/
389 <        SET_E_NTH_TRI(e_id0,0,t_id);
390 <        SET_E_NTH_TRI(e_id1,0,t_id);
391 <        SET_E_NTH_TRI(e_id2,0,t_id);
392 <
195 >        t_id = smTriangulate_add_tri(sm,v_id0,v_id1,v_id2,e_id0,e_id1,&e_id2);
196 >        *add_ptr = push_data(*add_ptr,t_id);
197          e_id0 = -e_id2;
198      }
395 –    
199      free_list(plist);
200      return(TRUE);
201   }
202 + #ifdef TEST_DRIVER
203 + FVECT Norm[500],B_V[500];
204 + int Ncnt,Bcnt,Del=0;
205 + #endif
206 +
207 +
208 + /* Triangulate the polygon defined by plist, and generating vertex p_id.
209 +   Return list of added triangles in list add_ptr. Returns TRUE if
210 +   successful, FALSE otherwise. This is NOT a general triangulation routine,
211 +   assumes polygon star relative to id
212 + */
213 +
214   int
215 < smTriangulate_elist(sm,plist)
215 > smTriangulate(sm,id,plist,add_ptr)
216   SM *sm;
217 < LIST *plist;
217 > int id;
218 > LIST *plist,**add_ptr;
219   {
220 <    LIST *l,*el1;
221 <    FVECT v0,v1,v2;
222 <    int id0,id1,id2,e,id_next;
223 <    char flipped;
224 <    int done;
220 >    LIST *l,*prev,*t;
221 >    FVECT v0,v1,v2,n,p;
222 >    int is_tri,is_convex,cut,t_id,id0,id1,id2,e2,e1,enew;
223 >    double dp;
224 >    static int debug=0;
225  
226 <    l = plist;
227 <    
226 >    VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
227 >    enew = 0;
228 >    is_convex = TRUE;
229 >    cut = is_tri= FALSE;
230 >    l = prev = plist;
231 >
232 >    /* get v0,v1 */
233 >    e1 = (int)LIST_DATA(l);
234 >    id0 = E_NTH_VERT(e1,0);
235 >    id1 = E_NTH_VERT(e1,1);
236 >    VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm));
237 >    VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm));  
238 > #ifdef TEST_DRIVER
239 >    Del = TRUE;
240 >    VCOPY(B_V[0],v0);
241 >    VCOPY(B_V[1],v1);
242 >    Bcnt = 2;
243 >    Ncnt = 0;
244 > #endif
245      while(l)
246      {
414 –        /* get v0,v1,v2 */
415 –      e = (int)LIST_DATA(l);
416 –      id0 = E_NTH_VERT(e,0);
417 –      id1 = E_NTH_VERT(e,1);
247        l = LIST_NEXT(l);
248 <      e = (int)LIST_DATA(l);
249 <      id2 = E_NTH_VERT(e,1);
248 >      /* Get v2 */
249 >      e2 = (int)LIST_DATA(l);
250 >      id2 = E_NTH_VERT(e2,1);
251 >      VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
252 > #ifdef TEST_DRIVER
253 >      VCOPY(B_V[Bcnt++],v2);
254 > #endif
255 >      if(LIST_NEXT(LIST_NEXT(l)) == prev)
256 >      {/* Check if have a triangle */
257 >           is_tri = TRUE;      
258 >           break;
259 >      }
260  
261 <      smDir(sm,v0,id0);
262 <      smDir(sm,v1,id1);
263 <      smDir(sm,v2,id2);
264 <      /* determine if convex (left turn), or concave(right turn) angle */
426 <      if(convex_angle(v0,v1,v2))
261 >      /* determine if v0-v1-v2 is convex:defined clockwise on the sphere-
262 >       so switch orientation
263 >       */
264 >      if(convex_angle(v2,v1,v0))
265        {
266 <        if(l == plist)
267 <          break;
268 <        else
266 >          /* test if safe to cut off v0-v1-v2 by testing if p lies outside of
267 >         triangle v0-v1-v2: if so, because plist is the star polygon around p,
268 >          the new edge v2-v0 cannot intersect any existing edges
269 >        */
270 >        VCROSS(n,v0,v2);
271 >        dp = DOT(n,p);
272 >        if(dp  <= 0.0)
273 >        {
274 >            /* remove edges e1,e2 and add triangle id0,id1,id2 */
275 >          enew = 0;
276 >          t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
277 >          cut = TRUE;
278 >          *add_ptr = push_data(*add_ptr,t_id);
279 >           /* Insert edge enew into the list, reuse prev list element */
280 >          LIST_NEXT(prev) = LIST_NEXT(l);
281 >          LIST_DATA(prev) = e1 = -enew;
282 >           /* If removing head of list- reset plist pointer */
283 >          if(l== plist)
284 >            plist = prev;
285 >          /* free list element for e2 */
286 >          LIST_NEXT(l)=NULL;
287 >          free_list(l);
288 >          l = prev;
289 >          VCOPY(v1,v2);
290 >          id1 = id2;
291            continue;
292 +        }
293        }
294 <      /* if concave: add edge and recurse on two sub polygons */
295 <      id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l));
296 <      if(id_next == SM_INVALID)
294 >      else
295 >        is_convex = FALSE;
296 >      VCOPY(v0,v1);
297 >      VCOPY(v1,v2);
298 >      id0 = id1;
299 >      id1 = id2;
300 >      e1 = e2;  
301 >      /* check if gone around circular list without adding any
302 >         triangles: prevent infinite loop */
303 >      if(l == plist)
304        {
305 +        if(LIST_NEXT(LIST_NEXT(l)) == prev)
306 +          {/* Check if have a triangle */
307 +            is_tri = TRUE;      
308 +            break;
309 +          }
310 +
311 +        if(is_convex)
312 +          break;
313 +        if(!cut)
314 +        {
315   #ifdef DEBUG
316 <          eputs("smTriangulate_elist():Unable to find convex vertex\n");
316 >          eputs("smTriangulate():Unable to triangulate\n");
317   #endif
318 +         free_list(l);
319 +          while(*add_ptr)
320 +          {
321 +            t_id = pop_list(add_ptr);
322 +            smDelete_tri(sm,t_id);
323 +          }
324            return(FALSE);
325 +         }
326 +        
327 +        cut = FALSE;
328 +        is_convex = TRUE;
329        }
330 <      /* add edge */
443 <      el1 = NULL;
444 <      /* Split edge list l into two lists: one from id1-id_next-id1,
445 <         and the next from id2-id_next-id2
446 <      */
447 <      split_edge_list(id1,id_next,&l,&el1);
448 <      /* Recurse and triangulate the two edge lists */
449 <      done = smTriangulate_elist(sm,l);
450 <      if(done)
451 <        done = smTriangulate_elist(sm,el1);
452 <      return(done);
330 >      prev = l;
331      }
332 <    done = smTriangulate_convex(sm,plist);
333 <    return(done);
334 < }
332 >    if(is_tri)
333 >    {
334 >      l = LIST_NEXT(l);
335 >      enew = (int)LIST_DATA(l);
336 >      t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
337 >      *add_ptr = push_data(*add_ptr,t_id);
338 >      free_list(l);
339 >    }
340 >    else
341 >      if(!smTriangulateConvex(sm,l,add_ptr))
342 >        return(FALSE);
343  
344 < int
345 < smTriangulate(sm,plist)
460 < SM *sm;
461 < LIST *plist;
462 < {
463 <    int e,id_t0,id_t1,e0,e1;
464 <    TRI *t0,*t1;
465 <    int test;
466 <    
467 <    test = smTriangulate_elist(sm,plist);
468 <
469 <    if(!test)
470 <       return(test);
471 <    FOR_ALL_EDGES(e)
344 >    /* Set triangle adjacencies based on edge adjacencies */
345 >    FOR_ALL_EDGES(enew)
346      {
347 <        id_t0 = E_NTH_TRI(e,0);
348 <        id_t1 = E_NTH_TRI(e,1);
475 <        if((id_t0==SM_INVALID) || (id_t1==SM_INVALID))
476 <        {
477 < #ifdef DEBUG
478 <           eputs("smTriangulate(): Unassigned edge neighbor\n");
479 < #endif
480 <            continue;
481 <        }
482 <        t0 = SM_NTH_TRI(sm,id_t0);
483 <        t1 = SM_NTH_TRI(sm,id_t1);
347 >      id0 = E_NTH_TRI(enew,0);
348 >      id1 = E_NTH_TRI(enew,1);
349          
350 <        e0 = T_WHICH_V(t0,E_NTH_VERT(e,0));
351 <        T_NTH_NBR(t0,e0) = id_t1;
352 <
353 <        e1 = T_WHICH_V(t1,E_NTH_VERT(e,1));
354 <        T_NTH_NBR(t1,e1) = id_t0;
350 >      e1 = (T_WHICH_V(SM_NTH_TRI(sm,id0),E_NTH_VERT(enew,0))+2)%3;
351 >      T_NTH_NBR(SM_NTH_TRI(sm,id0),e1) = id1;
352 >      
353 >      e2 = (T_WHICH_V(SM_NTH_TRI(sm,id1),E_NTH_VERT(enew,1))+2)%3;
354 >      T_NTH_NBR(SM_NTH_TRI(sm,id1),e2) = id0;
355      }
356 <    return(test);
356 >    return(TRUE);
357   }
358  
359   eIn_tri(e,t)
# Line 503 | Line 368 | TRI *t;
368        return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1));
369      else if(T_NTH_V(t,2)==E_NTH_VERT(e,0))
370        return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1));
371 +
372    return(FALSE);
373   }
374 < smFix_edges(sm)
374 >
375 > /* Test the new set of triangles for Delaunay condition. 'Edges' contains
376 >   all of the new edges added. The CCW triangle assoc with each edge is
377 >   tested against the opposite vertex of the CW triangle. If the vertex
378 >   lies inside the circle defined by the CCW triangle- the edge is swapped
379 >   for the opposite diagonal
380 > */
381 > smFixEdges(sm,add_list)
382     SM *sm;
383 +   LIST *add_list;
384   {
385 <    int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next;
386 <    TRI *t0,*t1,*nt0,*nt1;
513 <    int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1;
385 >    int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next;
386 >    int i,v0_id,v1_id,v2_id,p_id,t0_nid,t1_nid;
387      FVECT v0,v1,v2,p,np,v;
388 <    LIST *add,*del;
389 <    
517 <    add = del = NULL;
388 >    TRI *t0,*t1;
389 >
390      FOR_ALL_EDGES(e)
391      {
392 <        id_t0 = E_NTH_TRI(e,0);
393 <        id_t1 = E_NTH_TRI(e,1);
394 <        if((id_t0==SM_INVALID) || (id_t1==SM_INVALID))
392 >        t0_id = E_NTH_TRI(e,0);
393 >        t1_id = E_NTH_TRI(e,1);
394 >        if((t0_id==INVALID) || (t1_id==INVALID))
395          {
396   #ifdef DEBUG
397 <            eputs("smFix_edges: Unassigned edge nbr\n");
397 >            error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n");
398   #endif
527 –            continue;
399          }
400 <        t0 = SM_NTH_TRI(sm,id_t0);
401 <        t1 = SM_NTH_TRI(sm,id_t1);
402 <        
403 <        e0 = T_WHICH_V(t0,E_NTH_VERT(e,0));
533 <        e1 = T_WHICH_V(t1,E_NTH_VERT(-e,0));
534 <        e0_next = (e0+2)%3;
535 <        e1_next = (e1+2)%3;
536 <        id_v0 = E_NTH_VERT(e,0);
537 <        id_v1 = E_NTH_VERT(e,1);
538 <        id_v2 = T_NTH_V(t0,e0_next);
539 <        id_p = T_NTH_V(t1,e1_next);
400 >        t0 = SM_NTH_TRI(sm,t0_id);
401 >        t1 = SM_NTH_TRI(sm,t1_id);
402 >        e0 = T_NTH_NBR_PTR(t1_id,t0);
403 >        e1 = T_NTH_NBR_PTR(t0_id,t1);
404  
405 <        smDir(sm,v0,id_v0);
406 <        smDir(sm,v1,id_v1);
407 <        smDir(sm,v2,id_v2);
405 >        v0_id = E_NTH_VERT(e,0);
406 >        v1_id = E_NTH_VERT(e,1);
407 >        v2_id = T_NTH_V(t0,e0);
408 >        p_id = T_NTH_V(t1,e1);
409 >
410 >        smDir_in_cone(sm,v0,v0_id);
411 >        smDir_in_cone(sm,v1,v1_id);
412 >        smDir_in_cone(sm,v2,v2_id);
413          
414 <        VCOPY(p,SM_NTH_WV(sm,id_p));    
414 >        VCOPY(p,SM_NTH_WV(sm,p_id));    
415          VSUB(p,p,SM_VIEW_CENTER(sm));
416          if(point_in_cone(p,v0,v1,v2))
417          {
418 <            smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add,&del);
418 >           smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list);
419              
420 <            nt0 = SM_NTH_TRI(sm,nid_t0);
421 <            nt1 = SM_NTH_TRI(sm,nid_t1);
420 >           /* Adjust the triangle pointers of the remaining edges to be
421 >              processed
422 >            */
423              FOR_ALL_EDGES_FROM(e,i)
424              {
425 <              if(E_NTH_TRI(i,0)==id_t0 || E_NTH_TRI(i,0)==id_t1)
425 >              if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id)
426                {
427 <                if(eIn_tri(i,nt0))
428 <                  SET_E_NTH_TRI(i,0,nid_t0);
427 >                if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
428 >                  SET_E_NTH_TRI(i,0,t0_nid);
429                  else
430 <                  SET_E_NTH_TRI(i,0,nid_t1);
430 >                  SET_E_NTH_TRI(i,0,t1_nid);
431                }
432  
433 <              if(E_NTH_TRI(i,1)==id_t0 || E_NTH_TRI(i,1)==id_t1)
433 >              if(E_NTH_TRI(i,1)==t0_id || E_NTH_TRI(i,1)==t1_id)
434                {
435 <                if(eIn_tri(i,nt0))
436 <                  SET_E_NTH_TRI(i,1,nid_t0);
435 >                if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
436 >                  SET_E_NTH_TRI(i,1,t0_nid);
437                  else
438 <                  SET_E_NTH_TRI(i,1,nid_t1);
438 >                  SET_E_NTH_TRI(i,1,t1_nid);
439                }
440              }
441 <            id_t0 = nid_t0;
442 <            id_t1 = nid_t1;
441 >            t0_id = t0_nid;
442 >            t1_id = t1_nid;
443              e_new = eNew_edge();
444 <            SET_E_NTH_VERT(e_new,0,id_p);
445 <            SET_E_NTH_VERT(e_new,1,id_v2);
446 <            SET_E_NTH_TRI(e_new,0,id_t0);
447 <            SET_E_NTH_TRI(e_new,1,id_t1);
444 >            SET_E_NTH_VERT(e_new,0,p_id);
445 >            SET_E_NTH_VERT(e_new,1,v2_id);
446 >            SET_E_NTH_TRI(e_new,0,t0_id);
447 >            SET_E_NTH_TRI(e_new,1,t1_id);
448          }
449      }
450 <    smUpdate_locator(sm,add,del);
450 >    /* Add/Delete the appropriate triangles from the stree */
451 >    smUpdate_locator(sm,add_list);
452   }
453  
454 + /* Remove vertex "id" from the mesh- and retriangulate the resulting
455 +   hole: Returns TRUE if successful, FALSE otherwise.
456 + */
457   int
458 < smMesh_remove_vertex(sm,id)
458 > smRemoveVertex(sm,id)
459     SM *sm;
460     int id;
461   {
462 <    int tri;
463 <    LIST *elist;
464 <    int cnt,debug;
465 <    /* generate list of vertices that form the boundary of the
466 <       star polygon formed by vertex id and all of its adjacent
467 <       triangles
462 >    LIST *b_list,*add_list,*del_list;
463 >    int t_id,i;
464 >    static int cnt=0;
465 >    OBJECT *optr,*os;
466 >    /* generate list of edges that form the boundary of the
467 >       polygon formed by the triangles adjacent to vertex 'id'
468       */
469 <    eClear_edges();
470 <    elist = smVertex_star_polygon(sm,id);
597 <    if(!elist)
598 <       return(FALSE);
469 >    del_list = NULL;
470 >    b_list = smVertexPolygon(sm,id,&del_list);
471  
472 <    /* Triangulate spherical polygon */
473 <    smTriangulate(sm,elist);
472 >    add_list = NULL;
473 >    /* Triangulate polygonal hole  */
474 >    if(!smTriangulate(sm,id,b_list,&add_list))
475 >    {
476 >      free_list(del_list);
477 >      return(FALSE);
478 >    }
479 >    else
480 >    {
481 > #ifdef DEBUG
482 >      b_list = del_list;
483 >      while(b_list)
484 >      {
485 >        t_id = LIST_DATA(b_list);
486 >        b_list = LIST_NEXT(b_list);
487 >        T_VALID_FLAG(SM_NTH_TRI(sm,t_id))=-1;
488 >      }
489 > #endif
490 >      while(del_list)
491 >      {
492 >        t_id = pop_list(&del_list);
493 >        smDelete_tri(sm,t_id);
494 >      }    
495 >    }      
496 >    /* Fix up new triangles to be Delaunay-delnode contains set of
497 >     triangles to delete,add_list is the set of new triangles to add
498 >     */
499 >    smFixEdges(sm,add_list);
500  
603 –
604 –    /* Fix up new triangles to be Delaunay */
605 –    smFix_edges(sm);
606 –
501      return(TRUE);
502   }
503    
610 – /* Remove point from samples, and from mesh. Delete any triangles
611 –   adjacent to the point and re-triangulate the hole
612 –   Return TRUE is point found , FALSE otherwise
613 – */
614 – int
615 – smDelete_point(sm,id)
616 – SM *sm;
617 – int id;
618 – {
504  
620 –    /* Remove the corresponding vertex from the mesh */
621 –    smMesh_remove_vertex(sm,id);
622 –    /* Free the sample point */
623 –    smDelete_sample(sm,id);
624 –    return(TRUE);
625 – }
505  
506 <
628 <
506 >
507  
508  
509  

Diff Legend

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