Proper way to do "diamond" Heightfield tessellation?

Proper way to do "diamond" Heightfield tessellation?


In order for my heightfield collision to match my rendered mesh, I need to tessellate the heightfield such that the triangles form a diamond pattern -- in other words, a pattern where adjacent quads tessellate using alternating pairs of points (either [p00,p11] or [p01,p10]).

As I understand it, the heightfield's "getTriangleFlip" method is meant to return a constant (true/false) value, implying that the tessellation pattern described above isn't supported. When experimenting in the Havok demo code, I was able to support my pattern by maintaing a few static variables in the getTriangleFlip method, and incrementing them each time getTriangleFlip was called.

This approach only works if getTriangleFlip is called for each quad in a heightfield when that heightfield is queried for a raycast, rigidBody collision, etc. I have no idea if that assumption is true. Can someone tell me if my approach is reasonable, or if there's some better way to implement diamond tessellation in a Havok heightfield?


3 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

To follow up:

After experimenting further with the Havok demos, it seems wrong to hope that getTriangleFlip would be called sequentially for each triangle in the heightfield; this is done when initializing the heightfield for the renderer, but not during the staticLinearCast calls generated by collisions between a characterProxy and that heightfield (for example).

It looks like a workable approach would be to inherit off of hkpTriSampledHeightFieldCollection::getChildShape, as that method has a "key" param from which I think I can extract the XZ of the quad being queried. I could then prep my sampled heightfield shape to return the right true/false value when getChildShape eventually calls down to shape::getTriangleFlip.

This assumes getTriangleFlip is always called via Collection::getChildShape, but that at least seems a saner assumption than the one I was hoping to make in my original post. Still, any feedback from someone more knowledgeable would be much appreciated.

Thanks, -RG

Hi Rahul,
Yes, you're correct that getTriangleFlip() is generally expected to be constant. There's a pending request to change it to be getTriangleFlip(int x, int z), but I don't think there are any plans to do that in the near future.

Your idea of inheriting from hkpTriSampledHeightFieldCollection is a pretty good one. The header describes how the x, z, and triangle information is encoded in the shape key:

int xCoord = (key & 0x0000ffff) >> 1;
int zCoord = key >> 16;
int whichTriangle = (key & 1); // will be 0 or 1

I'm pretty sure that linear casting with then go through your getChildShape implementation, since hkpTriSampledHeightFieldBvTreeShape will grab a list of all triangles overlapping the AABB of the cast, and then each child shape will be linear casted against individually. The same goes for physics collisions.

One other thing to watch out for is that (by default) raycasting will always go through hkpSampledHeightFieldShape::castRayInternal, which uses the triangle flip. You can probably implement your own raycast method in a subclass of hkpTriSampledHeightFieldBvTreeShape; we basically do DDA in the (x,z) plane, but you might be able to get better results with something else, e.g. a kdtree.

Of course, all of this seems more work than just changing your rendering mesh Is there a particular reason that you do it that way, or is that just what your toolchain spits out?

Hope that helps; let me know if you hit any other snags...


Leave a Comment

Please sign in to add a comment. Not a member? Join today