Vertices Compression: Reduce a 3D Mesh's Vertex List by Merging Near-Duplicate Vertices

Question

## Problem

You are given a list of 3D vertices and a face list (triangles as index triples). Two vertices are considered duplicates if their Euclidean distance is below a threshold `eps`. Merge all duplicates into a single representative vertex, update the face list accordingly, and return the compressed mesh.

```python
def compress_vertices(
    vertices: list[tuple[float,float,float]],
    faces: list[tuple[int,int,int]],
    eps: float
) -> tuple[list[tuple[float,float,float]], list[tuple[int,int,int]]]:
    # Returns (new_vertices, new_faces)
    pass
```

**Example:**
```
vertices = [(0,0,0),(0,0,0.0001),(1,0,0),(1,0,0)]
faces    = [(0,1,2),(1,2,3)]
eps = 0.001
-> new_vertices = [(0,0,0), (1,0,0)]
   new_faces    = [(0,0,1), (0,1,1)]
```

## Follow-ups

1. What data structure would you use to make the O(n^2) pairwise comparison more efficient (e.g., k-d tree, spatial hash grid)?
2. After merging vertices, degenerate faces (all three indices the same) may appear. How do you detect and remove them?
3. How would you handle vertex attributes (normals, UVs) when merging -- average, take first, or discard?
4. What is weld tolerance and why is it important in game engine asset pipelines?

Vertices Compression: Reduce a 3D Mesh's Vertex List by Merging Near-Duplicate Vertices

Question Details

Full Details

Topics

More from Applied Intuition