Texturing, culling

​

Instructor: Christopher Rasmussen (cer@cis.udel.edu)

​

​

April 13, 2021 ❖ Lecture 15

Outline

• Texturing: Rasterization details
• Culling non-visible surfaces
• Viewing volume: Clipping
• Backface, occlusion: next time...

​

Texture mapping: Steps

• Creation: Where does the texture image come from?
• Geometry: Transformation from 3-D shape locations to 2-D texture image coordinates
• Rasterization: What to draw at each pixel (since texture coords. are floats)
• E.g., bilinear interpolation vs. nearest-neighbor

Texture mapping: Steps

• Creation: Where does the texture image come from?
• Geometry: Transformation from 3-D shape locations to 2-D texture image coordinates
• Rasterization: What to draw at each pixel (since texture coords. are floats)
• E.g., bilinear interpolation vs. nearest-neighbor

Texture mapping: Rasterization issue

Texture mapping: Rasterization issue

Texture mapping: Rasterization issue

Take "nearest neighbor" texel color or some kind of blend of surrounding texels?

Linear Interpolation (aka lerp)

• Parametric definition of a line segment:

p(t) = p₀ + t(p₁ - p₀), where t in [0, 1]

= p₀ - t p₀ + t p₁

= (1 - t)p₀ + t p₁

from Akenine-Möller & Haines

= lerp(p0, p1, t)

Bilinear interpolation for LIGHTING

GLSL linear vs. nearest filtering example

dest

I = texture image, I_dest = image we are rendering

Rasterization: Magnification and minification

​

​

​

​

​

• Magnification: Single screen pixel maps to area less than or equal to one texel

​

Magnification

Minification

from Angel

Rasterization: Magnification and minification

​

​

​

​

​

• Magnification: Single screen pixel maps to area less than or equal to one texel
• Minification: Single screen pixel area maps to area greater than one texel
• If texel area covered is much greater than 4, even bilinear filtering isn’t so great

Magnification

Minification

from Angel

GLSL linear vs. nearest filtering example

Filtering for minification

• Aliasing problem much like line rasterization
• Pixel maps to quadrilateral (pre-image) in texel space

image courtesy of D. Cohen-Or

Supersampling: Using more than BLI’s 4 texels

• Rasterize at higher resolution
• Regular grid pattern around each “normal” image pixel
• Irregular jittered sampling pattern reduces artifacts
• Combine multiple samples into one pixel via weighted average
• “Box” filter: All samples associated with a pixel have equal weight (i.e., directly take their average)
• Gaussian/cone filter: Sample weights inversely proportional to distance from associated pixel

​

from Hill

Regular supersampling

with 2x frequency

Mipmaps

• Filtering for minification is expensive, and different areas must be averaged depending on the amount of minification
• Idea:
• Prefilter entire texture image at different resolutions
• For each screen pixel, pick texture in mipmap at level of detail (LOD) that minimizes minification (i.e., pre-image area closest to 1)
• Do nearest or linear filtering in appropriate LOD texture image, or across levels

from Woo, et al.

WebGL mipmap example

Clipping

courtesy of L. McMillan

Clipping

courtesy of L. McMillan

Clipping

• Removal of portions of geometric primitives outside viewing volume (VV)
• Why?
• Optimization that saves computation which would otherwise be wasted on lighting, texturing, etc.
• Cases
• Trivial acceptance: Complete inside VV
• Trivial rejection: Completely outside VV
• Crossing clip plane(s): Partially outside, so must trim to fit
• Different primitives require different methods
• Points: Only trivial accept/reject
• Lines: Chop at intersection with clip plane
• Polygons: Must trim so as to maintain connectivity

​

courtesy of L. McMillan

Geometry pipeline

Coordinate change rigid transform

(View)

Perspective transformation

(and orthographic scaling)

(Projection)

Camera coordinates

Clip coordinates

Normalized device coordinates (CVV)

Window coordinates

Screen coordinates (pixels)

World coordinates

Model coordinates

Coordinate change rigid transform

(Model)

When to clip?

• The earlier in the pipeline invisible primitives are removed, the less computation is wasted on them
• However...difficulty of clipping problem depends on stage of geometry pipeline
• Camera coordinates: VV is a frustum, so clip planes are angled (dot product necessary for inside/outside (IO) test)
• Clip coordinates: CVV is an axis-aligned box (cube with corners at ±1 after perspective division), so clip planes are simple (IO test is simple greater-than/less-than comparison)
• NDC: Perspective division destroys true sign of point’s z---can’t distinguish between point at (x, y, z) and one at (-x, -y, -z). This allows points behind eye to be erroneously displayed
• Screen coordinates: Simple, but too late—nearly all of the work has already been done

​

Clipping: Basic issues

• Testing which side of a clip plane a point is on
• Which side of a line in 2-D
• How to trim primitives that span VV border
• Find the intersection of a line segment and a clip plane

​

from E. Angel

Cohen-Sutherland 2-D line clipping (not in textbook)

• Idea: Consider rectangle (the “viewing area” (VA)) as intersection of 4 half-planes defined by sides

VA

x_min

x_max

y_max

y_min

adapted from F. Pfenning

y < y_max

y > y_min

x > x_min

x < x_max

= ∩

Cohen-Sutherland clipping: Outcodes

• Test a line endpoint p = (x, y) against each of 4 half-planes and record whether it is outside the half-plane or not (T or F)
• These four T/F bits are p’s outcode o(p)

​

from Hill

Cohen-Sutherland clipping

• Outcodes partition plane around the viewing area
• Trivial line clipping cases
• Accept line (p₁, p₂): Both endpoints are inside the rectangle
• In terms of outcodes, this means o(p₁) = FFFF and o(p₂) = FFFF
• Reject line: Both endpoints outside rectangle on same side
• This means both points’ outcodes have a T at the same bit position—e.g., o(p₁) = FTTF and o(p₂) = FFTF

​

from Hill

Cohen-Sutherland clipping

• Tougher cases are what’s left

​

​

​

​

​

​

• Basic idea: Subdivide non-trivial lines by sequentially removing (aka clipping) portions outside rectangle edge lines until what’s left is trivial
• Arbitrary order: Left, right, bottom, top

adapted from E. Angel

Cohen-Sutherland: Algorithm

Computing the intersection point

• What is c = (c_x, c_y)?

​

adapted from Hill

Computing the intersection point

• What is c = (c_x, c_y)?
• Obviously, in this case c_x = x_max and c_y = a_y - d

​

adapted from Hill

Computing the intersection point

• What is c = (c_x, c_y)?
• Obviously, in this case c_x = x_max and c_y = a_y - d
• Noting that e = a_x - x_max and e/Δx = d/Δy , we can compute d = e Δy/Δx and obtain c_y

​

adapted from Hill

Computing the intersection point

• What is c = (c_x, c_y)?
• Obviously, in this case c_x = x_max and c_y = a_y - d
• Noting that e = a_x - x_max and e/Δx = d/Δy , we can compute d = e Δy/Δx and obtain c_y
• A similar approach works for the other clip lines

adapted from Hill

Line clipping: Notes

• C-S’s recursive clipping (up to 4 passes) is not optimal
• E.g., Liang-Barsky method can be faster
• C-S generalizable to 3-D (CVV)
• Instead of 4 half-planes there are 6 half-spaces (3-D volumes)
• Outcode has 6 bits (two more for near and far Z clip planes)

from E. Angel

from Hill

Clipping Triangles

• Four cases for the whole triangle:

​

​

​

​

​

​

​

​

Keep complete triangle

Throw away complete triangle

Keep triangular portion inside

Split quadrilateral portion inside into 2 triangles