ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_del.c
Revision: 3.14
Committed: Wed Apr 23 00:52:34 2003 UTC (20 years, 11 months ago) by greg
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R6P1, rad3R6
Changes since 3.13: +1 -1 lines
Log Message:
Added (void *) cast to realloc calls

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id$";
3 #endif
4 /*
5 * sm_del.c
6 */
7 #include "standard.h"
8 #include "sm_flag.h"
9 #include "sm_list.h"
10 #include "sm_geom.h"
11 #include "sm.h"
12
13 #define MAX_EDGE_INIT 100
14 static int Max_edges= MAX_EDGE_INIT;
15 static EDGE *Edges=NULL;
16 static int Ecnt=0;
17
18 smFree_tri(sm,id,t)
19 SM *sm;
20 int id;
21 TRI *t;
22 {
23 /* Add to the free_list */
24 T_NEXT_FREE(t) = SM_FREE_TRIS(sm);
25 SM_FREE_TRIS(sm) = id;
26 #ifdef DEBUG
27 T_VALID_FLAG(t) = INVALID;
28 #endif
29 }
30
31 /* Assumes mesh pointers have been cleaned up appropriately: just deletes from
32 Point location and triangle data structure
33 */
34 smDelete_tri(sm,t_id,t)
35 SM *sm;
36 int t_id;
37 TRI *t;
38 {
39
40 /* NOTE: Assumes that a new triangle adjacent to each vertex
41 has been added- before the deletion: replacing
42 the old tri- and therefore dont need to dereference any pointers
43 to id because the vertices can no longer
44 point to tri id as being the first triangle pointer
45 */
46 SM_CLR_NTH_T_ACTIVE(sm,t_id);
47 smFree_tri(sm,t_id,t);
48
49 }
50
51 int
52 eNew_edge()
53 {
54 if(!Edges)
55 if(!(Edges = (EDGE *)realloc(NULL,(Max_edges+1)*sizeof(EDGE))))
56 goto memerr;
57
58 if(Ecnt >= Max_edges)
59 {
60 #ifdef DEBUG
61 if(Max_edges > 10000)
62 error(CONSISTENCY,"Too many edges in vertex loop\n");
63 #endif
64 Max_edges += 100;
65 if(!(Edges = (EDGE *)realloc((void *)Edges,(Max_edges+1)*sizeof(EDGE))))
66 goto memerr;
67 }
68 #ifdef DEBUG
69 SET_E_NTH_TRI(Ecnt+1,0,INVALID);
70 SET_E_NTH_TRI(Ecnt+1,1,INVALID);
71 #endif
72 return(++Ecnt);
73
74 memerr:
75 error(SYSTEM,"eNew_edge): Unable to allocate memory");
76 }
77
78 /* Return list of edges defining polygon formed by boundary of triangles
79 adjacent to id. Return set of triangles adjacent to id to delete in delptr
80 */
81 LIST
82 *smVertexStar(sm,id)
83 SM *sm;
84 S_ID id;
85 {
86 TRI *tri,*t_next;
87 LIST *elist,*end;
88 int e,t_id,t_next_id,b_id,v_id,t_last_id;
89 S_ID v_next;
90
91 elist = end = NULL;
92
93 /* Get the first triangle adjacent to vertex id */
94 t_id = SM_NTH_VERT(sm,id);
95 tri = SM_NTH_TRI(sm,t_id);
96
97 e = eNew_edge();
98 /* Get the next vertex on the polygon boundary */
99 v_id = T_WHICH_V(tri,id);
100 b_id = (v_id + 1)%3;
101 /* Create an edge */
102 SET_E_NTH_VERT(e,0,T_NTH_V(tri,b_id));
103 SET_E_NTH_TRI(e,0,INVALID);
104 SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_id));
105 v_next = T_NTH_V(tri,(b_id+1)%3);
106 SET_E_NTH_VERT(e,1,v_next);
107
108 elist = add_data_to_circular_list(elist,&end,e);
109 t_next_id = t_id;
110 t_next = tri;
111 t_last_id = -1;
112
113 /* Create a set to hold all of the triangles for deletion later */
114
115 while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id)
116 {
117 e = eNew_edge();
118 if(t_last_id != -1)
119 {
120 smDelete_tri(sm,t_last_id,t_next);
121 }
122 t_next = SM_NTH_TRI(sm,t_next_id);
123 t_last_id = t_next_id;
124 SET_E_NTH_VERT(e,0,v_next);
125 SET_E_NTH_TRI(e,0,INVALID);
126 v_id = T_WHICH_V(t_next,id);
127 b_id = (v_id + 1)%3;
128 SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_id));
129 v_next = T_NTH_V(t_next,(b_id+1)%3);
130 SET_E_NTH_VERT(e,1,v_next);
131 elist = add_data_to_circular_list(elist,&end,e);
132
133 }
134 smDelete_tri(sm,t_last_id,t_next);
135 smDelete_tri(sm,t_id,tri);
136 return(elist);
137 }
138
139 int
140 smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr)
141 SM *sm;
142 S_ID id0,id1,id2;
143 int e0,e1,*e2ptr;
144 {
145 int t_id,e2;
146 TRI *t;
147
148 t_id = smAdd_tri(sm,id0,id1,id2,&t);
149 if(*e2ptr == 0)
150 {
151 e2 = eNew_edge();
152 SET_E_NTH_VERT(e2,0,id2);
153 SET_E_NTH_VERT(e2,1,id0);
154 }
155 else
156 e2 = *e2ptr;
157 /* set appropriate tri for each edge*/
158 SET_E_NTH_TRI(e0,0,t_id);
159 SET_E_NTH_TRI(e1,0,t_id);
160 SET_E_NTH_TRI(e2,0,t_id);
161 #ifdef DEBUG
162 #if DEBUG > 1
163 if(E_NTH_TRI(e0,1) == E_NTH_TRI(e0,0) ||
164 E_NTH_TRI(e1,1) == E_NTH_TRI(e1,0) ||
165 E_NTH_TRI(e2,1) == E_NTH_TRI(e2,0))
166 error(CONSISTENCY,"Non manifold\n");
167 #endif
168 #endif
169 *e2ptr = e2;
170 return(t_id);
171
172 }
173
174 int
175 smTriangulate_quad(sm,l)
176 SM *sm;
177 LIST *l;
178 {
179 int e1,e2,e3,e4,e,t_id;
180 S_ID id0,id1,id2,id3;
181 FVECT v0,v1,v2,v3,n;
182 double dp;
183 TRI *tri;
184 LIST *lptr;
185
186 #ifdef DEBUG
187 if(LIST_NEXT(LIST_NEXT(LIST_NEXT(LIST_NEXT(l)))) != l)
188 {
189 eputs("smTriangulate_quad(): not a quadrilateral\n");
190 return(FALSE);
191 }
192 eputs("smTriangulate_quad():\n");
193 #endif
194 lptr=l;
195 e1 = (int)LIST_DATA(l);
196 id0 = E_NTH_VERT(e1,0);
197 id1 = E_NTH_VERT(e1,1);
198 VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm));
199 VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm));
200 /* Get v2 */
201 l = LIST_NEXT(l);
202 e2 = (int)LIST_DATA(l);
203 id2 = E_NTH_VERT(e2,1);
204 VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
205 /* Get v3 */
206 l = LIST_NEXT(l);
207 e3 = (int)LIST_DATA(l);
208 id3 = E_NTH_VERT(e3,1);
209 VSUB(v3,SM_NTH_WV(sm,id3),SM_VIEW_CENTER(sm));
210 l = LIST_NEXT(l);
211 e4 = (int)LIST_DATA(l);
212 free_list(lptr);
213
214 VCROSS(n,v0,v2);
215 normalize(n);
216 normalize(v1);
217 dp = DOT(n,v1);
218 e = 0;
219 if(dp > 0)
220 {
221 if(dp >= EV_EPS)
222 {
223 normalize(v3);
224 if(DOT(n,v3) < 0)
225 {
226 t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&e);
227 e *= -1;
228 t_id = smTriangulate_add_tri(sm,id2,id3,id0,e3,e4,&e);
229 return(TRUE);
230 }
231 }
232
233 }
234 #ifdef DEBUG
235 #if DEBUG > 1
236 VCROSS(n,v1,v3);
237 normalize(n);
238 normalize(v0);
239 normalize(v2);
240 dp = DOT(n,v2);
241 if((dp < 0) || (dp < EV_EPS) || (DOT(n,v0) >= 0.0))
242 error(CONSISTENCY,"smTriangulate_quad: cannot triangulate\n");
243 #endif
244 #endif
245 t_id = smTriangulate_add_tri(sm,id1,id2,id3,e2,e3,&e);
246 e *= -1;
247 t_id = smTriangulate_add_tri(sm,id3,id0,id1,e4,e1,&e);
248 return(TRUE);
249 }
250
251 eIn_tri(e,t)
252 int e;
253 TRI *t;
254 {
255
256 if(T_NTH_V(t,0)==E_NTH_VERT(e,0))
257 return(T_NTH_V(t,1)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1));
258 else
259 if(T_NTH_V(t,1)==E_NTH_VERT(e,0))
260 return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1));
261 else if(T_NTH_V(t,2)==E_NTH_VERT(e,0))
262 return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1));
263
264 return(FALSE);
265 }
266
267
268 /* Triangulate the polygon defined by plist, and generating vertex p_id.
269 Return list of added triangles in list add_ptr. Returns TRUE if
270 successful, FALSE otherwise. This is NOT a general triangulation routine,
271 assumes polygon star relative to id
272 */
273
274 int
275 smTriangulate(sm,id,plist)
276 SM *sm;
277 S_ID id;
278 LIST *plist;
279 {
280 LIST *l,*prev,*t;
281 FVECT v0,v1,v2,n,p;
282 int is_tri,cut,t_id,e2,e1,enew;
283 S_ID id0,id1,id2;
284 double dp1,dp2;
285
286 VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
287 normalize(p);
288 l = plist;
289
290 enew = 0;
291 cut = is_tri= FALSE;
292 prev = l;
293 /* get v0,v1 */
294 e1 = (int)LIST_DATA(l);
295 id0 = E_NTH_VERT(e1,0);
296 id1 = E_NTH_VERT(e1,1);
297 VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm));
298 normalize(v0);
299 VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm));
300 normalize(v1);
301 while(l)
302 {
303 l = LIST_NEXT(l);
304 /* Get v2 */
305 e2 = (int)LIST_DATA(l);
306 id2 = E_NTH_VERT(e2,1);
307 VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm));
308 normalize(v2);
309 if(LIST_NEXT(LIST_NEXT(l)) == prev)
310 {/* Check if have a triangle */
311 is_tri = TRUE;
312 break;
313 }
314 /* determine if v0-v1-v2 is convex:defined clockwise on the sphere-
315 so switch orientation
316 */
317 VCROSS(n,v0,v2);
318 normalize(n);
319 dp1 = DOT(n,p);
320 if(dp1 <= 0.0)
321 {
322 /* test if safe to cut off v0-v1-v2 by testing if p lies outside of
323 triangle v0-v1-v2: if so, because plist is the star polygon around p,
324 the new edge v2-v0 cannot intersect any existing edges
325 */
326 dp1 = DOT(n,v1);
327 /* Distance from point s to plane is d = |N.p0s|/||N|| */
328 /* sp1 = s-p0 for point on plane p0, a.(b+c) = a.b + a.c */
329 if(dp1 >= EV_EPS)
330 {
331 /* remove edges e1,e2 and add triangle id0,id1,id2 */
332 enew = 0;
333 t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew);
334 cut = TRUE;
335 /* Insert edge enew into the list, reuse prev list element */
336 LIST_NEXT(prev) = LIST_NEXT(l);
337 LIST_DATA(prev) = e1 = -enew;
338 /* If removing head of list- reset plist pointer */
339 if(l== plist)
340 plist = prev;
341 /* free list element for e2 */
342 LIST_NEXT(l)=NULL;
343 free_list(l);
344 l = prev;
345 VCOPY(v1,v2);
346 id1 = id2;
347 continue;
348 }
349 }
350 VCOPY(v0,v1);
351 VCOPY(v1,v2);
352 id0 = id1;
353 id1 = id2;
354 e1 = e2;
355 /* check if gone around circular list without adding any
356 triangles: prevent infinite loop */
357 if(l == plist)
358 {
359 if(LIST_NEXT(LIST_NEXT(l)) == prev)
360 {/* Check if have a triangle */
361 is_tri = TRUE;
362 break;
363 }
364 if(!cut)
365 break;
366 cut = FALSE;
367 }
368 prev = l;
369 }
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 free_list(l);
376 }
377 else
378 if(!smTriangulate_quad(sm,l))
379 goto Terror;
380 /* Set triangle adjacencies based on edge adjacencies */
381 FOR_ALL_EDGES(enew)
382 {
383 id0 = E_NTH_TRI(enew,0);
384 id1 = E_NTH_TRI(enew,1);
385
386 e1 = (T_WHICH_V(SM_NTH_TRI(sm,id0),E_NTH_VERT(enew,0))+2)%3;
387 T_NTH_NBR(SM_NTH_TRI(sm,id0),e1) = id1;
388
389 e2 = (T_WHICH_V(SM_NTH_TRI(sm,id1),E_NTH_VERT(enew,1))+2)%3;
390 T_NTH_NBR(SM_NTH_TRI(sm,id1),e2) = id0;
391 }
392
393 #ifdef DEBUG
394 #if DEBUG > 1
395 {
396 TRI *t0,*t1,*n;
397
398 FOR_ALL_EDGES(enew)
399 {
400 id0 = E_NTH_TRI(enew,0);
401 id1 = E_NTH_TRI(enew,1);
402 t0 = SM_NTH_TRI(sm,id0);
403 t1 = SM_NTH_TRI(sm,id1);
404 if(T_NTH_NBR(t0,0) == T_NTH_NBR(t0,1) ||
405 T_NTH_NBR(t0,1) == T_NTH_NBR(t0,2) ||
406 T_NTH_NBR(t0,0) == T_NTH_NBR(t0,2))
407 error(CONSISTENCY,"Invalid topology\n");
408 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,0))) ||
409 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,1))) ||
410 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t0,2))))
411 error(CONSISTENCY,"Invalid topology\n");
412 n = SM_NTH_TRI(sm,T_NTH_NBR(t0,0));
413 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
414 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
415 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
416 error(CONSISTENCY,"Invalid topology\n");
417 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
418 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
419 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
420 error(CONSISTENCY,"Invalid topology\n");
421 n = SM_NTH_TRI(sm,T_NTH_NBR(t0,1));
422 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
423 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
424 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
425 error(CONSISTENCY,"Invalid topology\n");
426 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
427 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
428 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
429 error(CONSISTENCY,"Invalid topology\n");
430 n = SM_NTH_TRI(sm,T_NTH_NBR(t0,2));
431 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
432 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
433 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
434 error(CONSISTENCY,"Invalid topology\n");
435 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
436 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
437 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
438 error(CONSISTENCY,"Invalid topology\n");
439
440 if(T_NTH_NBR(t1,0) == T_NTH_NBR(t1,1) ||
441 T_NTH_NBR(t1,1) == T_NTH_NBR(t1,2) ||
442 T_NTH_NBR(t1,0) == T_NTH_NBR(t1,2))
443 error(CONSISTENCY,"Invalid topology\n");
444 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,0))) ||
445 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,1))) ||
446 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(t1,2))))
447 error(CONSISTENCY,"Invalid topology\n");
448 n = SM_NTH_TRI(sm,T_NTH_NBR(t1,0));
449 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
450 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
451 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
452 error(CONSISTENCY,"Invalid topology\n");
453 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
454 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
455 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
456 error(CONSISTENCY,"Invalid topology\n");
457 n = SM_NTH_TRI(sm,T_NTH_NBR(t1,1));
458 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
459 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
460 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
461 error(CONSISTENCY,"Invalid topology\n");
462 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
463 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
464 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
465 error(CONSISTENCY,"Invalid topology\n");
466 n = SM_NTH_TRI(sm,T_NTH_NBR(t1,2));
467 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
468 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
469 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
470 error(CONSISTENCY,"Invalid topology\n");
471 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
472 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
473 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
474 error(CONSISTENCY,"Invalid topology\n");
475 }
476
477 }
478 #endif
479 #endif
480
481 return(TRUE);
482
483 Terror:
484
485 error(CONSISTENCY,"smTriangulate():Unable to triangulate\n");
486
487 }
488
489
490 void
491 smTris_swap_edge(sm,t_id,t1_id,e,e1,tn_id,tn1_id)
492 SM *sm;
493 int t_id,t1_id;
494 int e,e1;
495 int *tn_id,*tn1_id;
496 {
497 S_ID verts[3];
498 int enext,eprev,e1next,e1prev;
499 TRI *n,*ta,*tb,*t,*t1;
500 FVECT p1,p2,p3;
501 int ta_id,tb_id;
502 /* form new diagonal (e relative to t, and e1 relative to t1)
503 defined by quadrilateral formed by t,t1- swap for the opposite diagonal
504 */
505 t = SM_NTH_TRI(sm,t_id);
506 t1 = SM_NTH_TRI(sm,t1_id);
507 enext = (e+1)%3;
508 eprev = (e+2)%3;
509 e1next = (e1+1)%3;
510 e1prev = (e1+2)%3;
511 verts[e] = T_NTH_V(t,e);
512 verts[enext] = T_NTH_V(t,enext);
513 verts[eprev] = T_NTH_V(t1,e1);
514 ta_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&ta);
515 #if 0
516 fprintf(stderr,"Added tri %d %d %d %d\n",ta_id,T_NTH_V(ta,0),
517 T_NTH_V(ta,1), T_NTH_V(ta,2));
518 #endif
519 verts[e1] = T_NTH_V(t1,e1);
520 verts[e1next] = T_NTH_V(t1,e1next);
521 verts[e1prev] = T_NTH_V(t,e);
522 tb_id = smAdd_tri(sm,verts[0],verts[1],verts[2],&tb);
523 #if 0
524 fprintf(stderr,"Added tri %d %d %d %d\n",tb_id,T_NTH_V(tb,0),
525 T_NTH_V(tb,1), T_NTH_V(tb,2));
526 #endif
527 /* set the neighbors */
528 T_NTH_NBR(ta,e) = T_NTH_NBR(t1,e1next);
529 T_NTH_NBR(tb,e1) = T_NTH_NBR(t,enext);
530 T_NTH_NBR(ta,enext)= tb_id;
531 T_NTH_NBR(tb,e1next)= ta_id;
532 T_NTH_NBR(ta,eprev)=T_NTH_NBR(t,eprev);
533 T_NTH_NBR(tb,e1prev)=T_NTH_NBR(t1,e1prev);
534
535 /* Reset neighbor pointers of original neighbors */
536 n = SM_NTH_TRI(sm,T_NTH_NBR(t,enext));
537 T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = tb_id;
538 n = SM_NTH_TRI(sm,T_NTH_NBR(t,eprev));
539 T_NTH_NBR(n,T_NTH_NBR_PTR(t_id,n)) = ta_id;
540 n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1next));
541 T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = ta_id;
542 n = SM_NTH_TRI(sm,T_NTH_NBR(t1,e1prev));
543 T_NTH_NBR(n,T_NTH_NBR_PTR(t1_id,n)) = tb_id;
544
545 smDelete_tri(sm,t_id,t);
546 smDelete_tri(sm,t1_id,t1);
547
548 #ifdef DEBUG
549 #if DEBUG > 1
550 if(T_NTH_NBR(ta,0) == T_NTH_NBR(ta,1) ||
551 T_NTH_NBR(ta,1) == T_NTH_NBR(ta,2) ||
552 T_NTH_NBR(ta,0) == T_NTH_NBR(ta,2))
553 error(CONSISTENCY,"Invalid topology\n");
554 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,0))) ||
555 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,1))) ||
556 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(ta,2))))
557 error(CONSISTENCY,"Invalid topology\n");
558 n = SM_NTH_TRI(sm,T_NTH_NBR(ta,0));
559 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
560 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
561 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
562 error(CONSISTENCY,"Invalid topology\n");
563 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
564 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
565 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
566 error(CONSISTENCY,"Invalid topology\n");
567 n = SM_NTH_TRI(sm,T_NTH_NBR(ta,1));
568 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
569 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
570 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
571 error(CONSISTENCY,"Invalid topology\n");
572 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
573 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
574 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
575 error(CONSISTENCY,"Invalid topology\n");
576 n = SM_NTH_TRI(sm,T_NTH_NBR(ta,2));
577 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
578 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
579 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
580 error(CONSISTENCY,"Invalid topology\n");
581 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
582 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
583 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
584 error(CONSISTENCY,"Invalid topology\n");
585 if(T_NTH_NBR(ta,0) == T_NTH_NBR(ta,1) ||
586 T_NTH_NBR(ta,1) == T_NTH_NBR(ta,2) ||
587 T_NTH_NBR(ta,0) == T_NTH_NBR(ta,2))
588 error(CONSISTENCY,"Invalid topology\n");
589
590 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,0))) ||
591 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,1))) ||
592 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(tb,2))))
593 error(CONSISTENCY,"Invalid topology\n");
594 n = SM_NTH_TRI(sm,T_NTH_NBR(tb,0));
595 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
596 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
597 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
598 error(CONSISTENCY,"Invalid topology\n");
599 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
600 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
601 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
602 error(CONSISTENCY,"Invalid topology\n");
603 n = SM_NTH_TRI(sm,T_NTH_NBR(tb,1));
604 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
605 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
606 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
607 error(CONSISTENCY,"Invalid topology\n");
608 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
609 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
610 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
611 error(CONSISTENCY,"Invalid topology\n");
612 n = SM_NTH_TRI(sm,T_NTH_NBR(tb,2));
613 if(T_NTH_NBR(n,0) == T_NTH_NBR(n,1) ||
614 T_NTH_NBR(n,1) == T_NTH_NBR(n,2) ||
615 T_NTH_NBR(n,0) == T_NTH_NBR(n,2))
616 error(CONSISTENCY,"Invalid topology\n");
617 if(!T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,0))) ||
618 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,1))) ||
619 !T_IS_VALID(SM_NTH_TRI(sm,T_NTH_NBR(n,2))))
620 error(CONSISTENCY,"Invalid topology\n");
621 #endif
622 #endif
623 *tn_id = ta_id;
624 *tn1_id = tb_id;
625
626 return;
627 }
628
629 /* Test the new set of triangles for Delaunay condition. 'Edges' contains
630 all of the new edges added. The CCW triangle assoc with each edge is
631 tested against the opposite vertex of the CW triangle. If the vertex
632 lies inside the circle defined by the CCW triangle- the edge is swapped
633 for the opposite diagonal
634 */
635 smFixEdges(sm)
636 SM *sm;
637 {
638 int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next;
639 S_ID v0_id,v1_id,v2_id,p_id;
640 int i,t0_nid,t1_nid;
641 FVECT v0,v1,v2,p,np,v;
642 TRI *t0,*t1;
643
644 FOR_ALL_EDGES(e)
645 {
646 t0_id = E_NTH_TRI(e,0);
647 t1_id = E_NTH_TRI(e,1);
648 #ifdef DEBUG
649 if((t0_id==INVALID) || (t1_id==INVALID))
650 error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n");
651 #endif
652 t0 = SM_NTH_TRI(sm,t0_id);
653 t1 = SM_NTH_TRI(sm,t1_id);
654 e0 = T_NTH_NBR_PTR(t1_id,t0);
655 e1 = T_NTH_NBR_PTR(t0_id,t1);
656
657 v0_id = E_NTH_VERT(e,0);
658 v1_id = E_NTH_VERT(e,1);
659 v2_id = T_NTH_V(t0,e0);
660 p_id = T_NTH_V(t1,e1);
661
662 smDir(sm,v0,v0_id);
663 smDir(sm,v1,v1_id);
664 smDir(sm,v2,v2_id);
665
666 VSUB(p,SM_NTH_WV(sm,p_id),SM_VIEW_CENTER(sm));
667 normalize(p);
668 if(pt_in_cone(p,v2,v1,v0))
669 {
670 smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid);
671 /* Adjust the triangle pointers of the remaining edges to be
672 processed
673 */
674 FOR_ALL_EDGES_FROM(e,i)
675 {
676 if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id)
677 {
678 if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
679 SET_E_NTH_TRI(i,0,t0_nid);
680 else
681 SET_E_NTH_TRI(i,0,t1_nid);
682 }
683
684 if(E_NTH_TRI(i,1)==t0_id || E_NTH_TRI(i,1)==t1_id)
685 {
686 if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid)))
687 SET_E_NTH_TRI(i,1,t0_nid);
688 else
689 SET_E_NTH_TRI(i,1,t1_nid);
690 }
691 #ifdef DEBUG
692 if(E_NTH_TRI(i,1) == E_NTH_TRI(i,0) )
693 error(CONSISTENCY,"invalid edge\n");
694 #endif
695 }
696 t0_id = t0_nid;
697 t1_id = t1_nid;
698 e_new = eNew_edge();
699 SET_E_NTH_VERT(e_new,0,p_id);
700 SET_E_NTH_VERT(e_new,1,v2_id);
701 SET_E_NTH_TRI(e_new,0,t0_id);
702 SET_E_NTH_TRI(e_new,1,t1_id);
703 #ifdef DEBUG
704 if(E_NTH_TRI(i,1) == E_NTH_TRI(i,0) )
705 error(CONSISTENCY,"invalid edge\n");
706 #endif
707 }
708 }
709 }
710
711
712 smDelete_samp(sm,s_id)
713 SM *sm;
714 S_ID s_id;
715 {
716 QUADTREE qt;
717 S_ID *os;
718
719 /* Mark as free */
720 smUnalloc_samp(sm,s_id);
721
722 #ifdef DEBUG
723 SM_NTH_VERT(sm,s_id) = INVALID;
724 /* fprintf(stderr,"deleting sample %d\n",s_id); */
725 #endif
726 /* remove from its set */
727 qt = SM_S_NTH_QT(sm,s_id);
728 os = qtqueryset(qt);
729 deletuelem(os, s_id); /* delete obj from unsorted os, no questions */
730 }
731 /* Remove vertex "id" from the mesh- and retriangulate the resulting
732 hole: Returns TRUE if successful, FALSE otherwise.
733 */
734 int
735 smRemoveVertex(sm,id)
736 SM *sm;
737 S_ID id;
738 {
739 LIST *b_list;
740 /* generate list of edges that form the boundary of the
741 polygon formed by the triangles adjacent to vertex 'id'*/
742 b_list = smVertexStar(sm,id);
743 #if 0
744 {int i;
745 eputs("\n\n");
746 for(i=1;i<=Ecnt;i++)
747 fprintf(stderr,"%d verts %d %d tris %d %d\n",
748 i,Edges[i].verts[0],Edges[i].verts[1],
749 Edges[i].tris[0],Edges[i].tris[1]);
750 }
751 #endif
752
753 /* Triangulate polygonal hole */
754 smTriangulate(sm,id,b_list);
755
756 /* Fix up new triangles to be Delaunay*/
757
758 smFixEdges(sm);
759 smDelete_samp(sm,id);
760 eClear_edges();
761 return(TRUE);
762 }
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777