Probability Distribution of Index Distances in Normal Index Array for Normal Vector Compression

Deok‐Soo Kim, Youngsong Cho, Donguk Kim, Hyun KimLecture Notes in Computer Science 2003 · DOI · OpenAlex

Abstract

Efficient storage of 3D mesh data is critical for real-time graphics and large-scale geometric modeling. While connectivity and geometry compression are well-studied, normal vectors often represent a significant portion of the data overhead. This paper provides a mathematical foundation for normal vector compression by analyzing the probability distribution of "index distances" in a normal index array. By modeling the relationship between mesh topology—specifically using the Edgebreaker algorithm—and recurring normal indices, we demonstrate how relative indexing can significantly reduce bit-rates.

Introduction: The Normal Vector Overhead

In 3D computer graphics, a shape model is defined by its topology (connectivity), geometry (vertex positions), and normal vectors, which are essential for accurate surface lighting and shading. Normal vectors are surprisingly data-intensive, often consuming up to 50% of a total file size. To mitigate this, researchers employ clustering (grouping similar normals) and indexing.

A common strategy to optimize indexing is "mixed indexing," where instead of storing absolute index values, the system stores the "distance" (D) in the array since the last time a specific normal appeared. Because 3D meshes are typically traversed locally, these distances tend to be very small, requiring fewer bits to encode. However, until now, there has been a lack of a formal mathematical model to quantify this locality and its impact on compression efficiency.

Figure 1: Mesh topology and its corresponding normal index array with index distances (D) illustrated.

Methodology: Mapping Topology to Probability

The core of our approach is bridging the gap between mesh topology and statistical probability. We utilize the Edgebreaker algorithm—a standard for mesh connectivity compression—as our baseline traversal method. Edgebreaker outputs a string of five op-codes (C, R, E, S, L) representing different triangle configurations as it walks the mesh.

Geometric Categorization

We categorize the relationship between a "previous face" (PF) and a "current face" (CF) into three distinct types based on their connectivity during traversal:

  1. Edge-Connected: The faces share an edge. This is the most common scenario, occurring when the previous op-code is C, S, L, or R.
  2. Vertex-Connected: The faces share only a single vertex. This typically occurs during an 'E' op-code when a face is popped from a stack.
  3. Disconnected: The faces are separated by other triangles, often occurring at the start of new mesh components.
Figure 6: Geometric relationship between the previous face (PF) and current face (CF) during mesh traversal.

Probabilistic Modeling

By analyzing these connections, we derived equations to calculate the probability of specific index distances ($D=1, 2, 3, 4,$ or $\infty$) based on the known frequencies of Edgebreaker op-codes. For complex paths, such as vertex-connected cases, we utilized "majorizing probabilities" to estimate lower bounds for these occurrences. This allows for a predictable model of how many bits are required to encode the normal stream for any given mesh.

Results and Analysis

The mathematical model was validated using the "Cow Model," a classic benchmark in 3D geometry processing consisting of 17,412 normal indices. Our analysis revealed that 14,508 of these indices (83.32%) were recurring, confirming that the vast majority of normal data benefits from relative indexing.

Key findings from the mapping of Edgebreaker op-codes to index distances include:

  • D=3 was the most frequent recurring distance, appearing in approximately 32% of cases.
  • D=1 occurred roughly 18% of the time.
  • Distances of 4 or less accounted for approximately 66% of all indices in the analysis.

These results prove that the efficiency of normal vector compression is a direct byproduct of the mesh's topological traversal. If the traversal pattern (op-codes) is known, the recurrence of normal vectors becomes a mathematically predictable property rather than a heuristic observation.

Conclusion and Future Work

This paper formalizes the relationship between mesh connectivity and normal vector redundancy. By demonstrating that small index distances dominate the normal array, we provide a theoretical justification for the high compression ratios achieved by mixed indexing schemes.

Future work will address the assumption of unique normal vectors per vertex, as "creased" or "sharp" edges in industrial models often require multiple normals per vertex. Additionally, refining the probability allocation for complex vertex-connected paths (the 'E' op-code) remains an area for further mathematical optimization.

Summary updated

BibTeX
@inproceedings{kim2003probability,
  author = {Deok‐Soo Kim and Youngsong Cho and Donguk Kim and Hyun Kim},
  title = {{Probability Distribution of Index Distances in Normal Index Array for Normal Vector Compression}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2003},
  doi = {10.1007/3-540-44860-8\_92},
}
Figure