Browse Prior Art Database

Flag-Mapped Area Fill ALGORITHM

IP.com Disclosure Number: IPCOM000061624D
Original Publication Date: 1986-Sep-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 4 page(s) / 61K

Publishing Venue

IBM

Related People

Boinodiris, S: AUTHOR

Abstract

INTRODUCTION The algorithm presented here fills all possible polygons including multiply bounded areas, three dimensional projections, areas bounded by curves or circular segments, and other two-dimensional extensions. The algorithm uses restricted local storage to achieve a desired cost-performance ratio of a particular graphic display terminal. The iteratively used storage can be equivalent to a single scan line, or be increased to any chosen level up to a full screen. As more memory becomes available, the designer can cause faster execution by setting a wider scan block. The area-filling algorithm is resource sharing a "Display Processor" (microprocessor) and a set of dedicated hardware in order to create the data used for displaying the filled area.

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

Page 1 of 4

Flag-Mapped Area Fill ALGORITHM

INTRODUCTION The algorithm presented here fills all possible polygons including multiply bounded areas, three dimensional projections, areas bounded by curves or circular segments, and other two-dimensional extensions. The algorithm uses restricted local storage to achieve a desired cost-performance ratio of a particular graphic display terminal. The iteratively used storage can be equivalent to a single scan line, or be increased to any chosen level up to a full screen. As more memory becomes available, the designer can cause faster execution by setting a wider scan block. The area-filling algorithm is resource sharing a "Display Processor" (microprocessor) and a set of dedicated hardware in order to create the data used for displaying the filled area. The Display Processor attaches to other processors and memory containing all parameters of the model to be filled. The Display Processor responds to numerous commands, which may require known display handling tasks, i.e., change of color table values, change of color attribute values, the writing of lines and characters, etc. The output of the Display Processor appears on the Frame Buffers, and, through the Video Output Controls, is presented on the Display. An entity to be filled is provided to the Display Processor by a series of points defining the boundary lines. The controlling algorithm of the microprocessor can display any pattern in the filled area, and, through the simple method used in the DISPERSION, execute clipping at an arbitrary window of the filled area with a small overhead. THE ALGORITHM The Flag-Mapped Area Fill Algorithm is a means to produce a set of frame buffer memory mapped data which are used to create color-filled or patterned area-shaded images, as such area images are defined by the "internal points" of a set of polygonal boundary lines. Boundary lines of an area are provided by a sequence of two-dimensional points, together with an attribute attached to the point indicating a "move" or a "draw". As an example, if (X,Y,A) indicate the positions of the X and Y dimensions of various points and the move (=0) or draw (=1) attribute A, then the series (5,-67,0), (234,0,1), (17,225,1), (5,- 67,1) define the boundary of a "closed" area. Closed boundary means one consisting of a sequence of perimeter straight lines where each segment starts where the previous one ended, and the last "draw" segment of the perimeter, prior to a "move" segment, ends where the first "draw" segment started. An internal point is one located so that all lines starting from it, and terminating at any point of at least one infinitely large two- dimensional coordinate, will intersect boundaries an odd number of times. The Flag-Mapped Area Fill Algorithm consists of PRE-PROCESSING, the DISPERSION, the COLLECTION, and the PAINTING. All received commands are handled by the Display Processor PRE- PROCESSING program, an operation which: (1) executes "closing" of...