Clipping (computer graphics)
Encyclopedia
Any procedure which identifies that portion of a picture which is either inside or outside a picture is referred to as a clipping algorithm or clipping.
The region against which an object is to be clipped is called clipping window.
for example, if the user of an image editing program is modifying an image and has "zoomed in" the view to display only the top half of the image, 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 image and avoiding these calculations, the program runs faster.
In 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.
s: if the objects are built up of 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 cut off the borders. Special care is needed for the case of polygons intersected by the viewport border as their shape has to be adjusted.
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 occlusion 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 composing the side of a building facing away from the observer; they are all completely occluded by the front of the building. Hence the software can save significant rendering time by doing a back-face culling pass before deciding which polygons to draw.
The clipping, back-face and occlusion culling optimizations both present interesting problems in scenes with a 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 maps), 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.
and visual quality. Despite GPU chips
that are faster every year, it remains computationally expensive to transform
, texture
, and 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.
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.
In video games, then, clipping is a critically important 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 heuristics 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.
The clipping problems introduced by reflective surfaces are generally avoided in games by simulating reflections without actually doing all the calculations that would be necessary for accurate reflections.
Due to the use of the term 'no clipping' to refer to turning off collision detection
, the two are often confused.
s have been devised.
The region against which an object is to be clipped is called clipping window.
Examples
In 2D graphics2D computer graphics
2D computer graphics is the computer-based generation of digital images—mostly from two-dimensional models and by techniques specific to them...
for example, if the user of an image editing program is modifying an image and has "zoomed in" the view to display only the top half of the image, 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 image and avoiding these calculations, the program runs faster.
In 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
Field of view
The field of view is the extent of the observable world that is seen at any given moment....
, 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.
Non-triviality
Clipping is non-trivial, especially for 3D animationAnimation
Animation is the rapid display of a sequence of images of 2-D or 3-D artwork or model positions in order to create an illusion of movement. The effect is an optical illusion of motion due to the phenomenon of persistence of vision, and can be created and demonstrated in several ways...
s: if the objects are built up of polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
s, a routine is needed that determines for each polygon whether it is visible within the viewport
Viewport
A viewport is a rectangular viewing region in computer graphics, or a term used for optical components. It has several definitions in different contexts:- Computing :...
(i.e. the part of the 3D "world" displayed) or cut off the borders. Special care is needed for the case of polygons intersected by the viewport border as their shape has to be adjusted.
While the term "clipping" is generally used to mean avoiding the drawing of things outside the camera's field of view
Field of view
The field of view is the extent of the observable world that is seen at any given moment....
, a related technique is occlusion 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 composing the side of a building facing away from the observer; they are all completely occluded by the front of the building. Hence the software can save significant rendering time by doing a back-face culling pass before deciding which polygons to draw.
The clipping, back-face and occlusion culling optimizations both present interesting problems in scenes with a reflective
Mirror
A mirror is an object that reflects light or sound in a way that preserves much of its original quality prior to its contact with the mirror. Some mirrors also filter out some wavelengths, while preserving other wavelengths in the reflection...
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 maps), 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.
Importance of clipping in video games
Good clipping strategy is important in the development of video games in order to maximize the game's frame rateFrame rate
Frame rate is the frequency at which an imaging device produces unique consecutive images called frames. The term applies equally well to computer graphics, video cameras, film cameras, and motion capture systems...
and visual quality. Despite GPU chips
Graphics processing unit
A graphics processing unit or GPU is a specialized circuit designed to rapidly manipulate and alter memory in such a way so as to accelerate the building of images in a frame buffer intended for output to a display...
that are faster every year, it remains computationally expensive to transform
Transformation (mathematics)
In mathematics, a transformation could be any function mapping a set X on to another set or on to itself. However, often the set X has some additional algebraic or geometric structure and the term "transformation" refers to a function from X to itself that preserves this structure.Examples include...
, texture
Texture mapping
Texture mapping is a method for adding detail, surface texture , or color to a computer-generated graphic or 3D model. Its application to 3D graphics was pioneered by Dr Edwin Catmull in his Ph.D. thesis of 1974.-Texture mapping:...
, and shade
Shader
In the field of computer graphics, a shader is a computer program that is used primarily to calculate rendering effects on graphics hardware with a high degree of flexibility...
polygons, especially with the multiple texture and shading passes common today. Hence, game developer
Video game developer
A video game developer is a software developer that creates video games. A developer may specialize in a certain video game console, such as Nintendo's Wii, Microsoft's Xbox 360, Sony's PlayStation 3, or may develop for a variety of systems, including personal computers.Most developers also...
s must live within a certain "budget" of polygons that can be drawn each video frame.
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.
In video games, then, clipping is a critically important optimization
Optimization (computer science)
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...
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 heuristics 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
Field of view
The field of view is the extent of the observable world that is seen at any given moment....
. One of the most popular methods for optimization is the use of octree
Octree
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
s to partition scenes into rendered and non-rendered areas.
The clipping problems introduced by reflective surfaces are generally avoided in games by simulating reflections without actually doing all the calculations that would be necessary for accurate reflections.
Due to the use of the term 'no clipping' to refer to turning off collision detection
Collision detection
Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics...
, the two are often confused.
Algorithms
Several clipping algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s have been devised.
- Line clippingLine clippingIn computer graphics, line clipping is the process of removing lines or portions of lines outside of an area of interest. Typically, any line or part thereof which is outside of the viewing area is removed....
algorithms:- Cohen–Sutherland
- Liang–Barsky
- Fast-clipping
- Cyrus–Beck
- Nicholl–Lee–Nicholl
- Fast culling for 2D side-scrolling games
- Skala
- O(lg N) Algorithm
- Circle and B-Splines clipping algorithms;
- Patrick-Gilles Maillot's Thesis on computer Graphics, pages 52 (circle), 53 (B-Splines) and respective algorithms pages 95 and 97.
- Polygon clipping algorithms:
- Sutherland–Hodgman
- Weiler–Atherton
- VattiVatti clipping algorithmThe Vatti clipping algorithm is used in computer graphics. It allows clipping of any number of arbitrarily shaped subject polygons by any number of arbitrarily shaped clip polygons. Unlike the Sutherland–Hodgman and Weiler–Atherton polygon clipping algorithms, the Vatti algorithm does not restrict...
- Polygon Structures clipping algorithms: