CHAPTER 7 - Implementation 1
Objectives
- Introduce basic implementation strategies (how rendering algorithms are performed?-> so we can provide efficient implementations ->what is supported in hardware?)
- Clipping
- Scan conversion
Meta Algorithms
- Consider two approaches to rendering a scene with opaque objects
- For every pixel, determine which object
that projects on the pixel is closest to the viewer and compute the
shade of this pixel
- Ray tracing paradigm
- For every object, determine which pixels
it covers and shade these pixels
- Pipeline approach as used in OpenGL ***
- Must keep track of depths
Common Tasks
- Modeling (application side)
- Pre Clipping: Back face culling and frustum culling
Back Face Culling
A solid polyhedron is an object that completely encloses its volume. All surface normals for the polyhedron point to the outside. Any normal that points away from the observer lies on a back face of the polyhedron. Back faces are not visible to the observer and should be removed or culled during the visibility determination.
Back faces may be easily recognized in the following manner:
compute the dot product of the normal vector for the polygon with a vector from the center of projection to the polygon. If the result is negative then the polygon is back facing.
Frustum Culling
All objects outside the view volume should be removed before traveling through the rendering pipeline.- Transformations
- Geometric Processing (front
end processing - 3D, floating point)
- View volume normalization (orthographic)
- Clipping
- Hidden surface removal
- Shading
- Projection
- Rasterization or scan conversion (2D - what pixels lie inside the 2D polygon?)
- Display
- Antialiasing
Line Segment Clipping (CLIPPER)
- 2D against clipping window
- 3D against clipping volume
- Easy for line segments and convex polygons
- Hard for curves and text
- Convert to lines and polygons first
Clipping 2D Line Segments
- Brute force approach: compute
intersections with all sides of clipping window
- Inefficient: one floating point division per intersection
- Let Wr be the right clipping extent, then Wr = x
- Let (x0, y0) be the point G, (x1, y1) be the point H
- If line segment GH intersects Wr then using the parametric line equation
- t = (Wr - x0) / (x1 - x0) for t in the interval [0, 1]
- t can then be substituted into
- y(t) = (1 - t)( y0) + (t)(y1) to find the y intersection
Cohen-Sutherland Algorithm
- Idea: eliminate as many cases as possible without computing intersections
- Start with four lines that determine the sides of the clipping window, breaking space into nine regions with clip rectangle specifying the center finite region.
The Cases
- Case 1: both endpoints of line segment
inside all four lines
- Draw (accept) line segment as is
- Case 2: both endpoints outside all lines
and on same side of a line
- Discard (reject) the line segment
The Cases
- Case 3: One endpoint inside, one outside
- Must do one intersection
- Case 4: Both outside
- May have part inside
- Must do at least one intersection and at most two intersections
Defining Outcodes
- For each endpoint, define an outcode>
- Outcodes divide space into 9 regions
- Computation of outcode requires at most 4 floating point subtractions (for each endpoint)
Using Outcodes
- Consider the 5 cases below
- AB: outcode(A) = outcode(B) = 0 => !(outcode(A) | outcode(B))
- Accept line segment
Using Outcodes
- CD: outcode (C) = 0, outcode(D) != 0
- Compute intersection
- Location of 1 in outcode(D) determines which edge to intersect with
- Note if there were a segment from A to a point in a region with 2 ones in outcode, we might have to do two intersections
Using Outcodes
- EF: outcode(E) & outcode(F) != 0
- Both outcodes have a 1 bit in the same place
- Line segment is outside of corresponding side of clipping window
- reject
Using Outcodes
- GH and IJ: same outcodes, neither zero but
logical AND yields zero
- Shorten line segment by intersecting with one of sides of window
- Compute outcode of intersection (new endpoint of shortened line segment)
- Reexecute algorithm
>
Efficiency
- In many applications, the clipping window
is small relative to the size of the whole data base
- Most line segments are outside one or more sides of the window and can be eliminated based on their outcodes (boolean operations)
- Inefficiency when code has to be reexecuted for line segments that must be shortened in more than one step (executed recursively)
Cohen Sutherland in 3D
- Use 6-bit outcodes
- When needed, clip line segment against planes
Liang-Barsky Clipping (more efficient)
- Consider the parametric form of a line
segment
- p(
) = (1-)p1+
p2, 0<= <= 1
- p(
- We can distinguish between the cases by
looking at the ordering of the values of
where the line segment crosses the clip lines that determine the window
Liang-Barsky Clipping
If the line is parallel to a clip boundary
this special case is handled easily and in the case where it is not
parallel
- In (a): 1 > 4
> 3 > 2
> 1 > 0 (23
defines new clipped line)
- Intersect right, top, left, bottom (extended sides of clip region): shorten
- In (b): 1 > 4
> 2 > 3
> 1 > 0
- Intersect right, left, top, bottom (extended sides of clip region): reject
- Other cases are argued in a similar manner
>
Advantages
- Can accept/reject as easily as with Cohen-Sutherland
- Using values of ,
we do not have to use algorithm recursively as with C-S
- Intersection tests do not require a floating point division
- Extends to 3D (add parametric equation for z and consider 6 intersections with clipping boundaries)
Clipping and Normalization
- General clipping in 3D requires intersection of line segments against arbitrary plane
- Example: oblique view
Plane-Line Intersections (6 multiplications- 2 each for x, y, z - and 1 division)
>
Normalized Form
- Normalization is part of viewing (pre clipping) but after normalization, we clip against sides of right parallelpiped
- Typical intersection calculation now requires only a floating point subtraction, e.g. is x > xmax ?
