22 |
|
int *fptr; |
23 |
|
int t_id; |
24 |
|
{ |
25 |
– |
OBJECT tset[QT_MAXSET+1]; |
25 |
|
int n; |
26 |
|
|
27 |
|
if(QT_IS_EMPTY(*qtptr)) |
56 |
|
} |
57 |
|
|
58 |
|
|
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 |
– |
|
59 |
|
smLocator_remove_tri(sm,t_id) |
60 |
|
SM *sm; |
61 |
|
int t_id; |
62 |
|
{ |
63 |
|
STREE *st; |
92 |
– |
char found; |
64 |
|
TRI *t; |
65 |
|
FVECT v0,v1,v2; |
66 |
|
|
71 |
|
VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm)); |
72 |
|
VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm)); |
73 |
|
VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm)); |
74 |
< |
found = stUpdate_tri(st,t_id,v0,v1,v2,remove_tri,remove_tri_compress); |
104 |
< |
return(found); |
74 |
> |
stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,t_id,NULL); |
75 |
|
} |
76 |
|
|
77 |
|
smFree_tri(sm,id) |
115 |
|
} |
116 |
|
|
117 |
|
|
118 |
< |
|
119 |
< |
LIST |
150 |
< |
*smVertex_star_polygon(sm,id) |
118 |
> |
LIST |
119 |
> |
*smVertex_star_polygon(sm,id,del_set) |
120 |
|
SM *sm; |
121 |
|
int id; |
122 |
+ |
OBJECT *del_set; |
123 |
|
{ |
124 |
|
TRI *tri,*t_next; |
125 |
< |
LIST *elist,*end,*tlist; |
125 |
> |
LIST *elist,*end; |
126 |
|
int t_id,v_next,t_next_id; |
127 |
|
int e; |
128 |
|
|
151 |
|
t_next_id = t_id; |
152 |
|
t_next = tri; |
153 |
|
|
154 |
< |
tlist = push_data(NULL,t_id); |
154 |
> |
insertelem(del_set,t_id); |
155 |
|
|
156 |
|
while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id) |
157 |
|
{ |
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 |
< |
tlist = push_data(tlist,t_next_id); |
173 |
> |
insertelem(del_set,t_next_id); |
174 |
|
} |
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 |
– |
} |
175 |
|
return(elist); |
176 |
|
} |
177 |
|
|
196 |
|
e = (int)LIST_DATA(el); |
197 |
|
id_e0 = E_NTH_VERT(e,0); |
198 |
|
id_e1 = E_NTH_VERT(e,1); |
199 |
< |
/* NOTE: DO these need to be normalized? Just subtract center? */ |
237 |
< |
/* |
238 |
< |
smDir(sm,e0,id_e0); |
239 |
< |
smDir(sm,e1,id_e1); |
240 |
< |
*/ |
199 |
> |
|
200 |
|
VSUB(e0,SM_NTH_WV(sm,id_e0),SM_VIEW_CENTER(sm)); |
201 |
|
VSUB(e1,SM_NTH_WV(sm,id_e1),SM_VIEW_CENTER(sm)); |
202 |
|
if(sedge_intersect(v0,v1,e0,e1)) |
313 |
|
|
314 |
|
|
315 |
|
int |
316 |
< |
smTriangulate_convex(sm,plist) |
316 |
> |
smTriangulate_convex(sm,plist,add_ptr) |
317 |
|
SM *sm; |
318 |
< |
LIST *plist; |
318 |
> |
LIST *plist,**add_ptr; |
319 |
|
{ |
320 |
|
TRI *tri; |
321 |
|
int t_id,e_id0,e_id1,e_id2; |
334 |
|
v_id2 = E_NTH_VERT(e_id1,1); |
335 |
|
/* form a triangle for each triple of with v0 as base of star */ |
336 |
|
t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri); |
337 |
< |
smLocator_add_tri(sm,t_id,v_id0,v_id1,v_id2); |
337 |
> |
*add_ptr = push_data(*add_ptr,t_id); |
338 |
> |
|
339 |
|
/* add which pointer?*/ |
340 |
|
|
341 |
|
lptr = LIST_NEXT(lptr); |
356 |
|
|
357 |
|
e_id0 = -e_id2; |
358 |
|
} |
399 |
– |
|
359 |
|
free_list(plist); |
360 |
|
return(TRUE); |
361 |
|
} |
362 |
|
int |
363 |
< |
smTriangulate_elist(sm,plist) |
363 |
> |
smTriangulate_elist(sm,plist,add_ptr) |
364 |
|
SM *sm; |
365 |
< |
LIST *plist; |
365 |
> |
LIST *plist,**add_ptr; |
366 |
|
{ |
367 |
|
LIST *l,*el1; |
368 |
|
FVECT v0,v1,v2; |
409 |
|
*/ |
410 |
|
split_edge_list(id1,id_next,&l,&el1); |
411 |
|
/* Recurse and triangulate the two edge lists */ |
412 |
< |
done = smTriangulate_elist(sm,l); |
412 |
> |
done = smTriangulate_elist(sm,l,add_ptr); |
413 |
|
if(done) |
414 |
< |
done = smTriangulate_elist(sm,el1); |
414 |
> |
done = smTriangulate_elist(sm,el1,add_ptr); |
415 |
|
return(done); |
416 |
|
} |
417 |
< |
done = smTriangulate_convex(sm,plist); |
417 |
> |
done = smTriangulate_convex(sm,plist,add_ptr); |
418 |
|
return(done); |
419 |
|
} |
420 |
|
|
421 |
|
int |
422 |
< |
smTriangulate(sm,plist) |
422 |
> |
smTriangulate(sm,plist,add_ptr) |
423 |
|
SM *sm; |
424 |
< |
LIST *plist; |
424 |
> |
LIST *plist,**add_ptr; |
425 |
|
{ |
426 |
|
int e,id_t0,id_t1,e0,e1; |
427 |
|
TRI *t0,*t1; |
428 |
|
int test; |
429 |
|
|
430 |
< |
test = smTriangulate_elist(sm,plist); |
430 |
> |
test = smTriangulate_elist(sm,plist,add_ptr); |
431 |
|
|
432 |
|
if(!test) |
433 |
|
return(test); |
468 |
|
return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1)); |
469 |
|
return(FALSE); |
470 |
|
} |
471 |
< |
smFix_edges(sm) |
471 |
> |
smFix_edges(sm,add_list,del_set) |
472 |
|
SM *sm; |
473 |
+ |
LIST *add_list; |
474 |
+ |
OBJECT *del_set; |
475 |
|
{ |
476 |
|
int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next; |
477 |
|
TRI *t0,*t1,*nt0,*nt1; |
478 |
|
int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1; |
479 |
|
FVECT v0,v1,v2,p,np,v; |
480 |
< |
LIST *add,*del; |
520 |
< |
|
521 |
< |
add = del = NULL; |
480 |
> |
|
481 |
|
FOR_ALL_EDGES(e) |
482 |
|
{ |
483 |
|
id_t0 = E_NTH_TRI(e,0); |
501 |
|
id_v2 = T_NTH_V(t0,e0_next); |
502 |
|
id_p = T_NTH_V(t1,e1_next); |
503 |
|
|
504 |
< |
smDir(sm,v0,id_v0); |
505 |
< |
smDir(sm,v1,id_v1); |
506 |
< |
smDir(sm,v2,id_v2); |
504 |
> |
smDir_in_cone(sm,v0,id_v0); |
505 |
> |
smDir_in_cone(sm,v1,id_v1); |
506 |
> |
smDir_in_cone(sm,v2,id_v2); |
507 |
|
|
508 |
|
VCOPY(p,SM_NTH_WV(sm,id_p)); |
509 |
|
VSUB(p,p,SM_VIEW_CENTER(sm)); |
510 |
|
if(point_in_cone(p,v0,v1,v2)) |
511 |
|
{ |
512 |
< |
smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add,&del); |
512 |
> |
smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add_list, |
513 |
> |
del_set); |
514 |
|
|
515 |
|
nt0 = SM_NTH_TRI(sm,nid_t0); |
516 |
|
nt1 = SM_NTH_TRI(sm,nid_t1); |
541 |
|
SET_E_NTH_TRI(e_new,1,id_t1); |
542 |
|
} |
543 |
|
} |
544 |
< |
smUpdate_locator(sm,add,del); |
544 |
> |
smUpdate_locator(sm,add_list,del_set); |
545 |
|
} |
546 |
|
|
547 |
|
int |
550 |
|
int id; |
551 |
|
{ |
552 |
|
int tri; |
553 |
< |
LIST *elist; |
553 |
> |
LIST *elist,*add_list; |
554 |
|
int cnt,debug; |
555 |
+ |
OBJECT del_set[QT_MAXSET +1]; |
556 |
+ |
|
557 |
|
/* generate list of vertices that form the boundary of the |
558 |
|
star polygon formed by vertex id and all of its adjacent |
559 |
|
triangles |
560 |
|
*/ |
561 |
|
eClear_edges(); |
562 |
< |
elist = smVertex_star_polygon(sm,id); |
562 |
> |
QT_CLEAR_SET(del_set); |
563 |
> |
elist = smVertex_star_polygon(sm,id,del_set); |
564 |
|
if(!elist) |
565 |
|
return(FALSE); |
566 |
|
|
567 |
+ |
add_list = NULL; |
568 |
|
/* Triangulate spherical polygon */ |
569 |
< |
smTriangulate(sm,elist); |
569 |
> |
smTriangulate(sm,elist,&add_list); |
570 |
|
|
571 |
|
|
572 |
|
/* Fix up new triangles to be Delaunay */ |
573 |
< |
smFix_edges(sm); |
573 |
> |
smFix_edges(sm,add_list,del_set); |
574 |
|
|
575 |
|
return(TRUE); |
576 |
|
} |