As of release 0.7.8 ClanLib comes with collision detection support. The collision system works by checking for intersections between line segments in line-loops surrounding the objects to collide. The advantage of this method over traditional methods, such as pixel based collision detection, is that the amount of data that needs to be worked with when checking for collisions and when doing transformations is very low. This enables besides fast collision testing also fast rotation and scaling of outline geometries.

Outlines can be generated from RGBA images by following the edge between transparent and opaque pixels.

To generate an outline from a RGBA image stored as image.png the following can be used:

CL_CollisionOutline outline("image.png");

Generating outlines from bitmaps can be quite expensive causing long load times. To battle that CL_CollisionOutline has a save function and constructors which can load saved outlines:

CL_CollisionOutline generated("image.png");
generated.save("image.out");

CL_CollisionOutline loaded("image.out");

Initially the contour following algorithm adds every pixel along the edge to the outline. This results in a lot of redundant information being added to the outline, but that can be optimized away without reducing the accuracy of the outline too much. The constructor which creates outlines from RGBA images takes a CL_OutlineAccuracy parameter which specifies how much to optimize the outline.

CL_CollisionOutline generated("image.png", accuracy_high);

The values for CL_CollisionAccuracy are:

• accuracy_raw
• accuracy_high
• accuracy_medium
• accuracy_low
• accuracy_poor

and their affects on generated outlines:


The optimization causes errors mostly in the round parts.

Once the collision outlines have been positioned using the transformation function (translate, rotate and scale) checking for a collision is simply a matter of calling the collide function. In a game one might have code similar to this:

if( outline.collide(outline2) )
{
	foo();
}

It's also possible to test if a point is inside an outline:

if( outline.point_inside( CL_Mouse::get_x(), CL_Mouse::get_y() )
{
	bar();
}

When checking for a collision a bounding circle test is always performed first. The way the collision testing is done can be adjusted by enabling/disabling completely inside test, and by enable/disable the object bounding box test.

When using the inside test, outlines completely inside another outline (or completely surrounding) will report a collision. If either of the objects being tested has inside_test set to true, the inside test will be done for both objects.

Object bounding box (obb) test uses a rotated tightly computed rectangle around the outline, and the obb is tested against the other obb first before any further (more detailed) collision detection tests are performed. For long narrow outlines an obb will give a lot more tighter bounds than a bounding circle, effectively eliminating further redundant checks.

outline.set_inside_test(true);
outline.set_obb_test(false);

The structure of the collision data structures is as follows:

CL_CollisionOutline
	CL_Contour(s)
		vector<CL_Pointf> points
		vector<CL_CollisionCircle> subcircles

Collisions are checked for by checking each line-segment forming the outline, against the line-segments of the other collision outline. If the number of line segments is big this will be somewhat slow. To eliminate checks that are sure to fail, the line-segments have been grouped into circles which hold a start and end index in the point array.

These sub-circles are collided against each other before any line-line intersection tests take place. Line-segments encapsulated in subcircles are only checked when two subcircles collides with each other. If the subcircles don't collide there is no chance that the line-segments inside them will collide either.

If an outline is created manually by adding a contour to the outline and points into the contour, it's necessary to calculate the subcircles and the radius before collision tests can be performed.

	CL_SurfaceOutline outline;

	CL_Contour contour;
	contour.points.push_back( CL_Pointf(0.0f,0.0f) );
	contour.points.push_back( CL_Pointf(0.0f,100.0f) );
	outline.get_contours().push_back(contour);
	outline.calculate_radius();
	outline.calculate_sub_circles();