Scan-Line Fill
• Can also fill by maintaining a data structure of all intersections of polygons with scan lines
• Sort by scan line
• Fill each span
vertex order generated by vertex list
desired order
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Scan-Line Algorithm
For each scan line:
1. Find the intersections of the scan line with all edges of the polygon.
2. Sort the intersections by increasing x- coordinate.
3. Fill in all pixels between pairs of intersections.
Problem:
Calculating intersections is slow.
Solution:
Incremental computation / coherence
For scan line number 8 the sorted list of x-coordinates is (2,4,9,13) (b and c are initially no integers)
Therefore fill pixels with x- coordinates 2-4 and 9-13.
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Edge Coherence
• Observation: Not all edges intersect each scanline.
• Many edges intersected by scanline i will also be intersected by scanline i+1
• Formula for scanline s is y = s, for an edge is y = mx + b
• Their intersection is
s = mxs + b –> xs = (s-b)/m
• For scanline s + 1,
xs+1 = (s+1 – b)/m = xs + 1/m
Incremental calculation: xs+1 = xs + 1/m Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Processing Polygons
• • •
•
•
Polygon edges are sorted according to their minimum / maximum Y.
Scan lines are processed in increasing (upward) / decreasing (downward) Y order.
When the current scan line reaches the lower / upper endpoint of an edge it becomes active.
When the current scan line moves above the upper / below the lower endpoint, the edge becomes inactive.
Active Edges
Not yet active
edges Finished edge
Ignored horizontal edge
Active edges are sorted according to increasing X. Filling the scan line starts at the leftmost edge intersection and stops at the second. It restarts at the third intersection and stops at the fourth. . . (spans)
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Polygon fill rules
(to ensure consistency)
1. Horizontal edges: Do not include in edge table
2. Horizontal edges: Drawn either on the bottom or on the top.
3. Vertices: If local max or min, then count twice, else count once.
4. Either vertices at local minima or at local maxima are drawn.
5. Only turn on pixels whose centers are interior to the polygon:
round up values on the left edge of a span, round down on the right edge
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
•
Polygon fill example
The edge table (ET) with edges entries sorted in increasing y and x of the lower end.
• ymax: max y-coordinate of edge
• xmin: x-coordinate of lowest edge point
• 1/m: x-increment used for stepping from one scan line to the next
ymax xmin 1/m
ymax xmin 1/m
19
18
17
16
15
14
13
NULL NULL NULL NULL NULL NULL NULL
12
->
15
8
-2 ->
18
8
4/3
NULL
11 10 9 8 7
NULL NULL NULL NULL NULL
6
->
18
16
0 NULL
5 4
NULL NULL
3
->
15
2
0 NULL
2
NULL
1
->
3
8
-3 ->
6
8
8/5
NULL
D (16,18)
F (2,15)
A (2,3)
E
(8,12)
B (8,1)
C
(16,6)
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Processing steps
1. Set y to smallest y with entry in ET, i.e., y for the first non-empty bucket
2. Init Active Edge Table (AET) to be empty
3. Repeat until AET and ET are empty:
1. 2.
3. 4. 5.
scan line 9: AET pointer
Move form ET bucket y to the AET those edges whose ymin=y (entering edges)
Remove from AET those edges for which y=ymax (not involved in next scan line), then sort AET (remember: ET is presorted)
Fill desired pixel values on scan line y by using pairs of x-coords from AET Increment y by 1 (next scan line)
For each nonvertical edge remaining in AET, update x for new y
FA EF DE CD
9 2 0 9 2 -5/2
11 10 6/ 11 13 0 ! 4
CD
0 ! Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Aliasing
• Aliasing is caused by finite addressability of the display.
• Approximation of lines and circles with discrete points often gives a staircase appearance or “Jaggies”.
• Ideal rasterized line should be 1 pixel wide
Aliased rendering of the line
Desired line
• Choosing best y for each x (or visa versa) produces aliased raster lines
ymax x 1/m
AET pointer scan line 10:
DE
11 12 6/ 4
11 13
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Aliasing / Antialiasing Examples
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Antialiasing – solutions
• •
•
Aliasing can be smoothed out by using higher addressability.
If addressability is fixed but intensity is variable, use the intensity to control the address of a “virtual pixel”.
• Two adjacent pixels can be be used to give the impression of a point part way between them.
• The perceived location of the point is dependent upon the ratio of the intensities used at each.
• The impression of a pixel located halfway between two addressable points can be given by having two adjacent pixels at half intensity.
An antialiased line has a series of virtual pixels each located at the proper address.
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Antialiasing by Area Averaging
• Color multiple pixels for each x depending on coverage by ideal line
original
antialiased
magnified
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Polygon Aliasing
• Aliasing problems can be serious for polygons • Jaggedness of edges
• Small polygons neglected
• Need compositing, so color
of one polygon does not totally determine color of pixel
All three polygons should contribute to color
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
•
•
Line drawing algorithms such as Bresenham’s can easily be modified to implement virtual pixels. We use the distance (e = di/a) value to determine pixel intensities.
Three possible cases which occur during the Bresenham algorithm:
Antialiased Bresenham Lines
e > 0 A
e B
0 > e > -0.5 e < -0.5
AA
e
BB
e CCC
A = 0.5 + e
B = 1 - abs(e+0.5) C = 0
A = 0.5 + e
B = 1 - abs(e+0.5) C = 0
A = 0
B = 1 - abs(e+0.5) C = -0.5 - e
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Clipping and Visibility
• Clipping has much in common with hidden- surface removal
• In both cases, we are trying to remove objects that are not visible to the camera
• Often we can use visibility or occlusion testing early in the process to eliminate as many polygons as possible before going through the entire pipeline
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Hidden Surface Removal
• Object-space approach: use pairwise testing between polygons (objects)
partially obscuring can draw independently
• Worst case complexity O(n2) for n polygons
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Painter’s Algorithm
• Render polygons a back to front order so that polygons behind others are simply painted over
B behind A as seen by viewer
Fill B then A
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Depth Sort
• Requires ordering of polygons first
• O(n log n) calculation for ordering
• Not every polygon is either in front or behind all other polygons
• Order polygons and deal with easy cases first, harder later
Polygons sorted by distance from COP
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Depth sort cases
• Easy cases:
• Lies behind all other polygons (can render):
• Polygons overlap in z but not in either x or y (can render independently):
• Hard cases:
Overlap in all directions but can one is fully on one side of the other
cyclic overlap
penetration
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
•
•
plane of face has form ax + by +cz +d =0 but after normalization n = ( 0 0 1 0)T
need only test the sign of c
In OpenGL we can simply enable culling
Back-Face Removal (Culling)
"
•face is visible iff 90 # " # -90 equivalently cos " # 0
or v • n # 0
•
but may not work correctly if we have nonconvex objects
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Image Space Approach
• Look at each projector (nm for an n x m frame
buffer) and find closest of k polygons • Complexity O(nmk)
• Ray tracing
• z-buffer
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
z-Buffer Algorithm
• Use a depth buffer called the z-buffer to store the depth of the closest object at each pixel found so far
• As we render each polygon, compare the depth of each pixel to depth in z buffer
• If less, place shade of pixel in color buffer and update z buffer
• Efficency:
• If we work scan line by scan line as we move across a scan line,
the depth changes
satisfy a$x+b$y+c$z=0
• Along scan line
• In screen space $x = 1
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Scan-Line Algorithm
• Can combine shading and hsr through scan
line algorithm
scan line i: no need for depth information, can only be in no or one polygon
scan line j: need depth information only when in more than one polygon
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
Visibility Testing
• In realtime applications, eliminate as many objects as possible within the application
• Reduce burden on pipeline
• Reduce traffic on bus
• Partition space with Binary Spatial Partition (BSP) Tree
• Easy example: Consider 6 parallel polygons. The plane of A separates B and C from D, E and F
• Can continue recursively
• Plane of C separates B from A
• Plane of D separates E and F
• Can put this information in a BSP tree
• Use for visibility and occlusion testing
Realtime 3D Computer Graphics / Virtual Reality – WS 2006/2007 – Marc Erich Latoschik
top view
B
C
A D EF