Back-face Culling

Back-face Culling

Polygon is back-facing if:

    V.N > 0 

Back-face Culling

Polygon is back-facing if:

    V.N > 0 

Assuming view is along Z (v = (0, 0, 1))

    V.N = (0 + 0 + zn)

Back-face Culling

Polygon is back-facing if:

    V.N > 0 

Assuming view is along Z (v = (0, 0, 1))

    V.N = (0 + 0 + Zn)

Simplify further to

    if Zn > 0, then cull

Works for non-overlapping convex polyhedra

Back-face Culling

Polygon is back-facing if:

    V.N > 0 

Assuming view is along Z (v = (0, 0, 1))

    V.N = (0 + 0 + Zn)

Simplify further to

    if Zn > 0, then cull

Works for non-overlapping convex polyhedra

    with concave polyhedra, some hidden surfaces
              will not be culled

Painter's Algorithm

First polygon:
    (6, 3, 10), (11, 5, 10), (2, 2, 10)
    scan it in

Painter's Algorithm

Second polygon:
    (1, 2, 8), (12, 2, 8), (12, 6, 8), (1, 6, 8)
    scan it on top

Painter's Algorithm

Third polygon:
    (6, 5, 5), (14, 5, 5), (14, 10, 5), (6, 10, 5)
    scan it on top

Painter's Algorithm

Given
    List of Polygons { P1, P1, ... , P1 }
    An array Intensity [x, y]

Begin
    Sort polygon list on minimum Z 
         (largest Z-value comes first in sorted list)

    for each polygon P in selected list do
       for each pixel (x, y) that intersects P do
          Intensity [x, y] = intensity of P at (x, y)

    Display Intensity array

Painter's Algorithm: Cyclic Overlapping

Which order to scan?

Painter's Algorithm: Cyclic Overlapping

Split along line, then scan 1, 2, 3

Painter's Algorithm: Cyclic Overlapping

Which order to scan?

Painter's Algorithm: Cyclic Overlapping

Split along line, then scan 1, 2, 3, 4

(or split another polygon and scan accordingly)

Moral:

Painter's algorithm is easy and fast, except for detecting and splitting cycles and other ambiguities.

Depth-sort: Overlapping Surfaces

Assume you have sorted by maximum Z

Then if Z_min > Z'_max

the surfaces do not overlap (minimax test)

Depth-sort: Overlapping Surfaces

Assume you've selected by maximum Z

Then if Z_min > Z'_max

the surfaces do not overlap (minimax test)

Correct ordering of overlapping surfaces may be ambiguous.
Check it

Depth-sort: Overlapping Surfaces

Assume you've selected by maximum Z

Then if Z_min > Z'_max

the surfaces do not overlap (minimax test)

Correct ordering of overlapping surfaces may be ambiguous.
Check it

No problem: paint S then S'

Depth-sort: Overlapping Surfaces

Assume you've selected by maximum Z

Then if Z_min > Z'_max

the surfaces do not overlap (minimax test)

Correct ordering of overlapping surfaces may be ambiguous.
Check it

Problem: painting in either order gives incorrect result

Depth-sort: Overlapping Surfaces

Assume you've selected by maximum Z

Then if Z_min > Z'_max

the surfaces do not overlap (minimax test)

Correct ordering of overlapping surfaces may be ambiguous.
Check it

Problem?: naive order S S' S'', correct order S' S'', S

Depth-sort: Checking Order Ambiguity

(1) Bounding rectangles in xy plane do not overlap

- check overlap in x
x'_min > x_min or x_min > x'_min
=> no overlap

Depth-sort: Checking Order Ambiguity

(1) Bounding recrangles in xy plane do not overlap

- check overlap in x
x'_min > x_max or x_min > x'_max
=> no overlap

- check overlap in y
y'_min > y_max or y_min > y'_max
=> no overlap

Depth-sort: Checking Order Ambiguity

(2) Surface S is completely behind S' relative to viewing direction.

Depth-sort: Checking Order Ambiguity

(2) Surface S is completely behind S' relative to viewing direction.

- substitute all vertices of S into plane equation for S', if all are "inside" (<0), then there is no ambiguity

Depth-sort: Checking Order Ambiguity

(3) S' completely in front of S relative to viewing direction

Depth-sort: Checking Order Ambiguity

(3) S' completely in front of S relative to viewing direction

- substitute all vertices of S' into plane equation for S, if all are "outside" (>0), then there is no ambiguity

Depth-sort: Checking Order Ambiguity

(4) Projection of the two surfaces onto the viewing plane do not overlap

Depth-sort: Checking Order Ambiguity

(4) Projection of the two surfaces onto the viewing plane do not overlap

- test edges for intersection

rule out some pairs with minimax tests

(can eliminate 3-4 intersection, but not 1-2)

Depth-sort: Checking Order Ambiguity

(4) Projection of the two surfaces onto the viewing plane do not overlap

- test edges for intersection

rule out some pairs with minimax tests

(can eliminate 3-4 intersection, but not 1-2)

check slopes - parallel lines do not intersect

Depth-sort: Checking Order Ambiguity

(4) Projection of the two surfaces onto the viewing plane do not overlap

- test edges for intersection

rule out some pairs with minimax tests

(can eliminate 3-4 intersection, but not 1-2)

check slopes - parallel lines do not intersect

compute intersection points:

s = [ (X'₁ - X'₂)(Y₁ - Y'₁) - (X₁ - X'₁)(Y'₁ - Y'₂)]/D

t = [ (X₁ - X₂)(Y₁ - Y'₁) - (X₁ - X'₁)(Y₁ - Y₂)]/D

where

D = (X'₁ - X'₂)(Y₁ - Y₂) - (X₁ - X₂)(Y'₁ - Y'₂)

Z-Buffer

First polygon:
    (1, 1, 5), (7, 7, 5), (1, 7, 5)
    scan it in with depth

Z-Buffer

Second polygon:
    (3, 5, 9), (10, 5, 9), (10, 9, 9), (3, 9, 9)

Z-Buffer

Third polygon:
    (2, 6, 3), (2, 3, 8), (7, 3, 3)

Z-Buffer

Z-Buffer Algorithm

Given
    List of Polygons { P1, P1, ... , P1 }
    An array z-buffer [x, y] initialized to +infinity
    An array Intensity [x, y]

Begin
    for each polygon P in selected list do
       for each pixel (x, y) that intersects P do
          Calculate z-depth of P at (x, y)
	  if z-depth < z-buffer [x, y] then	     
	     Intensity [x, y] = intensity of P at (x, y)
	     z-buffer [x, y] = z-depth

    Display Intensity array

Z-Buffer: Calculating Z-Depth

from plane equation, depth at position (x, y):

z = (-Ax - By - D) / C

Z-Buffer: Calculating Z-Depth

from plane equation, depth at position (x, y):

z = (-Ax - By - D) / C

Incrementally across scan line (x+1, y):

z' = (-A(x+1) - By - D) / C

Z-Buffer: Calculating Z-Depth

from plane equation, depth at position (x, y):

z = (-Ax - By - D) / C

Incrementally across scan line (x+1, y):

z' = (-A(x+1) - By - D) / C

= (-Ax - By - D) / C - A/C

Z-Buffer: Calculating Z-Depth

from plane equation, depth at position (x, y):

z = (-Ax - By - D) / C

Incrementally across scan line (x+1, y):

z' = (-A(x+1) - By - D) / C

= (-Ax - By - D) / C - A/C

= z - A/C

Z-Buffer: Calculating Z-Depth

from plane equation, depth at position (x, y):

z = (-Ax - By - D) / C

Incrementally across scan line (x+1, y):

z' = (-A(x+1) - By - D) / C

= (-Ax - By - D) / C - A/C

= z - A/C

Incrementally between scan lines (x', y+1):

z' = (-A(x') - B(y+1) - D) / C

Z-Buffer: Calculating Z-Depth

from plane equation, depth at position (x, y):

z = (-Ax - By - D) / C

Incrementally across scan line (x+1, y):

z' = (-A(x+1) - By - D) / C

= (-Ax - By - D) / C - A/C

= z - A/C

Incrementally between scan lines (x', y+1):

z' = (-A(x') - B(y+1) - D) / C

using x' = x + 1/m

= (-A(x + 1/m) - B(y+1) - D) / C

Z-Buffer: Calculating Z-Depth

from plane equation, depth at position (x, y):

z = (-Ax - By - D) / C

Incrementally across scan line (x+1, y):

z' = (-A(x+1) - By - D) / C

= (-Ax - By - D) / C - A/C

= z - A/C

Incrementally between scan lines (x', y+1):

z' = (-A(x') - B(y+1) - D) / C

using x' = x + 1/m

= (-A(x + 1/m) - B(y+1) - D) / C

= z - (A/m + B) / C

Z-Buffer: Characteristics

Good:

• Easy to implement
• Requires no sorting of surfaces
• Easy to put in hardware

Z-Buffer: Characteristics

Good:

• Easy to implement
• Requires no sorting of surfaces
• Easy to put in hardware

Bad

• Requires lots of memory

  (about 9MB for 1280x1024 Display)

• Can alias badly

  (Only one sample per pixel)

• Can not handle transparent surfaces

A-Buffer method

Basically z-buffer with additional memory to consider contribution of multiple surfaces to a pixel

A-Buffer method

Basically z-buffer with additional memory to consider contribution of multiple surfaces to a pixel

Need to store:

• Color (RGB triple)
• Opacity
• Depth
• Percent area covered
• Surface ID
• Misc. rendering parameters
• Pointer to next

Taxonomy of Visibility Algorithms

Taxonomy of Visibility Algorithms

Taxonomy of Visibility Algorithms