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

Diff Legend

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