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

Diff Legend

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