8 |
|
* sm_del.c |
9 |
|
*/ |
10 |
|
#include "standard.h" |
11 |
< |
|
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 EDGE Edges[MAX_EDGES]; |
18 |
> |
static int Max_edges=200; |
19 |
> |
static EDGE *Edges=NULL; |
20 |
|
static int Ecnt=0; |
21 |
|
|
22 |
< |
int |
23 |
< |
remove_tri(qtptr,fptr,t_id) |
22 |
> |
#define remove_tri_compress remove_tri |
23 |
> |
remove_tri(qtptr,fptr,tptr) |
24 |
|
QUADTREE *qtptr; |
25 |
|
int *fptr; |
26 |
< |
int t_id; |
26 |
> |
int *tptr; |
27 |
|
{ |
28 |
|
int n; |
29 |
|
|
30 |
< |
if(QT_IS_EMPTY(*qtptr)) |
31 |
< |
return(FALSE); |
32 |
< |
/* remove id from set */ |
33 |
< |
else |
31 |
< |
{ |
32 |
< |
if(!qtinset(*qtptr,t_id)) |
33 |
< |
return(FALSE); |
34 |
< |
n = QT_SET_CNT(qtqueryset(*qtptr))-1; |
35 |
< |
*qtptr = qtdelelem(*qtptr,t_id); |
36 |
< |
if(n == 0) |
37 |
< |
(*fptr) |= QT_COMPRESS; |
38 |
< |
if(!QT_FLAG_FILL_TRI(*fptr)) |
39 |
< |
(*fptr)++; |
40 |
< |
} |
41 |
< |
return(TRUE); |
42 |
< |
} |
30 |
> |
if(QT_IS_EMPTY(*qtptr)) |
31 |
> |
return; |
32 |
> |
if(QT_LEAF_IS_FLAG(*qtptr)) |
33 |
> |
return; |
34 |
|
|
35 |
< |
int |
36 |
< |
remove_tri_compress(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id) |
37 |
< |
QUADTREE *qtptr; |
38 |
< |
FVECT q0,q1,q2; |
39 |
< |
FVECT t0,t1,t2; |
40 |
< |
int n; |
50 |
< |
int *arg; |
51 |
< |
int t_id; |
52 |
< |
{ |
53 |
< |
int f = 0; |
54 |
< |
/* NOTE compress */ |
55 |
< |
return(remove_tri(qtptr,&f,t_id)); |
35 |
> |
n = QT_SET_CNT(qtqueryset(*qtptr))-1; |
36 |
> |
*qtptr = qtdelelem(*qtptr,*tptr); |
37 |
> |
if(n == 0) |
38 |
> |
(*fptr) |= QT_COMPRESS; |
39 |
> |
if(!QT_FLAG_FILL_TRI(*fptr)) |
40 |
> |
(*fptr)++; |
41 |
|
} |
42 |
|
|
43 |
|
|
44 |
< |
smLocator_remove_tri(sm,t_id) |
44 |
> |
smLocator_remove_tri(sm,t_id,v0_id,v1_id,v2_id) |
45 |
|
SM *sm; |
46 |
|
int t_id; |
47 |
+ |
int v0_id,v1_id,v2_id; |
48 |
|
{ |
49 |
|
STREE *st; |
64 |
– |
TRI *t; |
50 |
|
FVECT v0,v1,v2; |
51 |
< |
|
51 |
> |
|
52 |
|
st = SM_LOCATOR(sm); |
53 |
|
|
54 |
< |
t = SM_NTH_TRI(sm,t_id); |
54 |
> |
VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm)); |
55 |
> |
VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm)); |
56 |
> |
VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm)); |
57 |
|
|
58 |
< |
VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm)); |
59 |
< |
VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm)); |
60 |
< |
VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm)); |
61 |
< |
stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,t_id,NULL); |
58 |
> |
qtClearAllFlags(); |
59 |
> |
|
60 |
> |
stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,&t_id); |
61 |
> |
|
62 |
|
} |
63 |
|
|
64 |
|
smFree_tri(sm,id) |
82 |
|
int t_id; |
83 |
|
{ |
84 |
|
|
98 |
– |
|
85 |
|
/* NOTE: Assumes that a new triangle adjacent to each vertex |
86 |
|
has been added- before the deletion: replacing |
87 |
|
the old tri- and therefore dont need to dereference any pointers |
90 |
|
*/ |
91 |
|
if(!SM_IS_NTH_T_BASE(sm,t_id)) |
92 |
|
{ |
93 |
< |
SM_NUM_TRIS(sm)--; |
93 |
> |
SM_SAMPLE_TRIS(sm)--; |
94 |
|
if(SM_IS_NTH_T_NEW(sm,t_id)) |
95 |
|
smNew_tri_cnt--; |
96 |
|
} |
97 |
|
smClear_tri_flags(sm,t_id); |
98 |
|
|
99 |
|
smFree_tri(sm,t_id); |
114 |
– |
|
100 |
|
} |
101 |
|
|
102 |
|
|
103 |
+ |
int |
104 |
+ |
eNew_edge() |
105 |
+ |
{ |
106 |
+ |
if(!Edges) |
107 |
+ |
if(!(Edges = (EDGE *)realloc(NULL,(Max_edges+1)*sizeof(EDGE)))) |
108 |
+ |
goto memerr; |
109 |
+ |
|
110 |
+ |
if(Ecnt >= Max_edges) |
111 |
+ |
{ |
112 |
+ |
if(Max_edges > 10000) |
113 |
+ |
error(CONSISTENCY,"Too many edges in vertex loop\n"); |
114 |
+ |
Max_edges += 100; |
115 |
+ |
if(!(Edges = (EDGE *)realloc(Edges,(Max_edges+1)*sizeof(EDGE)))) |
116 |
+ |
goto memerr; |
117 |
+ |
} |
118 |
+ |
return(++Ecnt); |
119 |
+ |
|
120 |
+ |
memerr: |
121 |
+ |
error(SYSTEM,"eNew_edge(): Unable to allocate memory"); |
122 |
+ |
} |
123 |
+ |
|
124 |
|
LIST |
125 |
< |
*smVertex_star_polygon(sm,id,del_set) |
125 |
> |
*smVertex_star_polygon(sm,id,delptr) |
126 |
|
SM *sm; |
127 |
|
int id; |
128 |
< |
OBJECT *del_set; |
128 |
> |
QUADTREE *delptr; |
129 |
|
{ |
130 |
|
TRI *tri,*t_next; |
131 |
|
LIST *elist,*end; |
132 |
|
int t_id,v_next,t_next_id; |
133 |
|
int e; |
134 |
+ |
OBJECT del_set[2]; |
135 |
|
|
136 |
|
elist = end = NULL; |
137 |
|
/* Get the first triangle adjacent to vertex id */ |
138 |
|
t_id = SM_NTH_VERT(sm,id); |
139 |
|
tri = SM_NTH_TRI(sm,t_id); |
140 |
|
|
141 |
< |
|
142 |
< |
if((e = eNew_edge()) == SM_INVALID) |
143 |
< |
{ |
137 |
< |
#ifdef DEBUG |
138 |
< |
eputs("smVertex_star_polygon():Too many edges\n"); |
139 |
< |
#endif |
140 |
< |
return(NULL); |
141 |
< |
} |
142 |
< |
elist = add_data_to_circular_list(elist,&end,e); |
141 |
> |
if((e = eNew_edge()) == INVALID) |
142 |
> |
return(NULL); |
143 |
> |
|
144 |
|
v_next = (T_WHICH_V(tri,id)+1)%3; |
145 |
|
SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next)); |
146 |
< |
SET_E_NTH_TRI(e,0,SM_INVALID); |
146 |
> |
SET_E_NTH_TRI(e,0,INVALID); |
147 |
|
SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next)); |
148 |
|
v_next = (T_WHICH_V(tri,id)+2)%3; |
149 |
|
SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next)); |
150 |
+ |
elist = add_data_to_circular_list(elist,&end,e); |
151 |
|
|
150 |
– |
|
152 |
|
t_next_id = t_id; |
153 |
|
t_next = tri; |
154 |
|
|
155 |
< |
insertelem(del_set,t_id); |
155 |
> |
del_set[0] =1; del_set[1] = t_id; |
156 |
> |
*delptr = qtnewleaf(del_set); |
157 |
|
|
158 |
< |
while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id) |
158 |
> |
while((t_next_id = T_NTH_NBR(t_next,v_next)) != t_id) |
159 |
|
{ |
160 |
< |
if((e = eNew_edge()) == SM_INVALID) |
160 |
> |
if((e = eNew_edge()) == INVALID) |
161 |
> |
return(NULL); |
162 |
> |
|
163 |
> |
t_next = SM_NTH_TRI(sm,t_next_id); |
164 |
> |
v_next = (T_WHICH_V(t_next,id)+1)%3; |
165 |
> |
|
166 |
> |
SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next)); |
167 |
> |
SET_E_NTH_TRI(e,0,INVALID); |
168 |
> |
SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next)); |
169 |
> |
v_next = (T_WHICH_V(t_next,id)+2)%3; |
170 |
> |
SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next)); |
171 |
> |
elist = add_data_to_circular_list(elist,&end,e); |
172 |
> |
|
173 |
> |
|
174 |
> |
if(qtinset(*delptr,t_next_id)) |
175 |
|
{ |
176 |
|
#ifdef DEBUG |
177 |
< |
eputs("smVertex_star_polygon():Too many edges\n"); |
178 |
< |
#endif |
179 |
< |
return(NULL); |
177 |
> |
eputs("smVertex_star_polygon(): id already in set\n"); |
178 |
> |
#endif |
179 |
> |
free_list(elist); |
180 |
> |
return(NULL); |
181 |
|
} |
182 |
< |
elist = add_data_to_circular_list(elist,&end,e); |
183 |
< |
t_next = SM_NTH_TRI(sm,t_next_id); |
167 |
< |
v_next = (T_WHICH_V(t_next,id)+1)%3; |
168 |
< |
SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next)); |
169 |
< |
SET_E_NTH_TRI(e,0,SM_INVALID); |
170 |
< |
SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next)); |
171 |
< |
v_next = (T_WHICH_V(t_next,id)+2)%3; |
172 |
< |
SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next)); |
173 |
< |
insertelem(del_set,t_next_id); |
182 |
> |
else |
183 |
> |
qtaddelem(*delptr,t_next_id); |
184 |
|
} |
185 |
|
return(elist); |
186 |
|
} |
234 |
|
vertex v such that v0v1v is a convex angle, and the edge v1v does |
235 |
|
not intersect any other edges |
236 |
|
*/ |
237 |
< |
id = SM_INVALID; |
237 |
> |
id = INVALID; |
238 |
|
el = l; |
239 |
|
while(id != id0) |
240 |
|
{ |
250 |
|
if(el == l) |
251 |
|
break; |
252 |
|
} |
253 |
< |
return(SM_INVALID); |
253 |
> |
return(INVALID); |
254 |
|
} |
255 |
|
|
256 |
|
int |
261 |
|
LIST *list,*lptr,*end; |
262 |
|
int e,e1,e2,new_e; |
263 |
|
|
264 |
< |
e2 = SM_INVALID; |
264 |
> |
e2 = INVALID; |
265 |
|
list = lptr = *l; |
266 |
|
|
267 |
< |
if((new_e = eNew_edge())==SM_INVALID) |
267 |
> |
if((new_e = eNew_edge())==INVALID) |
268 |
|
{ |
269 |
|
#ifdef DEBUG |
270 |
|
eputs("split_edge_list():Too many edges\n"); |
273 |
|
} |
274 |
|
SET_E_NTH_VERT(new_e,0,id0); |
275 |
|
SET_E_NTH_VERT(new_e,1,id_new); |
276 |
< |
SET_E_NTH_TRI(new_e,0,SM_INVALID); |
277 |
< |
SET_E_NTH_TRI(new_e,1,SM_INVALID); |
276 |
> |
SET_E_NTH_TRI(new_e,0,INVALID); |
277 |
> |
SET_E_NTH_TRI(new_e,1,INVALID); |
278 |
|
|
279 |
|
while(e2 != id_new) |
280 |
|
{ |
299 |
|
/* now follow other cycle */ |
300 |
|
|
301 |
|
list = lptr; |
302 |
< |
e2 = SM_INVALID; |
302 |
> |
e2 = INVALID; |
303 |
|
while(e2 != id0) |
304 |
|
{ |
305 |
|
lptr = LIST_NEXT(lptr); |
327 |
|
SM *sm; |
328 |
|
LIST *plist,**add_ptr; |
329 |
|
{ |
320 |
– |
TRI *tri; |
330 |
|
int t_id,e_id0,e_id1,e_id2; |
331 |
|
int v_id0,v_id1,v_id2; |
332 |
|
LIST *lptr; |
342 |
|
v_id1 = E_NTH_VERT(e_id1,0); |
343 |
|
v_id2 = E_NTH_VERT(e_id1,1); |
344 |
|
/* form a triangle for each triple of with v0 as base of star */ |
345 |
< |
t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri); |
345 |
> |
t_id = smAdd_tri(sm,v_id0,v_id1,v_id2); |
346 |
|
*add_ptr = push_data(*add_ptr,t_id); |
347 |
|
|
348 |
|
/* add which pointer?*/ |
404 |
|
} |
405 |
|
/* if concave: add edge and recurse on two sub polygons */ |
406 |
|
id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l)); |
407 |
< |
if(id_next == SM_INVALID) |
407 |
> |
if(id_next == INVALID) |
408 |
|
{ |
409 |
|
#ifdef DEBUG |
410 |
|
eputs("smTriangulate_elist():Unable to find convex vertex\n"); |
428 |
|
} |
429 |
|
|
430 |
|
int |
431 |
< |
smTriangulate(sm,plist,add_ptr) |
431 |
> |
smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr) |
432 |
|
SM *sm; |
433 |
+ |
int id0,id1,id2,e0,e1,*e2ptr; |
434 |
+ |
{ |
435 |
+ |
int t_id; |
436 |
+ |
int e2; |
437 |
+ |
|
438 |
+ |
t_id = smAdd_tri(sm,id0,id1,id2); |
439 |
+ |
if(*e2ptr == 0) |
440 |
+ |
{ |
441 |
+ |
e2 = eNew_edge(); |
442 |
+ |
SET_E_NTH_VERT(e2,0,id2); |
443 |
+ |
SET_E_NTH_VERT(e2,1,id0); |
444 |
+ |
} |
445 |
+ |
else |
446 |
+ |
e2 = *e2ptr; |
447 |
+ |
/* set appropriate tri for each edge*/ |
448 |
+ |
SET_E_NTH_TRI(e0,0,t_id); |
449 |
+ |
SET_E_NTH_TRI(e1,0,t_id); |
450 |
+ |
SET_E_NTH_TRI(e2,0,t_id); |
451 |
+ |
|
452 |
+ |
*e2ptr = e2; |
453 |
+ |
return(t_id); |
454 |
+ |
} |
455 |
+ |
int |
456 |
+ |
smTriangulate_elist_new(sm,id,plist,add_ptr) |
457 |
+ |
SM *sm; |
458 |
+ |
int id; |
459 |
|
LIST *plist,**add_ptr; |
460 |
|
{ |
461 |
+ |
LIST *l,*prev,*t; |
462 |
+ |
FVECT v0,v1,v2,n,p; |
463 |
+ |
int is_tri,loop,t_id,id0,id1,id2,e2,eprev,enext; |
464 |
+ |
double dp; |
465 |
+ |
|
466 |
+ |
smDir(sm,p,id); |
467 |
+ |
enext=0; |
468 |
+ |
is_tri= loop = FALSE; |
469 |
+ |
l = prev = plist; |
470 |
+ |
/* get v0,v1,v2 */ |
471 |
+ |
eprev = (int)LIST_DATA(l); |
472 |
+ |
id0 = E_NTH_VERT(eprev,0); |
473 |
+ |
id1 = E_NTH_VERT(eprev,1); |
474 |
+ |
smDir(sm,v0,id0); |
475 |
+ |
smDir(sm,v1,id1); |
476 |
+ |
while(l) |
477 |
+ |
{ |
478 |
+ |
l = LIST_NEXT(l); |
479 |
+ |
e2 = (int)LIST_DATA(l); |
480 |
+ |
id2 = E_NTH_VERT(e2,1); |
481 |
+ |
/* Check if have a triangle */ |
482 |
+ |
if(LIST_NEXT(LIST_NEXT(l)) == prev) |
483 |
+ |
{ |
484 |
+ |
is_tri = TRUE; |
485 |
+ |
break; |
486 |
+ |
} |
487 |
+ |
if(LIST_NEXT(l) == plist) |
488 |
+ |
{ |
489 |
+ |
if(!loop) |
490 |
+ |
loop = 1; |
491 |
+ |
else |
492 |
+ |
loop++; |
493 |
+ |
if(loop > 3) |
494 |
+ |
break; |
495 |
+ |
} |
496 |
+ |
smDir(sm,v2,id2); |
497 |
+ |
/* determine if convex (left turn), or concave(right turn) angle */ |
498 |
+ |
if(!convex_angle(v0,v1,v2)) |
499 |
+ |
{ |
500 |
+ |
VCOPY(v0,v1); |
501 |
+ |
VCOPY(v1,v2); |
502 |
+ |
id0 = id1; |
503 |
+ |
id1 = id2; |
504 |
+ |
prev = l; |
505 |
+ |
eprev = e2; |
506 |
+ |
continue; |
507 |
+ |
} |
508 |
+ |
VCROSS(n,v0,v2); |
509 |
+ |
dp = DOT(n,p); |
510 |
+ |
if(loop <=1 && (!ZERO(dp) && dp < 0.0)) |
511 |
+ |
{ |
512 |
+ |
VCOPY(v0,v1); |
513 |
+ |
VCOPY(v1,v2); |
514 |
+ |
id0 = id1; |
515 |
+ |
id1 = id2; |
516 |
+ |
eprev = e2; |
517 |
+ |
prev = l; |
518 |
+ |
continue; |
519 |
+ |
} |
520 |
+ |
loop = FALSE; |
521 |
+ |
|
522 |
+ |
enext = 0; |
523 |
+ |
t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext); |
524 |
+ |
*add_ptr = push_data(*add_ptr,t_id); |
525 |
+ |
|
526 |
+ |
LIST_NEXT(prev) = LIST_NEXT(l); |
527 |
+ |
LIST_DATA(prev) = eprev = -enext; |
528 |
+ |
LIST_NEXT(l)=NULL; |
529 |
+ |
if(l== plist) |
530 |
+ |
plist = prev; |
531 |
+ |
free_list(l); |
532 |
+ |
l = prev; |
533 |
+ |
VCOPY(v1,v2); |
534 |
+ |
id1 = id2; |
535 |
+ |
} |
536 |
+ |
if(is_tri) |
537 |
+ |
{ |
538 |
+ |
l = LIST_NEXT(l); |
539 |
+ |
enext = (int)LIST_DATA(l); |
540 |
+ |
t_id = smTriangulate_add_tri(sm,id0,id1,id2,eprev,e2,&enext); |
541 |
+ |
*add_ptr = push_data(*add_ptr,t_id); |
542 |
+ |
free_list(l); |
543 |
+ |
} |
544 |
+ |
else |
545 |
+ |
{ |
546 |
+ |
#ifdef DEBUG |
547 |
+ |
eputs("smTriangulate_elist()Unable to triangulate\n"); |
548 |
+ |
#endif |
549 |
+ |
return(FALSE); |
550 |
+ |
} |
551 |
+ |
return(TRUE); |
552 |
+ |
} |
553 |
+ |
|
554 |
+ |
int |
555 |
+ |
smTriangulate(sm,p_id,plist,add_ptr) |
556 |
+ |
SM *sm; |
557 |
+ |
int p_id; |
558 |
+ |
LIST *plist,**add_ptr; |
559 |
+ |
{ |
560 |
|
int e,id_t0,id_t1,e0,e1; |
427 |
– |
TRI *t0,*t1; |
561 |
|
int test; |
562 |
< |
|
562 |
> |
|
563 |
> |
test = smTriangulate_elist_new(sm,p_id,plist,add_ptr); |
564 |
> |
#if 0 |
565 |
|
test = smTriangulate_elist(sm,plist,add_ptr); |
566 |
+ |
#endif |
567 |
|
|
568 |
|
if(!test) |
569 |
|
return(test); |
570 |
+ |
|
571 |
|
FOR_ALL_EDGES(e) |
572 |
|
{ |
573 |
|
id_t0 = E_NTH_TRI(e,0); |
574 |
|
id_t1 = E_NTH_TRI(e,1); |
575 |
< |
if((id_t0==SM_INVALID) || (id_t1==SM_INVALID)) |
575 |
> |
if((id_t0==INVALID) || (id_t1==INVALID)) |
576 |
|
{ |
577 |
|
#ifdef DEBUG |
578 |
|
eputs("smTriangulate(): Unassigned edge neighbor\n"); |
579 |
|
#endif |
580 |
|
continue; |
581 |
|
} |
445 |
– |
t0 = SM_NTH_TRI(sm,id_t0); |
446 |
– |
t1 = SM_NTH_TRI(sm,id_t1); |
582 |
|
|
583 |
< |
e0 = T_WHICH_V(t0,E_NTH_VERT(e,0)); |
584 |
< |
T_NTH_NBR(t0,e0) = id_t1; |
583 |
> |
e0 = T_WHICH_V(SM_NTH_TRI(sm,id_t0),E_NTH_VERT(e,0)); |
584 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,id_t0),e0) = id_t1; |
585 |
|
|
586 |
< |
e1 = T_WHICH_V(t1,E_NTH_VERT(e,1)); |
587 |
< |
T_NTH_NBR(t1,e1) = id_t0; |
586 |
> |
e1 = T_WHICH_V(SM_NTH_TRI(sm,id_t1),E_NTH_VERT(e,1)); |
587 |
> |
T_NTH_NBR(SM_NTH_TRI(sm,id_t1),e1) = id_t0; |
588 |
|
} |
589 |
|
return(test); |
590 |
|
} |
603 |
|
return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1)); |
604 |
|
return(FALSE); |
605 |
|
} |
606 |
< |
smFix_edges(sm,add_list,del_set) |
606 |
> |
|
607 |
> |
smFix_edges(sm,add_list,delptr) |
608 |
|
SM *sm; |
609 |
|
LIST *add_list; |
610 |
< |
OBJECT *del_set; |
610 |
> |
QUADTREE *delptr; |
611 |
> |
|
612 |
|
{ |
613 |
< |
int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next; |
614 |
< |
TRI *t0,*t1,*nt0,*nt1; |
478 |
< |
int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1; |
613 |
> |
int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next; |
614 |
> |
int i,v0_id,v1_id,v2_id,p_id,t0_nid,t1_nid; |
615 |
|
FVECT v0,v1,v2,p,np,v; |
616 |
|
|
617 |
|
FOR_ALL_EDGES(e) |
618 |
|
{ |
619 |
< |
id_t0 = E_NTH_TRI(e,0); |
620 |
< |
id_t1 = E_NTH_TRI(e,1); |
621 |
< |
if((id_t0==SM_INVALID) || (id_t1==SM_INVALID)) |
619 |
> |
t0_id = E_NTH_TRI(e,0); |
620 |
> |
t1_id = E_NTH_TRI(e,1); |
621 |
> |
if((t0_id==INVALID) || (t1_id==INVALID)) |
622 |
|
{ |
623 |
|
#ifdef DEBUG |
624 |
|
eputs("smFix_edges: Unassigned edge nbr\n"); |
625 |
|
#endif |
626 |
|
continue; |
627 |
|
} |
628 |
< |
t0 = SM_NTH_TRI(sm,id_t0); |
629 |
< |
t1 = SM_NTH_TRI(sm,id_t1); |
494 |
< |
|
495 |
< |
e0 = T_WHICH_V(t0,E_NTH_VERT(e,0)); |
496 |
< |
e1 = T_WHICH_V(t1,E_NTH_VERT(-e,0)); |
628 |
> |
e0 = T_WHICH_V(SM_NTH_TRI(sm,t0_id),E_NTH_VERT(e,0)); |
629 |
> |
e1 = T_WHICH_V(SM_NTH_TRI(sm,t1_id),E_NTH_VERT(-e,0)); |
630 |
|
e0_next = (e0+2)%3; |
631 |
|
e1_next = (e1+2)%3; |
632 |
< |
id_v0 = E_NTH_VERT(e,0); |
633 |
< |
id_v1 = E_NTH_VERT(e,1); |
634 |
< |
id_v2 = T_NTH_V(t0,e0_next); |
635 |
< |
id_p = T_NTH_V(t1,e1_next); |
632 |
> |
v0_id = E_NTH_VERT(e,0); |
633 |
> |
v1_id = E_NTH_VERT(e,1); |
634 |
> |
v2_id = T_NTH_V(SM_NTH_TRI(sm,t0_id),e0_next); |
635 |
> |
p_id = T_NTH_V(SM_NTH_TRI(sm,t1_id),e1_next); |
636 |
|
|
637 |
< |
smDir_in_cone(sm,v0,id_v0); |
638 |
< |
smDir_in_cone(sm,v1,id_v1); |
639 |
< |
smDir_in_cone(sm,v2,id_v2); |
637 |
> |
smDir_in_cone(sm,v0,v0_id); |
638 |
> |
smDir_in_cone(sm,v1,v1_id); |
639 |
> |
smDir_in_cone(sm,v2,v2_id); |
640 |
|
|
641 |
< |
VCOPY(p,SM_NTH_WV(sm,id_p)); |
641 |
> |
VCOPY(p,SM_NTH_WV(sm,p_id)); |
642 |
|
VSUB(p,p,SM_VIEW_CENTER(sm)); |
643 |
|
if(point_in_cone(p,v0,v1,v2)) |
644 |
|
{ |
645 |
< |
smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add_list, |
646 |
< |
del_set); |
645 |
> |
smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list, |
646 |
> |
delptr); |
647 |
|
|
515 |
– |
nt0 = SM_NTH_TRI(sm,nid_t0); |
516 |
– |
nt1 = SM_NTH_TRI(sm,nid_t1); |
648 |
|
FOR_ALL_EDGES_FROM(e,i) |
649 |
|
{ |
650 |
< |
if(E_NTH_TRI(i,0)==id_t0 || E_NTH_TRI(i,0)==id_t1) |
650 |
> |
if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id) |
651 |
|
{ |
652 |
< |
if(eIn_tri(i,nt0)) |
653 |
< |
SET_E_NTH_TRI(i,0,nid_t0); |
652 |
> |
if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid))) |
653 |
> |
SET_E_NTH_TRI(i,0,t0_nid); |
654 |
|
else |
655 |
< |
SET_E_NTH_TRI(i,0,nid_t1); |
655 |
> |
SET_E_NTH_TRI(i,0,t1_nid); |
656 |
|
} |
657 |
|
|
658 |
< |
if(E_NTH_TRI(i,1)==id_t0 || E_NTH_TRI(i,1)==id_t1) |
658 |
> |
if(E_NTH_TRI(i,1)==t0_id || E_NTH_TRI(i,1)==t1_id) |
659 |
|
{ |
660 |
< |
if(eIn_tri(i,nt0)) |
661 |
< |
SET_E_NTH_TRI(i,1,nid_t0); |
660 |
> |
if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid))) |
661 |
> |
SET_E_NTH_TRI(i,1,t0_nid); |
662 |
|
else |
663 |
< |
SET_E_NTH_TRI(i,1,nid_t1); |
663 |
> |
SET_E_NTH_TRI(i,1,t1_nid); |
664 |
|
} |
665 |
|
} |
666 |
< |
id_t0 = nid_t0; |
667 |
< |
id_t1 = nid_t1; |
666 |
> |
t0_id = t0_nid; |
667 |
> |
t1_id = t1_nid; |
668 |
|
e_new = eNew_edge(); |
669 |
< |
SET_E_NTH_VERT(e_new,0,id_p); |
670 |
< |
SET_E_NTH_VERT(e_new,1,id_v2); |
671 |
< |
SET_E_NTH_TRI(e_new,0,id_t0); |
672 |
< |
SET_E_NTH_TRI(e_new,1,id_t1); |
669 |
> |
SET_E_NTH_VERT(e_new,0,p_id); |
670 |
> |
SET_E_NTH_VERT(e_new,1,v2_id); |
671 |
> |
SET_E_NTH_TRI(e_new,0,t0_id); |
672 |
> |
SET_E_NTH_TRI(e_new,1,t1_id); |
673 |
|
} |
674 |
|
} |
675 |
< |
smUpdate_locator(sm,add_list,del_set); |
675 |
> |
smUpdate_locator(sm,add_list,qtqueryset(*delptr)); |
676 |
|
} |
677 |
|
|
678 |
|
int |
680 |
|
SM *sm; |
681 |
|
int id; |
682 |
|
{ |
683 |
< |
int tri; |
683 |
> |
int t_id; |
684 |
|
LIST *elist,*add_list; |
685 |
|
int cnt,debug; |
686 |
< |
OBJECT del_set[QT_MAXSET +1]; |
556 |
< |
|
686 |
> |
QUADTREE delnode; |
687 |
|
/* generate list of vertices that form the boundary of the |
688 |
|
star polygon formed by vertex id and all of its adjacent |
689 |
|
triangles |
690 |
|
*/ |
691 |
|
eClear_edges(); |
692 |
< |
QT_CLEAR_SET(del_set); |
563 |
< |
elist = smVertex_star_polygon(sm,id,del_set); |
564 |
< |
if(!elist) |
565 |
< |
return(FALSE); |
692 |
> |
elist = smVertex_star_polygon(sm,id,&delnode); |
693 |
|
|
694 |
+ |
if(!elist) |
695 |
+ |
{ |
696 |
+ |
#ifdef DEBUG |
697 |
+ |
eputs("smMesh_remove_vertex(): Unable to remove vertex"); |
698 |
+ |
#endif |
699 |
+ |
qtfreeleaf(delnode); |
700 |
+ |
return(FALSE); |
701 |
+ |
} |
702 |
|
add_list = NULL; |
703 |
|
/* Triangulate spherical polygon */ |
704 |
< |
smTriangulate(sm,elist,&add_list); |
705 |
< |
|
706 |
< |
|
704 |
> |
if(!smTriangulate(sm,id,elist,&add_list)) |
705 |
> |
{ |
706 |
> |
while(add_list) |
707 |
> |
{ |
708 |
> |
t_id = pop_list(&add_list); |
709 |
> |
smDelete_tri(sm,t_id); |
710 |
> |
} |
711 |
> |
qtfreeleaf(delnode); |
712 |
> |
return(FALSE); |
713 |
> |
} |
714 |
|
/* Fix up new triangles to be Delaunay */ |
715 |
< |
smFix_edges(sm,add_list,del_set); |
715 |
> |
smFix_edges(sm,add_list,&delnode); |
716 |
|
|
717 |
+ |
qtfreeleaf(delnode); |
718 |
|
return(TRUE); |
719 |
|
} |
720 |
|
|
578 |
– |
/* Remove point from samples, and from mesh. Delete any triangles |
579 |
– |
adjacent to the point and re-triangulate the hole |
580 |
– |
Return TRUE is point found , FALSE otherwise |
581 |
– |
*/ |
582 |
– |
int |
583 |
– |
smDelete_point(sm,id) |
584 |
– |
SM *sm; |
585 |
– |
int id; |
586 |
– |
{ |
587 |
– |
|
588 |
– |
/* Remove the corresponding vertex from the mesh */ |
589 |
– |
smMesh_remove_vertex(sm,id); |
590 |
– |
/* Free the sample point */ |
591 |
– |
smDelete_sample(sm,id); |
592 |
– |
return(TRUE); |
593 |
– |
} |
721 |
|
|
722 |
|
|
723 |
|
|