Last update: Aug. 28, 1998

Publications on Visibility computation by Gershon Elber et al., at Technion:

• Visibility as an Intrinsic Property of Geometric Models, 1998.
• Arbitrarily Precise Computation of Gauss Maps and Visibility Sets for Freeform Surfaces, 1995.

BibTeX references.

A list of visible polygons for each and every one of the polygons in the model is kept, as well as the light sources in the scene. A pre-processing, view-independent, visibility analysis stage is computed once for a given scene. This gives the Visibility Data Structure (VDS) that becomes part of the model.

Survey of Ray Tracing acceleration techniques

Bounding Volumes ('80-'86):

1. Bounding volumes are put around each object or set of objects in the scene:
   • spheres are the simplest for intersection tests.
2. Intersection Test in 2 phases:
   • (a) simple ray-volume intersection test;
   • (b) test with all the polygons inside the bounding volume.

3D Spatial Division ('80-'97):

1. Divide the space into "voxels" of varying sizes, e.g. through octrees or some hierarchical strategy.
2. Spatial division stops when a maximal level of division is achieved or until there is no more than one polygon in a voxel.

First-hit ('84):

1. Take the viewpoint into consideration by using a scanline algorithm, to sort out the 1st polygon being hit by each 1st ray.
2. This reduces the amount of computation time spent on the 1st-ray casting to the level of a simple scan-line computation step.

The Construction of the VDS

Visibility of a point p :

• Point p sees object O iff there exist a point q in O s.t. the line segment pq intersects no other object in the scene.

Visibility domain D in R³ :

• Point set s.t. every point in D sees the same set of objects in the scene.

Lemma 1 : Max. number of Visibility Domains (VD)

• Given an n-D scene (n = 2 or 3), with m objects (line segments in 2D, polygons in 3D), the disjoint partition of the space (R² or R³) into VD has at most O(m^4) such domains.

Proof: Given 2 polygons, P1 & P2, the space is divided into 3 VD: 1 s.t. only P1 is visible, 1 s.t. only P2 is visible and 1 where P1 & P2 are both visible. These 3 domains are delineated using a constant number of lines (in R²) or planes (in R³). Given m polygons, we are presented with O(m^2) such delineating lines or planes. O(m^2) such lines or planes can intersect in at most O(m^4) points or lines, respectively. In general position, each of the O(m^4) intersection is shared by 4 neighboring VD. Each such VD employs at least 1 intersection point or line. Hence, the number of VD is also bounded by O(m^4).

Invisibility of a polygon :

• Pj is invisible to Pi iff forall p in Pi and all q in Pj the line pq intersects some polygon Pk.
• This relation is symmetric.

Conservative VDS :

• Said of a VDS s.t. for every 2 visible polygons Pi & Pj in the scene, Pj is in ¥i and Pi is in ¥j ;
• where ¥i is the set of polygons visible from a polygon Pi, or a light source Li, that is, the VDS itself.

Approximate & Practical Construction of the VDS :

1. Assume all polygons are visible from each polygon Pi in the scene, i.e., the scene is fully conservative.
2. Remove hidden polygons from Pi's visibility data structure ¥i, using single polygons in the scene as occlusion buffers.
   • Thus, the solution will be approximate, as some polygons will be included in the VDS, although they are in fact occluded, but by several polygons simultaneously.
   • An exact solution for the VD of each polygon in the scene requires to test each such polygon against each of the O(m^4) domains, raising the total complexity even higher, which is practically intractable.

Two types of visibility testing are conducted during the VSD construction:

1. Reduction of the amount of polygons that are considered visible in each polygon's ¥i. This done in 2 main stages :
   • (a) Half-Space Visibility Test: this is a simple back-face culling stage. Its complexity is O(m^2), for m polygons in the scene.
   • (b) Volume Containment Test
2. Reduction of the amount of polygons in each ¥i of the light sources, in order to reduce the number of light rays which shall be casted (e.g. in ray tracing). This is done in a single stage of:
   • Volume Containment Test.

Volume Containment Test

1. Assume that all polygons are convex; otherwise decompose then into convex parts.
2. Approximate the VDS of each light source (point-like or directional), through the computation of shadow volumes. Only one projection point is necessary (i.e., the light source's origin or direction). This step has complexity O(m^2), for one light source. The visibility test of a polygon w/r to a light source is given according to the following lemma:
   • Lemma 2 : Visibility test of a polygon w/r to a light source
     • If all vertices of olygon Pk are within the shadow volume of some other polygon w/r to a light source, than Pk is invisible from that light source.
3. Approximate the VDS of each polygon. All points on the surface of a polygon must be considered. Compute the (convex) intersection of shadow volumes of all vertices of a polygon Pi w/r to another polygon Pj. This step has complexity O(m^3). Visibility can be tested according to the following lemma:
   • Lemma 3 : Visibility test of a polygon w/r to another polygon
     • Polygon Pk is invisible to Pi if there exist a polygon Pj s.t. Pk is contained in the Intersection of shadow volumes of Pi w/r to Pj.

• N.B.: A heurisitic, such as a cost function of the distance between polygon and their relative size, can be used to speed-up visibilty testing.

Applications using VDS

The higher the level of occlusion in the scene, the better one expect in the improvements in relative performance.

• Ray Tracing: Improvements of at least one order of magnitude were observed for simple scenes (between 10% to 40%). The use of the VDS permits to shoot less rays from light sources as well as less rays between polygons for (inter-)reflections simulation.
• Radiosity: Using the VDS reduces the amount of elements eac patch is considering on it's hemicube, before rendering.
• NC-machining: The VDS permits to more efficiently detect collisions with the moving tool.
• Computational Solid Geometry: The VDS becomes an intrinsic property of a modeled object, similar to color, texture, etc.

A symbolic method to compute the Gauss map is presented. It can be made arbitrarily precise for piecewise polynomials and rational surfaces.

Page created & maintained by Frederic Leymarie, 1998.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu