Main Page   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members  

ball_funcs.h

00001 // ball_funcs.h (n-dimensional ball implementation)
00002 //
00003 //  The WorldForge Project
00004 //  Copyright (C) 2000, 2001  The WorldForge Project
00005 //
00006 //  This program is free software; you can redistribute it and/or modify
00007 //  it under the terms of the GNU General Public License as published by
00008 //  the Free Software Foundation; either version 2 of the License, or
00009 //  (at your option) any later version.
00010 //
00011 //  This program is distributed in the hope that it will be useful,
00012 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 //  GNU General Public License for more details.
00015 //
00016 //  You should have received a copy of the GNU General Public License
00017 //  along with this program; if not, write to the Free Software
00018 //  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00019 //
00020 //  For information about WorldForge and its authors, please contact
00021 //  the Worldforge Web Site at http://www.worldforge.org.
00022 //
00023 
00024 // Author: Ron Steinke
00025 
00026 #ifndef WFMATH_BALL_FUNCS_H
00027 #define WFMATH_BALL_FUNCS_H
00028 
00029 #include <wfmath/const.h>
00030 #include <wfmath/point.h>
00031 #include <wfmath/axisbox.h>
00032 #include <wfmath/ball.h>
00033 #include <wfmath/miniball.h>
00034 
00035 namespace WFMath {
00036 
00037 template<const int dim>
00038 bool Ball<dim>::isEqualTo(const Ball<dim>& b, double epsilon) const
00039 {
00040   return Equal(m_center, b.m_center, epsilon)
00041       && Equal(m_radius, b.m_radius, epsilon);
00042 }
00043 
00044 template<const int dim>
00045 bool Ball<dim>::operator< (const Ball<dim>& b) const
00046 {
00047   if(!Equal(m_radius, b.m_radius))
00048     return m_radius < b.m_radius;
00049 
00050   return m_center < b.m_center;
00051 }
00052 
00053 template<const int dim>
00054 AxisBox<dim> Ball<dim>::boundingBox() const
00055 {
00056   Point<dim> p_low, p_high;
00057 
00058   for(int i = 0; i < dim; ++i) {
00059     p_low[i] = m_center[i] - m_radius;
00060     p_high[i] = m_center[i] + m_radius;
00061   }
00062 
00063   bool valid = m_center.isValid();
00064 
00065   p_low.setValid(valid);
00066   p_high.setValid(valid);
00067 
00068   return AxisBox<dim>(p_low, p_high, true);
00069 }
00070 
00071 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00072 template<const int dim, template<class> class container>
00073 Ball<dim> BoundingSphere(const container<Point<dim> >& c)
00074 {
00075   _miniball::Miniball<dim> m;
00076   _miniball::Wrapped_array<dim> w;
00077 
00078   typename container<Point<dim> >::const_iterator i, end = c.end();
00079   bool valid = true;
00080 
00081   for(i = c.begin(); i != end; ++i) {
00082     valid = valid && i->isValid();
00083     for(int j = 0; j < dim; ++j)
00084       w[j] = (*i)[j];
00085     m.check_in(w);
00086   }
00087 
00088   m.build();
00089 
00090 #ifndef NDEBUG
00091   double dummy;
00092 #endif
00093   assert("Check that bounding sphere is good to library accuracy" &&
00094          m.accuracy(dummy) < WFMATH_EPSILON);
00095 
00096   w = m.center();
00097   Point<dim> center;
00098 
00099   for(int j = 0; j < dim; ++j)
00100     center[j] = w[j];
00101 
00102   center.setValid(valid);
00103 
00104   return Ball<dim>(center, sqrt(m.squared_radius()));
00105 }
00106 
00107 template<const int dim, template<class> class container>
00108 Ball<dim> BoundingSphereSloppy(const container<Point<dim> >& c)
00109 {
00110   // This is based on the algorithm given by Jack Ritter
00111   // in Volume 2, Number 4 of Ray Tracing News
00112   // <http://www.acm.org/tog/resources/RTNews/html/rtnews7b.html>
00113 
00114   typename container<Point<dim> >::const_iterator i = c.begin(),
00115                                                 end = c.end();
00116   assert(i != end);
00117 
00118   CoordType min[dim], max[dim];
00119   typename container<Point<dim> >::const_iterator min_p[dim], max_p[dim];
00120   bool valid = i->isValid();
00121 
00122   for(int j = 0; j < dim; ++j) {
00123     min[j] = max[j] = (*i)[j];
00124     min_p[j] = max_p[j] = i;
00125   }
00126 
00127   while(++i != end) {
00128     valid = valid && i->isValid();
00129     for(int j = 0; j < dim; ++j) {
00130       if(min[j] > (*i)[j]) {
00131         min[j] = (*i)[j];
00132         min_p[j] = i;
00133       }
00134       if(max[j] < (*i)[j]) {
00135         max[j] = (*i)[j];
00136         max_p[j] = i;
00137       }
00138     }
00139   }
00140 
00141   CoordType span = -1;
00142   int direction = -1;
00143 
00144   for(int j = 0; j < dim; ++j) {
00145     CoordType new_span = max[j] - min[j];
00146     if(new_span > span) {
00147       span = new_span;
00148       direction = j;
00149     }
00150   }
00151 
00152   assert("Have a direction of maximum size" && direction != -1);
00153 
00154   Point<dim> center = Midpoint(*(min_p[direction]), *(max_p[direction]));
00155   CoordType dist = SloppyDistance(*(min_p[direction]), center);
00156 
00157   for(i = c.begin(); i != end; ++i) {
00158     if(i == min_p[direction] || i == max_p[direction])
00159       continue; // We already have these
00160 
00161     CoordType new_dist = SloppyDistance(*i, center);
00162 
00163     if(new_dist > dist) {
00164       CoordType delta_dist = (new_dist - dist) / 2;
00165       // Even though new_dist may be too large, delta_dist / new_dist
00166       // always gives enough of a shift to include the new point.
00167       center += (*i - center) * delta_dist / new_dist;
00168       dist += delta_dist;
00169       assert("Shifted ball contains new point" &&
00170              SquaredDistance(*i, center) <= dist * dist);
00171     }
00172   }
00173 
00174   center.setValid(valid);
00175 
00176   return Ball<2>(center, dist);
00177 }
00178 #endif
00179 
00180 // These two are here, instead of defined in the class, to
00181 // avoid include order problems
00182 
00183 template<const int dim>
00184 inline Ball<dim> Point<dim>::boundingSphere() const
00185 {
00186   return Ball<dim>(*this, 0);
00187 }
00188 
00189 template<const int dim>
00190 inline Ball<dim> Point<dim>::boundingSphereSloppy() const
00191 {
00192   return Ball<dim>(*this, 0);
00193 }
00194 
00195 } // namespace WFMath
00196 
00197 #endif  // WFMATH_BALL_FUNCS_H

Generated on Wed May 28 09:20:31 2003 for WFMath by doxygen1.3-rc3