1 /*
2 Copyright (c) 2005-2021 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.hpp"
52 #include "types.hpp"
53 #include "macros.hpp"
54 #include "bndbox.hpp"
55
56 #define OBJBOUND_PRIVATE
57 #include "objbound.hpp"
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 == nullptr) /* don't bound non-existent objects */
64 return;
65
66 gmin->x = FHUGE;
67 gmin->y = FHUGE;
68 gmin->z = FHUGE;
69 gmax->x = -FHUGE;
70 gmax->y = -FHUGE;
71 gmax->z = -FHUGE;
72
73 cur = *rootlist;
74 while (cur != nullptr) { /* Go! */
75 min.x = -FHUGE;
76 min.y = -FHUGE;
77 min.z = -FHUGE;
78 max.x = FHUGE;
79 max.y = FHUGE;
80 max.z = FHUGE;
81
82 cur->methods->bbox((void *)cur, &min, &max);
83
84 gmin->x = MYMIN(gmin->x, min.x);
85 gmin->y = MYMIN(gmin->y, min.y);
86 gmin->z = MYMIN(gmin->z, min.z);
87
88 gmax->x = MYMAX(gmax->x, max.x);
89 gmax->y = MYMAX(gmax->y, max.y);
90 gmax->z = MYMAX(gmax->z, max.z);
91
92 cur = (object *)cur->nextobj;
93 }
94 }
95
objinside(object * obj,vector * min,vector * max)96 static int objinside(object *obj, vector *min, vector *max) {
97 vector omin, omax;
98
99 if (obj == nullptr) /* non-existent object, shouldn't get here */
100 return 0;
101
102 if (obj->methods->bbox((void *)obj, &omin, &omax)) {
103 if ((min->x <= omin.x) && (min->y <= omin.y) && (min->z <= omin.z) && (max->x >= omax.x) &&
104 (max->y >= omax.y) && (max->z >= omax.z)) {
105 return 1;
106 }
107 }
108 return 0;
109 }
110
countobj(object * root)111 static int countobj(object *root) {
112 object *cur; /* counts the number of objects on a list */
113 int numobj;
114
115 numobj = 0;
116 cur = root;
117
118 while (cur != nullptr) {
119 cur = (object *)cur->nextobj;
120 numobj++;
121 }
122 return numobj;
123 }
124
movenextobj(object * thisobj,object ** root)125 static void movenextobj(object *thisobj, object **root) {
126 object *cur, *tmp;
127
128 /* move the object after thisobj to the front of the object list */
129 /* headed by root */
130 if (thisobj != nullptr) {
131 if (thisobj->nextobj != nullptr) {
132 cur = (object *)thisobj->nextobj; /* the object to be moved */
133 thisobj->nextobj = cur->nextobj; /* link around the moved obj */
134 tmp = *root; /* store the root node */
135 cur->nextobj = tmp; /* attach root to cur */
136 *root = cur; /* make cur, the new root */
137 }
138 }
139 }
140
octreespace(object ** rootlist,int maxoctnodes)141 static void octreespace(object **rootlist, int maxoctnodes) {
142 object *cur;
143 vector gmin, gmax, gctr;
144 vector cmin1, cmin2, cmin3, cmin4, cmin5, cmin6, cmin7, cmin8;
145 vector cmax1, cmax2, cmax3, cmax4, cmax5, cmax6, cmax7, cmax8;
146 bndbox *box1, *box2, *box3, *box4;
147 bndbox *box5, *box6, *box7, *box8;
148 int skipobj;
149
150 if (*rootlist == nullptr) /* don't subdivide non-existent data */
151 return;
152
153 skipobj = 0;
154 globalbound(rootlist, &gmin, &gmax); /* find global min and max */
155
156 gctr.x = ((gmax.x - gmin.x) / 2.0) + gmin.x;
157 gctr.y = ((gmax.y - gmin.y) / 2.0) + gmin.y;
158 gctr.z = ((gmax.z - gmin.z) / 2.0) + gmin.z;
159
160 cmin1 = gmin;
161 cmax1 = gctr;
162 box1 = newbndbox(cmin1, cmax1);
163
164 cmin2 = gmin;
165 cmin2.x = gctr.x;
166 cmax2 = gmax;
167 cmax2.y = gctr.y;
168 cmax2.z = gctr.z;
169 box2 = newbndbox(cmin2, cmax2);
170
171 cmin3 = gmin;
172 cmin3.y = gctr.y;
173 cmax3 = gmax;
174 cmax3.x = gctr.x;
175 cmax3.z = gctr.z;
176 box3 = newbndbox(cmin3, cmax3);
177
178 cmin4 = gmin;
179 cmin4.x = gctr.x;
180 cmin4.y = gctr.y;
181 cmax4 = gmax;
182 cmax4.z = gctr.z;
183 box4 = newbndbox(cmin4, cmax4);
184
185 cmin5 = gmin;
186 cmin5.z = gctr.z;
187 cmax5 = gctr;
188 cmax5.z = gmax.z;
189 box5 = newbndbox(cmin5, cmax5);
190
191 cmin6 = gctr;
192 cmin6.y = gmin.y;
193 cmax6 = gmax;
194 cmax6.y = gctr.y;
195 box6 = newbndbox(cmin6, cmax6);
196
197 cmin7 = gctr;
198 cmin7.x = gmin.x;
199 cmax7 = gctr;
200 cmax7.y = gmax.y;
201 cmax7.z = gmax.z;
202 box7 = newbndbox(cmin7, cmax7);
203
204 cmin8 = gctr;
205 cmax8 = gmax;
206 box8 = newbndbox(cmin8, cmax8);
207
208 cur = *rootlist;
209 while (cur != nullptr) {
210 if (objinside((object *)cur->nextobj, &cmin1, &cmax1)) {
211 movenextobj(cur, &box1->objlist);
212 }
213 else if (objinside((object *)cur->nextobj, &cmin2, &cmax2)) {
214 movenextobj(cur, &box2->objlist);
215 }
216 else if (objinside((object *)cur->nextobj, &cmin3, &cmax3)) {
217 movenextobj(cur, &box3->objlist);
218 }
219 else if (objinside((object *)cur->nextobj, &cmin4, &cmax4)) {
220 movenextobj(cur, &box4->objlist);
221 }
222 else if (objinside((object *)cur->nextobj, &cmin5, &cmax5)) {
223 movenextobj(cur, &box5->objlist);
224 }
225 else if (objinside((object *)cur->nextobj, &cmin6, &cmax6)) {
226 movenextobj(cur, &box6->objlist);
227 }
228 else if (objinside((object *)cur->nextobj, &cmin7, &cmax7)) {
229 movenextobj(cur, &box7->objlist);
230 }
231 else if (objinside((object *)cur->nextobj, &cmin8, &cmax8)) {
232 movenextobj(cur, &box8->objlist);
233 }
234 else {
235 skipobj++;
236 cur = (object *)cur->nextobj;
237 }
238 }
239
240 /* new scope, for redefinition of cur, and old */
241 {
242 bndbox *cur, *old;
243 old = box1;
244 cur = box2;
245 if (countobj(cur->objlist) > 0) {
246 old->nextobj = cur;
247 globalbound(&cur->objlist, &cur->min, &cur->max);
248 old = cur;
249 }
250 cur = box3;
251 if (countobj(cur->objlist) > 0) {
252 old->nextobj = cur;
253 globalbound(&cur->objlist, &cur->min, &cur->max);
254 old = cur;
255 }
256 cur = box4;
257 if (countobj(cur->objlist) > 0) {
258 old->nextobj = cur;
259 globalbound(&cur->objlist, &cur->min, &cur->max);
260 old = cur;
261 }
262 cur = box5;
263 if (countobj(cur->objlist) > 0) {
264 old->nextobj = cur;
265 globalbound(&cur->objlist, &cur->min, &cur->max);
266 old = cur;
267 }
268 cur = box6;
269 if (countobj(cur->objlist) > 0) {
270 old->nextobj = cur;
271 globalbound(&cur->objlist, &cur->min, &cur->max);
272 old = cur;
273 }
274 cur = box7;
275 if (countobj(cur->objlist) > 0) {
276 old->nextobj = cur;
277 globalbound(&cur->objlist, &cur->min, &cur->max);
278 old = cur;
279 }
280 cur = box8;
281 if (countobj(cur->objlist) > 0) {
282 old->nextobj = cur;
283 globalbound(&cur->objlist, &cur->min, &cur->max);
284 old = cur;
285 }
286
287 old->nextobj = *rootlist;
288
289 if (countobj(box1->objlist) > 0) {
290 globalbound(&box1->objlist, &box1->min, &box1->max);
291 *rootlist = (object *)box1;
292 }
293 else {
294 *rootlist = (object *)box1->nextobj;
295 }
296
297 } /**** end of special cur and old scope */
298
299 if (countobj(box1->objlist) > maxoctnodes) {
300 octreespace(&box1->objlist, maxoctnodes);
301 }
302 if (countobj(box2->objlist) > maxoctnodes) {
303 octreespace(&box2->objlist, maxoctnodes);
304 }
305 if (countobj(box3->objlist) > maxoctnodes) {
306 octreespace(&box3->objlist, maxoctnodes);
307 }
308 if (countobj(box4->objlist) > maxoctnodes) {
309 octreespace(&box4->objlist, maxoctnodes);
310 }
311 if (countobj(box5->objlist) > maxoctnodes) {
312 octreespace(&box5->objlist, maxoctnodes);
313 }
314 if (countobj(box6->objlist) > maxoctnodes) {
315 octreespace(&box6->objlist, maxoctnodes);
316 }
317 if (countobj(box7->objlist) > maxoctnodes) {
318 octreespace(&box7->objlist, maxoctnodes);
319 }
320 if (countobj(box8->objlist) > maxoctnodes) {
321 octreespace(&box8->objlist, maxoctnodes);
322 }
323 }
324
dividespace(int maxoctnodes,object ** toplist)325 void dividespace(int maxoctnodes, object **toplist) {
326 bndbox *gbox;
327 vector gmin, gmax;
328
329 if (countobj(*toplist) > maxoctnodes) {
330 globalbound(toplist, &gmin, &gmax);
331
332 octreespace(toplist, maxoctnodes);
333
334 gbox = newbndbox(gmin, gmax);
335 gbox->objlist = nullptr;
336 gbox->tex = nullptr;
337 gbox->nextobj = nullptr;
338 gbox->objlist = *toplist;
339 *toplist = (object *)gbox;
340 }
341 }
342