summaryrefslogtreecommitdiff
path: root/indra/llmath/lloctree.h
diff options
context:
space:
mode:
Diffstat (limited to 'indra/llmath/lloctree.h')
-rw-r--r--indra/llmath/lloctree.h165
1 files changed, 102 insertions, 63 deletions
diff --git a/indra/llmath/lloctree.h b/indra/llmath/lloctree.h
index 432e9fbcd8..ed97ff76ba 100644
--- a/indra/llmath/lloctree.h
+++ b/indra/llmath/lloctree.h
@@ -2,31 +2,25 @@
* @file lloctree.h
* @brief Octree declaration.
*
- * $LicenseInfo:firstyear=2005&license=viewergpl$
- *
- * Copyright (c) 2005-2009, Linden Research, Inc.
- *
+ * $LicenseInfo:firstyear=2005&license=viewerlgpl$
* Second Life Viewer Source Code
- * The source code in this file ("Source Code") is provided by Linden Lab
- * to you under the terms of the GNU General Public License, version 2.0
- * ("GPL"), unless you have obtained a separate licensing agreement
- * ("Other License"), formally executed by you and Linden Lab. Terms of
- * the GPL can be found in doc/GPL-license.txt in this distribution, or
- * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
+ * 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.
*
- * There are special exceptions to the terms and conditions of the GPL as
- * it is applied to this Source Code. View the full text of the exception
- * in the file doc/FLOSS-exception.txt in this software distribution, or
- * online at
- * http://secondlifegrid.net/programs/open_source/licensing/flossexception
+ * 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.
*
- * By copying, modifying or distributing this software, you acknowledge
- * that you have read and understood your obligations described above,
- * and agree to abide by those obligations.
+ * 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
*
- * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
- * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
- * COMPLETENESS OR PERFORMANCE.
+ * Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA
* $/LicenseInfo$
*/
@@ -95,22 +89,30 @@ public:
typedef LLOctreeNode<T> oct_node;
typedef LLOctreeListener<T> oct_listener;
+ /*void* operator new(size_t size)
+ {
+ return ll_aligned_malloc_16(size);
+ }
+
+ void operator delete(void* ptr)
+ {
+ ll_aligned_free_16(ptr);
+ }*/
+
LLOctreeNode( const LLVector4a& center,
const LLVector4a& size,
BaseType* parent,
- S32 octant = -1)
+ U8 octant = 255)
: mParent((oct_node*)parent),
mOctant(octant)
{
- mD = (LLVector4a*) ll_aligned_malloc_16(sizeof(LLVector4a)*4);
-
- mD[CENTER] = center;
- mD[SIZE] = size;
+ mCenter = center;
+ mSize = size;
updateMinMax();
- if ((mOctant == -1) && mParent)
+ if ((mOctant == 255) && mParent)
{
- mOctant = ((oct_node*) mParent)->getOctant(mD[CENTER]);
+ mOctant = ((oct_node*) mParent)->getOctant(mCenter);
}
clearChildren();
@@ -124,30 +126,27 @@ public:
{
delete getChild(i);
}
-
- ll_aligned_free_16(mD);
}
inline const BaseType* getParent() const { return mParent; }
inline void setParent(BaseType* parent) { mParent = (oct_node*) parent; }
- inline const LLVector4a& getCenter() const { return mD[CENTER]; }
- inline const LLVector4a& getSize() const { return mD[SIZE]; }
- inline void setCenter(const LLVector4a& center) { mD[CENTER] = center; }
- inline void setSize(const LLVector4a& size) { mD[SIZE] = size; }
+ inline const LLVector4a& getCenter() const { return mCenter; }
+ inline const LLVector4a& getSize() const { return mSize; }
+ inline void setCenter(const LLVector4a& center) { mCenter = center; }
+ inline void setSize(const LLVector4a& size) { mSize = size; }
inline oct_node* getNodeAt(T* data) { return getNodeAt(data->getPositionGroup(), data->getBinRadius()); }
- inline S32 getOctant() const { return mOctant; }
- inline void setOctant(S32 octant) { mOctant = octant; }
+ inline U8 getOctant() const { return mOctant; }
inline const oct_node* getOctParent() const { return (const oct_node*) getParent(); }
inline oct_node* getOctParent() { return (oct_node*) getParent(); }
- S32 getOctant(const LLVector4a& pos) const //get the octant pos is in
+ U8 getOctant(const LLVector4a& pos) const //get the octant pos is in
{
- return pos.greaterThan(mD[CENTER]).getGatheredBits() & 0x7;
+ return (U8) (pos.greaterThan(mCenter).getGatheredBits() & 0x7);
}
inline bool isInside(const LLVector4a& pos, const F32& rad) const
{
- return rad <= mD[SIZE][0]*2.f && isInside(pos);
+ return rad <= mSize[0]*2.f && isInside(pos);
}
inline bool isInside(T* data) const
@@ -157,13 +156,13 @@ public:
bool isInside(const LLVector4a& pos) const
{
- S32 gt = pos.greaterThan(mD[MAX]).getGatheredBits() & 0x7;
+ S32 gt = pos.greaterThan(mMax).getGatheredBits() & 0x7;
if (gt)
{
return false;
}
- S32 lt = pos.lessEqual(mD[MIN]).getGatheredBits() & 0x7;
+ S32 lt = pos.lessEqual(mMin).getGatheredBits() & 0x7;
if (lt)
{
return false;
@@ -174,8 +173,8 @@ public:
void updateMinMax()
{
- mD[MAX].setAdd(mD[CENTER], mD[SIZE]);
- mD[MIN].setSub(mD[CENTER], mD[SIZE]);
+ mMax.setAdd(mCenter, mSize);
+ mMin.setSub(mCenter, mSize);
}
inline oct_listener* getOctListener(U32 index)
@@ -195,7 +194,7 @@ public:
return false;
}
- F32 size = mD[SIZE][0];
+ F32 size = mSize[0];
F32 p_size = size * 2.f;
return (radius <= 0.001f && size <= 0.001f) ||
@@ -206,7 +205,7 @@ public:
{
const LLVector4a& pos = data->getPositionGroup();
- LLVector4a gt = pos.greaterThan(center);
+ LLVector4Logical gt = pos.greaterThan(center);
LLVector4a up;
up = _mm_and_ps(size, gt);
@@ -234,6 +233,29 @@ public:
void accept(tree_traveler* visitor) const { visitor->visit(this); }
void accept(oct_traveler* visitor) const { visitor->visit(this); }
+ void validateChildMap()
+ {
+ for (U32 i = 0; i < 8; i++)
+ {
+ U8 idx = mChildMap[i];
+ if (idx != 255)
+ {
+ LLOctreeNode<T>* child = mChild[idx];
+
+ if (child->getOctant() != i)
+ {
+ llerrs << "Invalid child map, bad octant data." << llendl;
+ }
+
+ if (getOctant(child->getCenter()) != child->getOctant())
+ {
+ llerrs << "Invalid child octant compared to position data." << llendl;
+ }
+ }
+ }
+ }
+
+
oct_node* getNodeAt(const LLVector4a& pos, const F32& rad)
{
LLOctreeNode<T>* node = this;
@@ -241,25 +263,19 @@ public:
if (node->isInside(pos, rad))
{
//do a quick search by octant
- S32 octant = node->getOctant(pos);
- BOOL keep_going = TRUE;
-
+ U8 octant = node->getOctant(pos);
+
//traverse the tree until we find a node that has no node
//at the appropriate octant or is smaller than the object.
//by definition, that node is the smallest node that contains
// the data
- while (keep_going && node->getSize()[0] >= rad)
+ U8 next_node = node->mChildMap[octant];
+
+ while (next_node != 255 && node->getSize()[0] >= rad)
{
- keep_going = FALSE;
- for (U32 i = 0; i < node->getChildCount() && !keep_going; i++)
- {
- if (node->getChild(i)->getOctant() == octant)
- {
- node = node->getChild(i);
- octant = node->getOctant(pos);
- keep_going = TRUE;
- }
- }
+ node = node->getChild(next_node);
+ octant = node->getOctant(pos);
+ next_node = node->mChildMap[octant];
}
}
else if (!node->contains(rad) && node->getParent())
@@ -439,6 +455,9 @@ public:
void clearChildren()
{
mChild.clear();
+
+ U32* foo = (U32*) mChildMap;
+ foo[0] = foo[1] = 0xFFFFFFFF;
}
void validate()
@@ -496,6 +515,8 @@ public:
}
#endif
+ mChildMap[child->getOctant()] = (U8) mChild.size();
+
mChild.push_back(child);
child->setParent(this);
@@ -517,6 +538,8 @@ public:
listener->handleChildRemoval(this, getChild(index));
}
+
+
if (destroy)
{
mChild[index]->destroy();
@@ -524,6 +547,15 @@ public:
}
mChild.erase(mChild.begin() + index);
+ //rebuild child map
+ U32* foo = (U32*) mChildMap;
+ foo[0] = foo[1] = 0xFFFFFFFF;
+
+ for (U32 i = 0; i < mChild.size(); ++i)
+ {
+ mChildMap[mChild[i]->getOctant()] = i;
+ }
+
checkAlive();
}
@@ -562,15 +594,20 @@ protected:
MIN = 3
} eDName;
- LLVector4a* mD;
+ LLVector4a mCenter;
+ LLVector4a mSize;
+ LLVector4a mMax;
+ LLVector4a mMin;
oct_node* mParent;
- S32 mOctant;
+ U8 mOctant;
child_list mChild;
+ U8 mChildMap[8];
+
element_list mData;
-};
+};
//just like a regular node, except it might expand on insert and compress on balance
template <class T>
@@ -613,6 +650,8 @@ public:
//destroy child
child->clearChildren();
delete child;
+
+ return false;
}
return true;
@@ -639,7 +678,7 @@ public:
const LLVector4a& v = data->getPositionGroup();
LLVector4a val;
- val.setSub(v, BaseType::mD[BaseType::CENTER]);
+ val.setSub(v, BaseType::mCenter);
val.setAbs(val);
S32 lt = val.lessThan(MAX_MAG).getGatheredBits() & 0x7;
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-22 11:34:20 +0000