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 
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 
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 
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 
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 
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 
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