3D configurator, surface determination (also known as Hidden Surface Removal (HSR), Occlusion Culling (OC), or Visible Surface Determination (VSD)) is the method used to determine which surfaces and parts of surfaces are not visible from a particular angle. A Hidden Surface Determination Algorithm is a solution to the visibility problem that was one of the first major problems in 3D computer graphics. The process of determining hidden surfaces is sometimes referred to as hiding. The analog for line rendering is the removal of hidden lines. The determination of the hidden surface is necessary to display an image correctly, so that no features hidden behind the model itself can be seen, so that only the naturally visible part of the graphic is visible.
Background.
Hidden Surface Determination is a method of preventing surfaces that should not be visible to the user (e.g. because they lie behind opaque objects such as walls) from being displayed. Despite advances in hardware capability, there is still a need for advanced rendering algorithms. The responsibility of a rendering engine lies in enabling large world spaces, and as the size of the world approaches infinity, the engine should not slow down but remain at constant speed. The optimization of this process requires that as few resources as possible can be used to display surfaces that are not displayed to the user.
There are many hidden surface determination techniques. They are basically an exercise in sorting and usually differ in the order in which sorting is performed and how the problem is subdivided. Sorting large quantities of graphic primitives is usually done by splitting and conquering.
Algorithms.
Taking the rendering pipeline into account, the following algorithms treat the projection, clipping, and rasterization steps differently:
During rasterization, the depth/Z value of each pixel (or sample in the case of anti-aliasing, but without losing publicity, the term pixel is used) is checked against an existing depth value. If the current pixel is behind the pixel in the Z buffer, the pixel is rejected, otherwise it is shaded and its depth value replaces that in the B buffer. Z-buffering supports dynamic scenes in a simple way and is currently efficiently implemented in graphics hardware. This is the current standard. The cost of using z-buffering is that it uses up to 4 bytes per pixel, and the rasterization algorithm must check each rasterized sample against the z-buffer. The Z buffer can also suffer from artifacts due to precision errors (also known as Z-fighting).
Coverage Buffer (C-Buffer) and Surface Buffer (S-Buffer).
These are faster than Z buffers and are commonly used in Quake I era games. Instead of storing the Z value per pixel, they store a list of segments already displayed per line of the screen. New polygons are then cut against already displayed segments that would hide them. An S buffer can display unsorted polygons, while a C buffer requires polygons to be displayed from bottom to top. Since the C buffer technique does not require a pixel to be drawn more than once, the process is somewhat faster. This was often used with BSP (Binary Space Partitioning) trees, which would allow sorting of polygons.
Sorted active edge list.
Used in Quake 1, this was to save a list of the edges of polygons already displayed (see Scanline rendering). Polygons are displayed from the nearest to the most distant location. New polygons are truncated at the edges of the polygons already displayed, creating new polygons that are then displayed and the additional edges saved. It is much more difficult to implement than S/C/Z buffers, but it scales much better with increasing resolution.
Sorts polygons by their center of gravity and pulls them forward. This leads to few artifacts when applied to scenes with polygons of similar size that form smooth meshes and backside selection is turned on. The cost here is the sorting step and the fact that visual artifacts can occur. This algorithm is broken by design for general scenes, since it cannot process polygons in various common configurations.
Binary space partitioning (BSP).
Splits a scene along layers that correspond to the polygon boundaries. The subdivision is designed to ensure a unique depth order from any point in the scene as the BSP tree is traversed. The disadvantage is that the BSP tree is created with an expensive pre-process. This means that the data is pre-sorted and error-free, ready for the algorithms mentioned above. Note that the BSP is not a solution for HSR, but only a tool.
Attempts to model the path of the light rays to a point of view by tracking the steels from the point of view into the scene. Although it is not an algorithm for removing hidden surfaces as such, it implicitly solves the problem of removing hidden surfaces by finding the nearest surface for each viewing beam. This is effectively equivalent to sorting the entire geometry on a pixel basis.
The Warnock algorithm.
Divides the screen into smaller areas and sorts triangles within them. Ambiguity (i.e. polygons overlap in these areas at depth) results in a further subdivision. At the boundary, a subdivision down to pixel level can occur.
Culling and Visible Surface Determination.
A related area for determining the visible surface (VSD) is culling, which normally occurs before VSD in a rendering pipeline. Primitives or batches of primitives can be completely rejected, which usually reduces the load on a well-designed system.
The advantage of early rejection is that whole, invisible objects do not need to be fetched, transformed, rasterized or shaded. Here are some types of con culling algorithms:
Viewing Frustum Culling.
The Viewing Frustum is a geometric representation of the volume visible to the virtual camera. Of course, objects outside this volume are not visible in the final image, so they are discarded. Often objects are at the limit of the viewing angle. These objects are cut into pieces along this boundary in a process called clipping, and the pieces outside the fall are discarded because there is no room to draw.
Back-face culling.
With 3D objects, part of the object surface points to the camera, the rest is directed away from the camera, i.e. on the back of the object, obstructed by the front. If the object is completely opaque, these surfaces do not need to be drawn. They are determined by the order of the vertex turn: If the drawn triangle has its vertices on the projection plane in front of the camera clockwise, they change to the counterclockwise order when the surface faces away from the camera.
By the way, this makes the objects completely transparent even if the angle camera is inside them, because then all surfaces of the object are directed away from the camera and are selected by the renderer. To prevent this, the object must be double-sided (i.e. no backface culling is performed) or have separate inner surfaces.
Contribution Culling.
Often they move the objects so far away that they do not make a significant contribution to the final image. These objects are thrown away if their projection is too small.
Objects that are completely behind other opaque objects can be selected. This is a very popular mechanism to speed up the representation of large scenes of medium to high complexity. There are several different occlusion culling approaches:
- The Potential Visible Sentence (PVS) rendering divides a scene into regions and introduces the visibility for them. These visibility sets are then indexed at runtime to quickly obtain high quality visibility sets (taking into account complex occluder interactions).
- Portal rendering divides a scene into cells/sectors (rooms) and portals (doors) and calculates which sectors are visible by truncating them against portals.
Share and conquer.
A popular topic in VSD literature is sharing and conquering. The Warnock algorithm was the first step towards splitting the screen. Beam tracing is a ray tracing approach that divides the visible volumes into beams. Different approaches to subdivide the screen space reduce the number of primitives considered per region, e.g. tiling or screen space BSP clipping. Tiling can be used as a precursor to other techniques. The hardware of the Z-buffer can typically contain a coarse “hi-Z” against which primitives can be rejected early without screening, this is a form of occlusion culling.
Bounding Volume Hierarchies (BVHs) are often used to divide the space of the scene (examples are the BSP tree, the octree, and the kd-tree). This allows the visibility determination to be performed hierarchically: If a node in the tree is considered invisible, all its sub-nodes are also invisible, and no further processing is required (they can all be rejected by the renderer). If a node is considered visible, each of its childs must be evaluated. This traverse is practically a tree migration where invisibility/closure or reaching a leaf node determines whether to stop or return.
Thank you very much for your visit.
Leave A Comment