快速实现3D空间四面体-四面体相交检测的技术需求

Hey there! Sounds like you're chasing a fast, no-frills way to check if two 3D tetrahedrons intersect—with the rules that contact counts as intersecting, but shared full triangular faces don't. Let's break down an optimized approach that prioritizes speed while covering all edge cases.

Quick Rejection (Critical for Speed) #

First, we want to eliminate as many non-intersecting pairs as possible before doing heavy computations:

• AABB Overlap Check: Compute an Axis-Aligned Bounding Box for each tetrahedron first. If these boxes don't overlap at all, you can immediately return "no intersection." This is super fast to calculate (just min/max of x/y/z coordinates for all vertices) and filters out most non-overlapping cases.
• Separating Axis Theorem (SAT) Quick Pass: If the AABBs overlap, run a simplified SAT check. For tetrahedrons, the potential separating axes are:
  • The face normals of both tetrahedrons (4 per tetrahedron, 8 total)
  • The cross products of every edge from the first tetrahedron with every edge from the second (6 edges each, 36 total—skip these initially and only run them if face normals don't find a separating axis to balance speed and accuracy)
    For each axis, project all vertices of both tetrahedrons onto the axis. If the projected intervals don't overlap, the tetrahedrons are separated—return "no intersection."

Precise Intersection Tests #

If quick rejection doesn't rule out intersection, move to these checks:

• Vertex-in-Tetrahedron Check: For every vertex of tetrahedron V0, check if it lies inside or on the surface of tetrahedron V1 (and vice versa):
  1. Precompute the plane equation (ax + by + cz + d = 0) for each face of the target tetrahedron.
  2. For a test vertex, compute the signed distance to each plane. If all distances are non-negative/non-positive (matching face orientation) OR exactly one distance is zero (vertex lies on a face), the vertex is inside/on the tetrahedron.
  3. If any vertex passes this check, return "intersecting"—unless the vertex lies on a face that is a full shared face between the two tetrahedrons (handled below).
• Edge-Face Intersection Check: For every edge of V0, check if it intersects any face of V1 (and vice versa). A valid intersection here means the edge crosses through the face (not just touching at a vertex or lying entirely on the face, unless it's a partial touch not part of a full shared face).

Edge Case Handling #

Stick to your specific rules with these checks:

• Contact Counts as Intersecting: If a vertex touches a face (but not part of a shared full face), or an edge touches a vertex/edge of the other tetrahedron, return "intersecting."
• Shared Full Triangular Faces Don't Count: After detecting a potential intersection, verify if the two tetrahedrons share an entire triangular face:
  1. For each face of V0, check if all three vertices match (in any order) a face of V1.
  2. If such a face exists, return "no intersection" regardless of the tetrahedrons' positions relative to the face.

Optimization Tips #

• Precompute & Cache: Calculate and store each tetrahedron's face normals, plane equations, and AABB once when the tetrahedron is created, instead of recalculating them every time you run an intersection check. This saves tons of repeated computation.
• Early Termination: As soon as you find any valid intersection (vertex inside, edge crossing face), return "intersecting" immediately—no need to run the rest of the checks.

内容的提问来源于stack exchange，提问作者Spektre