---

sglBoxBound.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: sglBoxBound.hpp
 *  Created: 14 November 1998
 *  Summary: bounding boxes for sglGeoSets
 *****************************************************************************/

#ifndef __SGL_BOX_BOUND_HPP
#define __SGL_BOX_BOUND_HPP

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

class SGL_DLL_API sglBoxBound : public sglBound
{
public:
   sglBoxBound();
   sglBoxBound(const sglBoxBound &);
   sglBoxBound &operator=(const sglBoxBound &);

   ~sglBoxBound() {};

   void makeEmpty();
   bool isEmpty() const { return (m_min[0]>m_max[0]); }

   // ---------------------------------------------------------
   // get/set min and max
   void setMin(float x, float y, float z) { m_min.set(x,y,z); }
   void setMin(const sglVec3f &min) { m_min = min; }
   const sglVec3f &getMin() const   { return m_min; }

   void setMax(float x, float y, float z) { m_max.set(x,y,z); }
   void setMax(const sglVec3f &max) { m_max = max; }
   const sglVec3f &getMax() const   { return m_max; }

   // ---------------------------------------------------------
   // generating bounding boxes from other volumes
   void expandToInclude(const sglVec3f & point);  // assumes min/max set
   void expandToInclude(const sglBoxBound &box);
   static void expandToInclude2s(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude2i(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude2f(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude2d(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude3s(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude3i(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude3f(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude3d(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude4s(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude4i(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude4f(sglBoxBound *bbox, const void *ptr);
   static void expandToInclude4d(sglBoxBound *bbox, const void *ptr);

   typedef void (*ExpandToIncludeFunc)(sglBoxBound *, const void *vtx);

   // Get the expandToInclude function for the given vertex data type.
   static ExpandToIncludeFunc getExpandToIncludeFunc(int vertex_type)
      { return s_expand_to_include_func_table[vertex_type]; }

   // ---------------------------------------------------------
   // intersection routines

   // Adapted from "Fast Ray-Box Intersection" by Andrew Woo
   // from _Graphics Gems_, Academic Press, 1990
   template <class S>
   IntersectResultEnum intersect(sglSegment<S> &ray) const
      {
         // check special case of empty bounding box
         if (isEmpty()) return eOUTSIDE;

         enum LocationEnum {eRIGHT = 0, eLEFT = 1, eMIDDLE = 2};
         int quadrant[3];
         register unsigned int i;
         unsigned int whichPlane;
         sglVec3<S> maxT;
         sglVec3<S> candidatePlane;
         sglVec3<S> coord;

         // The following is inefficient, but simplifies the code for
         // the time being 
         sglVec3<S> origin(ray.getPos());
         sglVec3<S> dir(ray.getDir());

         // Find candidate planes; i.e. sides of box facing the origin
         // of the ray (also detects is ray starts inside the bbox
         bool inside = TRUE;
         for (i=0; i<3; i++)
         {
            if (origin[i] < m_min[i])
            {
               quadrant[i] = eLEFT;
               candidatePlane[i] = m_min[i];
               inside = FALSE;
            }
            else if (origin[i] > m_max[i])
            {
               quadrant[i] = eRIGHT;
               candidatePlane[i] = m_max[i];
               inside = FALSE;
            }
            else
            {
               quadrant[i] = eMIDDLE;
            }
         }

         // Ray origin inside bounding box
         if (inside)
         {
            return eINSIDE;
         }


         // Calculate T distances to candidate planes 
         for (i = 0; i < 3; i++)
         {
            if ((quadrant[i] != eMIDDLE) && (dir[i] != 0.))
               maxT[i] = (candidatePlane[i]-origin[i]) / dir[i];
            else
               maxT[i] = -1.;
         }

         // Get largest of the maxT's for final choice of intersection 
         whichPlane = 0;
         for (i = 1; i < 3; i++)
         {
            if (maxT[whichPlane] < maxT[i])
            {
               whichPlane = i;
            }
         }

         // Check final candidate actually inside box
         if (maxT[whichPlane] < 0. || maxT[whichPlane] > ray.getLen())
         {
            return eOUTSIDE;
         }

         for (i = 0; i < 3; i++)
         {
            if (whichPlane != i)
            {
               coord[i] = origin[i] + maxT[whichPlane] *dir[i];
               if (coord[i] < m_min[i] || coord[i] > m_max[i])
               {
                  return eOUTSIDE;
               }
            }
            else
            {
               coord[i] = candidatePlane[i];
            }
         }

         ray.setLen(maxT[whichPlane]);
         return eINTERSECT;            // ray hits box 
      }


   template <class S>
   IntersectResultEnum intersect(const sglPlane<S> &plane) const 
      {
         // empty box is not intersected
         if (m_max[0] < m_min[0])
            return eOUTSIDE;

         // find the extremities
         sglVec3f vmin, vmax;
         sglVec3f pnorm = plane.getNormal();

         if (pnorm[0] > 0.f)
         {
            vmin[0] = m_min[0];
            vmax[0] = m_max[0];
         }
         else
         {
            vmin[0] = m_max[0];
            vmax[0] = m_min[0];
         }

         if (pnorm[1] > 0.f)
         {
            vmin[1] = m_min[1];
            vmax[1] = m_max[1];
         }
         else
         {
            vmin[1] = m_max[1];
            vmax[1] = m_min[1];
         }

         if (pnorm[2] > 0.f)
         {
            vmin[2] = m_min[2];
            vmax[2] = m_max[2];
         }
         else
         {
            vmin[2] = m_max[2];
            vmax[2] = m_min[2];
         }

         // now lets do the math
         if (plane.signedDistance(vmax) < 0.f)
            return eOUTSIDE;
         else if (plane.signedDistance(vmin) >= 0.f)
            return eINSIDE;
         else 
            return eINTERSECT;
      }

   template <class S>
   IntersectResultEnum intersect(const sglPolytope<S> &ptope) const 
      {
         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 Intersect
         return eINTERSECT;
      }

#if 1 //defined(WIN32)
   template <class S>
   IntersectResultEnum intersect(const sglPolytope<S> &ptope,
                                 unsigned int &plane_flags) const 
      {
         unsigned int cull_flags = 0;

         for (unsigned int i=0; i<ptope.getNumPlanes(); i++)
         {
            // only check those planes that intersected the previous
            // bounding volume 
            if (plane_flags & (1<<i))
            {
               IntersectResultEnum result = intersect(ptope.getPlane(i));
               if (result == eOUTSIDE)
               {
                  plane_flags=0;
                  return eOUTSIDE;
               }
               else if (result == eINTERSECT)
               {
                  cull_flags |= (1<<i);
               }
            }
         }

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

         // note: this is not optimal as we may be outside at a corner and
         // still return Intersect
         plane_flags = cull_flags;
         return eINTERSECT;
      }
#else
   IntersectResultEnum intersect(const sglPolytope<float> &ptope,
                                 unsigned int &plane_flags) const 
      {
         unsigned int cull_flags = 0;

         for (unsigned int i=0; i<ptope.getNumPlanes(); i++)
         {
            // only check those planes that intersected the previous
            // bounding volume 
            if (plane_flags & (1<<i))
            {
               IntersectResultEnum result = intersect(ptope.getPlane(i));
               if (result == eOUTSIDE)
               {
                  plane_flags=0;
                  return eOUTSIDE;
               }
               else if (result == eINTERSECT)
               {
                  cull_flags |= (1<<i);
               }
            }
         }

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

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

   IntersectResultEnum intersect(const sglPolytope<double> &ptope,
                                 unsigned int &plane_flags) const 
      {
         unsigned int cull_flags = 0;

         for (unsigned int i=0; i<ptope.getNumPlanes(); i++)
         {
            // only check those planes that intersected the previous
            // bounding volume 
            if (plane_flags & (1<<i))
            {
               IntersectResultEnum result = intersect(ptope.getPlane(i));
               if (result == eOUTSIDE)
               {
                  plane_flags=0;
                  return eOUTSIDE;
               }
               else if (result == eINTERSECT)
               {
                  cull_flags |= (1<<i);
               }
            }
         }

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

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

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

   friend SGL_DLL_API ostream &operator<<(ostream &ostrm,
                                          const sglBoxBound &box);

private:
   static ExpandToIncludeFunc s_expand_to_include_func_table[24];

   sglVec3f m_min;
   sglVec3f m_max;
};

SGL_DLL_API ostream &operator<<(ostream &ostrm, const sglBoxBound &box);

#endif

---