This article is currently only a proposal

The features or design guidelines described in this article are only a proposal made by one or some persons. It has not been evaluated or accepted by the core development team yet. Feel free to add your personal opinion about them or make counter proposals.

This page was created to document the collision detection algorithms used in The Mana World. After the algorithms are converted to C++ and added to the code base it is very difficult to verify the assumptions and math of the author. Therefore an explanation of the algorithms used is given below.

Circle-Segment with Circle

In order to determine if a circle-segment and a circle collide, we start with transforming the coordinates of the 2d space in such a way that the center of the circle-segment is located at the origin. The circle segment can then be defined by a radius R, a half-top angle alpha and a placement angle beta, as shown in diagram (1).

The circle can simply be defined by its center-point P and its radius R_P, where point P can be anywhere in the 2d space. See diagram (1) for an overview.

Diagram (1)

In order to determine if the circle-segment and the circle overlap, the x-y plane is divide in 6 Voronoi like regions. The regions are based on the vertexes O-A, O-B and the circular vertex A-B. They are shown in diagram (2).

Diagram (2)

For each region it is now determined what the pre-conditions for an overlap are, if P is in that region. If necessary, the pre-conditions for point P being in the region will be derived as well.

In the following text, a subscript x and y are used to indicate x and y coordinate of a point. If the coordinates considered are in a tranformed coordinate system, an extra indicator will be added. For example the x-coordinate of point A in the x₁-y₁ coordinate system is denoted as: A_x1

Region 1

Region 1 is highlighted in diagram (3), it includes the interior of the Circle-segment. For region 1, the coordinates for point P are transformed to coordinate system 1 (shown in diagram (4)).

Diagram(3) and (4)

The coordinates for point P in coordinate system 1 are:

P_x1 = P_x cos(beta-alpha) + P_y sin(beta-alpha)

P_y1 = P_y cos(beta-alpha) - P_x sin(beta-alpha)

Using goniometric relations this can be simplified to:

P_x1 = P_x {cos(alpha)cos(beta) + sin(alpha)sin(beta)} + P_y {-sin(alpha)cos(beta) + cos(alpha)sin(beta)}

P_y1 = P_y {cos(alpha)cos(beta) + sin(alpha)sin(beta)} - P_x {-sin(alpha)cos(beta) + cos(alpha)sin(beta)}

Point P is inside region 1 if

P_x1 >= 0 , P_y1 >= 0 and P_y1 <= P_x1 tan(2alpha)

The Circle-segment and the circle then intersect if

P_x² + P_x² <= (R + R_P)²

Region 2

Region 2 is highlighted in diagram (5). For this region no coordinate transformations are necessary.

Diagram (5)

If point P is inside region 2, the circle-segment and the circle can only intersect if point B is inside the circle.

(P_x - B_x)² + (P_y - B_y)² <= R_P²

The coordinates of point B are:

B_x = R cos(alpha + beta) = R {cos(alpha)cos(beta) - sin(alpha)sin(beta)}

B_y = R sin(alpha + beta) = R {sin(alpha)cos(beta) + cos(alpha)sin(beta)}

With the coordinates for B the condition can now be evaluated.

Region 3

Region 3 is highlighted in diagram (6). For this region no coordinate transformations are necessary.

Diagram (6)

Analogous to region 2, the circle-segment and the circle can only intersect if point A is inside the circle. The condition for this is:

(P_x - A_x)² + (P_y - A_y)² <= R_P²

The coordinates of point A are:

A_x = R cos(-alpha + beta) = R {cos(alpha)cos(beta) + sin(alpha)sin(beta)}

A_y = R sin(-alpha + beta) = R {-sin(alpha)cos(beta) + cos(alpha)sin(beta)}

With the coordinates for A the condition can now be evaluated.

Region 4

Region 4 is highlighted in diagram (7). For this region no coordinate transformations are necessary.

Diagram (7)

Analogous to regions 2 and 3, the circle-segment and the circle can only intersect if point O is inside the circle. The condition for this is:

P_x² + P_y² <= R_P²

Region 5

Region 5 is highlighted in diagram (8). For region 5, the coordinates for point P are transformed to coordinate system 2 (shown in diagram (9)).

Diagrams (8) and (9)

In the local coordinates the following conditions for P being in region 5, can be formulated:

P_x2 >= 0, P_x2 <= R and P_y2 >= 0

The condition for the circle-segment and the circle intersecting is:

P_y2 <= R_P

The coordinates for P in coordinate system 2 are given by:

P_x2 = (P_x - A_x)cos(alpha + beta + pi) + (P_y - A_y)sin(alpha + beta + pi)

P_y2 = (P_y - A_y)cos(alpha + beta + pi) - (P_x - A_x)sin(alpha + beta + pi)

Using the goniometric relations to handle the pi term first, the coordinates become:

P_x2 = -(P_x - A_x)cos(alpha + beta) + (P_y - A_y)sin(alpha + beta )

P_y2 = -(P_y - A_y)cos(alpha + beta) - (P_x - A_x)sin(alpha + beta )

Now using the goniometric relations to seperate alpha and beta:

P_x2 = -(P_x - A_x){cos(alpha)cos(beta) - sin(alpha)sin(beta)} + (P_y - A_y){sin(alpha)cos(beta) + cos(alpha)sin(beta)}

P_y2 = -(P_y - A_y){cos(alpha)cos(beta) - sin(alpha)sin(beta)} - (P_x - A_x){sin(alpha)cos(beta) + cos(alpha)sin(beta)}

With the coordinates for A, calculated for region 3, the conditions can now be evaluated.

Region 6

Region 6 is highlighted in diagram (10). For region 6, the coordinates for point P are transformed to coordinate system 3 (shown in diagram (11)).

Diagrams (10) and (11)

In the local coordinates the following conditions for P being in region 6, can be formulated:

P_x3 >= 0, P_x3 <= R and P_y3 >= 0

The condition for the circle-segment and the circle intersecting is:

P_y3 <= R_P

The coordinates for P in coordinate system 3 are given by:

P_x3 = P_xcos(alpha + beta) + P_ysin(alpha + beta)

P_y3 = P_ycos(alpha + beta) - P_xsin(alpha + beta)

Now using the goniometric relations to seperate alpha and beta:

P_x2 = P_x{cos(alpha)cos(beta) - sin(alpha)sin(beta)} + P_y{sin(alpha)cos(beta) + cos(alpha)sin(beta)}

P_y2 = P_y{cos(alpha)cos(beta) - sin(alpha)sin(beta)} - P_x{sin(alpha)cos(beta) + cos(alpha)sin(beta)}

The conditions can now be evaluated.