As I understand it–and please correct me if I’m mistaken–when using Bullet physics, it’s likely to be most efficient to have a level’s environment collision-(triangle-)mesh in a single node, allowing Bullet’s internal logic to handle culling, etc.
However, I’ve found a minor snag in doing so: I want the sound made by the player’s footsteps to vary according to the surface on which they’re walking. To this end, I’ve added a tag to various environmental collision objects (with most being untagged, indicating that the default sound is to be used). During the game, a ray-cast is used to detect the surface being walked on, and the tag can easily-enough be retrieved from the result of that cast. Merging the meshes would (presumably) lose this data.
Is there some other way that I might store that data? Vertex colours in the collision mesh, or some such?
Or would it be better to simply join the meshes according to their footstep sounds–or join only those that are near to each other, leaving scattered ones separate?
What if you used BulletRayHit.get_triangle_index() or BulletRayHit.get_shape_part() to get the index of the particular triangle that was hit and have a dictionary associating each triangle index in the mesh with a surface specific sound effect?
Hmm… That’s possible–presuming that I can read the triangle-index data and access some property of the triangle (like vertex colours, as previously mentioned), I could assign the footstep sounds in Blender and construct the dictionary or list at loading-time.
Looking at my current, small level, I see that I have nearly five thousand faces in my collision geometry. That might be reduced a little, but it’s likely to go up significantly once I move on to larger levels. Will this technique perform well for a medium-sized level?
I do not think a bullet triangle mesh preserves vertex colors, as when you create one from an egg or bam it gets stripped down to only what is needed for collision detection.
Sorry about suggesting using a dictionary (rather than a list), I had destructible environments on the brain. List should yield faster lookup in this case, I believe.
I am certainly no computer scientist, but for what it is worth I cannot see a reason why this approach should perform poorly for larger levels. Lists in python are actually dynamic arrays rather than linked lists, so reaching the datum accessed by a high index value does not require “walking” the list a like number of times. Dynamic arrays can allocate a bit more memory than they need (maybe twice in the worst case), but both the index and the stored data (itself probably an index for the surface type or sound effect to be used) should just be a single int each, so not a whole lot of extra memory, I suppose.
But the only way to really know if breaking up the level into separate shapes or using triangle indexing would be faster would to implement both and benchmark them against each other. The layout of your benchmarking level would play a role, in terms of how much broadphase overlap it has among different surfaces and the number of different surfaces. So you would want to use your worst case level, with lots of surfaces and AABB overlapping.
Then again the difference could be so small as to be no concern at all regardless of the method used. The bullet documentation doesn’t seem too clear on how much of a broadphase performance gain you get by putting all triangles under one roof. It just vaguely states:
Hmm… In that case, where would I store the footstep-sound data? I would far prefer that it be specified while building the level in Blender, which means that I want something that will be exported.
Not a problem, and fair enough–I thought that a list might be a better idea, I believe.
Hmm… Fair enough, that seems like a good point.
Fair enough again.
At the moment I only have two levels available, and one of those is a short prologue/tutorial level. Thus the other of those two is likely to be my benchmarking level, even though it’s not likely to be my most complex.
This does seem to indicate that combination is generally the better solution–but as you say, it’s somewhat vague on just how marked an difference there is likely to be between a single mesh and a handful of them.
I would, in Blender, break the mesh up by surface type and then recombine the fragments in Panda Bullet a triangle at a time so as to keep track of the triangle indexes.
Also, if the blender exporter is spitting out trifans or tristrips you might need to first split the mesh into individual triangles. These (I believe obsolete for modern GPUs) primitive types might throw off the indexing. If Panda Bullet quietly breaks these into individual tris then that will create many extra hidden indexes and ruin everything.
So you load your “snow” surface mesh that covers all of and only snow covered surfaces. Iterate over its GeomPrimitives and for each triangle primitive:
Call BulletTriangleMesh.add_triangle() and make sure the “remove_duplicate_vertices” parameter is set True so that it is recombined into an efficient mesh (this should only affect vertexes and not triangle indexing, but just in case you could start off with it set False until you know the system works correctly).
Append whatever variable indicates snow to your list.
Then do the same thing, for “sand”, “wood planking”, etc.
Now that I think about it, I suppose you could use vertex colors just to get your surface data from Blender to Panda, but it seems more problematic since you need data associated with triangles, not vertexes. Using vertex colors you will end up with triangles that have different colored vertexes telling it to be several different surface types at once and the triangle will have to decide for itself which vertex to listen to.
Yeah with a handful of meshes you could safely bet on no big slow down… except that they so heavily overlap. That really muddies the water.
Hmm… That could be done, but what effect would it have on the efficiency of the result? Is a collision mesh built up piecewise like that no less efficient than one generated from a mesh via the BulletHelper class?
Heh, that’s a good point. The suggestion of vertex colours was just an example, I believe–if a poor one–prompted, I daresay, by the fact that I’ve used them quite often elsewhere. ^^;
Indeed, I fear.
I’ve done some basic tests, and, even in the smallish level on which I’m working, combining the colliders does seem to help noticeably. I forget whether I combined them into a single mesh or one mesh per floor type, but whichever it was, it improved on the case of many separate meshes, as I recall.
Good point, I don’t really know if it would be the same now that I think about that. I suppose there might also be a risk that whatever optimization might be done for a collision mesh could also modify the indexes. So maybe this calls for a new plan A-- brute force raytesting.
Export everything as one mesh from blender first. This first export is converted directly into the bullet collision mesh with all of its optimizing goodness not messed with.
Export again as meshes separated by surface type. These becomes the guides for the raytest index finding.
For each triangle in a guide mesh, find the center of the triangle by averaging the positions of its three vertexes and shoot a short raytest through this center point so that it hits only the corresponding triangle on the master collision mesh (probably mostly z axis aligned rays if these surfaces are mostly floors, but where your game has climbing or wall walking you will need to test with some horizontal rays of course).
Get the triangle index from the “Ray Result” using either get_triangle_index() or get_shape_part() (by the sounds of it, the first one gets you what you want, but this is one place where bullet is vague and a bit odd so try the second if the first does not work as expected) add this to a temporary dictionary with the triangle index being the key and the surface type of the guide mesh being the value. For now we need a dictionary rather than a list because we will be receiving indexes in a random order.
Build up a list from the dictionary, iterating the length of the dictionary and accessing the dictionary with the current iteration count and appending the received value to the list. Throw out the dictionary and save the list.
I guess this actually might be a lot more performant than index counting while rebuilding the mesh. And even if not, it is only a one time cost per scene. So this approach maybe should have been my first suggestion.
Hmm… That sounds both a little slow during load-time, and feels a little… fragile, to me, a little too likely to produce errors.
My immediate thought was to simply iterate over the triangles, comparing the vertex-positions in one set to those in the other. However, from what I’ve seen in the documentation, there doesn’t seem to be a way of accessing the triangles…
In which case, what is the purpose of having the ray-cast return a triangle index? o_0
(I actually don’t have my collision meshes separated into floors and walls. While I forget my original reasons for doing so (I perhaps just didn’t think of it at the time, it does hopefully mean that the traversability of a given piece of geometry follows fairly consistently from its form. Separating the meshes also seems likely to invite mistakes that might result in areas seeming traversable, but being inexplicably impassable.
… It’s also easier to build that way, I feel.
Nevertheless, if really called for, I would consider separating the meshes.)
That may be why I did not think of or suggest it earlier, it seems really twisted.
But the way I figure it, in realtime you are doing a raytest every frame to detect what surface the player is standing on right? That’s ~60 raycasts per second and you said your level had 5000 collision triangles in it. So at that very modest rate of computing power it would take 83 seconds to process the level. Hardware which could not do that job in 1/10th that time probably could not even run the game at a decent frame rate.
As for errors, since the raytest would be so short, it would be hard for it to pick up anymore than the target triangle. It only needs to be long enough to amply handle any precision issues in parts of the scene far from the origin. You could also just compare triangle centers (technically called “centroids” by mathematicians so as to confuse us) and that should be completely error proof. But you won’t get broadphase optimization that comes automatically with raytesting through bullet and bullet is written in C++ not python, so I imagine this could be slower, perhaps by a lot even.
But if the necessary data can be acquired, the potential simplicity and error resistance of comparing triangle centers may make it still the better option over raytesting.
In Panda3D triangles are a type of GeomPrimitive so you get access to them through Geom.get_primitive(index) or Geom.get_primitives(). Although, this reminds me that again, trifans and tristrips might also be lumped in with them as they are primitives as well. You may need to export the guide mesh as separate triangles or write extra functions to handle trifan and tristrip centers too. I don’t remember if blender or yabee have any way to specify using only individual triangles for mesh composition but that would also work.
It is a way to access the triangles in the singular Bullet collision mesh. (If you mean you cannot find another way to access Bullet collision triangles individually then this might even be the way.)
Hmm, well you could use the vertex normals to determine the face normal and raytest along that vector.
Having done a bit more digging, it looks as though Bullet has a “striding mesh interface” that one can get from a btBvhTriangleMeshShape, which provides access to the triangles themselves. However, we don’t seem to have a wrapper for that in Panda.
… Come to think of it, are we confident that the triangle indices won’t change at some point after loading…? It seems unlikely, but without a better idea of what’s going on within Bullet I’m hesitant to say with confidence…
You could post a feature request for it to the panda issue tracker. Might be a while until someone with the necessary knowledge can get to exposing it in panda bullet though.
In the mean time there is still the raytest workaround, at least.
It is hard to imagine any advantage for bullet changing the data around for something that hasn’t itself in any way changed. That is, if you are not adding or removing parts or transforming or rotating the mesh after recording the triangle indexes, then it seems like a waste of resources for bullet to go mucking around with them.
But with technology as sophisticated and heavily optimized as a real time physics engine, I am not confident of anything until it is thoroughly tested with the specific application in mind. I find things can work differently from my starting assumptions based on the documentation and seemingly logical thinking.
Eh, I’m not inclined to wait so on this matter. I’ll look for other approaches, I think, even if it does mean using the ray-casting system that you propose. ^^;
Indeed, on both counts.
All right, unless there are further suggestions, I’m going to give this further thought on my end. I may try the ray-casting system, or may leave it at one mesh per footstep type–presuming that there are no further suggestions, and no better idea comes to me, I suppose.
Are there any performance implications that I should be aware of? And is there anything that I should be aware of when back-porting this into my build of 1.9.4? (Conflicts with old code, more-recent changes that it relies upon, etc.)
Actually, I think MAKE_MAP_PROPERTY might not be available in 1.9.4. You may have to remove the MAKE_MAP_PROPERTY line and move the methods from “public” to “PUBLISHED” section of the class so you will be able to use get_triangle(n) instead of triangles[n].
In all fairness, the point made above regarding Bullet’s optimisations making the ray-casting method likely faster than the triangle-comparison method does incline me a little more to the former, so I’m not sure that I’ll end up using this newly-exposed functionality. Nevertheless, I appreciate its addition–thank you!
