## 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?

InterviewDB Question · Paris

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

phone

Question Details

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. Example: Follow-ups What data structure would you use to make the O(n^2) pairwise comparison more efficient (e.g., k-d tree, spatial hash grid)? After merging vertices, degenerate faces (all th…

Full Details

🔒

Unlock all Applied Intuition questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a applied intuition interview during the phone round.

It covers the following topics: Coding, Phone, Onsite, Matrix .

Topics

Coding Phone Onsite Matrix

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

Question Details

Full Details

About This Question

Topics

More Applied Intuition Interview Questions