Browse Prior Art Database

Fast And Efficient Perimeter Drawing of Filled Polygons in a Graphics System

IP.com Disclosure Number: IPCOM000119390D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 7 page(s) / 241K

Publishing Venue

IBM

Related People

Kariolis, SJ: AUTHOR [+2]

Abstract

This article describes a scheme that provides a solution to the problem of drawing a graphic representation of filled polygons where the problem is to draw the perimeter of a polygon with a number of different characteristics, such as color, type (i.e., dotted, dashed, etc.) width, etc.

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

Fast And Efficient Perimeter Drawing of Filled Polygons in a Graphics
System

      This article describes a scheme that provides a solution
to the problem of drawing a graphic representation of filled polygons
where the problem is to draw the perimeter of a polygon with a number
of different characteristics, such as color, type (i.e., dotted,
dashed, etc.)  width, etc.

      Previously, algorithms attempted to draw perimeters of filled
polygons where the drawing of the perimeter was done at the beginning
of the fill process or as a separate functional entity after the fill
process.  Such approaches resulted in performance degradation and
complex polygon fill schemes.  The present approach utilizes existing
information handled by the polygon fill process and through the use
of a table renders the perimeter as the last step of the fill
process.

      This algorithm is used with a filled polygon algorithm and
creates a table that enables perimeter draw as the last step of the
fill process.

      Polygon filling can be accomplished quite effectively, for a
large class of polygons, utilizing a scanline type algorithm.  The
IBM 5080 graphics system and Megapel graphics adapter are using such
an implementation, for polygons with as many as 125 edges.  However,
the perimeter drawing scheme discussed here also may be used with
other types of polygon fill algorithms.

      A polygon fill operation requires specification of large number
of attributes, such as:
           Interior color
           Interior style
           Interior style index
           Interior color index
           Edge type
           Edge flag
           Edge width scaling factor
           Edge color index
           etc.

      The kind and number of attributes implemented depends on the
graphics architecture and, in most cases, is dictated by the
application environment.  As one can see from the above list of
attributes, polygon filling is a complex function to implement and it
is more than just 'painting' a given polygon.  In this article, the
problem of rendering the polygon's edges (or perimeter) is discussed,
and a solution is presented which maximizes performance and renders a
filled polygon with a good form.  Good form means the visual
representation of the polygon represents a true picture of the
mathematical definition of the polygon.

      This section describes the algorithm and tables used by the
Megapel Adapter and the IBM 5080 graphics system to render filled
polygons.  In the description that follows the BEGIN and END AREAFIL
functions used in the 5080 will be used synonymously with the BEGIN
and END POLYGON function in the Megapel adapter.  The tables used
with rendering the polygon fill function in the above two systems
are:
           Input Edge List     (IEL)
           Sorted Edge List    (SEL)
    ...