Umich Scanline
Umich Scanline
Scan-Line Algorithm 8
Scan-Line
sort objects by y, for all y {
sort objects by x, for all x {
compare z
}
}
This algorithm creates and image by processing the scene data on a line-by-line
basis from the top to the bottom of the frame buffer.
Lecture
Scan-Line Algorithm 8
Typical Steps
X-sorted List
•Sort polygons with one y bucket per scan line
For each scan line
• For all active polygons on this scan line find and sort
the x end points
• On a pixel by pixel basis sort out which line segment Z – Sort
is closest
Depth List
• Find the color for each pixel
•Move to the next scan line
Visible element
•Update x end points for all polygons still in y bucket
determination
•Add new x end points for new polygons.
1
Lecture
Scan-Line Algorithm 8
Polygon List
The greatest variation in scan line algorithms
occurs in the z sort or depth list
Y-sorted List
Worst case, a z-depth list must be generated for
each pixel
X-sorted List
If in the x sorted line list none of the objects cross For each scan line
each other, visibility can be found for large
sections of the scan line.
Z – Sort
If in the x sorted list lines do cross each others Depth List
span, lists can be generated so that again a large
number of pixels can be handle in one segment.
Visible element
determination
Lecture
Painter’s Algorithm 8
Painter’s
sort objects by z, for all objects {
for all covered pixels(x,y) {
paint
}
}
This algorithm solves the visible object problem by painting. It is simple but
is not always the most efficient.
2
Lecture
Painter’s Algorithm 8
Polygon List
•Start by sorting all objects by depth from
front to back.
•Find all objects that have mixed Z. Z-sorted list
Lecture
Painter’s Algorithm 8
3
Painter’s Algorithm Lecture
BSP 8
Example
2
3
1
4
Painter’s Algorithm Lecture
BSP 8
Example
3
5 1 4
2
2
3
1
1
4
Example
3
F B
5 1 4
5a 2 5b
5a
5b
2
3
1
1
4
10
5
Painter’s Algorithm Lecture
BSP 8
Example
3
F B
5 4
2
5a 5b
F B
5b
2 5a 1
3
1
1
4
11
Example
3
F B
5
2 4
5a B
F B
5b
2 5a 1 5b
3
1
1
4
12
6
Painter’s Algorithm Lecture
BSP 8
Example II
5
B
5
4
B
2 3
F
3
1 1
1
4 B
2
13
Lecture
Painter’s Algorithm 8
14
7
Lecture
Painter’s Algorithm 8
15
Lecture
Painter’s Algorithm 8
16
8
Lecture
Painter’s Algorithm 8
17
Lecture
Z-Buffer 8
Z-Buffer
for all objects {
for all covered pixels {
compare z
}
}
For each pixel in the display buffer record the depth value of the
object in the scene. Start with the nearest object in each pixel and
determine the shading values.
18
9
Lecture
Z-Buffer 8
19
Lecture
Z-Buffer 8
20
10
Lecture
Reyes Rendering System 8
Design Principles:
•Natural Coordinates
•Vectorization
•Common Representation
•Locality
•Geometric
•Texture
•Linearity
•Large Models
•Back Door
•Texture Maps
21
Lecture
The Alpha Buffer 8
22
11
Lecture
Alpha & Z-Buffer 8
Lecture
Alpha 8
24
12
Lecture
Compositing Example 8
25
Lecture
Compositing Example 8
26
13
Lecture
Compositing Example 8
27
Lecture
Compositing Example 8
28
14
Lecture
Compositing Example 8
29
Lecture
Compositing 8
Important Papers:
“Compositing - Theory”
“Composting - Practice”
30
15