Quote:I've thought of another question: How do you initially setup the tree? Do you create it as if you were creating a tree for static objects ie. perform a one step creation (slow) once all of your world objects are known?
These are the only methods that manage the tree:
Handle insert(const T& t, const Vec3& aabbMin, const Vec3& aabbMax); // Inserts a new object of type T into the aabb tree, return a handle to the object.void update(const Handle& it, const Vec3& aabbMin, const Vec3& aabbMax); // Updates an existing object.void erase(const Handle& it); // Removes an object.The handle works like an interator, except that you can't increase or decrease it (that's why I'm not calling it an iterator :).
When I load an instance of an "item", I simply call the insert method with the items aabb.
So, yes upon a "level" load, all loaded instances are inserted into the tree (just another cost of the load level phase).
It's not terrible slow (FrustumTest_10000.exe takes less then an second to start on my computer, including font loading, dx setup, 10000 tree insertions etc).
One thing to note is that the aabb tree is NOT "loose" for static aabb's.
This is important since you don't want to get too many false "hits" when do queries on the tree.
Try the SimpleFrustumTest_16.exe, and hit 'T' berfore animation is started and you'll see that the parent aabb's fit their children exactly.
It's not until one aabb moves that I increase it's parent size (if necesary).
These are some query methods:
template <class O> void testPolyhedra(const Vec4 planes[], const uint planeCount, O& overlapper); // For every aabb that's behind or intersection all planes, the overlapper functor is called.template <class O> void testAabb(const Vec3& aabbMin, const Vec3& aabbMax, O& overlapper); // For every aabb that's visible within the aabb, the overlapper functor is called.template <class O> void testLine(const Vec3& lineStart, const Vec3& lineEnd, O& overlapper); // For every aabb that's intesect the line, the overlapper functor is called.// A typical "overlapper"struct AddItemToRenderQueue{ AddItemToRenderQueue(Engine* const engine) : m_engine(engine) { } inline bool operator()(EngineTree::Handle it, const Vec3& aabbMin, const Vec3& aabbMax) { return m_engine->addItemToRenderQueue(engine); } Engine* m_engine;};// Typical usageEngine::render(void){ m_aabbTree.testPolyhedra(m_frustumPlanes, 5, AddItemToRenderQueue(this));}I've got other more specialized methods as well, that performs the same tests as above but sorts the objects in respect to a point.
I.e, for every node in the tree that's being traversed, list all childrens that's not rejected by the test, sort this list with respect to the point, traverse children in that order.
So my frustum test traverses the tree and gives me a list of all visible objects in roughly front to back order.
The extra sort costs nearly nothing and ray-cast are quite fast.
(I'd always liked to do a "ray tracer" that traces just the aabb's to see how fast it is, haven't profiled the early out ray test yet :).
