[go: up one dir, main page]

0% found this document useful (0 votes)
22 views15 pages

Umich Scanline

Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
22 views15 pages

Umich Scanline

Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

Lecture

Scan-Line Algorithm 8

Scan-Line
sort objects by y, for all y {
sort objects by x, for all x {
compare z
}
}

One of the earliest algorithms for image generation.


1967-1974

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.

Generally fast because:


1. Visibility decisions can be made in a 2-D subset of the 3-D scene
2. Coherency properties can be used to speed processing

Lecture
Scan-Line Algorithm 8

• Use a Window that is one scan line high (constant Y


value) Polygon List
• Polygons intersections can be considered as a
collection of line segments
• Visibility testing is then done on these line segments Y-sorted List
• This reduces the 3-D problem to a 2-D problem

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
}
}

Another of the earliest algorithms for image generation.


1969-1972

It can be thought of as painting, or filling, with opaque paint, where closer


objects are painted over farther ones.

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

•Subdivided these objects.


Subdivide
•Resort the sub objects by Z Mixed Polygons

•Repeat the above three steps until all Z-sort


object have clean Z values Sub-Polys
•Start at the back and draw and fill all
objects into the frame buffer. Draw and Paint
Back to Front

Lecture
Painter’s Algorithm 8

Z sorting is the key to the Painter’s Algorithm.

•Simple and straight forward sort/subdivide.

•Binary-Space-Partitioning (BSP) tree.

•2 1/2 D with a priori valid order (Compositing)

•Particle systems (Very simple to sort)

3
Painter’s Algorithm Lecture
BSP 8

Extremely efficient method for calculating the visibility


relationships among a static group of polygons.

It is a trade off between a time and space intensive preprocessing


step against a linear display step.

Well suited for applications in which the viewpoint changes, but


were the objects do not.
P1
A
f b
1
P2 P2
D 3 f b f b
B
2 D C A B
C 3,1,2 3,2,1 1,2,3 2,1,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

Painter’s Algorithm Lecture


BSP 8

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

Painter’s Algorithm Lecture


BSP 8

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

The “simplest” versions of the painters algorithm must do a


shading calculation for every pixel of every object.

Some shading calculations can be avoided by painting some


selected closest objects and then paint around them for the back
objects.

The above can have serious problems because of requiring global


order which can be very expensive to calculate.

With many Painter’s algorithms aliasing can be a real problem.


Using the alpha channel and compositing can help.

14

7
Lecture
Painter’s Algorithm 8

Particle systems lend them selves to the Painter’s Algorithm

Partical systems are made of small dynamic objects that


can be created, extinguished, or moved. They are
generally small and look like points which contain color
and transparency. If they do have shape it can change
with time along with color and material type.

Being small they are easily sorted into fixed bins in


space with little to no chance for z overlap.

Pseudo random location and motion tend to cause


uncorrelated obscurations suitable for antialiased
compositing.

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
}
}

Of all the image rendering algorithms the Z-Buffer or Depth Buffer


is one of the simplest.

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.

This algorithm lends it self to easy anti-aliasing

18

9
Lecture
Z-Buffer 8

Development of the Z-Buffer is attributed Polygon List


to Ed Catmull in 1974.
Many additions have been add including Project into
screen space
•Alpha buffers
•Jittered Samples For each pixel
find Z coverage
•Weighted averages anti-aliasing
Shade nearest
•Bi-cubic patch subdivision polygons
•Depth maps
•Shadows

19

Lecture
Z-Buffer 8

Two Papers that are a must for understanding Z-buffer rendering


systems.
“The Reyes Image Rendering Architecture”

“The A-Buffer, an Antialiased Hidden Surface Method”

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

The Alpha Buffer is


•Antialiased
•Area-averaged
•accumulation Buffer

Resolves visibility of an arbitrary collection of opaque and


transparent surfaces.

Increases image resolution many times over the standard Z-Buffer

22

11
Lecture
Alpha & Z-Buffer 8

Intensity Depth Buffer Alpha


23

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 Digital Images”

“Compositing 3-D Rendered Images

“Compositing - Theory”

“Composting - Practice”

30

15

You might also like