Curved Shapes and Edge Shapes?

Topics: Developer Forum, User Forum
Sep 2, 2010 at 5:57 PM

I've had an idea for a while about arbitrary curved shapes and curved edge shapes, but I'm not really an expert on implementing low level things in a physics engine, so I figured I'd throw the idea out there and maybe someone with more expertise could comment on the feasibility of it or a possible implementation. 

Basically the problem I am having is the same problem that we had with circle shapes in FP2, which is that we were approximating a curved surface by tessellating the surface into a polygon shape. This caused subtle problems because the circles would sometimes "hop" or otherwise not interact smoothly with other bodies. We solved this problem for circle shapes as a special case, but we still have the same issue when it comes to arbitrary curved surfaces, even when it's a circle shape interacting with the curved surface.

So, for example, this would be very beneficial in a pin-ball game. In a pin-ball game, you have a circle shape (the ball), and you want that physics body to VERY smoothly interact with curved parts of the pin-ball table. For example, if you hit the ball and it goes into a curved ramp, it should either slide or roll through the ramp and not bump off a "corner" edge and stall mid-way due to the tessellation of the ramp shape (or edge shape). The amount of tessellation needed to get acceptably smooth interactions in this scenario is very high and hurts performance.

Now, to be clear, my idea is still an approximation of curved shapes (or edge shapes). The basic idea is that, instead of just tessellating a Curve into a polygon shape, we also keep the Curve information and use it to make adjustments to collisions, contact points, penetration correction forces, friction forces, etc.. based on the curve. The engine detects collisions/penetrations in the same way it did before, with the tessellated shape.

So, here are a few pieces I think we'll need:

First, in order to keep the Curve calculations simple, you would need to make a few assumptions/requirements and you would need to pick your tessellation points intelligently.

  • Each edge in the tessellated shape should represent a portion of the Curve. The endpoints of the edge should be precisely on the curve itself.
  • There should be no control points on the curve between the two endpoints of an edge in the tessellated shape. They can be exactly on the end-points of the edge, but not between them. This means the number of control points on the curve represents the minimum number of vertices in the tessellated shape/edge. There will always be one vertex per control point.
  • Curved shapes should meet the same requirements as a polygon shape. For example, it needs to be convex and not concave. 
  • Perhaps this won't be necessary, but it might make it simpler if we assumed that the curve does not intersect the edge between the endpoints. If it does, we should break the edge into two edges, split at the point of intersection. I think this is only an issue for curved edge shapes, since the convex requirement for curved shapes would probably make this impossible.

 

So, given these assumptions/requirements are met, we essentially have a tessellated polygon shape that the engine processes like normal, however the engine would make some adjustments to the collision response based on the curve. We would need to make an adjustment to the contact point (find the closest point on the curve to the contact point on the tessellated edge), then an adjustment to the contact normal, given the contact point on the curve. These adjustments would need to be taken into account in any collision response calculations that would normally take place.

There are a couple of problems I've identified, which I'm unsure of how best to solve.

First of all, the curve will be entirely on one side or the other of each polygon edge. For curved shapes, the curve should always be on the "outside" of the shape (due to the convex requirement), but for curved edge shapes it could be on either side. This has a few consequences:

  • Collisions from the side that the curve is on will come late. The second shape would have to pass through the curve line to get to the tessellated polygon edge in order to register a collision. If the curve separates too much from the tessellation edge, and the second shape is moving in parallel to the tessellation edge, a collision may not be reported at all, when in fact there should have been one. For the most part I think this is acceptable, since you can reduce this by increasing the amount of tessellation. Again, this is still an approximation.
  • The other problem with the scenario above is that as soon as you apply the collision response, the two bodies will no longer be "touching" according to the engine (the tessellated shape doesn't touch, but the curved shape does). This might make it impossible for bodies to "settle" into the resting state, because the engine constantly separates the shapes, then allows them to collide again and again. The shapes would probably have a visible jitter during this process. I'm not sure the best way to handle this is. I think it would be acceptable to detect the first collision using just the polygon shape, and then go into a sort of "curve-touch" mode so the bodies don't separate until their curved edges are no longer touching. This might allow for smoother sliding along the curved edge.
  • For curved edge shapes, we have the same problems as above, but we also have an additional problem: If a second body travels towards the edge shape from the side that doesn't have curve, then a collision will be reported early. In this case, the engine would have to cancel the collision until the second body collides with the curve itself.

 

 

 

Coordinator
Sep 2, 2010 at 7:45 PM

FPE 3.1 will support shapes that can contain adjacency information on polygon segments (edges). More info will be released once I've implemented it. (in this week)

Coordinator
Sep 2, 2010 at 9:02 PM

@JeroMiya You might want to post this to the Box2D forums and see what people think.  Erin (Box2D creator) might have some good feedback on this.

@genbox, looking forward to the edge adjacency stuff.

Coordinator
Sep 3, 2010 at 12:04 PM

@JeroMiya, I noticed you reposted this to the Box2D.XNA forums.

FYI: When I said you should post it to the Box2D forums, I meant here:  http://www.box2d.org/forum/index.php  This is the actual "home" of the project. Erin Catto is the developer of the engine.

 

-Jeff

Sep 3, 2010 at 4:12 PM

Done:

http://www.box2d.org/forum/viewtopic.php?f=4&t=5537

Coordinator
Sep 3, 2010 at 7:08 PM

fyi, in case you didn't see, Erin responded.