10.Vis2

Taxonomy of Visibility Algorithms

Scan Line Algorithm

(1) Sort polygons into sorted surface table (SST) based on Y

(2) Initialize y and active surface table (AST)

y = first nonempty scanline

AST = SST [ y ]

(3) Repeat until AST and SST are empty

identify spans for this scanline (sorted on x)

For each span

determine visible element (based on z)

fill pixel intensities with values from visible element

Update AST

remove exhausted polygons

y++

update x intercepts

resort AST on x

add entering polygons

(4) Display Intensity Array

Scan Line Visibility Algorithm

Scanline [alpha]:

AST: ABC

spans:

0 -> x₁

x₁ -> x₂

x₂ -> max

Scan Line Visibility Algorithm

Scanline [alpha]:

AST: ABC

spans:

0 -> x₁

x₁ -> x₂ : Fill ABC

x₂ -> max

Scan Line Visibility Algorithm

Scanline [beta]:

AST: ABC DEF

spans:

0 -> x₁

x₁ -> x₂

x₂ -> x₃

x₃ -> x₄

x₄ -> max

Scan Line Visibility Algorithm

Scanline [beta]:

AST: ABC DEF

spans:

0 -> x₁

x₁ -> x₂ : Fill ABC

x₂ -> x₃

x₃ -> x₄ : Fill DEF

x₄ -> max

Scan Line Visibility Algorithm

Scanline [gamma]:

AST: ABC DEF

spans:

0 -> x₁

x₁ -> x₂

x₂ -> x₃

x₃ -> x₄

x₄ -> max

Scan Line Visibility Algorithm

Scanline [gamma]:

AST: ABC DEF

spans:

0 -> x₁

x₁ -> x₂ : Fill ABC

x₂ -> x₃

x₃ -> x₄ : Fill DEF

x₄ -> max

Scan Line Visibility Algorithm

Scanline [gamma]:

AST: ABC DEF

spans:

0 -> x₁

x₁ -> x₂ : Fill ABC

x₂ -> x₃ : Fill DEF

x₃ -> x₄ : Fill DEF

x₄ -> max

Scan Line Visibility Algorithm

Scanline [gamma]+1:

AST: ABC DEF

spans:

0 -> x₁

x₁ -> x₂ : Fill ABC

x₂ -> x₃ : Fill DEF

x₃ -> x₄ : Fill DEF

x₄ -> max

Scan Line Visibility Algorithm

Scanline [gamma]+1:

AST: ABC DEF

spans:

0 -> x₁

x₁ -> x₂ : Fill ABC

x₂ -> x₃ : Fill DEF

x₃ -> x₄ : Fill DEF

x₄ -> max

Scan Line Visibility Algorithm

Scanline [gamma]+2:

AST: ABC DEF

spans:

0 -> x₁

x₁ -> x₂ : Fill ABC

x₂ -> x₃

x₃ -> x₄ : Fill DEF

x₄ -> max

Characteristics of Scan Line Algorithm

Good

little memory required

can generate scan lines as required

can anti-alias within scan line

fast

simplification of problem simplifies geometry

can exploit coherence

Bad

fairly complicated to implement

difficult to anti-alias between scanlines

Ray-Tracing Algorithm

Given
    List of polygons { P₁, P₂, ..., P_n }
    An array of intensity [ x, y ]

{
    For each pixel (x, y) {
        form a ray R in object space through the
	    camera position C and the pixel (x, y)

        Intensity [ x, y ] = trace ( R )
    }

    Display array Intensity
}

Ray-Tracing Algorithm

Given
    List of polygons { P₁, P₂, ..., P_n }
    An array of intensity [ x, y ]

{
    For each pixel (x, y) {
        form a ray R in object space through the
	    camera position C and the pixel (x, y)

        Intensity [ x, y ] = trace ( R )
    }

    Display array Intensity
}

intensity Function  trace ( Ray )
{
    For each polygon P in the scene {
        calculate the intersection of P and the ray R
    }
    
    If ( The ray R hits no polygon ) {
        return ( background intensity )
    }
    else {
        find the polygon P with the closest intersection
	calculate intensity I at intersection point
	return ( I )
    }
}

Ray-Tracing Algorithm

Given
    List of polygons { P₁, P₂, ..., P_n }
    An array of intensity [ x, y ]

{
    For each pixel (x, y) {
        form a ray R in object space through the
	    camera position C and the pixel (x, y)

        Intensity [ x, y ] = trace ( R )
    }

    Display array Intensity
}

intensity Function  trace ( Ray )
{
    For each polygon P in the scene {
        calculate the intersection of P and the ray R
    }
    
    If ( The ray R hits no polygon ) {
        return ( background intensity )
    }
    else {
        find the polygon P with the closest intersection
	calculate intensity I at intersection point
	return ( Illumination model ( I, 
             trace (reflect ), trace ( refract ) ) )
    }
}

Ray-Tracing Algorithm

Presorted

Given
    List of polygons { P₁, P₂, ..., P_n }
    An array of intensity [ x, y ]

{
    Sort polygon list by minimum Z
    For each pixel (x, y) {
        form a ray R in object space through the
	    camera position C and the pixel (x, y)

        Intensity [ x, y ] = trace ( R )
    }

    Display array Intensity
}

intensity Function  trace ( Ray )
{
    While no intersection and polygons remaining {
        calculate the intersection of P and the ray R
    }
    
    If ( The ray R hits no polygon ) {
        return ( background intensity )
    }
    else {
	calculate intensity I at intersection point
	return ( Illumination model ( I, 
             trace (reflect ), trace ( refract ) ) )
    }
}

Ray-Tracing Algorithm

Presorted

Given
    List of polygons { P₁, P₂, ..., P_n }
    An array of intensity [ x, y ]

{
    Sort polygon list by minimum Z
    For each pixel (x, y) {
        form a ray R in object space through the
	    camera position C and the pixel (x, y)

        Intensity [ x, y ] = trace ( R )
    }

    Display array Intensity
}

intensity Function  trace ( Ray )
{
    While no intersection and polygons remaining {
        calculate the intersection of P and the ray R
    }
    
    Check for intersections with overlapping polygons

    If ( The ray R hits no polygon ) {
        return ( background intensity )
    }
    else {
	calculate intensity I at intersection point
	return ( Illumination model ( I, 
             trace (reflect ), trace ( refract ) ) )
    }
}

Ray-Tracing Algorithm

Presorted

Given
    List of polygons { P₁, P₂, ..., P_n }
    An array of intensity [ x, y ]

{
    Sort polygon list by minimum Z
    For each pixel (x, y) {
        form a ray R in object space through the
	    camera position C and the pixel (x, y)

        Intensity [ x, y ] = trace ( R )
    }

    Display array Intensity
}

intensity Function  trace ( Ray )
{
    While no intersection and polygons remaining {
        calculate the intersection of P and the ray R
    }
    
    Check for intersections with overlapping polygons

    If ( The ray R hits no polygon ) {
        return ( background intensity )
    }
    else {
	calculate intensity I at intersection point
	return ( Illumination model ( I, 
	     trace (reflect ), trace ( refract ) ) )
	        z-sort no longer useful
    }
}

Calculating Intersections

Define ray parametrically:

x = x₀ + t(x₁ - x₀)

y = y₀ + t(y₁ - y₀)

z = z₀ + t(z₁ - z₀)

Calculating Intersections

Define ray parametrically:

x = x₀ + t(x₁ - x₀)

y = y₀ + t(y₁ - y₀)

z = z₀ + t(z₁ - z₀)

If (x₀, y₀, z₀) is center of projection and (x₁, y₁, z₁) is center of pixel, then

0 <= t <= 1 : points between those locations

t < 0 : points behind viewer

t > 1 : points beyond view window

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

(1) What is intersection of ray and plane containing polygon?

Plane : Ax + By + Cz + D = 0

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

(1) What is intersection of ray and plane containing polygon?

Plane : Ax + By + Cz + D = 0

Substituting for x, y, z:

A(x₀ + t^.[delta]x) + B(y₀ + t^.[delta]y) + C(z₀ + t^.[delta]z) + D = 0

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

(1) What is intersection of ray and plane containing polygon?

Plane : Ax + By + Cz + D = 0

Substituting for x, y, z:

A(x₀ + t^.[delta]x) + B(y₀ + t^.[delta]y) + C(z₀ + t^.[delta]z) + D = 0

t(A^.[delta]x + B^.[delta]y + C^.[delta]z) + (Ax₀ + By₀ + Cz₀ + D) = 0

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

(1) What is intersection of ray and plane containing polygon?

Plane : Ax + By + Cz + D = 0

Substituting for x, y, z:

A(x₀ + t^.[delta]x) + B(y₀ + t^.[delta]y) + C(z₀ + t^.[delta]z) + D = 0

t(A^.[delta]x + B^.[delta]y + C^.[delta]z) + (Ax₀ + By₀ + Cz₀ + D) = 0

t = - (Ax₀ + By₀ + Cz₀ + D) / (A^.[delta]x + B^.[delta]y + C^.[delta]z)

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

(1) What is intersection of ray and plane containing polygon?

Plane : Ax + By + Cz + D = 0

Substituting for x, y, z:

A(x₀ + t^.[delta]x) + B(y₀ + t^.[delta]y) + C(z₀ + t^.[delta]z) + D = 0

t(A^.[delta]x + B^.[delta]y + C^.[delta]z) + (Ax₀ + By₀ + Cz₀ + D) = 0

t = - (Ax₀ + By₀ + Cz₀ + D) / (A^.[delta]x + B^.[delta]y + C^.[delta]z)

(2) Does ray/plane intersection point lie in polygon?

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

(1) What is intersection of ray and plane containing polygon?

Plane : Ax + By + Cz + D = 0

Substituting for x, y, z:

A(x₀ + t^.[delta]x) + B(y₀ + t^.[delta]y) + C(z₀ + t^.[delta]z) + D = 0

t(A^.[delta]x + B^.[delta]y + C^.[delta]z) + (Ax₀ + By₀ + Cz₀ + D) = 0

t = - (Ax₀ + By₀ + Cz₀ + D) / (A^.[delta]x + B^.[delta]y + C^.[delta]z)

(2) Does ray/plane intersection point lie in polygon?

Substitute into line equations for polygon edges
does point lie inside all edges?

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

(1) What is intersection of ray and plane containing polygon?

Plane : Ax + By + Cz + D = 0

Substituting for x, y, z:

A(x₀ + t^.[delta]x) + B(y₀ + t^.[delta]y) + C(z₀ + t^.[delta]z) + D = 0

t(A^.[delta]x + B^.[delta]y + C^.[delta]z) + (Ax₀ + By₀ + Cz₀ + D) = 0

t = - (Ax₀ + By₀ + Cz₀ + D) / (A^.[delta]x + B^.[delta]y + C^.[delta]z)

(2) Does ray/plane intersection point lie in polygon?

Substitute into line equations for polygon edges
does point lie inside all edges? <= convex!
Count edge crossings of ray from point to infinity

odd : inside
even : outside

Calculating Intersections : Polygons

Define ray parametrically:

x = x₀ + t^.[delta]x

y = y₀ + t^.[delta]y

z = z₀ + t^.[delta]z

(1) What is intersection of ray and plane containing polygon?

Plane : Ax + By + Cz + D = 0

Substituting for x, y, z:

A(x₀ + t^.[delta]x) + B(y₀ + t^.[delta]y) + C(z₀ + t^.[delta]z) + D = 0

t(A^.[delta]x + B^.[delta]y + C^.[delta]z) + (Ax₀ + By₀ + Cz₀ + D) = 0

t = - (Ax₀ + By₀ + Cz₀ + D) / (A^.[delta]x + B^.[delta]y + C^.[delta]z)

(2) Does ray/plane intersection point lie in polygon?

Substitute into line equations for polygon edges
does point lie inside all edges? <= convex!
Count edge crossings of ray from point to infinity

odd : inside
even : outside
Winding number testing

Determining if Point is in Polygon

1 corssing => inside
0,2 corssing => outside

Determining if Point is in Polygon

odd number of corssings => inside

Determining if Point is in Polygon

odd number of corssings => inside
even number of corssings => outside

Determining if Point is in Polygon

Self intersecting polygon

Odd even rule

Count each crossing as one

Determining if Point is in Polygon

Self intersecting polygon

Odd even rule

Count each crossing as one

Determining if Point is in Polygon

Self intersecting polygon

Odd even rule

Count each crossing as one

Determining if Point is in Polygon

Self intersecting polygon

Nonzero winding number rule

Determining if Point is in Polygon

Self intersecting polygon

Nonzero winding number rule

Count number of times border wraps point

+ clockwise

- counterclockwise

NC = 0 : outside
NC != 0 : inside

Ray-Tracing: Characteristics

Good:

Simple to implement
Minimal memory required
Easy to extend

Reflaction
Refraction
Other geometric primitives

Ray-Tracing: Characteristics

Good:

Simple to implement
Minimal memory required
Easy to extend

Reflaction
Refraction
Other geometric primitives

Bad

Aliasing
Computationally intensive

Intersections expensive (75 - 95% of rendering time)
Lots of rays

Taxonomy of Visibility Algorithms

BSP Tree Method : Building the Tree

BSPTree MakeBSP ( Polygon list ) 
{
   if ( list is empty )
      return null

   else {
      root = some polygon ; remove it from the list
      backlist = frontlist = null

      for ( each remaining polygon in the list ) {
         if ( p in front of root ) {
	    add to list ( p, front list )
	 }
	 else if ( p in back of root ) {
	    add to list ( p, back list )
         }
	 else {
	    split polygon ( p, root, frontpart, backpart )
	    add to list ( frontpart, front list )
	    add to list ( backpart, back list )
	 }
      }
      return ( combine tree ( MakeBSP ( front list ), root,
                              MakeBSP ( back list ) ) )
   }
}

Building a BSP Tree

Use 3 as root, split on its plane.

Polygon 5 split into 5a and 5b

Building a BSP Tree

Split left subtree at 2

Building a BSP Tree

Split right subtree at 4

Building a BSP Tree

Tree if splits are made at 5, 4, 3, 1

BSP Tree Method : Displaying the Tree

DisplayBSP ( tree )
{
   if ( tree not empty ) {
      if ( viewer in front of root ) {
         DisplayBSP ( tree -> back )
	 DisplayPolygon ( tree -> root )
	 DisplayBSP ( tree -> front )
      }
      else {
         DisplayBSP ( tree -> front )
	 DisplayPolygon ( tree -> root )
	 DisplayBSP ( tree -> back )
      }
   }
}

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self
				 display back

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self
				 display back

      at 5b : viewpoint on back -> display front (none)
                                 display self
				 display back (none)

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self
				 display back

      at 5b : viewpoint on back -> display front
                                 display self
				 display back (none)
		display self

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self
				 display back

      at 5b : viewpoint on back -> display front (none)
                                 display self
				 display back (none)
		display self
		display front

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self
				 display back

      at 5b : viewpoint on back -> display front (none)
                                 display self
				 display back (none)
		display self
		display front
      at 2 : viewpoint on back -> display front first

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self
				 display back

      at 5b : viewpoint on back -> display front (none)
                                 display self
				 display back (none)
		display self
		display front
      at 2 : viewpoint on back -> display front first 
         at 5a : viewpoint on back -> display front (none)
                                      display self
				      display back (none)

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self
				 display back

      at 5b : viewpoint on back -> display front (none)
                                 display self
				 display back (none)
		display self
		display front
      at 2 : viewpoint on back -> display front first 
         at 5a : viewpoint on back -> display front (none)
                                      display self
				      display back (none)
                                 display self

BSP Tree Display

For view point at C
   at 3 : viewpoint on front -> display back first
      at 4 : viewpoint on back -> display front first (none)
                                 display self
				 display back

      at 5b : viewpoint on back -> display front (none)
                                 display self
				 display back (none)
		display self
		display front
      at 2 : viewpoint on back -> display front first 
         at 5a : viewpoint on back -> display front (none)
                                      display self
				      display back (none)
                                 display self
         at 1 : viewpoint on back ->  display front (none)
                                      display self
				      display back (none)

Made by dynaPage 0.2