ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_del.c
Revision: 3.8
Committed: Mon Dec 28 18:07:34 1998 UTC (25 years, 3 months ago) by gwlarson
Content type: text/plain
Branch: MAIN
Changes since 3.7: +54 -68 lines
Log Message:
New insertion routine
New Culling routine based on insertion algorithm
Adapted old insertion code: now used by picking
Point location code returns on-vertex,on-edge, or in-triangle
Added on_edge case for subdivision
Implemented unordered sets
Removed deletion from quadtree- added set compression to replace functionality

File Contents

# User Rev Content
1 gwlarson 3.1 /* Copyright (c) 1998 Silicon Graphics, Inc. */
2    
3     #ifndef lint
4     static char SCCSid[] = "$SunId$ SGI";
5     #endif
6    
7     /*
8     * sm_del.c
9     */
10     #include "standard.h"
11 gwlarson 3.6 #include "sm_flag.h"
12 gwlarson 3.1 #include "sm_list.h"
13     #include "sm_geom.h"
14 gwlarson 3.6 #include "sm_qtree.h"
15     #include "sm_stree.h"
16 gwlarson 3.1 #include "sm.h"
17    
18 gwlarson 3.6 static int Max_edges=200;
19     static EDGE *Edges=NULL;
20 gwlarson 3.1 static int Ecnt=0;
21    
22     smFree_tri(sm,id)
23     SM *sm;
24     int id;
25     {
26 gwlarson 3.8 TRI *tri,*t;
27 gwlarson 3.1
28     tri = SM_NTH_TRI(sm,id);
29     /* Add to the free_list */
30 gwlarson 3.8
31 gwlarson 3.1 T_NEXT_FREE(tri) = SM_FREE_TRIS(sm);
32     SM_FREE_TRIS(sm) = id;
33     T_VALID_FLAG(tri) = -1;
34     }
35    
36     /* Assumes mesh pointers have been cleaned up appropriately: just deletes from
37     Point location and triangle data structure
38     */
39     smDelete_tri(sm,t_id)
40     SM *sm;
41     int t_id;
42     {
43    
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 gwlarson 3.6 SM_SAMPLE_TRIS(sm)--;
53 gwlarson 3.1 if(SM_IS_NTH_T_NEW(sm,t_id))
54     smNew_tri_cnt--;
55     }
56     smClear_tri_flags(sm,t_id);
57    
58     smFree_tri(sm,t_id);
59 gwlarson 3.8
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 gwlarson 3.6 }
75 gwlarson 3.1
76 gwlarson 3.6
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 gwlarson 3.1 }
97    
98 gwlarson 3.7 /* 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 gwlarson 3.5 LIST
102 gwlarson 3.8 *smVertexPolygon(sm,id,del_ptr)
103 gwlarson 3.1 SM *sm;
104     int id;
105 gwlarson 3.8 LIST **del_ptr;
106 gwlarson 3.1 {
107     TRI *tri,*t_next;
108 gwlarson 3.5 LIST *elist,*end;
109 gwlarson 3.7 int e,t_id,v_next,t_next_id,b_id,v_id;
110 gwlarson 3.1
111 gwlarson 3.7 eClear_edges();
112 gwlarson 3.1 elist = end = NULL;
113 gwlarson 3.7
114 gwlarson 3.1 /* 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 gwlarson 3.7 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 gwlarson 3.6 SET_E_NTH_TRI(e,0,INVALID);
125 gwlarson 3.7 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 gwlarson 3.6 elist = add_data_to_circular_list(elist,&end,e);
129 gwlarson 3.1 t_next_id = t_id;
130     t_next = tri;
131    
132 gwlarson 3.8 *del_ptr = push_data(*del_ptr,t_id);
133 gwlarson 3.7 /* Create a set to hold all of the triangles for deletion later */
134 gwlarson 3.1
135 gwlarson 3.7 while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id)
136     {
137     e = eNew_edge();
138 gwlarson 3.6 t_next = SM_NTH_TRI(sm,t_next_id);
139 gwlarson 3.7 SET_E_NTH_VERT(e,0,v_next);
140 gwlarson 3.6 SET_E_NTH_TRI(e,0,INVALID);
141 gwlarson 3.7 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 gwlarson 3.6 elist = add_data_to_circular_list(elist,&end,e);
147 gwlarson 3.8 *del_ptr = push_data(*del_ptr,t_next_id);
148 gwlarson 3.1 }
149     return(elist);
150     }
151    
152 gwlarson 3.7
153 gwlarson 3.1 int
154 gwlarson 3.7 smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr)
155 gwlarson 3.1 SM *sm;
156 gwlarson 3.7 int id0,id1,id2,e0,e1,*e2ptr;
157 gwlarson 3.1 {
158 gwlarson 3.7 int t_id;
159     int e2;
160 gwlarson 3.1
161 gwlarson 3.7 #ifdef DEBUG
162     if(id0 == INVALID || id1==INVALID || id2==INVALID)
163     error(CONSISTENCY,"bad id- smTriangulate_add_tri()\n");
164 gwlarson 3.1 #endif
165 gwlarson 3.7 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 gwlarson 3.1
179 gwlarson 3.7 *e2ptr = e2;
180     return(t_id);
181 gwlarson 3.1 }
182    
183 gwlarson 3.3 int
184 gwlarson 3.7 smTriangulateConvex(sm,plist,add_ptr)
185 gwlarson 3.1 SM *sm;
186 gwlarson 3.5 LIST *plist,**add_ptr;
187 gwlarson 3.1 {
188     int t_id,e_id0,e_id1,e_id2;
189     int v_id0,v_id1,v_id2;
190     LIST *lptr;
191    
192     lptr = plist;
193     e_id0 = (int)LIST_DATA(lptr);
194     v_id0 = E_NTH_VERT(e_id0,0);
195     lptr = LIST_NEXT(lptr);
196     while(LIST_NEXT(lptr) != plist)
197     {
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);
201     lptr = LIST_NEXT(lptr);
202    
203 gwlarson 3.7 if(LIST_NEXT(lptr) != plist)
204     e_id2 = 0;
205 gwlarson 3.1 else
206     e_id2 = (int)LIST_DATA(lptr);
207 gwlarson 3.7 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 gwlarson 3.1 e_id0 = -e_id2;
210     }
211     free_list(plist);
212 gwlarson 3.3 return(TRUE);
213 gwlarson 3.1 }
214 gwlarson 3.7 #ifdef TEST_DRIVER
215     FVECT Norm[500],B_V[500];
216     int Ncnt,Bcnt,Del=0;
217 gwlarson 3.1 #endif
218    
219 gwlarson 3.6
220 gwlarson 3.7 /* 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 gwlarson 3.6
226     int
227 gwlarson 3.7 smTriangulate(sm,id,plist,add_ptr)
228 gwlarson 3.6 SM *sm;
229     int id;
230 gwlarson 3.5 LIST *plist,**add_ptr;
231 gwlarson 3.1 {
232 gwlarson 3.6 LIST *l,*prev,*t;
233     FVECT v0,v1,v2,n,p;
234 gwlarson 3.7 int is_tri,is_convex,cut,t_id,id0,id1,id2,e2,e1,enew;
235 gwlarson 3.6 double dp;
236 gwlarson 3.8 static int debug=0;
237 gwlarson 3.6
238 gwlarson 3.7 VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
239     enew = 0;
240     is_convex = TRUE;
241     cut = is_tri= FALSE;
242 gwlarson 3.6 l = prev = plist;
243 gwlarson 3.7
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 gwlarson 3.6 while(l)
258     {
259     l = LIST_NEXT(l);
260 gwlarson 3.7 /* Get v2 */
261 gwlarson 3.6 e2 = (int)LIST_DATA(l);
262     id2 = E_NTH_VERT(e2,1);
263 gwlarson 3.7 VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
264     #ifdef TEST_DRIVER
265     VCOPY(B_V[Bcnt++],v2);
266     #endif
267 gwlarson 3.6 if(LIST_NEXT(LIST_NEXT(l)) == prev)
268 gwlarson 3.7 {/* Check if have a triangle */
269     is_tri = TRUE;
270     break;
271     }
272    
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 gwlarson 3.6 {
278 gwlarson 3.7 /* 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 gwlarson 3.6 }
306 gwlarson 3.7 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 gwlarson 3.6 {
317 gwlarson 3.7 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 gwlarson 3.6 break;
325 gwlarson 3.7 if(!cut)
326     {
327     #ifdef DEBUG
328     eputs("smTriangulate():Unable to triangulate\n");
329     #endif
330 gwlarson 3.8 free_list(l);
331 gwlarson 3.7 while(*add_ptr)
332     {
333     t_id = pop_list(add_ptr);
334     smDelete_tri(sm,t_id);
335     }
336     return(FALSE);
337 gwlarson 3.8 }
338    
339 gwlarson 3.7 cut = FALSE;
340     is_convex = TRUE;
341 gwlarson 3.6 }
342 gwlarson 3.7 prev = l;
343 gwlarson 3.6 }
344     if(is_tri)
345     {
346     l = LIST_NEXT(l);
347 gwlarson 3.7 enew = (int)LIST_DATA(l);
348     t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
349 gwlarson 3.6 *add_ptr = push_data(*add_ptr,t_id);
350     free_list(l);
351 gwlarson 3.7 }
352 gwlarson 3.6 else
353 gwlarson 3.7 if(!smTriangulateConvex(sm,l,add_ptr))
354 gwlarson 3.6 return(FALSE);
355    
356 gwlarson 3.7 /* Set triangle adjacencies based on edge adjacencies */
357     FOR_ALL_EDGES(enew)
358 gwlarson 3.1 {
359 gwlarson 3.7 id0 = E_NTH_TRI(enew,0);
360     id1 = E_NTH_TRI(enew,1);
361 gwlarson 3.1
362 gwlarson 3.7 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 gwlarson 3.1 }
368 gwlarson 3.7 return(TRUE);
369 gwlarson 3.1 }
370    
371     eIn_tri(e,t)
372     int e;
373     TRI *t;
374     {
375    
376     if(T_NTH_V(t,0)==E_NTH_VERT(e,0))
377     return(T_NTH_V(t,1)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1));
378     else
379     if(T_NTH_V(t,1)==E_NTH_VERT(e,0))
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 gwlarson 3.7
384 gwlarson 3.1 return(FALSE);
385     }
386 gwlarson 3.6
387 gwlarson 3.7 /* 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 gwlarson 3.8 smFixEdges(sm,add_list)
394 gwlarson 3.1 SM *sm;
395 gwlarson 3.5 LIST *add_list;
396 gwlarson 3.1 {
397 gwlarson 3.6 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 gwlarson 3.1 FVECT v0,v1,v2,p,np,v;
400 gwlarson 3.7 TRI *t0,*t1;
401 gwlarson 3.5
402 gwlarson 3.1 FOR_ALL_EDGES(e)
403     {
404 gwlarson 3.6 t0_id = E_NTH_TRI(e,0);
405     t1_id = E_NTH_TRI(e,1);
406     if((t0_id==INVALID) || (t1_id==INVALID))
407 gwlarson 3.1 {
408     #ifdef DEBUG
409 gwlarson 3.7 error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n");
410 gwlarson 3.1 #endif
411     }
412 gwlarson 3.7 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 gwlarson 3.6 v0_id = E_NTH_VERT(e,0);
418     v1_id = E_NTH_VERT(e,1);
419 gwlarson 3.7 v2_id = T_NTH_V(t0,e0);
420     p_id = T_NTH_V(t1,e1);
421 gwlarson 3.1
422 gwlarson 3.6 smDir_in_cone(sm,v0,v0_id);
423     smDir_in_cone(sm,v1,v1_id);
424     smDir_in_cone(sm,v2,v2_id);
425 gwlarson 3.1
426 gwlarson 3.6 VCOPY(p,SM_NTH_WV(sm,p_id));
427 gwlarson 3.1 VSUB(p,p,SM_VIEW_CENTER(sm));
428     if(point_in_cone(p,v0,v1,v2))
429     {
430 gwlarson 3.8 smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list);
431 gwlarson 3.1
432 gwlarson 3.7 /* Adjust the triangle pointers of the remaining edges to be
433     processed
434     */
435 gwlarson 3.1 FOR_ALL_EDGES_FROM(e,i)
436     {
437 gwlarson 3.6 if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id)
438 gwlarson 3.1 {
439 gwlarson 3.6 if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
440     SET_E_NTH_TRI(i,0,t0_nid);
441 gwlarson 3.1 else
442 gwlarson 3.6 SET_E_NTH_TRI(i,0,t1_nid);
443 gwlarson 3.1 }
444    
445 gwlarson 3.6 if(E_NTH_TRI(i,1)==t0_id || E_NTH_TRI(i,1)==t1_id)
446 gwlarson 3.1 {
447 gwlarson 3.6 if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
448     SET_E_NTH_TRI(i,1,t0_nid);
449 gwlarson 3.1 else
450 gwlarson 3.6 SET_E_NTH_TRI(i,1,t1_nid);
451 gwlarson 3.1 }
452     }
453 gwlarson 3.6 t0_id = t0_nid;
454     t1_id = t1_nid;
455 gwlarson 3.1 e_new = eNew_edge();
456 gwlarson 3.6 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 gwlarson 3.1 }
461     }
462 gwlarson 3.7 /* Add/Delete the appropriate triangles from the stree */
463 gwlarson 3.8 smUpdate_locator(sm,add_list);
464 gwlarson 3.1 }
465    
466 gwlarson 3.7 /* Remove vertex "id" from the mesh- and retriangulate the resulting
467     hole: Returns TRUE if successful, FALSE otherwise.
468     */
469 gwlarson 3.1 int
470 gwlarson 3.7 smRemoveVertex(sm,id)
471 gwlarson 3.1 SM *sm;
472     int id;
473     {
474 gwlarson 3.8 LIST *b_list,*add_list,*del_list;
475     int t_id,i;
476     static int cnt=0;
477     OBJECT *optr,*os;
478 gwlarson 3.7 /* generate list of edges that form the boundary of the
479     polygon formed by the triangles adjacent to vertex 'id'
480 gwlarson 3.1 */
481 gwlarson 3.8 del_list = NULL;
482     b_list = smVertexPolygon(sm,id,&del_list);
483 gwlarson 3.6
484 gwlarson 3.5 add_list = NULL;
485 gwlarson 3.7 /* Triangulate polygonal hole */
486     if(!smTriangulate(sm,id,b_list,&add_list))
487 gwlarson 3.6 {
488 gwlarson 3.8 free_list(del_list);
489 gwlarson 3.6 return(FALSE);
490     }
491 gwlarson 3.8 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 gwlarson 3.7 /* 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 gwlarson 3.8 smFixEdges(sm,add_list);
512 gwlarson 3.7
513 gwlarson 3.1 return(TRUE);
514     }
515    
516    
517    
518 gwlarson 3.8
519 gwlarson 3.1
520    
521    
522    
523    
524    
525    
526    
527    
528    
529