--- ray/src/hd/sm_del.c 1998/09/16 18:16:28 3.5 +++ ray/src/hd/sm_del.c 1998/12/28 18:07:34 3.8 @@ -8,80 +8,26 @@ static char SCCSid[] = "$SunId$ SGI"; * sm_del.c */ #include "standard.h" - +#include "sm_flag.h" #include "sm_list.h" #include "sm_geom.h" +#include "sm_qtree.h" +#include "sm_stree.h" #include "sm.h" -static EDGE Edges[MAX_EDGES]; +static int Max_edges=200; +static EDGE *Edges=NULL; static int Ecnt=0; -int -remove_tri(qtptr,fptr,t_id) - QUADTREE *qtptr; - int *fptr; - int t_id; -{ - int n; - - if(QT_IS_EMPTY(*qtptr)) - return(FALSE); - /* remove id from set */ - else - { - if(!qtinset(*qtptr,t_id)) - return(FALSE); - n = QT_SET_CNT(qtqueryset(*qtptr))-1; - *qtptr = qtdelelem(*qtptr,t_id); - if(n == 0) - (*fptr) |= QT_COMPRESS; - if(!QT_FLAG_FILL_TRI(*fptr)) - (*fptr)++; - } - return(TRUE); -} - -int -remove_tri_compress(qtptr,q0,q1,q2,t0,t1,t2,n,arg,t_id) -QUADTREE *qtptr; -FVECT q0,q1,q2; -FVECT t0,t1,t2; -int n; -int *arg; -int t_id; -{ - int f = 0; - /* NOTE compress */ - return(remove_tri(qtptr,&f,t_id)); -} - - -smLocator_remove_tri(sm,t_id) -SM *sm; -int t_id; -{ - STREE *st; - TRI *t; - FVECT v0,v1,v2; - - st = SM_LOCATOR(sm); - - t = SM_NTH_TRI(sm,t_id); - - VSUB(v0,SM_T_NTH_WV(sm,t,0),SM_VIEW_CENTER(sm)); - VSUB(v1,SM_T_NTH_WV(sm,t,1),SM_VIEW_CENTER(sm)); - VSUB(v2,SM_T_NTH_WV(sm,t,2),SM_VIEW_CENTER(sm)); - stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,t_id,NULL); -} - smFree_tri(sm,id) SM *sm; int id; { - TRI *tri; + TRI *tri,*t; tri = SM_NTH_TRI(sm,id); /* Add to the free_list */ + T_NEXT_FREE(tri) = SM_FREE_TRIS(sm); SM_FREE_TRIS(sm) = id; T_VALID_FLAG(tri) = -1; @@ -95,7 +41,6 @@ SM *sm; int t_id; { - /* NOTE: Assumes that a new triangle adjacent to each vertex has been added- before the deletion: replacing the old tri- and therefore dont need to dereference any pointers @@ -104,7 +49,7 @@ int t_id; */ if(!SM_IS_NTH_T_BASE(sm,t_id)) { - SM_NUM_TRIS(sm)--; + SM_SAMPLE_TRIS(sm)--; if(SM_IS_NTH_T_NEW(sm,t_id)) smNew_tri_cnt--; } @@ -112,216 +57,137 @@ int t_id; smFree_tri(sm,t_id); +#if 0 + { + int i; + TRI *t; + for(i=0; i < SM_NUM_TRI(sm);i++) + { + t = SM_NTH_TRI(sm,i); + if(!T_IS_VALID(t)) + continue; + if(T_NTH_NBR(t,0)==t_id || T_NTH_NBR(t,1)==t_id || T_NTH_NBR(t,2)==t_id) + eputs("Stale pointer: smDelete_tri()\n"); + } + } +#endif } +int +eNew_edge() +{ + if(!Edges) + if(!(Edges = (EDGE *)realloc(NULL,(Max_edges+1)*sizeof(EDGE)))) + goto memerr; + + if(Ecnt >= Max_edges) + { + if(Max_edges > 10000) + error(CONSISTENCY,"Too many edges in vertex loop\n"); + Max_edges += 100; + if(!(Edges = (EDGE *)realloc(Edges,(Max_edges+1)*sizeof(EDGE)))) + goto memerr; + } + return(++Ecnt); + +memerr: + error(SYSTEM,"eNew_edge(): Unable to allocate memory"); +} + +/* Return list of edges defining polygon formed by boundary of triangles +adjacent to id. Return set of triangles adjacent to id to delete in delptr +*/ LIST -*smVertex_star_polygon(sm,id,del_set) +*smVertexPolygon(sm,id,del_ptr) SM *sm; int id; -OBJECT *del_set; +LIST **del_ptr; { TRI *tri,*t_next; LIST *elist,*end; - int t_id,v_next,t_next_id; - int e; + int e,t_id,v_next,t_next_id,b_id,v_id; + eClear_edges(); elist = end = NULL; + /* Get the first triangle adjacent to vertex id */ t_id = SM_NTH_VERT(sm,id); tri = SM_NTH_TRI(sm,t_id); - - if((e = eNew_edge()) == SM_INVALID) - { -#ifdef DEBUG - eputs("smVertex_star_polygon():Too many edges\n"); -#endif - return(NULL); - } + e = eNew_edge(); + /* Get the next vertex on the polygon boundary */ + v_id = T_WHICH_V(tri,id); + b_id = (v_id + 1)%3; + /* Create an edge */ + SET_E_NTH_VERT(e,0,T_NTH_V(tri,b_id)); + SET_E_NTH_TRI(e,0,INVALID); + SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_id)); + v_next = T_NTH_V(tri,(b_id+1)%3); + SET_E_NTH_VERT(e,1,v_next); elist = add_data_to_circular_list(elist,&end,e); - v_next = (T_WHICH_V(tri,id)+1)%3; - SET_E_NTH_VERT(e,0,T_NTH_V(tri,v_next)); - SET_E_NTH_TRI(e,0,SM_INVALID); - SET_E_NTH_TRI(e,1,T_NTH_NBR(tri,v_next)); - v_next = (T_WHICH_V(tri,id)+2)%3; - SET_E_NTH_VERT(e,1,T_NTH_V(tri,v_next)); - - t_next_id = t_id; t_next = tri; - insertelem(del_set,t_id); + *del_ptr = push_data(*del_ptr,t_id); + /* Create a set to hold all of the triangles for deletion later */ - while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id) - { - if((e = eNew_edge()) == SM_INVALID) - { -#ifdef DEBUG - eputs("smVertex_star_polygon():Too many edges\n"); -#endif - return(NULL); - } - elist = add_data_to_circular_list(elist,&end,e); - t_next = SM_NTH_TRI(sm,t_next_id); - v_next = (T_WHICH_V(t_next,id)+1)%3; - SET_E_NTH_VERT(e,0,T_NTH_V(t_next,v_next)); - SET_E_NTH_TRI(e,0,SM_INVALID); - SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_next)); - v_next = (T_WHICH_V(t_next,id)+2)%3; - SET_E_NTH_VERT(e,1,T_NTH_V(t_next,v_next)); - insertelem(del_set,t_next_id); + while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id) + { + e = eNew_edge(); + t_next = SM_NTH_TRI(sm,t_next_id); + SET_E_NTH_VERT(e,0,v_next); + SET_E_NTH_TRI(e,0,INVALID); + v_id = T_WHICH_V(t_next,id); + b_id = (v_id + 1)%3; + SET_E_NTH_TRI(e,1,T_NTH_NBR(t_next,v_id)); + v_next = T_NTH_V(t_next,(b_id+1)%3); + SET_E_NTH_VERT(e,1,v_next); + elist = add_data_to_circular_list(elist,&end,e); + *del_ptr = push_data(*del_ptr,t_next_id); } return(elist); } + int -smEdge_intersect_polygon(sm,v0,v1,l) +smTriangulate_add_tri(sm,id0,id1,id2,e0,e1,e2ptr) SM *sm; -FVECT v0,v1; -LIST *l; +int id0,id1,id2,e0,e1,*e2ptr; { - FVECT e0,e1; - int e,id_e0,id_e1; - LIST *el,*eptr; - - /* Test the edges in l against v0v1 to see if v0v1 intersects - any other edges - */ - - el = l; + int t_id; + int e2; - while(el) - { - e = (int)LIST_DATA(el); - id_e0 = E_NTH_VERT(e,0); - id_e1 = E_NTH_VERT(e,1); - - VSUB(e0,SM_NTH_WV(sm,id_e0),SM_VIEW_CENTER(sm)); - VSUB(e1,SM_NTH_WV(sm,id_e1),SM_VIEW_CENTER(sm)); - if(sedge_intersect(v0,v1,e0,e1)) - return(TRUE); - - el = LIST_NEXT(el); - if(el == l) - break; - } - return(FALSE); -} - -int -smFind_next_convex_vertex(sm,id0,id1,v0,v1,l) - SM *sm; - int id0,id1; - FVECT v0,v1; - LIST *l; -{ - int e,id; - LIST *el; - FVECT v; - - /* starting with the end of edge at head of l, search sequentially for - vertex v such that v0v1v is a convex angle, and the edge v1v does - not intersect any other edges - */ - id = SM_INVALID; - el = l; - while(id != id0) - { - e = (int)LIST_DATA(el); - id = E_NTH_VERT(e,1); - - smDir(sm,v,id); - - if(convex_angle(v0,v1,v) && !smEdge_intersect_polygon(sm,v1,v,l)) - return(id); - - el = LIST_NEXT(el); - if(el == l) - break; - } - return(SM_INVALID); -} - -int -split_edge_list(id0,id_new,l,lnew) -int id0,id_new; -LIST **l,**lnew; -{ - LIST *list,*lptr,*end; - int e,e1,e2,new_e; - - e2 = SM_INVALID; - list = lptr = *l; - - if((new_e = eNew_edge())==SM_INVALID) - { -#ifdef DEBUG - eputs("split_edge_list():Too many edges\n"); +#ifdef DEBUG + if(id0 == INVALID || id1==INVALID || id2==INVALID) + error(CONSISTENCY,"bad id- smTriangulate_add_tri()\n"); #endif - return(FALSE); - } - SET_E_NTH_VERT(new_e,0,id0); - SET_E_NTH_VERT(new_e,1,id_new); - SET_E_NTH_TRI(new_e,0,SM_INVALID); - SET_E_NTH_TRI(new_e,1,SM_INVALID); - - while(e2 != id_new) - { - lptr = LIST_NEXT(lptr); - e = (int)LIST_DATA(lptr); - e2 = E_NTH_VERT(e,1); - if(lptr == list) - { -#ifdef DEBUG - eputs("split_edge_list():cant find vertex\n"); -#endif - *lnew = NULL; - return(FALSE); - } + t_id = smAdd_tri(sm,id0,id1,id2); + if(*e2ptr == 0) + { + e2 = eNew_edge(); + SET_E_NTH_VERT(e2,0,id2); + SET_E_NTH_VERT(e2,1,id0); + } + else + e2 = *e2ptr; + /* set appropriate tri for each edge*/ + SET_E_NTH_TRI(e0,0,t_id); + SET_E_NTH_TRI(e1,0,t_id); + SET_E_NTH_TRI(e2,0,t_id); - } - end = lptr; - lptr = LIST_NEXT(lptr); - list = add_data_to_circular_list(list,&end,-new_e); - *lnew = list; - - /* now follow other cycle */ - - list = lptr; - e2 = SM_INVALID; - while(e2 != id0) - { - lptr = LIST_NEXT(lptr); - e = (int)LIST_DATA(lptr); - e2 = E_NTH_VERT(e,1); - if(lptr == list) - { -#ifdef DEBUG - eputs("split_edge_list():cant find intial vertex\n"); -#endif - *l = NULL; - return(FALSE); - } - - } - end = lptr; - list = add_data_to_circular_list(list,&end,new_e); - *l = list; - return(TRUE); + *e2ptr = e2; + return(t_id); } - int -smTriangulate_convex(sm,plist,add_ptr) +smTriangulateConvex(sm,plist,add_ptr) SM *sm; LIST *plist,**add_ptr; { - TRI *tri; int t_id,e_id0,e_id1,e_id2; int v_id0,v_id1,v_id2; LIST *lptr; - int cnt; lptr = plist; e_id0 = (int)LIST_DATA(lptr); @@ -332,126 +198,174 @@ LIST *plist,**add_ptr; e_id1 = (int)LIST_DATA(lptr); v_id1 = E_NTH_VERT(e_id1,0); v_id2 = E_NTH_VERT(e_id1,1); - /* form a triangle for each triple of with v0 as base of star */ - t_id = smAdd_tri(sm,v_id0,v_id1,v_id2,&tri); - *add_ptr = push_data(*add_ptr,t_id); - - /* add which pointer?*/ - lptr = LIST_NEXT(lptr); - if(LIST_NEXT(lptr) != plist) - { - e_id2 = eNew_edge(); - SET_E_NTH_VERT(e_id2,0,v_id2); - SET_E_NTH_VERT(e_id2,1,v_id0); - } + if(LIST_NEXT(lptr) != plist) + e_id2 = 0; else e_id2 = (int)LIST_DATA(lptr); - - /* set appropriate tri for each edge*/ - SET_E_NTH_TRI(e_id0,0,t_id); - SET_E_NTH_TRI(e_id1,0,t_id); - SET_E_NTH_TRI(e_id2,0,t_id); - + t_id = smTriangulate_add_tri(sm,v_id0,v_id1,v_id2,e_id0,e_id1,&e_id2); + *add_ptr = push_data(*add_ptr,t_id); e_id0 = -e_id2; } free_list(plist); return(TRUE); } +#ifdef TEST_DRIVER +FVECT Norm[500],B_V[500]; +int Ncnt,Bcnt,Del=0; +#endif + + +/* Triangulate the polygon defined by plist, and generating vertex p_id. + Return list of added triangles in list add_ptr. Returns TRUE if + successful, FALSE otherwise. This is NOT a general triangulation routine, + assumes polygon star relative to id +*/ + int -smTriangulate_elist(sm,plist,add_ptr) +smTriangulate(sm,id,plist,add_ptr) SM *sm; +int id; LIST *plist,**add_ptr; { - LIST *l,*el1; - FVECT v0,v1,v2; - int id0,id1,id2,e,id_next; - char flipped; - int done; + LIST *l,*prev,*t; + FVECT v0,v1,v2,n,p; + int is_tri,is_convex,cut,t_id,id0,id1,id2,e2,e1,enew; + double dp; + static int debug=0; - l = plist; - + VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); + enew = 0; + is_convex = TRUE; + cut = is_tri= FALSE; + l = prev = plist; + + /* get v0,v1 */ + e1 = (int)LIST_DATA(l); + id0 = E_NTH_VERT(e1,0); + id1 = E_NTH_VERT(e1,1); + VSUB(v0,SM_NTH_WV(sm,id0),SM_VIEW_CENTER(sm)); + VSUB(v1,SM_NTH_WV(sm,id1),SM_VIEW_CENTER(sm)); +#ifdef TEST_DRIVER + Del = TRUE; + VCOPY(B_V[0],v0); + VCOPY(B_V[1],v1); + Bcnt = 2; + Ncnt = 0; +#endif while(l) { - /* get v0,v1,v2 */ - e = (int)LIST_DATA(l); - id0 = E_NTH_VERT(e,0); - id1 = E_NTH_VERT(e,1); l = LIST_NEXT(l); - e = (int)LIST_DATA(l); - id2 = E_NTH_VERT(e,1); + /* Get v2 */ + e2 = (int)LIST_DATA(l); + id2 = E_NTH_VERT(e2,1); + VSUB(v2,SM_NTH_WV(sm,id2),SM_VIEW_CENTER(sm)); +#ifdef TEST_DRIVER + VCOPY(B_V[Bcnt++],v2); +#endif + if(LIST_NEXT(LIST_NEXT(l)) == prev) + {/* Check if have a triangle */ + is_tri = TRUE; + break; + } - smDir(sm,v0,id0); - smDir(sm,v1,id1); - smDir(sm,v2,id2); - /* determine if convex (left turn), or concave(right turn) angle */ - if(convex_angle(v0,v1,v2)) + /* determine if v0-v1-v2 is convex:defined clockwise on the sphere- + so switch orientation + */ + if(convex_angle(v2,v1,v0)) { - if(l == plist) - break; - else + /* test if safe to cut off v0-v1-v2 by testing if p lies outside of + triangle v0-v1-v2: if so, because plist is the star polygon around p, + the new edge v2-v0 cannot intersect any existing edges + */ + VCROSS(n,v0,v2); + dp = DOT(n,p); + if(dp <= 0.0) + { + /* remove edges e1,e2 and add triangle id0,id1,id2 */ + enew = 0; + t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew); + cut = TRUE; + *add_ptr = push_data(*add_ptr,t_id); + /* Insert edge enew into the list, reuse prev list element */ + LIST_NEXT(prev) = LIST_NEXT(l); + LIST_DATA(prev) = e1 = -enew; + /* If removing head of list- reset plist pointer */ + if(l== plist) + plist = prev; + /* free list element for e2 */ + LIST_NEXT(l)=NULL; + free_list(l); + l = prev; + VCOPY(v1,v2); + id1 = id2; continue; + } } - /* if concave: add edge and recurse on two sub polygons */ - id_next = smFind_next_convex_vertex(sm,id0,id1,v0,v1,LIST_NEXT(l)); - if(id_next == SM_INVALID) + else + is_convex = FALSE; + VCOPY(v0,v1); + VCOPY(v1,v2); + id0 = id1; + id1 = id2; + e1 = e2; + /* check if gone around circular list without adding any + triangles: prevent infinite loop */ + if(l == plist) { + if(LIST_NEXT(LIST_NEXT(l)) == prev) + {/* Check if have a triangle */ + is_tri = TRUE; + break; + } + + if(is_convex) + break; + if(!cut) + { #ifdef DEBUG - eputs("smTriangulate_elist():Unable to find convex vertex\n"); + eputs("smTriangulate():Unable to triangulate\n"); #endif + free_list(l); + while(*add_ptr) + { + t_id = pop_list(add_ptr); + smDelete_tri(sm,t_id); + } return(FALSE); + } + + cut = FALSE; + is_convex = TRUE; } - /* add edge */ - el1 = NULL; - /* Split edge list l into two lists: one from id1-id_next-id1, - and the next from id2-id_next-id2 - */ - split_edge_list(id1,id_next,&l,&el1); - /* Recurse and triangulate the two edge lists */ - done = smTriangulate_elist(sm,l,add_ptr); - if(done) - done = smTriangulate_elist(sm,el1,add_ptr); - return(done); + prev = l; } - done = smTriangulate_convex(sm,plist,add_ptr); - return(done); -} + if(is_tri) + { + l = LIST_NEXT(l); + enew = (int)LIST_DATA(l); + t_id = smTriangulate_add_tri(sm,id0,id1,id2,e1,e2,&enew); + *add_ptr = push_data(*add_ptr,t_id); + free_list(l); + } + else + if(!smTriangulateConvex(sm,l,add_ptr)) + return(FALSE); -int -smTriangulate(sm,plist,add_ptr) -SM *sm; -LIST *plist,**add_ptr; -{ - int e,id_t0,id_t1,e0,e1; - TRI *t0,*t1; - int test; - - test = smTriangulate_elist(sm,plist,add_ptr); - - if(!test) - return(test); - FOR_ALL_EDGES(e) + /* Set triangle adjacencies based on edge adjacencies */ + FOR_ALL_EDGES(enew) { - id_t0 = E_NTH_TRI(e,0); - id_t1 = E_NTH_TRI(e,1); - if((id_t0==SM_INVALID) || (id_t1==SM_INVALID)) - { -#ifdef DEBUG - eputs("smTriangulate(): Unassigned edge neighbor\n"); -#endif - continue; - } - t0 = SM_NTH_TRI(sm,id_t0); - t1 = SM_NTH_TRI(sm,id_t1); + id0 = E_NTH_TRI(enew,0); + id1 = E_NTH_TRI(enew,1); - e0 = T_WHICH_V(t0,E_NTH_VERT(e,0)); - T_NTH_NBR(t0,e0) = id_t1; - - e1 = T_WHICH_V(t1,E_NTH_VERT(e,1)); - T_NTH_NBR(t1,e1) = id_t0; + e1 = (T_WHICH_V(SM_NTH_TRI(sm,id0),E_NTH_VERT(enew,0))+2)%3; + T_NTH_NBR(SM_NTH_TRI(sm,id0),e1) = id1; + + e2 = (T_WHICH_V(SM_NTH_TRI(sm,id1),E_NTH_VERT(enew,1))+2)%3; + T_NTH_NBR(SM_NTH_TRI(sm,id1),e2) = id0; } - return(test); + return(TRUE); } eIn_tri(e,t) @@ -466,134 +380,142 @@ TRI *t; return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,2)==E_NTH_VERT(e,1)); else if(T_NTH_V(t,2)==E_NTH_VERT(e,0)) return(T_NTH_V(t,0)==E_NTH_VERT(e,1)||T_NTH_V(t,1)==E_NTH_VERT(e,1)); + return(FALSE); } -smFix_edges(sm,add_list,del_set) + +/* Test the new set of triangles for Delaunay condition. 'Edges' contains + all of the new edges added. The CCW triangle assoc with each edge is + tested against the opposite vertex of the CW triangle. If the vertex + lies inside the circle defined by the CCW triangle- the edge is swapped + for the opposite diagonal +*/ +smFixEdges(sm,add_list) SM *sm; LIST *add_list; - OBJECT *del_set; { - int e,id_t0,id_t1,e_new,e0,e1,e0_next,e1_next; - TRI *t0,*t1,*nt0,*nt1; - int i,id_v0,id_v1,id_v2,id_p,nid_t0,nid_t1; + int e,t0_id,t1_id,e_new,e0,e1,e0_next,e1_next; + int i,v0_id,v1_id,v2_id,p_id,t0_nid,t1_nid; FVECT v0,v1,v2,p,np,v; + TRI *t0,*t1; FOR_ALL_EDGES(e) { - id_t0 = E_NTH_TRI(e,0); - id_t1 = E_NTH_TRI(e,1); - if((id_t0==SM_INVALID) || (id_t1==SM_INVALID)) + t0_id = E_NTH_TRI(e,0); + t1_id = E_NTH_TRI(e,1); + if((t0_id==INVALID) || (t1_id==INVALID)) { #ifdef DEBUG - eputs("smFix_edges: Unassigned edge nbr\n"); + error(CONSISTENCY,"smFix_edges: Unassigned edge nbr\n"); #endif - continue; } - t0 = SM_NTH_TRI(sm,id_t0); - t1 = SM_NTH_TRI(sm,id_t1); - - e0 = T_WHICH_V(t0,E_NTH_VERT(e,0)); - e1 = T_WHICH_V(t1,E_NTH_VERT(-e,0)); - e0_next = (e0+2)%3; - e1_next = (e1+2)%3; - id_v0 = E_NTH_VERT(e,0); - id_v1 = E_NTH_VERT(e,1); - id_v2 = T_NTH_V(t0,e0_next); - id_p = T_NTH_V(t1,e1_next); + t0 = SM_NTH_TRI(sm,t0_id); + t1 = SM_NTH_TRI(sm,t1_id); + e0 = T_NTH_NBR_PTR(t1_id,t0); + e1 = T_NTH_NBR_PTR(t0_id,t1); - smDir_in_cone(sm,v0,id_v0); - smDir_in_cone(sm,v1,id_v1); - smDir_in_cone(sm,v2,id_v2); + v0_id = E_NTH_VERT(e,0); + v1_id = E_NTH_VERT(e,1); + v2_id = T_NTH_V(t0,e0); + p_id = T_NTH_V(t1,e1); + + smDir_in_cone(sm,v0,v0_id); + smDir_in_cone(sm,v1,v1_id); + smDir_in_cone(sm,v2,v2_id); - VCOPY(p,SM_NTH_WV(sm,id_p)); + VCOPY(p,SM_NTH_WV(sm,p_id)); VSUB(p,p,SM_VIEW_CENTER(sm)); if(point_in_cone(p,v0,v1,v2)) { - smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add_list, - del_set); + smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list); - nt0 = SM_NTH_TRI(sm,nid_t0); - nt1 = SM_NTH_TRI(sm,nid_t1); + /* Adjust the triangle pointers of the remaining edges to be + processed + */ FOR_ALL_EDGES_FROM(e,i) { - if(E_NTH_TRI(i,0)==id_t0 || E_NTH_TRI(i,0)==id_t1) + if(E_NTH_TRI(i,0)==t0_id || E_NTH_TRI(i,0)==t1_id) { - if(eIn_tri(i,nt0)) - SET_E_NTH_TRI(i,0,nid_t0); + if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid))) + SET_E_NTH_TRI(i,0,t0_nid); else - SET_E_NTH_TRI(i,0,nid_t1); + SET_E_NTH_TRI(i,0,t1_nid); } - if(E_NTH_TRI(i,1)==id_t0 || E_NTH_TRI(i,1)==id_t1) + if(E_NTH_TRI(i,1)==t0_id || E_NTH_TRI(i,1)==t1_id) { - if(eIn_tri(i,nt0)) - SET_E_NTH_TRI(i,1,nid_t0); + if(eIn_tri(i,SM_NTH_TRI(sm,t0_nid))) + SET_E_NTH_TRI(i,1,t0_nid); else - SET_E_NTH_TRI(i,1,nid_t1); + SET_E_NTH_TRI(i,1,t1_nid); } } - id_t0 = nid_t0; - id_t1 = nid_t1; + t0_id = t0_nid; + t1_id = t1_nid; e_new = eNew_edge(); - SET_E_NTH_VERT(e_new,0,id_p); - SET_E_NTH_VERT(e_new,1,id_v2); - SET_E_NTH_TRI(e_new,0,id_t0); - SET_E_NTH_TRI(e_new,1,id_t1); + SET_E_NTH_VERT(e_new,0,p_id); + SET_E_NTH_VERT(e_new,1,v2_id); + SET_E_NTH_TRI(e_new,0,t0_id); + SET_E_NTH_TRI(e_new,1,t1_id); } } - smUpdate_locator(sm,add_list,del_set); + /* Add/Delete the appropriate triangles from the stree */ + smUpdate_locator(sm,add_list); } +/* Remove vertex "id" from the mesh- and retriangulate the resulting + hole: Returns TRUE if successful, FALSE otherwise. + */ int -smMesh_remove_vertex(sm,id) +smRemoveVertex(sm,id) SM *sm; int id; { - int tri; - LIST *elist,*add_list; - int cnt,debug; - OBJECT del_set[QT_MAXSET +1]; - - /* generate list of vertices that form the boundary of the - star polygon formed by vertex id and all of its adjacent - triangles + LIST *b_list,*add_list,*del_list; + int t_id,i; + static int cnt=0; + OBJECT *optr,*os; + /* generate list of edges that form the boundary of the + polygon formed by the triangles adjacent to vertex 'id' */ - eClear_edges(); - QT_CLEAR_SET(del_set); - elist = smVertex_star_polygon(sm,id,del_set); - if(!elist) - return(FALSE); + del_list = NULL; + b_list = smVertexPolygon(sm,id,&del_list); add_list = NULL; - /* Triangulate spherical polygon */ - smTriangulate(sm,elist,&add_list); + /* Triangulate polygonal hole */ + if(!smTriangulate(sm,id,b_list,&add_list)) + { + free_list(del_list); + return(FALSE); + } + else + { +#ifdef DEBUG + b_list = del_list; + while(b_list) + { + t_id = LIST_DATA(b_list); + b_list = LIST_NEXT(b_list); + T_VALID_FLAG(SM_NTH_TRI(sm,t_id))=-1; + } +#endif + while(del_list) + { + t_id = pop_list(&del_list); + smDelete_tri(sm,t_id); + } + } + /* Fix up new triangles to be Delaunay-delnode contains set of + triangles to delete,add_list is the set of new triangles to add + */ + smFixEdges(sm,add_list); - - /* Fix up new triangles to be Delaunay */ - smFix_edges(sm,add_list,del_set); - return(TRUE); } -/* Remove point from samples, and from mesh. Delete any triangles - adjacent to the point and re-triangulate the hole - Return TRUE is point found , FALSE otherwise -*/ -int -smDelete_point(sm,id) -SM *sm; -int id; -{ - /* Remove the corresponding vertex from the mesh */ - smMesh_remove_vertex(sm,id); - /* Free the sample point */ - smDelete_sample(sm,id); - return(TRUE); -} - - +