| Revision as of 22:26, 7 September 2006 editArnero (talk | contribs)Extended confirmed users1,719 edits →Visible surface determination← Previous edit | Revision as of 17:57, 12 September 2006 edit undoWolfkeeper (talk | contribs)31,832 edits Revert to revision 73942220 dated 2006-09-05 13:20:49 by 213.115.45.218 using popupsNext edit → | ||
| Line 15: | Line 15: | ||
| <!-- {{Cleanup-date|August 2006}} Maybe the tagger could post on the discussion ? --> | <!-- {{Cleanup-date|August 2006}} Maybe the tagger could post on the discussion ? --> | ||
| In some applications (CAD of simple work pieces) a large amount of geometry is visible. But in walk through applications only a small amount of geometry is visible. | In some applications (CAD of simple work pieces) a large amount of geometry is visible. But in walk through applications (], ]) only a small amount of geometry is visible. | ||
| Visible surface determination tries not to touch all the geometry residing in memory to avoid |
Visible surface determination tries not to touch all the geometry residing in memory to avoid cache misses or loading geometry from the hard drive or over the internet. | ||
| * cache misses | |||
| * loading geometry from the hard drive | |||
| * loading geometry over the internet | |||
| ** from a static, but large database | |||
| ** from a dynamic database, for example in ] or ] with other actors | |||
| * generate geometry | |||
| ** trees | |||
| ** textures | |||
| ** landscape | |||
| ** facial expressions | |||
| * do physics simulation | |||
| ** clouds in the sky | |||
| ** waves on the see | |||
| ** ragdoll | |||
| ** cars | |||
| Methods: | |||
| * ] : ], 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 ] and ]s. | * ] : ], 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 ] and ]s. | ||
| * ] | |||
| * ]: ] was able to render a testured view fluently, but stumbled at drawing the whole map in wireframe. | |||
| * ] as a type of ]-renderer | * ] as a type of ]-renderer | ||
Revision as of 17:57, 12 September 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 (possible on multiple graphic cards) is achieved by traversing the tree at different parts of the screen (needs some managing algorithmus) at the same time. The latency of the lookup in the z-buffer and BVH and the deep pipelinining architecture of modern computers still leads to some overdraw: The GPU traverses the BHV without waiting for the z-buffer comparison and sometimes needs to cancel large subtrees. Coherence between consecutive frames can be used to cache different parts of the scene on different graphic cards and to reorder the BVH in memory in the way it was accessed in the last frame. Shadow casting is achieved by repeating this process for every light source. Aborting BHV traversal when the box gets smaller then one pixel leads to level of detail, but this has to be synced between the rendering and the shadow casting to avoid jaggy shadows.
- 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
In some applications (CAD of simple work pieces) a large amount of geometry is visible. But in walk through applications (virtual reality, computer games) only a small amount of geometry is visible. Visible surface determination tries not to touch all the geometry residing in memory to avoid cache misses or loading geometry from the hard drive or over the internet.
- 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
- Google Earth as a type of Heightfield-renderer