Browse Prior Art Database

Arc Rastering Algorithm

IP.com Disclosure Number: IPCOM000060750D
Original Publication Date: 1986-May-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 3 page(s) / 38K

Publishing Venue

IBM

Related People

Niblett, PD: AUTHOR

Abstract

This article describes a method of rastering an elliptic arc to an all points addressable buffer. It is applicable to a graphics display device or to a plotter or printer. The technique can be shown always to generate accurate approximations to the ideal arc, something not always possible with previous algorithms. An elliptic arc may be specified by a center point (which is taken as the origin of our coordinate system) and an analytic equation of the form f(x,y) = 0 where f(x,y) = Ax2 + 2Hxy + By2 - AB + H2 A,B >= 0 Start and stop point may also be specified if a partial arc is required. NOTE: This assumes that the center point of the arc has been coerced to lie on a real pel (picture element). This is desirable in any case as it causes the arc to appear symmetrical.

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 50% of the total text.

Page 1 of 3

Arc Rastering Algorithm

This article describes a method of rastering an elliptic arc to an all points addressable buffer. It is applicable to a graphics display device or to a plotter or printer. The technique can be shown always to generate accurate approximations to the ideal arc, something not always possible with previous algorithms. An elliptic arc may be specified by a center point (which is taken as the origin of our coordinate system) and an analytic equation of the form f(x,y) = 0 where f(x,y) = Ax2 + 2Hxy + By2 - AB + H2 A,B >= 0 Start and stop point may also be specified if a partial arc is required. NOTE: This assumes that the center point of the arc has been coerced to lie on a real pel (picture element). This is desirable in any case as it causes the arc to appear symmetrical. The equation defines an 'ideal' ellipse consisting of points in continuous two-dimensional space. A set of points in our discrete APA (all-points-addressable) buffer have to be found, that in some sense approximate the arc. There are several possible criteria that can be used to decide which points to include in our approximation. Readers familiar with the theory of metric spaces will recognize the criteria as being the balls of radius 1/2 defined by simple metrics. CIRCLE OR EUCLIDEAN METRIC CRITERION. Imagine each pel in the buffer to be surrounded by a circular disk half a pel in radius. The pel is to be used in the approximation if and only if the ideal ellipse intersects the disk. SQUARE METRIC CRITERION. Imagine each pel in the buffer to be surrounded by a square with corners at (x + 1/2, y Å 1/2) and (x - 1/2, y Å 1/2). The pel is to be used in the approximation if and only if the ideal ellipse intersects the square. DIAMOND METRIC CRITERION. Imagine each pel in the buffer to be surrounded by a diamond with corners at (x Å 1/2,y) and (x,y Å 1/2). The pel is to be used in the approximation if and only if the ideal ellipse intersects the diamond. Of the three criteria, the square is the most easy to implement but also gives the least pleasing results; too many pels are turned on, and the curve drawn looks thick and splotchy. The circle criterion would seem to be the natural choice, but suffers from the same defects. Of the three, the best results are obtained with the diamond criterion and in fact it is the diamond approximation to a straight line that is produced by Bresenham's line drawing algorithm. The diamond approximation may be reduced to the square approximation by applying the following transformation

(Image Omitted)

This transformation is in fact an enlargement by sqrt(2) and a rotation of 45 degrees and so causes the diamonds to become squares. The coefficients A,B,H transform to A',B',H', where A' = A + B - 2H B' = A + B + 2H H' = A - B The diamond approximation to the arc with coefficients A,B,H can be obtained by taking the square approximation to A',B',H' in the transformed space and transforming the points back to the real...