Panda3D
Loading...
Searching...
No Matches
boundingHexahedron.cxx
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file boundingHexahedron.cxx
10 * @author drose
11 * @date 1999-10-03
12 */
13
14#include "boundingHexahedron.h"
15#include "boundingSphere.h"
16#include "boundingBox.h"
17#include "boundingPlane.h"
18#include "config_mathutil.h"
19
20#include <math.h>
21#include <algorithm>
22
23using std::max;
24using std::min;
25
26TypeHandle BoundingHexahedron::_type_handle;
27
28/**
29 *
30 */
31BoundingHexahedron::
32BoundingHexahedron(const LFrustum &frustum, bool is_ortho,
33 CoordinateSystem cs) {
34 if (cs == CS_default) {
35 cs = get_default_coordinate_system();
36 }
37
38 PN_stdfloat fs = 1.0f;
39 if (!is_ortho) {
40 fs = frustum._ffar / frustum._fnear;
41 }
42
43 // We build the points based on a Z-up right-handed frustum. If the
44 // requested coordinate system is otherwise, we'll convert it in a second
45 // pass.
46 _points[0].set(frustum._l * fs, frustum._ffar, frustum._b * fs);
47 _points[1].set(frustum._r * fs, frustum._ffar, frustum._b * fs);
48 _points[2].set(frustum._r * fs, frustum._ffar, frustum._t * fs);
49 _points[3].set(frustum._l * fs, frustum._ffar, frustum._t * fs);
50 _points[4].set(frustum._l, frustum._fnear, frustum._b);
51 _points[5].set(frustum._r, frustum._fnear, frustum._b);
52 _points[6].set(frustum._r, frustum._fnear, frustum._t);
53 _points[7].set(frustum._l, frustum._fnear, frustum._t);
54
55 _flags = 0;
56
57 // Now fix the coordinate system, if necessary.
58 if (cs == CS_zup_right) {
59 set_centroid();
60 set_planes();
61 } else {
62 xform(LMatrix4::convert_mat(CS_zup_right, cs));
63 }
64}
65
66/**
67 *
68 */
69BoundingHexahedron::
70BoundingHexahedron(const LPoint3 &fll, const LPoint3 &flr,
71 const LPoint3 &fur, const LPoint3 &ful,
72 const LPoint3 &nll, const LPoint3 &nlr,
73 const LPoint3 &nur, const LPoint3 &nul) {
74 _points[0] = fll;
75 _points[1] = flr;
76 _points[2] = fur;
77 _points[3] = ful;
78 _points[4] = nll;
79 _points[5] = nlr;
80 _points[6] = nur;
81 _points[7] = nul;
82
83 _flags = 0;
84 set_centroid();
85 set_planes();
86}
87
88/**
89 *
90 */
91BoundingVolume *BoundingHexahedron::
92make_copy() const {
93 return new BoundingHexahedron(*this);
94}
95
96/**
97 *
98 */
99LPoint3 BoundingHexahedron::
100get_min() const {
101 nassertr(!is_empty(), LPoint3(0.0f, 0.0f, 0.0f));
102 nassertr(!is_infinite(), LPoint3(0.0f, 0.0f, 0.0f));
103 int i;
104 LPoint3 m = _points[0];
105 for (i = 1; i < num_points; i++) {
106 m.set(min(m[0], _points[i][0]),
107 min(m[1], _points[i][1]),
108 min(m[2], _points[i][2]));
109 }
110 return m;
111}
112
113/**
114 *
115 */
116LPoint3 BoundingHexahedron::
117get_max() const {
118 nassertr(!is_empty(), LPoint3(0.0f, 0.0f, 0.0f));
119 nassertr(!is_infinite(), LPoint3(0.0f, 0.0f, 0.0f));
120 int i;
121 LPoint3 m = _points[0];
122 for (i = 1; i < num_points; i++) {
123 m.set(max(m[0], _points[i][0]),
124 max(m[1], _points[i][1]),
125 max(m[2], _points[i][2]));
126 }
127 return m;
128}
129
130/**
131 *
132 */
133LPoint3 BoundingHexahedron::
134get_approx_center() const {
135 nassertr(!is_empty(), LPoint3(0.0f, 0.0f, 0.0f));
136 nassertr(!is_infinite(), LPoint3(0.0f, 0.0f, 0.0f));
137 return _centroid;
138}
139
140/**
141 *
142 */
143void BoundingHexahedron::
144xform(const LMatrix4 &mat) {
145 if (!is_empty() && !is_infinite()) {
146 for (int i = 0; i < num_points; i++) {
147 _points[i] = _points[i] * mat;
148 }
149 set_centroid();
150 set_planes();
151 }
152}
153
154/**
155 *
156 */
157void BoundingHexahedron::
158output(std::ostream &out) const {
159 if (is_empty()) {
160 out << "bhexahedron, empty";
161 } else if (is_infinite()) {
162 out << "bhexahedron, infinite";
163 } else {
164 out << "bhexahedron, min " << get_min() << " max " << get_max();
165 }
166}
167
168/**
169 *
170 */
171void BoundingHexahedron::
172write(std::ostream &out, int indent_level) const {
173 if (is_empty()) {
174 indent(out, indent_level) << "bhexahedron, empty\n";
175 } else if (is_infinite()) {
176 out << "bhexahedron, infinite\n";
177 } else {
178 indent(out, indent_level)
179 << "bhexahedron, min " << get_min() << " max " << get_max() << ":\n";
180 int i;
181 for (i = 0; i < num_points; i++) {
182 indent(out, indent_level + 2) << _points[i] << "\n";
183 }
184 indent(out, indent_level + 2) << "centroid is " << _centroid << "\n";
185 }
186}
187
188/**
189 * Virtual downcast method. Returns this object as a pointer of the indicated
190 * type, if it is in fact that type. Returns NULL if it is not that type.
191 */
194 return this;
195}
196
197/**
198 *
199 */
200bool BoundingHexahedron::
201extend_other(BoundingVolume *other) const {
202 return other->extend_by_hexahedron(this);
203}
204
205/**
206 *
207 */
208bool BoundingHexahedron::
209around_other(BoundingVolume *other,
210 const BoundingVolume **first,
211 const BoundingVolume **last) const {
212 return other->around_hexahedrons(first, last);
213}
214
215/**
216 *
217 */
218int BoundingHexahedron::
219contains_other(const BoundingVolume *other) const {
220 return other->contains_hexahedron(this);
221}
222
223/**
224 *
225 */
226int BoundingHexahedron::
227contains_point(const LPoint3 &point) const {
228 if (is_empty()) {
229 return IF_no_intersection;
230
231 } else if (is_infinite()) {
232 return IF_possible | IF_some | IF_all;
233
234 } else {
235 // The hexahedron contains the point iff the point is behind all of the
236 // planes.
237 for (int i = 0; i < num_planes; i++) {
238 const LPlane &p = _planes[i];
239 if (p.dist_to_plane(point) > 0.0f) {
240 return IF_no_intersection;
241 }
242 }
243 return IF_possible | IF_some | IF_all;
244 }
245}
246
247/**
248 *
249 */
250int BoundingHexahedron::
251contains_lineseg(const LPoint3 &a, const LPoint3 &b) const {
252 if (is_empty()) {
253 return IF_no_intersection;
254
255 } else if (is_infinite()) {
256 return IF_possible | IF_some | IF_all;
257
258 } else {
259 // The hexahedron does not contains the line segment if both points are in
260 // front of any one plane.
261 for (int i = 0; i < num_planes; i++) {
262 const LPlane &p = _planes[i];
263 if (p.dist_to_plane(a) > 0.0f ||
264 p.dist_to_plane(b) > 0.0f) {
265 return IF_no_intersection;
266 }
267 }
268
269 // If there is no plane that both points are in front of, the hexahedron
270 // may or may not contain the line segment. For the moment, we won't
271 // bother to check that more thoroughly, though.
272 return IF_possible;
273 }
274}
275
276/**
277 *
278 */
279int BoundingHexahedron::
280contains_sphere(const BoundingSphere *sphere) const {
281 nassertr(!is_empty(), 0);
282
283 // The hexahedron contains the sphere iff the sphere is at least partly
284 // behind all of the planes.
285 const LPoint3 &center = sphere->get_center();
286 PN_stdfloat radius = sphere->get_radius();
287
288 int result = IF_possible | IF_some | IF_all;
289
290 for (int i = 0; i < num_planes; i++) {
291 const LPlane &p = _planes[i];
292 PN_stdfloat dist = p.dist_to_plane(center);
293
294 if (dist > radius) {
295 // The sphere is completely in front of this plane; it's thus completely
296 // outside of the hexahedron.
297 return IF_no_intersection;
298
299 } else if (dist > -radius) {
300 // The sphere is not completely behind this plane, but some of it is.
301 result &= ~IF_all;
302 }
303 }
304
305 return result;
306}
307
308/**
309 *
310 */
311int BoundingHexahedron::
312contains_box(const BoundingBox *box) const {
313 nassertr(!is_empty(), 0);
314 nassertr(!box->is_empty(), 0);
315
316 // Put the box inside a sphere for the purpose of this test.
317 const LPoint3 &min = box->get_minq();
318 const LPoint3 &max = box->get_maxq();
319 LPoint3 center = (min + max) * 0.5f;
320 PN_stdfloat radius2 = (max - center).length_squared();
321
322 int result = IF_possible | IF_some | IF_all;
323
324 for (int i = 0; i < num_planes; i++) {
325 const LPlane &p = _planes[i];
326 PN_stdfloat dist = p.dist_to_plane(center);
327 PN_stdfloat dist2 = dist * dist;
328
329 if (dist2 <= radius2) {
330 // The sphere is not completely behind this plane, but some of it is.
331
332 // Look a little closer.
333 bool all_in = true;
334 bool all_out = true;
335 for (int i = 0; i < 8 && (all_in || all_out) ; ++i) {
336 if (p.dist_to_plane(box->get_point(i)) < 0.0f) {
337 // This point is inside the plane.
338 all_out = false;
339 } else {
340 // This point is outside the plane.
341 all_in = false;
342 }
343 }
344
345 if (all_out) {
346 return IF_no_intersection;
347 } else if (!all_in) {
348 result &= ~IF_all;
349 }
350
351 } else if (dist >= 0.0f) {
352 // The sphere is completely in front of this plane.
353 return IF_no_intersection;
354 }
355 }
356
357 return result;
358}
359
360/**
361 *
362 */
363int BoundingHexahedron::
364contains_plane(const BoundingPlane *plane) const {
365 return plane->contains_hexahedron(this) & ~IF_all;
366}
367
368/**
369 *
370 */
371int BoundingHexahedron::
372contains_hexahedron(const BoundingHexahedron *hexahedron) const {
373 nassertr(!is_empty(), 0);
374 nassertr(!hexahedron->is_empty(), 0);
375
376 // Put the hexahedron inside a sphere for the purposes of this test.
377 LPoint3 min = hexahedron->get_min();
378 LPoint3 max = hexahedron->get_max();
379 LPoint3 center = (min + max) * 0.5f;
380 PN_stdfloat radius2 = (max - center).length_squared();
381
382 int result = IF_possible | IF_some | IF_all;
383
384 for (int i = 0; i < num_planes; i++) {
385 const LPlane &p = _planes[i];
386 PN_stdfloat dist = p.dist_to_plane(center);
387 PN_stdfloat dist2 = dist * dist;
388
389 if (dist >= 0.0f && dist2 > radius2) {
390 // The sphere is completely in front of this plane; it's thus completely
391 // outside of the hexahedron.
392 return IF_no_intersection;
393
394 } else {/*if (dist < 0.0f && dist2 < radius2) {*/
395 // The sphere is not completely behind this plane, but some of it is.
396
397 // Look a little closer.
398 unsigned points_out = 0;
399 for (int i = 0; i < 8; ++i) {
400 if (p.dist_to_plane(hexahedron->get_point(i)) > 0.0f) {
401 // This point is outside the plane.
402 ++points_out;
403 }
404 }
405
406 if (points_out != 0) {
407 if (points_out == 8) {
408 return IF_no_intersection;
409 }
410 result &= ~IF_all;
411 }
412 }
413 }
414
415 return result;
416}
417
418/**
419 *
420 */
421void BoundingHexahedron::
422set_planes() {
423 _planes[0] = LPlane(_points[0], _points[3], _points[2]);
424
425 // Test to see if we have accidentally inverted our frustum by transforming
426 // it with a -1 matrix. We do this by ensuring that the centroid is in
427 // front of all of the planes (actually, we only need to test the first
428 // plane).
429 if (_planes[0].dist_to_plane(_centroid) > 0) {
430 // Oops! We're flipped! Rebuild the planes in the opposite direction.
431 _planes[0] = LPlane(_points[0], _points[2], _points[3]);
432 _planes[1] = LPlane(_points[0], _points[5], _points[1]);
433 _planes[2] = LPlane(_points[1], _points[6], _points[2]);
434 _planes[3] = LPlane(_points[2], _points[7], _points[3]);
435 _planes[4] = LPlane(_points[3], _points[4], _points[0]);
436 _planes[5] = LPlane(_points[4], _points[7], _points[6]);
437
438 } else {
439 // No, a perfectly sane universe.
440 _planes[1] = LPlane(_points[0], _points[1], _points[5]);
441 _planes[2] = LPlane(_points[1], _points[2], _points[6]);
442 _planes[3] = LPlane(_points[2], _points[3], _points[7]);
443 _planes[4] = LPlane(_points[3], _points[0], _points[4]);
444 _planes[5] = LPlane(_points[4], _points[6], _points[7]);
445 }
446
447 // Still not entirely sure why some code keeps triggering these, but I'm
448 // taking them out of the normal build for now.
449#ifdef _DEBUG
450 nassertv(_planes[0].dist_to_plane(_centroid) <= 0.001);
451 nassertv(_planes[1].dist_to_plane(_centroid) <= 0.001);
452 nassertv(_planes[2].dist_to_plane(_centroid) <= 0.001);
453 nassertv(_planes[3].dist_to_plane(_centroid) <= 0.001);
454 nassertv(_planes[4].dist_to_plane(_centroid) <= 0.001);
455 nassertv(_planes[5].dist_to_plane(_centroid) <= 0.001);
456#endif
457}
458
459/**
460 *
461 */
462void BoundingHexahedron::
463set_centroid() {
464 LPoint3 net = _points[0];
465 for (int i = 1; i < num_points; i++) {
466 net += _points[i];
467 }
468 _centroid = net / (PN_stdfloat)num_points;
469}
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition boundingBox.h:29
const LPoint3 & get_minq() const
An inline accessor for the minimum value.
Definition boundingBox.I:41
get_point
Returns the nth vertex of the rectangular solid.
Definition boundingBox.h:51
const LPoint3 & get_maxq() const
An inline accessor for the maximum value.
Definition boundingBox.I:52
This defines a bounding convex hexahedron.
virtual const BoundingHexahedron * as_bounding_hexahedron() const
Virtual downcast method.
get_point
Returns the nth vertex of the hexahedron.
This funny bounding volume is an infinite plane that divides space into two regions: the part behind ...
This defines a bounding sphere, consisting of a center and a radius.
This is an abstract class for any volume in any sense which can be said to define the locality of ref...
bool is_empty() const
Any kind of volume might be empty.
bool is_infinite() const
The other side of the empty coin is an infinite volume.
TypeHandle is the identifier used to differentiate C++ class types.
Definition typeHandle.h:81
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition indent.cxx:20