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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} value.

What if polygons overlap?

Sort by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_{min}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_{max}} .

If object is uninterrupted, it's fine (i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_{min}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z} value for each pixel.
2. Only draw pixel if depth value is closer than stored Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^3)} objects created)