2 of 30

Reading

Foley et al, Chapter 15�

Optional

I. E. Sutherland, R. F. Sproull, and R. A. Schumacker, A characterization of ten hidden surface algorithms, ACM Computing Surveys 6(1): 1-55, March 1974.

3 of 30

The Quest for 3D

Construct a 3D hierarchical geometric model
Define a virtual camera
Map points in 3D space to points in an image

produce a wireframe drawing in 2D from a 3D object

Of course, there’s more work to be done…

4 of 30

Introduction

Not every part of every 3D object is visible to a particular viewer. We need an algorithm to determine what parts of each object should get drawn.
Known as “hidden surface elimination” or “visible surface determination”.
Hidden surface elimination algorithms can be categorized in three major ways:

Object space vs. image space
Object order vs. image order
Sort first vs. sort last

5 of 30

Object Space Algorithms

Operate on geometric primitives

For each object in the scene, compute the part of it which isn’t obscured by any other object, then draw.
Must perform tests at high precision
Resulting information is resolution-independent

Complexity

Must compare every pair of objects, so O(n²) for n objects
For an m x m display, have to fill in colors for m² pixels.
Overall complexity can be O(k_objn²+ k_dispm²).
Best for scenes with few polygons or resolution-independent output

Implementation

Difficult to implement!
Must carefully control numerical error

6 of 30

Image Space Algorithms

Operate on pixels

For each pixel in the scene, find the object closest to the COP which intersects the projector through that pixel, then draw.
Perform tests at device resolution, result works only for that resolution

Complexity

Naïve approach checks all n objects at every pixel.Then, O( ).
Better approaches check only the objects that could be visible at each pixel. Let’s say, on average, d objects are visible at each pixel (a.k.a., depth complexity). Then, O( ).

Implementation

Usually very simple!
Used a lot in practice.

n m²

d m²

7 of 30

Object Order vs. Image Order

Object order

Consider each object only once - draw its pixels and move on to the next object
Might draw the same pixel multiple times

Image order

Consider each pixel only once - draw part of an object and move on to the next pixel
Might compute relationships between objects multiple times

8 of 30

Sort First vs. Sort Last

Sort first

Find some depth-based ordering of the objects relative to the camera, then draw from back to front
Build an ordered data structure to avoid duplicating work

Sort last

Sort implicitly as more information becomes available

9 of 30

Important Algorithms

Ray casting
Z-buffer
Binary space partitioning
Back face culling

10 of 30

Ray Casting

Partition the projection plane into pixels to match screen resolution:
For each pixel p_i, construct ray from COP through PP at that pixel and into scene
Intersect the ray with every object in the scene
Color the pixel according to the object with the closest intersection

11 of 30

Ray Casting, cont.

Parameterize each ray:

r(t) = c + t (P_ij- c)

Each object O_i returns t_i >1 such that �first intersection with O_i occurs at r(t_i).

Q: Given the set {t_i} what is the first intersection point?

12 of 30

Aside: Definitions

An algorithm exhibits coherence if it uses knowledge about the continuity of the objects on which it operates
An online algorithm is one that doesn’t need all the data to be present when it starts running

Example: insertion sort

13 of 30

Ray Casting Analysis

Easy to implement?
Hardware implementation?
Pre-processing required?
Incremental drawing calculations (uses coherence)?
On-line (doesn’t need all objects before drawing begins)?
Memory intensive?
Handles transparency and refraction?
Polygon-based?
Extra work for moving objects?
Extra work for moving viewer?
Efficient shading?
Handles cycles and self-intersections?

14 of 30

Z-buffer

Idea: along with a pixel’s red, green and blue values, maintain some notion of its depth

An additional channel in memory, like alpha
Called the depth buffer or Z-buffer

When the time comes to draw a pixel, compare its depth with the depth of what’s already in the framebuffer. Replace only if it’s closer
Very widely used
History

Originally described as “brute-force image space algorithm”
Written off as impractical algorithm for huge memories
Today, done easily in hardware

void draw_mode_setup( void ) {

…

GlEnable( GL_DEPTH_TEST );

…

}

15 of 30

Z-buffer Implementation

for each pixel p_i

{

Z-buffer[ p_i ] = FAR

Fb[ p_i ] = BACKGROUND_COLOR

}

for each polygon P

{

for each pixel p_i in the projection of P

{

Compute depth z and shade s of P at p_i

if z < Z-buffer[ p_i ]

{

Z-buffer[ p_i ] = z

Fb[ p_i ] = s

}

16 of 30

Visibility tricks for Z-buffers

Z-buffering is the algorithm of choice for hardware rendering

What is the complexity of the Z-buffer algorithm?

What can we do to decrease the constants?

17 of 30

Z-buffer Tricks

The shade of a triangle can be computed incrementally from the shades of its vertices
Can do the same with depth

(R₁,G₁,B₁,z₁)

(R₂,G₂,B₂,z₂)

(R₃,G₃,B₃,z₃)

18 of 30

Z value interpolation

Scan line

19 of 30

Depth Preserving�Conversion to Parallel Projection

20 of 30

Computing Z

Use 3x4 projective transformation

And keep around z (e.g. z´=z)
To make sure that z bits are unifromly distributed between far and near clipping planes

21 of 30

Z-buffer Analysis

Easy to implement?
Hardware implementation?
Pre-processing required?
Incremental drawing calculations (uses coherence)?
On-line (doesn’t need all objects before drawing begins)?
Memory intensive?
Handles transparency and refraction?
Polygon-based?
Extra work for moving objects?
Extra work for moving viewer?
Efficient shading?
Handles cycles and self-intersections?

22 of 30

Binary Space Partitioning

Goal: build a structure that captures some relative depth information between objects. Use it to draw objects in the right order from any viewpoint.

Called the binary space partitioning tree, or BSP tree

Key observation: The polygons in the scene are painted in the correct order if for each polygon P,

Polygons on the far side of P are painted first
P is painted next
Polygons in front of P are painted last

23 of 30

Building a BSP Tree (in 2D)

24 of 30

Alternate BSP Tree

back

front

25 of 30

BSP Tree Construction

Splitting polygons is expensive! It helps to choose P wisely at each step.

Example: choose five candidates, keep the one that splits the fewest polygons

BSPtree makeBSP( L: list of polygons )

{

if L is empty

{

return the empty tree

}

Choose a polygon P from L to serve as root

Split all polygons in L according to P

return new TreeNode(

makeBSP( polygons on negative side of P ),

makeBSP( polygons on positive side of P ))

}

26 of 30

BSP Tree Display

showBSP( v: Viewer, T: BSPtree )

{

if T is empty then return

P := root of T

if viewer is in front of P

{

showBSP( back subtree of T )

draw P

showBSP( front subtree of T )

} else {