summaryrefslogtreecommitdiff
path: root/indra/llmath
diff options
context:
space:
mode:
Diffstat (limited to 'indra/llmath')
-rw-r--r--[-rwxr-xr-x]indra/llmath/CMakeLists.txt0
-rw-r--r--[-rwxr-xr-x]indra/llmath/llcamera.h0
-rw-r--r--[-rwxr-xr-x]indra/llmath/llmatrix3a.cpp0
-rw-r--r--[-rwxr-xr-x]indra/llmath/llmatrix4a.h0
-rw-r--r--indra/llmath/lloctree.h143
-rw-r--r--[-rwxr-xr-x]indra/llmath/llplane.h0
-rw-r--r--[-rwxr-xr-x]indra/llmath/llsimdmath.h0
-rw-r--r--[-rwxr-xr-x]indra/llmath/llvector4a.cpp0
-rw-r--r--[-rwxr-xr-x]indra/llmath/llvector4a.h0
-rw-r--r--[-rwxr-xr-x]indra/llmath/llvolume.cpp8
-rw-r--r--indra/llmath/llvolumeoctree.cpp6
-rw-r--r--[-rwxr-xr-x]indra/llmath/llvolumeoctree.h9
-rw-r--r--[-rwxr-xr-x]indra/llmath/tests/alignment_test.cpp0
13 files changed, 121 insertions, 45 deletions
diff --git a/indra/llmath/CMakeLists.txt b/indra/llmath/CMakeLists.txt
index 5865ae030c..5865ae030c 100755..100644
--- a/indra/llmath/CMakeLists.txt
+++ b/indra/llmath/CMakeLists.txt
diff --git a/indra/llmath/llcamera.h b/indra/llmath/llcamera.h
index 0b591be622..0b591be622 100755..100644
--- a/indra/llmath/llcamera.h
+++ b/indra/llmath/llcamera.h
diff --git a/indra/llmath/llmatrix3a.cpp b/indra/llmath/llmatrix3a.cpp
index ab077abcb0..ab077abcb0 100755..100644
--- a/indra/llmath/llmatrix3a.cpp
+++ b/indra/llmath/llmatrix3a.cpp
diff --git a/indra/llmath/llmatrix4a.h b/indra/llmath/llmatrix4a.h
index c4cefdb4fa..c4cefdb4fa 100755..100644
--- a/indra/llmath/llmatrix4a.h
+++ b/indra/llmath/llmatrix4a.h
diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h
index 6c7744cdf1..c3f6f7de2a 100644
--- a/indra/llmath/lloctree.h
+++ b/indra/llmath/lloctree.h
@@ -31,7 +31,6 @@
#include "v3math.h"
#include "llvector4a.h"
#include <vector>
-#include <set>
#define OCT_ERRS LL_WARNS("OctreeErrors")
@@ -79,11 +78,13 @@ public:
typedef LLOctreeTraveler<T> oct_traveler;
typedef LLTreeTraveler<T> tree_traveler;
- typedef typename std::set<LLPointer<T> > element_list;
- typedef typename element_list::iterator element_iter;
- typedef typename element_list::const_iterator const_element_iter;
+ typedef LLPointer<T>* element_list;
+ typedef LLPointer<T>* element_iter;
+ typedef const LLPointer<T>* const_element_iter;
typedef typename std::vector<LLTreeListener<T>*>::iterator tree_listener_iter;
- typedef typename std::vector<LLOctreeNode<T>* > child_list;
+ typedef LLOctreeNode<T>** child_list;
+ typedef LLOctreeNode<T>** child_iter;
+
typedef LLTreeNode<T> BaseType;
typedef LLOctreeNode<T> oct_node;
typedef LLOctreeListener<T> oct_listener;
@@ -105,6 +106,9 @@ public:
: mParent((oct_node*)parent),
mOctant(octant)
{
+ mData = NULL;
+ mDataEnd = NULL;
+
mCenter = center;
mSize = size;
@@ -123,6 +127,16 @@ public:
{
BaseType::destroyListeners();
+ for (U32 i = 0; i < mElementCount; ++i)
+ {
+ mData[i]->setBinIndex(-1);
+ mData[i] = NULL;
+ }
+
+ free(mData);
+ mData = NULL;
+ mDataEnd = NULL;
+
for (U32 i = 0; i < getChildCount(); i++)
{
delete getChild(i);
@@ -219,12 +233,17 @@ public:
}
void accept(oct_traveler* visitor) { visitor->visit(this); }
- virtual bool isLeaf() const { return mChild.empty(); }
+ virtual bool isLeaf() const { return mChildCount == 0; }
U32 getElementCount() const { return mElementCount; }
+ bool isEmpty() const { return mElementCount == 0; }
element_list& getData() { return mData; }
const element_list& getData() const { return mData; }
-
+ element_iter getDataBegin() { return mData; }
+ element_iter getDataEnd() { return mDataEnd; }
+ const_element_iter getDataBegin() const { return mData; }
+ const_element_iter getDataEnd() const { return mDataEnd; }
+
U32 getChildCount() const { return mChildCount; }
oct_node* getChild(U32 index) { return mChild[index]; }
const oct_node* getChild(U32 index) const { return mChild[index]; }
@@ -289,7 +308,7 @@ public:
virtual bool insert(T* data)
{
- if (data == NULL)
+ if (data == NULL || data->getBinIndex() != -1)
{
OCT_ERRS << "!!! INVALID ELEMENT ADDED TO OCTREE BRANCH !!!" << llendl;
return false;
@@ -302,13 +321,16 @@ public:
if ((getElementCount() < gOctreeMaxCapacity && contains(data->getBinRadius()) ||
(data->getBinRadius() > getSize()[0] && parent && parent->getElementCount() >= gOctreeMaxCapacity)))
{ //it belongs here
- //if this is a redundant insertion, error out (should never happen)
- llassert(mData.find(data) == mData.end());
+ mElementCount++;
+ mData = (element_list) realloc(mData, sizeof(LLPointer<T>)*mElementCount);
- mData.insert(data);
- BaseType::insert(data);
+ //avoid unref on uninitialized memory
+ memset(mData+mElementCount-1, 0, sizeof(LLPointer<T>));
- mElementCount = mData.size();
+ mData[mElementCount-1] = data;
+ mDataEnd = mData + mElementCount;
+ data->setBinIndex(mElementCount-1);
+ BaseType::insert(data);
return true;
}
else
@@ -342,10 +364,16 @@ public:
if( lt == 0x7 )
{
- mData.insert(data);
- BaseType::insert(data);
+ mElementCount++;
+ mData = (element_list) realloc(mData, sizeof(LLPointer<T>)*mElementCount);
+
+ //avoid unref on uninitialized memory
+ memset(mData+mElementCount-1, 0, sizeof(LLPointer<T>));
- mElementCount = mData.size();
+ mData[mElementCount-1] = data;
+ mDataEnd = mData + mElementCount;
+ data->setBinIndex(mElementCount-1);
+ BaseType::insert(data);
return true;
}
@@ -394,23 +422,59 @@ public:
return false;
}
+ void _remove(T* data, S32 i)
+ { //precondition -- mElementCount > 0, idx is in range [0, mElementCount)
+
+ mElementCount--;
+ data->setBinIndex(-1);
+
+ if (mElementCount > 0)
+ {
+ if (mElementCount != i)
+ {
+ mData[i] = mData[mElementCount]; //might unref data, do not access data after this point
+ mData[i]->setBinIndex(i);
+ }
+
+ mData[mElementCount] = NULL; //needed for unref
+ mData = (element_list) realloc(mData, sizeof(LLPointer<T>)*mElementCount);
+ mDataEnd = mData+mElementCount;
+ }
+ else
+ {
+ mData[0] = NULL; //needed for unref
+ free(mData);
+ mData = NULL;
+ mDataEnd = NULL;
+ }
+
+ notifyRemoval(data);
+ checkAlive();
+ }
+
bool remove(T* data)
{
- if (mData.find(data) != mData.end())
- { //we have data
- mData.erase(data);
- mElementCount = mData.size();
- notifyRemoval(data);
- checkAlive();
- return true;
- }
- else if (isInside(data))
+ S32 i = data->getBinIndex();
+
+ if (i >= 0 && i < mElementCount)
+ {
+ if (mData[i] == data)
+ { //found it
+ _remove(data, i);
+ llassert(data->getBinIndex() == -1);
+ return true;
+ }
+ }
+
+ if (isInside(data))
{
oct_node* dest = getNodeAt(data);
if (dest != this)
{
- return dest->remove(data);
+ bool ret = dest->remove(data);
+ llassert(data->getBinIndex() == -1);
+ return ret;
}
}
@@ -429,19 +493,20 @@ public:
//node is now root
llwarns << "!!! OCTREE REMOVING FACE BY ADDRESS, SEVERE PERFORMANCE PENALTY |||" << llendl;
node->removeByAddress(data);
+ llassert(data->getBinIndex() == -1);
return true;
}
void removeByAddress(T* data)
{
- if (mData.find(data) != mData.end())
+ for (U32 i = 0; i < mElementCount; ++i)
{
- mData.erase(data);
- mElementCount = mData.size();
- notifyRemoval(data);
- llwarns << "FOUND!" << llendl;
- checkAlive();
- return;
+ if (mData[i] == data)
+ { //we have data
+ _remove(data, i);
+ llwarns << "FOUND!" << llendl;
+ return;
+ }
}
for (U32 i = 0; i < getChildCount(); i++)
@@ -453,8 +518,8 @@ public:
void clearChildren()
{
- mChild.clear();
mChildCount = 0;
+
U32* foo = (U32*) mChildMap;
foo[0] = foo[1] = 0xFFFFFFFF;
}
@@ -516,7 +581,7 @@ public:
mChildMap[child->getOctant()] = mChildCount;
- mChild.push_back(child);
+ mChild[mChildCount] = child;
++mChildCount;
child->setParent(this);
@@ -543,9 +608,12 @@ public:
mChild[index]->destroy();
delete mChild[index];
}
- mChild.erase(mChild.begin() + index);
+
--mChildCount;
+ mChild[index] = mChild[mChildCount];
+
+
//rebuild child map
U32* foo = (U32*) mChildMap;
foo[0] = foo[1] = 0xFFFFFFFF;
@@ -601,11 +669,12 @@ protected:
oct_node* mParent;
U8 mOctant;
- child_list mChild;
+ LLOctreeNode<T>* mChild[8];
U8 mChildMap[8];
U32 mChildCount;
element_list mData;
+ element_iter mDataEnd;
U32 mElementCount;
};
diff --git a/indra/llmath/llplane.h b/indra/llmath/llplane.h
index 3c32441b11..3c32441b11 100755..100644
--- a/indra/llmath/llplane.h
+++ b/indra/llmath/llplane.h
diff --git a/indra/llmath/llsimdmath.h b/indra/llmath/llsimdmath.h
index 01458521ec..01458521ec 100755..100644
--- a/indra/llmath/llsimdmath.h
+++ b/indra/llmath/llsimdmath.h
diff --git a/indra/llmath/llvector4a.cpp b/indra/llmath/llvector4a.cpp
index 6edeb0fefe..6edeb0fefe 100755..100644
--- a/indra/llmath/llvector4a.cpp
+++ b/indra/llmath/llvector4a.cpp
diff --git a/indra/llmath/llvector4a.h b/indra/llmath/llvector4a.h
index 0526793d3a..0526793d3a 100755..100644
--- a/indra/llmath/llvector4a.h
+++ b/indra/llmath/llvector4a.h
diff --git a/indra/llmath/llvolume.cpp b/indra/llmath/llvolume.cpp
index 11fa7080ce..53d56e96da 100755..100644
--- a/indra/llmath/llvolume.cpp
+++ b/indra/llmath/llvolume.cpp
@@ -317,16 +317,16 @@ public:
LLVector4a& min = node->mExtents[0];
LLVector4a& max = node->mExtents[1];
- if (!branch->getData().empty())
+ if (!branch->isEmpty())
{ //node has data, find AABB that binds data set
- const LLVolumeTriangle* tri = *(branch->getData().begin());
+ const LLVolumeTriangle* tri = *(branch->getDataBegin());
//initialize min/max to first available vertex
min = *(tri->mV[0]);
max = *(tri->mV[0]);
for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter =
- branch->getData().begin(); iter != branch->getData().end(); ++iter)
+ branch->getDataBegin(); iter != branch->getDataEnd(); ++iter)
{ //for each triangle in node
//stretch by triangles in node
@@ -341,7 +341,7 @@ public:
max.setMax(max, *tri->mV[2]);
}
}
- else if (!branch->getChildren().empty())
+ else if (!branch->isLeaf())
{ //no data, but child nodes exist
LLVolumeOctreeListener* child = (LLVolumeOctreeListener*) branch->getChild(0)->getListener(0);
diff --git a/indra/llmath/llvolumeoctree.cpp b/indra/llmath/llvolumeoctree.cpp
index b5a935c2b5..cc83cb7235 100644
--- a/indra/llmath/llvolumeoctree.cpp
+++ b/indra/llmath/llvolumeoctree.cpp
@@ -131,7 +131,7 @@ void LLOctreeTriangleRayIntersect::traverse(const LLOctreeNode<LLVolumeTriangle>
void LLOctreeTriangleRayIntersect::visit(const LLOctreeNode<LLVolumeTriangle>* node)
{
for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter =
- node->getData().begin(); iter != node->getData().end(); ++iter)
+ node->getDataBegin(); iter != node->getDataEnd(); ++iter)
{
const LLVolumeTriangle* tri = *iter;
@@ -236,8 +236,8 @@ void LLVolumeOctreeValidate::visit(const LLOctreeNode<LLVolumeTriangle>* branch)
}
//children fit, check data
- for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = branch->getData().begin();
- iter != branch->getData().end(); ++iter)
+ for (LLOctreeNode<LLVolumeTriangle>::const_element_iter iter = branch->getDataBegin();
+ iter != branch->getDataEnd(); ++iter)
{
const LLVolumeTriangle* tri = *iter;
diff --git a/indra/llmath/llvolumeoctree.h b/indra/llmath/llvolumeoctree.h
index dac97b14b5..9ae34a0c4e 100755..100644
--- a/indra/llmath/llvolumeoctree.h
+++ b/indra/llmath/llvolumeoctree.h
@@ -49,7 +49,7 @@ public:
LLVolumeTriangle()
{
-
+ mBinIndex = -1;
}
LLVolumeTriangle(const LLVolumeTriangle& rhs)
@@ -74,9 +74,16 @@ public:
U16 mIndex[3];
F32 mRadius;
+ mutable S32 mBinIndex;
+
virtual const LLVector4a& getPositionGroup() const;
virtual const F32& getBinRadius() const;
+
+ S32 getBinIndex() const { return mBinIndex; }
+ void setBinIndex(S32 idx) const { mBinIndex = idx; }
+
+
};
class LLVolumeOctreeListener : public LLOctreeListener<LLVolumeTriangle>
diff --git a/indra/llmath/tests/alignment_test.cpp b/indra/llmath/tests/alignment_test.cpp
index ac0c45ae6f..ac0c45ae6f 100755..100644
--- a/indra/llmath/tests/alignment_test.cpp
+++ b/indra/llmath/tests/alignment_test.cpp
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 05:28:05 +0000