OctTree ray test optimization

Piraaate · Post by **Piraaate** » Tue Sep 23, 2008 2:33 pm

I found out that using an octtree wasn't helping me at all (performance wise) when massively testing collisions against a simple ray...
I looked at the code and found a TODO comment, so I did it !

Nothing fancy in those lines of code, I guess nobody's using it as intensively as I was but maybe someone will need this later !

new code in COctTreeTriangleSelector.cpp:

Code: Select all

// Copyright (C) 2002-2008 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h

#include "COctTreeTriangleSelector.h"
#include "ISceneNode.h"

#include "os.h"

namespace irr
{
namespace scene
{

//! constructor
COctTreeTriangleSelector::COctTreeTriangleSelector(const IMesh* mesh,
		const ISceneNode* node, s32 minimalPolysPerNode)
	: CTriangleSelector(mesh, node), Root(0), NodeCount(0),
	 MinimalPolysPerNode(minimalPolysPerNode)
{
	#ifdef _DEBUG
	setDebugName("COctTreeTriangleSelector");
	#endif
	
	if (!Triangles.empty())
	{
		u32 start = os::Timer::getRealTime();

		// create the triangle octtree
		Root = new SOctTreeNode();
		Root->Triangles = Triangles;
		constructOctTree(Root);

		u32 end = os::Timer::getRealTime();
		c8 tmp[255];
		sprintf(tmp, "Needed %ums to create OctTreeTriangleSelector.(%d nodes, %u polys)", 
			end - start, NodeCount, Triangles.size());
		os::Printer::log(tmp, ELL_INFORMATION);
	}
}


//! destructor
COctTreeTriangleSelector::~COctTreeTriangleSelector()
{
	delete Root;
}


void COctTreeTriangleSelector::constructOctTree(SOctTreeNode* node)
{
	++NodeCount;

	node->Box.reset(node->Triangles[0].pointA);

	// get bounding box
	const u32 cnt = node->Triangles.size();
	for (u32 i=0; i<cnt; ++i)
	{
		node->Box.addInternalPoint(node->Triangles[i].pointA);
		node->Box.addInternalPoint(node->Triangles[i].pointB);
		node->Box.addInternalPoint(node->Triangles[i].pointC);
	}

	const core::vector3df& middle = node->Box.getCenter();
	core::vector3df edges[8];
	node->Box.getEdges(edges);

	core::aabbox3d<f32> box;
	core::array<core::triangle3df> keepTriangles;

	// calculate children

	if (!node->Box.isEmpty() && (s32)node->Triangles.size() > MinimalPolysPerNode)
	for (s32 ch=0; ch<8; ++ch)
	{
		box.reset(middle);
		box.addInternalPoint(edges[ch]);
		node->Child[ch] = new SOctTreeNode();

		for (s32 i=0; i<(s32)node->Triangles.size(); ++i)
		{
			if (node->Triangles[i].isTotalInsideBox(box))
			{
				node->Child[ch]->Triangles.push_back(node->Triangles[i]);
				//node->Triangles.erase(i);
				//--i;
			}
			else
			{
				keepTriangles.push_back(node->Triangles[i]);
			}
		}
		memcpy(node->Triangles.pointer(), keepTriangles.pointer(), 
			sizeof(core::triangle3df)*keepTriangles.size());

		node->Triangles.set_used(keepTriangles.size());
		keepTriangles.set_used(0);

		if (node->Child[ch]->Triangles.empty())
		{
			delete node->Child[ch];
			node->Child[ch] = 0;
		}
		else
			constructOctTree(node->Child[ch]);
	}
}


//! Gets all triangles which lie within a specific bounding box.
void COctTreeTriangleSelector::getTriangles(core::triangle3df* triangles, 
					s32 arraySize, s32& outTriangleCount, 
					const core::aabbox3d<f32>& box,
					const core::matrix4* transform) const
{
	core::matrix4 mat;
	core::aabbox3d<f32> invbox = box;

	if (SceneNode)
	{
		mat = SceneNode->getAbsoluteTransformation();
		mat.makeInverse();
		mat.transformBoxEx(invbox);
	}

	mat.makeIdentity();

	if (transform)
		mat = *transform;

	if (SceneNode)
		mat *= SceneNode->getAbsoluteTransformation();

	s32 trianglesWritten = 0;

	if (Root)
		getTrianglesFromOctTree(Root, trianglesWritten,
			arraySize, invbox, &mat, triangles);

	outTriangleCount = trianglesWritten;
}


void COctTreeTriangleSelector::getTrianglesFromOctTree(
		SOctTreeNode* node, s32& trianglesWritten,
		s32 maximumSize, const core::aabbox3d<f32>& box,
		const core::matrix4* mat, core::triangle3df* triangles) const
{
	if (!box.intersectsWithBox(node->Box))
		return;

	s32 cnt = node->Triangles.size();
	if (cnt + trianglesWritten > maximumSize)
		cnt -= cnt + trianglesWritten - maximumSize;

	s32 i;
	
	for (i=0; i<cnt; ++i)
	{
		triangles[trianglesWritten] = node->Triangles[i];
		mat->transformVect(triangles[trianglesWritten].pointA);
		mat->transformVect(triangles[trianglesWritten].pointB);
		mat->transformVect(triangles[trianglesWritten].pointC);
		++trianglesWritten;
	}

	for (i=0; i<8; ++i)
		if (node->Child[i])
			getTrianglesFromOctTree(node->Child[i], trianglesWritten,
			maximumSize, box, mat, triangles);
}


//! Gets all triangles which have or may have contact with a 3d line.
void COctTreeTriangleSelector::getTriangles(core::triangle3df* triangles, s32 arraySize,
		s32& outTriangleCount, const core::line3d<f32>& line, 
		const core::matrix4* transform) const
{
	core::vector3df vectStartInv, vectEndInv;
	core::matrix4 mat;
	if (SceneNode)
	{
		mat = SceneNode->getAbsoluteTransformation();
		mat.makeInverse();
		mat.transformVect(vectStartInv, line.start);
		mat.transformVect(vectEndInv, line.end);
	}
	core::line3d<f32> invline(vectStartInv, vectEndInv);

	mat.makeIdentity();

	if (transform)
		mat = (*transform);

	if (SceneNode)
		mat *= SceneNode->getAbsoluteTransformation();

	s32 trianglesWritten = 0;

	if (Root)
		getTrianglesFromOctTree(Root, trianglesWritten, arraySize, invline, &mat, triangles);

	outTriangleCount = trianglesWritten;
}


void COctTreeTriangleSelector::getTrianglesFromOctTree(SOctTreeNode* node, s32& trianglesWritten, s32 maximumSize, 
													   const core::line3d<f32>& line, const core::matrix4* transform,
													   core::triangle3df* triangles)const
{
	if (!node->Box.intersectsWithLine(line))
		return;

	s32 cnt = node->Triangles.size();
	if (cnt + trianglesWritten > maximumSize)
		cnt -= cnt + trianglesWritten - maximumSize;

	s32 i;

	for (i=0; i<cnt; ++i)
	{
		triangles[trianglesWritten] = node->Triangles[i];
		transform->transformVect(triangles[trianglesWritten].pointA);
		transform->transformVect(triangles[trianglesWritten].pointB);
		transform->transformVect(triangles[trianglesWritten].pointC);
		++trianglesWritten;
	}

	for (i=0; i<8; ++i)
		if (node->Child[i])
			getTrianglesFromOctTree(node->Child[i], trianglesWritten,
			maximumSize, line, transform, triangles);

}


} // end namespace scene
} // end namespace irr

new code in COctTreeTriangleSelector.h:

Code: Select all

// Copyright (C) 2002-2008 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h

#ifndef __C_OCT_TREE_TRIANGLE_SELECTOR_H_INCLUDED__
#define __C_OCT_TREE_TRIANGLE_SELECTOR_H_INCLUDED__

#include "CTriangleSelector.h"

namespace irr
{
namespace scene
{

class ISceneNode;

//! Stupid triangle selector without optimization
class COctTreeTriangleSelector : public CTriangleSelector
{
public:

	//! Constructs a selector based on a mesh
	COctTreeTriangleSelector(const IMesh* mesh, const ISceneNode* node, s32 minimalPolysPerNode);

	virtual ~COctTreeTriangleSelector();

	//! Gets all triangles which lie within a specific bounding box.
	virtual void getTriangles(core::triangle3df* triangles, s32 arraySize, s32& outTriangleCount, 
		const core::aabbox3d<f32>& box, const core::matrix4* transform=0) const;

	//! Gets all triangles which have or may have contact with a 3d line.
	virtual void getTriangles(core::triangle3df* triangles, s32 arraySize,
		s32& outTriangleCount, const core::line3d<f32>& line, 
		const core::matrix4* transform=0) const;

private:

	struct SOctTreeNode
	{
		SOctTreeNode()
		{
			for (u32 i=0; i!=8; ++i)
				Child[i] = 0;
		}

		~SOctTreeNode()
		{
			for (u32 i=0; i!=8; ++i)
				delete Child[i];
		}

		core::array<core::triangle3df> Triangles;
		SOctTreeNode* Child[8];
		core::aabbox3d<f32> Box;
	};


	void constructOctTree(SOctTreeNode* node);
	void deleteEmptyNodes(SOctTreeNode* node);
	void getTrianglesFromOctTree(SOctTreeNode* node, s32& trianglesWritten,
			s32 maximumSize, const core::aabbox3d<f32>& box,
			const core::matrix4* transform,
			core::triangle3df* triangles) const;
	void getTrianglesFromOctTree(SOctTreeNode* node, s32& trianglesWritten, s32 maximumSize, 
		const core::line3d<f32>& line, const core::matrix4* transform,
		core::triangle3df* triangles) const;

	SOctTreeNode* Root;
	s32 NodeCount;
	s32 MinimalPolysPerNode;
};

} // end namespace scene
} // end namespace irr


#endif

JP · Post by JP » Tue Sep 23, 2008 2:36 pm

Nice one! Make sure hybrid knows about this so it can hopefully be included into the engine properly!

rogerborg · Post by **rogerborg** » Tue Sep 23, 2008 2:53 pm

Uh, could you explain (or better yet, post a SVN diff) what's actually changed? I'm having trouble seeing the diffs, as the posted code has spaces instead of tabs.

Piraaate · Post by **Piraaate** » Tue Sep 23, 2008 3:26 pm

rogerborg wrote:Uh, could you explain (or better yet, post a SVN diff) what's actually changed?

Wow guys, you answered fast, thank you !
Does this help ? I'm not used to read this type of reports...

Code: Select all

Index: GenericDriverMM3D/source/Irrlicht/COctTreeTriangleSelector.cpp
===================================================================
--- GenericDriverMM3D/source/Irrlicht/COctTreeTriangleSelector.cpp	(revision 1580)
+++ GenericDriverMM3D/source/Irrlicht/COctTreeTriangleSelector.cpp	(working copy)
@@ -177,15 +177,64 @@
 		s32& outTriangleCount, const core::line3d<f32>& line, 
 		const core::matrix4* transform) const
 {
-	core::aabbox3d<f32> box(line.start);
-	box.addInternalPoint(line.end);
+	core::vector3df vectStartInv, vectEndInv;
+	core::matrix4 mat;
+	if (SceneNode)
+	{
+		mat = SceneNode->getAbsoluteTransformation();
+		mat.makeInverse();
+		mat.transformVect(vectStartInv, line.start);
+		mat.transformVect(vectEndInv, line.end);
+	}
+	core::line3d<f32> invline(vectStartInv, vectEndInv);
 
-	// TODO: Could be optimized for line a little bit more.
-	COctTreeTriangleSelector::getTriangles(triangles, arraySize, outTriangleCount,
-		box, transform);
+	mat.makeIdentity();
+
+	if (transform)
+		mat = (*transform);
+
+	if (SceneNode)
+		mat *= SceneNode->getAbsoluteTransformation();
+
+	s32 trianglesWritten = 0;
+
+	if (Root)
+		getTrianglesFromOctTree(Root, trianglesWritten, arraySize, invline, &mat, triangles);
+
+	outTriangleCount = trianglesWritten;
 }
 
 
+void COctTreeTriangleSelector::getTrianglesFromOctTree(SOctTreeNode* node, s32& trianglesWritten, s32 maximumSize, 
+													   const core::line3d<f32>& line, const core::matrix4* transform,
+													   core::triangle3df* triangles)const
+{
+	if (!node->Box.intersectsWithLine(line))
+		return;
+
+	s32 cnt = node->Triangles.size();
+	if (cnt + trianglesWritten > maximumSize)
+		cnt -= cnt + trianglesWritten - maximumSize;
+
+	s32 i;
+
+	for (i=0; i<cnt; ++i)
+	{
+		triangles[trianglesWritten] = node->Triangles[i];
+		transform->transformVect(triangles[trianglesWritten].pointA);
+		transform->transformVect(triangles[trianglesWritten].pointB);
+		transform->transformVect(triangles[trianglesWritten].pointC);
+		++trianglesWritten;
+	}
+
+	for (i=0; i<8; ++i)
+		if (node->Child[i])
+			getTrianglesFromOctTree(node->Child[i], trianglesWritten,
+			maximumSize, line, transform, triangles);
+
+}
+
+
 } // end namespace scene
 } // end namespace irr

Code: Select all

Index: GenericDriverMM3D/source/Irrlicht/COctTreeTriangleSelector.h
===================================================================
--- GenericDriverMM3D/source/Irrlicht/COctTreeTriangleSelector.h	(revision 1580)
+++ GenericDriverMM3D/source/Irrlicht/COctTreeTriangleSelector.h	(working copy)
@@ -61,6 +61,9 @@
 			s32 maximumSize, const core::aabbox3d<f32>& box,
 			const core::matrix4* transform,
 			core::triangle3df* triangles) const;
+	void getTrianglesFromOctTree(SOctTreeNode* node, s32& trianglesWritten, s32 maximumSize, 
+		const core::line3d<f32>& line, const core::matrix4* transform,
+		core::triangle3df* triangles) const;
 
 	SOctTreeNode* Root;
 	s32 NodeCount;

rogerborg wrote:I'm having trouble seeing the diffs, as the posted code has spaces instead of tabs.

how can I fix this ? I just copy-paste from Visual Studio, is there a way to avoid that problem ?

Dorth · Post by **Dorth** » Tue Sep 23, 2008 3:44 pm

Yeah, use tabs, like 99% of people instead of spaces. In MSc++, I think there's an option as to whether your tabs are tabs or spaces and how many spaces they appear to be (or are).

Piraaate · Post by **Piraaate** » Tue Sep 23, 2008 3:48 pm

Ok no, my bad, I posted the original cpp file !! argh ! Sorry sorry ! I updated the first post...

rogerborg · Post by **rogerborg** » Thu Sep 25, 2008 8:02 am

Piraaate wrote:Ok no, my bad, I posted the original cpp file !! argh ! Sorry sorry ! I updated the first post...

Ah, good, I thought I was going fruit loops.

That looks reasonable.

My view is that all getTriangles() methods should reject as many individual triangles as possible, since any extra cost to do the rejections will be made up in not having to ray testing so many triangles.

I've also got a patch up for triangle selector checks that does that. It may be complimentary with this one; I haven't munged them together to check though.

varmint · Post by **varmint** » Mon Sep 29, 2008 9:14 am

very kewl

Interesting enough we used this routine a lot and is called every CPU tick multiple times. Something changed in the collision from 1.4 to 1.4.1.. Then change didn't work out well for us and slowed things down, so we stuck with 1.4's collision.

When I tested this code out we got 5 - 10 fps less then with the original. This was tested on multiple platforms and systems, with the same results. Not sure why, wonder if

Code: Select all

   if (SceneNode)
   {
      mat = SceneNode->getAbsoluteTransformation();
      mat.makeInverse();
      mat.transformVect(vectStartInv, line.start);
      mat.transformVect(vectEndInv, line.end);
   }

this is were the slow down.

Also all of our meshes are optimized.

hybrid · Post by **hybrid** » Mon Sep 29, 2008 10:57 am

Hmm, don't know which change might introduce a slow down in that part of the code. The only "major" change that the methods used here had was an additional check for identity. Could be that this slows down the rest a little bit, but I'd say it's just a little overhead compared to the full inversion of the matrix later on.
But it's also not really related to triangle checks, is it?