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_qtree.c: adapted from octree.c from radiance code |
6 |
|
*/ |
13 |
|
#include "standard.h" |
14 |
|
#include "sm_flag.h" |
15 |
|
#include "sm_geom.h" |
16 |
+ |
#include "object.h" |
17 |
|
#include "sm_qtree.h" |
18 |
|
|
19 |
< |
QUADTREE *quad_block[QT_MAX_BLK]; /* our quadtree */ |
19 |
> |
QUADTREE *quad_block[QT_MAX_BLK]; /* our quadtree */ |
20 |
|
static QUADTREE quad_free_list = EMPTY; /* freed octree nodes */ |
21 |
< |
static QUADTREE treetop = 0; /* next free node */ |
22 |
< |
int4 *quad_flag= NULL; |
21 |
> |
static QUADTREE treetop = 0; /* next free node */ |
22 |
> |
int32 *quad_flag= NULL; /* quadtree flags */ |
23 |
|
|
26 |
– |
#ifdef TEST_DRIVER |
27 |
– |
extern FVECT Pick_v0[500],Pick_v1[500],Pick_v2[500]; |
28 |
– |
extern int Pick_cnt,Pick_tri,Pick_samp; |
29 |
– |
extern FVECT Pick_point[500]; |
30 |
– |
extern int Pick_q[500]; |
24 |
|
|
32 |
– |
#endif |
33 |
– |
|
25 |
|
qtremovelast(qt,id) |
26 |
|
QUADTREE qt; |
27 |
< |
int id; |
27 |
> |
OBJECT id; |
28 |
|
{ |
29 |
+ |
#ifdef DEBUG |
30 |
|
if(qtqueryset(qt)[(*(qtqueryset(qt)))] != id) |
31 |
|
error(CONSISTENCY,"not removed\n"); |
32 |
+ |
#endif |
33 |
|
((*(qtqueryset(qt)))--); |
34 |
|
} |
35 |
|
QUADTREE |
52 |
|
error(SYSTEM,"qtAlloc(): Unable to allocate memory\n"); |
53 |
|
|
54 |
|
/* Realloc the per/node flags */ |
55 |
< |
quad_flag = (int4 *)realloc((char *)quad_flag, |
55 |
> |
quad_flag = (int32 *)realloc((void *)quad_flag, |
56 |
|
(QT_BLOCK(freet)+1)*((QT_BLOCK_SIZE+7)>>3)); |
57 |
|
if (quad_flag == NULL) |
58 |
|
error(SYSTEM,"qtAlloc(): Unable to allocate memory\n"); |
99 |
|
{ |
100 |
|
if (quad_block[i] == NULL) |
101 |
|
break; |
102 |
< |
free((char *)quad_block[i]); |
102 |
> |
free((void *)quad_block[i]); |
103 |
|
quad_block[i] = NULL; |
104 |
|
} |
105 |
|
/* Free the flags */ |
106 |
< |
if (i) free((char *)quad_flag); |
106 |
> |
if (i) free((void *)quad_flag); |
107 |
|
quad_flag = NULL; |
108 |
|
quad_free_list = EMPTY; |
109 |
|
treetop = 0; |
110 |
|
} |
111 |
|
|
112 |
+ |
/* |
113 |
+ |
* bary_parent(coord,i) : Set coord to be value of pt at one level up in |
114 |
+ |
* quadtree, given it was the ith child |
115 |
+ |
* BCOORD coord[3]; :barycentric coordinates of point, also will hold |
116 |
+ |
* result as side effect |
117 |
+ |
* int i; :designates which child coord was |
118 |
+ |
*/ |
119 |
+ |
bary_parent(coord,i) |
120 |
+ |
BCOORD coord[3]; |
121 |
+ |
int i; |
122 |
+ |
{ |
123 |
+ |
switch(i) { |
124 |
+ |
case 0: |
125 |
+ |
/* update bary for child */ |
126 |
+ |
coord[0] = (coord[0] >> 1) + MAXBCOORD4; |
127 |
+ |
coord[1] >>= 1; |
128 |
+ |
coord[2] >>= 1; |
129 |
+ |
break; |
130 |
+ |
case 1: |
131 |
+ |
coord[0] >>= 1; |
132 |
+ |
coord[1] = (coord[1] >> 1) + MAXBCOORD4; |
133 |
+ |
coord[2] >>= 1; |
134 |
+ |
break; |
135 |
+ |
|
136 |
+ |
case 2: |
137 |
+ |
coord[0] >>= 1; |
138 |
+ |
coord[1] >>= 1; |
139 |
+ |
coord[2] = (coord[2] >> 1) + MAXBCOORD4; |
140 |
+ |
break; |
141 |
+ |
|
142 |
+ |
case 3: |
143 |
+ |
coord[0] = MAXBCOORD4 - (coord[0] >> 1); |
144 |
+ |
coord[1] = MAXBCOORD4 - (coord[1] >> 1); |
145 |
+ |
coord[2] = MAXBCOORD4 - (coord[2] >> 1); |
146 |
+ |
break; |
147 |
+ |
#ifdef DEBUG |
148 |
+ |
default: |
149 |
+ |
eputs("bary_parent():Invalid child\n"); |
150 |
+ |
break; |
151 |
+ |
#endif |
152 |
+ |
} |
153 |
+ |
} |
154 |
+ |
|
155 |
+ |
/* |
156 |
+ |
* bary_from_child(coord,child,next): Given that coord was the (child) child |
157 |
+ |
* of the quadtree node, calculate what the (next) child |
158 |
+ |
* is at the same level. |
159 |
+ |
* BCOORD coord[3]; :At current level (child)th child of node,will also hold |
160 |
+ |
* result as side effect |
161 |
+ |
* int child,next; :Which child coord was (child), and which one |
162 |
+ |
* is now desired(next) |
163 |
+ |
*/ |
164 |
+ |
bary_from_child(coord,child,next) |
165 |
+ |
BCOORD coord[3]; |
166 |
+ |
int child,next; |
167 |
+ |
{ |
168 |
+ |
#ifdef DEBUG |
169 |
+ |
if(child <0 || child > 3) |
170 |
+ |
{ |
171 |
+ |
eputs("bary_from_child():Invalid child\n"); |
172 |
+ |
return; |
173 |
+ |
} |
174 |
+ |
if(next <0 || next > 3) |
175 |
+ |
{ |
176 |
+ |
eputs("bary_from_child():Invalid next\n"); |
177 |
+ |
return; |
178 |
+ |
} |
179 |
+ |
#endif |
180 |
+ |
if(next == child) |
181 |
+ |
return; |
182 |
+ |
|
183 |
+ |
switch(child){ |
184 |
+ |
case 0: |
185 |
+ |
coord[0] = 0; |
186 |
+ |
coord[1] = MAXBCOORD2 - coord[1]; |
187 |
+ |
coord[2] = MAXBCOORD2 - coord[2]; |
188 |
+ |
break; |
189 |
+ |
case 1: |
190 |
+ |
coord[0] = MAXBCOORD2 - coord[0]; |
191 |
+ |
coord[1] = 0; |
192 |
+ |
coord[2] = MAXBCOORD2 - coord[2]; |
193 |
+ |
break; |
194 |
+ |
case 2: |
195 |
+ |
coord[0] = MAXBCOORD2 - coord[0]; |
196 |
+ |
coord[1] = MAXBCOORD2 - coord[1]; |
197 |
+ |
coord[2] = 0; |
198 |
+ |
break; |
199 |
+ |
case 3: |
200 |
+ |
switch(next){ |
201 |
+ |
case 0: |
202 |
+ |
coord[0] = 0; |
203 |
+ |
coord[1] = MAXBCOORD2 - coord[1]; |
204 |
+ |
coord[2] = MAXBCOORD2 - coord[2]; |
205 |
+ |
break; |
206 |
+ |
case 1: |
207 |
+ |
coord[0] = MAXBCOORD2 - coord[0]; |
208 |
+ |
coord[1] = 0; |
209 |
+ |
coord[2] = MAXBCOORD2 - coord[2]; |
210 |
+ |
break; |
211 |
+ |
case 2: |
212 |
+ |
coord[0] = MAXBCOORD2 - coord[0]; |
213 |
+ |
coord[1] = MAXBCOORD2 - coord[1]; |
214 |
+ |
coord[2] = 0; |
215 |
+ |
break; |
216 |
+ |
} |
217 |
+ |
break; |
218 |
+ |
} |
219 |
+ |
} |
220 |
+ |
|
221 |
+ |
/* |
222 |
+ |
* int |
223 |
+ |
* bary_child(coord): Return which child coord is of node at current level |
224 |
+ |
* As side effect recalculate coord at next level |
225 |
+ |
* BCOORD coord[3]; :At current level coordinates of point, will also set |
226 |
+ |
* to coords at next level as side effect |
227 |
+ |
*/ |
228 |
+ |
int |
229 |
+ |
bary_child(coord) |
230 |
+ |
BCOORD coord[3]; |
231 |
+ |
{ |
232 |
+ |
int i; |
233 |
+ |
|
234 |
+ |
if(coord[0] > MAXBCOORD4) |
235 |
+ |
{ |
236 |
+ |
/* update bary for child */ |
237 |
+ |
coord[0] = (coord[0]<< 1) - MAXBCOORD2; |
238 |
+ |
coord[1] <<= 1; |
239 |
+ |
coord[2] <<= 1; |
240 |
+ |
return(0); |
241 |
+ |
} |
242 |
+ |
else |
243 |
+ |
if(coord[1] > MAXBCOORD4) |
244 |
+ |
{ |
245 |
+ |
coord[0] <<= 1; |
246 |
+ |
coord[1] = (coord[1] << 1) - MAXBCOORD2; |
247 |
+ |
coord[2] <<= 1; |
248 |
+ |
return(1); |
249 |
+ |
} |
250 |
+ |
else |
251 |
+ |
if(coord[2] > MAXBCOORD4) |
252 |
+ |
{ |
253 |
+ |
coord[0] <<= 1; |
254 |
+ |
coord[1] <<= 1; |
255 |
+ |
coord[2] = (coord[2] << 1) - MAXBCOORD2; |
256 |
+ |
return(2); |
257 |
+ |
} |
258 |
+ |
else |
259 |
+ |
{ |
260 |
+ |
coord[0] = MAXBCOORD2 - (coord[0] << 1); |
261 |
+ |
coord[1] = MAXBCOORD2 - (coord[1] << 1); |
262 |
+ |
coord[2] = MAXBCOORD2 - (coord[2] << 1); |
263 |
+ |
return(3); |
264 |
+ |
} |
265 |
+ |
} |
266 |
+ |
|
267 |
+ |
|
268 |
+ |
|
269 |
|
QUADTREE |
270 |
|
qtLocate(qt,bcoord) |
271 |
|
QUADTREE qt; |
404 |
|
} |
405 |
|
} |
406 |
|
|
257 |
– |
|
258 |
– |
|
259 |
– |
|
260 |
– |
|
261 |
– |
|
262 |
– |
|
263 |
– |
|
407 |
|
#define TEST_INT(tl,th,d,q0,q1,h,l) \ |
408 |
|
tl=d>q0;th=d<q1; if(tl&&th) goto Lfunc_call; \ |
409 |
|
if(tl) if(l) goto Lfunc_call; else h=TRUE; \ |
1549 |
|
return(qt); |
1550 |
|
} |
1551 |
|
} |
1552 |
+ |
|
1553 |
|
|
1554 |
|
|
1555 |
|
|