Optimal Way of Colliding with Visible Geometry

What options are there for speeding up visible geometry collisions (without using simplified Collision Geometry such as spheres, planes, etc…)?

I have spent quite some time looking at 2 options which unfortunately didn’t end up working out.

My first idea was to use trianglemesh from bullet. Unfortunately, I want to detect the interior of the mesh and the testAllRays query only returns the first surface of collision with the test ray. This doesn’t help me much because I must know all surfaces of a trianglemesh that the ray passes through.

My second idea was to implement this helper function:
[url]GeomNode vs CollisionPolygon]

Here is my code for converting a geometry into a set of collision polygons (below). Note that for the simple case of the prebuilt “smiley” model everything runs fine. But when I try to load my sketchup cylinder.egg file (I converted it using dae2egg) the converted collision solid isn’t at all like the visible geometry (missing triangles). So, is this an issue with dae2egg?

note: see my comments for where I specify what “works” and what doesn’t


from direct.showbase.ShowBase import ShowBase
from panda3d.core import CollisionTraverser
from panda3d.core import CollisionHandlerQueue,CollisionRay
from panda3d.core import CollisionNode
from panda3d.core import CollisionPolygon
from panda3d.core import NodePath
from panda3d.core import GeomVertexReader
from panda3d.core import BitMask32
from panda3d.core import PointLight
from panda3d.core import Point3

def geoms_to_collisions(incomingNode):
	parent = NodePath('cGeomConversionParent')
	for c in incomingNode.findAllMatches('**/+GeomNode'):
		geomNode = c.node()
		for i in range(geomNode.getNumGeoms()):
			geom = geomNode.getGeom(i)
			vdata = geom.getVertexData()
			cChild = CollisionNode(c.getName())
			for i in range(geom.getNumPrimitives()):
				prim = geom.getPrimitive(i)
				vertex = GeomVertexReader(vdata, 'vertex')
				prim = prim.decompose()
				for p in range(prim.getNumPrimitives()):
					s = prim.getPrimitiveStart(p)
					e = prim.getPrimitiveEnd(p)
					v = []
					for i in range(s, e):
						vi = prim.getVertex(i)

					colPoly = CollisionPolygon(*v)
			parent.attachNewNode (cChild)
	return parent

base.cTrav = CollisionTraverser()

#this works:
model = loader.loadModel('smiley')
#this doesn't
#model = loader.loadModel('cylinder.egg')
model.setPos(0, 25, 0)

model_NP = geoms_to_collisions(model)

interior_test_ray = render.attachNewNode("interior_root")
inside_ray = CollisionRay()	 # Create the ray
inside_ray.setOrigin(0,0,0)	# Set its origin
inside_ray.setDirection(1,0,0) # And its direction
rayCol = CollisionNode('insideRay') # Create and name the node
rayCol.addSolid(inside_ray) # Add the ray
rayCol.setFromCollideMask(BitMask32.bit(0)) # Set its bitmasks
insideColNp = interior_test_ray.attachNewNode(rayCol)

cRayHandler = CollisionHandlerQueue()
base.cTrav.addCollider(insideColNp, cRayHandler)


insideColNp.posInterval(5, Point3(5, 25, -2), startPos=Point3(-10, 25, 1), fluid=1).loop()

redPointLight = render.attachNewNode( PointLight( "PointLight" ) )
render.setLight( redPointLight )


not_working_model.zip (5.04 KB)

When you ask that… are you indeed talking about exact collision detection (using non collision optimized geometry e.g. sphere, retangle) or collision detection in general?

Exact collision detection will always be more expensive than sphere or rectangle, but there is something faster than even spheres and retangles…

Pure mathematics.

I used that approach in the RTS project I was working on, which kept my frame rate looking good on an old outdated graphics card, even with all the geometry and many actors moving around and animating. If I would have ran that project on an up to date PC, the frame rate would have been 60 at worst.

If you really don’t truly need the exact collision detection, I would recommend using a pure mathematical approach. It will require more programming work but the results will be worth it. I designed an entire path finding system using it and the fps results did not disappoint.

Hope you find an approach that works.


Mark, can you explain what you mean or give an example for your approach? I’m in a similar situation.


yes, as long as my precise geometry is maintained. So, as an example CollisionPolygon is fine but CollisionSphere is not.

Here is a summary of the collective ideas so far:

Pure math approach: use (for instance) the C++ CGAL library (development time is an issue unfortunately)

Only Detect a Small Piece of Visible Geometry at a Time:This works quite well. The solution involves partitioning your GeomNodes (collections of polygons) into sets (for instance, maybe Z-axis sub level sets - meaning feet are in one GeomNode and head are in another). I used the egg writing capabilities of Panda to read the Z axis vertex points of ALL polygons in the egg file. I then reorganize the polygons into their respective Z-level subsets. Now, your game logic decides which subset of GeomNodes to traverse for collisions. And that’s it, you make a custom CollisionTraverser and set the Collision node to one or a few of your GeomNodes. This all assumes you have this information in realtime. Now you are only examining a tiny portion of the geometry at once and it is very very fast!! It is also simple to code (aside from partitioning the geomnodes which you do offline of course).