Efficient Vertex Deduplication for glTF Geometry

When generating or processing 3D models for glTF via code, generating flat polygon lists often creates redundant vertex data that inflates buffer sizes and degrades GPU rendering efficiency. Vertex deduplication transforms unstructured soups of triangles into indexed primitive arrays (indices accessor in glTF) by merging vertices that share identical spatial and attribute data. This article explores the most efficient algorithms used in production pipelines to deduplicate vertices, ranging from spatial hash grids to cache-optimized linear sorting methods.

Hash-Based Quantization and Bucket Lookup

The standard approach for \(O(N)\) average-time complexity involves hashing vertex attributes into a lookup table. Because floating-point rounding errors often prevent exact bitwise equality, vertices must first be quantized.

  1. Grid Snapping (Quantization): Float coordinates for positions, normals, and texture coordinates are divided by an epsilon tolerance value (\(\epsilon\)) and converted to integer grid coordinates: \[\text{Cell} = \lfloor \text{Coordinate} / \epsilon \rfloor\]
  2. Hash Generation: The quantized integer components (X, Y, Z, plus UVs and normals) are combined using a fast, non-cryptographic hash function such as MurmurHash3 or FNV-1a.
  3. Collision and Neighbor Checking: A simple hash table merges vertices falling into the same grid cell. However, vertices placed closely across a cell boundary may be missed. To resolve this, the algorithm either snaps vertices unconditionally to the grid before hashing or queries the 26 neighboring cells within the spatial hash map for any vertex within the radial distance \(\epsilon\).

Sort-and-Sweep (Lexicographical Sorting)

For large geometries where memory fragmentation or dynamic allocation in hash maps is a bottleneck, sorting-based algorithms provide better cache coherence and deterministic \(O(N \log N)\) execution (or \(O(N)\) using Radix Sort).

  1. Axis Projection: Vertices are sorted along a primary axis (e.g., the X-axis) or mapped to a 1D Morton space-filling curve (Z-order).
  2. Linear Sweep: The algorithm iterates linearly through the sorted list. For each vertex, it compares subsequent vertices in the list.
  3. Early Termination: Because the list is ordered by coordinate value, the comparison loop terminates as soon as the difference along the primary axis exceeds \(\epsilon\). Vertices meeting the tolerance threshold across all additional attributes (normals, UVs, joints) are merged into a canonical index.

Space-Filling Curves (Morton / Hilbert Codes)

Using space-filling curves improves on standard 1D sorting by preserving 3D spatial locality in a single scalar dimension.

  1. Coordinate Encoding: Integer-quantized 3D coordinates are interleaved at the bit level to produce a 32-bit or 64-bit Morton code.
  2. Sorting: Vertices are sorted directly by their Morton key using an efficient Radix sort.
  3. Clustering: Because points that are close in 3D space are almost always adjacent or near-adjacent in Morton order, duplicate detection requires checking only a narrow sliding window of neighboring elements in the sorted array.

K-D Trees and Bounding Volume Hierarchies

When exact Euclidean distance (\(L_2\) norm) must be evaluated without cell-boundary artifacts and with variable tolerances, spatial partitioning trees (k-d trees or octrees) are utilized.

  • Query Process: Vertices are inserted incrementally or loaded in bulk. Before adding a vertex, a fixed-radius neighbor search (\(r \le \epsilon\)) queries the tree.
  • Trade-Off: While exact and versatile, tree-based methods incur pointer overhead and branch mispredictions, generally making them slower than flat spatial hash tables for web or real-time glTF compilation.

The Production Standard: Remap Tables

In performance-critical libraries such as meshoptimizer, deduplication is structured as an index remapping pipeline rather than repeated dynamic queries:

  1. Binary Bitwise Deduplication: First, a strict bitwise hash map checks for 100% byte-identical vertices across the entire vertex buffer structure. This executes at memory bandwidth speeds and handles non-floating point data cleanly.
  2. Attribute Tolerance Welding: A secondary pass uses quantized spatial buckets to merge vertices that differ within defined attribute tolerances.
  3. Index Buffer Generation: A compact remap array outputs the final glTF index buffer while compacting the original interleaved vertex attributes, preserving spatial locality to optimize the GPU's post-transform vertex cache (FIFO).