Transcript document

Part I:
Basics of Computer Graphics
Chapter 3
Visible Surface
Determination
3-1
Visible Surface Determination
 When 3D objects are projected onto the 2D





screen, occlusion happens
From a given viewpoint, what is in front?
Viewpoint dependent problem
Object-based algorithms
Image-based algorithms
Major algorithms:
 Back face culling
 Depth-sort (painter’s) algorithm
 Z-buffer algorithm
 Scanline algorithm
 Area coherence algorithm
 Ray-casting and ray-tracing algorithm
3-2
Back Face Culling
q
n
v
 A polygon is front facing when q (the angle




between the viewing vector v and the
normal n of the polygon) lies between
-90o and 90o or cos q  0
Use dot product to test visibility
v . n = |v| |n| cos q
0
visible
<0
invisible
All polygon vertices must be ordered in anticlockwise fashion to yield a correctly
directed normal vector
Might not remove all invisible objects (those
due to occlusion)
Might remove objects we want. Sometimes
we want back facing polygon (when inside
an object)
3-3
Depth-sort algorithm
 Sort all polygons according to the furthest
z coordinates
 Resolve problems of overlapping (in z)
polygons (e.g. subdivision)
 Scan convert (project 3D polygon to 2D and
draw it) each polygon in ascending order of
z coordinate (back to front)
x
z
 The mechanism is similar to how a painter
draws layers of objects from back to front
 Also known as painter’s algorithm
3-4
Z-Buffer Algorithm
 Maintain a Z-buffer with same resolution as
frame buffer
 During scan conversion compare
 Z value of pixel about to be stored and
 Z value of current pixel in Z-buffer
 If new pixel’s Z value is closer, store new
pixel value (color) in frame buffer and new
Z value in Z-buffer
Frame buffer
for recording
pixel color
Depth buffer
for recording
pixel depth
 Running time is linear to the number of
objects
 Suffers from aliasing if precision is low
 Frequent hardware implementations
because of its simplicity and speed
3-5
Scanline algorithm
 Use of data structures reduce computation
 Exploits edge coherence
 While advancing along scan-line


determine surface that projects to pixel
choose closest surface from the sorted
list
 Due to the complexity of manipulating the
data structure, it is less popular
3-6
Ray tracing algorithm
 Actually backward ray tracing
 Send ray from the eye, through the pixel
into the modeled virtual world
 Determine which surface is intersected first
 Can be combined with lighting algorithms
 Extremely slow: O(resolution*number of
objects)
 Comprehensive solution to shadow
generation, reflection, and refraction
 Partially solves the global illumination
problem
3-7