In
renderingRendering is the process of generating an image from a model, by means of computer programs. The model is a description of three-dimensional objects in a strictly defined language or data structure. It would contain geometry, viewpoint, texture, lighting, and shading information. The image is a...
,
clipping refers to an optimization where the computer only draws things that might be visible to the viewer.
In
2D graphics2D 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 of the
Mona LisaMona Lisa is a 16th century portrait painted in oil on a poplar panel by Leonardo da Vinci during the Italian Renaissance. The work is owned by the Government of France and is on the wall in the Louvre in Paris, France with the title Portrait of Lisa Gherardini, wife of Francesco del Giocondo...
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.
In
renderingRendering is the process of generating an image from a model, by means of computer programs. The model is a description of three-dimensional objects in a strictly defined language or data structure. It would contain geometry, viewpoint, texture, lighting, and shading information. The image is a...
,
clipping refers to an optimization where the computer only draws things that might be visible to the viewer.
Examples
In
2D graphics2D 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 of the
Mona LisaMona Lisa is a 16th century portrait painted in oil on a poplar panel by Leonardo da Vinci during the Italian Renaissance. The work is owned by the Government of France and is on the wall in the Louvre in Paris, France with the title Portrait of Lisa Gherardini, wife of Francesco del Giocondo...
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.
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 viewThe field of view is the angular extent of the observable world that is seen at any given moment.Different animals have different fields of view, depending on the placement of the eyes. Humans have an almost 180-degree forward-facing field of view, while some birds have a complete or...
, 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 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. It is an optical illusion of motion due to the phenomenon of persistence of vision, and can be created and demonstrated in a number of ways...
s: if the objects are built up of
polygonIn geometry a polygon is traditionally a plane figure that is bounded by a closed path or circuit, composed of a finite sequence of straight line segments . These segments are called its edges or sides, and the points where two edges meet are the polygon's vertices or corners...
s, a routine is needed that determines for each polygon whether it is visible within the
viewportA viewport is a rectangular region in computer graphics. It has several definitions in different contexts:* In 3D computer graphics it refers to the 2D rectangle used to project the 3D scene to the position of a virtual camera....
(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 viewThe field of view is the angular extent of the observable world that is seen at any given moment.Different animals have different fields of view, depending on the placement of the eyes. Humans have an almost 180-degree forward-facing field of view, while some birds have a complete or...
, 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
reflectiveA mirror is an object with at least one polished and therefore specularly reflective surface. The most familiar type of mirror is the plane mirror, which has a flat surface...
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, or frame frequency, is the measurement of 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 chipsA graphics processing unit or GPU is a specialized processor that offloads 3D graphics rendering from the microprocessor. It is used in embedded systems, mobile phones, personal computers, workstations, and game consoles...
that are faster every year, it remains computationally expensive to
transformIn 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 which preserves this structure.Examples include...
,
textureTexture mapping is a method for adding detail, surface texture, or colour 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
shadeIn the field of computer graphics, a shader is a set of software instructions, which 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 developerA video game developer is a software developer that creates video games. A developer may specialize in a certain video game console, such as Sony's PlayStation 3, PSP, Microsoft's Xbox 360, Nintendo's Wii, Nintendo DS, or may develop for a variety of systems, including personal computers.Some...
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
optimizationIn 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
heuristicIn computer science, a heuristic algorithm, or simply a heuristic, is an algorithm that is able to produce an acceptable solution to a problem in many practical scenarios, in the fashion of a general heuristic, but for which there is no formal proof of its correctness...
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 viewThe field of view is the angular extent of the observable world that is seen at any given moment.Different animals have different fields of view, depending on the placement of the eyes. Humans have an almost 180-degree forward-facing field of view, while some birds have a complete or...
. One of the most popular methods for optimization is the use of
octreeAn octree is a tree data structure in which each internal node has up to 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...
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 detectionIn physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids. Simulating what happens once a collision is detected is sometimes referred to as "collision response"...
, the two are often confused.
Algorithms
Several clipping
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
s have been devised.
- Line clipping
In 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
In computer graphics, the Cohen-Sutherland algorithm is a line clipping algorithm. The algorithm divides a 2D space into 9 parts, of which only the middle part is visible.-The algorithm:...
- Liang-Barsky
In computer graphics, the Liang-Barsky algorithm is a line clipping algorithm. The Liang-Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping box to determine the intersections between the line and the clipping box. With these intersections...
- Fast-Clipping
- Cyrus-Beck
- Nicholl-Lee-Nicholl
Nicholl-Lee-Nicholl is one of computer graphics line clipping algorithms. It uses symmetry to categorize endpoints into one of three regions...
- Fast culling for 2D side-scrolling games
- Circle and B-Splines clipping algorithms;
- Polygon clipping algorithms:
- Polygon Structures clipping algorithms: