Binary-Space-Partitioned Images for Resolving Image-Based Visibility

Chi-Wing Fu , Tien-Tsin Wong , Wai-Shun Tong , Chi-Keung Tang , and Andrew J. Hanson
IEEE Transactions on Visualization and Computer Graphics, Vol. 10, No. 1, January-February 2004, pp. 58-71.

Abstract

We propose a novel 2D representation for 3D visibility sorting, the Binary-Space-Partitioned Image (BSPI), to accelerate real-time image-based rendering. BSPI is an efficient 2D realization of a 3D BSP tree, which is commonly used in computer graphics for time-critical visibility sorting. Since the overall structure of a BSP tree is encoded in a BSPI, traversing a BSPI is comparable to traversing the corresponding BSP tree. BSPI performs visibility sorting efficiently and accurately in the 2D image space, by warping the reference image triangle-by-triangle, instead of pixel-by-pixel. Multiple BSPIs can be combined to solve `disocclusion', when an occluded portion of the scene becomes visible at a novel viewpoint. Our method is highly automatic, including the tensor voting preprocessing step that generates candidate image partition lines for BSPIs, filters the noisy input data by rejecting outliers, and interpolates missing information. Our system has been applied to a variety of real data, including stereo, motion, and range images.

Video Presentation

The following presentation animation explains our algorithm with running examples and animations.
  1. Open 320 x 240 movie (MPEG1, 28.1MB)
  2. Open 720 x 480 movie (MPEG2, 87.3MB)

Download Paper

Related Publications

  1. " Triangle-based View Interpolation Without Depth Buffering",
    C. W. Fu, T. T. Wong and P. A. Heng,
    Journal of Graphics Tools, Vol. 3, No. 4, 1998, pp. 13-31.

  2. " Computing Visibility for Triangulated Panoramas",
    C. W. Fu, T. T. Wong and P. A. Heng,
    in Proceedings of the 10-th Eurographics Workshop on Rendering (Rendering Techniques'99), Granada, Spain, June 1999, pp. 169-182.