--- ray/src/hd/sm_qtree.c 1998/08/19 17:45:24 3.1 +++ ray/src/hd/sm_qtree.c 1998/08/25 11:03:27 3.3 @@ -22,9 +22,8 @@ static char SCCSid[] = "$SunId$ SGI"; QUADTREE *quad_block[QT_MAX_BLK]; /* our quadtree */ static QUADTREE quad_free_list = EMPTY; /* freed octree nodes */ static QUADTREE treetop = 0; /* next free node */ +int4 *quad_flag; - - QUADTREE qtAlloc() /* allocate a quadtree */ { @@ -41,14 +40,26 @@ qtAlloc() /* allocate a quadtree */ if (QT_BLOCK(freet) >= QT_MAX_BLK) return(EMPTY); if ((quad_block[QT_BLOCK(freet)] = (QUADTREE *)malloc( - (unsigned)QT_BLOCK_SIZE*4*sizeof(QUADTREE))) == NULL) + QT_BLOCK_SIZE*4*sizeof(QUADTREE))) == NULL) return(EMPTY); + quad_flag = (int4 *)realloc((char *)quad_flag, + (QT_BLOCK(freet)+1)*QT_BLOCK_SIZE/(8*sizeof(int4))); + if (quad_flag == NULL) + return(EMPTY); } treetop += 4; return(freet); } +qtClearAllFlags() /* clear all quadtree branch flags */ +{ + if (!treetop) return; + bzero((char *)quad_flag, + (QT_BLOCK(treetop-1)+1)*QT_BLOCK_SIZE/(8*sizeof(int4))); +} + + qtFree(qt) /* free a quadtree */ register QUADTREE qt; { @@ -72,14 +83,18 @@ qtDone() /* free EVERYTHING */ for (i = 0; i < QT_MAX_BLK; i++) { - free((char *)quad_block[i], - (unsigned)QT_BLOCK_SIZE*4*sizeof(QUADTREE)); + if (quad_block[i] == NULL) + break; + free((char *)quad_block[i]); quad_block[i] = NULL; } + if (i) free((char *)quad_flag); + quad_flag = NULL; quad_free_list = EMPTY; treetop = 0; } + QUADTREE qtCompress(qt) /* recursively combine nodes */ register QUADTREE qt; @@ -101,21 +116,232 @@ register QUADTREE qt; return(qres); } + QUADTREE -qtPoint_locate(qtptr,v1,v2,v3,pt,type,which,p0,p1,p2) +*qtLocate_leaf(qtptr,bcoord,t0,t1,t2) QUADTREE *qtptr; -FVECT v1,v2,v3; +double bcoord[3]; +FVECT t0,t1,t2; +{ + int i; + QUADTREE *child; + FVECT a,b,c; + + if(QT_IS_TREE(*qtptr)) + { + i = bary2d_child(bcoord); + child = QT_NTH_CHILD_PTR(*qtptr,i); + if(t0) + { + qtSubdivide_tri(t0,t1,t2,a,b,c); + qtNth_child_tri(t0,t1,t2,a,b,c,i,t0,t1,t2); + } + return(qtLocate_leaf(child,bcoord,t0,t1,t2)); + } + else + return(qtptr); +} + + + +int +qtLeaf_add_tri_from_pt(qtptr,bcoord,id,v0,v1,v2,n) +QUADTREE *qtptr; +double bcoord[3]; +int id; +FVECT v0,v1,v2; +int n; +{ + int i; + QUADTREE *child; + OBJECT os[MAXSET+1],*optr; + int found; + FVECT r0,r1,r2; + + if(QT_IS_TREE(*qtptr)) + { + QT_SET_FLAG(*qtptr); + i = bary2d_child(bcoord); + child = QT_NTH_CHILD_PTR(*qtptr,i); + return(qtLeaf_add_tri_from_pt(child,bcoord,id,v0,v1,v2,++n)); + } + else + { + /* If this leave node emptry- create a new set */ + if(QT_IS_EMPTY(*qtptr)) + *qtptr = qtaddelem(*qtptr,id); + else + { + qtgetset(os,*qtptr); + /* If the set is too large: subdivide */ + if(QT_SET_CNT(os) < QT_SET_THRESHOLD) + *qtptr = qtaddelem(*qtptr,id); + else + { + if (n < QT_MAX_LEVELS) + { + /* If set size exceeds threshold: subdivide cell and + reinsert set tris into cell + */ + n++; + qtfreeleaf(*qtptr); + qtSubdivide(qtptr); + QT_SET_FLAG(*qtptr); + found = qtLeaf_add_tri_from_pt(qtptr,bcoord,id,v0,v1,v2,n); +#if 0 + if(!found) + { +#ifdef TEST_DRIVER + HANDLE_ERROR("qtAdd_tri():Found in parent but not children\n"); +#else + eputs("qtAdd_tri():Found in parent but not children\n"); +#endif + } +#endif + for(optr = &(os[1]),i = QT_SET_CNT(os); i > 0; i--) + { + id = QT_SET_NEXT_ELEM(optr); + qtTri_verts_from_id(id,r0,r1,r2); + found= qtLeaf_add_tri_from_pt(qtptr,bcoord,id,v0,v1,v2,++n); +#ifdef DEBUG + if(!found) + eputs("qtAdd_tri():Reinsert-in parent but not children\n"); +#endif + } + } + else + if(QT_SET_CNT(os) < QT_MAX_SET) + { + *qtptr = qtaddelem(*qtptr,id); + } + else + { +#ifdef DEBUG + eputs("qtAdd_tri():two many levels\n"); +#endif + return(FALSE); + } + } + } + } + return(TRUE); +} + + +int +qtAdd_tri_from_point(qtptr,v0,v1,v2,pt,id) +QUADTREE *qtptr; +FVECT v0,v1,v2; FVECT pt; -char *type,*which; -FVECT p0,p1,p2; +int id; { char d,w; - int i; + int i,x,y; QUADTREE *child; QUADTREE qt; - FVECT a,b,c; - FVECT t1,t2,t3; + FVECT i_pt,n,a,b,c,r0,r1,r2; + double pd,bcoord[3]; + OBJECT os[MAXSET+1],*optr; + int found; + + /* Determine if point lies within pyramid (and therefore + inside a spherical quadtree cell):GT_INTERIOR, on one of the + pyramid sides (and on cell edge):GT_EDGE(1,2 or 3), + or on pyramid vertex (and on cell vertex):GT_VERTEX(1,2, or 3). + For each triangle edge: compare the + point against the plane formed by the edge and the view center + */ + d = test_single_point_against_spherical_tri(v0,v1,v2,pt,&w); + /* Not in this triangle */ + if(!d) + return(FALSE); + + /* Will return lowest level triangle containing point: It the + point is on an edge or vertex: will return first associated + triangle encountered in the child traversal- the others can + be derived using triangle adjacency information + */ + if(QT_IS_TREE(*qtptr)) + { + QT_SET_FLAG(*qtptr); + /* Find the intersection point */ + tri_plane_equation(v0,v1,v2,n,&pd,FALSE); + intersect_vector_plane(pt,n,pd,NULL,i_pt); + + i = max_index(n); + x = (i+1)%3; + y = (i+2)%3; + /* Calculate barycentric coordinates of i_pt */ + bary2d(v0[x],v0[y],v1[x],v1[y],v2[x],v2[y],i_pt[x],i_pt[y],bcoord); + + i = bary2d_child(bcoord); + child = QT_NTH_CHILD_PTR(*qtptr,i); + /* NOTE: Optimize: only subdivide for specified child */ + qtSubdivide_tri(v0,v1,v2,a,b,c); + qtNth_child_tri(v0,v1,v2,a,b,c,i,v0,v1,v2); + return(qtLeaf_add_tri_from_pt(child,bcoord,id,v0,v1,v2,1)); + } + else + { + /* If this leave node emptry- create a new set */ + if(QT_IS_EMPTY(*qtptr)) + *qtptr = qtaddelem(*qtptr,id); + else + { + qtgetset(os,*qtptr); + /* If the set is too large: subdivide */ + if(QT_SET_CNT(os) < QT_SET_THRESHOLD) + *qtptr = qtaddelem(*qtptr,id); + else + { + /* If set size exceeds threshold: subdivide cell and + reinsert set tris into cell + */ + qtfreeleaf(*qtptr); + qtSubdivide(qtptr); + found = qtLeaf_add_tri_from_pt(qtptr,bcoord,id,v0,v1,v2,1); +#if 0 + if(!found) + { +#ifdef TEST_DRIVER + HANDLE_ERROR("qtAdd_tri():Found in parent but not children\n"); +#else + eputs("qtAdd_tri():Found in parent but not children\n"); +#endif + } +#endif + for(optr = &(os[1]),i = QT_SET_CNT(os); i > 0; i--) + { + id = QT_SET_NEXT_ELEM(optr); + qtTri_verts_from_id(id,r0,r1,r2); + found=qtAdd_tri(qtptr,id,r0,r1,r2,v0,v1,v2,1); +#ifdef DEBUG + if(!found) + eputs("qtAdd_tri():Reinsert-in parent but not children\n"); +#endif + } + } + } + } + return(TRUE); +} + + +QUADTREE +*qtRoot_point_locate(qtptr,v0,v1,v2,pt,t0,t1,t2) +QUADTREE *qtptr; +FVECT v0,v1,v2; +FVECT pt; +FVECT t0,t1,t2; +{ + char d,w; + int i,x,y; + QUADTREE *child; + QUADTREE qt; + FVECT n,i_pt,a,b,c; + double pd,bcoord[3]; + /* Determine if point lies within pyramid (and therefore inside a spherical quadtree cell):GT_INTERIOR, on one of the pyramid sides (and on cell edge):GT_EDGE(1,2 or 3), @@ -123,14 +349,12 @@ FVECT p0,p1,p2; For each triangle edge: compare the point against the plane formed by the edge and the view center */ - d = test_single_point_against_spherical_tri(v1,v2,v3,pt,&w); + d = test_single_point_against_spherical_tri(v0,v1,v2,pt,&w); /* Not in this triangle */ if(!d) { - if(which) - *which = 0; - return(EMPTY); + return(NULL); } /* Will return lowest level triangle containing point: It the @@ -138,55 +362,29 @@ FVECT p0,p1,p2; triangle encountered in the child traversal- the others can be derived using triangle adjacency information */ - if(QT_IS_TREE(*qtptr)) { - qtSubdivide_tri(v1,v2,v3,a,b,c); - child = QT_NTH_CHILD_PTR(*qtptr,0); - if(!QT_IS_EMPTY(*child)) + /* Find the intersection point */ + tri_plane_equation(v0,v1,v2,n,&pd,FALSE); + intersect_vector_plane(pt,n,pd,NULL,i_pt); + + i = max_index(n); + x = (i+1)%3; + y = (i+2)%3; + /* Calculate barycentric coordinates of i_pt */ + bary2d(v0[x],v0[y],v1[x],v1[y],v2[x],v2[y],i_pt[x],i_pt[y],bcoord); + + i = bary2d_child(bcoord); + child = QT_NTH_CHILD_PTR(*qtptr,i); + if(t0) { - qt = qtPoint_locate(child,v1,a,c,pt,type,which,p0,p1,p2); - if(!QT_IS_EMPTY(qt)) - return(qt); + qtSubdivide_tri(v0,v1,v2,a,b,c); + qtNth_child_tri(v0,v1,v2,a,b,c,i,t0,t1,t2); } - child = QT_NTH_CHILD_PTR(*qtptr,1); - if(!QT_IS_EMPTY(*child)) - { - qt = qtPoint_locate(child,a,b,c,pt,type,which,p0,p1,p2); - if(!QT_IS_EMPTY(qt)) - return(qt); - } - child = QT_NTH_CHILD_PTR(*qtptr,2); - if(!QT_IS_EMPTY(*child)) - { - qt = qtPoint_locate(child,a,v2,b,pt,type,which,p0,p1,p2); - if(!QT_IS_EMPTY(qt)) - return(qt); - } - child = QT_NTH_CHILD_PTR(*qtptr,3); - if(!QT_IS_EMPTY(*child)) - { - qt = qtPoint_locate(child,c,b,v3,pt,type,which,p0,p1,p2); - if(!QT_IS_EMPTY(qt)) - return(qt); - } + return(qtLocate_leaf(child,bcoord,t0,t1,t2)); } else - if(!QT_IS_EMPTY(*qtptr)) - { - /* map GT_VERTEX,GT_EDGE,GT_FACE GT_INTERIOR of pyramid to - spherical triangle primitives - */ - if(type) - *type = d; - if(which) - *which = w; - VCOPY(p0,v1); - VCOPY(p1,v2); - VCOPY(p2,v3); - return(*qtptr); - } - return(EMPTY); + return(qtptr); } int @@ -196,18 +394,18 @@ FVECT v0,v1,v2; FVECT pt; char *type,*which; { - QUADTREE qt; OBJECT os[MAXSET+1],*optr; char d,w; int i,id; FVECT p0,p1,p2; - - qt = qtPoint_locate(qtptr,v0,v1,v2,pt,type,which,p0,p1,p2); - if(QT_IS_EMPTY(qt)) + + qtptr = qtRoot_point_locate(qtptr,v0,v1,v2,pt,NULL,NULL,NULL); + + if(!qtptr || QT_IS_EMPTY(*qtptr)) return(EMPTY); /* Get the set */ - qtgetset(os,qt); + qtgetset(os,*qtptr); for (i = QT_SET_CNT(os),optr = QT_SET_PTR(os); i > 0; i--) { /* Find the triangle that pt falls in (NOTE:FOR now return first 1) */ @@ -250,51 +448,45 @@ int n; return(node); } -/* for triangle v1-v2-v3- returns a,b,c: children are: +/* for triangle v0-v1-v2- returns a,b,c: children are: - v3 0: v1,a,c - /\ 1: a,b,c - /3 \ 2: a,v2,b - c/____\b 3: c,b,v3 + v2 0: v0,a,c + /\ 1: a,v1,b + /2 \ 2: c,b,v2 + c/____\b 3: b,c,a /\ /\ - /0 \1 /2 \ - v1/____\/____\v2 + /0 \3 /1 \ + v0____\/____\v1 a */ -qtSubdivide_tri(v1,v2,v3,a,b,c) -FVECT v1,v2,v3; +qtSubdivide_tri(v0,v1,v2,a,b,c) +FVECT v0,v1,v2; FVECT a,b,c; { - EDGE_MIDPOINT_VEC3(a,v1,v2); - normalize(a); - EDGE_MIDPOINT_VEC3(b,v2,v3); - normalize(b); - EDGE_MIDPOINT_VEC3(c,v3,v1); - normalize(c); + EDGE_MIDPOINT_VEC3(a,v0,v1); + EDGE_MIDPOINT_VEC3(b,v1,v2); + EDGE_MIDPOINT_VEC3(c,v2,v0); } -qtNth_child_tri(v1,v2,v3,a,b,c,i,r1,r2,r3) -FVECT v1,v2,v3; +qtNth_child_tri(v0,v1,v2,a,b,c,i,r0,r1,r2) +FVECT v0,v1,v2; FVECT a,b,c; int i; -FVECT r1,r2,r3; +FVECT r0,r1,r2; { - VCOPY(r1,a); VCOPY(r2,b); VCOPY(r3,c); switch(i){ case 0: - VCOPY(r2,r1); - VCOPY(r1,v1); + VCOPY(r0,v0); VCOPY(r1,a); VCOPY(r2,c); break; case 1: + VCOPY(r0,a); VCOPY(r1,v1); VCOPY(r2,b); break; case 2: - VCOPY(r3,r2); - VCOPY(r2,v2); + VCOPY(r0,c); VCOPY(r1,b); VCOPY(r2,v2); break; case 3: - VCOPY(r1,r3); - VCOPY(r3,v3); + VCOPY(r0,b); VCOPY(r1,c); VCOPY(r2,a); break; } } @@ -308,39 +500,78 @@ into the new child cells: it is assumed that "v1,v2,v3 */ int -qtAdd_tri(qtptr,id,t1,t2,t3,v1,v2,v3,n) +qtRoot_add_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n) QUADTREE *qtptr; int id; -FVECT t1,t2,t3; -FVECT v1,v2,v3; +FVECT t0,t1,t2; +FVECT v0,v1,v2; int n; { + char test; + int found; + + test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2); + if(!test) + return(FALSE); + found = qtAdd_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n); + return(found); +} + +int +qtRoot_add_tri_from_point(qtptr,id,t0,t1,t2,v0,v1,v2,n) +QUADTREE *qtptr; +int id; +FVECT t0,t1,t2; +FVECT v0,v1,v2; +int n; +{ char test; + int found; + + test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2); + if(!test) + return(FALSE); + + found = qtAdd_tri_from_point(qtptr,id,t0,t1,t2,v0,v1,v2,n); + return(found); +} + +int +qtAdd_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n) +QUADTREE *qtptr; +int id; +FVECT t0,t1,t2; +FVECT v0,v1,v2; +int n; +{ + + char test; int i,index; FVECT a,b,c; OBJECT os[MAXSET+1],*optr; QUADTREE qt; int found; - FVECT r1,r2,r3; + FVECT r0,r1,r2; - /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */ - test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3); - - /* If triangles do not overlap: done */ - if(!test) - return(FALSE); found = 0; - /* if this is tree: recurse */ if(QT_IS_TREE(*qtptr)) { n++; - qtSubdivide_tri(v1,v2,v3,a,b,c); - found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t1,t2,t3,v1,a,c,n); - found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t1,t2,t3,a,b,c,n); - found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t1,t2,t3,a,v2,b,n); - found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t1,t2,t3,c,b,v3,n); + qtSubdivide_tri(v0,v1,v2,a,b,c); + test = spherical_tri_intersect(t0,t1,t2,v0,a,c); + if(test) + found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t0,t1,t2,v0,a,c,n); + test = spherical_tri_intersect(t0,t1,t2,a,v1,b); + if(test) + found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t0,t1,t2,a,v1,b,n); + test = spherical_tri_intersect(t0,t1,t2,c,b,v2); + if(test) + found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t0,t1,t2,c,b,v2,n); + test = spherical_tri_intersect(t0,t1,t2,b,c,a); + if(test) + found |= qtAdd_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t0,t1,t2,b,c,a,n); #if 0 if(!found) @@ -357,47 +588,13 @@ int n; { /* If this leave node emptry- create a new set */ if(QT_IS_EMPTY(*qtptr)) - { - *qtptr = qtaddelem(*qtptr,id); -#if 0 - { - int k; - qtgetset(os,*qtptr); - printf("\n%d:\n",os[0]); - for(k=1; k <= os[0];k++) - printf("%d ",os[k]); - printf("\n"); - } -#endif - /* - os[0] = 0; - insertelem(os,id); - qt = fullnode(os); - *qtptr = qt; - */ - } + *qtptr = qtaddelem(*qtptr,id); else { qtgetset(os,*qtptr); /* If the set is too large: subdivide */ if(QT_SET_CNT(os) < QT_SET_THRESHOLD) - { *qtptr = qtaddelem(*qtptr,id); -#if 0 - { - int k; - qtgetset(os,*qtptr); - printf("\n%d:\n",os[0]); - for(k=1; k <= os[0];k++) - printf("%d ",os[k]); - printf("\n"); - } -#endif - /* - insertelem(os,id); - *qtptr = fullnode(os); - */ - } else { if (n < QT_MAX_LEVELS) @@ -408,7 +605,7 @@ int n; n++; qtfreeleaf(*qtptr); qtSubdivide(qtptr); - found = qtAdd_tri(qtptr,id,t1,t2,t3,v1,v2,v3,n); + found = qtAdd_tri(qtptr,id,t0,t1,t2,v0,v1,v2,n); #if 0 if(!found) { @@ -422,8 +619,8 @@ int n; for(optr = &(os[1]),i = QT_SET_CNT(os); i > 0; i--) { id = QT_SET_NEXT_ELEM(optr); - qtTri_verts_from_id(id,r1,r2,r3); - found=qtAdd_tri(qtptr,id,r1,r2,r3,v1,v2,v3,n); + qtTri_verts_from_id(id,r0,r1,r2); + found=qtAdd_tri(qtptr,id,r0,r1,r2,v0,v1,v2,n); #ifdef DEBUG if(!found) eputs("qtAdd_tri():Reinsert-in parent but not children\n"); @@ -464,18 +661,18 @@ int n; int -qtApply_to_tri_cells(qtptr,t1,t2,t3,v1,v2,v3,func,arg) +qtApply_to_tri_cells(qtptr,t0,t1,t2,v0,v1,v2,func,arg) QUADTREE *qtptr; -FVECT t1,t2,t3; -FVECT v1,v2,v3; +FVECT t0,t1,t2; +FVECT v0,v1,v2; int (*func)(); char *arg; { char test; FVECT a,b,c; - /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */ - test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3); + /* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */ + test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2); /* If triangles do not overlap: done */ if(!test) @@ -484,11 +681,11 @@ char *arg; /* if this is tree: recurse */ if(QT_IS_TREE(*qtptr)) { - qtSubdivide_tri(v1,v2,v3,a,b,c); - qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,0),t1,t2,t3,v1,a,c,func,arg); - qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,1),t1,t2,t3,a,b,c,func,arg); - qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,2),t1,t2,t3,a,v2,b,func,arg); - qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,3),t1,t2,t3,c,b,v3,func,arg); + qtSubdivide_tri(v0,v1,v2,a,b,c); + qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,0),t0,t1,t2,v0,a,c,func,arg); + qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,1),t0,t1,t2,a,v1,b,func,arg); + qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,2),t0,t1,t2,c,b,v2,func,arg); + qtApply_to_tri_cells(QT_NTH_CHILD_PTR(*qtptr,3),t0,t1,t2,b,c,a,func,arg); } else return(func(qtptr,arg)); @@ -496,11 +693,11 @@ char *arg; int -qtRemove_tri(qtptr,id,t1,t2,t3,v1,v2,v3) +qtRemove_tri(qtptr,id,t0,t1,t2,v0,v1,v2) QUADTREE *qtptr; int id; -FVECT t1,t2,t3; -FVECT v1,v2,v3; +FVECT t0,t1,t2; +FVECT v0,v1,v2; { char test; @@ -508,8 +705,8 @@ FVECT v1,v2,v3; FVECT a,b,c; OBJECT os[MAXSET+1]; - /* test if triangle (t1,t2,t3) overlaps cell triangle (v1,v2,v3) */ - test = spherical_tri_intersect(t1,t2,t3,v1,v2,v3); + /* test if triangle (t0,t1,t2) overlaps cell triangle (v0,v1,v2) */ + test = spherical_tri_intersect(t0,t1,t2,v0,v1,v2); /* If triangles do not overlap: done */ if(!test) @@ -518,11 +715,11 @@ FVECT v1,v2,v3; /* if this is tree: recurse */ if(QT_IS_TREE(*qtptr)) { - qtSubdivide_tri(v1,v2,v3,a,b,c); - qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t1,t2,t3,v1,a,c); - qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t1,t2,t3,a,b,c); - qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t1,t2,t3,a,v2,b); - qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t1,t2,t3,c,b,v3); + qtSubdivide_tri(v0,v1,v2,a,b,c); + qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,0),id,t0,t1,t2,v0,a,c); + qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,1),id,t0,t1,t2,a,v1,b); + qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,2),id,t0,t1,t2,c,b,v2); + qtRemove_tri(QT_NTH_CHILD_PTR(*qtptr,3),id,t0,t1,t2,b,c,a); } else { @@ -545,21 +742,20 @@ FVECT v1,v2,v3; else { *qtptr = qtdelelem(*qtptr,id); -#if 0 - { - int k; - if(!QT_IS_EMPTY(*qtptr)) - {qtgetset(os,*qtptr); - printf("\n%d:\n",os[0]); - for(k=1; k <= os[0];k++) - printf("%d ",os[k]); - printf("\n"); - } - - } -#endif } } } return(TRUE); } + + + + + + + + + + + +