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