Clipping (computer graphics)
From Wikipedia, the free encyclopedia
 |
This article or section may be confusing or unclear for many readers. Please improve the article or discuss this issue on the talk page. This article has been tagged since December 2006. |
In rendering, clipping refers to an optimization where the computer only draws things that might be visible to the viewer.
Contents |
[edit] Examples
In 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.
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.
[edit] Non-triviality
Clipping is non-trivial, especially for 3D animations: if the objects are built up of, say, 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 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.
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.
The clipping and back-face 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.
[edit] 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. (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.
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.
Mameri and Nascimento [1] have proposed an efficient clipping algorithm for video games. It takes advantage of the way video games work to optimize performance. Although their published work focuses 2D games, the original algorithm can be easily extended to 3D.
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.
[edit] Algorithms
Several clipping algorithms have been devised.
- Line clipping algorithms:
- Cohen-Sutherland
- Liang-Barsky
- Fast-Clipping
- Nicholl-Lee-Nicholl
- 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:
- Polygon Structures clipping algorithms:
[edit] See also
[edit] References
- ^ F. Mameri and R. Nascimento (November 2006). "A Fast Culling Algorithm for 2D and 2.5D Side-scrolling Games". Digital Proceedings of the V Brazilian Symposium on Computer Games and Digital Entertainment. ISBN: 85-7669-098-5.
