Browse Prior Art Database

Polygon Fill Routine for Artwork Generators

IP.com Disclosure Number: IPCOM000079932D
Original Publication Date: 1973-Sep-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 37K

Publishing Venue

IBM

Related People

Weinert, GS: AUTHOR

Abstract

The purpose of this program is to convert design data in the form of line segments representing the outline of closed figures into artwork generator control sequences, to allow production of photographic mask patterns. The particular family of artwork generators supported by this program have the capability of exposing various sized rectangular elements placed at any angle.

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

Page 1 of 3

Polygon Fill Routine for Artwork Generators

The purpose of this program is to convert design data in the form of line segments representing the outline of closed figures into artwork generator control sequences, to allow production of photographic mask patterns. The particular family of artwork generators supported by this program have the capability of exposing various sized rectangular elements placed at any angle.

If each figure to be exposed were bounded with only horizontal and vertical lines, filling the inside areas of the figures with light flashes would be a simple matter. However, when figures contain angled lines, in order to fully utilize the capabilities of the artwork generator it is necessary to utilize angled flashes. The basic objective of the filling algorithm is to determine for each angled line in a polygon, the largest suitable rectangle totally contained within the polygon, and then filling the rest of the polygon with horizontal/vertical flashes.

The major problem encountered in the filling of a polygon is in insuring that the entire area to be exposed is accounted for, so that no holes are left in the final figure. Filling, as accomplished by the program, is described in conjunction with the figures, which illustrate the basic sequence of operation.

The following definitions are used in conjunction with the description. HVC (Horizontal-Vertical-Connector).

A connected set of horizontal and vertical lines that connect the end points of an angled line and are contained inside, or are lines of, the figure bounded, in part, by the angled line. HVAC (Horizontal-Vertical-Angled-Connector).

Where an HVC cannot be created, a set of horizontal, vertical, and angled lines that connect the end points of an angled line and/or are contained within, or are lines of, the figure bounded, in part, by the angled lines. HVCR (Horizontal- Vertical-Connector-Region).

The area inside the angled line and its HVC or HVAC. LOGICAL HVC.

A set of horizontal-vertical lines, not necessarily connected, which can be logically substituted for the angled line in the original figure. SUFFER.

The largest angled rectangle that can be totally contained within the designated figure.

A suitable sized angled rectangle (SUFFER) is established by the usual scissoring techniques. Independently of scissoring, for each angled line, a connected set of horizontal and vertical lines (HVC) is generated. An HVC serves to divide the polygon into two, or more, regions, only one of which, the HVCR, contains the angled line, thereby isolating the angled line from the rest of the polygon. For many simple polygons, the...