Panda3D
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 
23 using std::max;
24 using std::min;
25 
26 TypeHandle BoundingHexahedron::_type_handle;
27 
28 /**
29  *
30  */
31 BoundingHexahedron::
32 BoundingHexahedron(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  */
69 BoundingHexahedron::
70 BoundingHexahedron(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  */
91 BoundingVolume *BoundingHexahedron::
92 make_copy() const {
93  return new BoundingHexahedron(*this);
94 }
95 
96 /**
97  *
98  */
99 LPoint3 BoundingHexahedron::
100 get_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  */
116 LPoint3 BoundingHexahedron::
117 get_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  */
133 LPoint3 BoundingHexahedron::
134 get_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  */
143 void BoundingHexahedron::
144 xform(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  */
157 void BoundingHexahedron::
158 output(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  */
171 void BoundingHexahedron::
172 write(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  */
193 as_bounding_hexahedron() const {
194  return this;
195 }
196 
197 /**
198  *
199  */
200 bool BoundingHexahedron::
201 extend_other(BoundingVolume *other) const {
202  return other->extend_by_hexahedron(this);
203 }
204 
205 /**
206  *
207  */
208 bool BoundingHexahedron::
209 around_other(BoundingVolume *other,
210  const BoundingVolume **first,
211  const BoundingVolume **last) const {
212  return other->around_hexahedrons(first, last);
213 }
214 
215 /**
216  *
217  */
218 int BoundingHexahedron::
219 contains_other(const BoundingVolume *other) const {
220  return other->contains_hexahedron(this);
221 }
222 
223 /**
224  *
225  */
226 int BoundingHexahedron::
227 contains_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  */
250 int BoundingHexahedron::
251 contains_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  */
279 int BoundingHexahedron::
280 contains_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  */
311 int BoundingHexahedron::
312 contains_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  */
363 int BoundingHexahedron::
364 contains_plane(const BoundingPlane *plane) const {
365  return plane->contains_hexahedron(this) & ~IF_all;
366 }
367 
368 /**
369  *
370  */
371 int BoundingHexahedron::
372 contains_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  */
421 void BoundingHexahedron::
422 set_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  */
462 void BoundingHexahedron::
463 set_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 ...
Definition: boundingPlane.h:28
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