VISIBLE SURFACE

DETECTION

Reference link
The problem of Visibility – Occlusion.
Problem Definition:
Given a set of 3-D surfaces to be
projected onto a 2-D screen, obtain the
nearest surface corresponding to any point
on the screen.

Two types of methods used:

• Object-space methods (Continuous):

Compares parts of objects to each other
to determine which surfaces should be labeled
as visible (use of bounding boxes, and check
limits along each direction).
 Order the surfaces being drawn, such
that it provides the correct impression of
depth variations and positions.

Image Space methods (discrete):

Visibility is decided point by point at

each pixel position on the projection plane.
Screen resolution can be a limitation.

Hidden Surface – (a) Surface for rendering

or
(b) Line drawing
Coherence properties:
• Object Coherence – If one object is entirely
separate from another, do not compare.

• Face Coherence – smooth variations across a

face; incrementally modify.

• Edge Coherence – Visibility changes if a

edge crosses behind a visible face.

• Implied edge coherence – Line of

intersection of a planar face penetrating
another, can be obtained from two points on
the intersection.
• Scanline coherence – Successive lines have
similar spans.

• Area Coherence – Span of adjacent group

of pixels is often covered by the same
visible face.

• Depth Coherence – Use difference equation

to estimate depths of nearby points on the
same surface.

• Frame Coherence – Pictures of two

successive frames of an animation
sequence are quite similar (small changes
in object and viewpoint).
 Different Visible Surface
Detection Methods:

• Back-face Detection
• Depth (Z) buffer method
• Scan-line method
• Depth-sorting method
• Area-subdivision method
• Octree methods
• A-buffer method
• BSP Trees
• Ray casting method

Visible surface techniques are 3D

versions of sorting algorithms
– basically compare depth.
 Back face Culling or removal
A Polygon (in 3D) is a back face if:
V.N > 0.

Let V = (0, 0, Vz) and N = Ai + Bj + Ck.

Then V.N = Vz.C;

Let Vz be +ve (view along +ve Z-direction),

Check the sign of C.

Condition of back face is thus:

sgn(C) > 0.
What happens if
V. N = 0 ??
N V

V
How to get normal vector (N) for a
3D surface, polygon ?
R Q

R=PXQ 
P

-R

Order of vertices for calculation

of N – w.r.t the front side of the surface.

Brighter
Darker
Side
side
Take the order of vertices to be
counter-clockwise for the brighter side.

Take the case of a cube:

Exterior faces of a cube:

 You can choose any two vectors (edges)
to obtain the normal to the surface.

Any risks in such a case, if we randomly

choose any two vectors?
Better Solution to obtain the direction
cosines of N:
n

Assume a =  (Yi −Y j )(Z i + Z j )

i =1
n vertices
b =  (Z i −Z j )(X i + X j ) where j = i + 1
n
of the
polygon: i =1

(Xi, Yi, Zi);

n

i=1,2,…,n.
c  (X i −X j )(Yi Y j )
i =1

Compute: If i = n, j = 1
 n
a =  (Yi −Y j )(Z i + Z j )
i =1

b =  (Z i −Z j )(X i + X j ) where j = i + 1
n

i =1
n
c =  (X i −X j )(Yi + Y j )
i =1

If i = n, j = 1
Take the expression of “c”:
Can you relate that to one property of
the 2-D polygon in X-Y plane?
a, b and c also describe the projection
surface of the polygon on the Y-Z, Z-X and
X-Y planes (or along the X, Y and Z axis)
respectively.
c = (X1 −X2)(Y1 +Y2) + (X2 −X3)(Y2 +Y3) + (X3 −X1)(Y3 +Y1)
= X1(Y2 −Y3)+X2(Y3 −Y1)+X3(Y1 −Y2)
If A is the total area of the polygon, the
projected areas are:

AYZ = a/2; AXZ = b/2; AXY = c/2;

The surface normal appears to be

pointing outwards. Facing towards the viewer,
the edges of the polygon appears to be drawn
counter-clockwise.
The polygon is a back face, if c > 0

If the view direction is along the –ve Z-

direction, the above condition becomes:
c<0
Drawbacks of back face culling:

• Partially hidden faces cannot be

determined by this method

• Not useful for ray tracing, or

photometry/ radiosity.

However, this is still

useful as a pre-processing
step, as almost 50% of the
surfaces are eliminated.
 Depth-buffer
or
Z-buffer method

COP
 Each (X,Y,Z) point on a polygon
surface, corresponds to the orthographic
projection point (X, Y) on the view plane.

At each point (X, Y) on the PP,

object depths are compared by using
the depth(Z) values.
Assume normalized coordinates:

(FCP) Zmax > Z > 0 (BCP), where Zmax = 1.

Two buffer areas are used:

(i) Depth (Z) buffer: To store the depth

values for each (X, Y) position, as
surfaces are processed.

(ii) Refresh Buffer: To store the intensity

value at each position (X, Y).
 Depth-buffer
or
Z-buffer method

COP
 Steps for Processing:
(a) Initialize depth(X,Y) = Z max
(X,Y)
IB = background refresh(X,Y)= I B
intensity

(b) For each position on each polygon surface:

(i) Calculate depth Z for each position

(X, Y) on the polygon.

(ii) If Z < depth(X, Y) then

depth (X, Y) = Z;

refresh (X, Y) = Is (X, Y)

 Is is the projected intensity value of the
surface at position (X, Y), which has the
minimum value of Z, at the current stage of
iteration.
Equation of thesurface:
AX+ BY+ CZ + D = 0;
Calculation of Z:
− AX− BY− D
Z=
C
Equation for Z at the next scan line:
Remember scanline/Polyfill algorithm?
Using edge coherence, we get for the next
scanline (Y+1):
X’ = X -1/m;
 Y
Y-1

X X+1
A
Z X +1 = Z X − ;
C
A
+B
+ m
ZY +1 = YZ ;
C

For a vertical edge: Z’ = Z + B/C;

 So to implement the algorithm, three
constants are required for each surface:

A
( + B)
− ,
A m ,
B
C C C
What is the special condition, C = 0?
Using the above three constants, we can
keep calculating the successive depth values
along and for successive scanlines. Similar
approaches can be used for curved surfaces:
Z = f(X, Y).
 Z-Buffer Algo:
for all (x,y)
depth(x,y) = -∞ /* Watch this change */
refresh(x,y) = IB

for each polygon P

for each position (x,y) on polygon P
calculate depth z

if z > depth(x,y) then

1. depth(x,y) = z
2. refresh(x,y) = IP(x,y)

Lets take an example →

Z-values of the 4 4 9 8 7 6 5
coordinates: 4 4 8 7 7 6 5

4 4
4 4
Z-Buffer
values
9 8 9 8
8 7 4 7 8 7 4
4 4 7 6 5 4
Z-values of the 4 4 9 8 7 6 5
coordinates: 4 4 8 7 7 6 5

9 8
7 8 7 4
7 6 5 4
Z-Buffer
values

IMAGES (after pseudo-texture rendering)

V
V
 SCAN-LINE Algorithms (for VSD)
Extension of 2-D Scanline (polyfill) algorithm.

Here we deal with a set of polygons.

Data structure used:
ET (Edge Table),
AET (Active Edge Table) and
PT (Polygon Table).

Edge Table entries contain information

about edges of the polygon, bucket sorted
based on each edge’s smaller Y coordinate.

Entries within a bucket are ordered by

increasing X-coordinate of their endpoint.
 Structure of each entry in ET:
• X-Coordn. of the end point with the smaller
Y-Coordn.
• Y-Coordn. of the edge’s other end point
• X = 1/m
• Polygon ID X Ymax X ID

Structure of each entry in PT:

• Coefficients of the plane equations
• Shading or color information of the polygon
• Flag (IN/OUT), initialized to ‘false’

Plane Shading
ID IN/OUT
Coeffs. Info.
Take Adjacent (not successive) pairs of intersections to fill;
FILL (within pair) if POLY_FLAG is set to IN.

B E

L1
L2
L3
D
C
L4
F
L5

L3
ABC IN; ABC IN; ABC OUT;
DEF OUT DEF IN. DEF IN.

Compare Z values in this region

to find the visible Z value.
 B E

L1
L2
L3
D
C
L4
L5 F

AET Contents
Scan Line Entries
L5 AB CA
L4 AB CA FD EF
L3, L2 AB DE BC EF
L1 AB BC DE EF
Three non-intersecting polygons

J B I
E

D C
F
A
G H

GHIJ is behind ABC and DEF.

 So, when scanline leaves edge BC, it is
still inside polygons DEF and GHIJ. If
polygons do not intersect, depth calculations
and comparisons between GHIJ and DEF can
be avoided.

Thus depth computations are

unnecessary when the scanline leaves an
obscured polygon. It is required only when it
leaves an obscuring polygon.

Additional treatment is necessary for

intersecting polygons.
 Depth-sorting or Painter’s Algorithm
Paint the polygons in the frame buffer
in order of decreasing distance from the
viewpoint.
Broad Steps:
• Surfaces are sorted in increasing order
of DEPTH.

• Resolve ambiguities when polygons

overlap (in DEPTH), splitting polygons
if necessary.
• Surfaces are scan converted in order,
starting with the surface of greatest
DEPTH.
Principle:

Each layer of paint (polygon surface of

an object) covers up the previous layers
while drawing.

ZMax1
S1
ZMin1
ZMax2
S2
ZMin2
X
Z
Since, ZMin1 > ZMax2 no overlap occurs.
S1 is first scan converted, and then S2.
This goes on, as long as no overlap occurs.

ZMax1
S1
ZMin1
ZMax2
S2
ZMin2 V
X
Z
If depth overlap occurs, additional
comparisons are necessary to reorder the
surfaces.
The following set of tests are used to
ensure that no re-ordering of surfaces is
necessary:
 Four(4) Tests in Painter’s algorithm

[Link] boundary rectangles in the X-Y plane

for the two surfaces do not overlap.

[Link] S is completely behind the

overlapping surface relative to the viewing
position.

[Link] overlapping surface is completely in

front of S relative to the viewing position.

[Link] projections of the two surfaces onto

the view plane do not overlap.
Tests must be performed in order, as specified.

Condition to RE-ORDER the surfaces:

If any one of the 4 tests is TRUE, we

proceed to the next overlapping surface. i.e.
If all overlapping surfaces pass at least one of
the tests, none of them is behind S.
No re-ordering is required, and then S is
scan converted.

RE-ORDERing is required if all the four

tests fail.
 TEST #1:
The boundary rectangles in the X-Y
plane for the two surfaces do not overlap.

We have depth overlap , but no overlap

in X-direction.
Hence, Test #1 is passed, scan convert
S2 and then S1.

S2
If we have X
S1
overlap, check
for the rest.
Z X1 X2 X 3 X4 X
TEST #2:
Surface S is completely behind the
overlapping surface relative to the viewing
position.
S1

S2

Z X

Fig. 1. S1 is completely behind/inside the

overlapping surface S2
TEST #3:
The overlapping surface is completely in
front of S relative to the viewing position.

S1 is not completely behind S2.

So, Test #2 fails.
S1
Fig. 2. Overlapping S2
surface S2 is completely
front/outside S1.
Z X

In Fig. 2, S2 is in front of S1, but S1 is

not completely inside S2 – Test #2 it not TRUE
or FAILS, although Test #3 is TRUE.
 How to check these conditions?

i) Set the plane equation of S2, such that the

surface S2 is towards the viewing position.

ii) Substitute the coordinates of all vertices of

S1 into the plane equation of S2 and check
for the sign.

iii) If all vertices of S1 are inside S2, then

S1 is behind S2. (Fig. 1).
iv)If all vertices of S1 are outside S2, S1 is
in front of S2.
TEST #4:
The projections of the two surfaces onto
the view plane do not overlap.

S2
S1

Z X
 Four(4) Tests in Painter’s algorithm
- revisited

[Link] boundary rectangles in the X-Y plane

for the two surfaces do not overlap.

[Link] S is completely behind the

overlapping surface relative to the viewing
position.

[Link] overlapping surface is completely in

front of S relative to the viewing position.

[Link] projections of the two surfaces onto

the view plane do not overlap.
Tests must be performed in order, as specified.

Condition to RE-ORDER the surfaces:

If any one of the 4 tests is TRUE, we

proceed to the next overlapping surface. i.e.
If all overlapping surfaces pass at least one of
the tests, none of them is behind S.
No re-ordering is required, and then S is
scan converted.

RE-ORDERing is required if all the four

tests fail.
Case Studies – examples of

Painter’s Algorithm
 Case Study - I

S2

S1

X
Z
Initial order:
S1 -> S2

Change the order:

S2 -> S1
 Case Study - II
S3
Initial Order: S1 S2
S1 -> S2 -> S3.

S1 -> S2, X
Z
Test 1 passed.

Check S1, S3. All tests fail.

Interchange. S3 -> S2 -> S1.

Check S2 and S3. All tests fail again.

Correct Order: S2 -> S3 -> S1.

Process of checking the order,
results in an infinite loop.

Avoided by setting a FLAG for a

surface that has been re-ordered
or shuffled. If it has to be altered
again, split it into two parts.
 0 0 0
Y -0.5 -0.5 Y 0
-0.5 -0.5

S1 S2
S2 S1

0
0.5 0.5
0.5 0.5
0 0
0
X Fig. B X
Fig. A

What happens in these cases ?

 Area sub-division method

Examine and divide if necessary

• Works in image-space

• Area Coherence is exploited

• Divide-and-conquer strategy.

WARNOCK’s
Algorithm
 Possible relationships of the area of interest
(rectangular, AOI) and the projection of the
polygon:
[Link] polygons are completely
overlapping the area of interest.

2. Intersecting polygons intersect the area.

3. Contained polygons are completely inside

the area.

[Link] polygons area completely outside

the area.
 Four cases of Polygon position w.r.t rectangular AOI.

Intersecting

Surrounding

Contained

Disjoint
 Treat interior part of the intersection
and contained as equivalent. Disjoint is
irrelevant. The decisions about division of an
area is based on:

[Link] polygons are disjoint from the area.

Display background color.

[Link] one intersecting part or interior

(contained): Fill the area with background
color and then scan-convert the polygon.

[Link] surrounding polygon, and no

intersecting or contained polygon. Use
color of surrounding polygon to shade the
area.
4. More than one polygon intersect, contained
in and surrounding the area. But the
surrounding polygon is in front of all other
polygons. Then fill the area with the color
of the surrounding polygon.
Step 4 is implemented by comparing the
Z-coordinates of the planes of all polygons
(involved) at the four corners of the area
If all four tests fail, divide the
rectangular area into four equal parts.

Recursively apply this logic, till you reach

the lowest minimum area or maximum
resolution – pixel size.
Use nearest surface in that case to
paint/shade.
 X
Decision – Step 4
X

Z
Z
Intersection with:
Contained Polygon Surrounding
Polygon
Intersecting Polygon
 Four cases of Polygon position w.r.t rectangular AOI.

Intersecting

Surrounding

Contained

Disjoint
Case Studies – examples of

Area Sub-division method

(i) (ii)

(iii) (iv)
BSP (Binary Space Partition) trees
 P1
P2 C

A
D
P1

B BP F B
FP
FP
BP P2F P2B

F B F B
BSP (Binary Space
D
Partition) trees A C B
Salient features:

• Identify surfaces that are inside/front and

outside/back w.r.t. the partitioning plane at
each step of the space division, relative to
the viewing direction.

• Start with any plane and find one set of

objects behind and the rest in the front.

• In the tree, the objects are represented as

terminal nodes with front objects as left
branches and back objects as right
branches.
• BSP tree’s root is a polygon selected from
those to be displayed.

• One polygon each from the root polygon’s

front and back half plane, becomes its front
and back children

• The algorithm terminates when each node

contains only a single polygon.

• Intersection and sorting at object

space/ precision
 3
5a 5 2 4
2 5b
5b 5a 1
1 3
4

5a 5
2
3 5b
1 3
4
1 4
2 5b
5a
 5

5a 5 4
2
3
5b
1 3 1
4
2

5
2
3
1 3
2 4 4

5a 1 5b
 5a
5
2
V
5b 3
1 3
4 5b
2

1 5a 4
Also see:
Other applications:
potential visibility sets;
• Robot navigation
KD trees, R+-trees;
• Collision Detecion
Bounding Volume Hierarchy (BVH)
• GIS
and
Shadow Volume BSP Tree (SVBSP) • Image Registration
 Display list of a BSP tree
• BSP tree may be traversed in a “modified in-
order tree” walk to yield a correctly priority-
ordered polygon list for an arbitrary
viewpoint.
• If the viewer is in the root polygon’s front
half space, the algorithm must first display:
[Link] polygons in the root’s rear half-
space.
[Link] the root.
[Link] finally all polygons in the front
half-space.
• Use back face culling
• Each of the root’s children is
recursively processed.
 Disadvantages

– more polygon splitting may occur than

in Painter's algorithm

– appropriate partitioning hyperplane

selection is quite complicated and
difficult

Finding Optimal BSP:

Finding an optimal root node is by testing a small

number of candidates.

The node that results in the smallest number of

nodes in the BSP tree should be chosen
VSD - Ray Tracing

COP
 Figure for illustrating
VSD - Ray Tracing

In reality, possibilities with a light ray:

absorption, reflection, refraction, scattering, fluorescence or
chromatic aberration (error in lens).
Remember? For Z-buffer:
Each (X,Y,Z) point on a polygon surface,
corresponds to the orthographic projection
point (X, Y) on the view plane.
At each point (X, Y) on the PP, object
depths are compared by using the depth(Z)
values.

For Ray-tracing:
• Shoot ray from eye point through pixel (x,y)
into scene

• Intersect with all surfaces, find first one the

ray hits
 For Ray-tracing (cont’d):

• Line of Sight of each pixel is

intersected with all surfaces

• Shade that point to compute the color

of pixel (x,y)

• Consider only the closest surface for shading

• Based on optics of image formation, paths

of light rays are traced

• Light rays are traced backward

 For Ray-tracing (cont’d):

• Suitable for complex curved surfaces

• Computationally expensive

• Need of an efficient ray-surface intersection

technique

• Almost all visual effects can be generated

• Can be parallelized

• Has aliasing problems

 Mathematically, the intersection
problem is of finding the roots of an equation:

Surface – RAY = 0;

Ray Equation: r(t) = t (P – C)

Eqns. for
LINE: x = x0 +tx; y = y0 +ty; z = z0 +tz;
SPHERE: (x−a) +(y−b) +(z−c) =r
2 2 2 2
Substitution
gives us:
(x0 t x) − 2a(x0
2
t x) a 2

+ (y0 + ty) −2b(y0 + ty) + b

2 2

+ (z0 + tz) −2c(z0 + tz) + c = r

2 2 2

Collecting terms
gives us:
(x 2 +y2 + z 2 )t 2 +
2t[x(x0 −a) + y( y0 −b)+ z(z0 −c)]
+(x0 −a) +( y0 −b) +(z0 −c)2 −r 2 = 0
2 2
 The Equation is Quadratic, with
coefficients from the constants of sphere and
ray equations.

Cases:
• No real roots - Surface and ray do
not intersect

• One real root - Ray tangentially

grazes the surface

• Two real roots - From both

intersections, get
the one with the
smallest value of t.
What is the shade, at that point of
intersection?

Sphere has center (a, b, c).

The surface normal at any point of

intersection is:
xp −a yp −b z p −c
[ , , ]
r r r
What about intersection with other (regular) non-
linear surfaces ??

• Gaussian
• Ellipsoid
• Directional sinusoid
• Torus
Eqns. for
LINE : x = x0 + tx ; y = y0 + ty ; z = z0 + tz ;
PLANE : Ax + By + Cz + D = 0
Substitution gives us:
(Ax0 + By0 + Cz0 + D)
t=−
(Ax + By + Cz)
• Denominator should not be zero;

• Find if intersection is within the polygon,

by projecting onto a suitable coordinate
plane;

• Overall processing is ray-wise,

not polygon-wise.
Read about:

• Stochastic/Distributed Ray Tracing (Monte Carlo on Graphics)

• Global Illumination

• Radiosity

• The Metropolis light transport (MLT) - SIGGRAPH 1997

• Bi-directional Ray Tracing

 Rendering with global illumination: Light is reflected by
surfaces, and colored light transfers from one surface to
another. Color from the red wall and green wall (latter not
visible) reflects onto other surfaces in the scene. Also
notable is the caustic projected onto the red wall from
light passing through the glass sphere.
Comparison of VSD (HSR) techniques
Algorithms/
Memory Speed
Methods
Two Depth
Z-Buffer
arrays complexity
Apriori
One sorting helps
Painter’s
array
speed-up
Object O(#pixels,
Ray casting data #surfaces or
base objects)
Scanline, Area
- Slowest
sub-division
Algorithms Issues in
Remarks
/Methods Implementation
Scan conversion,
Z-Buffer Commonly used
Hardware
Splitting and
sorting the
Painter’s Scan conversion
major
bottleneck
Excellent
Spatial data for CSG,
Ray casting structures help
shadows,
speedup
transparency
Cannot be
Scanline, Area
Hard generalized for non-
sub-division
polygonal models.
VSD - “Visible Surface Detection”
is also called:

Hidden Surface Elimination (HSE); Also: HSR, OC.

So, what is HLE:

Hidden Line Elimination.

Problem:
Take any VSD algorithm and
convert to an HLE algorithm