Clipping (computer graphics): Difference between revisions

Revision as of 23:53, 13 January 2007

Latest revision as of 19:38, 17 December 2023

(206 intermediate revisions by more than 100 users not shown)

Line 1:

{{Short description|Excluding certain graphical elements from being rendered in a scene}}

{{Cleanup-verify}}

{{Multiple issues|

{{Confusing|December 2006}}

{{original research|date=August 2015}}

In [[rendering (computer graphics)|rendering]], '''clipping''' refers to an optimization where the computer only draws things that might be visible to the viewer.

{{more citations needed|date=August 2015}}

}}

'''Clipping''', in the context of [[computer graphics]], is a method to selectively enable or disable [[rendering (computer graphics)|rendering operations]] within a defined [[region of interest]]. Mathematically, clipping can be described using the terminology of [[constructive geometry]]. A [[rendering algorithm]] only draws [[pixel]]s in the [[intersection]] between the clip region and the scene model. Lines and surfaces outside the [[view volume]] (aka. frustum) are removed.<ref name="bertoline-graphics-comm">{{cite book |last1=Bertoline |first1=Gary |last2=Wiebe |first2=Eric |title=Fundamentals of Graphics Communication |page=G-3 |date=2002 |edition=3rd |isbn=0-07-232209-8 |url=https://archive.org/details/fundamentalsofgr00bert |publisher=McGraw-Hill |access-date=2015-01-04 |url-access=registration }}</ref>

==Examples==

In [[2D computer graphics|2D graphics]] for example, if the user of an image editing program is modifying an image of the [[Mona Lisa]] and has "zoomed in" the view to display only the top half of the painting, there is no need for the program to spend any [[CPU]] time doing any of the calculations or memory moves needed to display the bottom half. By clipping the bottom half of the painting and avoiding these calculations, the program runs faster.

Clip regions are commonly specified to improve render performance. A well-chosen clip{{clarify|clip region?|date=December 2023}} allows the renderer to save time and energy by skipping calculations related to pixels that the user cannot see. Pixels that will be drawn are said to be within the clip region. Pixels that will not be drawn are outside the clip region. More informally, pixels that will not be drawn are said to be "clipped."

In [[3-D computer graphics|3D graphics]], in a city street scene the computer may have model, texture, and shader data in memory for every building in the city; but since the camera viewing the scene only sees things within, say, a 90° angle, or [[field of view]], the computer does not need to transform, texture, and shade the buildings that are behind the camera, nor those which are far enough to the side that they are off the screen. The clipping algorithm lets the rendering code skip all consideration of those buildings, and the program runs faster.

== In 2D graphics ==

==Non-triviality==

In two-dimensional graphics, a clip region may be defined so that pixels are only drawn within the boundaries of a [[window (computing)|window]] or frame. Clip regions can also be used to selectively control pixel rendering for aesthetic or artistic purposes. In many implementations, the final clip region is the composite (or intersection) of one or more application-defined shapes, as well as any system hardware constraints

Clipping is non-trivial, especially for 3D [[animation]]s: if the objects are built up of, say, [[polygon]]s, a routine is needed that determines for each polygon whether it is visible within the [[viewport]] (i.e. the part of the 3D "world" displayed) or out off the borders. Special care is needed for the case of polygons intersected by the viewport border as their shape has to be adjusted.

In one example application, consider an image editing program. A user application may render the image into a viewport. As the user zooms and scrolls to view a smaller portion of the image, the application can set a clip boundary so that pixels outside the viewport are not rendered. In addition, [[GUI widget]]s, overlays, and other [[windowing system|windows or frames]] may obscure some pixels from the original image. In this sense, the clip region is the composite of the application-defined "user clip" and the "device clip" enforced by the system's software and hardware implementation.<ref name="java-awt-graphics-javadoc"/> Application software can take advantage of this clip information to save computation time, energy, and memory, avoiding work related to pixels that aren't visible.

While the term "clipping" is generally used to mean avoiding the drawing of things outside the camera's [[field of view]], a related technique is [[back-face culling]], in which polygons ''within'' the field of view are not drawn if they would be occluded by other polygons. For example, there is no need to render the polygons comprising the side of a building facing away from the player; they are all completely occluded by the front of the building. Hence the game can save significant rendering time by doing a back-face culling pass before deciding which polygons to draw.

== In 3D graphics ==

The clipping and back-face culling optimizations both present interesting problems in scenes with a [[mirror|reflective]] surface visible. For example, problems would ensue if the 3D scene contained a mirror that showed the reflection of a building that had been clipped because the building was behind the camera. To deal with 'true' reflective surfaces (as opposed to the 'fake' reflections of [[environment map]]s), the clipper might do a clipping and rendering pass from the point of view of the mirror, and then the normal clipping pass for the camera.

[[Image:ViewFrustum.svg|thumb|right|A view frustum, with near- and far- clip planes. Only the shaded volume is rendered.]]

In three-dimensional graphics, the terminology of clipping can be used to describe many related features. Typically, "clipping" refers to operations in the plane that work with rectangular shapes, and "culling" refers to more general methods to selectively process scene model elements. This terminology is not rigid, and exact usage varies among many sources.

Scene model elements include geometric primitives: points or vertices; line segments or edges; polygons or faces; and more abstract model objects such as curves, splines, surfaces, and even text. In complicated scene models, individual elements may be selectively disabled (clipped) for reasons including visibility within the viewport ([[frustum culling]]); orientation ([[backface culling]]), obscuration by other scene or model elements ([[occlusion culling]], depth- or "z" clipping). Sophisticated algorithms exist to efficiently detect and perform such clipping. Many optimized clipping methods rely on specific hardware acceleration logic provided by a [[graphics processing unit]] (GPU).

==Video games==

Good clipping strategy is important in the development of [[video games]] in order to maximize the game's [[frame rate]] and visual quality. Despite [[graphics processing unit|GPU chips]] that are faster every year, it remains computationally expensive to [[transformation (mathematics)|transform]], [[texture mapping|texture]], and [[shader|shade]] polygons, especially with the multiple texture and shading passes common today. Hence, [[game developer]]s must live within a certain "budget" of polygons that can be drawn each video frame. (Normally there are 30 video frames drawn per second on an American or Japanese ([[NTSC]]) video game console, or 25 video frames per second on a European ([[PAL]]) console.) To maximize the game's visual quality, developers prefer to establish the highest possible polygon budget; therefore, every optimization of the graphics pipeline benefits the polygon budget and therefore the game.

The concept of clipping can be extended to higher dimensionality using methods of abstract [[algebraic geometry]].

In video games, then, clipping is a critically important [[optimization (computer science)|optimization]] that speeds up the rendering of the current scene, and therefore allows the developer to increase the renderer's polygon budget. Programmers often devise clever [[heuristic (computer science)|heuristic]]s to speed up the clipper, as it would be computationally prohibitive to use line casting or [[ray tracing]] to determine with 100% accuracy which polygons are and are not within the camera's [[field of view]]. One of the most popular methods for optimization is the use of [[Octree]]s to partition scenes into rendered and non-rendered areas.

=== Near clipping ===

The clipping problems introduced by reflective surfaces are generally avoided in games [[as of 2005]] by simulating reflections without actually doing all the calculations that would be necessary for accurate reflections.

Beyond projection of vertices & 2D clipping, near clipping is required to correctly rasterise 3D primitives; this is because vertices may have been projected behind the eye. Near clipping ensures that all the vertices used have valid 2D coordinates. Together with '''far-clipping''' it also helps prevent overflow of depth-buffer values. Some early [[texture mapping hardware]] (using [[forward texture mapping]]) in video games suffered from complications associated with near clipping and [[UV coordinates]].

=== Occlusion clipping (Z- or depth clipping) ===

==Algorithms==

{{Main|depth buffer|occlusion culling}}

Several clipping [[algorithm]]s have been devised.

In 3D computer graphics, "Z" often refers to the depth axis in the system of coordinates centered at the viewport origin: "Z" is used interchangeably with "depth", and conceptually corresponds to the distance "into the virtual screen." In this coordinate system, "X" and "Y" therefore refer to a conventional [[cartesian coordinate]] system laid out on the user's screen or [[viewport]]. This viewport is defined by the geometry of the [[viewing frustum]], and parameterizes the [[field of view]].

Z-clipping, or depth clipping, refers to techniques that selectively render certain scene objects based on their depth relative to the screen. Most graphics toolkits allow the programmer to specify a "near" and "far" clip depth, and only portions of objects between those two planes are displayed. A creative application programmer can use this method to render visualizations of the interior of a 3D object in the scene. For example, a [[medical imaging]] application could use this technique to render the organs inside a human body. A video game programmer can use clipping information to accelerate game logic.<ref name="gpu-gems-1-29"/> For example, a tall wall or building that occludes other game entities can save GPU time that would otherwise be spent transforming and texturing items in the rear areas of the scene; and a tightly integrated software program can use this same information to save CPU time by optimizing out game logic for objects that aren't seen by the player.<ref name="gpu-gems-1-29"/>

== Algorithms ==

* '''[[Line clipping]] algorithms''':

** [[Cohen-SutherlandCohen–Sutherland]]

** [[Liang-BarskyLiang–Barsky]]

** [[Line clipping#Fast clipping|Fast-Clippingclipping]]

** [[Line clipping#Cyrus–Beck|Cyrus–Beck]]

** [[Nicholl-Lee-Nicholl]]

** [[Nicholl–Lee–Nicholl]]

** [[Line clipping#Skala|Skala]]

** [[Line clipping#O(lg N) algorithm|O(lg ''N'') algorithm]]

* '''Polygon clipping algorithms''':

** [[Greiner–Hormann clipping algorithm|Greiner–Hormann]]

** [[Sutherland–Hodgman]]

** [[Weiler–Atherton]]

** [[Vatti clipping algorithm|Vatti]]

* Rendering methodologies

** [[Painter's algorithm]]

== See also ==

* '''Circle and B-Splines clipping algorithms''';

* [[Boolean operations on polygons]]

** [http://www.chez.com/pmaillot Patrick-Gilles Maillot's Thesis] on computer Graphics, pages 52 (circle), 53 (B-Splines) and respective algorithms pages 95 and 97.

* [[Bounding volume]]

* [[Clip space]]

* [[Distance fog]]

* [[Guard-band clipping]]

* [[Hidden-surface determination]]

* [[Pruning (decision trees)]]

* [[Visibility (geometry)]]

== Further reading ==

* '''Polygon clipping algorithms''':

* GPU Gems: Efficient Occlusion Culling <ref name="gpu-gems-1-29">{{cite book |last=Sekulic |first=Dean |date=2004 |title=GPU Gems |url=https://developer.nvidia.com/content/gpu-gems |chapter=Efficient Occlusion Culling |chapter-url=http://http.developer.nvidia.com/GPUGems/gpugems_ch29.html |publisher=Pearson |access-date=2015-01-02 |archive-url=https://web.archive.org/web/20130605124431/https://developer.nvidia.com/content/gpu-gems |archive-date=2013-06-05 |url-status=dead }}</ref>

** [[Sutherland-Hodgman]]

* Clipping in [[Java AWT]]: [http://docs.oracle.com/javase/8/docs/api/java/awt/Graphics.html#clipRect-int-int-int-int- <code>java.awt.Graphics.clipRect</code> JavaDoc] <ref name="java-awt-graphics-javadoc">{{cite web |url=http://docs.oracle.com/javase/8/docs/api/java/awt/Graphics.html#clipRect-int-int-int-int- |title=java.awt.Graphics.clipRect |publisher=Oracle | date=2014}}</ref>

** [[Weiler-Atherton]]

* Clipping in UIKit for [[iOS]] (2D): [https://developer.apple.com/library/ios/documentation/UIKit/Reference/UIKitFunctionReference/index.html#//apple_ref/c/func/UIRectClip <code>UIRectClip</code>]

** [http://www.chez.com/pmaillot Optimized 2D Polygon Clipping (Patrick-Gilles Maillot)]

* Clipping in SceneKit for iOS (3D): [https://developer.apple.com/library/mac/documentation/SceneKit/Reference/SCNCamera_Class/index.html#//apple_ref/occ/instp/SCNCamera/zNear <code>SCNCamera</code> ''(Adjusting Camera Perspective)'']

* Clipping in [[OpenGL]]: [https://www.opengl.org/archives/resources/faq/technical/clipping.htm OpenGL Technical FAQs: ''Clipping, Culling, and Visibility Testing'']<ref name="OpenGL-tech-faq-10">{{cite web |url=https://www.opengl.org/archives/resources/faq/technical/clipping.htm |title=Clipping, Culling, and Visibility Testing|author=Paul Martz |date=2001 |website=OpenGL.org|access-date=2015-01-02}}

</ref>

== References ==

* '''Polygon Structures clipping algorithms''':

<references />

** [http://www.chez.com/pmaillot Triangle Strips and Quad-Meshes 3D Homogeneous Clipping (Patrick-Gilles Maillot)]

{{Computer graphics}}

==See also==

*[[Bounding volume]]

[[Category:Clipping (computer graphics)| ]]

[[Category:Computer graphics]]

[[Category:Computer graphic artifacts]]

[[nl:Clipping (afbeelding)]]