Billboard clouds for extreme model simplification

Xavier Décoret, Frédo Durand, François X. Sillion, Julie DorseyACM Trans. Graphics 2003 · DOI

TL;DR

This paper introduces "billboard clouds," a novel representation for simplifying complex 3D models for real-time rendering. By representing models as a collection of textured, semi-transparent planes, they achieve extreme simplification while preserving visual fidelity, particularly for silhouettes and parallax effects, bridging the gap between traditional mesh simplification and image-based impostors.

What Problem Does This Paper Address?

In computer graphics, rendering highly detailed 3D models in real-time is a significant challenge. As models become more complex, their polygon counts increase, demanding more computational resources. Traditional mesh simplification techniques, while effective for moderate simplification, struggle with "extreme simplification" (reducing models to a very small number of primitives). These methods often require mesh connectivity, have difficulty handling complex, non-manifold geometry (like trees), and can lead to unacceptable visual artifacts like cracks and loss of detail when pushed to their limits. Image-based impostors, on the other hand, are efficient but can suffer from the "cardboard-set look" when viewed up close. This paper addresses the need for a simplification method that can handle arbitrary complex models at extreme levels of detail, maintaining visual quality and offering a smooth transition between distant and near views.

Methods

The core of the paper is the introduction of the "billboard cloud" representation. This involves:

  • Plane-Based Simplification: Instead of polygons, models are simplified into a set of planar polygons (billboards) that are textured and can have transparency.
  • Error-Driven Optimization: An optimization approach is used to build the billboard cloud. A key aspect is defining an error metric (Euclidean distance) that a plane must satisfy for the primitives it represents.
  • Density Estimation in Plane Space: To select the best planes, the authors discretize "plane space" (parameterized by normal direction and distance from the origin) and compute a density for each region. This density considers both the "coverage" (how many faces a plane can represent within the error threshold) and a "penalty" for planes that might miss primitives in their vicinity, favoring quasi-tangent planes.
  • Greedy Plane Selection: A greedy algorithm iteratively selects the plane (or bin in plane space) with the highest density. This process continues until all faces of the original model are covered.
  • Adaptive Refinement: To ensure accuracy, the algorithm adaptively refines the selected bins in plane space to find the optimal plane that best represents the valid faces.
  • Texture Generation: Once planes are selected, textures (including color and potentially normal maps) are generated by projecting the original model's geometry onto these planes. Transparency is handled to avoid rendering unseen parts.

What's novel is the combination of an object-space error metric with a plane-space density estimation and a greedy selection strategy that doesn't rely on mesh connectivity, allowing it to handle arbitrary geometry. The penalty term for missed primitives is also a key innovation for robustness.

Datasets

The paper evaluates their technique on a variety of models, including:

  • Castle
  • Dinosaur
  • Tree
  • Madcat
  • Eiffel Tower

These are standard complex 3D models commonly used in computer graphics research. No new benchmarks or datasets were introduced.

Key Insights and Ideas

  • Decoupling Geometry and Appearance: Billboard clouds effectively separate the geometric complexity of a model from its visual appearance, allowing for significant simplification without losing visual richness.
  • Bridging the Gap: This method successfully bridges the gap between traditional mesh simplification (good for close-ups, struggles with extreme detail) and image-based impostors (efficient for distance, can look artificial up close).
  • Robustness to Arbitrary Geometry: The lack of reliance on mesh connectivity makes billboard clouds applicable to a much wider range of models, including those with complex, non-manifold structures.
  • Importance of "Near-Tangency": The penalty term for missed primitives is crucial for ensuring that selected planes are well-aligned with the model's surface, preventing artifacts and improving visual quality.
  • Error-Based Control: The ability to control simplification via an explicit error threshold provides predictable and controllable results.

Key Results

  • The method successfully simplifies complex models into a small number of billboards (e.g., fewer than 200 for the examples shown).
  • Visual quality is maintained, with precise silhouettes and noticeable parallax effects even at extreme simplification levels.
  • The number of billboards required scales roughly as $1/\epsilon$, where $\epsilon$ is the error bound, suggesting predictable behavior.
  • Rendering times for billboard clouds are competitive with or better than highly simplified meshes, especially when considering fill-rate limitations. For instance, a 60-plane billboard cloud was comparable to a 250-polygon mesh.
  • The technique can be extended to include normal maps for real-time relighting.

Limitations and Future Work

  • Cracks: The authors acknowledge that "cracks" between adjacent billboards are the only artifacts not explicitly prevented by the method, though they are significantly minimized. They are working on reducing these through triangle redistribution and plane re-optimization.
  • Computational Cost: The computation time for generating billboard clouds is noted as being too long for online simplification, suggesting it's primarily a pre-computation technique. They suggest that using a random subset of faces could accelerate density computation.
  • View-Dependent Simplification: The current approach is view-independent. The authors plan to extend it to view-dependent billboard clouds, which could enable even higher levels of simplification.
  • Further Error Metrics: Exploring different application-dependent error metrics is suggested.
  • Budget-Based Optimization: Developing a budget-based optimization method (finding the best billboard cloud for a given polygon/texture budget) is a promising future direction.
  • Shadows and Collision Detection: The planar nature of billboard clouds might lead to efficient approximations for soft shadows and collision detection.

Summary updated

BibTeX
@article{decoret2003billboard,
  author = {Xavier Décoret and Frédo Durand and François X. Sillion and Julie Dorsey},
  title = {{Billboard clouds for extreme model simplification}},
  journal = {ACM Trans. Graphics},
  year = {2003},
  doi = {10.1145/882262.882326},
}
Figure