aboutsummaryrefslogtreecommitdiff
path: root/externals/g3dlite/AABox.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'externals/g3dlite/AABox.cpp')
-rw-r--r--externals/g3dlite/AABox.cpp366
1 files changed, 366 insertions, 0 deletions
diff --git a/externals/g3dlite/AABox.cpp b/externals/g3dlite/AABox.cpp
new file mode 100644
index 00000000000..035497aa3c4
--- /dev/null
+++ b/externals/g3dlite/AABox.cpp
@@ -0,0 +1,366 @@
+/**
+ @file AABox.cpp
+
+ @maintainer Morgan McGuire, http://graphics.cs.williams.edu
+
+ @created 2004-01-10
+ @edited 2006-01-11
+*/
+
+#include "G3D/platform.h"
+#include "G3D/AABox.h"
+#include "G3D/Box.h"
+#include "G3D/Plane.h"
+#include "G3D/Sphere.h"
+#include "G3D/BinaryInput.h"
+#include "G3D/BinaryOutput.h"
+
+
+namespace G3D {
+
+const AABox& AABox::maxFinite() {
+ static const AABox b = AABox(Vector3::minFinite(),
+ Vector3::maxFinite());
+ return b;
+}
+
+
+const AABox& AABox::large() {
+ static const AABox b = AABox(Vector3::minFinite() * 0.5f,
+ Vector3::maxFinite() * 0.5f);
+ return b;
+}
+
+
+const AABox& AABox::inf() {
+ static const AABox b = AABox(-Vector3::inf(), Vector3::inf());
+ return b;
+}
+
+
+const AABox& AABox::zero() {
+ static const AABox b = AABox(Vector3::zero(), Vector3::zero());
+ return b;
+}
+
+
+void AABox::serialize(class BinaryOutput& b) const {
+ b.writeVector3(lo);
+ b.writeVector3(hi);
+}
+
+
+void AABox::deserialize(class BinaryInput& b) {
+ lo = b.readVector3();
+ hi = b.readVector3();
+}
+
+
+void AABox::split(const Vector3::Axis& axis, float location, AABox& low, AABox& high) const {
+ // Low, medium, and high along the chosen axis
+ float L = G3D::min(location, lo[axis]);
+ float M = G3D::min(G3D::max(location, lo[axis]), hi[axis]);
+ float H = G3D::max(location, hi[axis]);
+
+ // Copy over this box.
+ high = low = *this;
+
+ // Now move the split points along the special axis
+ low.lo[axis] = L;
+ low.hi[axis] = M;
+ high.lo[axis] = M;
+ high.hi[axis] = H;
+}
+
+
+Vector3 AABox::randomSurfacePoint() const {
+ Vector3 extent = hi - lo;
+ float aXY = extent.x * extent.y;
+ float aYZ = extent.y * extent.z;
+ float aZX = extent.z * extent.x;
+
+ float r = (float)uniformRandom(0.0f, aXY + aYZ + aZX);
+
+ // Choose evenly between positive and negative face planes
+ float d = ((float)uniformRandom(0, 1) < 0.5f) ? 0.0f : 1.0f;
+
+ // The probability of choosing a given face is proportional to
+ // its area.
+ if (r < aXY) {
+ return
+ lo +
+ Vector3(
+ (float)uniformRandom(0.0f, extent.x),
+ (float)uniformRandom(0.0f, extent.y),
+ d * extent.z);
+ } else if (r < aYZ) {
+ return
+ lo +
+ Vector3(
+ d * extent.x,
+ (float)uniformRandom(0, extent.y),
+ (float)uniformRandom(0, extent.z));
+ } else {
+ return
+ lo +
+ Vector3(
+ (float)uniformRandom(0, extent.x),
+ d * extent.y,
+ (float)uniformRandom(0, extent.z));
+ }
+}
+
+
+Vector3 AABox::randomInteriorPoint() const {
+ return Vector3(
+ (float)uniformRandom(lo.x, hi.x),
+ (float)uniformRandom(lo.y, hi.y),
+ (float)uniformRandom(lo.z, hi.z));
+}
+
+
+bool AABox::intersects(const AABox& other) const {
+ // Must be overlap along all three axes.
+ // Try to find a separating axis.
+
+ for (int a = 0; a < 3; ++a) {
+
+ // |--------|
+ // |------|
+
+ if ((lo[a] > other.hi[a]) ||
+ (hi[a] < other.lo[a])) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+int AABox::dummy = 0;
+
+bool AABox::culledBy(
+ const Array<Plane>& plane,
+ int& cullingPlane,
+ const uint32 _inMask,
+ uint32& childMask) const {
+
+ uint32 inMask = _inMask;
+ assert(plane.size() < 31);
+
+ childMask = 0;
+
+ const bool finite =
+ (abs(lo.x) < G3D::finf()) &&
+ (abs(hi.x) < G3D::finf()) &&
+ (abs(lo.y) < G3D::finf()) &&
+ (abs(hi.y) < G3D::finf()) &&
+ (abs(lo.z) < G3D::finf()) &&
+ (abs(hi.z) < G3D::finf());
+
+ // See if there is one plane for which all of the
+ // vertices are in the negative half space.
+ for (int p = 0; p < plane.size(); ++p) {
+
+ // Only test planes that are not masked
+ if ((inMask & 1) != 0) {
+
+ Vector3 corner;
+
+ int numContained = 0;
+ int v = 0;
+
+ // We can early-out only if we have found one point on each
+ // side of the plane (i.e. if we are straddling). That
+ // occurs when (numContained < v) && (numContained > 0)
+ for (v = 0; (v < 8) && ((numContained == v) || (numContained == 0)); ++v) {
+ // Unrolling these 3 if's into a switch decreases performance
+ // by about 2x
+ corner.x = (v & 1) ? hi.x : lo.x;
+ corner.y = (v & 2) ? hi.y : lo.y;
+ corner.z = (v & 4) ? hi.z : lo.z;
+
+ if (finite) { // this branch is highly predictable
+ if (plane[p].halfSpaceContainsFinite(corner)) {
+ ++numContained;
+ }
+ } else {
+ if (plane[p].halfSpaceContains(corner)) {
+ ++numContained;
+ }
+ }
+ }
+
+ if (numContained == 0) {
+ // Plane p culled the box
+ cullingPlane = p;
+
+ // The caller should not recurse into the children,
+ // since the parent is culled. If they do recurse,
+ // make them only test against this one plane, which
+ // will immediately cull the volume.
+ childMask = 1 << p;
+ return true;
+
+ } else if (numContained < v) {
+ // The bounding volume straddled the plane; we have
+ // to keep testing against this plane
+ childMask |= (1 << p);
+ }
+ }
+
+ // Move on to the next bit.
+ inMask = inMask >> 1;
+ }
+
+ // None of the planes could cull this box
+ cullingPlane = -1;
+ return false;
+}
+
+
+bool AABox::culledBy(
+ const Array<Plane>& plane,
+ int& cullingPlane,
+ const uint32 _inMask) const {
+
+ uint32 inMask = _inMask;
+ assert(plane.size() < 31);
+
+ const bool finite =
+ (abs(lo.x) < G3D::finf()) &&
+ (abs(hi.x) < G3D::finf()) &&
+ (abs(lo.y) < G3D::finf()) &&
+ (abs(hi.y) < G3D::finf()) &&
+ (abs(lo.z) < G3D::finf()) &&
+ (abs(hi.z) < G3D::finf());
+
+ // See if there is one plane for which all of the
+ // vertices are in the negative half space.
+ for (int p = 0; p < plane.size(); ++p) {
+
+ // Only test planes that are not masked
+ if ((inMask & 1) != 0) {
+
+ bool culled = true;
+ Vector3 corner;
+
+ int v;
+
+ // Assume this plane culls all points. See if there is a point
+ // not culled by the plane... early out when at least one point
+ // is in the positive half space.
+ for (v = 0; (v < 8) && culled; ++v) {
+
+ // Unrolling these 3 if's into a switch decreases performance
+ // by about 2x
+ corner.x = (v & 1) ? hi.x : lo.x;
+ corner.y = (v & 2) ? hi.y : lo.y;
+ corner.z = (v & 4) ? hi.z : lo.z;
+
+ if (finite) { // this branch is highly predictable
+ culled = ! plane[p].halfSpaceContainsFinite(corner);
+ } else {
+ culled = ! plane[p].halfSpaceContains(corner);
+ }
+ }
+
+ if (culled) {
+ // Plane p culled the box
+ cullingPlane = p;
+
+ return true;
+ }
+ }
+
+ // Move on to the next bit.
+ inMask = inMask >> 1;
+ }
+
+ // None of the planes could cull this box
+ cullingPlane = -1;
+ return false;
+}
+
+
+bool AABox::intersects(const class Sphere& sphere) const {
+ double d = 0;
+
+ //find the square of the distance
+ //from the sphere to the box
+ for (int i = 0; i < 3; ++i) {
+ if (sphere.center[i] < lo[i]) {
+ d += square(sphere.center[i] - lo[i]);
+ } else if (sphere.center[i] > hi[i]) {
+ d += square(sphere.center[i] - hi[i]);
+ }
+ }
+
+ return d <= square(sphere.radius);
+}
+
+Vector3 AABox::corner(int index) const {
+
+ // default constructor inits all components to 0
+ Vector3 v;
+
+ switch (index)
+ {
+ case 0:
+ v.x = lo.x;
+ v.y = lo.y;
+ v.z = hi.z;
+ break;
+
+ case 1:
+ v.x = hi.x;
+ v.y = lo.y;
+ v.z = hi.z;
+ break;
+
+ case 2:
+ v.x = hi.x;
+ v.y = hi.y;
+ v.z = hi.z;
+ break;
+
+ case 3:
+ v.x = lo.x;
+ v.y = hi.y;
+ v.z = hi.z;
+ break;
+
+ case 4:
+ v.x = lo.x;
+ v.y = lo.y;
+ v.z = lo.z;
+ break;
+
+ case 5:
+ v.x = hi.x;
+ v.y = lo.y;
+ v.z = lo.z;
+ break;
+
+ case 6:
+ v.x = hi.x;
+ v.y = hi.y;
+ v.z = lo.z;
+ break;
+
+ case 7:
+ v.x = lo.x;
+ v.y = hi.y;
+ v.z = lo.z;
+ break;
+
+ default:
+ debugAssertM(false, "Invalid corner index");
+ break;
+ }
+
+ return v;
+}
+
+
+}