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

Diff Legend

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