网格内部点的可见多面体求解及O(n²)算法相关问询

Hey John, let's flesh out that O(n²) approach you're thinking of, and cover the key details to make it work reliably for your visible polyhedron problem.

First, let's clarify the core idea you started: the polyhedron formed by your moveable point P and a triangle T is actually a tetrahedron (4 vertices total). The missing piece here is checking whether this tetrahedron is blocked by other triangles in your mesh—aka, whether triangle T is actually visible from P without any obstructions.

Step-by-Step Implementation #

Here's how to turn your initial thought into a working algorithm:

• Pre-check: Verify point is inside the mesh
  Before doing any visibility checks, confirm P is inside your closed mesh (you mentioned this already). A quick way to do this is the ray-casting method: shoot a ray from P in any direction, count how many times it intersects mesh triangles. If the count is odd, P is inside.
• Iterate over every triangle T in the mesh
  For each triangle, determine if it's visible from P:
  1. Skip back-facing triangles (optional but efficient)
     If your mesh is closed and all triangles have consistent normals (e.g., pointing outward), calculate the dot product between the triangle's normal and the vector from T's centroid to P. If the dot product is negative, T is facing away from P—you can skip it immediately since it can't be visible.
  2. Cast a visibility ray
     Create a ray R starting at P and pointing toward T's centroid (or any point on T that's not an edge/vertex, to avoid edge cases).
  3. Check for obstructions
     Iterate over every other triangle T' in the mesh:
     • Calculate if ray R intersects T', and that the intersection point lies between P and T (not beyond T).
     • If any such T' exists, T is blocked—don't add it to your visible set.
     • If no obstructions are found, T is visible: add it to your visible polyhedron's face collection.
• Assemble the visible polyhedron
  The collection of all visible triangles forms the boundary of your visible polyhedron. If you need to output it as a full polyhedron (with vertices and faces), you can keep track of the unique vertices from these visible triangles, then map the faces to the reduced vertex array.

Critical Edge Cases to Handle #

• Floating-point precision issues
  Use a small epsilon value (like 1e-6) when checking ray-triangle intersections or distance comparisons. This avoids false positives from rays grazing edges/vertices or points being almost coplanar.
• Coplanar triangles
  If P lies in the same plane as T, or another triangle T' is coplanar with R, you'll need to handle this explicitly—usually by treating coplanar faces as occluding only if they lie between P and T.
• Self-occlusion
  Make sure you don't check intersections between T and itself (skip T' = T in your inner loop).

Optimizations for Larger Meshes #

If your mesh has thousands of triangles, the O(n²) approach might get slow. Here are two ways to speed it up without ditching the core logic:

• BVH (Bounding Volume Hierarchy)
  Precompute a hierarchical bounding box tree for your mesh. When checking ray intersections, traverse the BVH first to quickly eliminate entire groups of triangles that can't possibly intersect the ray. This drops the time complexity to roughly O(n log n).
• Distance sorting
  Sort triangles by their distance from P (closest first). For each triangle, once you find an occluding triangle, you can skip checking farther triangles—this won't change the worst-case complexity, but it can speed up real-world execution.

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