The only consideration given to the box in COctTreeTriangleSelector::getTrianglesFromOctTree() is this:
Code: Select all
if (!box.intersectsWithBox(node->Box))
return;
So if the box intersects the oct tree node's box (including if the selection box is completely contained by the node's box), you get all the triangles, regardless of whether they are individually inside the selection box or not.
Well, that
technically honours the contract:
Code: Select all
//! Gets all triangles which lie within a specific bounding box.
//! Please note that unoptimized triangle selectors also may return
//! triangles which are not in the specific box at all.
But you'd expect an oct tree to be "optimized", and to do the selection properly. If the user supplied a box, then presumably he really does want only the triangles that lie "within it". Efficiency arguments be damned, the method should do what the contract implies, or else the user will have to do it himself, which is even more wasteful.
This patch fixes the problem as seen above, interpreting "within" as meaning "intersects it". If the API really does mean triangles that are fully within the box, it's easier: just test
tri.isTotalInsideBox(). However, for collision purposes, I suggest that "intersects it" is a more appropriate interpretation.
HOWEVER, it's not a candidate patch (yet) because it seems like collision animators are relying on the current behaviour. With the test program above and this patch, the camera just falls straight through the floor (comment out
camera->addAnimator(anim); to test the box selection).
I'll take a look at that later, along with CTriangleSelector::getTriangles(), which completely ignores any provided box and which presumably could also do the pruning internally rather than leaving the user to do it afterwards.
Code: Select all
Index: include/triangle3d.h
===================================================================
--- include/triangle3d.h (revision 1286)
+++ include/triangle3d.h (working copy)
@@ -49,6 +49,47 @@
box.isPointInside(pointC));
}
+
+ //! Determines if the triangle is totally outside a bounding box.
+ //! \param box: Box to check.
+ //! \return Returns true if the triangle is outside the box,
+ //! and false otherwise.
+ bool isTotalOutsideBox(const aabbox3d<T>& box) const
+ {
+ if(pointA.X > box.MaxEdge.X
+ && pointB.X > box.MaxEdge.X
+ && pointC.X > box.MaxEdge.X)
+ return true;
+
+ if(pointA.Y > box.MaxEdge.Y
+ && pointB.Y > box.MaxEdge.Y
+ && pointC.Y > box.MaxEdge.Y)
+ return true;
+
+ if(pointA.Z > box.MaxEdge.Z
+ && pointB.Z > box.MaxEdge.Z
+ && pointC.Z > box.MaxEdge.Z)
+ return true;
+
+ if(pointA.X < box.MinEdge.X
+ && pointB.X < box.MinEdge.X
+ && pointC.X < box.MinEdge.X)
+ return true;
+
+ if(pointA.Y < box.MinEdge.Y
+ && pointB.Y < box.MinEdge.Y
+ && pointC.Y < box.MinEdge.Y)
+ return true;
+
+ if(pointA.Z < box.MinEdge.Z
+ && pointB.Z < box.MinEdge.Z
+ && pointC.Z < box.MinEdge.Z)
+ return true;
+
+ return false;
+ }
+
+
//! Get the closest point on a triangle to a point on the same plane.
//! \param p: Point which must be on the same plane as the triangle.
//! \return The closest point of the triangle
Index: source/Irrlicht/COctTreeTriangleSelector.cpp
===================================================================
--- source/Irrlicht/COctTreeTriangleSelector.cpp (revision 1286)
+++ source/Irrlicht/COctTreeTriangleSelector.cpp (working copy)
@@ -159,7 +159,35 @@
for (i=0; i<cnt; ++i)
{
- triangles[trianglesWritten] = node->Triangles[i];
+ core::triangle3df & tri = node->Triangles[i];
+
+ // This test is relatively cheap, so do it first.
+ if(tri.isTotalOutsideBox(box))
+ continue;
+
+ bool intersects = false;
+
+ // This this is the next cheapest test.
+ if(tri.isTotalInsideBox(box))
+ intersects = true;
+ else
+ {
+ // Then three relatively expensive tests.
+ core::line3df lineA(tri.pointA, tri.pointB);
+ core::line3df lineB(tri.pointB, tri.pointC);
+ core::line3df lineC(tri.pointC, tri.pointA);
+ if(box.intersectsWithLine(lineA)
+ ||
+ box.intersectsWithLine(lineB)
+ ||
+ box.intersectsWithLine(lineC))
+ intersects = true;
+ }
+
+ if(!intersects)
+ continue;
+
+ triangles[trianglesWritten] = tri;
mat->transformVect(triangles[trianglesWritten].pointA);
mat->transformVect(triangles[trianglesWritten].pointB);
mat->transformVect(triangles[trianglesWritten].pointC);
