Visible Surface Detection Methods(VSD)

Views:

Category: Education

Presentation Description

Visible Surface Detection Methods(VSD)

Presentation Transcript

Visible Surface Detection Methods(VSD)orHidden Surface Removal(HSR)ORocclusion culling (OC) :

Visible Surface Detection Methods(VSD)orHidden Surface Removal(HSR)ORocclusion culling (OC)

Slide 2:

We are viewing from a position and have to identify those parts of the scene that are visible from the viewing position. There are many algorithms used for this purpose. These algorithms are called visible surface detection method or hidden surface removal methods.

Slide 3:

Back face detection Depth-buffer method A-buffer method Scan-line method Depth Sorting Area Subdivision method

Slide 4:

Determination of which algorithm to be applied for a particular application involves the following conditions. Complexity of the scene. Type of the object to be displayed. Available equipment. Type of display needed.(static or animated)

Two Main Approaches :

Two Main Approaches Visible surface detection algorithms are broadly classified as: Object Space Methods: Compares objects and parts of objects to each other within the scene definition to determine which surfaces are visible Image Space Methods: Visibility is decided point-by-point at each pixel position on the projection plane Image space methods are by far the more common

Slide 6:

Image space algorithms are called point sampling. They perform visibility determination over discrete areas giving results.

Slide 8:

Image space methods Z buffer A buffer Scan line Object space Back face detection Both Depth sorting, Area sub division

Back-Face Detection :

Back-Face Detection A polygon has two faces. Front face Back face.

Slide 11:

A point (x, y, z) is inside a polygon surface with plane parameters A, B, C & D if i.e it is in back face A point (x, y, z) is outside a polygon surface with plane parameters A, B, C & D if i.e it is in front face

Slide 12:

Let ‘N’ be the normal vector to a polygon surface, which has Cartesian coordinates (A,B,C) and ‘V’ is the vector in the viewing direction, then the polygon in the back face if

Slide 14:

If object descriptions have been converted to projection coordinates and our viewing direction is parallel to the viewing Zv axis, then V= (0,0,Vz) and V. N= Vz C So that we only need to consider the sign of C, the z component of the normal vector N.

Slide 15:

In a right handed viewing system with the viewing direction along the negative zv-axis, the polygon is a back face if c<0. We cannot see any face whose normal has z component C=0. We can label any polygon as a back face if its normal vector has z-component value

Slide 17:

In general back-face detection can be expected to eliminate about half of the polygon surfaces in a scene from further visibility tests. We need better techniques to handle these kind of situations.

Depth-Buffer Method :

Depth-Buffer Method

Slide 19:

It is a commonly used image space approach to detect visible surface. It compares the surface depth at each pixel on the projection plane. It is also known as Z-buffer method , because object depth is usually from the view plane along the Z- axis.

Slide 20:

In depth buffer two buffers are used. Depth buffer (Z buffer) Refresh buffer

Depth buffer (Z buffer) :

Depth buffer (Z buffer) Used to store the depth values for each (x,y) position , as surfaces are proceeded.

Refresh buffer :

Refresh buffer To store the intensity value at each position(x,y).

Slide 23:

Z-Buffer has memory corresponding to each pixel location Usually, 16 to 20 bits/location.

Slide 24:

We can implement the depth- buffer algorithm in normalized coordinates. So that z values range from 0 at the back clipping plane to zmax at the front clipping plane.

Depth-Buffer (Z-Buffer) :

Depth-Buffer (Z-Buffer) Initialize Each z-buffer location  Max z value Each frame buffer location  background color For each polygon: Compute z(x,y), polygon depth at the pixel (x,y) If z(x,y) < z-buffer value at pixel (x,y), then z buffer(x,y)  z(x,y) pixel(x,y)  color of polygon at (x,y)

Depth Calculation :

Depth Calculation Calculate the z-value on the plane Incremental calculation

For horizontal movement :

For horizontal movement For vertical movement

Iterative Calculations (cont…) :

Iterative Calculations (cont…) top scan line bottom scan line y scan line y - 1 scan line x x’

Depth-Buffer (Z-Buffer) :

Depth-Buffer (Z-Buffer) Advantages/Disadvantages Lots of memory Linear performance Polygons may be processed in any order Modifications needed to implement antialiasing, transparency, translucency effects Commonly implemented in hardware  very fast

A-Buffer Method An Antialiased, Area-Averaged, Accumulation - Buffer :

A-Buffer Method An Antialiased, Area-Averaged, Accumulation - Buffer

Slide 33:

The A-buffer method is an extension of the depth-buffer method. The A-buffer method is visibility detection method developed at Lucasfilm Studios for the rendering system REYES (Renders Everything You Ever Saw)

Slide 34:

The A-buffer expands on the depth buffer method to allow transparencies The key data structure in the A-buffer is the accumulation buffer

Slide 35:

A drawback of depth buffer is that it can find one visible surface at each pixel position. The A- buffer method expands the depth buffer so that each position in the buffer can reference a linked list of surfaces. Each position in the A-buffer has two fields. Depth field – stores a positive or negative real number. Intensity field – stores surface- intensity information or a pointer value.

A-Buffer Method (cont…) :

A-Buffer Method (cont…) If depth is >= 0, then the surface data field stores the depth of that pixel position as before.(Single intensity & single depth value). If depth < 0 then the data filed stores a pointer to a linked list of surface data.(multiple surfaces).

Slide 38:

If the depth value is positive , the number stored at that position is the depth of a single surface overlapping the corresponding pixel area. The intensity field stores the RGB components of the surface color at that point and the percent of pixel coverage.

Slide 39:

If the depth value is negative, this indicates multiple – surface contributions to the pixel intensity. The intensity field then stores a pointer to a linked list of surface data. Data for each surface in the linked list includes the following details.

Slide 40:

RGB intensity components Opacity parameter Depth Percent of area coverage Surface identifier Other surface rendering parameters The algorithm proceeds just like the depth buffer algorithm. The depth and opacity values are used to determine the final colour of a pixel.

Scan-Line Method

Slide 42:

An image space method for identifying visible surfaces . Computes and compares depth values along the various scan-lines for a scene.

Slide 43:

Two important tables are maintained: The edge table The surface face table The edge table contains: Coordinate end points of each line in the scene The inverse slope of each line Pointers into the surface face table to connect edges to surfaces

Slide 44:

The surface face tables contains: The plane coefficients Surface material properties Other surface data May be pointers into the edge table

Slide 45:

To facilitate the search for surfaces crossing a given scan-line an active list of edges is formed for each scan-line as it is processed. The active list stores only those edges that cross the scan-line in order of increasing x. Also a flag is set for each surface to indicate whether a position along a scan-line is either inside or outside the surface.

Scan-Line Method (cont…) :

Scan-Line Method (cont…) Pixel positions across each scan-line are processed from left to right At the left intersection with a surface the surface flag is turned on. At the right intersection point the flag is turned off. We only need to perform depth calculations when more than one surface has its flag turned on at a certain scan-line position.

Scan Line Method Example :

Scan Line Method Example

Slide 49:

If two surfaces are set to ON then we have to calculate the surface depth. Store the surface information of the surface having minimum depth. In the above example, S1 has minimum depth. Therefore store the surface information to the refresh buffer.

Advantages Any no. of overlapping polygon surfaces can be processed with this scan line method. Flags for the surfaces are set to indicate whether a position is inside or outside. Depth calculations are performed when surfaces overlap.

Scan-Line Method Limitations :

Scan-Line Method Limitations The scan-line method runs into trouble when surfaces cut through each other or otherwise cyclically overlap Such surfaces need to be divided

Depth-Sorting Method :

Depth-Sorting Method

Slide 53:

A visible surface detection method that uses both image-space and object-space operations Basically, the following two operations are performed Surfaces are sorted in order of decreasing depth Surfaces are scan-converted in order, starting with the surface of greatest depth The depth-sorting method is often also known as the painter’s method

Depth-Sorting Method (cont…) :

Depth-Sorting Method (cont…) First, assume that we are viewing along the z direction. All surfaces in the scene are ordered according to the smallest z value on each surface. The surface S at the end of the list is then compared against all other surfaces to see if there are any depth overlaps. If no overlaps occur then the surface is scan converted as before and the process repeats with the next surface.

Depth Overlapping :

Depth Overlapping S S’ z’max z’min zmax zmin x z No Depth Overlap Depth Overlap

Depth-Sorting Method (cont…) :

Depth-Sorting Method (cont…) When there is depth overlap, we make the following tests: The bounding rectangles for the two surfaces do no overlap Surface S is completely behind the overlapping surface relative to the viewing position The overlapping surface is completely in front of S realtive to the viewing position The boundary edge projections of the two surfaces onto the view plane do not overlap

Depth-Sorting Method (cont…) :

Depth-Sorting Method (cont…) The tests are performed in the order listed and as soon as one is true we move on to the next surface If all tests fail then we swap the orders of the surfaces

Depth Sorting :

Depth Sorting Painter’s algorithm Draw polygons as an oil painters might do Sort polygons by depth and draw them from back to front Depth sorting is NOT simple

Depth Sorting :

Depth Sorting We make the following tests for each polygon that has a depth overlap with S If any one of these tests is true, no reordering is necessary for S and the polygon being tested Polygon S is completely behind the overlapping surface relative to the viewing position The overlapping polygon is completely in front of S relative to the viewing position The boundary-edge projections of the two polygons onto the view plane do not overlap

Depth Sorting :

Depth Sorting Example

Depth Sorting :

Depth Sorting Cyclically overlapping surfaces that alternately obscure one another We can divide the surfaces to eliminate the cyclic overlaps

Area Subdivision(Warnock’s Algorithm) :

Area Subdivision(Warnock’s Algorithm) Image-space method taking advantage of area coherence in a scene Recursively subdivide a square area into equal-sized quadrants if the area is too complex to analyze easily

Slide 63:

Try to make an easy decision about which polygon is visible in a section of the image. If a decision cannot be made , subdivide the area recursively until one can be made.

Slide 64:

For each area do the following tests. Are all polygons disjoint from area? if yes, display background colour. 2) Only one intersecting or contained polygon ? If yes, fill with background colour, and then draw contained polygon or intersecting portion.

Slide 65:

3) One single surrounding polygon, no intersecting or contained polygon? If yes, draw area with the polygon’s color. 4) More than one polygon is intersecting, contained in, or surrounding, but only one polygon is surrounding the area and is in front of others.? If yes, draw area with that front polygons color. 5)otherwise, subdivide the area into 4 equal areas and reuse.

Area Subdivision :

Area Subdivision Four possible relationships between polygon surfaces and a rectangular section of the viewing plane

Slide 67:

Terminating criteria Case 1: An area has no inside, overlapping, or surrounding surfaces (all surfaces are outside the area) Case 2: An area has only one inside, overlapping or surrounding surfaces Case 3: An area has one surrounding surface that obscures all other surfaces within the area boundaries