| 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 |
|
|
| 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 |
+ |
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; |
| 636 |
|
} |
| 637 |
|
|
| 638 |
|
|
| 644 |
– |
/* New Insertion code!!! */ |
| 645 |
– |
|
| 646 |
– |
|
| 639 |
|
BCOORD qtRoot[3][3] = { {MAXBCOORD2,0,0},{0,MAXBCOORD2,0},{0,0,MAXBCOORD2}}; |
| 640 |
|
|
| 641 |
|
|
| 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 |
|
|
