1 |
– |
/* Copyright (c) 1998 Silicon Graphics, Inc. */ |
2 |
– |
|
1 |
|
#ifndef lint |
2 |
< |
static char SCCSid[] = "$SunId$ SGI"; |
2 |
> |
static const char RCSid[] = "$Id$"; |
3 |
|
#endif |
6 |
– |
|
4 |
|
/* |
5 |
|
* sm_stree.c |
6 |
|
* An stree (spherical quadtree) is defined by an octahedron in |
13 |
|
#include "sm_list.h" |
14 |
|
#include "sm_flag.h" |
15 |
|
#include "sm_geom.h" |
16 |
+ |
#include "object.h" |
17 |
|
#include "sm_qtree.h" |
18 |
|
#include "sm_stree.h" |
19 |
|
|
20 |
+ |
|
21 |
|
#ifdef TEST_DRIVER |
22 |
|
extern FVECT Pick_point[500],Pick_v0[500],Pick_v1[500],Pick_v2[500]; |
23 |
|
extern int Pick_cnt; |
62 |
|
{ |
63 |
|
int i,j; |
64 |
|
|
65 |
< |
ST_TOP_QT(st) = qtAlloc(); |
67 |
< |
ST_BOTTOM_QT(st) = qtAlloc(); |
68 |
< |
/* Clear the children */ |
65 |
> |
qtDone(); |
66 |
|
|
67 |
+ |
ST_TOP_QT(st) = qtAlloc(); |
68 |
+ |
ST_BOTTOM_QT(st) = qtAlloc(); |
69 |
+ |
/* Clear the children */ |
70 |
+ |
|
71 |
|
QT_CLEAR_CHILDREN(ST_TOP_QT(st)); |
72 |
|
QT_CLEAR_CHILDREN(ST_BOTTOM_QT(st)); |
73 |
|
} |
74 |
|
|
75 |
< |
/* Frees the children of the 2 quadtrees rooted at st, |
76 |
< |
Does not free root nodes: just clears |
76 |
< |
*/ |
77 |
< |
stClear(st) |
78 |
< |
STREE *st; |
75 |
> |
stFree(st) |
76 |
> |
STREE *st; |
77 |
|
{ |
78 |
< |
qtDone(); |
79 |
< |
stInit(st); |
78 |
> |
qtDone(); |
79 |
> |
free(st); |
80 |
|
} |
81 |
|
|
82 |
|
/* Allocates a stree structure and creates octahedron base */ |
95 |
|
/* Allocate the top and bottom quadtree root nodes */ |
96 |
|
stInit(st); |
97 |
|
|
100 |
– |
|
101 |
– |
/* will go ********************************************/ |
102 |
– |
/* Set the octahedron base */ |
103 |
– |
ST_SET_BASE(st,stDefault_base); |
104 |
– |
|
105 |
– |
/* Calculate octahedron face and edge normals */ |
106 |
– |
for(i=0; i < ST_NUM_ROOT_NODES; i++) |
107 |
– |
{ |
108 |
– |
VCOPY(v0,ST_NTH_V(st,i,0)); |
109 |
– |
VCOPY(v1,ST_NTH_V(st,i,1)); |
110 |
– |
VCOPY(v2,ST_NTH_V(st,i,2)); |
111 |
– |
tri_plane_equation(v0,v1,v2, &ST_NTH_PLANE(st,i),FALSE); |
112 |
– |
m = max_index(FP_N(ST_NTH_PLANE(st,i)),NULL); |
113 |
– |
FP_X(ST_NTH_PLANE(st,i)) = (m+1)%3; |
114 |
– |
FP_Y(ST_NTH_PLANE(st,i)) = (m+2)%3; |
115 |
– |
FP_Z(ST_NTH_PLANE(st,i)) = m; |
116 |
– |
VCROSS(ST_EDGE_NORM(st,i,0),v0,v1); |
117 |
– |
VCROSS(ST_EDGE_NORM(st,i,1),v1,v2); |
118 |
– |
VCROSS(ST_EDGE_NORM(st,i,2),v2,v0); |
119 |
– |
} |
120 |
– |
|
121 |
– |
/*****************************************************************/ |
98 |
|
return(st); |
99 |
|
} |
100 |
|
|
399 |
|
|
400 |
|
if(QT_FLAG_IS_DONE(f)) |
401 |
|
return(TRUE); |
402 |
< |
/* |
402 |
> |
/* |
403 |
|
d = DOT(orig,dir)/sqrt(DOT(orig,orig)); |
404 |
|
VSUM(v,orig,dir,-d); |
405 |
|
*/ |
425 |
|
} |
426 |
|
|
427 |
|
|
428 |
< |
stVisit_poly(st,verts,l,root,func) |
428 |
> |
stVisit_poly(st,verts,l,root,func,n) |
429 |
|
STREE *st; |
430 |
|
FVECT *verts; |
431 |
|
LIST *l; |
432 |
|
unsigned int root; |
433 |
|
FUNC func; |
434 |
+ |
int n; |
435 |
|
{ |
436 |
|
int id0,id1,id2; |
437 |
|
FVECT tri[3]; |
444 |
|
VCOPY(tri[0],verts[id0]); |
445 |
|
VCOPY(tri[1],verts[id1]); |
446 |
|
VCOPY(tri[2],verts[id2]); |
447 |
< |
stRoot_visit_tri(st,root,tri,func); |
447 |
> |
stRoot_visit_tri(st,root,tri,func,n); |
448 |
|
id1 = id2; |
449 |
|
} |
450 |
|
} |
451 |
+ |
/* Assumption: know crosses plane:dont need to check for 'on' case */ |
452 |
+ |
intersect_edge_coord_plane(v0,v1,w,r) |
453 |
+ |
FVECT v0,v1; |
454 |
+ |
int w; |
455 |
+ |
FVECT r; |
456 |
+ |
{ |
457 |
+ |
FVECT dv; |
458 |
+ |
int wnext; |
459 |
+ |
double t; |
460 |
|
|
461 |
< |
stVisit_clip(st,i,verts,vcnt,l,cell,func) |
461 |
> |
VSUB(dv,v1,v0); |
462 |
> |
t = -v0[w]/dv[w]; |
463 |
> |
r[w] = 0.0; |
464 |
> |
wnext = (w+1)%3; |
465 |
> |
r[wnext] = v0[wnext] + dv[wnext]*t; |
466 |
> |
wnext = (w+2)%3; |
467 |
> |
r[wnext] = v0[wnext] + dv[wnext]*t; |
468 |
> |
} |
469 |
> |
|
470 |
> |
|
471 |
> |
stVisit_clip(st,i,verts,vcnt,l,cell,func,n) |
472 |
|
STREE *st; |
473 |
|
int i; |
474 |
|
FVECT *verts; |
476 |
|
LIST *l; |
477 |
|
unsigned int cell; |
478 |
|
FUNC func; |
479 |
+ |
int n; |
480 |
|
{ |
481 |
|
|
482 |
|
LIST *labove,*lbelow,*endb,*enda; |
568 |
|
if(LIST_NEXT(lbelow) && LIST_NEXT(LIST_NEXT(lbelow))) |
569 |
|
{ |
570 |
|
cellb = cell | (1 << i); |
571 |
< |
stVisit_poly(st,verts,lbelow,cellb,func); |
571 |
> |
stVisit_poly(st,verts,lbelow,cellb,func,n); |
572 |
|
} |
573 |
|
else |
574 |
|
free_list(lbelow); |
576 |
|
if(labove) |
577 |
|
{ |
578 |
|
if(LIST_NEXT(labove) && LIST_NEXT(LIST_NEXT(labove))) |
579 |
< |
stVisit_poly(st,verts,labove,cell,func); |
579 |
> |
stVisit_poly(st,verts,labove,cell,func,n); |
580 |
|
else |
581 |
|
free_list(labove); |
582 |
|
} |
588 |
|
if(LIST_NEXT(lbelow) && LIST_NEXT(LIST_NEXT(lbelow))) |
589 |
|
{ |
590 |
|
cellb = cell | (1 << i); |
591 |
< |
stVisit_clip(st,i+1,verts,vcnt,lbelow,cellb,func); |
591 |
> |
stVisit_clip(st,i+1,verts,vcnt,lbelow,cellb,func,n); |
592 |
|
} |
593 |
|
else |
594 |
|
free_list(lbelow); |
596 |
|
if(labove) |
597 |
|
{ |
598 |
|
if(LIST_NEXT(labove) && LIST_NEXT(LIST_NEXT(labove))) |
599 |
< |
stVisit_clip(st,i+1,verts,vcnt,labove,cell,func); |
599 |
> |
stVisit_clip(st,i+1,verts,vcnt,labove,cell,func,n); |
600 |
|
else |
601 |
|
free_list(labove); |
602 |
|
} |
604 |
|
|
605 |
|
} |
606 |
|
|
607 |
< |
stVisit(st,tri,func) |
607 |
> |
stVisit(st,tri,func,n) |
608 |
|
STREE *st; |
609 |
|
FVECT tri[3]; |
610 |
|
FUNC func; |
611 |
+ |
int n; |
612 |
|
{ |
613 |
|
int r0,r1,r2; |
614 |
|
LIST *l; |
617 |
|
r1 = stLocate_root(tri[1]); |
618 |
|
r2 = stLocate_root(tri[2]); |
619 |
|
if(r0 == r1 && r1==r2) |
620 |
< |
stRoot_visit_tri(st,r0,tri,func); |
620 |
> |
stRoot_visit_tri(st,r0,tri,func,n); |
621 |
|
else |
622 |
|
{ |
623 |
|
FVECT verts[ST_CLIP_VERTS]; |
631 |
|
l = add_data(l,1,NULL); |
632 |
|
l = add_data(l,2,NULL); |
633 |
|
cnt = 3; |
634 |
< |
stVisit_clip(st,0,verts,&cnt,l,0,func); |
634 |
> |
stVisit_clip(st,0,verts,&cnt,l,0,func,n); |
635 |
|
} |
636 |
|
} |
637 |
|
|
638 |
|
|
641 |
– |
/* New Insertion code!!! */ |
642 |
– |
|
643 |
– |
|
639 |
|
BCOORD qtRoot[3][3] = { {MAXBCOORD2,0,0},{0,MAXBCOORD2,0},{0,0,MAXBCOORD2}}; |
640 |
|
|
641 |
|
|
684 |
|
return(qt); |
685 |
|
} |
686 |
|
|
687 |
< |
stRoot_visit_tri(st,root,tri,f) |
687 |
> |
stRoot_visit_tri(st,root,tri,f,n) |
688 |
|
STREE *st; |
689 |
|
int root; |
690 |
|
FVECT tri[3]; |
691 |
|
FUNC f; |
692 |
+ |
int n; |
693 |
|
{ |
694 |
|
BCOORD b0[3],b1[3],b2[3]; |
695 |
|
BCOORD db10[3],db21[3],db02[3]; |
707 |
|
QT_SET_FLAG(ST_QT(st,root)); |
708 |
|
/* Visit cells that triangle intersects */ |
709 |
|
qtVisit_tri(root,qt,qtRoot[0],qtRoot[1],qtRoot[2], |
710 |
< |
b0,b1,b2,db10,db21,db02,MAXBCOORD2 >> 1,s0,s1,s2, sq0,sq1,sq2,f); |
710 |
> |
b0,b1,b2,db10,db21,db02,MAXBCOORD2 >> 1,s0,s1,s2, sq0,sq1,sq2,f,n); |
711 |
|
|
712 |
|
} |
713 |
|
|
737 |
|
} |
738 |
|
} |
739 |
|
|
740 |
+ |
stInsert_samp(st,p,f) |
741 |
+ |
STREE *st; |
742 |
+ |
FVECT p; |
743 |
+ |
FUNC f; |
744 |
+ |
{ |
745 |
+ |
|
746 |
+ |
QUADTREE qt; |
747 |
+ |
BCOORD bcoordi[3]; |
748 |
+ |
int i,done; |
749 |
+ |
|
750 |
+ |
/* Find root quadtree that contains p */ |
751 |
+ |
i = stLocate_root(p); |
752 |
+ |
qt = ST_ROOT_QT(st,i); |
753 |
+ |
|
754 |
+ |
vert_to_qt_frame(i,p,bcoordi); |
755 |
+ |
ST_ROOT_QT(st,i) = qtInsert_point(i,qt,EMPTY,qtRoot[0],qtRoot[1], |
756 |
+ |
qtRoot[2],bcoordi,MAXBCOORD2>>1,f,0,&done); |
757 |
+ |
|
758 |
+ |
} |
759 |
|
|
760 |
|
|
761 |
|
|