Browse Prior Art Database

Arc Clipping Algorithm

IP.com Disclosure Number: IPCOM000060333D
Original Publication Date: 1986-Mar-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 4 page(s) / 52K

Publishing Venue

IBM

Related People

Niblett, PD: AUTHOR

Abstract

This article describes a method by which an arc rastering routine may be modified to generate an elliptic arc clipped to a rectangular window. The algorithm described here traces around the ellipse, splitting it into visible and invisible segments. THE PROBLEM Various algorithms have been proposed to raster a circular or elliptic arc defined by an analytic equation of the form: ax2 + 2hxy + by2 = ab - h2 about a given center point (here assumed to be integral). The algorithms all operate in a similar manner, tracking around the boundary of the ellipse and causing the appropriate points to be drawn. This article discusses a way in which clipping against a rectangular window may be added to these algorithms.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 4

Arc Clipping Algorithm

This article describes a method by which an arc rastering routine may be modified to generate an elliptic arc clipped to a rectangular window. The algorithm described here traces around the ellipse, splitting it into visible and invisible segments. THE PROBLEM Various algorithms have been proposed to raster a circular or elliptic arc defined by an analytic equation of the form: ax2 + 2hxy + by2 = ab - h2 about a given center point (here assumed to be integral). The algorithms all operate in a similar manner, tracking around the boundary of the ellipse and causing the appropriate points to be drawn. This article discusses a way in which clipping against a rectangular window may be added to these algorithms.

(Image Omitted)

In this example the arc indicated by asterisks has been clipped at the top to lie within the rectangle RSTU. This rectangle might be an application-defined clip window, the boundaries of a display screen or a printer swathe. There are three parts to the problem: o Clipping a full arc - it could split into up to four distinct visible segments. o Coping with start and stop points, which may lie either inside or outside the window. o Handling an arc received as part of an area boundary definition. The arc's behavior outside the window may have to be communicated to an area fill process, typically by projecting it onto the vertical window boundaries. The rastering algorithm clearly has to be adapted so that it can detect when it is about to cross one of the clipping boundaries (for example, when at point P above). It is what happens next that is of interest. A commonly favored approach is to continue to "generate" points outside the window, but to discard them before attempting to draw them. If the arc forms part of a boundary definition, these discarded points have to be projected onto the vertical window boundaries. This method can be very time consuming as an eccentric ellipse may continue a long way beyond the boundary. Furthermore, the internal variables used by the algorithm may exceed the register size being used in a particular implementation. The new algorithm is described for an arc that is being drawn in an anticlockwise sense. The visible segments are rastered by the normal rastering routine, and the invisible are ignored or passed as straight lines to a line-clipping routine if the arc is part of an area definition. Processing stops when the stopping point is reached. 1.Set current position to the start point. 2. Test current position against the four edges of the clip window. a. If left of the left edge, then set current position to the lower intersection of the arc with the left edge. b. If below the bottom edge, then set current position to the rightmost intersection of the arc with the bottom edge. c. If right of the right edge, then set current position to the upper intersection of the arc with the right edge. d. If above the top edge, then set current position to the leftmost...