IEEE Copyright Notice
© 199x (200x) IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.


Jiri Bittner, Peter Wonka and Michael Wimmer
Visibility Preprocessing in Urban Scenes using Line Space Subdivision
In Proceedings of Pacific Graphics (PG'01), pages 276-284, Tokyo, Japan, October 2001.

Abstract

We present an algorithm for visibility preprocessing of urban environments. The algorithm uses a subdivision of \emph{line space} to analytically calculate a conservative potentially visible set for a given region in the scene. We present a detailed evaluation of our method including a comparison to another recently published visibility preprocessing algorithm. To the best of our knowledge the proposed method is the first algorithm that scales to large scenes and efficiently handles large view cells.
Postscript (3.5 MB)

J. Bittner, V. Havran, and P. Slavik.
Hierarchical visibility culling with occlusion trees.
In Proceedings of Computer Graphics International '98 (CGI'98) , pages 207-219, Hannover, Germany, June 1998. IEEE, New York.

Abstract

In the scope of rendering complex models with high depth complexity, it is of great importance to design {\em output-sensitive} algorithms, i.e., algorithms with the time complexity proportional to the number of visible graphic primitives in the resulting image. In this paper an algorithm allowing efficient culling of the invisible portion of the rendered model is presented. Our approach uses a spatial hierarchy to represent the topology of the model. For a current viewpoint a set of polygonal {\em occluders} is determined that are used to build the {\em occlusion tree}. In the occlusion tree {\em occlusion volumes} of the selected occluders are merged. Visibility from the viewpoint is determined by processing the spatial hierarchy and classifying the visibility of its regions. In this process the occlusion tree is used to determine the viewpoint-to-region visibility efficiently. The algorithm is well-suited for complex models where large occluders are present.
Postscript (63 KB) | PDF (180 KB)

Jiri Bittner and Vlastimil Havran Exploiting Temporal and Spatial Coherence in Hierarchical Visibility Algorithms Proceedings of Spring Conference on Computer Graphics (SCCG'01), Budmerice, Slovakia, April 2001.

Abstract

We present a series of simple improvements that make use of temporal and spatial coherence in the scope of hierarchical visibility algorithms. The {\em hierarchy updating} avoids visibility tests of certain interior nodes of the hierarchy. The {\em visibility propagation} algorithm reuses information about visibility of neighbouring spatial regions. Finally, the {\em conservative hierarchy updating} avoids visibility tests of the hierarchy nodes that are expected to remain visible. We evaluate the presented methods in the context of hierarchical visibility culling using {\em occlusion trees}.
Postscript (200 KB)
V. Havran and J. Bittner.
LCTS: Ray Shooting using Longest Common Traversal Sequences
Computer Graphics Forum , Vol.19, No. 3, pages 59-70, (Proceedings of EG 2000, Interlaken, Switzerland).

Abstract

We describe two new techniques of ray shooting acceleration that exploit the traversal coherence of a spatial hierarchy. The first technique determines a sequence of adjacent leaf--cells of the hierarchy that is pierced by all rays contained within a certain convex shaft. This sequence is used to accelerate ray shooting for all remaining rays within the shaft. The second technique establishes a cut of the hierarchy that contains nodes where the hierarchy traversal can no longer be predetermined for all rays contained within a given shaft. This cut is used to initiate the traversal for all remaining rays contained in the shaft. The description of the methods is followed by results evaluated by their practical implementation.
Postscript (650 KB)
Jiri Bittner
Efficient Construction of Visibility Maps using Approximate Occlusion Sweep
To appear in Proceedings of SCCG '02. Budmerice, Slovakia. April 2002.

Abstract

We present an algorithm that efficiently constructs a visibility map for a given view of a polygonal scene. The view is represented by a BSP tree and the visibility map is obtained by postprocessing of that tree. The scene is organised in a kD-tree that is used to perform an approximate occlusion sweep. The occlusion sweep is interleaved with hierarchical visibility tests what results in expected output sensitive behaviour of the algorithm. We evaluate our implementation of the method on several scenes and demonstrate its application to discontinuity meshing.
PDF (1052 KB)
Vlastimil Havran and Jiri Bittner
On Improving Kd-Trees for Ray Shooting
In Journal of WSCG. Volume 10, No.1-3, February 2002.

Abstract

Efficient ray shooting algorithm is inherently required by many computer graphics algorithms, particularly in image synthesis. Practical ray shooting algorithms aiming at the average-case complexity use some underlying spatial data structure such as $kd$-tree. We show the new termination criteria algorithm that improves the space and time complexity of the $kd$-tree construction. It provides efficient ray-shooting queries and does not require any specific constants from a user. Further, we show how to apply a novel clipping algorithm into the $kd$-tree within construction phase in order to improve its properties.
PDF (240 KB)
Jiri Bittner and Jan Prikryl
Exact Regional Visibility using Line Space Partitioning
Technical Report TR-186-2-01-06, Institute of Computer Graphics and Algorithms, Vienna University of Technology, March 2001.

Abstract

We present a new technique for exact and output sensitive determination of visibility from a polygonal region in the plane. It uses hierarchical partitioning of {\em line space}, that provid es comprehensive description of visibility for a set of {\em occluders}. To the best of our knowledge, it is the first exact regional visibility algorithm suitable for visibility preprocessing of large scenes of unspecific type. We have evaluated the implementation on scenes with various visibility characteristics.
Postscript (798 KB)

J. Bittner.
Hierarchical techniques for visibility determination.
Postgraduate study report DS-005, Department of Computer Science and Engineering, CTU Prague, March 1999.

Abstract

This report introduces a new classification of visibility problems in three dimensions based on the dimension of the space of lines inherited in the particular problem. Three classes of visibility problems are studied --- visibility along a line, visibility from a point, and visibility from a region. For each class an algorithm extending previous results is presented. In particular the following algorithms are proposed: ray shooting using kD--tree with neighbour links (trees), hierarchical visibility culling with occlusion trees, and determination of visibility from a polygonal region using a regional occlusion tree. Finally, it is outlined how the results can be used in a unified framework for the hierarchical visibility determination.
Postscript (1.94 MB)

V. Havran and J. Bittner.
Rectilinear BSP trees for preferred ray sets.
In Proceedings of the SCCG'99 , Budmerice, April 1999.

Abstract

Rectilinear {\em Binary Space Partitioning} (BSP) trees are often used for solving various types of range searching problems including ray shooting. We propose a novel method for construction of rectilinear BSP trees for a preferred set of ray shooting queries. Particularly, we study ray sets formed by fixing either the direction or the origin of rays. We analyse and discuss the properties of constructed trees. Theoretical considerations are followed by results obtained from the practical implementation.
Postscript (2.75 MB)

V. Havran, T. Kopal, J. Bittner, and J. Zara.
Fast robust BSP tree traversal algorithm for ray tracing.
Journal of Graphics Tools , December 1998.

Abstract

An orthogonal BSP (binary space partitioning) tree is a commonly used spatial subdivision data structure for ray tracing acceleration. While the construction of a BSP tree takes a relatively short time, the efficiency of a traversal algorithm significantly influences the overall rendering time. We propose a new fast traversal algorithm based on statistical evaluation of all possible cases occurring during traversing a BSP tree. More frequent cases are handled simply, while less frequent ones are more computationally expensive. The proposed traversal algorithm handles all singularities correctly. The algorithm saves from 30% up to 50% of traversal time comparing with the commonly known Sung and Arvo algorithms.
HTML | Sample Code

V. Havran, J. Bittner, and J. Zara.
Ray tracing with rope trees.
In Proceedings of 13th Spring Conference on Computer Graphics , pages 130-139, Budmerice, 1998.

Abstract

In this paper an acceleration method for finding the nearest ray--object intersection for ray tracing purposes is presented. We use the concept of BSP trees enriched by {\em rope trees}. These are used to accelerate the traversal of the BSP tree. We give a comparison of experimental results between the technique based on BSP tree and uniform spatial subdivision.
Postscript (0.16 MB)

J. Bittner.
Global visibility.
In Proceedings of the CESCG '97, April 97, Bratislava and Vienna, pages 105-111, 1997.

Abstract

Solving the hidden surface removal is an essential problem since the early time of computer graphics. Most of the algorithms designed, like z-buffer or BSP-tree, are not output-sensitive what means, that their time complexity is proportional to the total number of graphic primitives in the model. However, in many complex models most their parts are invisible to an observer while located in certain region. This observation yields a search to design output-sensitive algorithms with the runtime complexity (time of rendering) proportional to the number of visible graphic primitives. We present one such algorithm together withe an empirical evidence of the asset of the visibility determination. The method presented in this paper subdivides the model into smaller parts (cells) continuing with determination of visibility relations between them. To describe potentially visible sets a tree data structure is used, where edges correspond to tight approximations of potentially visible frustums.
Postscript (0.23 MB)

J. Bittner.
Global visibility computations.
Master's thesis, Department of Computer Science and Engineering, Czech Technical University Prague, January 1997.

Abstract

This diploma thesis deals with the problem of visibility computations in object space. Description of restrictions in visibility for a bounded region of virtual environment can significantly improve the visualization process and brings many advantages in applications of virtual reality. The first chapter describes motivation of the research in the field of visibility preprocessing. It defines important features of different approaches of visibility computations and gives an overview about related work. Second chapter discusses the spatial subdivision, which is the first step necessary to perform to gain knowledge about the structure of the virtual environment. The visibility determination is the subject of third chapter. Several ways how to process visibility is shown there, each having different complexity in both theoretical and computational resources. Chapter number four documents one of the most important part of conservative visibility determination - polyhedra enumeration in arbitrary dimension. Chapter five is devoted to implementation issues as an extension to previous chapters. It describes the current implementation, points some troubles encountered in the practical usage of the theoretical concept. In sixth chapter an overview about empirical measurements of features of visibility computations is given. Finally, chapter seven contains summary information and drafts subjects of future work.
Postscript (1.88 MB)

M. Trefny and J. Bittner.
Global visibility.
In Proceedings of the WSCG'97, Pilsen, volume IV, pages 691-694, February 1997.

Abstract

Virtual reality applications such as architectural walkthroughs require a powerful graphics hardware to achieve interactive frame rates of rendering. Usual rendering algorithms like z-buffer or BSP-tree often spend significant time processing portions of model that are currently invisible to an observer. To describe restrictions in visibility, the visibility information can be precomputed and used to dramatically reduce amount of data to be processed during rendering. The model of a virtual environment is divided into cells using an algorithm of spatial subdivision. The spatial subdivision is represented by a graph structure. For each cell the cell-to-cell and cell-to-frustum visibility information is determined and stored in a tree data structure within that cell. However, widely used languages for description of model geometry, such as VRML, do not offer resources to describe the scene subdivision and to store the explicit visibility information along with the geometry. This article discusses some solutions that were chosen during the global visibility research project at the Department of Computer Science and Engineering at FEE CTU in Prague.
Postscript (54 KB)

J. Bittner.
Recnet - the speech recognition system.
Technical Report TR 96-160, Technical University of Delft, June 1996.

Abstract

Postscript (200 KB)