In the three-dimensional space, the intersection algorithm of the straight line and triangles is the most basic algorithm for collision detection and selection operations in computer three-dimensional graphics.
DirectX SDK is in the PICK example, providing the original code, which has different understandings for this code.
Here is the way to use the affine coordinate system to explain it.
basic knowledge
Spatial plane equation, n * p D = 0; or n * p = D,
Here * is a vector of the point, n is a plane method, and P is any point on the plane.
And D represents the distance from the origin to the plane, or the distance from the plane to the origin, pay attention to this distance is vector
Point to space plane
For n * p = d, D is from the origin to the plane
N * p0-d is the distance from the plane.
To solve the problem of line segments and space triangles, solve two steps
first step
Calculate the plane intersection of line segments and space triangles
The two endpoints of the calculated line segment to the plane, if the symbol is the same, indicating that the same test is located, inevitably not intersecting
Depending on the distance, you can get 0 distances, this point is the intersection.
In the second step, whether the intersection is in the interior of the space triangle
At this time, you can calculate the method of decomposition of affine coordinate system.
First introduce what is the affine coordinate system
We are more familiar with the orthogonal coordinate system of Cartesi, and the two coordinates are vertical.
Among the affine coordinate systems, the two coordinate axes are not perpendicular, as long as they are not parallel, they can form an affine coordinate system.
Obviously, the orthogonal coordinate system of Cartesi is a special case of the affine coordinate system.
Whether it is orthogonal or affine coordinate system, there are the following facts:
Assuming that the two coordinate axes is X and Y
One point P in space can be represented as a p = o x * x y * y
O is the origin, X and Y is the coordinate of this coordinate system.
Any point in space, according to this coordinate system, the value of X and Y is unique
For a point on the space, it has been parallel lines of parallel coordinate axes, and the distance between the intersection is the coefficient of the origin.
For orthogonal coordinate system, the parallel line and the coordinate axis are enclosed in a rectangle.
For the affine coordinate system, the parallel line and the coordinate axis are not a parallelogram
If we regard a vertex of the triangle as the origin of the affine coordinate system, two sides from this vertex as the two coordinate axes of the affine coordinate system, then any point in the plane is in this The coordinate value under the affine coordinate system can distinguish between the point and this triangle. Assume that the coordinates are U and V, then u> 0, V> 0 is indicated, point in the first quadrant
U V <= 1 represents the interior of the triangle
If 0 <= u <= 1 and 0 <= V <= 1 represents the inside of parallelogram composed of two edges
According to finding a principle, we can determine if the point is in the triangle or parallel.
Specific calculation
The three vertices of the triangle are P1, P2, P3, the same plane PO
Two edge vectors are u = p2-p1 v = p3-p1
Point PO '= PO - P1 in this coordinate system
Solution This equation can get the coordinates under the affine coordinate system:
PO '= U * U V * V
Because the point is three-dimensional, as long as U and V are numbered, the two coordinate components of the three-dimensional coordinate are removed can be removed.
In fact, we only need to find the three coordinate components of the flat method, the two coordinate components of the absolute value are calculated.
In fact, this is to solve a binary equation.
The specific algorithm does not need to be given
