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 |
|
|
|
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 |
|
|
|
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 |
|
|
|
42 |
|
|
smFree_tri(sm,id) |
43 |
|
|
SM *sm; |
44 |
|
|
int id; |
45 |
|
|
{ |
46 |
|
|
TRI *tri; |
47 |
|
|
|
48 |
|
|
tri = SM_NTH_TRI(sm,id); |
49 |
|
|
/* Add to the free_list */ |
50 |
|
|
T_NEXT_FREE(tri) = SM_FREE_TRIS(sm); |
51 |
|
|
SM_FREE_TRIS(sm) = id; |
52 |
|
|
T_VALID_FLAG(tri) = -1; |
53 |
|
|
} |
54 |
|
|
|
55 |
|
|
/* Assumes mesh pointers have been cleaned up appropriately: just deletes from |
56 |
|
|
Point location and triangle data structure |
57 |
|
|
*/ |
58 |
|
|
smDelete_tri(sm,t_id) |
59 |
|
|
SM *sm; |
60 |
|
|
int t_id; |
61 |
|
|
{ |
62 |
|
|
|
63 |
|
|
|
64 |
|
|
/* NOTE: Assumes that a new triangle adjacent to each vertex |
65 |
|
|
has been added- before the deletion: replacing |
66 |
|
|
the old tri- and therefore dont need to dereference any pointers |
67 |
|
|
to id because the vertices can no longer |
68 |
|
|
point to tri id as being the first triangle pointer |
69 |
|
|
*/ |
70 |
|
|
if(!SM_IS_NTH_T_BASE(sm,t_id)) |
71 |
|
|
{ |
72 |
|
|
SM_NUM_TRIS(sm)--; |
73 |
|
|
if(SM_IS_NTH_T_NEW(sm,t_id)) |
74 |
|
|
smNew_tri_cnt--; |
75 |
|
|
} |
76 |
|
|
smClear_tri_flags(sm,t_id); |
77 |
|
|
|
78 |
|
|
smFree_tri(sm,t_id); |
79 |
|
|
|
80 |
|
|
} |
81 |
|
|
|
82 |
|
|
|
83 |
|
|
|
84 |
|
|
LIST |
85 |
|
|
*smVertex_star_polygon(sm,id) |
86 |
|
|
SM *sm; |
87 |
|
|
int id; |
88 |
|
|
{ |
89 |
|
|
TRI *tri,*t_next; |
90 |
|
|
LIST *elist,*end,*tlist; |
91 |
|
|
int t_id,v_next,t_next_id; |
92 |
|
|
int e; |
93 |
|
|
|
94 |
|
|
elist = end = NULL; |
95 |
|
|
/* Get the first triangle adjacent to vertex id */ |
96 |
|
|
t_id = SM_NTH_VERT(sm,id); |
97 |
|
|
tri = SM_NTH_TRI(sm,t_id); |
98 |
|
|
|
99 |
|
|
|
100 |
|
|
if((e = eNew_edge()) == SM_INVALID) |
101 |
|
|
{ |
102 |
|
|
#ifdef DEBUG |
103 |
|
|
eputs("smVertex_star_polygon():Too many edges\n"); |
104 |
|
|
#endif |
105 |
|
|
return(NULL); |
106 |
|
|
} |
107 |
|
|
elist = add_data_to_circular_list(elist,&end,e); |
108 |
|
|
v_next = (T_WHICH_V(tri,id)+1)%3; |
109 |
|
|
SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next)); |
110 |
|
|
SET_E_NTH_TRI(e,0,SM_INVALID); |
111 |
|
|
SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next)); |
112 |
|
|
v_next = (T_WHICH_V(tri,id)+2)%3; |
113 |
|
|
SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next)); |
114 |
|
|
|
115 |
|
|
|
116 |
|
|
t_next_id = t_id; |
117 |
|
|
t_next = tri; |
118 |
|
|
|
119 |
|
|
tlist = push_data(NULL,t_id); |
120 |
|
|
|
121 |
|
|
while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id) |
122 |
|
|
{ |
123 |
|
|
if((e = eNew_edge()) == SM_INVALID) |
124 |
|
|
{ |
125 |
|
|
#ifdef DEBUG |
126 |
|
|
eputs("smVertex_star_polygon():Too many edges\n"); |
127 |
|
|
#endif |
128 |
|
|
return(NULL); |
129 |
|
|
} |
130 |
|
|
elist = add_data_to_circular_list(elist,&end,e); |
131 |
|
|
t_next = SM_NTH_TRI(sm,t_next_id); |
132 |
|
|
v_next = (T_WHICH_V(t_next,id)+1)%3; |
133 |
|
|
SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next)); |
134 |
|
|
SET_E_NTH_TRI(e,0,SM_INVALID); |
135 |
|
|
SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next)); |
136 |
|
|
v_next = (T_WHICH_V(t_next,id)+2)%3; |
137 |
|
|
SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next)); |
138 |
|
|
tlist = push_data(tlist,t_next_id); |
139 |
|
|
} |
140 |
|
|
while(tlist) |
141 |
|
|
{ |
142 |
|
|
t_id = (int)pop_list(&tlist); |
143 |
gwlarson |
3.2 |
/* first remove from point location structure */ |
144 |
|
|
smLocator_remove_tri(sm,t_id); |
145 |
gwlarson |
3.1 |
smDelete_tri(sm,t_id); |
146 |
|
|
} |
147 |
|
|
return(elist); |
148 |
|
|
} |
149 |
|
|
|
150 |
|
|
int |
151 |
|
|
smEdge_intersect_polygon(sm,v0,v1,l) |
152 |
|
|
SM *sm; |
153 |
|
|
FVECT v0,v1; |
154 |
|
|
LIST *l; |
155 |
|
|
{ |
156 |
|
|
FVECT e0,e1; |
157 |
|
|
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; |
165 |
|
|
|
166 |
|
|
while(el) |
167 |
|
|
{ |
168 |
|
|
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"); |
233 |
|
|
#endif |
234 |
|
|
return(FALSE); |
235 |
|
|
} |
236 |
|
|
SET_E_NTH_VERT(new_e,0,id0); |
237 |
|
|
SET_E_NTH_VERT(new_e,1,id_new); |
238 |
|
|
SET_E_NTH_TRI(new_e,0,SM_INVALID); |
239 |
|
|
SET_E_NTH_TRI(new_e,1,SM_INVALID); |
240 |
|
|
|
241 |
|
|
while(e2 != id_new) |
242 |
|
|
{ |
243 |
|
|
lptr = LIST_NEXT(lptr); |
244 |
|
|
e = (int)LIST_DATA(lptr); |
245 |
|
|
e2 = E_NTH_VERT(e,1); |
246 |
|
|
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 |
|
|
} |
254 |
|
|
|
255 |
|
|
} |
256 |
|
|
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); |
284 |
|
|
} |
285 |
|
|
|
286 |
|
|
|
287 |
|
|
|
288 |
|
|
LIST |
289 |
|
|
*smTriangulate_convex(sm,plist) |
290 |
|
|
SM *sm; |
291 |
|
|
LIST *plist; |
292 |
|
|
{ |
293 |
|
|
TRI *tri; |
294 |
|
|
int t_id,e_id0,e_id1,e_id2; |
295 |
|
|
int v_id0,v_id1,v_id2; |
296 |
|
|
LIST *lptr; |
297 |
|
|
int cnt; |
298 |
|
|
|
299 |
|
|
lptr = plist; |
300 |
|
|
e_id0 = (int)LIST_DATA(lptr); |
301 |
|
|
v_id0 = E_NTH_VERT(e_id0,0); |
302 |
|
|
lptr = LIST_NEXT(lptr); |
303 |
|
|
while(LIST_NEXT(lptr) != plist) |
304 |
|
|
{ |
305 |
|
|
e_id1 = (int)LIST_DATA(lptr); |
306 |
|
|
v_id1 = E_NTH_VERT(e_id1,0); |
307 |
|
|
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 |
gwlarson |
3.2 |
smLocator_add_tri(sm,t_id,v_id0,v_id1,v_id2); |
311 |
gwlarson |
3.1 |
/* add which pointer?*/ |
312 |
|
|
|
313 |
|
|
lptr = LIST_NEXT(lptr); |
314 |
|
|
|
315 |
|
|
if(LIST_NEXT(lptr) != plist) |
316 |
|
|
{ |
317 |
|
|
e_id2 = eNew_edge(); |
318 |
|
|
SET_E_NTH_VERT(e_id2,0,v_id2); |
319 |
|
|
SET_E_NTH_VERT(e_id2,1,v_id0); |
320 |
|
|
} |
321 |
|
|
else |
322 |
|
|
e_id2 = (int)LIST_DATA(lptr); |
323 |
|
|
|
324 |
|
|
/* set appropriate tri for each edge*/ |
325 |
|
|
SET_E_NTH_TRI(e_id0,0,t_id); |
326 |
|
|
SET_E_NTH_TRI(e_id1,0,t_id); |
327 |
|
|
SET_E_NTH_TRI(e_id2,0,t_id); |
328 |
|
|
|
329 |
|
|
e_id0 = -e_id2; |
330 |
|
|
} |
331 |
|
|
free_list(plist); |
332 |
|
|
} |
333 |
|
|
|
334 |
|
|
smTriangulate_elist(sm,plist) |
335 |
|
|
SM *sm; |
336 |
|
|
LIST *plist; |
337 |
|
|
{ |
338 |
|
|
LIST *l,*el1; |
339 |
|
|
FVECT v0,v1,v2; |
340 |
|
|
int id0,id1,id2,e,id_next; |
341 |
|
|
char flipped; |
342 |
|
|
int debug = TRUE; |
343 |
|
|
|
344 |
|
|
l = plist; |
345 |
|
|
|
346 |
|
|
while(l) |
347 |
|
|
{ |
348 |
|
|
/* get v0,v1,v2 */ |
349 |
|
|
e = (int)LIST_DATA(l); |
350 |
|
|
id0 = E_NTH_VERT(e,0); |
351 |
|
|
id1 = E_NTH_VERT(e,1); |
352 |
|
|
l = LIST_NEXT(l); |
353 |
|
|
e = (int)LIST_DATA(l); |
354 |
|
|
id2 = E_NTH_VERT(e,1); |
355 |
|
|
|
356 |
|
|
smDir(sm,v0,id0); |
357 |
|
|
smDir(sm,v1,id1); |
358 |
|
|
smDir(sm,v2,id2); |
359 |
|
|
/* determine if convex (left turn), or concave(right turn) angle */ |
360 |
|
|
if(convex_angle(v0,v1,v2)) |
361 |
|
|
{ |
362 |
|
|
if(l == plist) |
363 |
|
|
break; |
364 |
|
|
else |
365 |
|
|
continue; |
366 |
|
|
} |
367 |
|
|
/* if concave: add edge and recurse on two sub polygons */ |
368 |
|
|
id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l)); |
369 |
|
|
if(id_next == SM_INVALID) |
370 |
|
|
{ |
371 |
|
|
#ifdef DEBUG |
372 |
|
|
eputs("smTriangulate_elist():Unable to find convex vertex\n"); |
373 |
|
|
#endif |
374 |
|
|
return; |
375 |
|
|
} |
376 |
|
|
/* add edge */ |
377 |
|
|
el1 = NULL; |
378 |
|
|
/* Split edge list l into two lists: one from id1-id_next-id1, |
379 |
|
|
and the next from id2-id_next-id2 |
380 |
|
|
*/ |
381 |
|
|
debug = split_edge_list(id1,id_next,&l,&el1); |
382 |
|
|
/* Recurse and triangulate the two edge lists */ |
383 |
|
|
if(debug) |
384 |
|
|
debug = smTriangulate_elist(sm,l); |
385 |
|
|
if(debug) |
386 |
|
|
debug = smTriangulate_elist(sm,el1); |
387 |
|
|
|
388 |
|
|
return(debug); |
389 |
|
|
} |
390 |
|
|
smTriangulate_convex(sm,plist); |
391 |
|
|
return(TRUE); |
392 |
|
|
} |
393 |
|
|
|
394 |
|
|
int |
395 |
|
|
smTriangulate_polygon(sm,plist) |
396 |
|
|
SM *sm; |
397 |
|
|
LIST *plist; |
398 |
|
|
{ |
399 |
|
|
int e,id_t0,id_t1,e0,e1; |
400 |
|
|
TRI *t0,*t1; |
401 |
|
|
int test; |
402 |
|
|
|
403 |
|
|
test = smTriangulate_elist(sm,plist,NULL); |
404 |
|
|
|
405 |
|
|
if(!test) |
406 |
|
|
return(test); |
407 |
|
|
FOR_ALL_EDGES(e) |
408 |
|
|
{ |
409 |
|
|
id_t0 = E_NTH_TRI(e,0); |
410 |
|
|
id_t1 = E_NTH_TRI(e,1); |
411 |
|
|
if((id_t0==SM_INVALID) || (id_t1==SM_INVALID)) |
412 |
|
|
{ |
413 |
|
|
#ifdef DEBUG |
414 |
|
|
eputs("smTriangulate_polygon(): Unassigned edge neighbor\n"); |
415 |
|
|
#endif |
416 |
|
|
continue; |
417 |
|
|
} |
418 |
|
|
t0 = SM_NTH_TRI(sm,id_t0); |
419 |
|
|
t1 = SM_NTH_TRI(sm,id_t1); |
420 |
|
|
|
421 |
|
|
e0 = T_WHICH_V(t0,E_NTH_VERT(e,0)); |
422 |
|
|
T_NTH_NBR(t0,e0) = id_t1; |
423 |
|
|
|
424 |
|
|
e1 = T_WHICH_V(t1,E_NTH_VERT(e,1)); |
425 |
|
|
T_NTH_NBR(t1,e1) = id_t0; |
426 |
|
|
} |
427 |
|
|
return(test); |
428 |
|
|
} |
429 |
|
|
|
430 |
|
|
eIn_tri(e,t) |
431 |
|
|
int e; |
432 |
|
|
TRI *t; |
433 |
|
|
{ |
434 |
|
|
|
435 |
|
|
if(T_NTH_V(t,0)==E_NTH_VERT(e,0)) |
436 |
|
|
return(T_NTH_V(t,1)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1)); |
437 |
|
|
else |
438 |
|
|
if(T_NTH_V(t,1)==E_NTH_VERT(e,0)) |
439 |
|
|
return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1)); |
440 |
|
|
else if(T_NTH_V(t,2)==E_NTH_VERT(e,0)) |
441 |
|
|
return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1)); |
442 |
|
|
return(FALSE); |
443 |
|
|
} |
444 |
|
|
smFix_edges(sm) |
445 |
|
|
SM *sm; |
446 |
|
|
{ |
447 |
|
|
int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next; |
448 |
|
|
TRI *t0,*t1,*nt0,*nt1; |
449 |
|
|
int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1; |
450 |
|
|
FVECT v0,v1,v2,p,np,v; |
451 |
gwlarson |
3.2 |
LIST *add,*del; |
452 |
|
|
|
453 |
|
|
add = del = NULL; |
454 |
gwlarson |
3.1 |
FOR_ALL_EDGES(e) |
455 |
|
|
{ |
456 |
|
|
id_t0 = E_NTH_TRI(e,0); |
457 |
|
|
id_t1 = E_NTH_TRI(e,1); |
458 |
|
|
if((id_t0==SM_INVALID) || (id_t1==SM_INVALID)) |
459 |
|
|
{ |
460 |
|
|
#ifdef DEBUG |
461 |
|
|
eputs("smFix_edges: Unassigned edge nbr\n"); |
462 |
|
|
#endif |
463 |
|
|
continue; |
464 |
|
|
} |
465 |
|
|
t0 = SM_NTH_TRI(sm,id_t0); |
466 |
|
|
t1 = SM_NTH_TRI(sm,id_t1); |
467 |
|
|
|
468 |
|
|
e0 = T_WHICH_V(t0,E_NTH_VERT(e,0)); |
469 |
|
|
e1 = T_WHICH_V(t1,E_NTH_VERT(-e,0)); |
470 |
|
|
e0_next = (e0+2)%3; |
471 |
|
|
e1_next = (e1+2)%3; |
472 |
|
|
id_v0 = E_NTH_VERT(e,0); |
473 |
|
|
id_v1 = E_NTH_VERT(e,1); |
474 |
|
|
id_v2 = T_NTH_V(t0,e0_next); |
475 |
|
|
id_p = T_NTH_V(t1,e1_next); |
476 |
|
|
|
477 |
|
|
smDir(sm,v0,id_v0); |
478 |
|
|
smDir(sm,v1,id_v1); |
479 |
|
|
smDir(sm,v2,id_v2); |
480 |
|
|
|
481 |
|
|
VCOPY(p,SM_NTH_WV(sm,id_p)); |
482 |
|
|
VSUB(p,p,SM_VIEW_CENTER(sm)); |
483 |
|
|
if(point_in_cone(p,v0,v1,v2)) |
484 |
|
|
{ |
485 |
gwlarson |
3.2 |
smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add,&del); |
486 |
gwlarson |
3.1 |
|
487 |
|
|
nt0 = SM_NTH_TRI(sm,nid_t0); |
488 |
|
|
nt1 = SM_NTH_TRI(sm,nid_t1); |
489 |
|
|
FOR_ALL_EDGES_FROM(e,i) |
490 |
|
|
{ |
491 |
|
|
if(E_NTH_TRI(i,0)==id_t0 || E_NTH_TRI(i,0)==id_t1) |
492 |
|
|
{ |
493 |
|
|
if(eIn_tri(i,nt0)) |
494 |
|
|
SET_E_NTH_TRI(i,0,nid_t0); |
495 |
|
|
else |
496 |
|
|
SET_E_NTH_TRI(i,0,nid_t1); |
497 |
|
|
} |
498 |
|
|
|
499 |
|
|
if(E_NTH_TRI(i,1)==id_t0 || E_NTH_TRI(i,1)==id_t1) |
500 |
|
|
{ |
501 |
|
|
if(eIn_tri(i,nt0)) |
502 |
|
|
SET_E_NTH_TRI(i,1,nid_t0); |
503 |
|
|
else |
504 |
|
|
SET_E_NTH_TRI(i,1,nid_t1); |
505 |
|
|
} |
506 |
|
|
} |
507 |
|
|
id_t0 = nid_t0; |
508 |
|
|
id_t1 = nid_t1; |
509 |
|
|
e_new = eNew_edge(); |
510 |
|
|
SET_E_NTH_VERT(e_new,0,id_p); |
511 |
|
|
SET_E_NTH_VERT(e_new,1,id_v2); |
512 |
|
|
SET_E_NTH_TRI(e_new,0,id_t0); |
513 |
|
|
SET_E_NTH_TRI(e_new,1,id_t1); |
514 |
|
|
} |
515 |
|
|
} |
516 |
gwlarson |
3.2 |
smUpdate_locator(sm,add,del); |
517 |
gwlarson |
3.1 |
} |
518 |
|
|
|
519 |
|
|
int |
520 |
|
|
smMesh_remove_vertex(sm,id) |
521 |
|
|
SM *sm; |
522 |
|
|
int id; |
523 |
|
|
{ |
524 |
|
|
int tri; |
525 |
|
|
LIST *elist; |
526 |
|
|
int cnt,debug; |
527 |
|
|
/* generate list of vertices that form the boundary of the |
528 |
|
|
star polygon formed by vertex id and all of its adjacent |
529 |
|
|
triangles |
530 |
|
|
*/ |
531 |
|
|
eClear_edges(); |
532 |
|
|
elist = smVertex_star_polygon(sm,id); |
533 |
|
|
if(!elist) |
534 |
|
|
return(FALSE); |
535 |
|
|
|
536 |
|
|
/* Triangulate spherical polygon */ |
537 |
|
|
debug = smTriangulate_polygon(sm,elist); |
538 |
|
|
|
539 |
|
|
|
540 |
|
|
/* Fix up new triangles to be Delaunay */ |
541 |
|
|
if(debug) |
542 |
|
|
smFix_edges(sm); |
543 |
|
|
|
544 |
|
|
return(TRUE); |
545 |
|
|
} |
546 |
|
|
|
547 |
|
|
/* Remove point from samples, and from mesh. Delete any triangles |
548 |
|
|
adjacent to the point and re-triangulate the hole |
549 |
|
|
Return TRUE is point found , FALSE otherwise |
550 |
|
|
*/ |
551 |
|
|
int |
552 |
|
|
smDelete_point(sm,id) |
553 |
|
|
SM *sm; |
554 |
|
|
int id; |
555 |
|
|
{ |
556 |
|
|
|
557 |
|
|
/* Remove the corresponding vertex from the mesh */ |
558 |
|
|
smMesh_remove_vertex(sm,id); |
559 |
|
|
/* Free the sample point */ |
560 |
|
|
smDelete_sample(sm,id); |
561 |
|
|
return(TRUE); |
562 |
|
|
} |
563 |
|
|
|
564 |
|
|
|
565 |
|
|
|
566 |
|
|
|
567 |
|
|
|
568 |
|
|
|
569 |
|
|
|
570 |
|
|
|
571 |
|
|
|
572 |
|
|
|
573 |
|
|
|
574 |
|
|
|
575 |
|
|
|
576 |
|
|
|