Dismiss
Surety is performing system maintenance this weekend. Electronic date stamps on new Prior Art Database disclosures may be delayed.
Browse Prior Art Database

# Hardware Implementation of the Outline Contour of the Edge Flag Algorithm

IP.com Disclosure Number: IPCOM000107369D
Original Publication Date: 1992-Feb-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 81K

IBM

## Related People

Lindgren, TW: AUTHOR [+2]

## Abstract

This article describes an optimized hardware implementation of the edge flag algorithm for polygon filling as described by Ackland and Weste in The Edge Flag Algorithm - A Fill Method for Raster Scan Displays (1981). The implementation takes advantage of the fact that the reduced outline contour is combinatorial in structure in order to provide hardware optimization.

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

Hardware Implementation of the Outline Contour of the Edge Flag Algorithm

implementation of the edge flag algorithm for polygon filling as
described by Ackland and Weste in The Edge Flag Algorithm - A Fill
Method for Raster Scan Displays (1981).  The implementation takes
advantage of the fact that the reduced outline contour is
combinatorial in structure in order to provide hardware optimization.

The algorithm described by Ackland and Weste records a reduced
copy of the polygonal boundary in a working plane and then performs
the scan line algorithm to fill the interior correctly.

Let Y denote the rise of the curved line segment of the outline
contour (Positive or Negative) and
P denote a change in Y from the Previous pixel (True or
False) and P' denote a change in Y to the Next pixel
(True or False) and D(i) denote a data bit in the
working plane.
Then the pixels may be adjusted as follows:
FOR Each Boundary Point Pixel DO
IF Y = Negative THEN
IF P = TRUE THEN
D(i) =  COMPLEMENT(D(i))  (*Change Current Pixel*)
ELSE
D(i) = D(i)
ELSE
IF P = TRUE THEN
D(i-1) = COMPLEMENT(D(i-1))  (*Change Previous Pixel*)
ELSE
D(i-1) = D(i-1)

This method of pr...