Graphics Reference
In-Depth Information
We already mentioned antialiasing lines and polygons in Section 2.6. Antialiasing
algorithms are incorporated into image precision algorithms, such as the Warnock
algorithm, by a supersampling type approach. One subdivides to below a pixel and
averages the subpixel values.
Early antialiasing efforts in scan line algorithms ([Crow77a], [Catm78]) led to the
A-buffer algorithm that is used for antialiasing in Z-buffer algorithms. This algorithm
originated with [Carp84] and was subsequently improved by [AbWW85]. A pixel is
again assumed to have area, but rather than making complicated geometric clipping
computations on this area one associates a bitmask to the pixel (Carpenter used a 4
¥ 8 bitmask) and one does the clipping via Boolean operations on the bits, which is
much faster. The bitmasks are used in conjunction with a z-ordering of the polygon
pieces. An edge fill scan conversion algorithm is used to enter the edges of the polygon
pieces into the bitmask. The bitmasks are initialized to 0 and in the end have a certain
number of 1's. A simple counting of the number of 1's determines the percentage of
area of the polygon piece that is used to determine its contribution to the shade asso-
ciated to the pixel. See [MagT87], [WatW92], or [Roge98].
For antialiasing in ray tracing, see Section 10.2.
7.12
Conclusions
We finish the chapter with some observations on visible surface algorithms. To begin
with, note the importance of coherence. Basically, one thinks of a picture as consist-
ing of regions all of whose pixels have the same value. Once we have the value of a
pixel for a region, then we keep setting all adjacent pixels to the same value until we
run into one of those “few” boundaries between regions where a change takes place.
Below is a sampling of some different types of coherence guidelines when dealing
with linear polyhedra.
Edge coherence:
The visibility of an edge changes only when it crosses another edge.
Therefore, we can create a list of edge segments without intersections and need only check
one point per segment.
Face coherence:
A face is often small compared to the whole scene. Therefore, usually the
whole face is visible if one point of it is.
Object coherence:
The use of bounding objects is a form of coherence.
Depth coherence:
Different surfaces are usually well separated in depth.
Scan line coherence:
Segments visible on one line are likely to be visible on the next.
Frame coherence:
Images do not change much from frame to frame.
Geometric coherence:
The possible visible/invisible configurations at any vertex are
limited. For example, in a convex object the outside lines are visible (Figure 7.20(a)) as are
all the edges surrounding a vertex (Figure 7.20(b)).
