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

Publishing Venue

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

       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.

      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...