1 /*
2 Copyright (c) 2005-2020 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 /*
18 The original source for this example is
19 Copyright (c) 1994-2008 John E. Stone
20 All rights reserved.
21
22 Redistribution and use in source and binary forms, with or without
23 modification, are permitted provided that the following conditions
24 are met:
25 1. Redistributions of source code must retain the above copyright
26 notice, this list of conditions and the following disclaimer.
27 2. Redistributions in binary form must reproduce the above copyright
28 notice, this list of conditions and the following disclaimer in the
29 documentation and/or other materials provided with the distribution.
30 3. The name of the author may not be used to endorse or promote products
31 derived from this software without specific prior written permission.
32
33 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
34 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
35 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
36 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
37 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
38 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
39 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
41 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
42 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
43 SUCH DAMAGE.
44 */
45
46 /*
47 * objbound.cpp - This file contains the functions to find bounding boxes
48 * for the various primitives
49 */
50
51 #include "machine.h"
52 #include "types.h"
53 #include "macros.h"
54 #include "bndbox.h"
55
56 #define OBJBOUND_PRIVATE
57 #include "objbound.h"
58
globalbound(object ** rootlist,vector * gmin,vector * gmax)59 static void globalbound(object ** rootlist, vector * gmin, vector * gmax) {
60 vector min, max;
61 object * cur;
62
63 if (*rootlist == NULL) /* don't bound non-existent objects */
64 return;
65
66 gmin->x = FHUGE; gmin->y = FHUGE; gmin->z = FHUGE;
67 gmax->x = -FHUGE; gmax->y = -FHUGE; gmax->z = -FHUGE;
68
69 cur=*rootlist;
70 while (cur != NULL) { /* Go! */
71 min.x = -FHUGE; min.y = -FHUGE; min.z = -FHUGE;
72 max.x = FHUGE; max.y = FHUGE; max.z = FHUGE;
73
74 cur->methods->bbox((void *) cur, &min, &max);
75
76 gmin->x = MYMIN( gmin->x , min.x);
77 gmin->y = MYMIN( gmin->y , min.y);
78 gmin->z = MYMIN( gmin->z , min.z);
79
80 gmax->x = MYMAX( gmax->x , max.x);
81 gmax->y = MYMAX( gmax->y , max.y);
82 gmax->z = MYMAX( gmax->z , max.z);
83
84 cur=(object *)cur->nextobj;
85 }
86 }
87
objinside(object * obj,vector * min,vector * max)88 static int objinside(object * obj, vector * min, vector * max) {
89 vector omin, omax;
90
91 if (obj == NULL) /* non-existent object, shouldn't get here */
92 return 0;
93
94 if (obj->methods->bbox((void *) obj, &omin, &omax)) {
95 if ((min->x <= omin.x) && (min->y <= omin.y) && (min->z <= omin.z) &&
96 (max->x >= omax.x) && (max->y >= omax.y) && (max->z >= omax.z)) {
97 return 1;
98 }
99 }
100 return 0;
101 }
102
countobj(object * root)103 static int countobj(object * root) {
104 object * cur; /* counts the number of objects on a list */
105 int numobj;
106
107 numobj=0;
108 cur=root;
109
110 while (cur != NULL) {
111 cur=(object *)cur->nextobj;
112 numobj++;
113 }
114 return numobj;
115 }
116
movenextobj(object * thisobj,object ** root)117 static void movenextobj(object * thisobj, object ** root) {
118 object * cur, * tmp;
119
120 /* move the object after thisobj to the front of the object list */
121 /* headed by root */
122 if (thisobj != NULL) {
123 if (thisobj->nextobj != NULL) {
124 cur=(object *)thisobj->nextobj; /* the object to be moved */
125 thisobj->nextobj = cur->nextobj; /* link around the moved obj */
126 tmp=*root; /* store the root node */
127 cur->nextobj=tmp; /* attach root to cur */
128 *root=cur; /* make cur, the new root */
129 }
130 }
131 }
132
octreespace(object ** rootlist,int maxoctnodes)133 static void octreespace(object ** rootlist, int maxoctnodes) {
134 object * cur;
135 vector gmin, gmax, gctr;
136 vector cmin1, cmin2, cmin3, cmin4, cmin5, cmin6, cmin7, cmin8;
137 vector cmax1, cmax2, cmax3, cmax4, cmax5, cmax6, cmax7, cmax8;
138 bndbox * box1, * box2, * box3, * box4;
139 bndbox * box5, * box6, * box7, * box8;
140 int skipobj;
141
142 if (*rootlist == NULL) /* don't subdivide non-existent data */
143 return;
144
145 skipobj=0;
146 globalbound(rootlist, &gmin, &gmax); /* find global min and max */
147
148 gctr.x = ((gmax.x - gmin.x) / 2.0) + gmin.x;
149 gctr.y = ((gmax.y - gmin.y) / 2.0) + gmin.y;
150 gctr.z = ((gmax.z - gmin.z) / 2.0) + gmin.z;
151
152 cmin1=gmin;
153 cmax1=gctr;
154 box1 = newbndbox(cmin1, cmax1);
155
156 cmin2=gmin;
157 cmin2.x=gctr.x;
158 cmax2=gmax;
159 cmax2.y=gctr.y;
160 cmax2.z=gctr.z;
161 box2 = newbndbox(cmin2, cmax2);
162
163 cmin3=gmin;
164 cmin3.y=gctr.y;
165 cmax3=gmax;
166 cmax3.x=gctr.x;
167 cmax3.z=gctr.z;
168 box3 = newbndbox(cmin3, cmax3);
169
170 cmin4=gmin;
171 cmin4.x=gctr.x;
172 cmin4.y=gctr.y;
173 cmax4=gmax;
174 cmax4.z=gctr.z;
175 box4 = newbndbox(cmin4, cmax4);
176
177 cmin5=gmin;
178 cmin5.z=gctr.z;
179 cmax5=gctr;
180 cmax5.z=gmax.z;
181 box5 = newbndbox(cmin5, cmax5);
182
183 cmin6=gctr;
184 cmin6.y=gmin.y;
185 cmax6=gmax;
186 cmax6.y=gctr.y;
187 box6 = newbndbox(cmin6, cmax6);
188
189 cmin7=gctr;
190 cmin7.x=gmin.x;
191 cmax7=gctr;
192 cmax7.y=gmax.y;
193 cmax7.z=gmax.z;
194 box7 = newbndbox(cmin7, cmax7);
195
196 cmin8=gctr;
197 cmax8=gmax;
198 box8 = newbndbox(cmin8, cmax8);
199
200 cur = *rootlist;
201 while (cur != NULL) {
202 if (objinside((object *)cur->nextobj, &cmin1, &cmax1)) {
203 movenextobj(cur, &box1->objlist);
204 }
205 else if (objinside((object *)cur->nextobj, &cmin2, &cmax2)) {
206 movenextobj(cur, &box2->objlist);
207 }
208 else if (objinside((object *)cur->nextobj, &cmin3, &cmax3)) {
209 movenextobj(cur, &box3->objlist);
210 }
211 else if (objinside((object *)cur->nextobj, &cmin4, &cmax4)) {
212 movenextobj(cur, &box4->objlist);
213 }
214 else if (objinside((object *)cur->nextobj, &cmin5, &cmax5)) {
215 movenextobj(cur, &box5->objlist);
216 }
217 else if (objinside((object *)cur->nextobj, &cmin6, &cmax6)) {
218 movenextobj(cur, &box6->objlist);
219 }
220 else if (objinside((object *)cur->nextobj, &cmin7, &cmax7)) {
221 movenextobj(cur, &box7->objlist);
222 }
223 else if (objinside((object *)cur->nextobj, &cmin8, &cmax8)) {
224 movenextobj(cur, &box8->objlist);
225 }
226 else {
227 skipobj++;
228 cur=(object *)cur->nextobj;
229 }
230 }
231
232 /* new scope, for redefinition of cur, and old */
233 { bndbox * cur, * old;
234 old=box1;
235 cur=box2;
236 if (countobj(cur->objlist) > 0) {
237 old->nextobj=cur;
238 globalbound(&cur->objlist, &cur->min, &cur->max);
239 old=cur;
240 }
241 cur=box3;
242 if (countobj(cur->objlist) > 0) {
243 old->nextobj=cur;
244 globalbound(&cur->objlist, &cur->min, &cur->max);
245 old=cur;
246 }
247 cur=box4;
248 if (countobj(cur->objlist) > 0) {
249 old->nextobj=cur;
250 globalbound(&cur->objlist, &cur->min, &cur->max);
251 old=cur;
252 }
253 cur=box5;
254 if (countobj(cur->objlist) > 0) {
255 old->nextobj=cur;
256 globalbound(&cur->objlist, &cur->min, &cur->max);
257 old=cur;
258 }
259 cur=box6;
260 if (countobj(cur->objlist) > 0) {
261 old->nextobj=cur;
262 globalbound(&cur->objlist, &cur->min, &cur->max);
263 old=cur;
264 }
265 cur=box7;
266 if (countobj(cur->objlist) > 0) {
267 old->nextobj=cur;
268 globalbound(&cur->objlist, &cur->min, &cur->max);
269 old=cur;
270 }
271 cur=box8;
272 if (countobj(cur->objlist) > 0) {
273 old->nextobj=cur;
274 globalbound(&cur->objlist, &cur->min, &cur->max);
275 old=cur;
276 }
277
278 old->nextobj=*rootlist;
279
280 if (countobj(box1->objlist) > 0) {
281 globalbound(&box1->objlist, &box1->min, &box1->max);
282 *rootlist=(object *) box1;
283 }
284 else {
285 *rootlist=(object *) box1->nextobj;
286 }
287
288 } /**** end of special cur and old scope */
289
290 if (countobj(box1->objlist) > maxoctnodes) {
291 octreespace(&box1->objlist, maxoctnodes);
292 }
293 if (countobj(box2->objlist) > maxoctnodes) {
294 octreespace(&box2->objlist, maxoctnodes);
295 }
296 if (countobj(box3->objlist) > maxoctnodes) {
297 octreespace(&box3->objlist, maxoctnodes);
298 }
299 if (countobj(box4->objlist) > maxoctnodes) {
300 octreespace(&box4->objlist, maxoctnodes);
301 }
302 if (countobj(box5->objlist) > maxoctnodes) {
303 octreespace(&box5->objlist, maxoctnodes);
304 }
305 if (countobj(box6->objlist) > maxoctnodes) {
306 octreespace(&box6->objlist, maxoctnodes);
307 }
308 if (countobj(box7->objlist) > maxoctnodes) {
309 octreespace(&box7->objlist, maxoctnodes);
310 }
311 if (countobj(box8->objlist) > maxoctnodes) {
312 octreespace(&box8->objlist, maxoctnodes);
313 }
314 }
315
dividespace(int maxoctnodes,object ** toplist)316 void dividespace(int maxoctnodes, object **toplist) {
317 bndbox * gbox;
318 vector gmin, gmax;
319
320 if (countobj(*toplist) > maxoctnodes) {
321 globalbound(toplist, &gmin, &gmax);
322
323 octreespace(toplist, maxoctnodes);
324
325 gbox = newbndbox(gmin, gmax);
326 gbox->objlist = NULL;
327 gbox->tex = NULL;
328 gbox->nextobj=NULL;
329 gbox->objlist=*toplist;
330 *toplist=(object *) gbox;
331 }
332 }
333