--- ray/src/hd/sm_del.c 1998/11/11 12:05:38 3.7 +++ ray/src/hd/sm_del.c 1999/03/05 16:32:22 3.11 @@ -19,56 +19,15 @@ static int Max_edges=200; static EDGE *Edges=NULL; static int Ecnt=0; -#define remove_tri_compress remove_tri -remove_tri(qtptr,fptr,tptr) - QUADTREE *qtptr; - int *fptr; - int *tptr; -{ - int n; - - if(QT_IS_EMPTY(*qtptr)) - return; - if(QT_LEAF_IS_FLAG(*qtptr)) - return; - - n = QT_SET_CNT(qtqueryset(*qtptr))-1; - *qtptr = qtdelelem(*qtptr,*tptr); - if(n == 0) - (*fptr) |= QT_COMPRESS; - if(!QT_FLAG_FILL_TRI(*fptr)) - (*fptr)++; -} - - -smLocator_remove_tri(sm,t_id,v0_id,v1_id,v2_id) -SM *sm; -int t_id; -int v0_id,v1_id,v2_id; -{ - STREE *st; - FVECT v0,v1,v2; - - st = SM_LOCATOR(sm); - - VSUB(v0,SM_NTH_WV(sm,v0_id),SM_VIEW_CENTER(sm)); - VSUB(v1,SM_NTH_WV(sm,v1_id),SM_VIEW_CENTER(sm)); - VSUB(v2,SM_NTH_WV(sm,v2_id),SM_VIEW_CENTER(sm)); - - qtClearAllFlags(); - - stApply_to_tri(st,v0,v1,v2,remove_tri,remove_tri_compress,&t_id); - -} - smFree_tri(sm,id) SM *sm; int id; { - TRI *tri; + TRI *tri,*t; tri = SM_NTH_TRI(sm,id); /* Add to the free_list */ + smClear_tri_flags(sm,id); T_NEXT_FREE(tri) = SM_FREE_TRIS(sm); SM_FREE_TRIS(sm) = id; T_VALID_FLAG(tri) = -1; @@ -88,12 +47,10 @@ int t_id; to id because the vertices can no longer point to tri id as being the first triangle pointer */ - if(!SM_IS_NTH_T_BASE(sm,t_id)) - { - SM_SAMPLE_TRIS(sm)--; - if(SM_IS_NTH_T_NEW(sm,t_id)) - smNew_tri_cnt--; - } + SM_SAMPLE_TRIS(sm)--; + if(SM_IS_NTH_T_NEW(sm,t_id)) + smNew_tri_cnt--; + smClear_tri_flags(sm,t_id); smFree_tri(sm,t_id); @@ -110,7 +67,10 @@ eNew_edge() if(Ecnt >= Max_edges) { if(Max_edges > 10000) - error(CONSISTENCY,"Too many edges in vertex loop\n"); + { + eputs("Too many edges in vertex loop\n"); + return(-1); + } Max_edges += 100; if(!(Edges = (EDGE *)realloc(Edges,(Max_edges+1)*sizeof(EDGE)))) goto memerr; @@ -125,15 +85,14 @@ memerr: adjacent to id. Return set of triangles adjacent to id to delete in delptr */ LIST -*smVertexPolygon(sm,id,delptr) +*smVertexStar(sm,id,del_ptr) SM *sm; int id; -QUADTREE *delptr; +LIST **del_ptr; { TRI *tri,*t_next; LIST *elist,*end; int e,t_id,v_next,t_next_id,b_id,v_id; - OBJECT del_set[2]; eClear_edges(); elist = end = NULL; @@ -143,6 +102,7 @@ QUADTREE *delptr; tri = SM_NTH_TRI(sm,t_id); e = eNew_edge(); + /* Get the next vertex on the polygon boundary */ v_id = T_WHICH_V(tri,id); b_id = (v_id + 1)%3; @@ -156,13 +116,14 @@ QUADTREE *delptr; t_next_id = t_id; t_next = tri; + *del_ptr = push_data(*del_ptr,t_id); /* Create a set to hold all of the triangles for deletion later */ - del_set[0] = 1; del_set[1] = t_id; - *delptr = qtnewleaf(del_set); while((t_next_id = T_NTH_NBR(t_next,b_id)) != t_id) { e = eNew_edge(); + if(e== INVALID) + return(NULL); t_next = SM_NTH_TRI(sm,t_next_id); SET_E_NTH_VERT(e,0,v_next); SET_E_NTH_TRI(e,0,INVALID); @@ -172,7 +133,7 @@ QUADTREE *delptr; 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); - qtaddelem(*delptr,t_next_id); + *del_ptr = push_data(*del_ptr,t_next_id); } return(elist); } @@ -261,6 +222,7 @@ LIST *plist,**add_ptr; 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; VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm)); enew = 0; @@ -354,14 +316,15 @@ LIST *plist,**add_ptr; #ifdef DEBUG eputs("smTriangulate():Unable to triangulate\n"); #endif - free_list(l); + free_list(l); while(*add_ptr) { t_id = pop_list(add_ptr); smDelete_tri(sm,t_id); } return(FALSE); - } + } + cut = FALSE; is_convex = TRUE; } @@ -416,11 +379,9 @@ TRI *t; lies inside the circle defined by the CCW triangle- the edge is swapped for the opposite diagonal */ -smFixEdges(sm,add_list,delptr) +smFixEdges(sm,add_list) SM *sm; LIST *add_list; - QUADTREE *delptr; - { 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; @@ -447,16 +408,15 @@ smFixEdges(sm,add_list,delptr) 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); + smDir(sm,v0,v0_id); + smDir(sm,v1,v1_id); + smDir(sm,v2,v2_id); 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,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list, - delptr); + smTris_swap_edge(sm,t0_id,t1_id,e0,e1,&t0_nid,&t1_nid,&add_list); /* Adjust the triangle pointers of the remaining edges to be processed @@ -489,8 +449,7 @@ smFixEdges(sm,add_list,delptr) } } /* Add/Delete the appropriate triangles from the stree */ - smUpdate_locator(sm,add_list,qtqueryset(*delptr)); - + smUpdate_locator(sm,add_list); } /* Remove vertex "id" from the mesh- and retriangulate the resulting @@ -501,35 +460,47 @@ smRemoveVertex(sm,id) SM *sm; int id; { - LIST *b_list,*add_list; - QUADTREE delnode=-1; - int t_id; - + 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' */ - b_list = smVertexPolygon(sm,id,&delnode); - + del_list = NULL; + b_list = smVertexStar(sm,id,&del_list); + if(!b_list) + { + if(del_list) + free_list(del_list); + return(FALSE); + } add_list = NULL; /* Triangulate polygonal hole */ if(!smTriangulate(sm,id,b_list,&add_list)) { - qtfreeleaf(delnode); + free_list(del_list); return(FALSE); } + else + { + 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,&delnode); + smFixEdges(sm,add_list); - - qtfreeleaf(delnode); return(TRUE); } - +