[SOLVED] CS data structure algorithm CS580

CS580

Scan Line Rasterizer
HW2
Hidden Surfaces & Culling Algorithms
Ulrich Neumann
CS580
Computer Graphics Rendering

Scan Line Rasterizer
DDA is an incremental approach to interpolation (see wikipedia)
DDA uses slope dx/dy to compute tri edges at each scan line
Generic DDA has position start, end, current, and slope data
Add additional parameter value (Z) start, end, current, and slope data for interpolation
Assume conventions:
Screen origin is UL corner of screen
Screen coords (RH) -> X = right, Y = down, and Z into screen

X
Y
https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)
Incrementally compute edge coords at each scan line by stepping down (increment Y) along edges

1
2
3
3
2
1

Scan Line Algorithm
Sort verts by Y into (1-2, 2-3), and (1-3)(sort for sequence of use)
Setup edge DDAsfor (1-2), (2-3), (1-3)
Sort edges by L or R(2 possible configurations above figure)
Ex: Assign edge DDAs as L (1-2-3), and R (1-3)(for right-most tri above)
Recall:Use dx/dy slopes (1-2) < or > (1-3), OR y-intercept method, OR edge classifier
Advance (1-2) and (1-3) DDA current positions to top y-scan line (ceiling)
Setup span DDA on successive lines based on edge DDA position values
Set span DDA current and end positions to right and left edge values
Advance span current position to left-most covered pixel (ceiling)
Interpolate span position and parameters (Z) until current position > end
Test interpolated-Z against FB-Z for each pixel lowest Z wins
Write color value into FB pixel(default or computed color)
Switch from 1-2 edge to 2-3 edge when current 1-2 edge position > Y(2)
Continue spans until vert 3 is passed: current 1-3 edge position > Y(3)

1
2
3
3
2
1

interpolators init edges
Setup edge DDAsfor E(1-2), E(2-3), E(1-3)

E(1-2) {
start = V1(X,Y,Z)
end = V2(X,Y,Z)
current = V1 (X,Y,Z)
slopex = dx/dy(X2-X1)/(Y2-Y1)
slopez = dz/dy(Z2-Z1)/(Y2-Y1)
}
V3
V2
V1

interpolators advance edges
Advance (1-2) and (1-3) DDA current positions to top y-scan line (orange points)
Move down edges to first line
Y = ceil(V1(Y)) V1(Y)

E(1-2) {
start = V1(X,Y,Z)
end = V2(X,Y,Z)
current =
V1 (X + slopex Y),
V1 (Y + Y),
V1 (Z + slopez Y)
slopex = dx/dy(X2-X1)/(Y2-Y1)
slopez = dz/dy(Z2-Z1)/(Y2-Y1)
}
V3
V2
V1

Note: advanced points can determine L/R edges

interpolators span setup and advance
Setup span DDA on successive lines based on edge DDA values
Set span DDA current and end positions to right and left edge values

SPAN {
start = L(X, Z)
end = R(X, Z)
current = L (X, Z)
slopez = dz/dx(RZ-LZ)/(RX-LX)
}

Advance span current position to left-most covered pixel (red) X = ceil(LX) LX

SPAN {
start = L(X, Z)
end = R(X, Z)
current = LX + X, LZ + X slopez
slopez = dz/dx(RZ-LZ)/(RX-LX)
}
V3
V2
V1

L
R

HW2
Tris are pre-transformed into screen coordinates for HW2
Input file has tris with X,Y,Z ready for rasterization
Color is assigned for each tri

The renderer must do z-buffering
so you need to initialize z in
the frame buffer, in addition
to setting the background color

Initial z-value is MAXINT,
the maximum positive integer
value (farthest from viewpoint)

HW2.txt
Your assignment is to produce a working scan converter based on the files youre given below.
The API calls in rend.cpp *must* be provided just as they are outlined.
Remember to interpolate Z and do Z-buffer testing on each pixel write to the Display.
*** Changes in the API are not allowed ***
The standard application you are given must work without modification.
The renderer will be added to your display code from HW1.
If your display code is not yet correct, youll have to complete it since you need it now.
There are several other files there that will be useful.

Gz.h : Global definitions
Application2.cpp : new application that calls for your rend.cpp functions
rend.cpp : new skeleton file with API definition and comments
pot4.screen.asc : the Utah teapot triangle data transformed for scan conversion
pot4.ppm : the result of runningwith input file pot4.screen.asc to create pot4.ppm

The result images are made into a 256256 window.
Do not change the resolution/size of your display image since the transformation
is precomputed for that image size.

NOTE You mush initialize Z in your frame buffer in addition to the background color

Application API
View Application2.cpp
Use API calls to GzRender() to create the renderer
Use GzDefault() to initialize at the start of a new frame
Color is sent to renderer via the generic GzPutAttribute() call that also uses pointers to a token list and value list
A Triangle is sent to renderer via the GzPutTriangle() call that passes a pointer to a vertex structure defined in Gz.h
Note: *nameList points to a list of type tokens
and *valueList points to a list of parameters of those types
Note: a simple shading function is within the application and it computes a color for each triangle

Tokens and Values
int GzPutAttribute (int numAttributes,
GzToken*nameList,GzPointer *valueList)

List of Tokens(ints)List of values

GZ_RGB_COLOR Float Color [3]
….

Increment through tokens (ints) and use (sizeof) token type to increment the pointer through the value list
Only use GZ_RGB_COLOR for HW2, but other data will be passed in later HWs

int GzPutTriangle (int numParts,
GzToken*nameList,GzPointer*valueList)

Same with PutTriangle function only use GZ_POSITION token for HW2 that token means valueList is a pointer to 3 vertex positionsXYZ, XYZ, XYZ

Renderer API
Look at Rend.cpp
Note separate GzPutAttribute() and GzPutTriangle() calls
Tokens for types in PutTriangle call only use GZ_POSITION right now no other triangle data for HW2
Color is passed to Renderer as RGB in an array of floats defined over the range [0.0, 1.0]
Ctoi( ) function converts float color range of [0.0, 1.0] to GzIntensity 12-bit range for PutPixel calls to the display
Bound the float range to ensure conversion doesnt overflow 12-bit range (0-4095)

The Original Scan Line Algorithm
The classic scan line algorithm was a variation of what is described in the prior slides.
Walk the screen scan lines (top to bottom) and deal with all triangles that intersect the current line.This requires only one scan-line of Z-buffer for hidden surface calculations.

Y-sort all triangles based on their lowest-Y vertex.Put all of them into the unrendered list
For all scan lines {
Test the pool of unrendered tris to see if any start on the current line.If so, move them to the current tri list.

Render the current list tris for by incrementing their DDAs to the current line do the same edge stepping and span stepping we discussed.Keep all the DDA parameters for a triangle in each tri data structure since well need them on subsequent lines.Use Z-buffering for all pixel writes.

Increment the scan line and test all current list tris for completion.
Remove any completed tris from the current list.
}

HSR vs Culling
Hidden Surface Removal Algorithms
Finding the visible surface at each pixel during rasterization
Required to produce a correct image

Culling Algorithms
Finding surfaces that will not be visible and removing them before rasterization
Optional to improve performance

Hidden Line Removal (HLR)
Edge or line drawing also requires visibility methods
wireframe lines are hard to deal with
simple z-buffer does not work when the renderer only draws lines (outlines of polygons)
edge-crossing and object sorting methods

hidden line drawing provides depth sense
no line hiding means no depth sense

Raycasting
For every ray through a pixel,
Perform a ray-intersection with every object
Keep the closest intersection
Image plane
View point
or focal point

Painters Algorithm (1)
Just render in order front to back or back to front
view-dependent ordering needs to be computed very frame
Simple cases allow sorting by a simple per polygon test :(not pixel test)
Z of all verts of one poly are < or > than all verts of another
top
view

front
view

View (Z) direction
All B vertex Z-values are less than
all R vertex Z-values

Painters Algorithm (2)
Failure cases:
Vertex Z-sort is ambiguous when all vert test fails
Cant tell if B in front of R or not(in examples below)
Vert sort of B-R and G-R produce same order

Cannot resolve cycles or overlapping surfaces
top
view

front
view

View (Z) direction

Warnock algorithm
Overcomes problem of view dependent ordering and intersecting geometry by divide and conquer strategy
Subdivide screen until a leaf region has a simple front/back relationship
Leaf regions have one or zero surfaces visible, and smallest region is usually a pixel
Usually use quad tree subdivision
Useful for curved surfaces and antialiasing where the subdivision is done to sub-pixel levels
Efficient and focuses work where needed adaptively
a common theme in graphics

Think of z-buffer as a fixed subdivision to pixel regions

Area Subdivision (Warnock)
Initialize the area to be the image plane
Four cases:
No polygons in area: done
One polygon in area: draw it
Pixel sized area: draw closest polygon
Front polygon covers area: draw it
Otherwise, subdivide and recurse

BSP-Tree
A view-independent binary tree structure that allows a view-dependent front-to-back or back-to-front traversal of surfaces
use Painters Algorithm with back-to-front traversal
useful for transparency full depth-sort of all surfaces
fast no Z-calculation or testing per pixel
more detail in later class

Z-buffer
Compare each new surface pixels depth to current frame-buffer pixel value
Compare FB-Z with new triangle pixel-Z
Lowest Z-value (front-most) wins and becomes the new FB pixel
Most common today due to cheap/fast memory

Advantages
simple
reasonably efficient
Disadvantages
increased memory & bandwidth
z-quantization/accuracy limits
over-rendering
no support for transparency

Culling: Skipping Triangles
Culling methods reduce the number of triangles
that need to be rasterized for a scene image

Portals precompute visible (or invisible) sets
of triangles for view-point regions (precompute once)

Frustum cull skip triangles that fall completely
off screen (check every triangle every frame)

Backface cull skip triangles for closed objects that are facing away from the camera
(check every triangle every frame)

Culling With Portals
Useful concept for buildings and other static scenes
Represent the environment as a graph of Nodes which are bounded areas of visible triangles

Graphs are precomputed for view positions (optionally also directions)
Edges are portals through which Nodes are visible
All potentially-visible triangles are included in a graph

Each room triangle set is a Node

Construct a graph of all visible Nodes from any view point in each room

When rendering: use the graph to determine all Nodes visible from current position and render only those Node triangle sets

Check if entire object lies outside the frustum created by extending the four screen edges into the viewing volume
Simplest test is to skip a triangle
iff all its vertices are beyond
the same screen edge
(e.g., to the right of the screen)

Culling by View Frustum
image

image

skip, this
meets the
cull test
criteria
verts are all
off-screen, but
not off the same
edge, so dont skip

Backface Culling (1)
For closed (water-tight) objects, surfaces with oriented-normals facing away from the camera (called back-facing) are never visible
The inner surfaces of closed objects are never seen
Oriented-normals (N) face outward from the outer surface side
Below, the red surfaces have normals that face the viewpoint P so they are rendered.The blue surface normals face away so they can be skipped since the front (red) surfaces will always occlude the rear (blue) ones.
If triangle models include an oriented surface-normal vector N, then we can find and skip backfacing triangles:

If (View N) > 0, then skip the triangle

View is a vector from the view-point P
to any point (or vertex) on the surface

Note: our teapot model does not have
oriented-normal vectors it is not closed or water-tight
N
View
P

Backface Culling (2)
Alternatively, rather than adding a surface-normal to a triangle data structure, the triangle vertex sequence can encode face orientation
When viewed from front face, the vertex sequence V0,V1,V2 appears in clock-wise order
When viewed from the back face, the same vertex sequence appears counter clock-wise
Example (right image) shows RGB dots to illustrate vertex sequence for front and back facing triangles

With BF-culling, all the back-face triangles are skipped

Backface Cull
Wireframe rendering with BF-cull shows missing surfaces at top of spout and crack around lid (left image)
Such problems occur when models are not closed or watertight

BF-cull
No BF-cull

Frustums
The view frustum is formed by a view point, a view direction, and a view plane
The field of view (FOV) is the angle that fits the view plane (or image plane) into the frustum (horizontal and vertical FOV)
The image is created by projecting objects in the frustum to the focal point the projections pass through the image plane (more about this later)
Frame buffer pixels are sample points on the view (or image) plane

Horizontal FOV
Vertical FOV

Frustums and Clipping
Clipping to the view frustum ensures that only visible triangles (or fragments) are drawn into the frame buffer
Trivial clipping to frustum sides is done in the HW1 display by checking for valid pixel addresses
A far clip plane can be useful, but we
dont need or use one in our HWs
A near clip plane is needed to eliminate
objects behind the image plane
in HW3 (details
coming later)
Our near clip plane
is the image
plane at Z = 0
(screen space)