summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRye <rye@alchemyviewer.org>2025-12-15 15:07:30 -0500
committerAndrey Kleshchev <117672381+akleshchev@users.noreply.github.com>2025-12-16 04:19:35 +0200
commit7bb5ea40b86d6d8baef0b24f9dabb21f6fdb3d2b (patch)
tree33c4b21ac816e20ecf191ada787ccba751fd8d3f
parent3450fa04d38c5886f6cdf2f890a14a05b6e013cc (diff)
Clean up dead LLSphere code and related tests
Signed-off-by: Rye <rye@alchemyviewer.org>
-rw-r--r--indra/llmath/CMakeLists.txt2
-rw-r--r--indra/llmath/llsphere.cpp370
-rw-r--r--indra/llmath/llsphere.h77
-rw-r--r--indra/llmath/tests/mathmisc_test.cpp161
-rw-r--r--indra/newview/llvoicevisualizer.cpp1
5 files changed, 0 insertions, 611 deletions
diff --git a/indra/llmath/CMakeLists.txt b/indra/llmath/CMakeLists.txt
index a4e4d0a50b..f97e4a5bb6 100644
--- a/indra/llmath/CMakeLists.txt
+++ b/indra/llmath/CMakeLists.txt
@@ -24,7 +24,6 @@ set(llmath_SOURCE_FILES
llquaternion.cpp
llrigginginfo.cpp
llrect.cpp
- llsphere.cpp
llvector4a.cpp
llvolume.cpp
llvolumemgr.cpp
@@ -72,7 +71,6 @@ set(llmath_HEADER_FILES
llsimdmath.h
llsimdtypes.h
llsimdtypes.inl
- llsphere.h
lltreenode.h
llvector4a.h
llvector4a.inl
diff --git a/indra/llmath/llsphere.cpp b/indra/llmath/llsphere.cpp
deleted file mode 100644
index 5f48764455..0000000000
--- a/indra/llmath/llsphere.cpp
+++ /dev/null
@@ -1,370 +0,0 @@
-/**
- * @file llsphere.cpp
- * @author Andrew Meadows
- * @brief Simple line class that can compute nearest approach between two lines
- *
- * $LicenseInfo:firstyear=2007&license=viewerlgpl$
- * Second Life Viewer Source Code
- * Copyright (C) 2010, Linden Research, Inc.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation;
- * version 2.1 of the License only.
- *
- * 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
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
- *
- * Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA
- * $/LicenseInfo$
- */
-
-#include "linden_common.h"
-
-#include "llsphere.h"
-
-LLSphere::LLSphere()
-: mCenter(0.f, 0.f, 0.f),
- mRadius(0.f)
-{ }
-
-LLSphere::LLSphere( const LLVector3& center, F32 radius)
-{
- set(center, radius);
-}
-
-void LLSphere::set( const LLVector3& center, F32 radius )
-{
- mCenter = center;
- setRadius(radius);
-}
-
-void LLSphere::setCenter( const LLVector3& center)
-{
- mCenter = center;
-}
-
-void LLSphere::setRadius( F32 radius)
-{
- if (radius < 0.f)
- {
- radius = -radius;
- }
- mRadius = radius;
-}
-
-const LLVector3& LLSphere::getCenter() const
-{
- return mCenter;
-}
-
-F32 LLSphere::getRadius() const
-{
- return mRadius;
-}
-
-// returns 'true' if this sphere completely contains other_sphere
-bool LLSphere::contains(const LLSphere& other_sphere) const
-{
- F32 separation = (mCenter - other_sphere.mCenter).length();
- return mRadius >= separation + other_sphere.mRadius;
-}
-
-// returns 'true' if this sphere completely contains other_sphere
-bool LLSphere::overlaps(const LLSphere& other_sphere) const
-{
- F32 separation = (mCenter - other_sphere.mCenter).length();
- return mRadius >= separation - other_sphere.mRadius;
-}
-
-// returns overlap
-// negative overlap is closest approach
-F32 LLSphere::getOverlap(const LLSphere& other_sphere) const
-{
- // separation is distance from other_sphere's edge and this center
- return (mCenter - other_sphere.mCenter).length() - mRadius - other_sphere.mRadius;
-}
-
-bool LLSphere::operator==(const LLSphere& rhs) const
-{
- return fabs(mRadius - rhs.mRadius) <= FLT_EPSILON &&
- (mCenter - rhs.mCenter).length() <= FLT_EPSILON;
-}
-
-std::ostream& operator<<( std::ostream& output_stream, const LLSphere& sphere)
-{
- output_stream << "{center=" << sphere.mCenter << "," << "radius=" << sphere.mRadius << "}";
- return output_stream;
-}
-
-// static
-// removes any spheres that are contained in others
-void LLSphere::collapse(std::vector<LLSphere>& sphere_list)
-{
- std::vector<LLSphere>::iterator first_itr = sphere_list.begin();
- while (first_itr != sphere_list.end())
- {
- bool delete_from_front = false;
-
- std::vector<LLSphere>::iterator second_itr = first_itr;
- ++second_itr;
- while (second_itr != sphere_list.end())
- {
- if (second_itr->contains(*first_itr))
- {
- delete_from_front = true;
- break;
- }
- else if (first_itr->contains(*second_itr))
- {
- sphere_list.erase(second_itr++);
- }
- else
- {
- ++second_itr;
- }
- }
-
- if (delete_from_front)
- {
- sphere_list.erase(first_itr++);
- }
- else
- {
- ++first_itr;
- }
- }
-}
-
-// static
-// returns the bounding sphere that contains both spheres
-LLSphere LLSphere::getBoundingSphere(const LLSphere& first_sphere, const LLSphere& second_sphere)
-{
- LLVector3 direction = second_sphere.mCenter - first_sphere.mCenter;
-
- // HACK -- it is possible to get enough floating point error in the
- // other getBoundingSphere() method that we have to add some slop
- // at the end. Unfortunately, this breaks the link-order invarience
- // for the linkability tests... unless we also apply the same slop
- // here.
- F32 half_milimeter = 0.0005f;
-
- F32 distance = direction.length();
- if (0.f == distance)
- {
- direction.setVec(1.f, 0.f, 0.f);
- }
- else
- {
- direction.normVec();
- }
- // the 'edge' is measured from the first_sphere's center
- F32 max_edge = 0.f;
- F32 min_edge = 0.f;
-
- max_edge = llmax(max_edge + first_sphere.getRadius(), max_edge + distance + second_sphere.getRadius() + half_milimeter);
- min_edge = llmin(min_edge - first_sphere.getRadius(), min_edge + distance - second_sphere.getRadius() - half_milimeter);
- F32 radius = 0.5f * (max_edge - min_edge);
- LLVector3 center = first_sphere.mCenter + (0.5f * (max_edge + min_edge)) * direction;
- return LLSphere(center, radius);
-}
-
-// static
-// returns the bounding sphere that contains an arbitrary set of spheres
-LLSphere LLSphere::getBoundingSphere(const std::vector<LLSphere>& sphere_list)
-{
- // this algorithm can get relatively inaccurate when the sphere
- // collection is 'small' (contained within a bounding sphere of about
- // 2 meters or less)
- // TODO -- improve the accuracy for small collections of spheres
-
- LLSphere bounding_sphere( LLVector3(0.f, 0.f, 0.f), 0.f );
- auto sphere_count = sphere_list.size();
- if (1 == sphere_count)
- {
- // trivial case -- single sphere
- std::vector<LLSphere>::const_iterator sphere_itr = sphere_list.begin();
- bounding_sphere = *sphere_itr;
- }
- else if (2 == sphere_count)
- {
- // trivial case -- two spheres
- std::vector<LLSphere>::const_iterator first_sphere = sphere_list.begin();
- std::vector<LLSphere>::const_iterator second_sphere = first_sphere;
- ++second_sphere;
- bounding_sphere = LLSphere::getBoundingSphere(*first_sphere, *second_sphere);
- }
- else if (sphere_count > 0)
- {
- // non-trivial case -- we will approximate the solution
- //
- // NOTE -- there is a fancy/fast way to do this for large
- // numbers of arbirary N-dimensional spheres -- you can look it
- // up on the net. We're dealing with 3D spheres at collection
- // sizes of 256 spheres or smaller, so we just use this
- // brute force method.
-
- // TODO -- perhaps would be worthwile to test for the solution where
- // the largest spanning radius just happens to work. That is, where
- // there are really two spheres that determine the bounding sphere,
- // and all others are contained therein.
-
- // compute the AABB
- std::vector<LLSphere>::const_iterator first_itr = sphere_list.begin();
- LLVector3 max_corner = first_itr->getCenter() + first_itr->getRadius() * LLVector3(1.f, 1.f, 1.f);
- LLVector3 min_corner = first_itr->getCenter() - first_itr->getRadius() * LLVector3(1.f, 1.f, 1.f);
- {
- std::vector<LLSphere>::const_iterator sphere_itr = sphere_list.begin();
- for (++sphere_itr; sphere_itr != sphere_list.end(); ++sphere_itr)
- {
- LLVector3 center = sphere_itr->getCenter();
- F32 radius = sphere_itr->getRadius();
- for (S32 i=0; i<3; ++i)
- {
- if (center.mV[i] + radius > max_corner.mV[i])
- {
- max_corner.mV[i] = center.mV[i] + radius;
- }
- if (center.mV[i] - radius < min_corner.mV[i])
- {
- min_corner.mV[i] = center.mV[i] - radius;
- }
- }
- }
- }
-
- // get the starting center and radius from the AABB
- LLVector3 diagonal = max_corner - min_corner;
- F32 bounding_radius = 0.5f * diagonal.length();
- LLVector3 bounding_center = 0.5f * (max_corner + min_corner);
-
- // compute the starting step-size
- F32 minimum_radius = 0.5f * llmin(diagonal.mV[VX], llmin(diagonal.mV[VY], diagonal.mV[VZ]));
- F32 step_length = bounding_radius - minimum_radius;
- //S32 step_count = 0;
- //S32 max_step_count = 12;
- F32 half_milimeter = 0.0005f;
-
- // wander the center around in search of tighter solutions
- S32 last_dx = 2; // 2 is out of bounds --> no match
- S32 last_dy = 2;
- S32 last_dz = 2;
-
- while (step_length > half_milimeter
- /*&& step_count < max_step_count*/)
- {
- // the algorithm for testing the maximum radius could be expensive enough
- // that it makes sense to NOT duplicate testing when possible, so we keep
- // track of where we last tested, and only test the new points
-
- S32 best_dx = 0;
- S32 best_dy = 0;
- S32 best_dz = 0;
-
- // sample near the center of the box
- bool found_better_center = false;
- for (S32 dx = -1; dx < 2; ++dx)
- {
- for (S32 dy = -1; dy < 2; ++dy)
- {
- for (S32 dz = -1; dz < 2; ++dz)
- {
- if (dx == 0 && dy == 0 && dz == 0)
- {
- continue;
- }
-
- // count the number of indecies that match the last_*'s
- S32 match_count = 0;
- if (last_dx == dx) ++match_count;
- if (last_dy == dy) ++match_count;
- if (last_dz == dz) ++match_count;
- if (match_count == 2)
- {
- // we've already tested this point
- continue;
- }
-
- LLVector3 center = bounding_center;
- center.mV[VX] += (F32) dx * step_length;
- center.mV[VY] += (F32) dy * step_length;
- center.mV[VZ] += (F32) dz * step_length;
-
- // compute the radius of the bounding sphere
- F32 max_radius = 0.f;
- std::vector<LLSphere>::const_iterator sphere_itr;
- for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
- {
- F32 radius = (sphere_itr->getCenter() - center).length() + sphere_itr->getRadius();
- if (radius > max_radius)
- {
- max_radius = radius;
- }
- }
- if (max_radius < bounding_radius)
- {
- best_dx = dx;
- best_dy = dy;
- best_dz = dz;
- bounding_center = center;
- bounding_radius = max_radius;
- found_better_center = true;
- }
- }
- }
- }
- if (found_better_center)
- {
- // remember where we came from so we can avoid retesting
- last_dx = -best_dx;
- last_dy = -best_dy;
- last_dz = -best_dz;
- }
- else
- {
- // reduce the step size
- step_length *= 0.5f;
- //++step_count;
- // reset the last_*'s
- last_dx = 2; // 2 is out of bounds --> no match
- last_dy = 2;
- last_dz = 2;
- }
- }
-
- // HACK -- it is possible to get enough floating point error for the
- // bounding sphere to too small on the order of 10e-6, but we only need
- // it to be accurate to within about half a millimeter
- bounding_radius += half_milimeter;
-
- // this algorithm can get relatively inaccurate when the sphere
- // collection is 'small' (contained within a bounding sphere of about
- // 2 meters or less)
- // TODO -- fix this
- /* debug code
- {
- std::vector<LLSphere>::const_iterator sphere_itr;
- for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
- {
- F32 radius = (sphere_itr->getCenter() - bounding_center).length() + sphere_itr->getRadius();
- if (radius + 0.1f > bounding_radius)
- {
- std::cout << " rad = " << radius << " bounding - rad = " << (bounding_radius - radius) << std::endl;
- }
- }
- std::cout << "\n" << std::endl;
- }
- */
-
- bounding_sphere.set(bounding_center, bounding_radius);
- }
- return bounding_sphere;
-}
-
-
diff --git a/indra/llmath/llsphere.h b/indra/llmath/llsphere.h
deleted file mode 100644
index cb923dcd3c..0000000000
--- a/indra/llmath/llsphere.h
+++ /dev/null
@@ -1,77 +0,0 @@
-// llsphere.h
-/**
- * @file llsphere.cpp
- * @author Andrew Meadows
- * @brief Simple sphere implementation for basic geometric operations
- *
- * $LicenseInfo:firstyear=2007&license=viewerlgpl$
- * Second Life Viewer Source Code
- * Copyright (C) 2010, Linden Research, Inc.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation;
- * version 2.1 of the License only.
- *
- * 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
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
- *
- * Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA
- * $/LicenseInfo$
- */
-
-#ifndef LL_SPHERE_H
-#define LL_SPHERE_H
-
-#include "stdtypes.h"
-#include "v3math.h"
-#include <iostream>
-#include <vector>
-
-class LLSphere
-{
-public:
- LLSphere();
- LLSphere( const LLVector3& center, F32 radius );
-
- void set( const LLVector3& center, F32 radius );
- void setCenter( const LLVector3& center );
- void setRadius( F32 radius );
-
- const LLVector3& getCenter() const;
- F32 getRadius() const;
-
- // returns true if this sphere completely contains other_sphere
- bool contains(const LLSphere& other_sphere) const;
-
- // returns true if this sphere overlaps other_sphere
- bool overlaps(const LLSphere& other_sphere) const;
-
- // returns overlap distance
- // negative overlap is closest approach
- F32 getOverlap(const LLSphere& other_sphere) const;
-
- // removes any spheres that are contained in others
- static void collapse(std::vector<LLSphere>& sphere_list);
-
- // returns minimum sphere bounding sphere for a set of spheres
- static LLSphere getBoundingSphere(const LLSphere& first_sphere, const LLSphere& second_sphere);
- static LLSphere getBoundingSphere(const std::vector<LLSphere>& sphere_list);
-
- bool operator==(const LLSphere& rhs) const;
-
- friend std::ostream& operator<<( std::ostream& output_stream, const LLSphere& line );
-
-protected:
- LLVector3 mCenter;
- F32 mRadius;
-};
-
-
-#endif
diff --git a/indra/llmath/tests/mathmisc_test.cpp b/indra/llmath/tests/mathmisc_test.cpp
index ff0899e975..810b0d80da 100644
--- a/indra/llmath/tests/mathmisc_test.cpp
+++ b/indra/llmath/tests/mathmisc_test.cpp
@@ -35,7 +35,6 @@
#include "../llline.h"
#include "../llmath.h"
-#include "../llsphere.h"
#include "../v3math.h"
namespace tut
@@ -280,166 +279,6 @@ namespace tut
namespace tut
{
- struct sphere_data
- {
- };
- typedef test_group<sphere_data> sphere_test;
- typedef sphere_test::object sphere_object;
- tut::sphere_test tsphere("LLSphere");
-
- template<> template<>
- void sphere_object::test<1>()
- {
- // test LLSphere::contains() and ::overlaps()
- S32 number_of_tests = 10;
- for (S32 test = 0; test < number_of_tests; ++test)
- {
- LLVector3 first_center(1.f, 1.f, 1.f);
- F32 first_radius = 3.f;
- LLSphere first_sphere( first_center, first_radius );
-
- F32 half_millimeter = 0.0005f;
- LLVector3 direction( ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
- direction.normalize();
-
- F32 distance = ll_frand(first_radius - 2.f * half_millimeter);
- LLVector3 second_center = first_center + distance * direction;
- F32 second_radius = first_radius - distance - half_millimeter;
- LLSphere second_sphere( second_center, second_radius );
- ensure("first sphere should contain the second", first_sphere.contains(second_sphere));
- ensure("first sphere should overlap the second", first_sphere.overlaps(second_sphere));
-
- distance = first_radius + ll_frand(first_radius);
- second_center = first_center + distance * direction;
- second_radius = distance - first_radius + half_millimeter;
- second_sphere.set( second_center, second_radius );
- ensure("first sphere should NOT contain the second", !first_sphere.contains(second_sphere));
- ensure("first sphere should overlap the second", first_sphere.overlaps(second_sphere));
-
- distance = first_radius + ll_frand(first_radius) + half_millimeter;
- second_center = first_center + distance * direction;
- second_radius = distance - first_radius - half_millimeter;
- second_sphere.set( second_center, second_radius );
- ensure("first sphere should NOT contain the second", !first_sphere.contains(second_sphere));
- ensure("first sphere should NOT overlap the second", !first_sphere.overlaps(second_sphere));
- }
- }
-
- template<> template<>
- void sphere_object::test<2>()
- {
- skip("See SNOW-620. Neither the test nor the code being tested seem good. Also sim-only.");
-
- // test LLSphere::getBoundingSphere()
- S32 number_of_tests = 100;
- S32 number_of_spheres = 10;
- F32 sphere_center_range = 32.f;
- F32 sphere_radius_range = 5.f;
-
- for (S32 test = 0; test < number_of_tests; ++test)
- {
- // gegnerate a bunch of random sphere
- std::vector< LLSphere > sphere_list;
- for (S32 sphere_count=0; sphere_count < number_of_spheres; ++sphere_count)
- {
- LLVector3 direction( ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f, ll_frand(2.f) - 1.f);
- direction.normalize();
- F32 distance = ll_frand(sphere_center_range);
- LLVector3 center = distance * direction;
- F32 radius = ll_frand(sphere_radius_range);
- LLSphere sphere( center, radius );
- sphere_list.push_back(sphere);
- }
-
- // compute the bounding sphere
- LLSphere bounding_sphere = LLSphere::getBoundingSphere(sphere_list);
-
- // make sure all spheres are inside the bounding sphere
- {
- std::vector< LLSphere >::const_iterator sphere_itr;
- for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
- {
- ensure("sphere should be contained by the bounding sphere", bounding_sphere.contains(*sphere_itr));
- }
- }
-
- // TODO -- improve LLSphere::getBoundingSphere() to the point where
- // we can reduce the 'expansion' in the two tests below to about
- // 2 mm or less
-
- F32 expansion = 0.005f;
- // move all spheres out a little bit
- // and count how many are NOT contained
- {
- std::vector< LLVector3 > uncontained_directions;
- std::vector< LLSphere >::iterator sphere_itr;
- for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
- {
- LLVector3 direction = sphere_itr->getCenter() - bounding_sphere.getCenter();
- direction.normalize();
-
- sphere_itr->setCenter( sphere_itr->getCenter() + expansion * direction );
- if (! bounding_sphere.contains( *sphere_itr ) )
- {
- uncontained_directions.push_back(direction);
- }
- }
- ensure("when moving spheres out there should be at least two uncontained spheres",
- uncontained_directions.size() > 1);
-
- /* TODO -- when the bounding sphere algorithm is improved we can open up this test
- * at the moment it occasionally fails when the sphere collection is tight and small
- * (2 meters or less)
- if (2 == uncontained_directions.size() )
- {
- // if there were only two uncontained spheres then
- // the two directions should be nearly opposite
- F32 dir_dot = uncontained_directions[0] * uncontained_directions[1];
- ensure("two uncontained spheres should lie opposite the bounding center", dir_dot < -0.95f);
- }
- */
- }
-
- // compute the new bounding sphere
- bounding_sphere = LLSphere::getBoundingSphere(sphere_list);
-
- // increase the size of all spheres a little bit
- // and count how many are NOT contained
- {
- std::vector< LLVector3 > uncontained_directions;
- std::vector< LLSphere >::iterator sphere_itr;
- for (sphere_itr = sphere_list.begin(); sphere_itr != sphere_list.end(); ++sphere_itr)
- {
- LLVector3 direction = sphere_itr->getCenter() - bounding_sphere.getCenter();
- direction.normalize();
-
- sphere_itr->setRadius( sphere_itr->getRadius() + expansion );
- if (! bounding_sphere.contains( *sphere_itr ) )
- {
- uncontained_directions.push_back(direction);
- }
- }
- ensure("when boosting sphere radii there should be at least two uncontained spheres",
- uncontained_directions.size() > 1);
-
- /* TODO -- when the bounding sphere algorithm is improved we can open up this test
- * at the moment it occasionally fails when the sphere collection is tight and small
- * (2 meters or less)
- if (2 == uncontained_directions.size() )
- {
- // if there were only two uncontained spheres then
- // the two directions should be nearly opposite
- F32 dir_dot = uncontained_directions[0] * uncontained_directions[1];
- ensure("two uncontained spheres should lie opposite the bounding center", dir_dot < -0.95f);
- }
- */
- }
- }
- }
-}
-
-namespace tut
-{
F32 SMALL_RADIUS = 1.0f;
F32 MEDIUM_RADIUS = 5.0f;
F32 LARGE_RADIUS = 10.0f;
diff --git a/indra/newview/llvoicevisualizer.cpp b/indra/newview/llvoicevisualizer.cpp
index c5704982b8..e6dac0530d 100644
--- a/indra/newview/llvoicevisualizer.cpp
+++ b/indra/newview/llvoicevisualizer.cpp
@@ -32,7 +32,6 @@
#include "llviewerprecompiledheaders.h"
#include "llviewercontrol.h"
#include "llglheaders.h"
-#include "llsphere.h"
#include "llvoicevisualizer.h"
#include "llviewercamera.h"
#include "llviewerobject.h"