Line clipping: Difference between revisions
No edit summary |
|||
| Line 5: | Line 5: | ||
==Cohen–Sutherland== |
==Cohen–Sutherland== |
||
{{Main| |
{{Main|Cohen–Sutherland}} |
||
This algorithm divides a 2D space into 9 parts, of which only the middle part (viewport) is visible. The algorithm includes, excludes or partially includes the line based on where the two endpoints are: |
This algorithm divides a 2D space into 9 parts, of which only the middle part (viewport) is visible. The algorithm includes, excludes or partially includes the line based on where the two endpoints are: |
||
Revision as of 06:07, 22 February 2011
In computer graphics, line clipping is the process of removing lines or portions of lines outside of an area of interest. Typically, any line or part thereof which is outside of the viewing area is removed.
There are two common algorithms for line clipping: Cohen–Sutherland and Liang–Barsky.
Cohen–Sutherland
This algorithm divides a 2D space into 9 parts, of which only the middle part (viewport) is visible. The algorithm includes, excludes or partially includes the line based on where the two endpoints are:
- Both endpoints are in the viewport (bitwise OR of endpoints == 0): trivial accept.
- Both endpoints are in the same part, which is not visible (bitwise AND of endpoints != 0): trivial reject.
- Both endpoints are in different parts: In case of this non trivial situation the algorithm finds one of the two points that are outside the viewport (there is at least one point outside). The intersection of the outpoint and extended viewport border is then calculated (i.e. with the parametric equation for the line) and this new point replaces the outpoint. The algorithm repeats until a trivial accept or reject occurs.
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. It eliminates the disadvantages of Cohen-Sutherland clipping algorithm.
Cyrus–Beck
liang barskey method was developed to form cyrus beck algorithm
Nicholl–Lee–Nicholl
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. [1]
See also
References
- ^ 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.
 |