Visible-Surface Detection Methods

Deepika Sahu
CSE Department
 Korea University

Abstract
 Visible Surface detection methods or hidden surface
elimination methods is the process of identifying visible
parts of a scene from a viewpoint
 Numerous algorithms
• More memory - storage
• More processing time – execution time
• Only for special types of objects - constraints

 Deciding a method for a particular application

• Complexity of the scene
• Type of objects
• Available equipment
• Static or animated scene
 Korea University
Classification of Visible-Surface Detection
Algorithms
 Object-space methods vs. Image-space methods
• Object definition directly vs. their projected images
• Most visible-surface algorithms use image-space methods

 Object-space methods
• Compares objects and parts of objects to each other within
the scene definition to determine which surfaces are visible
 Image-space methods
• Point by point at each pixel position on the projection
plane
 Korea University

Back-Face Detection
 A fast and simple object-space method for locating
back faces of a polyhedron which is based on the inside
- outside tests

 A point (x,y,z) is “inside” a polygon surface with plane

parameters A, B, C, D if : Ax + By + Cz + D < 0.

 When an inside point is along the line of sight to the

surface, the polygon must be a back face and so cannot
be seen
 Korea University

Inside-outside test

 A point (x, y, z) is “inside” a surface with plane

parameters A, B, C, and D if
Ax  By  Cz  D  0
 The polygon is a back face if

V N  0 N = (A, B, C)
V

• V is a vector in the viewing direction from the eye(camera)

• N is the normal vector to a polygon surface
 Korea University

If the object descriptions have been converted to

projection coordinates and our viewing direction is
parallel to the viewing ZV axis, then

V= (0, 0, VZ) and V.N = VZC.

 Korea University

As Vz is negative (V’s direction is towards negative

Zv axis) we need to consider the sign of C.
In a right handed viewing system(viewing direction
along negative Zv axis) the polygon is back face if
C<0.
Also we can’t see any face whose normal Z compo
nent C=0.
In general we can say any polygon as back

face if its normal vector has Z-component value C≤0

Similarly in a left handed viewing system the poly
gon is back face if C≥0, when the viewing direction
is along the positive Zv axis.
 Korea University

Advantages

 For a single convex polyhedron such as pyramid,

this test identifies all the hidden surfaces in the
scene, since each surface is either completely
visible or completely hidden.
 If a scene contains only non-overlapping convex
polyhedra, then all hidden surfaces are identified
with the back face method
 Korea University

Limitation:
 It cannot be applicable for all situation like
overlapping case (if two objects are overlapping)
or two faces of a single object is overlapping.
 Back-face detection can be expected to eliminate
about half of the polygon surfaces in a scene
from further visibility tests.
Depth-Buffer Method
 Korea University

Characteristics
 Commonly used image-space approach
 Compares depths of each pixel on the projection plane
• Referred to as the z-buffer method
• Here the object depth is usually measured from the view plane
along the z-axis of a viewing system.
 Usually applied to scenes of polygonal surfaces
• Depth values can be computed very quickly
Yv
• Easy to implement S3
S2
S1

(x, y)
Xv

Zv
 Korea University

Depth Buffer & Refresh Buffer

 Two buffer areas are required
• Depth buffer
 Store depth values for each (x, y) position
 All positions are initialized to minimum depth
 Usually 0
• Refresh buffer
 Stores the intensity values for each position
 All positions are initialized to the background
intensity
Basic idea:
 Scan-convert each polygon, one at a time.
 Calculate the depth (z value) at each (X,Y) pixel
position.
 The calculated depth is compared to the value
previously stored in the depth buffer at that position.
 If the calculated depth is smaller than the value
stored in depth buffer, the new depth value is stored.
 Surface intensity at that position is determined and
placed in the same (X,Y) location in the refresh
buffer.
 Depth Buffer Method
• Depth-Buffer Algorithm
for all (x,y)
depthBuff(x,y) = 0.0, frameBuff(x,y)=backgndcolor
for each polygon P
for each position (x,y) on polygon P
calculate depth z
if z < depthBuff(x,y) then
depthBuff(x,y) =z
frameBuff(x,y)=surfColor(x,y)
Where backgndcolor is the value for the background intensity,
surfColor is the projected intensity value for the surface at pixel
position(x,y)
 Calculation of depth(Calculated from plane equation of each
surface)
• We know the equation of the plane is:
Ax + By + Cz + D =0
z= (-Ax –By – D) / C ---- (1)

If the depth of position (x,y) has been determined then

the depth of z` of the next position (x+1,y) along the
scan line is obtained as:
z` = (-A(x+1) –By – D ) / C ----(2)
z` = (-Ax – A - By – D) / C =[ (-Ax –By – D) / C ] –A/C
= z- A/C ---- (3)
• On each scan line, we start by calculating the depth on
a left edge of the polygon that intersects the scan line
depth values at each successive position across the scan
line are calculated by equation(3).
• We process the surface from the topmost scan line to
the bottom scan line.
• Suppose we move from scan line y to scan line y-1
Then we can calculate x positions down a left edge of
polygon as x`= x- 1/m where m is the slope.
 Cont..
• Depth values for y`= y-1 & x`=x-1/m is calculated as:
z` = (-A(x-1/m) –B(y-1) – D) / C ----(4)
z`= (-Ax –By – D) / C + (A/m +B)/C
z`= z + (A/m +B) / C ----(5)
If we process down a vertical edge, the slope is infinite
and the recursive calculation reduce to
z` = z + B/C
 Z-Buffering: Computing Z
• How do you compute the z value at a given pixel?
 Interpolate between vertices
z1
y1  y s
y1
z a  z1  z1  z 2 
za zb y1  y 2
ys
y1  y s
zb  z1  z1  z3 
zp
y2
y1  y3
z2

xb  x p
z p  zb  zb  z a 
xb  xa
y3
z3
Advantages:-
• Easy Implementation
• No sorting of surfaces
• Good rendering algorithm with polygon models

Limitations
• Suitable for opaque objects and not suitable for transparent
objects.
• Additional Buffer: Large number of memory is required as we
are using image space approach
• Aliasing effect
• Objects are processed in arbitrary order, so that a color can be
computed for a surface point that is alter replaced by a closer
surface
A-Buffer Method
 Characteristics Korea University

 This method represented an anti-aliased, area-averaged,

accumulation-buffer method.
 Accumulation buffer – buffer accumulates multiple pieces of


information for each pixel in addition to depth for transparency
or anti-aliasing (high-end movies, etc.).
 Each position in the A-buffer element stores:

• Depth Field : real-number. It stores a positive or negative

real number
• Surface Data Field (SDF): stores surface data or pointer
• When Depth >= 0:
 real-number is depth of a single surface at pixel
overlapping are the corresponding pixel.
 SDF is surface color and pixel coverage percentage
intensity & Other
depth ≥ 0
Info
 Korea University

Algorithm(1 / 2)

 Each position in the buffer can reference a linked list of

surfaces
• Several intensities can be considered at each pixel position
• Object edges can be antialiased

<Organization of an A-buffer pixel position : (a) single-surface overlap (b)

multiple-surface overlap>
 Korea University
Algorithm(2 / 2)
 If the depth field is positive
• The number at that position is the depth
• The intensity field stores the RGB

 If the depth field is negative

• Multiple-surface contributions to the pixel
• The intensity field stores a pointer to a linked list of surfaces
• Data for each surface in the linked list

The following information about each pixel is stored in accumulation buffer:

 RGB intensity components  Percent of area coverage

 Opacity parameters(percent of transparency)  Surface identifier

 Depth  Pointers to next surface
 Korea University

Algorithm
 For transparent surfaces and filter based anti-aliasing:
Algorithm (1): filling buffer
 at each pixel, maintain a pointer to a list of polygons

sorted by depth.
 when filling a pixel:
• if polygon is opaque and covers pixel, insert into list, removing all
polygons farther away
• if polygon is opaque and only partially covers pixel, insert into list,
but don’t remove farther polygons
Algorithm (2): rendering pixels
 at each pixel, traverse buffer using brightness values in polygons to fill.
 values are used for either for calculations involving transparency or for filter
ing for aliasing
 Korea University

Cont..

 The A-buffer can be constructed using methods

similar to depth buffer algorithm.
 Using the opacity factors and percentage of surface
overlaps, we can calculate the intensity of each pixel
as an average of the contributions from the
overlapping surfaces.
Scan-Line Method
 Korea University

Characteristics

 Extension of the scan-line algorithm for filling

polygon interiors
• For all polygons intersecting each scan line
 Processed from left to right
 Depth calculations for each overlapping surface
 The intensity of the nearest position is entered into the
refresh buffer
 Korea University

Tables for The Various Surfaces

 Edge table
• Coordinate endpoints for each line
• Slope of each line
• Pointers into the polygon table
 Identify the surfaces bounded by each line

 Polygon table
• Coefficients of the plane equation for each surface
• Intensity information for the surfaces
• Pointers into the edge table
 Korea University

Active List & Flag

 Active list
• Contain only edges across the current scan line
• Sorted in order of increasing x
 Flag for each surface
• Indicate whether inside or outside of the surface
• At the leftmost boundary of a surface
 The surface flag is turned on
• At the rightmost boundary of a surface
 The surface flag is turned off
 Example Korea University

 Active list for scan line 1

• Edge table
 AB, BC, EH, and FG B
E
yv F
 Between AB and BC, only A Scan line 1
S1 S2
Scan line 2
the flag for surface S1 is on
Scan line 3
H
 No depth calculations are C

D
G
necessary xv

 Intensity for surface S1 is entered into the refresh buffer.

 Similarly, between EH and FG, only the flag for S2 is on
 Korea University
Example(cont.)
 For scan line 2, 3
• AD, EH, BC, and FG
 Between AD and EH, only the flag for S1 is on
 Between EH and BC, the flags for both surfaces
are on
 Depth calculation is needed
 Intensities for S1 are loaded into the refresh
buffer until BC
• Take advantage of coherence
 Pass from one scan line to next
 Scan line 3 has the same active list as scan line 2
 Unnecessary to make depth calculations between
EH and BC
 Korea University

Coherence

 The properties of one part of a scene are related in

some way to other parts of a scene so that the
relationship can be used to reduce processing.
 It involves incremental calculations applied along
a single scan line or between successive scan lines.
 Korea University

Advantage of Coherence

 As we pass from scan line 2 to scan line 3, it has

the same active list as of scan line 2.
 Since no changes have occurred in line intersectio
ns depth calculations between EH and BC is not
needed.
 Korea University

Drawback
 Only if surfaces don’t cut through or otherwise cyclically
overlap each other
• If any kind of cyclic overlap is present
 Divide the surfaces
Depth-Sorting Method
 Korea University

Operations

 Image-space and object-space operations

• Sorting operations in both image and object-space
• The scan conversion of polygon surfaces in image-
space
 Basic functions
• Surfaces are sorted in order of decreasing depth
• Surfaces are scan-converted in order, starting with the
surface of greatest depth
 Korea University

Algorithm
 Referred to as the painter’s algorithm
• In creating an oil painting
 First paints the background colors
 The most distant objects are added
 Then the nearer objects, and so forth
 Finally, the foregrounds are painted over all objects
• Each layer of paint covers up the previous layer
 Process
• Sort surfaces according to their distance from the view plane
• The intensities for the farthest surface are then entered into the
refresh buffer
• Taking each succeeding surface in decreasing depth order, we
paint the surface intensities of the previously processed surfaces.
 Cont.. Korea University

 Assumptions: We are viewing along the z-directions.

 Surfaces are ordered on the first pass according to the
smallest z value on each surface.
 Surface S with the greatest depth is compared to the other
surfaces in the list to determine whether there are any
overlaps in depth.
 If no overlaps occurs, S is scan converted.
 Cont.. Korea University

 Figure shows two surface that overlap in the xy plane but

have no depth overlap.
 To decide S1 and S2 overlaps or not we have to compare
Zmin1 with Zmax2.
 In this case: Zmax2 > Zmin1 , so no overlap.
 If depth overlap occurs, additional comparisons are
necessary to reorder the surfaces.
 Overlapping Tests Korea University

 The following tests for each surface that overlaps with S to

ensure that no reordering of surfaces is necessary:
1. Test 1: The bounding rectangle in the xy plane for the
two surfaces do not overlap (1)
• We first check for overlap in the x direction, then we
check for overlap in y direction.
• If either of these directions show no overlap, the two
planes can’t obscure one another.
• Test 1 is passed, scan convert
S2 and then S1
• If test1 fails then go to test2
 Korea University

Overlapping Tests
 Test2 : Surface S is completely behind the overlapping
surface relative to the viewing position
• S1 is completely behind/inside the overlapping
surface S2 using plane equations:
Ax +By+Cz+D < 0
• Test2 is passed, scan convert S1 and then S2.
• If test2 fails, then go to test3.
 Korea University

Overlapping Tests
 Test 3: The overlapping surface is completely in front
of S relative to the viewing position
• S1 is not completely behind S2, so Test2 fails.
• Overlapping surface S2 is completely front/outside of S1,
so Test3 passed.
i.e. Ax+By+Cz+D > 0 – S1 is front/outside of S2
else Ax+By+Cz+D < 0 - S1 is behind/inside of S2
• Scan convert S1 and then S2
• If the test3 fails, then go to test4.
 Korea University

Overlapping Tests
 Test 4: The projections of the two surfaces onto the
viewplane do not overlap.
 To check this find whether Ei intersects Ej or not where Ei
and Ej are the edges of overlapping polygons.
 Korea University

Overlapping Tests

 If all the surfaces pass at least one of the tests, none of

them is behind S
• No reordering is then necessary and S is scan
converted
 If all the tests fail with a particular overlapping surface S`,
we interchange (reorder) the surfaces S and S` in the sorted
order.
 Korea University

Overlapping Test Examples

S’

xv xv
(1) (2)
zv zv

S S

S’ S’

xv xv
(3) (4)
zv zv
 Korea University

Surface Reordering

 If all four tests fail with S’

• Interchange surfaces S and S’ in the sorted list
• Repeat the tests for each surface that is reordered in
the list

S’’
S
S’ S S’

xv xv
<S  S’> <S  S’’, then S’’  S’>
zv zv
 Korea University

Drawback
 If two or more surfaces alternately obscure each
other
• Infinite loop
• Flag any surface that has been reordered to a farther
depth
 It can’t be moved again
• If an attempt to switch the surface a second time
 Divide it into two parts to eliminate the cyclic loop
 The original surface is then replaced by the two
new surfaces