Visibility Determination

Subscribe Send me a message home page tags


#3D mathematics  #visibility determination  #computer graphics  #bounding volume 

This post is an introduction to visibility determination and it's a reading note of Chapter 8: Visibility Determination of the book Mathematics for 3D Game Programming and Computer Graphics.

Visibility determination is the process to determine which objects in the world are visible. This problem is solved from the opposite direction: the engine determines which parts of the world are definitely not visible and renders whatever is leftover.

There are two layers of the problems:

Bounding Volume Construction

The virtual representation of an object does not need to keep all the details but it needs to fully "cover" the object. Additionally, the representation needs to be simple so that we don't need to deal with complex algorithms when working with the volume. There are four common bounding volume types:

Bounding Box Construction

To construct a bounding box we can use the world axes or the natural axes of the object. The figure on the left uses the world axes and the figure on the right uses the natural axes of the object. As we can see the bounding box built from the natural axes of the object fits more tightly to the object.

bounding_box.png

To determine the natural axes of an data set, we can apply Principal Component Analysis.

Bounding Sphere Construction

To construct a bounding sphere, we can first determine the principal axis and calculate an estimate of the radius. However, the sphere constructed in this way may not cover all the data set. Iterative adjustments are required: we iterate all data points. If we find a point that is not covered by the current sphere, we can extend the sphere by adjusting the center and the radius. Note that the new sphere contains the old sphere. This process is illustrated by the figure below:

center_and_radius_adjustment.png

When this iterative process terminates, we will have a bounding sphere that covers all the data points. The final sphere constructed in this way may not be optimal in the sense that there may exist a smaller sphere that also covers all the data points. According to the book, determining the optimal bounding sphere is a tough problem.

Bounding Ellipsoid Construction

To construct a bounding ellipsoid, we need to scale the data so that the scaled version can be covered by a cube, which can be covered by a sphere. Then we transform the sphere back to the unscaled version and the resulting volume is an ellipsoid.

Bounding Cylinder Construction

A cylinder can be defined by two endpoints and a radius. The two endpoints also define a segment. We can choose a segment that is parallel to the principal axis of the data set and then use the iterative approach when constructing a bounding sphere to determine the radius and center of the top/bottom face of the cylinder.

bounding_cylinder.jpg

When appling the iterative approach, we can ignore the coordiate of the \(R\) axis in the object's natural coordinates.

Bounding Volume Test

The main idea is to check if the bounding volume of an object intersects with the view frustum. If there is no overlap, then we know the object is not visible.

Point Test

To understand the point test, let's take a look at a simple example. Suppose the bounding volume is a sphere with radius \(r\). If the distance between the center of the sphere and a plane of the frustum is larger than \(r\), then we know the sphere does not intersect with the plane. Recall that the plan of the frustum has a direction pointing inwards, thus the distance between the center and the frustum plane is a signed distance and if the (signed) distance between the center of the sphere and the frustum is less then \(-r\), then we know the sphere is on the outside of the frustum plane.

bounding_volume_test.png
signed_distance_to_frustum_plane.jpg

It's more complicated for ellipsoid because we lose the isotropic property of the sphere. However, the method is similar. In order to use the approach described in the previous section, we need to calculate an effective radius of the bounding ellipsoid. Note that the effective radius depends on the frustum plane:

effective_radius.png

Segment Test

To perform the bounding volume test for a cylinder, we need to use the segment test method. We first perform the point test against the two endpoints on the segment (the red part in the figure below). If both endpoints are invisible, then we know the cylinder is invisible; if both endpoints are visible, then we move to the next frustum plane. If one of them are visible, we clip the segment which removes the invisible part of the cylinder and then move to the next frustum plane.

segment_test.png

Tricks

Sometimes, the angle between two frustum planes is acute. In this case, even if the object is far away from the view frustum, it may still fail the visibility test (i.e. the distance between the center of the bounding volume and the frustum plane is larger than \(-r\) and the program would think the object is visible.). For such cases, we could add an artificial plane (the blue part in the figure below): the circle interacts with the two frustum planes (in orange) but not with the blue plane.

artificial_plane.png

----- END -----

Welcome to join reddit self-learning community.
Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png