Intersection Tests

Intro

These can be divided into many categories. The two basic issues are whether the intersection occurred and should the intersection points be calculated. This is non-trivial as operations such as division can be minimized or totally avoided.

Today's modern computer architecture has been optimized for floating point calculations and spread sheets so integer operations are now expensive but on the other hand you do no longer need to design your algorithms with integers to get performance. Why collision or intersection tests are important is that their design results in many orders of magnitude in computational performance.

The geometry that the computer allows us to do now is incredible and it has freed us from the millions of computations that are required. Most mathematics has not included or considered the existence of the computer so traditional geometry has been challenged and frankly dies. If like me you do not have a photographic memory, the ability to rotate 3D data sets in you head and project overlays in your mind then (and I believe Archimedes and others did have some of these attributes) you will appreciate what a computer can do. Geometry is not dead - it has only just begun. Neither is it a theory of projections nor even a vector calculus. I am quite happy to throw away the old especially if it is rigid, inefficient (in my time) and did I say rigid. And geometry is not topology and for all those really cool people who get to study topology and believe they are the cleverest of humans you make me puke. I have a couple of surprises for you.

Bounding Boxes

Let a bounding box be defined in n dimension space as an interval in each dimension.

Let bounding boxes be created from a set of points where each point is added to the box cause the interval in each dimension to be widened to include the new point in that dimension.

Let p be a point in n dimensional space that is to be included in the bounding box
i = 0..n-1
if p[i] < b[i].min
b[i].min = p[i]
if p[i] < b[i].max
b[i].max = p[i]

Bounding boxes take advantage of the use of Cartesian or rectangular coordinate systems. Since the data is already in this coordinate system a comparison test on the axes is used to test for inclusion.

The bounding boxes are often defined as two points in n dimensional space where one is the minimum point has all the minimum values and the other the maximum point having all the maximum values.

The bounding box has corners which are any combination of the maximum or minimum values of a component. For 2D there are two components each having a maximum or minimum value gives four possible combinations which correspond to the four corners of a square. In 3D there are 2^3=8 corner points.

Point and Box

Does a point intersect a box?

Let p be a point in n dimensional space
Let b be a bounding box
i = 0..n-1
if p[i] < b[i].min
return reject p
if p[i] > b[i].max
return reject p
return accept p

The issue of points on the boundary is interesting. I am not going to discuss this because often what you are trying to do will answer your question of whether to include the boundary or what issues will arise from such decisions which can be critical.

Box and Box

Let A and B be two bounding boxes
Iterate over the corner points of B
if a corner point of B is inside A then
return accept intersection
return reject intersection

Half Space sees Box

This is another box box intersection test. If a separating half space is found then the intersection is rejected.

Let A and B be two bounding boxes
Construct half spaces on the faces of B pointing away from B.
Iterate over the half spaces
if the current half space can see all of A's corner points
return reject intersection
return accept intersection

Simplex to Simplex

Separation Axis

Let n be the number of dimensions of the simplexes.
Let A and B be two simplexes. Does A have a separating half space which sees all of simplex B's points?

Let H_i be a half space opposite the point indexed by i. The half space points away from the simplex.
i=0..n-1
k=0
flag = true
while ((k<n)&flag)
if (H_i sees B.p_k)
k = k + 1
else
flag=false
if (flag==true)
return true
return false

If no axis of separation was found the simplexes are swapped in roles and now B tests if its half spaces can see all of point A's points.

Seeing a point involves calculating the normal and applying a dot product. Calculating the normal is done in constant time.

Line Segment Intersections

By iterating over simplex B's faces see if these intersect A's faces. For example consider the 2D case of two intersecting triangles A and B. If any line segment in B intersects a line segment in A then an intersection has occurred.

There are 3 line segments in B that can intersect with 3 line segments in A therefore there are 3*3=9 possible intersections to consider. Using a direct way of calculating the intersecting variable and testing if it is within bounds. The division operation is avoided by multiplying the equality 0≤t≤1 by t's denominator and then using comparison. If a segment in B intersects a line in A then a second test decides if the line segment in A intersects the line from B.

The worst case then is that 9 such comparisons are performed which suggests that this method is very efficient (no divisions necessary).

If simplex A is inside simplex B then this test will fail to notice this condition. By keeping the results of the intersection tests the cases where A is inside B or B is inside A may be found.

Consider the case where B is inside simplex A. Then all the intersection tests of segments of B are outside the ranges of the variable, but intersect line segments in A.

Similarly considering the case where A is inside B then all the intersection tests of segments of B are outside valid ranges but all intersect A within A's line segments.

TriangleTriangle Interval Overlap Method

This is a discussion on a triangle to triangle intersection algorithm presented in [1]. This tests if two triangles in 3D space intersect. And if so computes their line segment intersections.

Firstly test if the two triangles are co linear. While the book recommends deferring this test if you want robustness and I do then deferring this can result in a triangle collision being rejected. Consider a counter example where both are co linear and one is slightly above the other so a trivial rejection rejects it.

The basic rejection test creates a half space from one of the triangles and rejects intersection if all the points of the other triangle are on a particular side of the half space.

Similarly repeat for the other triangle.

Next is the tricky part. The intersection of two planes is generally a line. Calculate this using the cross product to find the direction. Then calculate a point on the line by setting t=0 substituting into the equations of the planes. This gives an extra degree of freedom. ie two equations and three unknowns which are a point on the line in 3D space when t=0. Solve this equation.

From here after references to the line refer to the line intersecting the two triangles planes.

To find one of the triangles intersection intervals with the line or more formally where it cuts the other triangle, project the triangles points to the other triangles plane. The projected triangle will cut the intersection line so find the t values where this cuts. Similarly do the other interval.

I have ignored the major details because I have not verified their equations. I am relatively confident that I could implement a computationally equivalent test. Their optimized version avoids calculating a point on the line which is equivalent to solving a 2 by 2 simultaneous equation so the saving is not that great. I have not tested this processor but division is not as expensive as it used to be and hence is no longer that costly (On sum intersection tests there was up to 30% saving avoiding division, but if this instruction is insignificant in the overall algorithm then optimizing on it could be more trouble than its worth.)

To make this point if the first tests reject 80-95% of the triangle intersections the optimizing on the rest of the algorithm becomes a pedantic issue. Unless a significant event such as computational cost explodes. This view of algorithms while disturbing is logically true - it just does not matter especially if the two methods are nearly computationally equivalent.

Plane to Plane

Although simple this needs to be made robust and calculated fast. The problem is given as solving two plane equations. Given two equations and three unknowns there is an extra degree of freedom.

a₀x + a₁y + a₂z = d₀
b₀x + b₁y + b₂z = d₁

If one of the dimensions has zero in both plane components then ignore that dimension and solve the equation as a 2 by 2 simultaneous equation. eg a_i=b_i.

Be prepared to have the algorithm return a result that it can not solve the problem. For example if the two lines or planes are parallel.

If there is no zero component in both normals then fix z and solve the 2 by 2 simultaneaous equation.

References

Tomas Akenine-Moller and Eric Haines (2002). Real-Time Rendering (Second Edition). ISBN 1-56881-182-9. Pages 590-594.

<TODO>

Bounding Boxes rewrite.
The bounding boxes are axis aligned bounding boxes. What about boxes from half spaces?
Point and Box is an axis aligned box
What about half spaces?
Box and Box is axis aligned.
Implement the triangle overlap algorithm.
Basic Vector Geometry has several intersection tests.
Do these need reorganizing, atleast under their own Line intersection tests category. Do not move them here because that page uses MathML and this page does not.