--- ray/src/hd/sm_qtree.c	1998/12/28 18:07:36	3.9
+++ ray/src/hd/sm_qtree.c	1999/06/10 15:22:23	3.13
@@ -30,8 +30,15 @@ extern FVECT Pick_point[500];
 extern int Pick_q[500];
 
 #endif
-int Incnt=0;
 
+qtremovelast(qt,id)
+QUADTREE qt;
+int id;
+{
+  if(qtqueryset(qt)[(*(qtqueryset(qt)))] != id)
+    error(CONSISTENCY,"not removed\n");
+  ((*(qtqueryset(qt)))--);
+}
 QUADTREE
 qtAlloc()			/* allocate a quadtree */
 {
@@ -281,18 +288,24 @@ int n;
 
   /* First check if can trivial accept: if vertex in cell */
   if(s0 & s1 & s2)
+  {
     goto Lfunc_call;
-
+  }
   /* Assumption: Could not trivial reject*/
   /* IF any coords lie on edge- must be in if couldnt reject */
   a = q1[0];b= q0[1]; c= q0[2];
   if(t0[0]== a || t0[1] == b || t0[2] == c)
+  {
     goto Lfunc_call;
+  }
   if(t1[0]== a || t1[1] == b || t1[2] == c)
+  {
     goto Lfunc_call;
+  }
   if(t2[0]== a || t2[1] == b || t2[2] == c)
+  {
     goto Lfunc_call;
-  
+  }
   /* Test for edge crossings */
   /* Test t0t1,t1t2,t2t0 against a */
   /* Calculate edge crossings */
@@ -411,26 +424,33 @@ int n;
   char testl,testh,test_t0t1,test_t1t2,test_t2t0;
   unsigned int ls0,ls1,ls2;
   
+  
   /* May have gotten passed trivial reject if one/two vertices are ON */
   a = q1[0];b= q0[1]; c= q0[2];
   SIDES_LESS(t0,t1,t2,ls0,ls1,ls2,a,b,c);
   
   /* First check if can trivial accept: if vertex in cell */
   if(ls0 & ls1 & ls2)
+  {
     goto Lfunc_call;
-
+  }
   if(ls0==0 || ls1 == 0 || ls2 ==0)
     return(qt);
   /* Assumption: Could not trivial reject*/
   /* IF any coords lie on edge- must be in if couldnt reject */
 
   if(t0[0]== a || t0[1] == b || t0[2] == c)
+  {
     goto Lfunc_call;
+  }
   if(t1[0]== a || t1[1] == b || t1[2] == c)
+  {
     goto Lfunc_call;
+  }
   if(t2[0]== a || t2[1] == b || t2[2] == c)
+  {
     goto Lfunc_call;
-
+  }
   /* Test for edge crossings */
   /* Test t0t1 against a,b,c */
   /* First test if t0t1 can be trivially rejected */
@@ -454,7 +474,7 @@ int n;
       db = t1[1] + dt21[1]*((double)(a - t1[0]))/dt21[0];
       TEST_INT(testl,testh,db,q1[1],b,bl,bh)
   }
-  test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) || 
+ test_t2t0 = !(((ls0 & 5)==0) || ((ls1 & 5)==0)|| ((ls2 & 5)==0) || 
        ((sq0 & 5)==0) ||((sq1 & 5)==0)|| ((sq2 & 5)==0));
   if(test_t2t0 && (e0 & 4))
   {
@@ -519,7 +539,6 @@ int n;
 
   return(qt);
 Lfunc_call:
-
   qt = f.func(f.argptr,root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
 	      s0,s1,s2,sq0,sq1,sq2,1,f,n);
   return(qt);
@@ -650,6 +669,7 @@ BCOORD dt10[3],dt21[3],dt02[3];
 BCOORD scale;
 unsigned int s0,s1,s2,sq0,sq1,sq2;
 FUNC f;
+int n;
 {
   BCOORD a,b,c;
   BCOORD va[3],vb[3],vc[3];
@@ -740,11 +760,11 @@ FUNC f;
 /*************************************************************************/
 /* Visit code for applying functions: NOTE THIS IS THE SAME AS INSERT CODE:
   except sets flags: wanted insert to be as efficient as possible: so 
-  broke into two sets of routines
+  broke into two sets of routines. Also traverses only to n levels.
 */
 
 qtVisit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
-	    s0,s1,s2,sq0,sq1,sq2,f)
+	    s0,s1,s2,sq0,sq1,sq2,f,n)
 int root;
 QUADTREE qt;
 BCOORD q0[3],q1[3],q2[3];
@@ -753,11 +773,14 @@ BCOORD dt10[3],dt21[3],dt02[3];
 BCOORD scale;
 unsigned int s0,s1,s2,sq0,sq1,sq2;
 FUNC f;
+int n;
 {
   BCOORD a,b,c;
   BCOORD va[3],vb[3],vc[3];
   unsigned int sa,sb,sc;
 
+  if(n == 0)
+    return;
   /* If a tree: trivial reject and recurse on potential children */
   if(QT_IS_TREE(qt))
   {
@@ -780,7 +803,7 @@ FUNC f;
       vb[2] = c;
       vb[0] = vc[0] = a;
       qtVisit_tri(root,QT_NTH_CHILD(qt,0),q0,vc,
-	  vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f);
+	  vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
       return;
     }
    if(sb==7)
@@ -791,7 +814,7 @@ FUNC f;
      va[2] = c;
      vc[0] = a;
      qtVisit_tri(root,QT_NTH_CHILD(qt,1),vc,q1,va,
-	     t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
+	     t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
      return;
    }
    if(sc==7)
@@ -802,7 +825,7 @@ FUNC f;
      va[2] = vb[2] = c;
      vb[0] = a;
      qtVisit_tri(root,QT_NTH_CHILD(qt,2),vb,va,
-       q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
+       q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
      return;
    }
 
@@ -816,32 +839,32 @@ FUNC f;
    if(sa==0 && sb==0 && sc==0)
    {
      qtVisit_tri_rev(root,QT_NTH_CHILD(qt,3),va,vb,
-       vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f);
+       vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
       return;
    }
 
    if(sa)
      qtVisit_tri(root,QT_NTH_CHILD(qt,0),q0,vc,vb,t0,
-	  t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f);
+	  t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
    if(sb)
      qtVisit_tri(root,QT_NTH_CHILD(qt,1),vc,q1,va,t0,
-	      t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
+	      t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
    if(sc)
      qtVisit_tri(root,QT_NTH_CHILD(qt,2),vb,va,q2,t0,
-	      t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
+	      t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
    qtVisit_tri_rev(root,QT_NTH_CHILD(qt,3),va,vb,vc,t0,
-	     t1,t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f);
+	     t1,t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
   }
   /* Leaf node: Do definitive test */
   else
     qtLeaf_visit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
-			 scale,s0,s1,s2,sq0,sq1,sq2,f);
+			 scale,s0,s1,s2,sq0,sq1,sq2,f,n);
 
 }
 
 
 qtVisit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,scale,
-	    s0,s1,s2,sq0,sq1,sq2,f)
+	    s0,s1,s2,sq0,sq1,sq2,f,n)
 int root;
 QUADTREE qt;
 BCOORD q0[3],q1[3],q2[3];
@@ -850,11 +873,14 @@ BCOORD dt10[3],dt21[3],dt02[3];
 BCOORD scale;
 unsigned int s0,s1,s2,sq0,sq1,sq2;
 FUNC f;
+int n;
 {
   BCOORD a,b,c;
   BCOORD va[3],vb[3],vc[3];
   unsigned int sa,sb,sc;
 
+  if(n==0)
+    return;
   /* If a tree: trivial reject and recurse on potential children */
   if(QT_IS_TREE(qt))
   {
@@ -876,7 +902,7 @@ FUNC f;
       vb[2] = c;
       vb[0] = vc[0] = a;
       qtVisit_tri_rev(root,QT_NTH_CHILD(qt,0),q0,vc,
-	  vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f);
+	  vb,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
       return;
     }
     if(sb==0)
@@ -887,7 +913,7 @@ FUNC f;
       va[2] = c;
       vc[0] = a;
       qtVisit_tri_rev(root,QT_NTH_CHILD(qt,1),vc,q1,va,
-         t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
+         t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
       return;
     }
     if(sc==0)
@@ -898,7 +924,7 @@ FUNC f;
       va[2] = vb[2] = c;
       vb[0] = a;
       qtVisit_tri_rev(root,QT_NTH_CHILD(qt,2),vb,va,
-	 q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
+	 q2,t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
       return;
     }
     va[0] = q1[0]; 
@@ -911,33 +937,33 @@ FUNC f;
     if(sa==7 && sb==7 && sc==7)
     {
      qtVisit_tri(root,QT_NTH_CHILD(qt,3),va,vb,
-	   vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f);
+	   vc,t0,t1,t2,dt10,dt21,dt02, scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
       return;
     }
     if(sa!=7)
       qtVisit_tri_rev(root,QT_NTH_CHILD(qt,0),q0,vc,vb,
-	   t0,t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f);
+	   t0,t1,t2,dt10,dt21,dt02,scale>>1,sa,s1,s2,sq0,sb,sc,f,n-1);
     if(sb!=7)
       qtVisit_tri_rev(root,QT_NTH_CHILD(qt,1),vc,q1,va,
-	   t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f);
+	   t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,sb,s2,sa,sq1,sc,f,n-1);
     if(sc!=7)
       qtVisit_tri_rev(root,QT_NTH_CHILD(qt,2),vb,va,q2,
-	   t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f);
+	   t0,t1,t2,dt10,dt21,dt02,scale>>1,s0,s1,sc,sa,sb,sq2,f,n-1);
 
     qtVisit_tri(root,QT_NTH_CHILD(qt,3),va,vb,vc,t0,t1,
-	      t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f);
+	      t2,dt10,dt21,dt02,scale>>1,sa,sb,sc,s0,s1,s2,f,n-1);
     return;
   }
   /* Leaf node: Do definitive test */
   else
     qtLeaf_visit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
-			 scale,s0,s1,s2,sq0,sq1,sq2,f);
+			 scale,s0,s1,s2,sq0,sq1,sq2,f,n);
 }
 
 
 
 qtLeaf_visit_tri(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
-		 scale, s0,s1,s2,sq0,sq1,sq2,f)
+		 scale, s0,s1,s2,sq0,sq1,sq2,f,n)
 int root;
 QUADTREE qt;
 BCOORD q0[3],q1[3],q2[3];
@@ -945,13 +971,14 @@ BCOORD t0[3],t1[3],t2[3];
 BCOORD dt10[3],dt21[3],dt02[3];
 unsigned int scale,s0,s1,s2,sq0,sq1,sq2;
 FUNC f;
+int n;
 { 
   double db;
   unsigned int e0,e1,e2;
   char al,ah,bl,bh,cl,ch,testl,testh;
   char test_t0t1,test_t1t2,test_t2t0;
   BCOORD a,b,c;
-
+  
   /* First check if can trivial accept: if vertex in cell */
   if(s0 & s1 & s2)
     goto Lfunc_call;
@@ -1055,9 +1082,11 @@ FUNC f;
   return;
 
 Lfunc_call:
-  f.func(f.argptr,root,qt);
+
+  f.func(f.argptr,root,qt,n);
   if(!QT_IS_EMPTY(qt))
     QT_LEAF_SET_FLAG(qt);
+
 }
 
 
@@ -1065,7 +1094,7 @@ Lfunc_call:
 /* Leaf node: Do definitive test */
 QUADTREE
 qtLeaf_visit_tri_rev(root,qt,q0,q1,q2,t0,t1,t2,dt10,dt21,dt02,
-		 scale, s0,s1,s2,sq0,sq1,sq2,f)
+		 scale, s0,s1,s2,sq0,sq1,sq2,f,n)
 int root;
 QUADTREE qt;
 BCOORD q0[3],q1[3],q2[3];
@@ -1073,6 +1102,7 @@ BCOORD t0[3],t1[3],t2[3];
 BCOORD dt10[3],dt21[3],dt02[3];
 unsigned int scale,s0,s1,s2,sq0,sq1,sq2;
 FUNC f;
+int n;
 { 
   double db;
   unsigned int e0,e1,e2;
@@ -1191,10 +1221,198 @@ FUNC f;
   return;
 
 Lfunc_call:
-  f.func(f.argptr,root,qt);
+  f.func(f.argptr,root,qt,n);
   if(!QT_IS_EMPTY(qt))
     QT_LEAF_SET_FLAG(qt);
 }
+
+
+QUADTREE
+qtInsert_point(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
+int root;
+QUADTREE qt,parent;
+BCOORD q0[3],q1[3],q2[3],bc[3],scale; 
+FUNC f;
+int n,*doneptr;
+{
+  BCOORD a,b,c;
+  BCOORD va[3],vb[3],vc[3];
+
+  if(QT_IS_TREE(qt))
+  {  
+    a = q1[0] + scale;
+    b = q0[1] + scale;
+    c = q0[2] + scale;
+    if(bc[0] > a)
+    {
+      vc[0] = a; vc[1] = b; vc[2] = q0[2];
+      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
+      QT_NTH_CHILD(qt,0) = qtInsert_point(root,QT_NTH_CHILD(qt,0),
+				  qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
+      if(!*doneptr)
+      {
+	f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
+      }	      
+      return(qt);
+    }
+    if(bc[1] > b)
+    {
+      vc[0] = a; vc[1] = b; vc[2] = q0[2];
+      va[0] = q1[0]; va[1] = b; va[2] = c;
+      QT_NTH_CHILD(qt,1) =qtInsert_point(root,QT_NTH_CHILD(qt,1),
+				 qt,vc,q1,va,bc,scale >>1,f,n+1,doneptr);
+      if(!*doneptr)
+      {
+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
+      }	      
+      return(qt);
+    }
+    if(bc[2] > c)
+    {
+      va[0] = q1[0]; va[1] = b; va[2] = c;
+      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
+      QT_NTH_CHILD(qt,2) = qtInsert_point(root,QT_NTH_CHILD(qt,2),
+				  qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
+      if(!*doneptr)
+      {
+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
+      }	
+      return(qt);
+    }
+    else
+    {
+      va[0] = q1[0]; va[1] = b; va[2] = c;
+      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
+      vc[0] = a; vc[1] = b; vc[2] = q0[2];
+      QT_NTH_CHILD(qt,3) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,3),
+				      qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
+      if(!*doneptr)
+      {
+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
+      }	
+      return(qt);
+    }
+  }
+  else
+  {
+    qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,0,f,n,doneptr);
+    return(qt);
+  }
+}
+
+
+QUADTREE
+qtInsert_point_rev(root,qt,parent,q0,q1,q2,bc,scale,f,n,doneptr)
+int root;
+QUADTREE qt,parent;
+BCOORD q0[3],q1[3],q2[3],bc[3]; 
+BCOORD scale;
+FUNC f;
+int n,*doneptr;
+{
+  BCOORD a,b,c;
+  BCOORD va[3],vb[3],vc[3];
+
+  if(QT_IS_TREE(qt))
+  {  
+    a = q1[0] - scale;
+    b = q0[1] - scale;
+    c = q0[2] - scale;
+    if(bc[0] < a)
+    {
+      vc[0] = a; vc[1] = b; vc[2] = q0[2];
+      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
+      QT_NTH_CHILD(qt,0) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,0),
+				  qt,q0,vc,vb,bc,scale>>1,f,n+1,doneptr);
+      if(!*doneptr)
+      {
+	f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
+      }	
+      return(qt);
+    }
+    if(bc[1] < b)
+    {
+      vc[0] = a; vc[1] = b; vc[2] = q0[2];
+      va[0] = q1[0]; va[1] = b; va[2] = c;
+      QT_NTH_CHILD(qt,1) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,1),
+				   qt,vc,q1,va,bc,scale>>1,f,n+1,doneptr);
+      if(!*doneptr)
+      {
+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
+      }	
+      return(qt);
+    }
+    if(bc[2] < c)
+    {
+      va[0] = q1[0]; va[1] = b; va[2] = c;
+      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
+      QT_NTH_CHILD(qt,2) = qtInsert_point_rev(root,QT_NTH_CHILD(qt,2),
+				qt,vb,va,q2,bc,scale>>1,f,n+1,doneptr);
+      if(!*doneptr)
+      {
+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,3),f,doneptr);
+      }	
+      return(qt);
+    }
+    else
+    {
+      va[0] = q1[0]; va[1] = b; va[2] = c;
+      vb[0] = a; vb[1] = q0[1]; vb[2] = c;
+      vc[0] = a; vc[1] = b; vc[2] = q0[2];
+      QT_NTH_CHILD(qt,3) = qtInsert_point(root,QT_NTH_CHILD(qt,3),
+				   qt,va,vb,vc,bc,scale>>1,f,n+1,doneptr);
+      if(!*doneptr)
+      {
+	f.func_after(f.argptr,QT_NTH_CHILD(qt,0),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,1),f,doneptr);
+	if(!*doneptr)
+	  f.func_after(f.argptr,QT_NTH_CHILD(qt,2),f,doneptr);
+      }	
+      return(qt);
+    }
+  }
+  else
+  {
+    qt = f.func(f.argptr,root,qt,parent,q0,q1,q2,bc,scale,1,f,n,doneptr);
+    return(qt);
+  }
+}
+
+
+
+
+
+
+