Shape Defined Via Equation?

Post Reply
GlitchEnzo
Posts: 6
Joined: Fri Apr 09, 2010 1:23 am

Shape Defined Via Equation?

Post by GlitchEnzo » Fri Apr 09, 2010 1:28 am

I was wondering if it would be possible to define a custom shape by using the equation of the solid.

Let me explain what I mean in a simple example:
Let's say I want to create a custom sphere shape. A sphere has an specific equation that defines it, so given a point in 3D space, you can determine whether or not that point lies within the sphere. This should allow collision detection. Also, it is very easy to calculate the normal vector of any point on a sphere.

Now for a more complicated explanation of WHY i want to do this:
Currently I am rendering spherical terrain that is tessellated via the DX11 tessellator and then displaced by different sums of Perlin and Voronoi Noise. I could use the base mesh that I am sending to the GPU for physics, but it would look horrible because it is too low in detail. (At the highest level of tessellation, each quad becomes 4,076 quads, so you would see objects sinking below/floating above the rendered terrain.) I can't use btHeightfieldTerrainShape because the terrain is spherical, not flat. I could try to use btBvhTriangleMeshShape, but my mesh is simply a sphere on the CPU side since it doesn't get displaced until the GPU. So that means I would have to displace it all on the CPU just for physics, which be wasteful. Not only that, but it would be hard (if not impossible) to keep the physics mesh tessellation somewhat in sync with the GPU tessellation. (btBvhTriangleMeshShape is meant to be static, so I would have destroy and recreate each tessellated quad as they changed.)

If I could define a shape in Bullet via an equation that would be much better. I have the equation defining my terrain (the combination of Perlin and Voronoi Noise). Instead of creating many meshes, I could have a method that just takes a 3D point and determines if it lies within my terrain solid. I could have a similar method for getting the terrain surface normal.

I should mention that I have not yet used Bullet, but I have read some of the documentation. In the past I have used PhysX for my physics, but since it is closed source then I cannot easily try something like this.

I guess what I want to know is this:
Does this sound feasible at all?
Is this possible in Bullet by writing my own custom shape?
Does anyone have any potential better ideas to solve this problem?

I fully accept the fact that I may be way off base here. I haven't yet looked into how Bullet detects collision between shapes.

bone
Posts: 235
Joined: Tue Feb 20, 2007 4:56 pm

Re: Shape Defined Via Equation?

Post by bone » Fri Apr 09, 2010 2:49 pm

I just posted something similar last night, I hadn't seen your post yet: http://www.bulletphysics.org/Bullet/php ... f=9&t=4954

But we may have different primary goals here. It sounds like your terrain is being deformed, is that correct? The reason I need to do this is because I can't possibly store the entire tessellated mesh, so instead I want to generate just what I need on-the-fly. The ability to change the shape function isn't currently a requirement, but it wouldn't seem to interfere with my goal at all.

GlitchEnzo
Posts: 6
Joined: Fri Apr 09, 2010 1:23 am

Re: Shape Defined Via Equation?

Post by GlitchEnzo » Fri Apr 09, 2010 4:15 pm

It does sound like we have very similar goals.

I do not require my terrain to be deformed, but since I have changing LOD via tessellation and the actual terrain height displaced via noise functions, then from Bullet's point of view it is essentially mesh deformation.

I'm going to poke around in the source code and see if I can somehow create a SphericalSolidShape or something similar that achieves what I was talking about.

bone
Posts: 235
Joined: Tue Feb 20, 2007 4:56 pm

Re: Shape Defined Via Equation?

Post by bone » Fri Apr 09, 2010 5:42 pm

In the end, you're planning on colliding things against a triangular mesh representation of your sphere, right? I guess I could see two ways of approaching this. One is to create a custom shape as you are suggesting, where I would assume you are planning to tessellate during the collision call?

The other way would be something like btBvhTriangleMeshShape without the Bvh. You would tessellate what you need and add triangles to the structure *before* the collision call. What would work as an advantage in my case is that it could be re-used several times while an object stayed in the same basic location.

GlitchEnzo
Posts: 6
Joined: Fri Apr 09, 2010 1:23 am

Re: Shape Defined Via Equation?

Post by GlitchEnzo » Fri Apr 09, 2010 10:22 pm

bone wrote:In the end, you're planning on colliding things against a triangular mesh representation of your sphere, right?
Actually no. That's what I'm trying (and failing) to explain. Since I have the equation that defines my shape then why do I have to worry about generating a triangular mesh, tessellating it, displacing it, etc? I should be able to just use that equation for all collision detection.

Look at the built-in sphere shape. You simply define a radius and collision detection is done by checking whether or not a point lies within that radius.

I'm essentially talking about the same thing except that I have a "sphere" with a variable radius. Instead of calling getRadius() with no parameters, you would pass in the point and the method will return the radius of the sphere at that vector. Does that make sense?

Maybe I should try creating some diagrams to help illustrate what I mean.

krux
Posts: 11
Joined: Tue Apr 06, 2010 7:25 pm

Re: Shape Defined Via Equation?

Post by krux » Fri Apr 09, 2010 11:10 pm

maybe you shoud just do it youself.
write a new type of shape, maybe something like BezierShape, and an collision detection algorithm. As far as I can see collisionShape has no child that fits into your description.

GlitchEnzo
Posts: 6
Joined: Fri Apr 09, 2010 1:23 am

Re: Shape Defined Via Equation?

Post by GlitchEnzo » Fri Apr 09, 2010 11:54 pm

I've always known that I would have to write this custom shape myself. I was mainly asking if it sounded feasible and would fit into the existing Bullet code, for the most part. I don't want to have to go rewrite big chucks just to get my own new shape in.

Plus there is always the chance that somebody has done something similar in the past and could give me pointers.

At this point I'm trying to figure out exactly what class my new shape should inherit from. I'm tempted to say btSphereShape, but it could potentially be concave (depending on displacement), so maybe I should inherit from btConcaveShape. Edit: I just saw that btConcaveShape objects are non-moving, so that is definitely the better option for me.

bone
Posts: 235
Joined: Tue Feb 20, 2007 4:56 pm

Re: Shape Defined Via Equation?

Post by bone » Sat Apr 10, 2010 8:49 pm

GlitchEnzo wrote:
bone wrote:In the end, you're planning on colliding things against a triangular mesh representation of your sphere, right?
Actually no. That's what I'm trying (and failing) to explain. Since I have the equation that defines my shape then why do I have to worry about generating a triangular mesh, tessellating it, displacing it, etc?
Ahh, okay. Now that I re-read your other posts, you only seem to need the sphere radius to figure out if a specific 3D point is inside it. I understand why you are proceeding with a custom shape now.

User avatar
Erwin Coumans
Site Admin
Posts: 4193
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Shape Defined Via Equation?

Post by Erwin Coumans » Sat Apr 10, 2010 9:39 pm

This should be possible by deriving your custom shape from btConcaveShape.

See more details in this posting: http://bulletphysics.org/Bullet/phpBB3/ ... 4954#18194
Thanks,
Erwin

GlitchEnzo
Posts: 6
Joined: Fri Apr 09, 2010 1:23 am

Re: Shape Defined Via Equation?

Post by GlitchEnzo » Sun Apr 11, 2010 8:45 pm

Thanks for the input.

One thing that I'm trying to confirm, which I can't seem to find defined anywhere:
Does the winding matter for the processTriangle() method on the callback object?

My guess is it doesn't matter, but I wanted to make sure before going down the wrong path.

User avatar
Erwin Coumans
Site Admin
Posts: 4193
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Shape Defined Via Equation?

Post by Erwin Coumans » Tue Apr 13, 2010 10:46 pm

GlitchEnzo wrote:Thanks for the input.

One thing that I'm trying to confirm, which I can't seem to find defined anywhere:
Does the winding matter for the processTriangle() method on the callback object?

My guess is it doesn't matter, but I wanted to make sure before going down the wrong path.
The winding doesn't matter. Bullet uses double-sided triangles.

Thanks,
Erwin

GlitchEnzo
Posts: 6
Joined: Fri Apr 09, 2010 1:23 am

Re: Shape Defined Via Equation?

Post by GlitchEnzo » Fri Apr 16, 2010 6:46 am

Thanks to your help, I was able to get it working.

I created a shape that I called btSphericalTerrainShape which inherits from btConcaveShape. It takes three parameters: the center of the terrain, the maximum radius (for its AABB), and a function pointer that is used to calculate the terrain vertex from a given position in space (usually a corner of the input AABB).

The function pointer passes 2 parameters: the position to evaluate and the center of the terrain, which should allow pretty much any algorithm to be used (potentially even heightmap texture reads or lookup table indexing).

For example, if you wanted to define the terrain as a simple sphere with a radius of 50, you would use the following method:

Code: Select all

btVector3 calculateTerrainVertex(const btVector3& position, const btVector3& center)
{
    return (position - center).normalized() * 50.0f;
}
If you wanted to define the terrain as a sphere with a radius of 50 that was offset by 8 octaves of Perlin Noise, you would use this method:

Code: Select all

btVector3 calculateTerrainVertex(const btVector3& position, const btVector3& center)
{
    btVector3 normalized = (position - center).normalized();
    double result = PerlinNoise::fBm(normalized.x(), normalized.y(), normalized.z(), 8);
    return normalized * btScalar(50.0f + result * 10.0);
}
These are the steps done in the processAllTriangles() method:

1) Calculate the 8 corners of the AABB
2) Calculate the midpoint of each of the 6 sides of the AABB
3) Calculate the position of the vertex on the terrain by calling the calculateTerrainVertex function pointer
4) Determine which of the corners of the AABB are colliding with the terrain by checking if the bounding box corners are closer to the center point than the respective terrain vertices
5) Find which 3 sides of the AABB are closest to the terrain in order to prevent extraneous triangle processing
6) Use the callback to process each triangle that collides with the AABB

You can read more details about the implementation and even download the source code to btSphericalTerrainShape at my blog:
http://recreationstudios.blogspot.com/2 ... ysics.html

I should note that although it works very well, there are still some rare cases where objects fall through the terrain. I'm still investigating the issue, so I'll post something here if I figure it out. I thought I saw something somewhere about specifying a "thickness" for terrain for cases such as this. I wonder if that is something I can potentially do with this spherical terrain.

ola
Posts: 169
Joined: Sun Jan 14, 2007 7:56 pm
Location: Norway
Contact:

Re: Shape Defined Via Equation?

Post by ola » Fri Apr 16, 2010 1:35 pm

Really nice!!!

I think it would help a bit if you try to make the triangles single-sided. Then your objects will be moved out to the front side as soon as they touch a triangle, which sortof makes the ground a bit "thicker".

It was discussed in this thread earlier:
http://bulletphysics.org/Bullet/phpBB3/ ... ide#p17945

Cheers,
Ola

Post Reply