Clipping (computer graphics)
Any procedure which identifies that portion of a picture which is either inside or outside a region is referred to as a clipping algorithm or clipping. The region against which an object is to be clipped is called clipping window.
Examples
In 2D graphics 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° 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.
Non-triviality
Clipping is non-trivial, especially for 3D animations: if the objects are built up of polygons, 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 a car if a building stands between the observer and the car, completely obscuring it; the cars' polygons are all completely occluded by the building. Hence the software can save significant rendering time by doing an occlusion 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.
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 rate 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 developers 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 octrees to partition scenes into rendered and non-rendered areas.
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.
Due to the use of the term 'no clipping' to refer to turning off collision detection, the two are often confused.
In 3D gaming, "to clip through" is also sometimes used to refer to the situation in which part of a model passes through part of another in an unnatural manner, like a leg passing through a cape when running.
Algorithms
Several clipping algorithms have been devised.
- Line clipping 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
- Vatti
- Patrick-Gilles Maillot 2D polygon clipping using integer or floating point - Sun Microsystems' patent #5079719, 1989.
- Polygon Structures clipping algorithms: