In computer graphics, line clipping is the process of removing (clipping) lines or portions of lines outside an area of interest (a viewport or view volume). Typically, any part of a line which is outside of the viewing area is removed.
Example of line clipping for a two-dimensional region
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 calculations are carried out with one or more clipping boundaries.[1] 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.
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.
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.
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 clipping a line in the parametric form against a convex polygon in 2 dimensions or against a convex polyhedron in 3 dimensions.[2]
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 clippingedit
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.[3]
O(lg N) algorithmedit
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.[4]
Skalaedit
This algorithm is based on homogeneous coordinates and duality.[5] 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 r1, r2 given in homogeneous coordinates directly using the cross product as
^Renka, R. J. (2014-10-19). "Line Clipping" (PDF). Department of Computer Science & Engineering, University of North Texas. Retrieved 2016-01-12.
^Cyrus, M., Beck, J.: Generalized Two and Three Dimensional Clipping, Computers & Graphics, Vol. 3, No. 1, pp. 23–28, 1978.
^Mark S. Sobkow, Paul Pospisil and Yee-Hong Yang. A Fast Two-Dimensional Line Clipping Algorithm via Line Encoding//Computer & Graphics, Vol. 11, No. 4, pp. 459–467, 1987.
^Skala, V.: O(lg N) Line Clipping Algorithm in E2, Computers & Graphics, Pergamon Press, Vol. 18, No. 4, 1994.
^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.
January 01, 1970
line, clipping, computer, graphics, line, clipping, process, removing, clipping, lines, portions, lines, outside, area, interest, viewport, view, volume, typically, part, line, which, outside, viewing, area, removed, example, line, clipping, dimensional, regio. In computer graphics line clipping is the process of removing clipping lines or portions of lines outside an area of interest a viewport or view volume Typically any part of a line which is outside of the viewing area is removed Example of line clipping for a two dimensional region 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 calculations are carried out with one or more clipping boundaries 1 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 Contents 1 Cohen Sutherland 2 Liang Barsky 3 Cyrus Beck 4 Nicholl Lee Nicholl 5 Fast clipping 6 O lg N algorithm 7 Skala 8 See also 9 ReferencesCohen Sutherland editMain article Cohen Sutherland algorithm 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 editMain article Liang Barsky 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 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 Cyrus Beck editMain article Cyrus Beck algorithm 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 clipping a line in the parametric form against a convex polygon in 2 dimensions or against a convex polyhedron in 3 dimensions 2 Nicholl Lee Nicholl editMain article Nicholl Lee Nicholl algorithm 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 editThis 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 3 O lg N algorithm editThis 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 4 Skala editThis algorithm is based on homogeneous coordinates and duality 5 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 r1 r2 given in homogeneous coordinates directly using the cross product as p r1 r2 x1 y1 w1 x2 y2 w2 or as p r1 r2 x1 y1 1 x2 y2 1 See also editClipping computer graphics References edit Renka R J 2014 10 19 Line Clipping PDF Department of Computer Science amp Engineering University of North Texas Retrieved 2016 01 12 Cyrus M Beck J Generalized Two and Three Dimensional Clipping Computers amp Graphics Vol 3 No 1 pp 23 28 1978 Mark S Sobkow Paul Pospisil and Yee Hong Yang A Fast Two Dimensional Line Clipping Algorithm via Line Encoding Computer amp Graphics Vol 11 No 4 pp 459 467 1987 Skala V O lg N Line Clipping Algorithm in E2 Computers amp Graphics Pergamon Press Vol 18 No 4 1994 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 Retrieved from https en wikipedia org w index php title Line clipping amp oldid 1194338730 Fast clipping, wikipedia, wiki, book, books, library,
