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