--- ray/src/hd/sm_del.c	1998/08/19 17:45:24	3.1
+++ ray/src/hd/sm_del.c	1998/09/16 18:16:28	3.5
@@ -16,27 +16,62 @@ static char SCCSid[] = "$SunId$ SGI";
 static EDGE Edges[MAX_EDGES];
 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;
-  char found;
   TRI *t;
-  FVECT p0,p1,p2;
+  FVECT v0,v1,v2;
 
   st = SM_LOCATOR(sm);
 
   t = SM_NTH_TRI(sm,t_id);
 
-  smDir(sm,p0,T_NTH_V(t,0));
-  smDir(sm,p1,T_NTH_V(t,1));
-  smDir(sm,p2,T_NTH_V(t,2));
-
-  found = stRemove_tri(st,t_id,p0,p1,p2);
-
-  return(found);
+  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)
@@ -60,8 +95,6 @@ SM *sm;
 int t_id;
 {
 
-    /* first remove from point location structure */
-    smLocator_remove_tri(sm,t_id);
 
   /* NOTE: Assumes that a new triangle adjacent to each vertex
      has been added- before the deletion: replacing
@@ -82,14 +115,14 @@ int t_id;
 }
 
 
-
-LIST
-*smVertex_star_polygon(sm,id)
+LIST 
+*smVertex_star_polygon(sm,id,del_set)
 SM *sm;
 int id;
+OBJECT *del_set;
 {
     TRI *tri,*t_next;
-    LIST *elist,*end,*tlist;
+    LIST *elist,*end;
     int t_id,v_next,t_next_id;
     int e;
 
@@ -118,7 +151,7 @@ int id;
     t_next_id = t_id;
     t_next = tri;
 
-    tlist = push_data(NULL,t_id);
+    insertelem(del_set,t_id);
 
     while((t_next_id = smTri_next_ccw_nbr(sm,t_next,id)) != t_id)
     {	
@@ -137,13 +170,8 @@ int id;
 	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));
-	tlist = push_data(tlist,t_next_id);
+	insertelem(del_set,t_next_id);
     }
-    while(tlist)
-    {
-	t_id = (int)pop_list(&tlist);
-	smDelete_tri(sm,t_id);
-    }
     return(elist);
 }
 
@@ -169,9 +197,9 @@ LIST *l;
       id_e0 = E_NTH_VERT(e,0);
       id_e1 = E_NTH_VERT(e,1);
 
-      smDir(sm,e0,id_e0);
-      smDir(sm,e1,id_e1);
-      if(spherical_polygon_edge_intersect(v0,v1,e0,e1))
+      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);
@@ -284,11 +312,10 @@ LIST **l,**lnew;
 }
 
 
-
-LIST
-*smTriangulate_convex(sm,plist)
+int
+smTriangulate_convex(sm,plist,add_ptr)
 SM *sm;
-LIST *plist;
+LIST *plist,**add_ptr;
 {
     TRI *tri;
     int t_id,e_id0,e_id1,e_id2;
@@ -307,6 +334,8 @@ LIST *plist;
 	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);
@@ -328,17 +357,18 @@ LIST *plist;
 	e_id0 = -e_id2;
     }
     free_list(plist);
+    return(TRUE);
 }
-
-smTriangulate_elist(sm,plist)
+int
+smTriangulate_elist(sm,plist,add_ptr)
 SM *sm;
-LIST *plist;
+LIST *plist,**add_ptr;
 {
     LIST *l,*el1;
     FVECT v0,v1,v2;
     int id0,id1,id2,e,id_next;
     char flipped;
-    int debug = TRUE;
+    int done;
 
     l = plist;
     
@@ -370,36 +400,34 @@ LIST *plist;
 #ifdef DEBUG
 	  eputs("smTriangulate_elist():Unable to find convex vertex\n");
 #endif
-	  return;
+	  return(FALSE);
       }
       /* 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
       */
-      debug = split_edge_list(id1,id_next,&l,&el1);
+      split_edge_list(id1,id_next,&l,&el1);
       /* Recurse and triangulate the two edge lists */
-      if(debug)
-	debug = smTriangulate_elist(sm,l);
-      if(debug)
-	debug = smTriangulate_elist(sm,el1);
-
-      return(debug);
+      done = smTriangulate_elist(sm,l,add_ptr);
+      if(done)
+	done = smTriangulate_elist(sm,el1,add_ptr);
+      return(done);
     }
-    smTriangulate_convex(sm,plist);
-    return(TRUE);
+    done = smTriangulate_convex(sm,plist,add_ptr);
+    return(done);
 }
 
 int
-smTriangulate_polygon(sm,plist)
+smTriangulate(sm,plist,add_ptr)
 SM *sm;
-LIST *plist;
+LIST *plist,**add_ptr;
 {
     int e,id_t0,id_t1,e0,e1;
     TRI *t0,*t1;
     int test;
     
-    test = smTriangulate_elist(sm,plist,NULL);
+    test = smTriangulate_elist(sm,plist,add_ptr);
 
     if(!test)
        return(test);
@@ -410,7 +438,7 @@ LIST *plist;
 	if((id_t0==SM_INVALID) || (id_t1==SM_INVALID))
 	{
 #ifdef DEBUG
-	   eputs("smTriangulate_polygon(): Unassigned edge neighbor\n");
+	   eputs("smTriangulate(): Unassigned edge neighbor\n");
 #endif
 	    continue;
 	}
@@ -440,8 +468,10 @@ TRI *t;
       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)
+smFix_edges(sm,add_list,del_set)
    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;
@@ -471,15 +501,16 @@ smFix_edges(sm)
 	id_v2 = T_NTH_V(t0,e0_next);
 	id_p = T_NTH_V(t1,e1_next);
 
-	smDir(sm,v0,id_v0);
-	smDir(sm,v1,id_v1);
-	smDir(sm,v2,id_v2);
+	smDir_in_cone(sm,v0,id_v0);
+	smDir_in_cone(sm,v1,id_v1);
+	smDir_in_cone(sm,v2,id_v2);
 	
 	VCOPY(p,SM_NTH_WV(sm,id_p));	
 	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);
+	   smTris_swap_edge(sm,id_t0,id_t1,e0,e1,&nid_t0,&nid_t1,&add_list,
+			    del_set);
 	    
 	    nt0 = SM_NTH_TRI(sm,nid_t0);
 	    nt1 = SM_NTH_TRI(sm,nid_t1);
@@ -510,7 +541,7 @@ smFix_edges(sm)
 	    SET_E_NTH_TRI(e_new,1,id_t1);
 	}
     }
-
+    smUpdate_locator(sm,add_list,del_set);
 }
 
 int
@@ -519,24 +550,27 @@ smMesh_remove_vertex(sm,id)
    int id;
 {
     int tri;
-    LIST *elist;
+    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
      */
     eClear_edges();
-    elist = smVertex_star_polygon(sm,id);
+    QT_CLEAR_SET(del_set);
+    elist = smVertex_star_polygon(sm,id,del_set);
     if(!elist)
        return(FALSE);
 
+    add_list = NULL;
     /* Triangulate spherical polygon */
-    debug = smTriangulate_polygon(sm,elist);
+    smTriangulate(sm,elist,&add_list);
 
 
     /* Fix up new triangles to be Delaunay */
-    if(debug)
-       smFix_edges(sm);
+    smFix_edges(sm,add_list,del_set);
 
     return(TRUE);
 }