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:
- First, we need to select an appropriate representation of the objects in the world.
- Second, we need an algorithm to determine if an object is visible.
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
- bounding sphere
- bounding ellipsoid
- bounding cylinder
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.
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:
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.
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.
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.
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:
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.
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.
----- END -----
©2019 - 2022 all rights reserved