---

sglSphereBound.hpp

/*****************************************************************************
 * SGL: A Scene Graph Library
 *
 * Copyright (C) 1997-2001  Scott McMillan   All Rights Reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *****************************************************************************
 *     File: sglSphereBound.hpp
 *  Created: 14 November 1998
 *  Summary: bounding sphere class (for view frustum culling)
 *****************************************************************************/

#ifndef __SGL_SPHERE_BOUND_HPP
#define __SGL_SPHERE_BOUND_HPP

#include <sgl.h>
#include <sglVector.hpp>
#include <sglPlane.hpp>
#include <sglPolytope.hpp>

#include <sglSegment.hpp>
#include <sglBound.hpp>
#include <sglBoxBound.hpp>

// zero radius is empty, negative radius is infinite

//----------------------------------------------------------------------------

template <class T>
class sglSphereBound : public sglBound
{
public:
   sglSphereBound() : m_radius(0), m_center(0,0,0) {};

   template <class S>
   sglSphereBound(const sglSphereBound<S> &rhs)
         : m_radius((T)rhs.getRadius()),m_center(rhs.getCenter()) {}
         

   ~sglSphereBound() {};

#ifndef WIN32
   sglSphereBound &operator=(const sglSphereBound<T> &rhs)
      {
         if (this != &rhs)   // check for self assignment
         {
            m_radius = rhs.m_radius;
            m_center = rhs.m_center;
         }
         return *this;
      }
#endif

   template <class S>
   sglSphereBound &operator=(const sglSphereBound<S> &rhs)
      {
         if (this != (sglSphereBound<T>*)&rhs)   // check for self assignment
         {
            m_radius = rhs.getRadius();
            m_center = rhs.getCenter();
         }
         return *this;
      }

   template <class S>
   bool operator==(const sglSphereBound<S> &rhs) const
      {
         return ((m_radius == rhs.getRadius()) &&
                 (m_center == rhs.getCenter()));
      }

   void makeEmpty() { m_radius = 0.0; }
   bool isEmpty() const { return (m_radius == 0.0); }
   bool isInfinite() const { return (m_radius < 0.0); }

   // ---------------------------------------------------------
   // get/set center and radius
   void setCenter(T x, T y, T z) {m_center.set(x,y,z);}
   template <class S> void setCenter(const sglVec3<S> &v) { m_center = v; }
   const sglVec3<T> &getCenter() const  { return m_center; }

   void setRadius(T radius) { m_radius = radius; }
   T getRadius() const { return m_radius; }

   // ---------------------------------------------------------
   // transform the sphere
   template <class S>
   void mul(const sglMat4<S>& mat)
      {
         sglVec3<T> center;
         center[0] = (T)(m_center[0]*mat[0][0] + m_center[1]*mat[1][0] +
                         m_center[2]*mat[2][0] + mat[3][0]);
         center[1] = (T)(m_center[0]*mat[0][1] + m_center[1]*mat[1][1] +
                         m_center[2]*mat[2][1] + mat[3][1]);
         center[2] = (T)(m_center[0]*mat[0][2] + m_center[1]*mat[1][2] +
                         m_center[2]*mat[2][2] + mat[3][2]);
         m_center = center;

         // STILL NEED TO DO THE SCALE for the radius
      }

   // ---------------------------------------------------------
   // generate bounding spheres from other volumes
   void computeFromBox(const sglBoxBound &box);

   void expandToInclude(const sglSphereBound<T> &sphere);

   // ---------------------------------------------------------
   // intersection routines
   template <class S>
   IntersectResultEnum intersect(sglSegment<S> &ray) const
      {
         // check special cases of bounding sphere
         if (isEmpty()) return eOUTSIDE;
         if (isInfinite()) return eINSIDE;

         // if ray starts inside sphere return inside
         sglVec3<S> eo = m_center - ray.getPos();
         //cout << "eo = " << eo << endl;
         double d_sqr = eo.dot(eo);
         double r_sqr = m_radius*m_radius;
         if (d_sqr < r_sqr)
         {
            return eINSIDE;
         }

         // ray starts outside now find out if it crosses into sphere
         double v = eo.dot(ray.getDir());
         //cout << "eo.dot(dir) = " << v << endl;
         if ((v < 0) || (v > (m_radius + ray.getLen())))
         {
            return eOUTSIDE;
         }

         double disc = r_sqr - d_sqr + v*v;
         //cout << "disc = " << disc << endl;

         if (disc < 0)
         {
            return eOUTSIDE;
         }
         else
         {
            double new_len = v - sqrt(disc);
            if (ray.getLen() < new_len)
            {
               return eOUTSIDE;
            }
            else
            {
               ray.setLen(new_len);
               return eINTERSECT;
            }
         }
      }

   template <class S>
   IntersectResultEnum intersect(const sglPlane<S> &plane) const
      {
         // by definition a plane cuts the space in two parts

         // an infinite sphere is always bisected
         if (m_radius < 0.0)  return eINTERSECT;

         // an empty sphere is culled, so it is outside
         if (m_radius == 0.0) return eOUTSIDE;

         // check a finite sphere
         T p = (T)plane.signedDistance(m_center);

         if (p - m_radius > 0.0)      return eINSIDE;
         else if (p + m_radius < 0.0) return eOUTSIDE;
         else                         return eINTERSECT;
      }

   template <class S>
   IntersectResultEnum intersect(const sglPolytope<S> &ptope) const
      {
         // if sphere is infinite set all cull flags back on and return
         // eINTERSECT (basically reset the intersection
         if (isInfinite())
         {
            return eINTERSECT;
         }

         bool intersect_flag = false;

         for (unsigned int i=0; i<ptope.getNumPlanes(); i++)
         {
            IntersectResultEnum result = intersect(ptope.getPlane(i));
            if (result == eOUTSIDE)
            {
               return eOUTSIDE;
            }
            else if (result == eINTERSECT)
            {
               intersect_flag = true;
            }
         }

         if (!intersect_flag)
         {
            return eINSIDE;
         }

         // note: this is not optimal as we may be outside at a corner and
         // still return eINTERSECT
         return eINTERSECT;
      }

   template <class S>
   IntersectResultEnum intersect(const sglPolytope<S> &ptope,
                                 unsigned int &cull_flags) const
      {
         // if sphere is infinite set all cull flags back on and return
         // eINTERSECT (basically reset the intersection
         if (isInfinite())
         {
            for (unsigned int i=0; i<ptope.getNumPlanes(); i++)
            {
               cull_flags |= (1<<i);
            }
            return eINTERSECT;
         }

         unsigned int new_flags = 0;

         for (unsigned int i=0; i<ptope.getNumPlanes(); i++)
         {
            // do the intersection test if this plane is still active as
            // indicated by a bit in the cull_flags bit field;
            if (cull_flags & (1<<i))
            {
               IntersectResultEnum result = intersect(ptope.getPlane(i));
               if (result == eOUTSIDE)
               {
                  cull_flags=0;
                  return eOUTSIDE;
               }
               else if (result == eINTERSECT)
               {
                  new_flags |= (1<<i);
               }
            }
         }

         if (new_flags == 0)
         {
            cull_flags=0;
            return eINSIDE;
         }

         // note: this is not optimal as we may be outside at a corner and
         // still return eINTERSECT
         cull_flags = new_flags;
         return eINTERSECT;
      }

   //bool contains(const sglVec3f& pnt) const;
   //bool contains(const sglSphereBound& sph) const;

   // ---------------------------------------------------------
   // Informational output
   void drawImmediate() const;

   friend ostream &operator<<(ostream &ostrm, const sglSphereBound<T> &sphere)
      {
         if (sphere.isEmpty())
            return (ostrm << "bsphere: [empty]");
         if (sphere.isInfinite())
            return (ostrm << "bsphere: [infinite]");

         return (ostrm << "bsphere:  [" << setprecision(12)
                 << sphere.m_radius << setprecision(6) << ", "
                 << sphere.m_center << "]");
      }

protected:
   T m_radius;
   sglVec3<T> m_center;
};


//----------------------------------------------------------------------------
// convenience types:
//    template class 'should' only be float or double

typedef sglSphereBound<float>  sglSphereBoundf;
typedef sglSphereBound<double> sglSphereBoundd;

#endif

---