| Revision as of 10:31, 19 August 2006 editArnero (talk | contribs)Extended confirmed users1,719 edits Bounding Volume Hierarchies (BVHs)← Previous edit | Revision as of 05:39, 21 August 2006 edit undoArnero (talk | contribs)Extended confirmed users1,719 edits fillrate, parallelNext edit → | ||
| Line 7: | Line 7: | ||
| ; Backface culling : Since ]es are hollow shells, not solid objects, the back side of some faces, or ]s, in the mesh will never face the camera. Typically, there is no reason to draw such faces. This is responsible for the effect often seen in ] in which, if the camera happens to be inside a mesh, rather than seeing the "inside" surfaces of the mesh, it disappears completely (all faces are seen from behind, and are culled). | ; Backface culling : Since ]es are hollow shells, not solid objects, the back side of some faces, or ]s, in the mesh will never face the camera. Typically, there is no reason to draw such faces. This is responsible for the effect often seen in ] in which, if the camera happens to be inside a mesh, rather than seeing the "inside" surfaces of the mesh, it disappears completely (all faces are seen from behind, and are culled). | ||
| ; Viewing frustum culling : The ] is a geometric representation of the volume visible to the virtual camera. Naturally, objects outside this volume will not be visible in the final image, so they are discarded. Often, objects lie on the boundary of the viewing frustum. These objects are cut into pieces along this boundary in a process called ], and the pieces that lie outside the frustum are discarded. | ; Viewing frustum culling : The ] is a geometric representation of the volume visible to the virtual camera. Naturally, objects outside this volume will not be visible in the final image, so they are discarded. Often, objects lie on the boundary of the viewing frustum. These objects are cut into pieces along this boundary in a process called ], and the pieces that lie outside the frustum are discarded. | ||
| ; Occlusion culling : Occlusion culling is the process of determining which portions of objects are hidden by other objects from a given viewpoint. This is one of the fundamental problems in computer graphics, and many different occlusion culling algorithms have been developed. The simplest is ], in which polygons are sorted, then drawn back to front. The most common in real-time computer graphics is ], in which the depth value at each pixel is stored as each polygon is rendered. The pixel is only overwritten if the depth value of the current point is less than the depth value stored in the z-buffer. Both of these methods operate on polygon meshes. ] can be used to traverse complex scenes front to back and a hirachical z-buffer can be used to reject large nodes of the BVH. | ; Occlusion culling : Occlusion culling is the process of determining which portions of objects are hidden by other objects from a given viewpoint. This is one of the fundamental problems in computer graphics, and many different occlusion culling algorithms have been developed. The simplest is ], in which polygons are sorted, then drawn back to front. The most common in real-time computer graphics is ], in which the depth value at each pixel is stored as each polygon is rendered. The pixel is only overwritten if the depth value of the current point is less than the depth value stored in the z-buffer. Both of these methods operate on polygon meshes. ] can be used to traverse complex scenes front to back and a hirachical z-buffer can be used to reject large nodes of the BVH. To reduce fillrate in this case, large nodes are rendered at adaptivly at lower resolution so that they cover about 8 pixels (in their level of the hirachy). Parallelism (for multiple GPUs (on multiple graphic cards) and for a single GPU wich is waiting for a long ] lookup in the z-buffer or BVH) is achieved by traversing the tree at different parts of the screen (needs some managing algorithmus) at the same time. | ||
| ; Contribution culling : Often, objects are so far away that they do not contribute significantly to the final image. These objects are thrown away if their screen ] is too small. | ; Contribution culling : Often, objects are so far away that they do not contribute significantly to the final image. These objects are thrown away if their screen ] is too small. | ||
Revision as of 05:39, 21 August 2006
In 3D computer graphics, hidden surface determination is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. A hidden surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. The analogue for line rendering is hidden line removal.
Hidden surface determination is necessary to render an image correctly, as parts of the image that are not visible should not be drawn. It also speeds up rendering since objects that aren't visible can be removed from the graphics pipeline.
There are many techniques for hidden surface determination, and the core differences between most rendering algorithms is how they handle this problem. There are also different stages of hidden surface determination. These stages include:
- Backface culling
- Since meshes are hollow shells, not solid objects, the back side of some faces, or polygons, in the mesh will never face the camera. Typically, there is no reason to draw such faces. This is responsible for the effect often seen in computer and video games in which, if the camera happens to be inside a mesh, rather than seeing the "inside" surfaces of the mesh, it disappears completely (all faces are seen from behind, and are culled).
- Viewing frustum culling
- The viewing frustum is a geometric representation of the volume visible to the virtual camera. Naturally, objects outside this volume will not be visible in the final image, so they are discarded. Often, objects lie on the boundary of the viewing frustum. These objects are cut into pieces along this boundary in a process called clipping, and the pieces that lie outside the frustum are discarded.
- Occlusion culling
- Occlusion culling is the process of determining which portions of objects are hidden by other objects from a given viewpoint. This is one of the fundamental problems in computer graphics, and many different occlusion culling algorithms have been developed. The simplest is painter's algorithm, in which polygons are sorted, then drawn back to front. The most common in real-time computer graphics is z-buffering, in which the depth value at each pixel is stored as each polygon is rendered. The pixel is only overwritten if the depth value of the current point is less than the depth value stored in the z-buffer. Both of these methods operate on polygon meshes. Bounding Volume Hierarchies (BVHs) can be used to traverse complex scenes front to back and a hirachical z-buffer can be used to reject large nodes of the BVH. To reduce fillrate in this case, large nodes are rendered at adaptivly at lower resolution so that they cover about 8 pixels (in their level of the hirachy). Parallelism (for multiple GPUs (on multiple graphic cards) and for a single GPU wich is waiting for a long latency lookup in the z-buffer or BVH) is achieved by traversing the tree at different parts of the screen (needs some managing algorithmus) at the same time.
- Contribution culling
- Often, objects are so far away that they do not contribute significantly to the final image. These objects are thrown away if their screen projection is too small.
Though hidden surface determination is most often used to determine what is visible in the final image, it is also has other applications, such as determining which parts of objects are in shadow.
Visible surface determination
Sometimes the majority of surfaces is invisible, so why ever touch them? This approach is opposite to hidden surface removal and used in:
- Ray tracer : Ray tracing, which can also operate on parametric geometry, attempts to model the path of light rays into a viewpoint by tracing rays from the viewpoint into the scene. The first object the ray intersects is rendered, as it naturally is the object visible to the camera. Additional data structures used to solve this sorting problem include bsp trees and octrees.
- Portal rendering
- some Heightfield renderers work this way. Google Earth certainly does not process the whole earth for every frame.