text: /**
   @file Sphere.cpp
  
   Sphere class
  
   @maintainer Morgan McGuire, http://graphics.cs.williams.edu
  
   @created 2001-04-17
   @edited  2009-01-20
   */
  
  #include "G3D/platform.h"
  #include "G3D/Sphere.h"
  #include "G3D/stringutils.h"
  #include "G3D/BinaryOutput.h"
  #include "G3D/BinaryInput.h"
  #include "G3D/AABox.h"
  #include "G3D/Plane.h"
  
  namespace G3D {
  int32 Sphere::dummy;
  
  Sphere::Sphere(class BinaryInput& b) {
      deserialize(b);
  }
  
  void Sphere::serialize(class BinaryOutput& b) const {
      center.serialize(b);
      b.writeFloat64(radius);
  }
  
  void Sphere::deserialize(class BinaryInput& b) {
      center.deserialize(b);
      radius = (float)b.readFloat64();
  }
  
  std::string Sphere::toString() const {
      return format("Sphere(<%g, %g, %g>, %g)",
                    center.x, center.y, center.z, radius);
  }
  
  bool Sphere::contains(const Vector3& point) const {
      float distance = (center - point).squaredMagnitude();
      return distance <= square(radius);
  }
  
  bool Sphere::contains(const Sphere& other) const {
      float distance = (center - other.center).squaredMagnitude();
      return (radius >= other.radius) && (distance <= square(radius - other.radius));
  }
  
  bool Sphere::intersects(const Sphere& other) const {
      return (other.center - center).length() <= (radius + other.radius);
  }
  
  void Sphere::merge(const Sphere& other) {
      if (other.contains(*this)) {
          *this = other;
      } else if (! contains(other)) {
          // The farthest distance is along the axis between the centers, which
          // must not be colocated since neither contains the other.
          Vector3 toMe = center - other.center;
          // Get a point on the axis from each
          toMe = toMe.direction();
          const Vector3& A = center + toMe * radius;
          const Vector3& B = other.center - toMe * other.radius;
  
          // Now just bound the A->B segment
          center = (A + B) * 0.5f;
          radius = (A - B).length();
      }
      // (if this contains other, we're done)
  }
  
  bool Sphere::culledBy(
      const Array<Plane>&		plane,
      int&				    cullingPlaneIndex,
      const uint32			inMask,
      uint32&					outMask) const {
      return culledBy(plane.getCArray(), plane.size(), cullingPlaneIndex, inMask, outMask);
  }
  
  bool Sphere::culledBy(
                        const Array<Plane>&		plane,
                        int&				    cullingPlaneIndex,
                        const uint32			inMask) const {
      return culledBy(plane.getCArray(), plane.size(), cullingPlaneIndex, inMask);
  }
  
  bool Sphere::culledBy(
      const class Plane*  plane,
      int                 numPlanes,
      int&				cullingPlane,
      const uint32		_inMask,
      uint32&             childMask) const {
      if (radius == finf()) {
          // No plane can cull the infinite box
          return false;
      }
  
  	uint32 inMask = _inMask;
  	assert(numPlanes < 31);
  
      childMask = 0;
  
      // See if there is one plane for which all of the
  	// vertices are in the negative half space.
      for (int p = 0; p < numPlanes; p++) {
  		// Only test planes that are not masked
  		if ((inMask & 1) != 0) {
              bool culledLow = ! plane[p].halfSpaceContainsFinite(center + plane[p].normal() * radius);
              bool culledHigh = ! plane[p].halfSpaceContainsFinite(center - plane[p].normal() * radius);
  
  			if (culledLow) {
  				// Plane p culled the sphere
  				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 (culledHigh) {
                  // 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 Sphere::culledBy(
      const class Plane*  plane,
      int                 numPlanes,
  	int&				cullingPlane,
  	const uint32		_inMask) const {
  	uint32 inMask = _inMask;
  	assert(numPlanes < 31);
  
      // See if there is one plane for which all of the
  	// vertices are in the negative half space.
      for (int p = 0; p < numPlanes; p++) {
  		// Only test planes that are not masked
  		if ((inMask & 1) != 0) {
  			bool culled = ! plane[p].halfSpaceContains(center + plane[p].normal() * radius);
  			if (culled) {
  				// Plane p culled the sphere
  				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;
  }
  
  Vector3 Sphere::randomSurfacePoint() const {
      return Vector3::random() * radius + center;
  }
  
  Vector3 Sphere::randomInteriorPoint() const {
      Vector3 result;
      do {
          result = Vector3(uniformRandom(-1, 1),
                           uniformRandom(-1, 1),
                           uniformRandom(-1, 1));
      } while (result.squaredMagnitude() >= 1.0f);
  
      return result * radius + center;
  }
  
  float Sphere::volume() const {
      return (float)pi() * (4.0f / 3.0f) * powf((float)radius, 3.0f);
  }
  
  float Sphere::area() const {
      return (float)pi() * 4.0f * powf((float)radius, 2.0f);
  }
  
  void Sphere::getBounds(AABox& out) const {
      Vector3 extent(radius, radius, radius);
      out = AABox(center - extent, center + extent);
  }
  } // namespace