Spatially-encoded far-field representations for interactive walkthroughs

Andrew T. Wilson, Ketan Mayer-Patel, Dinesh ManochaACM Multimedia 2001 · DOI

TL;DR

This paper introduces "spatially-encoded video" to represent distant geometry (far-fields) in interactive walkthroughs. By exploiting spatial coherence between these far-field representations, they achieve significant compression (up to 48x) and improve runtime performance, making complex 3D environments more accessible.

What Problem Does This Paper Address?

Visualizing and interacting with large, complex 3D environments (like CAD models, architectural designs, or flight simulators) is a significant challenge in computer graphics. These models often contain millions of polygons, making it impossible to render them at interactive frame rates (e.g., 30 frames per second) on current hardware. To overcome this, researchers have developed techniques to simplify or replace distant geometry with "impostors" – image-based representations. However, these impostors can consume vast amounts of memory and bandwidth, and naive compression methods don't fully leverage the inherent spatial relationships between them, leading to artifacts like popping or aliasing. The core problem this paper addresses is how to efficiently represent and render these impostors for interactive walkthroughs, minimizing storage and bandwidth while maintaining visual quality and interactivity.

Methods

The paper proposes a novel approach called "spatially-encoded video" for representing far-field impostors. This method extends traditional video compression techniques (like MPEG) by organizing frames not just along a temporal dimension, but across multiple spatial dimensions (position and orientation).

Here's a breakdown of their approach:

  • Model Decomposition: The 3D model is automatically partitioned into rectangular "cells," each enclosed by a "cull-box." Geometry within the cull-box is considered "near" and rendered directly, while geometry outside is approximated by far-field impostors.
  • Far-Field Generation: For each cell (and sub-cell), six impostors are generated, representing views from the six cardinal directions. These impostors can be either cached images or Textured Depth Meshes (TDMs).
  • Spatial Encoding: Instead of treating each impostor independently or linearly, they are organized in a multi-dimensional space. The core idea is to exploit spatial coherence: impostors in nearby cells or with similar orientations are related.
  • I-cells and B-cells: They adapt MPEG's I-frame (independent) and B-frame (bidirectionally predictive) concepts. "I-cells" contain impostors encoded as I-frames, while "B-cells" contain impostors encoded as B-frames, referencing impostors from nearby I-cells. This allows for significant compression by predicting changes between related impostors.
  • Auxiliary Index: A crucial component is an auxiliary index that explicitly stores the reference relationships between these spatially encoded impostors. This index enables random access, allowing the system to quickly retrieve and decode any required impostor without scanning through a linear stream.
  • Runtime System: A two-process system (rendering and prefetching) manages data loading and display. The prefetching process uses spatial coherence to load data asynchronously, ensuring it's available for the rendering process, which handles user interaction and displays geometry and decoded impostors using projective texture mapping.

Datasets

The paper evaluates their system on a complex CAD environment of a coal-fired power plant, comprising approximately 13.2 million triangles. This dataset is described as posing challenges for both geometric and image-based rendering due to its dense, repetitive structures (pipes) and high-frequency details. No new benchmarks are introduced; the focus is on demonstrating the effectiveness of their method on a challenging, real-world-like dataset.

Key Insights and Ideas

  • Spatial Coherence is Key: The most significant insight is that far-field impostors for adjacent cells or viewpoints are highly correlated. Traditional video compression exploits temporal coherence; this paper extends that to spatial coherence for static environments.
  • Beyond Linear Encoding: Traditional MPEG encoding is linear (temporal). By treating impostors as points in a multi-dimensional space (position + orientation), they unlock new compression opportunities.
  • Random Access is Crucial for Walkthroughs: Interactive walkthroughs require unpredictable navigation. The auxiliary index is vital for enabling efficient random access to compressed impostors, unlike standard video streams.
  • I/B-cell Structure for Compression: Adapting the I/B-frame concept to spatial cells provides a structured way to exploit redundancy, leading to substantial compression ratios.
  • Sub-linear Storage Growth: As more impostors are generated (higher sampling density), the storage cost per impostor decreases sub-linearly, making it feasible to add more samples to reduce artifacts without prohibitive storage penalties.

Key Results

  • Compression: The spatially-encoded video approach achieves an average compression ratio of approximately 48:1 on the power plant model, with individual ratios ranging from 2:1 to 303:1. This is a significant improvement over standard JPEG compression, which offers only 5-20x compression.
  • Runtime Performance: The system achieves interactive frame rates of 12-35 frames per second on a dual-processor PC with a Quadro2 graphics card. This is a substantial improvement over rendering only near geometry (which would be too slow for the full model) or using non-spatially encoded impostors.
  • Memory Efficiency: Spatial encoding significantly reduces the amount of data fetched from disk at runtime compared to non-spatially encoded impostors.
  • Image Fidelity: While some compression artifacts are inherent, the paper claims that spatial encoding offers little additional loss in image fidelity compared to non-spatially encoded methods, and helps reduce popping artifacts.

Limitations and Future Work

  • Compression Artifacts: The compression is not lossless, and artifacts can be more pronounced in areas with high-frequency components (e.g., detailed textures, fine geometric details). The paper notes that the compression ratio is content-dependent.
  • Depth Encoding: The current spatial encoding primarily targets the image portion of impostors. Compressing depth information efficiently remains an open challenge.
  • Popping Artifacts: While reduced, popping artifacts can still occur when switching between cells.
  • Future Work:
    • Improving the encoding algorithm to better handle high-frequency components and reduce artifacts.
  • Developing efficient depth encoding techniques.
  • Exploring blending techniques to further reduce popping artifacts.
  • Applying the spatial video approach to other synthetic environments (terrains, urban models) and dynamic datasets.
  • Investigating its use with real-world captured data like light-fields and lumigraphs.

Summary updated

BibTeX
@inproceedings{wilson2001spatially,
  author = {Andrew T. Wilson and Ketan Mayer-Patel and Dinesh Manocha},
  title = {{Spatially-encoded far-field representations for interactive walkthroughs}},
  booktitle = {ACM Multimedia},
  year = {2001},
  doi = {10.1145/500141.500193},
}

Loading related content...

Figure