Ways to define a curve

Question

I'm trying to give shapes in my physics engine roundness/ curvature.

I am aware of various methods for mathematically defining curves; such as bezier-cruves, ellipses, etc. However I am not sure which methods would be most appropriate for use in my physics engine, because speed, feasibility of construction, and flexibility of each method must be considered. I want a system in which a user can easily form fairly complex curves, but still make the intersection calculations simple and fast.

My physics engine is also purely continuous, which means I must be able to calculate the time in which curves will collide with other curves and lines based on a constant linear/angular velocity.

• What techniques are there for mathematically defining a 2D curve?

• What are the advantages/disatvantages of each in terms of speed, flexibility, and simplicity of construction?

• Is the technique feasible for an engine where predictability of shape intersection is crucial?

Answer 1

The curves you describe looks like the Bézier curves.

Usually simpler shapes are used to simulate curves. It is without any doubt possible to test collision with a Bézier curve, but I don't know whether it is more efficient or not than converting it to a set of primitives (lines, rectangles, circles...).

I think it worth testing collisions using the both to see which one is the more efficient.

And even if the simple shapes are faster to test collision with, than using the Bézier curves equation directly, you could still use it in your game editor to create what you need and feel like with Adobe photoshop and convert the curves in a simpler shape set when exporting the level.

As for the circles; they are often used in collision detection system because the are straightforward to test collision with (distance from center, that's all you need).

Answer 2

If your physics engine works solely in terms of straight line segments and circles then the collision detection is as straightforward as you can possibly make it.

The standard technique for rendering Bézier curves is to use de Casteljau's algorithm to reduce them to a series of straight lines (bounding the error, aka distance from the original curve, to e.g. 0.5 pixels).

Put the two together and you have a tried and tested approach which allows you to define curves, is familiar to anyone who's ever worked with paths in Photoshop or the GIMP, and can then be transformed into a suitable structure for collision detection.