Collision with procedural mesh

[klobaska]

I have procedurally generated hexagon mesh, where every hexagon is GeomNode which contains one 2 geoms (one hexagon lines other hexagon surface). The hexagon surface is a geom created with 6 triangle primitives. The chunks of hexagons are grouped into NodePath.

I would like to pick individual hex based on mouse position. For this i have set up CollisionRay with CollisionTraverser. However, when i try to see detected collisions with myTraverser.showCollisions(base.render) it seems that it tests against every single primitive. (The small triangles.) This seems like very inefficient method.

1. How can i specify the into objects for collisions?

2. Based on documentation, i was under impression, that i have to specify collisions solids before being able to check for collisions. But it seems my ray is checking against all visible geometry, even if i haven’t specified any collision solids, nor set up CollisionNodes. I would be glad if someone could explain why it behaves this way.

3. The efficiency: I understand that the most efficient way to select objects is to set up collision plane and determine the intersection and calculate corresponding hex. However, in the future the mesh wont be flat, some hexes will be elevated, therefore this is not viable. I could set up several planes at different heights, but would this really be more efficient? The mesh will have large number of hexes, so is it really so inefficient to test for collisions with every hex?

example code of collision picker:

def pickHex():
    mpos = base.mouseWatcherNode.getMouse()
    pickerRay.setFromLens(base.camNode, mpos.getX(), mpos.getY())

    myTraverser.traverse(base.render)
    # Assume for simplicity's sake that myHandler is a CollisionHandlerQueue.
    if handler_queue.getNumEntries() > 0:
        # This is so we get the closest object
        handler_queue.sortEntries()
        pickedObj = handler_queue.getEntry(0).getIntoNodePath()
        print(pickedObj)


CollisionTraverser()
handler_queue = CollisionHandlerQueue()

myTraverser = CollisionTraverser('myTraverser')

pickerNode = CollisionNode('mouseRay')
pickerNP = base.camera.attachNewNode(pickerNode)
pickerNode.setFromCollideMask(GeomNode.getDefaultCollideMask())
pickerRay = CollisionRay()
pickerNode.addSolid(pickerRay)
myTraverser.addCollider(pickerNP, handler_queue)
myTraverser.showCollisions(base.render)

def printMouse(task):
    if base.mouseWatcherNode.hasMouse():
        pickHex()
    return Task.cont

[Thaumaturge]

@klobaska

How can i specify the into objects for collisions?

There are two ways that come to mind, offhand:

First, you could simply keep in the scene-graph only those that you want to test against, detaching the others until you want to test against them.

(“But,” you might say, “it’s testing against visible geometry, so doing this would involve removing my hexes!” To that, look to my answer to your next question…)

And second, you could apply bitmasks to control which collision-objects are considered valid targets for the ray.

(For more on this, see this page.)

@klobaska

But it seems my ray is checking against all visible geometry, even if i haven’t specified any collision solids, nor set up CollisionNodes. I would be glad if someone could explain why it behaves this way.

That comes from the following line in your code, I believe:

@klobaska

pickerNode.setFromCollideMask(GeomNode.getDefaultCollideMask())

This line instructs the ray to collide with visible geometry, which has the collision-mask that is returned by “GeomNode.getDefaultCollideMask()”.

I’m guessing that you got that line from the manual. I think that it’s used there just for the sake of simplicity, so that the example needn’t set up specific collision geometry.

@klobaska

I could set up several planes at different heights, but would this really be more efficient? The mesh will have large number of hexes, so is it really so inefficient to test for collisions with every hex?

Hmm… How many different heights might hexes be placed at?

If there are only a few potential heights that they might have, then using the “plane” method might be fine.

If not, then if you switch from colliding with visible geometry to colliding with collision geometry then you might find that Panda’s internal culling mechanisms keep it sufficiently performant.

It would be something to test, I think!

[H3LLB0Y]

Hi kobaska,

Firstly, great response from @Thaumaturge, a lot of good info there.

Not sure if you’ve come across this other post in your searches, if not it might be worth looking into.

Picking visible models

Hey all, with the help of @rdb I recently created a little script to pick any 3D objects without the need of using a collision detection system but only a simple GLSL shader. The sample shows how to set up the scene and handle the actual picking. Hope you’ll find this useful.

I’m considering it for my project which has some similar aspects to your project!
While I’m not using procedurally generated geometry, I do have hexagons that need picking!
Here’s a little preview of it. (To note: I’m picking EVERY frame, and still getting 60+FPS even in it’s unoptimized state, except when showing the collisions )

Picking Hexagons

Initially I was using the same approach to pick my objects (picking using visible geometry).
However that quickly became immensely inefficient.
Currently I’m using Blender for modelling, and using blend2bam to convert.
Now rather than GeomNode.getDefaultCollideMask() I’m using CollisionNode.getDefaultCollideMask() and it’s very smooth even with a large amount of models on screen at once! There’s probably a lot more that could be done to optimize it further also.

Some quick thoughts on optimizations that I might look into:

• Using Cylinder collision primitives (this is pure speculation and I’ve not looked into how any of the collision checks work, but my intuition tells me that a Cylinder would be more efficient than checking multiple triangles).
  • Caveat: This would mean some parts of the Visible Geometry would be outside the Cylinder and thus will be an inaccurate pick operation.
• Hierarchical collision tree
  • If your scene is static this might be a good option: Magical collision scene optimizer
  • If not, then dividing your scene up dynamically somehow and checking only for collisions in relevant spaces.

Your idea about having multiple planes and testing that was is an interesting one, and I think has a fair amount of potential! Assuming the planes are at discrete steps (and the hex-grid is the same on each plane), then this might actually be the most efficient approach if all you’re looking to pick are the hexagons.
For this I’d recommend:

• Taking a peek at the Panda3D Chessboard sample. (specifically, the PointAtZ function)
• From there, check out the following website (specifically, Pixel to Hex (linked)) Hexagonal Grids (Absolutely amazing resource this one!)

Best of luck going forward!
Curious to know which approach you take and how it works out for you.

[klobaska]

Thank you for the answers, it helped me clarify some things.

[klobaska]

Hi, thanks for sharing. It seems like very interesting project. Nice job.

In the end, I am more less decided to use several planes to detect collisions. My grid will only have ± 10 discrete height levels. It will still lead to some minor imprecisions (caused by slopes), but i am willing to live with it. So far I tested it only with a single plane. Seems like a computationally efficient method.

To be honest I don’t like the solution with cylinders. It will speed up some things, but you will most likely get some dead spots.

I did came across Hexagonal Grids, it is very helpful indeed. Very good resource you might have heard of is HexMap Tutorial, it is not for panda3D, but most of the logic still applies.

I have one newbie question, how did you achieve the highlight effect on hover? I mean, if you your ray collides with hex, you can change your color, but how did you achieved the reversal effect, that is, changing it back when you no longer collide with it.

[Thaumaturge]

@klobaska

I have one newbie question, how did you achieve the highlight effect on hover? I mean, if you your ray collides with hex, you can change your color, but how did you achieved the reversal effect, that is, changing it back when you no longer collide with it.

One way might be to check the object that the ray collided with, and if it isn’t the previously-highlighted object, to then de-highlight that previously-highlighted object.

That is, when you test with the ray, if it hits something other than the thing that was highlighted (or hits nothing at all), then you can de-highlight the thing that was highlighted.

Something like this, in broad strokes:

# Presume that you found the object that the ray collided with,
# or "None" if it collided with nothing. Either way, presume
# that it's stored in a variable called "rayHitResult"...

if self.lastHit != rayHitResult:
    self.dehighlight(self.lastHit)

if rayHitResult is not None:
    self.highlight(rayHitResult)

self.lastHit = rayHitResult

[H3LLB0Y]

Again, thanks @Thaumaturge for your great reply

My approach is pretty much as described.

There were issues that I ran into during my implementation, such as the hit object being a GeomNode in my objects hierarchy, so a bit of work was needed to get back the actual object I was after. (Intricacies due to the Python/C++ interface I believe, can’t go into too much detail sorry )

My objects set themselves as a Python Tag on the “root” NodePath of the object (They actually subclass NodePath so for me). self.setPythonTag(key, self)

Then when picking, ancestorNodePath = pickedObj.findNetPythonTag(key) (Confirm this isn’t empty incase you pick something that’s actually got the tag.)

And finally, myObject = ancestorNodePath.getPythonTag(key) will return you the original object set at the beginning.

See: NodePath — Panda3D Manual (setPythonTag) and NodePath — Panda3D Manual (getNetPythonTag)

The following Manual page might also be of some use.
https://docs.panda3d.org/1.10/python/programming/collision-detection/clicking-on-3d-objects

As for specific details about the highlighting, my highlight and dehighlight are just calling setColorScale(2.5) and clearColorScale on the retrieved NodePath object that’s picked.

Hope that’s of some use!