CSCE 441 Lecture 21

« previous | Wednesday, March 5, 2014 | next »

Begin Exam 2 content

Hidden Surfaces

Painter's Algorithm

Draw from back to front, but how do we sort polygons?

Sort by $z$ value.

What if polygons overlap?

Sort by $z_{min}$ and $z_{max}$.

If object is uninterrupted, it's fine (i.e. $z_{min}$ and $z_{max}$ are adjacent in list)

We may have to split polygons.

• find plane to split polygon so each new polygon is entirely in front or entirely in back
• resort list

Advantages:

• simple sorting algorithm

Disadvantages:

• sorting criteria are difficult to produce
• Redraws same pixel many times (overdraw)
• sorting can be expensive

Depth (Z) Buffer

Simple modification to scan-conversion

1. Maintain a separate buffer storing closest $Z$ value for each pixel.
2. Only draw pixel if depth value is closer than stored $Z$ value.
3. update buffer with closest depth value

Advantages:

• simple to implement (about 5 lines)
• allows for streaming approach to polygon drawing

Disadvantages:

• Requires extra storage space
• Still lots of overdraw if painter's algorithm is used

Binary Space Partitioning (BSP) Trees

Organize all of space into a binary tree

• preprocess: overlay a binary tree on objects in the scene
• runtime: correctly traversing this tree enumerates objects from back to front

Divide space recursively into half-spaces by choosing splitting planes (arbitrarily oriented)

• planes can be chosen independently for each half-space
• If plane passes through object, split and give each side to each node. (worst case $O(n^{3})$ objects created)