computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...

, line clipping is the process of removing ( clipping) lines or portions of lines outside an area of interest (a viewport or

view volume In 3D computer graphics, the view frustum (also called viewing frustum) is the region of space in the modeled world that may appear on the screen; it is the field of view of a perspective virtual camera system. The view frustum is typically ...

). Typically, any part of a line which is outside of the viewing area is removed. There are two common algorithms for line clipping: Cohen–Sutherland and Liang–Barsky. A line-clipping method consists of various parts. Tests are conducted on a given line segment to find out whether it lies outside the view area or volume. Then,

intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...

calculations are carried out with one or more clipping boundaries. Determining which portion of the line is inside or outside of the clipping volume is done by processing the endpoints of the line with regards to the intersection.

Cohen–Sutherland

In computer graphics, the Cohen–Sutherland algorithm (named after Danny Cohen and Ivan Sutherland) is a line-clipping algorithm. The algorithm divides a 2D space into 9 regions, of which only the middle part (viewport) is visible. In 1967, flight-simulation work by Danny Cohen led to the development of the Cohen–Sutherland computer graphics two- and three-dimensional line clipping algorithms, created with Ivan Sutherland.

Liang–Barsky

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 it knows which portion of the line should be drawn. This algorithm is significantly more efficient than Cohen–Sutherland, but Cohen–Sutherland does trivial accepts and rejects much faster, so it should be considered instead if most of the lines you need to clip would be completely in or out of the

clip window This is a glossary of terms relating to computer graphics. For more general computer hardware terms, see glossary of computer hardware terms. 0–9 A B ...

Cyrus–Beck

Very similar to Liang–Barsky line-clipping algorithm. The difference is that Liang–Barsky is a simplified Cyrus–Beck variation that was optimized for a rectangular clip window. The Cyrus–Beck algorithm is primarily intended for a clipping a line in the parametric form against a convex polygon in 2 dimensions or against a convex polyhedron in 3 dimensions.

Nicholl–Lee–Nicholl

The Nicholl–Lee–Nicholl algorithm is a fast line-clipping algorithm that reduces the chances of clipping a single line segment multiple times, as may happen in the Cohen–Sutherland algorithm. The clipping window is divided into a number of different areas, depending on the position of the initial point of the line to be clipped.

Fast clipping

This algorithm has similarities with Cohen–Sutherland. The start and end positions are classified by which portion of the 9-area grid they occupy. A large switch statement jumps to a specialized handler for that case. In contrast, Cohen–Sutherland may have to iterate several times to handle the same case.

''O''(lg ''N'') algorithm

This algorithm classifies vertices against the given line in the implicit form ''p'': ''ax'' + ''by'' + ''c'' = 0. As the polygon is assumed to be convex and vertices are ordered clockwise or anti-clockwise, binary search can be applied and leads to a ''O''(lg ''N'') run-time complexity.

Skala

This algorithm is based on

homogeneous coordinates In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. T ...

and

duality Duality may refer to: Mathematics * Duality (mathematics), a mathematical concept ** Dual (category theory), a formalization of mathematical duality ** Duality (optimization) ** Duality (order theory), a concept regarding binary relations ** Dual ...

.Skala, V.
A new approach to line and line segment clipping in homogeneous coordinates
The Visual Computer, ISSN 0178-2789, Vol. 21, No. 11, pp. 905–914, Springer Verlag, 2005. It can be used for line or line-segment clipping against a rectangular window, as well as against a convex polygon. The algorithm is based on classifying a vertex of the clipping window against a half-space given by a line ''p'': ''ax'' + ''by'' + ''c'' = 0. The result of the classification determines the edges intersected by the line ''p''. The algorithm is simple, easy to implement and extensible to a convex window as well. The line or line segment p can be computed from points r₁, r₂ given in homogeneous coordinates directly using the cross product as :p = r₁ × r₂ = (''x''₁, ''y''₁, ''w''₁) × (''x''₂, ''y''₂, ''w''₂) or as :p = r₁ × r₂ = (''x''₁, ''y''₁, 1) × (''x''₂, ''y''₂, 1).

References

{{DEFAULTSORT:Line Clipping Clipping (computer graphics)