Browse Prior Art Database

Optimized Drawing of Filled And Unfilled Circles in a Two-Dimensional Graphics System

IP.com Disclosure Number: IPCOM000102475D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 5 page(s) / 160K

Publishing Venue

IBM

Related People

Fleischman, RL: AUTHOR [+2]

Abstract

Most algorithms are quite efficient in drawing large unfilled circles. However, in most cases, the circles appearing on the screen are quite small and in each one of the algorithms the time to calculate the points on the circle can be as much as 90% of the total time taken to render the circle. To improve this situation a customized look-up table can be used to reduce the calculation time to a minimum.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 38% of the total text.

Optimized Drawing of Filled And Unfilled Circles in a Two-Dimensional Graphics System

       Most algorithms are quite efficient in drawing large
unfilled circles.  However, in most cases, the circles appearing on
the screen are quite small and in each one of the algorithms the time
to calculate the points on the circle can be as much as 90% of the
total time taken to render the circle.  To improve this situation a
customized look-up table can be used to reduce the calculation time
to a minimum.

      To optimize the drawing of filled circles, a version of the
Bresenham algorithm is used.

      Both of these techniques are discussed in this article.

      Circle Algorithms In reviewing the literature [1,2,3,4] for the
implementation of drawing circles in graphics systems, it becomes
apparent that the only algorithm that minimizes errors in finding the
points on the perimeter of circle is the Bresenham algorithm.  This
algorithm computes the points on the perimeter one by one starting
from some point and proceeding until the total circle is drawn.  The
Bresenham algorithm is described in detail in [4].

      In the case where the perimeter of the circle is to be drawn,
there is a need to compute a sequence of vectors that makes up the
perimeter of the circle, which are given to the hardware generator to
plot these vectors in the video pixel memory.  These vectors should
be computed sequentially in a clockwise or counterclockwise fashion
to enable drawing the circle's perimeter with different line types.
In using the Bresenham algorithm, points are generated and
accumulated to create vectors which are then passed to the hardware
generator.  The polar coordinate version also may be used to
calculate the points.  Here a combination of both is implemented for
drawing perimeters.

      Filled Circles Every point on the perimeter of the circle is
needed in order to fill a circle.  The Bresenham algorithm, shown
below, is the most attractive algorithm since the Bresenham algorithm
computes all the perimeter points needed for the filled circle
procedure.

      Bresenham Algorithm for a Single Octant
      Parametric Variables:   U, V, and E
      Initially:
           Let  U(i) = 1
                V(i) = E(i) - (2 * Radius)
                E(i) = 1 - Radius
      Algorithm:
           If (E(n) < 0 ),
              Then Move Axially and
                   Update Parametric Variables
                      U(n+1) = U(n) + 2
                      V(n+1) = V(n) + 2
                      E(n+1) = E(n) + U(n+1)
                End If
           Else If ( E(n) >= 0 ),
                Then Move Diagonally and
                     Update Parametric Variables
                     ...