ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_del.c
Revision: 3.9
Committed: Tue Jan 5 16:52:37 1999 UTC (25 years, 3 months ago) by gwlarson
Content type: text/plain
Branch: MAIN
Changes since 3.8: +4 -16 lines
Log Message:
fixed logic in smTest to handle nearby and coincident points, added base tris to rendering, made list of new triangles to speed up rendering

File Contents

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