00001
00023 #include "llsphere.h"
00024
00025 LLSphere::LLSphere()
00026 : mCenter(0.f, 0.f, 0.f),
00027 mRadius(0.f)
00028 { }
00029
00030 LLSphere::LLSphere( const LLVector3& center, F32 radius)
00031 {
00032 set(center, radius);
00033 }
00034
00035 void LLSphere::set( const LLVector3& center, F32 radius )
00036 {
00037 mCenter = center;
00038 setRadius(radius);
00039 }
00040
00041 void LLSphere::setCenter( const LLVector3& center)
00042 {
00043 mCenter = center;
00044 }
00045
00046 void LLSphere::setRadius( F32 radius)
00047 {
00048 if (radius < 0.f)
00049 {
00050 radius = -radius;
00051 }
00052 mRadius = radius;
00053 }
00054
00055 const LLVector3& LLSphere::getCenter() const
00056 {
00057 return mCenter;
00058 }
00059
00060 F32 LLSphere::getRadius() const
00061 {
00062 return mRadius;
00063 }
00064
00065
00066 BOOL LLSphere::contains(const LLSphere& other_sphere) const
00067 {
00068 F32 separation = (mCenter - other_sphere.mCenter).length();
00069 return (mRadius >= separation + other_sphere.mRadius) ? TRUE : FALSE;
00070 }
00071
00072
00073 BOOL LLSphere::overlaps(const LLSphere& other_sphere) const
00074 {
00075 F32 separation = (mCenter - other_sphere.mCenter).length();
00076 return (separation <= mRadius + other_sphere.mRadius) ? TRUE : FALSE;
00077 }
00078
00079
00080
00081 F32 LLSphere::getOverlap(const LLSphere& other_sphere) const
00082 {
00083
00084 return (mCenter - other_sphere.mCenter).length() - mRadius - other_sphere.mRadius;
00085 }
00086
00087 bool LLSphere::operator==(const LLSphere& rhs) const
00088 {
00089
00090 return (mRadius == rhs.mRadius
00091 && mCenter == rhs.mCenter);
00092 }
00093
00094 std::ostream& operator<<( std::ostream& output_stream, const LLSphere& sphere)
00095 {
00096 output_stream << "{center=" << sphere.mCenter << "," << "radius=" << sphere.mRadius << "}";
00097 return output_stream;
00098 }
00099
00100
00101
00102 void LLSphere::collapse(std::vector<LLSphere>& sphere_list)
00103 {
00104 std::vector<LLSphere>::iterator first_itr = sphere_list.begin();
00105 while (first_itr != sphere_list.end())
00106 {
00107 bool delete_from_front = false;
00108
00109 std::vector<LLSphere>::iterator second_itr = first_itr;
00110 ++second_itr;
00111 while (second_itr != sphere_list.end())
00112 {
00113 if (second_itr->contains(*first_itr))
00114 {
00115 delete_from_front = true;
00116 break;
00117 }
00118 else if (first_itr->contains(*second_itr))
00119 {
00120 sphere_list.erase(second_itr++);
00121 }
00122 else
00123 {
00124 ++second_itr;
00125 }
00126 }
00127
00128 if (delete_from_front)
00129 {
00130 sphere_list.erase(first_itr++);
00131 }
00132 else
00133 {
00134 ++first_itr;
00135 }
00136 }
00137 }
00138
00139
00140
00141 LLSphere LLSphere::getBoundingSphere(const LLSphere& first_sphere, const LLSphere& second_sphere)
00142 {
00143 LLVector3 direction = second_sphere.mCenter - first_sphere.mCenter;
00144
00145
00146
00147
00148
00149
00150 F32 half_milimeter = 0.0005f;
00151
00152 F32 distance = direction.length();
00153 if (0.f == distance)
00154 {
00155 direction.setVec(1.f, 0.f, 0.f);
00156 }
00157 else
00158 {
00159 direction.normVec();
00160 }
00161
00162 F32 max_edge = 0.f;
00163 F32 min_edge = 0.f;
00164
00165 max_edge = llmax(max_edge + first_sphere.getRadius(), max_edge + distance + second_sphere.getRadius() + half_milimeter);
00166 min_edge = llmin(min_edge - first_sphere.getRadius(), min_edge + distance - second_sphere.getRadius() - half_milimeter);
00167 F32 radius = 0.5f * (max_edge - min_edge);
00168 LLVector3 center = first_sphere.mCenter + (0.5f * (max_edge + min_edge)) * direction;
00169 return LLSphere(center, radius);
00170 }
00171
00172
00173
00174 LLSphere LLSphere::getBoundingSphere(const std::vector<LLSphere>& sphere_list)
00175 {
00176
00177
00178
00179
00180
00181 LLSphere bounding_sphere( LLVector3(0.f, 0.f, 0.f), 0.f );
00182 S32 sphere_count = sphere_list.size();
00183 if (1 == sphere_count)
00184 {
00185
00186 std::vector<LLSphere>::const_iterator sphere_itr = sphere_list.begin();
00187 bounding_sphere = *sphere_itr;
00188 }
00189 else if (2 == sphere_count)
00190 {
00191
00192 std::vector<LLSphere>::const_iterator first_sphere = sphere_list.begin();
00193 std::vector<LLSphere>::const_iterator second_sphere = first_sphere;
00194 ++second_sphere;
00195 bounding_sphere = LLSphere::getBoundingSphere(*first_sphere, *second_sphere);
00196 }
00197 else if (sphere_count > 0)
00198 {
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213 std::vector<LLSphere>::const_iterator first_itr = sphere_list.begin();
00214 LLVector3 max_corner = first_itr->getCenter() + first_itr->getRadius() * LLVector3(1.f, 1.f, 1.f);
00215 LLVector3 min_corner = first_itr->getCenter() - first_itr->getRadius() * LLVector3(1.f, 1.f, 1.f);
00216 {
00217 std::vector<LLSphere>::const_iterator sphere_itr = sphere_list.begin();
00218 for (++sphere_itr; sphere_itr != sphere_list.end(); ++sphere_itr)
00219 {
00220 LLVector3 center = sphere_itr->getCenter();
00221 F32 radius = sphere_itr->getRadius();
00222 for (S32 i=0; i<3; ++i)
00223 {
00224 if (center.mV[i] + radius > max_corner.mV[i])
00225 {
00226 max_corner.mV[i] = center.mV[i] + radius;
00227 }
00228 if (center.mV[i] - radius < min_corner.mV[i])
00229 {
00230 min_corner.mV[i] = center.mV[i] - radius;
00231 }
00232 }
00233 }
00234 }
00235
00236
00237 LLVector3 diagonal = max_corner - min_corner;
00238 F32 bounding_radius = 0.5f * diagonal.length();
00239 LLVector3 bounding_center = 0.5f * (max_corner + min_corner);
00240
00241
00242 F32 minimum_radius = 0.5f * llmin(diagonal.mV[VX], llmin(diagonal.mV[VY], diagonal.mV[VZ]));
00243 F32 step_length = bounding_radius - minimum_radius;
00244 S32 step_count = 0;
00245 S32 max_step_count = 12;
00246 F32 half_milimeter = 0.0005f;
00247
00248
00249 S32 last_dx = 2;
00250 S32 last_dy = 2;
00251 S32 last_dz = 2;
00252
00253 while (step_length > half_milimeter
00254 && step_count < max_step_count)
00255 {
00256
00257
00258
00259
00260 S32 best_dx = 0;
00261 S32 best_dy = 0;
00262 S32 best_dz = 0;
00263
00264
00265 bool found_better_center = false;
00266 for (S32 dx = -1; dx < 2; ++dx)
00267 {
00268 for (S32 dy = -1; dy < 2; ++dy)
00269 {
00270 for (S32 dz = -1; dz < 2; ++dz)
00271 {
00272 if (dx == 0 && dy == 0 && dz == 0)
00273 {
00274 continue;
00275 }
00276
00277
00278 S32 match_count = 0;
00279 if (last_dx == dx) ++match_count;
00280 if (last_dy == dy) ++match_count;
00281 if (last_dz == dz) ++match_count;
00282 if (match_count == 2)
00283 {
00284
00285 continue;
00286 }
00287
00288 LLVector3 center = bounding_center;
00289 center.mV[VX] += (F32) dx * step_length;
00290 center.mV[VY] += (F32) dy * step_length;
00291 center.mV[VZ] += (F32) dz * step_length;
00292
00293
00294 F32 max_radius = 0.f;
00295 std::vector<LLSphere>::const_iterator sphere_itr;
00296 for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
00297 {
00298 F32 radius = (sphere_itr->getCenter() - center).length() + sphere_itr->getRadius();
00299 if (radius > max_radius)
00300 {
00301 max_radius = radius;
00302 }
00303 }
00304 if (max_radius < bounding_radius)
00305 {
00306 best_dx = dx;
00307 best_dy = dy;
00308 best_dz = dz;
00309 bounding_center = center;
00310 bounding_radius = max_radius;
00311 found_better_center = true;
00312 }
00313 }
00314 }
00315 }
00316 if (found_better_center)
00317 {
00318
00319 last_dx = -best_dx;
00320 last_dy = -best_dy;
00321 last_dz = -best_dz;
00322 }
00323 else
00324 {
00325
00326 step_length *= 0.5f;
00327
00328
00329 last_dx = 2;
00330 last_dy = 2;
00331 last_dz = 2;
00332 }
00333 }
00334
00335
00336
00337
00338 bounding_radius += half_milimeter;
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359 bounding_sphere.set(bounding_center, bounding_radius);
00360 }
00361 return bounding_sphere;
00362 }
00363
00364