Line clipping

Last updated
Example of line clipping for a two-dimensional region Line2 clipping.png
Example of line clipping for a two-dimensional region

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.

Contents

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.

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.

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 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

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. [3]

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. [4]

Skala

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

p = r1 × r2 = (x1, y1, w1) × (x2, y2, w2)

or as

p = r1 × r2 = (x1, y1, 1) × (x2, y2, 1).

See also

Related Research Articles

<span class="mw-page-title-main">Line drawing algorithm</span> Methods of approximating line segments for pixel displays

In computer graphics, a line drawing algorithm is an algorithm for approximating a line segment on discrete graphical media, such as pixel-based displays and printers. On such media, line drawing requires an approximation. Basic algorithms rasterize lines in one color. A better representation with multiple color gradations requires an advanced process, spatial anti-aliasing.

<span class="mw-page-title-main">Homogeneous coordinates</span> Coordinate system used in projective geometry

In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work Der barycentrische Calcul, are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. They have the advantage that the coordinates of points, including points at infinity, can be represented using finite coordinates. Formulas involving homogeneous coordinates are often simpler and more symmetric than their Cartesian counterparts. Homogeneous coordinates have a range of applications, including computer graphics and 3D computer vision, where they allow affine transformations and, in general, projective transformations to be easily represented by a matrix. They are also used in fundamental elliptic curve cryptography algorithms.

<span class="mw-page-title-main">Point in polygon</span> Determining where a point is in relation to a coplanar polygon

In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, computer vision, geographic information systems (GIS), motion planning, and computer-aided design (CAD).

The Weiler–Atherton is a polygon-clipping algorithm. It is used in areas like computer graphics and games development where clipping of polygons is needed. It allows clipping of a subject or candidate polygon by an arbitrarily shaped clipping polygon/area/region.

Clipping, in the context of computer graphics, is a method to selectively enable or disable rendering operations within a defined region of interest. Mathematically, clipping can be described using the terminology of constructive geometry. A rendering algorithm only draws pixels in the intersection between the clip region and the scene model. Lines and surfaces outside the view volume are removed.

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 window to determine the intersections between the line and the clip window. With these intersections it knows which portion of the line should be drawn. So this algorithm is significantly more efficient than Cohen–Sutherland. The idea of the Liang–Barsky clipping algorithm is to do as much testing as possible before computing line intersections.

A viewport is a polygon viewing region in computer graphics.

In computer graphics, the Cohen–Sutherland algorithm is an algorithm used for line clipping. The algorithm divides a two-dimensional space into 9 regions and then efficiently determines the lines and portions of lines that are visible in the central region of interest.

In computer graphics, the Nicholl–Lee–Nicholl algorithm is a fast algorithm for line clipping that reduces the chances of clipping a single line segment multiple times, as may happen in the Cohen–Sutherland algorithm.

The clip coordinate system is a homogeneous coordinate system in the graphics pipeline that is used for clipping.

In computational geometry, the problem of computing the intersection of a polyhedron with a line has important applications in computer graphics, optimization, and even in some Monte Carlo methods. It can be viewed as a three-dimensional version of the line clipping problem.

<span class="mw-page-title-main">Boolean operations on polygons</span>

Boolean operations on polygons are a set of Boolean operations operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA.

The Sutherland–Hodgman algorithm is an algorithm used for clipping polygons. It works by extending each line of the convex clip polygon in turn and selecting only vertices from the subject polygon that are on the visible side.

In computer graphics, a digital differential analyzer (DDA) is hardware or software used for interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons. They can be extended to non linear functions, such as perspective correct texture mapping, quadratic curves, and traversing voxels.

The Vatti clipping algorithm is used in computer graphics. It allows clipping of any number of arbitrarily shaped subject polygons by any number of arbitrarily shaped clip polygons. Unlike the Sutherland–Hodgman and Weiler–Atherton polygon clipping algorithms, the Vatti algorithm does not restrict the types of polygons that can be used as subjects or clips. Even complex (self-intersecting) polygons, and polygons with holes can be processed. The algorithm is generally applicable only in 2D space.

<span class="mw-page-title-main">Cyrus–Beck algorithm</span> Line-clipping algorithm in computer graphics

In computer graphics, the Cyrus–Beck algorithm is a generalized algorithm for line clipping. It was designed to be more efficient than the Cohen–Sutherland algorithm, which uses repetitive clipping. Cyrus–Beck is a general algorithm and can be used with a convex polygon clipping window, unlike Cohen-Sutherland, which can be used only on a rectangular clipping area.

In computer graphics programming, hit-testing is the process of determining whether a user-controlled cursor intersects a given graphical object drawn on the screen. Hit-testing may be performed on the movement or activation of a mouse or other pointing device.

The Greiner-Hormann algorithm is used in computer graphics for polygon clipping. It performs better than the Vatti clipping algorithm, but cannot handle degeneracies. It can process both self-intersecting and non-convex polygons. It can be trivially generalized to compute other Boolean operations on polygons, such as union and difference.

You-Dong Liang (梁友栋) is a mathematician and educator, best known for his contributions in geometric modeling and the Liang-Barsky algorithm.

This is a glossary of terms relating to computer graphics.

References

  1. ↑ Renka, R. J. (2014-10-19). "Line Clipping" (PDF). Department of Computer Science & Engineering, University of North Texas. Retrieved 2016-01-12.
  2. ↑ Cyrus, M., Beck, J.: Generalized Two and Three Dimensional Clipping, Computers & Graphics, Vol. 3, No. 1, pp. 23–28, 1978.
  3. ↑ 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.
  4. ↑ Skala, V.: O(lg N) Line Clipping Algorithm in E2, Computers & Graphics, Pergamon Press, Vol. 18, No. 4, 1994.
  5. ↑ 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.