四面体空间雕刻：表面网格生成算法疑问及伪代码请求

Hey there! I’ve worked through similar tetrahedral-to-surface mesh extraction problems before, so let’s break this down clearly for you, aligned with the ICCV 2013 paper you’re studying. We’ll cover how to cull internal triangles, handle inside/outside detection, and wrap it up with actionable pseudocode.

Core Idea Recap #

First, let's ground this in the paper's logic: The ray-casting approach helps distinguish between faces that lie on the object's outer surface (between the object and air) versus internal faces (sandwiched between two tetrahedrons). The end goal is to isolate only the faces that form the visible boundary of your target mesh.

Step 1: Culling Internal vs. Candidate Surface Faces #

The fastest initial filter relies on face adjacency:

• A triangular face shared by two tetrahedrons is an internal face (it’s entirely inside the object, so we discard it immediately).
• A face that belongs to only one tetrahedron is a candidate surface face—we then use ray casting to confirm it’s not part of an enclosed internal cavity.

Step 2: Inside/Outside Detection for Candidate Faces #

To verify if a candidate face is part of the outer surface, we use a ray-casting test from a point known to be outside the entire tetrahedral mesh (e.g., far beyond its bounding box):

1. Cast a ray from this external point through the centroid of the candidate face.
2. Count how many times the ray intersects with other tetrahedron faces along its path.
3. Apply the even-odd rule:
   • If the intersection count is even, the face is on the outer surface (the ray travels from outside, hits this face, and doesn’t cross any other boundaries).
   • If the count is odd, the face is inside a cavity (the ray crosses multiple boundaries to reach it), so we discard it.

Alternatively, you can complement this with face orientation checks: A valid outer surface face will have its normal pointing away from the centroid of its parent tetrahedron.

Pseudocode Implementation #

Here’s a structured, paper-aligned pseudocode that combines adjacency filtering and ray-casting verification:

# Input: List of tetrahedrons (each with 4 triangular faces + 4 vertices)
# Output: List of valid outer surface triangle faces

1. # First, map face occurrences to identify shared internal faces
   face_occurrence_map = {}  # Key: sorted vertex indices of a face, Value: number of tetrahedrons using it
2. For each tetrahedron in tetrahedrons:
    a. For each face in tetrahedron.faces:
        i. # Create a unique key for the face (sort vertices to handle reverse-order duplicates)
           face_key = sorted(face.vertex_indices)
        ii. If face_key in face_occurrence_map:
               face_occurrence_map[face_key] += 1
            Else:
               face_occurrence_map[face_key] = 1

3. # Collect candidate surface faces (only used by one tetrahedron)
   candidate_surface_faces = []
   For each tetrahedron in tetrahedrons:
    a. For each face in tetrahedron.faces:
        i. face_key = sorted(face.vertex_indices)
        ii. If face_occurrence_map[face_key] == 1:
               candidate_surface_faces.append(face)

4. # Define a point guaranteed to be outside the entire mesh
   mesh_bbox = compute_bounding_box(tetrahedrons)
   external_point = (mesh_bbox.max_x + 20, mesh_bbox.max_y + 20, mesh_bbox.max_z + 20)

5. # Validate candidates with ray casting
   final_surface_faces = []
   For each face in candidate_surface_faces:
    a. face_centroid = average(face.vertex1, face.vertex2, face.vertex3)
    b. # Create ray from external point to face centroid
       ray_origin = external_point
       ray_direction = normalize(face_centroid - external_point)
    c. intersection_count = 0
    d. For each tetrahedron in tetrahedrons:
        i. For each tetra_face in tetrahedron.faces:
            ii. # Skip checking the candidate face itself
               if tetra_face == face:
                   continue
            iii. # Check if ray intersects this tetrahedron face
               if ray_intersects_face(ray_origin, ray_direction, tetra_face):
                   intersection_count += 1
    e. # Apply even-odd rule to confirm outer surface
       if intersection_count % 2 == 0:
           final_surface_faces.append(face)

6. # Output the final surface mesh
   return final_surface_faces

Optimization Notes #

• To speed up ray intersection checks, use a spatial partition (like a grid or octree) to only test tetrahedrons along the ray’s path, instead of iterating all tetrahedrons.
• For watertight tetrahedral meshes, the adjacency check alone may be sufficient—ray casting is mainly needed to handle non-watertight or cavity-containing meshes.

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