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 |
|
12 |
#include "sm_list.h" |
13 |
#include "sm_geom.h" |
14 |
#include "sm.h" |
15 |
|
16 |
static EDGE Edges[MAX_EDGES]; |
17 |
static int Ecnt=0; |
18 |
|
19 |
int |
20 |
remove_tri(qtptr,fptr,t_id) |
21 |
QUADTREE *qtptr; |
22 |
int *fptr; |
23 |
int t_id; |
24 |
{ |
25 |
OBJECT tset[QT_MAXSET+1]; |
26 |
int n; |
27 |
|
28 |
if(QT_IS_EMPTY(*qtptr)) |
29 |
return(FALSE); |
30 |
/* remove id from set */ |
31 |
else |
32 |
{ |
33 |
if(!qtinset(*qtptr,t_id)) |
34 |
return(FALSE); |
35 |
n = QT_SET_CNT(qtqueryset(*qtptr))-1; |
36 |
*qtptr = qtdelelem(*qtptr,t_id); |
37 |
if(n == 0) |
38 |
(*fptr) |= QT_COMPRESS; |
39 |
if(!QT_FLAG_FILL_TRI(*fptr)) |
40 |
(*fptr)++; |
41 |
} |
42 |
return(TRUE); |
43 |
} |
44 |
|
45 |
int |
46 |
remove_tri_compress(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id) |
47 |
QUADTREE *qtptr; |
48 |
FVECT q0,q1,q2; |
49 |
FVECT t0,t1,t2; |
50 |
int n; |
51 |
int *arg; |
52 |
int t_id; |
53 |
{ |
54 |
int f = 0; |
55 |
/* NOTE compress */ |
56 |
return(remove_tri(qtptr,&f,t_id)); |
57 |
} |
58 |
|
59 |
|
60 |
|
61 |
int |
62 |
stDelete_tri(st,t_id,t0,t1,t2) |
63 |
STREE *st; |
64 |
int t_id; |
65 |
FVECT t0,t1,t2; |
66 |
{ |
67 |
int f; |
68 |
FVECT dir; |
69 |
|
70 |
/* First add all of the leaf cells lying on the triangle perimeter: |
71 |
mark all cells seen on the way |
72 |
*/ |
73 |
ST_CLEAR_FLAGS(st); |
74 |
f = 0; |
75 |
VSUB(dir,t1,t0); |
76 |
stTrace_edge(st,t0,dir,1.0,remove_tri,&f,t_id); |
77 |
VSUB(dir,t2,t1); |
78 |
stTrace_edge(st,t1,dir,1.0,remove_tri,&f,t_id); |
79 |
VSUB(dir,t0,t2); |
80 |
stTrace_edge(st,t2,dir,1.0,remove_tri,&f,t_id); |
81 |
/* Now visit interior */ |
82 |
if(QT_FLAG_FILL_TRI(f) || QT_FLAG_UPDATE(f)) |
83 |
stVisit_tri_interior(st,t0,t1,t2,remove_tri_compress,&f,t_id); |
84 |
} |
85 |
|
86 |
|
87 |
smLocator_remove_tri(sm,t_id) |
88 |
SM *sm; |
89 |
int t_id; |
90 |
{ |
91 |
STREE *st; |
92 |
char found; |
93 |
TRI *t; |
94 |
FVECT v0,v1,v2; |
95 |
|
96 |
st = SM_LOCATOR(sm); |
97 |
|
98 |
t = SM_NTH_TRI(sm,t_id); |
99 |
|
100 |
VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm)); |
101 |
VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm)); |
102 |
VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm)); |
103 |
found = stUpdate_tri(st,t_id,v0,v1,v2,remove_tri,remove_tri_compress); |
104 |
return(found); |
105 |
} |
106 |
|
107 |
smFree_tri(sm,id) |
108 |
SM *sm; |
109 |
int id; |
110 |
{ |
111 |
TRI *tri; |
112 |
|
113 |
tri = SM_NTH_TRI(sm,id); |
114 |
/* Add to the free_list */ |
115 |
T_NEXT_FREE(tri) = SM_FREE_TRIS(sm); |
116 |
SM_FREE_TRIS(sm) = id; |
117 |
T_VALID_FLAG(tri) = -1; |
118 |
} |
119 |
|
120 |
/* Assumes mesh pointers have been cleaned up appropriately: just deletes from |
121 |
Point location and triangle data structure |
122 |
*/ |
123 |
smDelete_tri(sm,t_id) |
124 |
SM *sm; |
125 |
int t_id; |
126 |
{ |
127 |
|
128 |
|
129 |
/* NOTE: Assumes that a new triangle adjacent to each vertex |
130 |
has been added- before the deletion: replacing |
131 |
the old tri- and therefore dont need to dereference any pointers |
132 |
to id because the vertices can no longer |
133 |
point to tri id as being the first triangle pointer |
134 |
*/ |
135 |
if(!SM_IS_NTH_T_BASE(sm,t_id)) |
136 |
{ |
137 |
SM_NUM_TRIS(sm)--; |
138 |
if(SM_IS_NTH_T_NEW(sm,t_id)) |
139 |
smNew_tri_cnt--; |
140 |
} |
141 |
smClear_tri_flags(sm,t_id); |
142 |
|
143 |
smFree_tri(sm,t_id); |
144 |
|
145 |
} |
146 |
|
147 |
|
148 |
|
149 |
LIST |
150 |
*smVertex_star_polygon(sm,id) |
151 |
SM *sm; |
152 |
int id; |
153 |
{ |
154 |
TRI *tri,*t_next; |
155 |
LIST *elist,*end,*tlist; |
156 |
int t_id,v_next,t_next_id; |
157 |
int e; |
158 |
|
159 |
elist = end = NULL; |
160 |
/* Get the first triangle adjacent to vertex id */ |
161 |
t_id = SM_NTH_VERT(sm,id); |
162 |
tri = SM_NTH_TRI(sm,t_id); |
163 |
|
164 |
|
165 |
if((e = eNew_edge()) == SM_INVALID) |
166 |
{ |
167 |
#ifdef DEBUG |
168 |
eputs("smVertex_star_polygon():Too many edges\n"); |
169 |
#endif |
170 |
return(NULL); |
171 |
} |
172 |
elist = add_data_to_circular_list(elist,&end,e); |
173 |
v_next = (T_WHICH_V(tri,id)+1)%3; |
174 |
SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next)); |
175 |
SET_E_NTH_TRI(e,0,SM_INVALID); |
176 |
SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next)); |
177 |
v_next = (T_WHICH_V(tri,id)+2)%3; |
178 |
SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next)); |
179 |
|
180 |
|
181 |
t_next_id = t_id; |
182 |
t_next = tri; |
183 |
|
184 |
tlist = push_data(NULL,t_id); |
185 |
|
186 |
while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id) |
187 |
{ |
188 |
if((e = eNew_edge()) == SM_INVALID) |
189 |
{ |
190 |
#ifdef DEBUG |
191 |
eputs("smVertex_star_polygon():Too many edges\n"); |
192 |
#endif |
193 |
return(NULL); |
194 |
} |
195 |
elist = add_data_to_circular_list(elist,&end,e); |
196 |
t_next = SM_NTH_TRI(sm,t_next_id); |
197 |
v_next = (T_WHICH_V(t_next,id)+1)%3; |
198 |
SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next)); |
199 |
SET_E_NTH_TRI(e,0,SM_INVALID); |
200 |
SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next)); |
201 |
v_next = (T_WHICH_V(t_next,id)+2)%3; |
202 |
SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next)); |
203 |
tlist = push_data(tlist,t_next_id); |
204 |
} |
205 |
while(tlist) |
206 |
{ |
207 |
t_id = (int)pop_list(&tlist); |
208 |
/* first remove from point location structure */ |
209 |
smLocator_remove_tri(sm,t_id); |
210 |
smDelete_tri(sm,t_id); |
211 |
} |
212 |
return(elist); |
213 |
} |
214 |
|
215 |
int |
216 |
smEdge_intersect_polygon(sm,v0,v1,l) |
217 |
SM *sm; |
218 |
FVECT v0,v1; |
219 |
LIST *l; |
220 |
{ |
221 |
FVECT e0,e1; |
222 |
int e,id_e0,id_e1; |
223 |
LIST *el,*eptr; |
224 |
|
225 |
/* Test the edges in l against v0v1 to see if v0v1 intersects |
226 |
any other edges |
227 |
*/ |
228 |
|
229 |
el = l; |
230 |
|
231 |
while(el) |
232 |
{ |
233 |
e = (int)LIST_DATA(el); |
234 |
id_e0 = E_NTH_VERT(e,0); |
235 |
id_e1 = E_NTH_VERT(e,1); |
236 |
/* NOTE: DO these need to be normalized? Just subtract center? */ |
237 |
/* |
238 |
smDir(sm,e0,id_e0); |
239 |
smDir(sm,e1,id_e1); |
240 |
*/ |
241 |
VSUB(e0,SM_NTH_WV(sm,id_e0),SM_VIEW_CENTER(sm)); |
242 |
VSUB(e1,SM_NTH_WV(sm,id_e1),SM_VIEW_CENTER(sm)); |
243 |
if(sedge_intersect(v0,v1,e0,e1)) |
244 |
return(TRUE); |
245 |
|
246 |
el = LIST_NEXT(el); |
247 |
if(el == l) |
248 |
break; |
249 |
} |
250 |
return(FALSE); |
251 |
} |
252 |
|
253 |
int |
254 |
smFind_next_convex_vertex(sm,id0,id1,v0,v1,l) |
255 |
SM *sm; |
256 |
int id0,id1; |
257 |
FVECT v0,v1; |
258 |
LIST *l; |
259 |
{ |
260 |
int e,id; |
261 |
LIST *el; |
262 |
FVECT v; |
263 |
|
264 |
/* starting with the end of edge at head of l, search sequentially for |
265 |
vertex v such that v0v1v is a convex angle, and the edge v1v does |
266 |
not intersect any other edges |
267 |
*/ |
268 |
id = SM_INVALID; |
269 |
el = l; |
270 |
while(id != id0) |
271 |
{ |
272 |
e = (int)LIST_DATA(el); |
273 |
id = E_NTH_VERT(e,1); |
274 |
|
275 |
smDir(sm,v,id); |
276 |
|
277 |
if(convex_angle(v0,v1,v) && !smEdge_intersect_polygon(sm,v1,v,l)) |
278 |
return(id); |
279 |
|
280 |
el = LIST_NEXT(el); |
281 |
if(el == l) |
282 |
break; |
283 |
} |
284 |
return(SM_INVALID); |
285 |
} |
286 |
|
287 |
int |
288 |
split_edge_list(id0,id_new,l,lnew) |
289 |
int id0,id_new; |
290 |
LIST **l,**lnew; |
291 |
{ |
292 |
LIST *list,*lptr,*end; |
293 |
int e,e1,e2,new_e; |
294 |
|
295 |
e2 = SM_INVALID; |
296 |
list = lptr = *l; |
297 |
|
298 |
if((new_e = eNew_edge())==SM_INVALID) |
299 |
{ |
300 |
#ifdef DEBUG |
301 |
eputs("split_edge_list():Too many edges\n"); |
302 |
#endif |
303 |
return(FALSE); |
304 |
} |
305 |
SET_E_NTH_VERT(new_e,0,id0); |
306 |
SET_E_NTH_VERT(new_e,1,id_new); |
307 |
SET_E_NTH_TRI(new_e,0,SM_INVALID); |
308 |
SET_E_NTH_TRI(new_e,1,SM_INVALID); |
309 |
|
310 |
while(e2 != id_new) |
311 |
{ |
312 |
lptr = LIST_NEXT(lptr); |
313 |
e = (int)LIST_DATA(lptr); |
314 |
e2 = E_NTH_VERT(e,1); |
315 |
if(lptr == list) |
316 |
{ |
317 |
#ifdef DEBUG |
318 |
eputs("split_edge_list():cant find vertex\n"); |
319 |
#endif |
320 |
*lnew = NULL; |
321 |
return(FALSE); |
322 |
} |
323 |
|
324 |
} |
325 |
end = lptr; |
326 |
lptr = LIST_NEXT(lptr); |
327 |
list = add_data_to_circular_list(list,&end,-new_e); |
328 |
*lnew = list; |
329 |
|
330 |
/* now follow other cycle */ |
331 |
|
332 |
list = lptr; |
333 |
e2 = SM_INVALID; |
334 |
while(e2 != id0) |
335 |
{ |
336 |
lptr = LIST_NEXT(lptr); |
337 |
e = (int)LIST_DATA(lptr); |
338 |
e2 = E_NTH_VERT(e,1); |
339 |
if(lptr == list) |
340 |
{ |
341 |
#ifdef DEBUG |
342 |
eputs("split_edge_list():cant find intial vertex\n"); |
343 |
#endif |
344 |
*l = NULL; |
345 |
return(FALSE); |
346 |
} |
347 |
|
348 |
} |
349 |
end = lptr; |
350 |
list = add_data_to_circular_list(list,&end,new_e); |
351 |
*l = list; |
352 |
return(TRUE); |
353 |
} |
354 |
|
355 |
|
356 |
int |
357 |
smTriangulate_convex(sm,plist) |
358 |
SM *sm; |
359 |
LIST *plist; |
360 |
{ |
361 |
TRI *tri; |
362 |
int t_id,e_id0,e_id1,e_id2; |
363 |
int v_id0,v_id1,v_id2; |
364 |
LIST *lptr; |
365 |
int cnt; |
366 |
|
367 |
lptr = plist; |
368 |
e_id0 = (int)LIST_DATA(lptr); |
369 |
v_id0 = E_NTH_VERT(e_id0,0); |
370 |
lptr = LIST_NEXT(lptr); |
371 |
while(LIST_NEXT(lptr) != plist) |
372 |
{ |
373 |
e_id1 = (int)LIST_DATA(lptr); |
374 |
v_id1 = E_NTH_VERT(e_id1,0); |
375 |
v_id2 = E_NTH_VERT(e_id1,1); |
376 |
/* form a triangle for each triple of with v0 as base of star */ |
377 |
t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri); |
378 |
smLocator_add_tri(sm,t_id,v_id0,v_id1,v_id2); |
379 |
/* add which pointer?*/ |
380 |
|
381 |
lptr = LIST_NEXT(lptr); |
382 |
|
383 |
if(LIST_NEXT(lptr) != plist) |
384 |
{ |
385 |
e_id2 = eNew_edge(); |
386 |
SET_E_NTH_VERT(e_id2,0,v_id2); |
387 |
SET_E_NTH_VERT(e_id2,1,v_id0); |
388 |
} |
389 |
else |
390 |
e_id2 = (int)LIST_DATA(lptr); |
391 |
|
392 |
/* set appropriate tri for each edge*/ |
393 |
SET_E_NTH_TRI(e_id0,0,t_id); |
394 |
SET_E_NTH_TRI(e_id1,0,t_id); |
395 |
SET_E_NTH_TRI(e_id2,0,t_id); |
396 |
|
397 |
e_id0 = -e_id2; |
398 |
} |
399 |
|
400 |
free_list(plist); |
401 |
return(TRUE); |
402 |
} |
403 |
int |
404 |
smTriangulate_elist(sm,plist) |
405 |
SM *sm; |
406 |
LIST *plist; |
407 |
{ |
408 |
LIST *l,*el1; |
409 |
FVECT v0,v1,v2; |
410 |
int id0,id1,id2,e,id_next; |
411 |
char flipped; |
412 |
int done; |
413 |
|
414 |
l = plist; |
415 |
|
416 |
while(l) |
417 |
{ |
418 |
/* get v0,v1,v2 */ |
419 |
e = (int)LIST_DATA(l); |
420 |
id0 = E_NTH_VERT(e,0); |
421 |
id1 = E_NTH_VERT(e,1); |
422 |
l = LIST_NEXT(l); |
423 |
e = (int)LIST_DATA(l); |
424 |
id2 = E_NTH_VERT(e,1); |
425 |
|
426 |
smDir(sm,v0,id0); |
427 |
smDir(sm,v1,id1); |
428 |
smDir(sm,v2,id2); |
429 |
/* determine if convex (left turn), or concave(right turn) angle */ |
430 |
if(convex_angle(v0,v1,v2)) |
431 |
{ |
432 |
if(l == plist) |
433 |
break; |
434 |
else |
435 |
continue; |
436 |
} |
437 |
/* if concave: add edge and recurse on two sub polygons */ |
438 |
id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l)); |
439 |
if(id_next == SM_INVALID) |
440 |
{ |
441 |
#ifdef DEBUG |
442 |
eputs("smTriangulate_elist():Unable to find convex vertex\n"); |
443 |
#endif |
444 |
return(FALSE); |
445 |
} |
446 |
/* add edge */ |
447 |
el1 = NULL; |
448 |
/* Split edge list l into two lists: one from id1-id_next-id1, |
449 |
and the next from id2-id_next-id2 |
450 |
*/ |
451 |
split_edge_list(id1,id_next,&l,&el1); |
452 |
/* Recurse and triangulate the two edge lists */ |
453 |
done = smTriangulate_elist(sm,l); |
454 |
if(done) |
455 |
done = smTriangulate_elist(sm,el1); |
456 |
return(done); |
457 |
} |
458 |
done = smTriangulate_convex(sm,plist); |
459 |
return(done); |
460 |
} |
461 |
|
462 |
int |
463 |
smTriangulate(sm,plist) |
464 |
SM *sm; |
465 |
LIST *plist; |
466 |
{ |
467 |
int e,id_t0,id_t1,e0,e1; |
468 |
TRI *t0,*t1; |
469 |
int test; |
470 |
|
471 |
test = smTriangulate_elist(sm,plist); |
472 |
|
473 |
if(!test) |
474 |
return(test); |
475 |
FOR_ALL_EDGES(e) |
476 |
{ |
477 |
id_t0 = E_NTH_TRI(e,0); |
478 |
id_t1 = E_NTH_TRI(e,1); |
479 |
if((id_t0==SM_INVALID) || (id_t1==SM_INVALID)) |
480 |
{ |
481 |
#ifdef DEBUG |
482 |
eputs("smTriangulate(): Unassigned edge neighbor\n"); |
483 |
#endif |
484 |
continue; |
485 |
} |
486 |
t0 = SM_NTH_TRI(sm,id_t0); |
487 |
t1 = SM_NTH_TRI(sm,id_t1); |
488 |
|
489 |
e0 = T_WHICH_V(t0,E_NTH_VERT(e,0)); |
490 |
T_NTH_NBR(t0,e0) = id_t1; |
491 |
|
492 |
e1 = T_WHICH_V(t1,E_NTH_VERT(e,1)); |
493 |
T_NTH_NBR(t1,e1) = id_t0; |
494 |
} |
495 |
return(test); |
496 |
} |
497 |
|
498 |
eIn_tri(e,t) |
499 |
int e; |
500 |
TRI *t; |
501 |
{ |
502 |
|
503 |
if(T_NTH_V(t,0)==E_NTH_VERT(e,0)) |
504 |
return(T_NTH_V(t,1)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1)); |
505 |
else |
506 |
if(T_NTH_V(t,1)==E_NTH_VERT(e,0)) |
507 |
return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1)); |
508 |
else if(T_NTH_V(t,2)==E_NTH_VERT(e,0)) |
509 |
return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1)); |
510 |
return(FALSE); |
511 |
} |
512 |
smFix_edges(sm) |
513 |
SM *sm; |
514 |
{ |
515 |
int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next; |
516 |
TRI *t0,*t1,*nt0,*nt1; |
517 |
int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1; |
518 |
FVECT v0,v1,v2,p,np,v; |
519 |
LIST *add,*del; |
520 |
|
521 |
add = del = NULL; |
522 |
FOR_ALL_EDGES(e) |
523 |
{ |
524 |
id_t0 = E_NTH_TRI(e,0); |
525 |
id_t1 = E_NTH_TRI(e,1); |
526 |
if((id_t0==SM_INVALID) || (id_t1==SM_INVALID)) |
527 |
{ |
528 |
#ifdef DEBUG |
529 |
eputs("smFix_edges: Unassigned edge nbr\n"); |
530 |
#endif |
531 |
continue; |
532 |
} |
533 |
t0 = SM_NTH_TRI(sm,id_t0); |
534 |
t1 = SM_NTH_TRI(sm,id_t1); |
535 |
|
536 |
e0 = T_WHICH_V(t0,E_NTH_VERT(e,0)); |
537 |
e1 = T_WHICH_V(t1,E_NTH_VERT(-e,0)); |
538 |
e0_next = (e0+2)%3; |
539 |
e1_next = (e1+2)%3; |
540 |
id_v0 = E_NTH_VERT(e,0); |
541 |
id_v1 = E_NTH_VERT(e,1); |
542 |
id_v2 = T_NTH_V(t0,e0_next); |
543 |
id_p = T_NTH_V(t1,e1_next); |
544 |
|
545 |
smDir(sm,v0,id_v0); |
546 |
smDir(sm,v1,id_v1); |
547 |
smDir(sm,v2,id_v2); |
548 |
|
549 |
VCOPY(p,SM_NTH_WV(sm,id_p)); |
550 |
VSUB(p,p,SM_VIEW_CENTER(sm)); |
551 |
if(point_in_cone(p,v0,v1,v2)) |
552 |
{ |
553 |
smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add,&del); |
554 |
|
555 |
nt0 = SM_NTH_TRI(sm,nid_t0); |
556 |
nt1 = SM_NTH_TRI(sm,nid_t1); |
557 |
FOR_ALL_EDGES_FROM(e,i) |
558 |
{ |
559 |
if(E_NTH_TRI(i,0)==id_t0 || E_NTH_TRI(i,0)==id_t1) |
560 |
{ |
561 |
if(eIn_tri(i,nt0)) |
562 |
SET_E_NTH_TRI(i,0,nid_t0); |
563 |
else |
564 |
SET_E_NTH_TRI(i,0,nid_t1); |
565 |
} |
566 |
|
567 |
if(E_NTH_TRI(i,1)==id_t0 || E_NTH_TRI(i,1)==id_t1) |
568 |
{ |
569 |
if(eIn_tri(i,nt0)) |
570 |
SET_E_NTH_TRI(i,1,nid_t0); |
571 |
else |
572 |
SET_E_NTH_TRI(i,1,nid_t1); |
573 |
} |
574 |
} |
575 |
id_t0 = nid_t0; |
576 |
id_t1 = nid_t1; |
577 |
e_new = eNew_edge(); |
578 |
SET_E_NTH_VERT(e_new,0,id_p); |
579 |
SET_E_NTH_VERT(e_new,1,id_v2); |
580 |
SET_E_NTH_TRI(e_new,0,id_t0); |
581 |
SET_E_NTH_TRI(e_new,1,id_t1); |
582 |
} |
583 |
} |
584 |
smUpdate_locator(sm,add,del); |
585 |
} |
586 |
|
587 |
int |
588 |
smMesh_remove_vertex(sm,id) |
589 |
SM *sm; |
590 |
int id; |
591 |
{ |
592 |
int tri; |
593 |
LIST *elist; |
594 |
int cnt,debug; |
595 |
/* generate list of vertices that form the boundary of the |
596 |
star polygon formed by vertex id and all of its adjacent |
597 |
triangles |
598 |
*/ |
599 |
eClear_edges(); |
600 |
elist = smVertex_star_polygon(sm,id); |
601 |
if(!elist) |
602 |
return(FALSE); |
603 |
|
604 |
/* Triangulate spherical polygon */ |
605 |
smTriangulate(sm,elist); |
606 |
|
607 |
|
608 |
/* Fix up new triangles to be Delaunay */ |
609 |
smFix_edges(sm); |
610 |
|
611 |
return(TRUE); |
612 |
} |
613 |
|
614 |
/* Remove point from samples, and from mesh. Delete any triangles |
615 |
adjacent to the point and re-triangulate the hole |
616 |
Return TRUE is point found , FALSE otherwise |
617 |
*/ |
618 |
int |
619 |
smDelete_point(sm,id) |
620 |
SM *sm; |
621 |
int id; |
622 |
{ |
623 |
|
624 |
/* Remove the corresponding vertex from the mesh */ |
625 |
smMesh_remove_vertex(sm,id); |
626 |
/* Free the sample point */ |
627 |
smDelete_sample(sm,id); |
628 |
return(TRUE); |
629 |
} |
630 |
|
631 |
|
632 |
|
633 |
|
634 |
|
635 |
|
636 |
|
637 |
|
638 |
|
639 |
|
640 |
|
641 |
|
642 |
|
643 |
|