src/hd/sm_stree.c

/* Copyright (c) 1998 Silicon Graphics, Inc. */

#ifndef lint
static char SCCSid[] = "$SunId$ SGI";
#endif

/*
 * sm_stree.c
 */
#include "standard.h"
#include "object.h"

#include "sm_geom.h"
#include "sm_stree.h"


/* Define 4 vertices on the sphere to create a tetrahedralization on 
   the sphere: triangles are as follows:
        (0,1,2),(0,2,3), (0,3,1), (1,3,2)
*/

FVECT stDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV},
                          {-SQRT3_INV, -SQRT3_INV, SQRT3_INV},
                          {-SQRT3_INV, SQRT3_INV, -SQRT3_INV},
                          {SQRT3_INV, -SQRT3_INV, -SQRT3_INV}};
int stTri_verts[4][3] = { {2,1,0}, 
                          {3,2,0}, 
                          {1,3,0}, 
                          {2,3,1}};

stNth_base_verts(st,i,v1,v2,v3)
STREE *st;
int i;
FVECT v1,v2,v3;
{
  VCOPY(v1,ST_NTH_BASE(st,stTri_verts[i][0]));
  VCOPY(v2,ST_NTH_BASE(st,stTri_verts[i][1]));
  VCOPY(v3,ST_NTH_BASE(st,stTri_verts[i][2]));
}

/* Frees the 4 quadtrees rooted at st */
stClear(st)
STREE *st;
{
  int i;

  /* stree always has 4 children corresponding to the base tris
  */
  for (i = 0; i < 4; i++)
    qtFree(ST_NTH_ROOT(st, i));

  QT_CLEAR_CHILDREN(ST_ROOT(st));

}


STREE
*stInit(st,center,base)
STREE *st;
FVECT  center,base[4];
{

  if(base)
    ST_SET_BASE(st,base);
  else
    ST_SET_BASE(st,stDefault_base);

  ST_SET_CENTER(st,center);
  stClear(st);

  return(st);
}


/* "base" defines 4 vertices on the sphere to create a tetrahedralization on 
     the sphere: triangles are as follows:(0,1,2),(0,2,3), (0,3,1), (1,3,2)
     if base is null: does default.

 */
STREE
*stAlloc(st)
STREE *st;
{
  int i;

  if(!st)
    st = (STREE *)malloc(sizeof(STREE));

  ST_ROOT(st) = qtAlloc();
    
  QT_CLEAR_CHILDREN(ST_ROOT(st));

  return(st);
}


/* Find location of sample point in the DAG and return lowest level
   containing triangle. "type" indicates whether the point was found
   to be in interior to the triangle: GT_FACE, on one of its
   edges GT_EDGE or coinciding with one of its vertices GT_VERTEX.
   "which" specifies which vertex (0,1,2) or edge (0=v0v1, 1 = v1v2, 2 = v21) 
*/
int
stPoint_locate(st,npt,type,which)
    STREE *st;
    FVECT npt;
    char *type,*which;
{
    int i,d,j,id;
    QUADTREE *rootptr,*qtptr;
    FVECT v1,v2,v3;
    OBJECT os[MAXSET+1],*optr;
    char w;
    FVECT p0,p1,p2;

    /* Test each of the root triangles against point id */
    for(i=0; i < 4; i++)
     {
         rootptr = ST_NTH_ROOT_PTR(st,i);
         stNth_base_verts(st,i,v1,v2,v3);
         /* Return tri that p falls in */
         qtptr = qtRoot_point_locate(rootptr,v1,v2,v3,npt,NULL,NULL,NULL);
         if(!qtptr)
            continue;
         /* Get the set */
         qtgetset(os,*qtptr);
         for (j = QT_SET_CNT(os),optr = QT_SET_PTR(os); j > 0; j--)
         {
             /* Find the first triangle that pt falls */
             id = QT_SET_NEXT_ELEM(optr);
             qtTri_verts_from_id(id,p0,p1,p2);
             d = test_single_point_against_spherical_tri(p0,p1,p2,npt,&w);  
             if(d)
                {
                    if(type)
                       *type = d;
                    if(which)
                       *which = w;
                    return(id);
                }
         }
     }
    if(which)
      *which = 0;
    if(type)
      *type = 0;
    return(EMPTY);
}

QUADTREE
*stPoint_locate_cell(st,p,t0,t1,t2)
    STREE *st;
    FVECT p;
    FVECT t0,t1,t2;
{
    int i,d;
    QUADTREE *rootptr,*qtptr;
    FVECT v0,v1,v2;

    
    /* Test each of the root triangles against point id */
    for(i=0; i < 4; i++)
     {
         rootptr = ST_NTH_ROOT_PTR(st,i);
         stNth_base_verts(st,i,v0,v1,v2);
         /* Return tri that p falls in */
         qtptr = qtRoot_point_locate(rootptr,v0,v1,v2,p,t0,t1,t2);
         /* NOTE: For now return only one triangle */
         if(qtptr)
            return(qtptr);
     }    /* Point not found */
    return(NULL);
}


QUADTREE
*stAdd_tri_from_pt(st,p,t_id)
    STREE *st;
    FVECT p;
    int t_id;
{
    int i,d;
    QUADTREE *rootptr,*qtptr;
    FVECT v0,v1,v2;

    
    /* Test each of the root triangles against point id */
    for(i=0; i < 4; i++)
     {
         rootptr = ST_NTH_ROOT_PTR(st,i);
         stNth_base_verts(st,i,v0,v1,v2);
         /* Return tri that p falls in */
         qtptr = qtRoot_add_tri_from_point(rootptr,v0,v1,v2,p,t_id);
         /* NOTE: For now return only one triangle */
         if(qtptr)
            return(qtptr);
     }    /* Point not found */
    return(NULL);
}

int
stAdd_tri(st,id,v0,v1,v2)
STREE *st;
int id;
FVECT v0,v1,v2;
{
  
  int i,found;
  QUADTREE *rootptr;
  FVECT t0,t1,t2;

  found = 0;
  for(i=0; i < 4; i++)
  {
    rootptr = ST_NTH_ROOT_PTR(st,i);
    stNth_base_verts(st,i,t0,t1,t2);
    found |= qtRoot_add_tri(rootptr,id,v0,v1,v2,t0,t1,t2,0);
  }
  return(found);
}

int
stApply_to_tri_cells(st,v0,v1,v2,func,arg)
STREE *st;
FVECT v0,v1,v2;
int (*func)();
char *arg;
{
  int i,found;
  QUADTREE *rootptr;
  FVECT t0,t1,t2;

  found = 0;
  for(i=0; i < 4; i++)
  {
    rootptr = ST_NTH_ROOT_PTR(st,i);
    stNth_base_verts(st,i,t0,t1,t2); 
    found |= qtApply_to_tri_cells(rootptr,v0,v1,v2,t0,t1,t2,func,arg);
  }
  return(found);
}


int
stRemove_tri(st,id,v0,v1,v2)
STREE *st;
int id;
FVECT v0,v1,v2;
{
  
  int i,found;
  QUADTREE *rootptr;
  FVECT t0,t1,t2;

  found = 0;
  for(i=0; i < 4; i++)
  {
    rootptr = ST_NTH_ROOT_PTR(st,i);
    stNth_base_verts(st,i,t0,t1,t2); 
   found |= qtRemove_tri(rootptr,id,v0,v1,v2,t0,t1,t2);
  }
  return(found);
}


#if 0
int
stAdd_tri_opt(st,id,v0,v1,v2)
STREE *st;
int id;
FVECT v0,v1,v2;
{
  
  int i,found;
  QUADTREE *qtptr;
  FVECT pt,t0,t1,t2;

  /* First add all of the leaf cells lying on the triangle perimeter:
     mark all cells seen on the way
   */
  /* clear all of the flags */
  qtClearAllFlags();            /* clear all quadtree branch flags */

  /* Now trace each triangle edge-marking cells visited, and adding tri to
     the leafs
   */
  stAdd_tri_from_pt(st,v0,id,t0,t1,t2);
  /* Find next cell that projection of ray intersects */
  VCOPY(pt,v0);
  /* NOTE: Check if in same cell */
  while(traceEdge(pt,v1,t0,t1,t2,pt))
  {
      stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
      traceEdge(pt,v1,t0,t1,t2,pt);
  }
  while(traceEdge(pt,v2,t0,t1,t2,pt))
  {
      stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
      traceEdge(pt,v2,t0,t1,t2,pt);
  }
  while(traceEdge(pt,v0,t0,t1,t2,pt))
  {
      stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
      traceEdge(pt,v2,t0,t1,t2,pt);
  }

  /* NOTE: Optimization: if <= 2 cells added: dont need to fill */
  /* Traverse: follow nodes with flag set or one vertex in triangle */
  
}

#endif
Revision:	3.3
Committed:	Tue Aug 25 11:03:27 1998 UTC (25 years, 8 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.2:	+86 -17 lines
Log Message:	fixed problem with picking (ray tracking) of tetrahedron
#	User	Rev	Content
1	gwlarson	3.1	/* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ SGI";
5			#endif
6
7			/*
8			* sm_stree.c
9			*/
10			#include "standard.h"
11			#include "object.h"
12
13			#include "sm_geom.h"
14			#include "sm_stree.h"
15
16
17			/* Define 4 vertices on the sphere to create a tetrahedralization on
18			the sphere: triangles are as follows:
19			(0,1,2),(0,2,3), (0,3,1), (1,3,2)
20			*/
21
22			FVECT stDefault_base[4] = { {SQRT3_INV, SQRT3_INV, SQRT3_INV},
23			{-SQRT3_INV, -SQRT3_INV, SQRT3_INV},
24			{-SQRT3_INV, SQRT3_INV, -SQRT3_INV},
25			{SQRT3_INV, -SQRT3_INV, -SQRT3_INV}};
26			int stTri_verts[4][3] = { {2,1,0},
27			{3,2,0},
28			{1,3,0},
29			{2,3,1}};
30
31			stNth_base_verts(st,i,v1,v2,v3)
32			STREE *st;
33			int i;
34			FVECT v1,v2,v3;
35			{
36			VCOPY(v1,ST_NTH_BASE(st,stTri_verts[i][0]));
37			VCOPY(v2,ST_NTH_BASE(st,stTri_verts[i][1]));
38			VCOPY(v3,ST_NTH_BASE(st,stTri_verts[i][2]));
39			}
40
41			/* Frees the 4 quadtrees rooted at st */
42			stClear(st)
43			STREE *st;
44			{
45			int i;
46
47			/* stree always has 4 children corresponding to the base tris
48			*/
49			for (i = 0; i < 4; i++)
50			qtFree(ST_NTH_ROOT(st, i));
51
52			QT_CLEAR_CHILDREN(ST_ROOT(st));
53
54			}
55
56
57			STREE
58			*stInit(st,center,base)
59			STREE *st;
60			FVECT center,base[4];
61			{
62
63			if(base)
64			ST_SET_BASE(st,base);
65			else
66			ST_SET_BASE(st,stDefault_base);
67
68			ST_SET_CENTER(st,center);
69			stClear(st);
70
71			return(st);
72			}
73
74
75			/* "base" defines 4 vertices on the sphere to create a tetrahedralization on
76			the sphere: triangles are as follows:(0,1,2),(0,2,3), (0,3,1), (1,3,2)
77			if base is null: does default.
78
79			*/
80			STREE
81			*stAlloc(st)
82			STREE *st;
83			{
84			int i;
85
86			if(!st)
87			st = (STREE *)malloc(sizeof(STREE));
88
89			ST_ROOT(st) = qtAlloc();
90
91			QT_CLEAR_CHILDREN(ST_ROOT(st));
92
93			return(st);
94			}
95
96
97			/* Find location of sample point in the DAG and return lowest level
98			containing triangle. "type" indicates whether the point was found
99			to be in interior to the triangle: GT_FACE, on one of its
100			edges GT_EDGE or coinciding with one of its vertices GT_VERTEX.
101			"which" specifies which vertex (0,1,2) or edge (0=v0v1, 1 = v1v2, 2 = v21)
102			*/
103			int
104			stPoint_locate(st,npt,type,which)
105			STREE *st;
106			FVECT npt;
107			char type,which;
108			{
109			int i,d,j,id;
110	gwlarson	3.3	QUADTREE rootptr,qtptr;
111	gwlarson	3.1	FVECT v1,v2,v3;
112			OBJECT os[MAXSET+1],*optr;
113	gwlarson	3.2	char w;
114	gwlarson	3.1	FVECT p0,p1,p2;
115	gwlarson	3.2
116	gwlarson	3.1	/* Test each of the root triangles against point id */
117			for(i=0; i < 4; i++)
118			{
119			rootptr = ST_NTH_ROOT_PTR(st,i);
120			stNth_base_verts(st,i,v1,v2,v3);
121			/* Return tri that p falls in */
122	gwlarson	3.3	qtptr = qtRoot_point_locate(rootptr,v1,v2,v3,npt,NULL,NULL,NULL);
123			if(!qtptr)
124	gwlarson	3.1	continue;
125			/* Get the set */
126	gwlarson	3.3	qtgetset(os,*qtptr);
127	gwlarson	3.1	for (j = QT_SET_CNT(os),optr = QT_SET_PTR(os); j > 0; j--)
128			{
129			/* Find the first triangle that pt falls */
130			id = QT_SET_NEXT_ELEM(optr);
131			qtTri_verts_from_id(id,p0,p1,p2);
132			d = test_single_point_against_spherical_tri(p0,p1,p2,npt,&w);
133			if(d)
134			{
135			if(type)
136			*type = d;
137			if(which)
138			*which = w;
139			return(id);
140			}
141			}
142			}
143			if(which)
144			*which = 0;
145			if(type)
146			*type = 0;
147			return(EMPTY);
148			}
149
150	gwlarson	3.3	QUADTREE
151			*stPoint_locate_cell(st,p,t0,t1,t2)
152	gwlarson	3.1	STREE *st;
153	gwlarson	3.2	FVECT p;
154	gwlarson	3.3	FVECT t0,t1,t2;
155	gwlarson	3.1	{
156			int i,d;
157	gwlarson	3.3	QUADTREE rootptr,qtptr;
158	gwlarson	3.1	FVECT v0,v1,v2;
159
160
161			/* Test each of the root triangles against point id */
162			for(i=0; i < 4; i++)
163			{
164			rootptr = ST_NTH_ROOT_PTR(st,i);
165			stNth_base_verts(st,i,v0,v1,v2);
166			/* Return tri that p falls in */
167	gwlarson	3.3	qtptr = qtRoot_point_locate(rootptr,v0,v1,v2,p,t0,t1,t2);
168	gwlarson	3.1	/* NOTE: For now return only one triangle */
169	gwlarson	3.3	if(qtptr)
170			return(qtptr);
171	gwlarson	3.1	} /* Point not found */
172	gwlarson	3.3	return(NULL);
173	gwlarson	3.1	}
174
175	gwlarson	3.3
176			QUADTREE
177			*stAdd_tri_from_pt(st,p,t_id)
178			STREE *st;
179			FVECT p;
180			int t_id;
181			{
182			int i,d;
183			QUADTREE rootptr,qtptr;
184			FVECT v0,v1,v2;
185
186
187			/* Test each of the root triangles against point id */
188			for(i=0; i < 4; i++)
189			{
190			rootptr = ST_NTH_ROOT_PTR(st,i);
191			stNth_base_verts(st,i,v0,v1,v2);
192			/* Return tri that p falls in */
193			qtptr = qtRoot_add_tri_from_point(rootptr,v0,v1,v2,p,t_id);
194			/* NOTE: For now return only one triangle */
195			if(qtptr)
196			return(qtptr);
197			} /* Point not found */
198			return(NULL);
199			}
200
201	gwlarson	3.1	int
202	gwlarson	3.2	stAdd_tri(st,id,v0,v1,v2)
203	gwlarson	3.1	STREE *st;
204			int id;
205	gwlarson	3.2	FVECT v0,v1,v2;
206	gwlarson	3.1	{
207
208			int i,found;
209			QUADTREE *rootptr;
210	gwlarson	3.2	FVECT t0,t1,t2;
211
212	gwlarson	3.1	found = 0;
213			for(i=0; i < 4; i++)
214			{
215			rootptr = ST_NTH_ROOT_PTR(st,i);
216	gwlarson	3.2	stNth_base_verts(st,i,t0,t1,t2);
217	gwlarson	3.3	found \|= qtRoot_add_tri(rootptr,id,v0,v1,v2,t0,t1,t2,0);
218	gwlarson	3.1	}
219			return(found);
220			}
221
222			int
223			stApply_to_tri_cells(st,v0,v1,v2,func,arg)
224			STREE *st;
225			FVECT v0,v1,v2;
226			int (*func)();
227			char *arg;
228			{
229			int i,found;
230			QUADTREE *rootptr;
231			FVECT t0,t1,t2;
232
233			found = 0;
234			for(i=0; i < 4; i++)
235			{
236			rootptr = ST_NTH_ROOT_PTR(st,i);
237			stNth_base_verts(st,i,t0,t1,t2);
238			found \|= qtApply_to_tri_cells(rootptr,v0,v1,v2,t0,t1,t2,func,arg);
239			}
240			return(found);
241			}
242
243
244
245
246			int
247			stRemove_tri(st,id,v0,v1,v2)
248			STREE *st;
249			int id;
250			FVECT v0,v1,v2;
251			{
252
253			int i,found;
254			QUADTREE *rootptr;
255			FVECT t0,t1,t2;
256
257			found = 0;
258			for(i=0; i < 4; i++)
259			{
260			rootptr = ST_NTH_ROOT_PTR(st,i);
261			stNth_base_verts(st,i,t0,t1,t2);
262			found \|= qtRemove_tri(rootptr,id,v0,v1,v2,t0,t1,t2);
263			}
264			return(found);
265			}
266
267
268
269
270
271	gwlarson	3.3	#if 0
272			int
273			stAdd_tri_opt(st,id,v0,v1,v2)
274			STREE *st;
275			int id;
276			FVECT v0,v1,v2;
277			{
278
279			int i,found;
280			QUADTREE *qtptr;
281			FVECT pt,t0,t1,t2;
282
283			/* First add all of the leaf cells lying on the triangle perimeter:
284			mark all cells seen on the way
285			*/
286			/* clear all of the flags */
287			qtClearAllFlags(); /* clear all quadtree branch flags */
288
289			/* Now trace each triangle edge-marking cells visited, and adding tri to
290			the leafs
291			*/
292			stAdd_tri_from_pt(st,v0,id,t0,t1,t2);
293			/* Find next cell that projection of ray intersects */
294			VCOPY(pt,v0);
295			/* NOTE: Check if in same cell */
296			while(traceEdge(pt,v1,t0,t1,t2,pt))
297			{
298			stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
299			traceEdge(pt,v1,t0,t1,t2,pt);
300			}
301			while(traceEdge(pt,v2,t0,t1,t2,pt))
302			{
303			stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
304			traceEdge(pt,v2,t0,t1,t2,pt);
305			}
306			while(traceEdge(pt,v0,t0,t1,t2,pt))
307			{
308			stAdd_tri_from_pt(st,pt,id,t0,t1,t2);
309			traceEdge(pt,v2,t0,t1,t2,pt);
310			}
311
312			/* NOTE: Optimization: if <= 2 cells added: dont need to fill */
313			/* Traverse: follow nodes with flag set or one vertex in triangle */
314
315			}
316
317			#endif