Main Page | Namespace List | Class List | File List | Namespace Members | Class 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 inline 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 AxisBox<dim> Ball<dim>::boundingBox() const 00046 { 00047 Point<dim> p_low, p_high; 00048 00049 for(int i = 0; i < dim; ++i) { 00050 p_low[i] = m_center[i] - m_radius; 00051 p_high[i] = m_center[i] + m_radius; 00052 } 00053 00054 bool valid = m_center.isValid(); 00055 00056 p_low.setValid(valid); 00057 p_high.setValid(valid); 00058 00059 return AxisBox<dim>(p_low, p_high, true); 00060 } 00061 00062 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS 00063 template<const int dim, template<class> class container> 00064 Ball<dim> BoundingSphere(const container<Point<dim> >& c) 00065 { 00066 _miniball::Miniball<dim> m; 00067 _miniball::Wrapped_array<dim> w; 00068 00069 typename container<Point<dim> >::const_iterator i, end = c.end(); 00070 bool valid = true; 00071 00072 for(i = c.begin(); i != end; ++i) { 00073 valid = valid && i->isValid(); 00074 for(int j = 0; j < dim; ++j) 00075 w[j] = (*i)[j]; 00076 m.check_in(w); 00077 } 00078 00079 m.build(); 00080 00081 #ifndef NDEBUG 00082 double dummy; 00083 #endif 00084 assert("Check that bounding sphere is good to library accuracy" && 00085 m.accuracy(dummy) < WFMATH_EPSILON); 00086 00087 w = m.center(); 00088 Point<dim> center; 00089 00090 for(int j = 0; j < dim; ++j) 00091 center[j] = w[j]; 00092 00093 center.setValid(valid); 00094 00095 return Ball<dim>(center, sqrt(m.squared_radius())); 00096 } 00097 00098 template<const int dim, template<class> class container> 00099 Ball<dim> BoundingSphereSloppy(const container<Point<dim> >& c) 00100 { 00101 // This is based on the algorithm given by Jack Ritter 00102 // in Volume 2, Number 4 of Ray Tracing News 00103 // <http://www.acm.org/tog/resources/RTNews/html/rtnews7b.html> 00104 00105 typename container<Point<dim> >::const_iterator i = c.begin(), 00106 end = c.end(); 00107 assert(i != end); 00108 00109 CoordType min[dim], max[dim]; 00110 typename container<Point<dim> >::const_iterator min_p[dim], max_p[dim]; 00111 bool valid = i->isValid(); 00112 00113 for(int j = 0; j < dim; ++j) { 00114 min[j] = max[j] = (*i)[j]; 00115 min_p[j] = max_p[j] = i; 00116 } 00117 00118 while(++i != end) { 00119 valid = valid && i->isValid(); 00120 for(int j = 0; j < dim; ++j) { 00121 if(min[j] > (*i)[j]) { 00122 min[j] = (*i)[j]; 00123 min_p[j] = i; 00124 } 00125 if(max[j] < (*i)[j]) { 00126 max[j] = (*i)[j]; 00127 max_p[j] = i; 00128 } 00129 } 00130 } 00131 00132 CoordType span = -1; 00133 int direction = -1; 00134 00135 for(int j = 0; j < dim; ++j) { 00136 CoordType new_span = max[j] - min[j]; 00137 if(new_span > span) { 00138 span = new_span; 00139 direction = j; 00140 } 00141 } 00142 00143 assert("Have a direction of maximum size" && direction != -1); 00144 00145 Point<dim> center = Midpoint(*(min_p[direction]), *(max_p[direction])); 00146 CoordType dist = SloppyDistance(*(min_p[direction]), center); 00147 00148 for(i = c.begin(); i != end; ++i) { 00149 if(i == min_p[direction] || i == max_p[direction]) 00150 continue; // We already have these 00151 00152 CoordType new_dist = SloppyDistance(*i, center); 00153 00154 if(new_dist > dist) { 00155 CoordType delta_dist = (new_dist - dist) / 2; 00156 // Even though new_dist may be too large, delta_dist / new_dist 00157 // always gives enough of a shift to include the new point. 00158 center += (*i - center) * delta_dist / new_dist; 00159 dist += delta_dist; 00160 assert("Shifted ball contains new point" && 00161 SquaredDistance(*i, center) <= dist * dist); 00162 } 00163 } 00164 00165 center.setValid(valid); 00166 00167 return Ball<2>(center, dist); 00168 } 00169 #endif 00170 00171 // These two are here, instead of defined in the class, to 00172 // avoid include order problems 00173 00174 template<const int dim> 00175 inline Ball<dim> Point<dim>::boundingSphere() const 00176 { 00177 return Ball<dim>(*this, 0); 00178 } 00179 00180 template<const int dim> 00181 inline Ball<dim> Point<dim>::boundingSphereSloppy() const 00182 { 00183 return Ball<dim>(*this, 0); 00184 } 00185 00186 } // namespace WFMath 00187 00188 #endif // WFMATH_BALL_FUNCS_H

Generated on Thu Jul 29 07:09:56 2004 for WFMath by doxygen 1.3.7