CLICK HERE TO DOWNLOAD PPT ON Visible Surface Detection
Visible Surface Detection Presentation Transcript
1.Visible Surface Detection
2.Back-Face Culling
Used to remove unseen polygons from convex, closed polyhedron (Cube, Sphere)
Does not completely solve hidden surface problem since one polyhedron may obscure another
Used to remove unseen polygons from convex, closed polyhedron (Cube, Sphere)
Does not completely solve hidden surface problem since one polyhedron may obscure another
3.Recall Slide: ITCS 4120-3D Viewing.ppt # 51-53, “3D?3D collineation on cube”
4.Depth-Buffer AlgorithmInitialize depth buffer and frame buffer for all pixels (x,y)
depthBuffer(x,y) = 1.0; frameBuffer(x,y)=BackgroundColor
Process each polygon face, F, in scene
For each projected pixel, P, at location (x,y) in F, calculate the depth z
If z < depthBuffer(x,y), compute surface color, C, at the pixel P, so set:
depthBuffer(x,y) = z; frameBuffer(x,y)=C
Note: After all surfaces are processed, depth buffer contains depth for visible surfaces and frame buffer contains corresponding color values for those surfaces
depthBuffer(x,y) = 1.0; frameBuffer(x,y)=BackgroundColor
Process each polygon face, F, in scene
For each projected pixel, P, at location (x,y) in F, calculate the depth z
If z < depthBuffer(x,y), compute surface color, C, at the pixel P, so set:
depthBuffer(x,y) = z; frameBuffer(x,y)=C
Note: After all surfaces are processed, depth buffer contains depth for visible surfaces and frame buffer contains corresponding color values for those surfaces
5.A-Buffer Method
accumulation buffer – buffer accumulates multiple pieces of information for each pixel in addition to depth for transparency or anti-aliasing (high-end movies, etc.). A-buffer element stores:
Depth Field : real-number
Surface Data Field (SDF): stores surface data or pointer
accumulation buffer – buffer accumulates multiple pieces of information for each pixel in addition to depth for transparency or anti-aliasing (high-end movies, etc.). A-buffer element stores:
Depth Field : real-number
Surface Data Field (SDF): stores surface data or pointer
6.A-Buffer Method
7.Scan-Line Method
Unlike z-buffer or A-buffer, scan-line method has depth info only for a single scan-line.
In order to require one scan-line of depth values, we must group and process all polygons intersecting a given scan-line at the same time before process the next scan-line
Build table of edges of all polygons in scene. Maintain active-edge-table as we visit each scan-line in scene. AET now contains edges for all polygons at that scanline. Must maintain flag for each surface to determine whether pixel on scan-line is inside that surface.
Unlike z-buffer or A-buffer, scan-line method has depth info only for a single scan-line.
In order to require one scan-line of depth values, we must group and process all polygons intersecting a given scan-line at the same time before process the next scan-line
Build table of edges of all polygons in scene. Maintain active-edge-table as we visit each scan-line in scene. AET now contains edges for all polygons at that scanline. Must maintain flag for each surface to determine whether pixel on scan-line is inside that surface.
8.Scan-Line Method Basic Example
Scan Line 1:
(A,B) to (B,C) only inside S1, so color from S1
(E,H) to (F,G) only inside S2, so color from S2
Scan Line 2:
(A,D) to (E,H) only inside S1, so color from S1
(E,H) to (B,C) inside S1 and S2 , so compute & test depth In this example we color from S1
(B,C) to (F,G) only inside S2, so color from S2
Scan Line 1:
(A,B) to (B,C) only inside S1, so color from S1
(E,H) to (F,G) only inside S2, so color from S2
Scan Line 2:
(A,D) to (E,H) only inside S1, so color from S1
(E,H) to (B,C) inside S1 and S2 , so compute & test depth In this example we color from S1
(B,C) to (F,G) only inside S2, so color from S2
9.Scan-Line Method Generalization
This basic approach fails when surfaces cut-through each other or overlap. To generalize we must divide surfaces to eliminate overlaps
This basic approach fails when surfaces cut-through each other or overlap. To generalize we must divide surfaces to eliminate overlaps
10.Depth-Sorting Method
Painter’s Algorithm
Approach:
sorted surfaces by increasing depth
may require surface splitting
scan-convert surfaces in sorted order (back to front)
We can avoid reorder if:
1) Bounding rectangles in xy don’t overlap
2) Sf is completely behind overlapping surface relative to view position
3) Overlapping surface is completely in front of Sf relative to view position
4) Boundary edges of projections of two surfaces on projection plane don’t overlap
Painter’s Algorithm
Approach:
sorted surfaces by increasing depth
may require surface splitting
scan-convert surfaces in sorted order (back to front)
We can avoid reorder if:
1) Bounding rectangles in xy don’t overlap
2) Sf is completely behind overlapping surface relative to view position
3) Overlapping surface is completely in front of Sf relative to view position
4) Boundary edges of projections of two surfaces on projection plane don’t overlap
11.4) Boundary edges of projections of two surfaces on projection plane don’t overlap. (Knowing that bounding rectangles overlap from (1) doesn’t help. We must compute expensive polygon/polygon intersection).
12.It also is possible that there are cyclic occlusion relationships or surfaces penetrate. To deal with this we flag a surface when it is put at the end of the depth sort list and if we ever try to place a surface at the end more than once, we must split the polygon
13.BSP-trees
14.Traversing BSP-Tree
Traverse the BSP tree such that the branch descended first is the side that is away from the eyepoint. This can be determined by substituting the eye point into the plane equation for the polygon at the root.
When there is no first branch to descend, or that branch has been completed then render the polygonat this node.
After the current node's polygon has been rendered, descend the branch that is closer to the eyepoint.
Traverse the BSP tree such that the branch descended first is the side that is away from the eyepoint. This can be determined by substituting the eye point into the plane equation for the polygon at the root.
When there is no first branch to descend, or that branch has been completed then render the polygonat this node.
After the current node's polygon has been rendered, descend the branch that is closer to the eyepoint.
15.Area-Subdivision Method
Recursively subdivide viewplane into quadrants until:
rectangle contains part of 1 projected surface
rectangle contains part of no surface
rectangle is size of pixel
Recursively subdivide viewplane into quadrants until:
rectangle contains part of 1 projected surface
rectangle contains part of no surface
rectangle is size of pixel
16.We need tests that can quickly determine tell if current area is part of one surface or if further subdivision is needed.
Four cases for relation between surface and rectangular area:
Four cases for relation between surface and rectangular area:
17.Area-Subdivision: Stopping Conditions
Recursive subdivision can stop when either:
1) a rectangle has all surfaces outside
2) a rectangle has exactly one inside, overlapping, or surrounding surface
3) a rectangle has one surrounding surface and the surface occludes all other surfaces in the area
For efficiency:
compare rectangle to projected surface bounding rectangle first. Only perform exact interaction test if necessary. If single bounding rect. intersects rectangle, test for exact intersection and color the framebuffer for the intersection of surface & rectangle.
Recursive subdivision can stop when either:
1) a rectangle has all surfaces outside
2) a rectangle has exactly one inside, overlapping, or surrounding surface
3) a rectangle has one surrounding surface and the surface occludes all other surfaces in the area
For efficiency:
compare rectangle to projected surface bounding rectangle first. Only perform exact interaction test if necessary. If single bounding rect. intersects rectangle, test for exact intersection and color the framebuffer for the intersection of surface & rectangle.
18.Testing Condition 3
sort surfaces on minimum depth from view plane
for each surrounding surface for current rectangle compute maximum depth within rectangle subsection
If maximum depth of a surrounding surface is closer to view plane than the minimum depths of all other surfaces within the area, condition 3 is achieved (i.e. surrounding surface occludes all others).
sort surfaces on minimum depth from view plane
for each surrounding surface for current rectangle compute maximum depth within rectangle subsection
If maximum depth of a surrounding surface is closer to view plane than the minimum depths of all other surfaces within the area, condition 3 is achieved (i.e. surrounding surface occludes all others).
19.sort surfaces on minimum depth from view plane
for each surrounding surface for current rectangle compute maximum depth within rectangle subsection
If maximum depth of a surrounding surface is closer to view plane than the minimum depths of all other surfaces within the area, condition 3 is achieved (i.e. surrounding surface occludes all others).
for each surrounding surface for current rectangle compute maximum depth within rectangle subsection
If maximum depth of a surrounding surface is closer to view plane than the minimum depths of all other surfaces within the area, condition 3 is achieved (i.e. surrounding surface occludes all others).
20.There are cases that this computation will miss. Rather than performing further more expensive testing, we just subdivide the rectangle (i.e. don’t stop recursion).
This choice is conservative: we may recurse when we don’t need (to avoid complex geometric computation), but as we continue recursive subdivision we will eventually compute exact answer because in limiting case rectangle is one pixel and in this case we simply calculate depth of each intersecting surface at that single point and set the framebuffer to the nearest surface’s color.
This choice is conservative: we may recurse when we don’t need (to avoid complex geometric computation), but as we continue recursive subdivision we will eventually compute exact answer because in limiting case rectangle is one pixel and in this case we simply calculate depth of each intersecting surface at that single point and set the framebuffer to the nearest surface’s color.
21.based geometric optics method that trace rays of light
“backwards” light path tracing
compare to depth buffer (surfaces to pixels versus pixel to surfaces)
special case of ray-tracing
“backwards” light path tracing
compare to depth buffer (surfaces to pixels versus pixel to surfaces)
special case of ray-tracing
22.Octree:
partitions 3-space by a regular, recursive subdivision of 3-space into axis-aligned boxes
3D objects are stored in the octree node that contains them. Recursively subdivide until each octree node is either empty, a homogeneous volume, or contains single object that’s “easy” to compute visibility (example can use back-face culling alone).
partitions 3-space by a regular, recursive subdivision of 3-space into axis-aligned boxes
3D objects are stored in the octree node that contains them. Recursively subdivide until each octree node is either empty, a homogeneous volume, or contains single object that’s “easy” to compute visibility (example can use back-face culling alone).
23.Octrees: Rendering
Given a particular view, the octants can be ordered in view depth order. The order is the same for octants at all levels in the recursive subdivision.
For general perspective viewing, traverse the octree in back-to-front order and render contents of each node (nearer object’s pixels overwrite farther object’s pixels).
Given a particular view, the octants can be ordered in view depth order. The order is the same for octants at all levels in the recursive subdivision.
For general perspective viewing, traverse the octree in back-to-front order and render contents of each node (nearer object’s pixels overwrite farther object’s pixels).
24.Comparison of visibility-detection methods
effectiveness of method depends on surface distribution
wide distribution along view depth implies little depth overlap. This is ideal for depth-sorting and BSP-trees
few overlaps in surface view plane projections is ideal for scan-line or area-subdivision
more generally
few surfaces implies few depth overlaps which is ideal for depth-sort or BSP-tree
scan-line also good for a few thousand polygon surfaces
for large number of surfaces octree or depth-buffer is better
depth-buffer – tends to have constant computation cost as # of surfaces increases because more surfaces tends to imply individual surfaces are small (but beware of depth-complexity). Relative performance best for complex scenes.
Octree – for parallel projection of volume data only need integer add/sub. operations
effectiveness of method depends on surface distribution
wide distribution along view depth implies little depth overlap. This is ideal for depth-sorting and BSP-trees
few overlaps in surface view plane projections is ideal for scan-line or area-subdivision
more generally
few surfaces implies few depth overlaps which is ideal for depth-sort or BSP-tree
scan-line also good for a few thousand polygon surfaces
for large number of surfaces octree or depth-buffer is better
depth-buffer – tends to have constant computation cost as # of surfaces increases because more surfaces tends to imply individual surfaces are small (but beware of depth-complexity). Relative performance best for complex scenes.
Octree – for parallel projection of volume data only need integer add/sub. operations
25.Visibility Detection of Curve Surfaces
ray-casting – compute ray surface intersections
scan-line – compute intersection of scan-line’s extruded plane with surfaces
octrees – chop up surfaces into pieces at octant boundaries
depth-buffer – approximate surface with polygons
surfaces represented as parametric, explicit or implicit equations
use efficient numerical approximation methods for computing surface intersections with parallel calculations or hardware implementation for common surfaces (quadrics, bezier-surfaces, etc.)
ray-casting – compute ray surface intersections
scan-line – compute intersection of scan-line’s extruded plane with surfaces
octrees – chop up surfaces into pieces at octant boundaries
depth-buffer – approximate surface with polygons
surfaces represented as parametric, explicit or implicit equations
use efficient numerical approximation methods for computing surface intersections with parallel calculations or hardware implementation for common surfaces (quadrics, bezier-surfaces, etc.)
26.Surface contour plots
given some surface representation write it in view coordinate system (z is depth): y=f(x,z)
plot curves each at fixed z in front-to-back order and eliminate hidden sections. Increment z by ?z over surfaces visible z range. For each curve, iterate over x coordinate in screen coordinates, compute corresponding y and plot point (x,y). To eliminate hidden surfaces record (ymin,ymax) of plotted points for each x screen coordinate. Only plot point (x,y) if y is outside (ymin,ymax) at x.
given some surface representation write it in view coordinate system (z is depth): y=f(x,z)
plot curves each at fixed z in front-to-back order and eliminate hidden sections. Increment z by ?z over surfaces visible z range. For each curve, iterate over x coordinate in screen coordinates, compute corresponding y and plot point (x,y). To eliminate hidden surfaces record (ymin,ymax) of plotted points for each x screen coordinate. Only plot point (x,y) if y is outside (ymin,ymax) at x.
27.Wire-frame visibility methods
28.Wire-Frame Depth Cueing
29.OpenGL Visibility
30.OpenGL Visibility
Use a sequence of sorting steps and tests of increasing computational complexity to handle all possible cases of polygon depth orderings
11.Depth Sorting Details
12.Depth Sorting: Reorder Avoidance Tests
Use a sequence of sorting steps and tests of increasing computational complexity to handle all possible cases of polygon depth orderings
11.Depth Sorting Details
12.Depth Sorting: Reorder Avoidance Tests
Posts
0 comments