Hidden-surface determination: Difference between revisions

Browse history interactively ← Previous editContent deleted Content addedVisual WikitextInline

Revision as of 16:48, 29 August 2004 editBenjBot (talk \| contribs)432 editsm Benjamin Goldenberg - Robot-assisted disambiguation: Plane← Previous edit		Latest revision as of 17:58, 1 September 2024 edit undoPink Bee (talk \| contribs)Extended confirmed users1,091 editsm ce CN templates
(228 intermediate revisions by more than 100 users not shown)
Line 1:		Line 1:
			{{short description\|Visibility in 3D computer graphics}}
	<!-- Hidden Face Removal -->
			{{multiple issues\|{{Update\|date=February 2016}}
	<!-- original article by Matthew Wegner -->
			{{Refimprove\|date=July 2017}}}}
	<!-- February 14, 2004 -->
			{{3D computer graphics}}
	'''Hidden face removal''' is a technique used in ] for drawing a ] scene correctly. It is also implemented to save time, because if a face cannot be seen, that means it should not be drawn in the scene, and therefore you don't have to waste ] cycles drawing it. This article deals with several methods of hidden face removal.
			In ], '''hidden-surface determination''' (also known as '''shown-surface determination''', '''hidden-surface removal''' ('''HSR'''), '''occlusion culling''' ('''OC''') or '''visible-surface determination''' ('''VSD''')) is the process of identifying what ] and parts of surfaces can be seen from a particular viewing angle. A hidden-surface determination ] is a solution to the ], which was one of the first major problems in the field of 3D computer graphics.{{citation-needed\|date=June 2020}} The process of hidden-surface determination is sometimes called '''hiding''', and such an algorithm is sometimes called a '''hider'''.{{citation-needed\|date=June 2020}} When referring to line rendering it is known as ].{{citation-needed\|date=June 2020}} Hidden-surface determination is necessary to render a scene correctly, so that one may not view features hidden behind the model itself, allowing only the naturally viewable portion of the graphic to be visible.

	== ~~Backface culling~~ ==		== Background ==
			Hidden-surface determination is a process by which surfaces that should not be visible to the user (for example, because they lie behind opaque objects such as walls) are prevented from being rendered. Despite advances in hardware capability, there is still a need for advanced ]s. The responsibility of a rendering engine is to allow for large world spaces, and as the world’s size approaches infinity, the engine should not slow down but remain at a constant speed. Optimizing this process relies on being able to ensure the deployment of as few resources as possible towards the rendering of surfaces that will not end up being displayed to the user.

			There are many techniques for hidden-surface determination. They are fundamentally an exercise in ] and usually vary in the order in which the sort is performed and how the problem is subdivided. Sorting large quantities of graphics primitives is usually done by ].

			== Algorithms ==
	In ''backface culling'' we want to remove or "cull" the backfaces from an object we are drawing. A backface is essentially what it sounds like; the back of something. But of what? Well, that would be the backface of what are usually referred to as ]s or facets. ] objects are made up of polygons or facets, which are made up of ]. One property of polygons is that they generally have a particular direction they are facing. The direction a polygon is facing is determined by its ]. The normal is a ] which is perpendicular to the polygon which can also be said to be a ] (as defined in ].) The normal sticks out of the front of the polygon, and so, in backface culling, we only want to draw polygons that are facing us. You may be asking yourself, "Why would we want to do that?" Well, first of all, as with most hidden face removal techniques, it saves time. For example, with a cube, we can only see a maximum of three faces at any one time. Considering there are six faces in a cube, drawing only those three can save at least 50% of the work from the rest of your ]. Also, this makes objects appear to be more solid. With a ], you can see right through it to the other side. But, if you look at your monitor, you can't see the back of it, right? That's the principle backface culling works on.
			Considering the ], the ], the ], and the ] steps are handled differently by the following algorithms:
			; ]: During rasterization, the depth/Z value of each pixel (or ''sample'' in the case of anti-aliasing, but without loss of generality 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 the one in the Z-buffer. Z-buffering supports dynamic scenes easily and is currently implemented efficiently 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 that the rasterization algorithm needs to check each rasterized sample against the Z-buffer. The Z-buffer can also suffer from artifacts due to precision errors (also known as ]).
			; Coverage buffers ({{visible anchor\|C-buffer}}) and surface buffer (]): Faster than Z-buffers and commonly used in games in the ] era. Instead of storing the Z value per pixel, they store a list of already displayed segments 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 the nearest to the furthest. Because the C-buffer technique does not require a pixel to be drawn more than once, the process is slightly faster. This was commonly used with ] (BSP) trees, which would provide sorting for the polygons.
			; Sorted active edge list: Used in Quake 1, this was storing a list of the edges of already displayed polygons (see ]). Polygons are displayed from the nearest to the furthest. New polygons are clipped against already displayed polygons' edges, creating new polygons to display then storing the additional edges. It's much harder to implement than S/C/Z-buffers, but it scales much better with increases in resolution.
			; ]: Sorts polygons by their ] and draws them back to front. This produces few artifacts when applied to scenes with polygons of similar size forming smooth meshes and ] 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, as it cannot handle polygons in various common configurations, such as surfaces that intersect each other.
			; ] (BSP): Divides a scene along planes corresponding to polygon boundaries. The subdivision is constructed in such a way as to provide an unambiguous depth ordering from any point in the scene when the BSP tree is traversed. The disadvantage here is that the BSP tree is created with an expensive pre-process. This means that it is less suitable for scenes consisting of dynamic geometry. The advantage is that the data is pre-sorted and error-free, ready for the previously mentioned algorithms. Note that the BSP is not a solution to HSR, only an aid.
			; ]: Attempts to model the path of light rays to a viewpoint by tracing rays from the viewpoint into the scene. Although not a hidden-surface removal algorithm as such, it implicitly solves the hidden-surface removal problem by finding the nearest surface along each view-ray. Effectively this is equivalent to sorting all the geometry on a per-pixel basis.
			; The ]: Divides the screen into smaller areas and sorts triangles within these. If there is ambiguity (i.e., polygons overlap in-depth extent within these areas), then further subdivision occurs. At the limit, the subdivision may occur down to the pixel level.

			== Culling and visible-surface determination ==
⚫	== ~~View~~ frustum culling ==
			A related area to visible-surface determination (VSD) is ''culling'', which usually happens before VSD in a rendering pipeline. Primitives or batches of primitives can be rejected in their entirety, which ''usually'' reduces the load on a well-designed system.

			The advantage of culling early on in the pipeline is that entire objects that are invisible do not have to be fetched, transformed, rasterized, or shaded. Types of culling algorithms include:
	With ''View frustum culling'' we set up a sort of sideways pyramid, representing the viewer's field of vision. Any ]s falling totally outside of it, are ignored in rendering. A polygon partially inside it is clipped to the view, so we only draw the parts that are actually being seen. Finally, a polygon totally inside is drawn normally. The obvious way to accomplish this, is to check every polygon with the view ]. Well, that may work when there are only a few objects, but if you're viewing a complex scene, with numerous objects and things to be rendered, it takes up more CPU cycles than it really needs to, because there is a faster way. We can speed this process up by dividing the scene up into octrees, which is a cube split along each axis, x, y, and z. For the areas of the scene that have more objects in them, we can continue to divide each ] into smaller ones, for more precision, while fairly empty areas can make do with one big box. The reason for all these boxes, and boxes of boxes is that we can test the boxes themselves against the view frustum. But we only check the parent boxes at first (the parent boxes being the big ones that were divided.) If a parent box is totally outside the view frustum, we don't need to check any of the smaller boxes inside it, because logically, they aren't in the view frustum either. However, if a parent box IS in the view frustum, in part or in whole, we can then check which of the child boxes are inside the view frustum. Then, we only render polygons that are inside boxes in the view frustum.

		⚫	=== Viewing-frustum culling ===
	== Occlusion culling == <!-- This needs more info on other areas -->
			The ] is a geometric representation of the volume visible to the ]. 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 as there is no place to draw them.

		⚫	=== Back-face culling ===
	''Occlusion culling'' checks which objects are in front of others and draws them in the correct order. An object which is in front of another, and therefore blocking part or all of it from sight is said to "occlude" that object. BSP (]) trees (used in ] and ]) are an example of occlusion culling. There are several forms of occlusion culling, but the one I know best is Z-Buffering. In the Z-Buffer, the z values for each pixel are stored. When plotting a pixel in a ], for example, we check to see if the value for that pixel is closer to the camera than the pixel we are plotting. A good way to find this out is through ]. If the current value is closer to the camera, then we don't plot the pixel we wanted, but otherwise, pixel plotting goes ahead as normal. This is one of the most accurate ways to properly order your drawing, so things appear in the right order, but also very time consuming. Not only do we have to run a check for any pixel we want to plot, but after we're done, we have to reset the buffer, so we can perform the check again. There are however optimizations for this method, to cut down some of the time, but seeing as I'm still learning this method, I can't tell you how things like "1/z" work exactly. <!-- This ought to be explained properly -->
			{{main\|Back-face culling}}
	A primitive method, called Z-Ordering, is to get the overall depth of the polygons (by average of the defining points), sort them, then drawing in the reverse order (deeper first, closer last).<!-- Added by Dalvi. Can be erased when the article is completed with appropriate info --> <!-- Thanks for bringing that up, I forgot about z-ordering. Fixed spelling error, added name of method -->

			With 3D objects, some of the object's surface is facing the camera, and the rest is facing away from the camera, i.e. is on the backside of the object, hindered by the front side. If the object is completely opaque, those surfaces never need to be drawn. They are determined by the vertex winding order: if the triangle drawn has its vertices in clockwise order on the projection plane when facing the camera, they switch into counter-clockwise order when the surface turns away from the camera.
⚫	== ~~Contribution~~ culling ==

			Incidentally, this also makes the objects completely transparent when the viewpoint camera is located inside them, because then all the surfaces of the object are facing away from the camera and are culled by the renderer. To prevent this the object must be set as double-sided (i.e. no back-face culling is done) or have separate inside surfaces.
	Basically ''contribution culling'' checks projection values and if they are too small, or off-screen, you don't draw the ]/].

			=== 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. See ].

			=== Occlusion culling ===
			{{See also\|Z-buffering#Z-culling}}
			Objects that are entirely behind other opaque objects may be culled. This is a very popular mechanism to speed up the rendering of large scenes that have a moderate to high ]. There are several types of occlusion culling approaches:
			* ] (''PVS'') rendering divides a scene into regions and pre-computes visibility for them. These visibility sets are then indexed at run-time to obtain high-quality visibility sets (accounting for complex occluder interactions) quickly.
			* ] divides a scene into cells/sectors (rooms) and portals (doors), and computes which sectors are visible by clipping them against portals.

			Hansong Zhang's dissertation "Effective Occlusion Culling for the Interactive Display of Arbitrary Models"<ref>{{cite web \|url=http://www.cs.unc.edu/~zhangh/hom.html \|title=Occlusion Culling with Hierarchical Occlusion Maps \|website=www.cs.unc.edu}}</ref> describes an occlusion culling approach.

			== Divide and conquer ==
			A popular theme in the VSD literature is ]. The ] pioneered dividing the screen. ] is a ray-tracing approach that divides the visible volumes into beams. Various screen-space subdivision approaches reducing the number of primitives considered per region, e.g. tiling, or screen-space BSP clipping. Tiling may be used as a preprocess to other techniques. Z-buffer hardware may typically include a coarse "hi-Z", against which primitives can be rejected early without rasterization, this is a form of occlusion culling.

			] (BVHs) are often used to subdivide the scene's space (examples are the ], the ] and the ]). This allows visibility determination to be performed hierarchically: effectively, if a node in the tree is considered to be ''invisible'', then all of its child nodes are also invisible, and no further processing is necessary (they can all be rejected by the renderer). If a node is considered ''visible'', then each of its children needs to be evaluated. This traversal is effectively a tree walk, where invisibility/occlusion or reaching a leaf node determines whether to stop or whether to recurse respectively.

			==See also==
			*]

			==Sources==
			{{reflist}}
			*
			* (] copy)

			{{Computer graphics}}

			]
			]
			]

Latest revision as of 17:58, 1 September 2024

Visibility in 3D computer graphics

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)

This article needs to be updated. Please help update this article to reflect recent events or newly available information. (February 2016)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Hidden-surface determination" – news · newspapers · books · scholar · JSTOR (July 2017) (Learn how and when to remove this message)

(Learn how and when to remove this message)

Three-dimensional (3D) computer graphics

Fundamentals
Modeling Scanning Rendering Printing
Primary uses
3D models Computer-aided design Graphic design Video games Visual effects Visualization Virtual engineering Virtual reality Virtual cinematography
Related topics
Computer-generated imagery (CGI) Animation computer skeletal 3D display Wire-frame model Texture mapping Motion capture Crowd simulation Global illumination Volume rendering
v t e

In 3D computer graphics, hidden-surface determination (also known as shown-surface determination, hidden-surface removal (HSR), occlusion culling (OC) or visible-surface determination (VSD)) is the process of identifying what surfaces and parts of surfaces can be seen from a particular viewing angle. 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. When referring to line rendering it is known as hidden-line removal. Hidden-surface determination is necessary to render a scene correctly, so that one may not view features hidden behind the model itself, allowing only the naturally viewable portion of the graphic to be visible.

Background

Hidden-surface determination is a process by which surfaces that should not be visible to the user (for example, because they lie behind opaque objects such as walls) are prevented from being rendered. Despite advances in hardware capability, there is still a need for advanced rendering algorithms. The responsibility of a rendering engine is to allow for large world spaces, and as the world’s size approaches infinity, the engine should not slow down but remain at a constant speed. Optimizing this process relies on being able to ensure the deployment of as few resources as possible towards the rendering of surfaces that will not end up being displayed to the user.

There are many techniques for hidden-surface determination. They are fundamentally an exercise in sorting and usually vary in the order in which the sort is performed and how the problem is subdivided. Sorting large quantities of graphics primitives is usually done by divide and conquer.

Algorithms

Considering the rendering pipeline, the projection, the clipping, and the rasterization steps are handled differently by the following algorithms:

Z-buffering: During rasterization, the depth/Z value of each pixel (or sample in the case of anti-aliasing, but without loss of generality 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 the one in the Z-buffer. Z-buffering supports dynamic scenes easily and is currently implemented efficiently 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 that the rasterization algorithm needs to 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 buffers (C-buffer) and surface buffer (S-buffer): Faster than Z-buffers and commonly used in games in the Quake I era. Instead of storing the Z value per pixel, they store a list of already displayed segments 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 the nearest to the furthest. Because the C-buffer technique does not require a pixel to be drawn more than once, the process is slightly faster. This was commonly used with binary space partitioning (BSP) trees, which would provide sorting for the polygons.
Sorted active edge list: Used in Quake 1, this was storing a list of the edges of already displayed polygons (see scanline rendering). Polygons are displayed from the nearest to the furthest. New polygons are clipped against already displayed polygons' edges, creating new polygons to display then storing the additional edges. It's much harder to implement than S/C/Z-buffers, but it scales much better with increases in resolution.
Painter's algorithm: Sorts polygons by their barycenter and draws them back to front. This produces few artifacts when applied to scenes with polygons of similar size forming smooth meshes and back-face culling 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, as it cannot handle polygons in various common configurations, such as surfaces that intersect each other.
Binary space partitioning (BSP): Divides a scene along planes corresponding to polygon boundaries. The subdivision is constructed in such a way as to provide an unambiguous depth ordering from any point in the scene when the BSP tree is traversed. The disadvantage here is that the BSP tree is created with an expensive pre-process. This means that it is less suitable for scenes consisting of dynamic geometry. The advantage is that the data is pre-sorted and error-free, ready for the previously mentioned algorithms. Note that the BSP is not a solution to HSR, only an aid.
Ray tracing: Attempts to model the path of light rays to a viewpoint by tracing rays from the viewpoint into the scene. Although not a hidden-surface removal algorithm as such, it implicitly solves the hidden-surface removal problem by finding the nearest surface along each view-ray. Effectively this is equivalent to sorting all the geometry on a per-pixel basis.
The Warnock algorithm: Divides the screen into smaller areas and sorts triangles within these. If there is ambiguity (i.e., polygons overlap in-depth extent within these areas), then further subdivision occurs. At the limit, the subdivision may occur down to the pixel level.

Culling and visible-surface determination

A related area to visible-surface determination (VSD) is culling, which usually happens before VSD in a rendering pipeline. Primitives or batches of primitives can be rejected in their entirety, which usually reduces the load on a well-designed system.

The advantage of culling early on in the pipeline is that entire objects that are invisible do not have to be fetched, transformed, rasterized, or shaded. Types of culling algorithms include:

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 as there is no place to draw them.

Back-face culling

Main article: Back-face culling

With 3D objects, some of the object's surface is facing the camera, and the rest is facing away from the camera, i.e. is on the backside of the object, hindered by the front side. If the object is completely opaque, those surfaces never need to be drawn. They are determined by the vertex winding order: if the triangle drawn has its vertices in clockwise order on the projection plane when facing the camera, they switch into counter-clockwise order when the surface turns away from the camera.

Incidentally, this also makes the objects completely transparent when the viewpoint camera is located inside them, because then all the surfaces of the object are facing away from the camera and are culled by the renderer. To prevent this the object must be set as double-sided (i.e. no back-face culling is done) or have separate inside surfaces.

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. See Clipping plane.

Occlusion culling

Divide and conquer

A popular theme in the VSD literature is divide and conquer. The Warnock algorithm pioneered dividing the screen. Beam tracing is a ray-tracing approach that divides the visible volumes into beams. Various screen-space subdivision approaches reducing the number of primitives considered per region, e.g. tiling, or screen-space BSP clipping. Tiling may be used as a preprocess to other techniques. Z-buffer hardware may typically include a coarse "hi-Z", against which primitives can be rejected early without rasterization, this is a form of occlusion culling.

Bounding volume hierarchies (BVHs) are often used to subdivide the scene's space (examples are the BSP tree, the octree and the kd-tree). This allows visibility determination to be performed hierarchically: effectively, if a node in the tree is considered to be invisible, then all of its child nodes are also invisible, and no further processing is necessary (they can all be rejected by the renderer). If a node is considered visible, then each of its children needs to be evaluated. This traversal is effectively a tree walk, where invisibility/occlusion or reaching a leaf node determines whether to stop or whether to recurse respectively.