 |
Description  |
|
|
CROSS-REFERENCE TO RELATED APPLICATIONS
The present application is related to the applications of Richard A. Dermer for "Method for Automatic Trap Selection for Correcting for Plate Misregistration in Color Printing" and of Richard A. Dermer and Edward C. Reifenstein, III for "Method
for Determining color Boundaries for Correcting for Plate Misregistration in color Printing" filed simultaneously herewith and assigned to the same assignee.
BACKGROUND OF THE INVENTION
The field to which the invention applies is the electronic processing of graphic images to produce multi-color output using offset or other printing methods. Images are obtained electronically by digital scanning of photographic material and
combined with "structured graphics" to provide composed images or pages which are then separated into monochromatic images each corresponding to an ink to be used in the printing process. Typically, four process color inks, cyan, magenta, yellow and
black are used, although special "spot" colors can be used instead of or in addition to the process color inks. The separated images can then be output to photographic films from which printing plates are made. Alternatively, the separated images can
be used to produce engraved cylinders from which gravure prints can be made.
The layout of a page or graphic image to be printed as described above depends upon combination of "structured graphics" according to a pre-established graphic design. The structured graphics are contiguous regions of color which represent a
succession of graphic objects imaged on the printing medium (e.g. the "paper"). The objects so imaged are polygon shapes which can be isolated from each other, can abut one another at one or more points, can partially overlap one another, or can
completely overlap one another. The resulting printed page or graphic image is therefore made up of a patchwork of polygon shapes representing the graphic objects, some of which are "clipped" by objects imaged later in the succession.
The result of abutting or overlapping polygon shapes is a boundary between adjacent regions of color which under ideal printing conditions should have zero width. The "colors" which fill the polygon shapes can be solid colors, tints, degrades,
contone images, or "no fill" (i.e., the paper with no ink applied). In general, the "colors" represented in these adjacent regions are printed using more than one ink. In practice therefore, the realization of a zero width boundary between regions of
different color is impossible as a result of small but visible misregistration problems from one printing plate to another. The error is manifested as a "light leak" or as a visible boundary of an undesired color.
Methods for correcting for this misregistration are well known in the prior art. The general approach is to expand one of the regions which abut so as to fill the gap or misregistration border region with a color determined so as to minimize the
visual effect when printed. Borders which are expanded from a region of one color to another in this manner are said to be "spread". A border which has been so expanded is referred to as a "trap", and the zone within which color is added is called the
"trap zone".
Commonly used methods for automatic trapping of digital images rely on images which have been first scanned and are stored internally as a sequence of (high resolution) scan lines each containing individual scan elements or pixels. These methods
process each raster line in sequence and compare one or more adjacent pixels to determine color boundaries, and apply rules for determining whether or not to create a trap at such boundaries, and finally apply a second set of rules to determine the
nature of the trap if one is to be created.
For example, the method of Taniguchi, described in U.S. Pat. No. 4,931,861, uses two rasterized images representing abutting or overlapping objects within an image field to define a third binary image representing the map of the pixels which
make up the borders between the first and second images. These three images are superimposed, pixel by pixel, to create a fourth and final binary image. The method of Hennig et al., described in U.S. Pat. No. 4,583,116 is also defined on a pixel
basis, in as much as the images described are obtained by opto-electrical scanning source images. The patent also teaches a method for determining the boundary color for the (pixel-based) boundary separating the color regions. The method of Darby et
at., described in U.S. Pat. No. 4,725,966, again defined on a pixel basis, uses a mask which is moved, one resolution element at a time, to evaluate the presence or absence of (pixel) colors upon which a positive or negative spread decision is based.
The method of Yosefi, described in U.S. Pat. No. 5,113,249 uses a set of automated rules as the basis for deciding, for each pair of abutting or overlapping shapes whether or not to create a trap (an overlap region referred to as a "frame"),
and, if so, the nature of the trap to create. The preferred embodiment described by Yosefi makes use of scanned data, and processes each line of pixels in order, comparing for each pixel three pixels from the previous scan line and two pixels from the
same line to determine if a color change has occurred. The decisions regarding whether or not to create a trap, and the nature of such a trap if created are imbedded within the processing sequence, making use of criteria established prior to the onset
of processing.
A commercially available product, "TrapWise", from Aldus Corporation, Seattle Wash., also makes use of a raster approach to trapping. In this product, the processing time is proportional to the number of resolution elements, thereby increasing
quadratically with resolution, and leading to greater computation times for high device resolution, e.g., 3600 dots per inch (d.p.i.). Furthermore, traps are created with this package using pre-set rules, and are not editable by a user without the
requirement for repeating the computation.
The trapping methods described in the above cited prior art references have two common features: The first is the processing of images represented in raster form. This places a requirement for extra processing steps in images which constitute
primarily structured graphics or which combine structured graphics with contone images. Such images must first be rasterized at the output resolution, and then the appropriate line-scan algorithm applied. As a result of the number of edge boundaries
involved (at output resolutions of for example 3600 d.p.i.), a substantial amount of redundant computation is required, particularly if a trap is created at each edge.
The second common feature of prior art methods is the necessity to make and apply trapping decisions within the processing based upon pre-established criteria. For raster based processing at high output device resolution, the potential number of
pixel-to-pixel color transitions is large due to repetition of transitions corresponding to a single color region border shared by many scan lines. In U.S. Pat. No. 5,113,249, the decision to make a trap is conditional, so the number of color pairs to
be considered is reduced below that which would be required if all color pairs were automatically trapped. Since the decision to make a trap is applicable only to generic color pairs encountered within a particular image, only color pairs processed in
the first pass through the raster data can be subject to modification without reprocessing the raster at least once. To address other color pairs (i.e., to repeat the decision process), another pass is required. The method of the above patent does not
therefore permit interactive modification and display of trapping decision modifications, since iterative application or modification of trapping decision rules is impractical when processing must generally be repeated (at least once through the entire
raster) with each change.
Many rule-based methods exist in the prior art for automatic determination of the particular trap to be specified for a given combination of bounding colors. For example, in U.S. Pat. No. 5,113,249, a set of logical tests is used in sequence
to differentiate between pre-established generic color-pair categories, with a rule applied to each color pair. Such built-in role systems attempt to replicate the human aesthetic judgement used in manual specification of traps and each can provide
results satisfactory to an "expert" user in most cases while failing to do so in other special situations. Without a means for configuring the automatic trap selection method, a user is forced to rely on manual trap specification, even for routine
operations.
The specification of a trap at the boundary between two color regions does not in itself eliminate the misregistration of printing plates, but reduces the visual effect of misregistration within the trap zone through proper choice of the trap
operation. In the event of plate misregistration involving a color separation for which a trap has been specified, additional "secondary" effects occur. The methods described in the prior art provide no information from which such effects can be
visualized during the process of trap specification, and therefore necessitate a "trial and error" approach.
It is therefore a general object of the present invention to permit the direct processing of structured graphic objects of an original image without the requirement for an initial rasterization process to specify trap characteristics at the
boundaries between clipping or abutting regions of color considered as adjacent polygons each made up of a path of sequential line segments and filled by a solid color, a tint, a degrade, a contone image, or no fill (the blank "paper"), thereby producing
a graphic image containing all such boundaries of the original image.
It is a further object of the present invention to generate a graphic image containing all boundaries of the original image in such a manner that its basic geometry is independent of any decisions regarding whether or not traps between individual
regions are necessary, or the nature of such traps, thereby providing a wide range of options based upon pre-established rules or direct user interaction which can be applied iteratively without the necessity for recomputing the aforementioned geometry.
It is a further object of the invention to provide a system which allows trapping of document pages and images on a production basis with a user interface permitting display of the trapped and untrapped data, and the selection of trap decision
methods ranging from fully automatic to completely manual interactive modes.
It is a still further object of the invention to permit the user of a trapping system to employ graphic user interface tools for direct manipulation of the borders between adjacent color regions on a trial basis and to observe the effects of such
manipulation without the necessity of recomputing the aforementioned graphic image containing all boundaries of the original image, and before committing to the final output processing of the data being manipulated.
It is a still further object of the invention to include in the user interface of a trapping system an indication for any selected color region bounding other color regions a display of all possible effects of misregistration of printing plates
which can occur for the selected color region as a result of no trapping, and as a result of any candidate trapping decision applied to all boundaries of the selected color region.
It is a still further object of the invention to include in the user interface of a trapping system an indication for any selected boundary between adjacent color regions a display of all possible secondary misregistration effects which would
result from any candidate trapping decision.
It is a still further object of the invention to provide automatic specification of traps by user selection from more than one trap selection methods, or use of a combination of more than one trap selection method, based upon aesthetic judgement
or special situations.
It is a feature of the present invention that the processing time required for generation of the trapping map is in general reduced in comparison to raster methods carried out at high device resolution, since the number of boundaries grows
linearly with resolution while the number of pixels to be scanned in a raster grows quadratically.
SUMMARY OF THE INVENTION
A method and apparatus are disclosed for processing digital data representing a structured graphic image to compensate for the printing plate misregistration. As an aid to understanding the discussion to follow, the terms defined herein apply to
the entire specification and claims, and are indicated by small capitalization. The term STRUCTURED GRAPHIC IMAGE means a document page description, i.e., a page layout which can contain linework, typographic or display text, tints and degrades, and
regions to be filled with (halftone-screened) continuous-tone images when they are rasterized for output. The digital data format for this image can be a data description such as that of the PICT (a trademark of Apple Computer, Inc.) data format, or it
can be a procedural description such as that of the "PostScript" (a trademark of Adobe Systems, Inc.) Page Description Language.
The first step is to generate from the given STRUCTURED GRAPHIC IMAGE a sequence of GRAPHIC OBJECT DESCRIPTIONS making up a DISPLAY LIST, in which each GRAPHIC OBJECT DESCRIPTIONS in the DISPLAY LIST is a polygon definition. A GRAPHIC OBJECT
DESCRIPTION refers to a single CLOSED POLYGON, which is defined as any of the following: (1) a single region containing an interior fill color; (2) two or more overlapping regions having the same interior fill color; or, (3) two or more disjoint regions
having the same interior fill color. The GRAPHIC OBJECT DESCRIPTION for each CLOSED POLYGON is made up of the coordinates of all of the vertices which define the CLOSED POLYGON, along with the lines connecting these vertices and the fill color of the
interior of the enclosed region(s). The spatial coordinates of the line segments defining each CLOSED POLYGON can be expressed in any two-dimensional rectilinear coordinate system, and the line segments themselves can be "vertical", "horizontal", or
"slanted" with respect to the chosen coordinate system. For the purposes of this discussion, a coordinate system is used with X- and Y-values ("horizontal" and "vertical" respectively). Of particular importance to the invention is the fact that,
through an appropriate rotation of coordinates applicable to the entire set of GRAPHIC OBJECT DESCRIPTIONS making up the DISPLAY LIST, a new coordinate system can be obtained in which there exist no "horizontal" lines. The order of the GRAPHIC OBJECT
DESCRIPTIONS in the DISPLAY LIST is the order in which they are to be rendered in the output rasterization process, with the first GRAPHIC OBJECT DESCRIPTION describing the first object to be rendered, and the last GRAPHIC OBJECT DESCRIPTION describing
the last to be rendered.
The graphic objects described in the DISPLAY LIST represent polygon shapes located as they are to appear in the output medium when imaged, with each polygon in the sequence clipping those previously so located in this space. As used herein, the
term CLIPPING by an opaque polygon shape (the "clipping polygon") means the partial or complete obscuration of polygon shapes (the "clipped polygons") whose boundaries it overlaps with the resultant "hiding" of boundaries contained within the region of
overlap. After removal of hidden lines, there remains a patchwork of polygon shapes representing the different color regions which are to appear in the final image. The set of boundaries between adjacent polygon regions is identified and collected
together to form a single graphic object hereinafter referred to as a BOUNDARY MAP. The BOUNDARY MAP is a geometrical description of all straight line segments making up the above boundaries without specification of stroke characteristics (width,
offset, shape and fall color) and therefore independent of any trapping decisions to be made later and which are to be used to determine such characteristics. The computation time required to construct the BOUNDARY MAP is linearly proportional to the
total number of line segments making it up, and is therefore more efficient than raster methods or methods which compare object boundaries with those of other objects.
After construction of the BOUNDARY MAP, the stroke width, offset and fill characteristics are defined for each of the line segments of which it is comprised. Offsetting the stroke of a line segment towards or away from one of the clipped
polygons for which the line segment forms a boundary edge causes the color region from which the offset occurs to be spread towards the region to which the offset occurs. The effects achieved depend in practice upon the combinations of the various inks
used for the colors involved according to predefined rules or user interaction. Assignment of stroke characteristics to each line segment of the BOUNDARY MAP yields a TRAPPING MAP as a graphic object to be superimposed as a TRAPPING MAP IMAGE on top of
the original STRUCTURED GRAPHIC IMAGE from which it was derived. Stroke width and offset can be specified manually by direct user interaction, or automatically using stored parameters. As used herein, manual interaction with the system can include
combinations of keyboard entries and mouse, pen, tablet, etc. "picks" on elements of a graphical information display.
The trap specification step can be carried out automatically, or manually through direct user interaction. The automatic trap selection method ranks all possible trap decisions for a given color pair according to a weighted average of ranks
obtained by multiple ranking methods, utilizing user-specified weights. In the manual interaction mode, a CANDIDATE TRAPPING MAP can be viewed at a user interface display and manipulated directly by specification of trap color, stroke width and offset
for selected object boundaries, selected objects, or for all objects of a given color. New or modified trap specifications are applied to the previously derived BOUNDARY MAP to generate a new CANDIDATE TRAPPING MAP, with the effects of the changes
immediately visible at the user interface display.
The next step is to add the GRAPHIC OBJECT DESCRIPTION of the TRAPPING MAP to the end of the DISPLAY LIST of GRAPHIC OBJECT DESCRIPTIONS making up the original STRUCTURED GRAPHIC IMAGE so as to ensure that the TRAPPING MAP graphic object is the
last object rendered in the output process, i.e., it is superimposed upon the STRUCTURED GRAPHIC IMAGE when finally output. This can be accomplished either by appending the TRAPPING MAP graphic object description to the end of the DISPLAY LIST described
previously followed by conversion of the resulting augmented DISPLAY LIST to the digital data format required for the output rasterization system, or alternatively, conversion of the TRAPPING MAP GRAPHIC OBJECT DESCRIPTION to the output format and
appending it to end of the original image data file. In either case, the result is a TRAPPED IMAGE DATA FILE, representing the original STRUCTURED GRAPHIC IMAGE with the TRAPPING MAP superimposed upon it.
The final step is the output processing of the TRAPPED IMAGE DATA FILE by color separation and rasterization in the manner appropriate for the selected printing method.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention will be best understood from a detailed description of a preferred embodiment thereof, selected for purposes of illustration, and presented with reference to the accompanying drawings, in which:
FIG. 1 is a block diagram of the processing steps associated with electronic prepress processing of a graphic image;
FIG. 2A and 2B demonstrate the effect of misregistration of monochromatic printing plates used for printing an image containing two simple graphic objects;
FIG. 3A and 3B illustrate the use of a TRAPPING MAP IMAGE superimposed upon an image subject to the misregistration effects of FIG. 2B;
FIG. 4 is a block diagram showing the processing steps associated with a trapping module;
FIG. 5 is a block diagram showing the processing steps making up the TRAPPING MAP generator processing step of the trapping module of FIG. 4;
FIG. 6 shows the polygon map of the graphic objects making up the image of FIG. 2A and 2B;
FIG. 7A and 7B illustrate the data structures used to generate the BOUNDARY MAP for the image of FIG. 2A and 2B;
FIG. 8 shows the main flow chart of the data procesing steps by which the data of FIG. 7A and 7B is used to generate the BOUNDARY MAP for the image of FIG. 2A and 2B;
FIG. 9 shows the geometry for data processing within a single SCAN BEAM;
FIG. 10 shows the processing flowchart for processing intersections;
FIG. 11 shows the processing flowchart for processing terminated edges in the active edge table;
FIG. 12 shows the BOUNDARY MAP resulting from application of the DERMER TRAP METHOD;
FIG. 13 is a graph comparing the processing time of the DERMER TRAP METHOD with that of a raster method for CANDIDATE TRAPPING MAP generation;
FIG. 14A and 14B show the effect of spreading one or the other of the colors represented in the image of FIG. 2A and 2B by assignment of stroke characteristics to the BOUNDARY MAP;
FIG. 15A and 15B show the effect of choking one or the other of the colors represented in the image of FIG. 2A and 2B by assignment of stroke characteristics to the BOUNDARY MAP;
FIG. 16A and 16B show the effect of spreading or choking an entire region of color represented in the image of FIG. 2A and 2B by assignment of stroke characteristics to the BOUNDARY MAP;
FIG. 17A and 17B illustrate the logical result of superposition of a trap boundary specified with process colors and the resulting color planes when rendered and separated;
FIG. 18A and 18B illustrate the result of fill with overprint vs. fill with knockout using the example of FIG. 17A and 17B;
FIG. 19A and 19B illustrate trapping by foreground spreading magenta and yellow, applied to the example image of the image of FIG. 2A and 2B;
FIG. 20A and 20B illustrate the effects of secondary plate misregistration for a trapped image;
FIG. 21 provides definitions for trap stroke parameters which can be supplied to specify a trap along a single boundary of an object;
FIG. 22 is a block diagram of the user interface to the trapping system
FIG. 23 depicts the view of the trapping system as seen by a user; and,
FIG. 24 illustrates the manual trap selection user interface.
DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT
Turning now to the drawings, the steps associated with electronic prepress processing of a document page or graphic image is shown in FIG. 1. In the figure, a graphic design 116 is used to construct a STRUCTURED GRAPHIC IMAGE 120 representing
the layout of graphic objects on the document page or image to be printed. The STRUCTURED GRAPHIC IMAGE 120 contains the line work, tints, degrades, typographic and display text, and regions to be filled with (halftone-screened) continuous tone images
at output. The continuous tone ("contone") images 114 used for this purpose are scanned from original artwork or photographs 110 using a color scanner 112.
The trapping procedure takes place within the trapping module 124, which uses the STRUCTURED GRAPHIC IMAGE 120 as input, and produces a TRAPPED GRAPHIC IMAGE 126 compensated for potential misregistration problems. The procedure can operate
automatically or under optional control of user 122 through a user interface to the trapping module 124. The trapped graphic image 126 is input to an assembly and separation module 128, which creates color-separated images including the screened
halftone representations of scanned images 114 used as the "full color" for regions of the document page layout in which they are to appear. In the example of FIG. 1, four process color separations 130, designated c (cyan), m (magenta), y (yellow) and k
(black) are shown, although in practice special "spot" color inks, varnishes, embossing, etc. can be used instead of or in addition to the process colors 130.
The color-separated (monochrome) versions of the assembled document page 130 are rasterized and recorded on film by a raster output module 132 yielding a set of color-separation films 134, from which color separation plates 136 are made, one for
each of the inks to be used by the printing press 138 in final printing of the resultant document page 140.
In FIG. 2 and the following figures, a simple example of a STRUCTURED GRAPHIC IMAGE 200 is shown, for the purpose of illustration. The STRUCTURED GRAPHIC IMAGE 200 is made up of two rectangular objects, a "red" object 210 which partially
obscures a "blue" object 220. In FIG. 2A, the printed result is shown as it would appear with perfect registration. In FIG. 2B, the printed result is shown in the case of a slight misregistration of the printing plates used to print the (two or more)
inks required. If "spot" colors are used for the "red" and "blue" inks, the example shows the effect of a slight shift of the "blue" plate up and to the right with respect to the "red" plate, resulting in a visible white line 230 at the boundary between
the red region 210 and the blue region 220. Note that herein the term "white" refers to the color of the medium on which the image is printed. If the process colors cyan, magenta, yellow and black are used, the example shows the effect of a slight
shift of the cyan plate up and to the right with respect to the magenta plate, resulting in a visible yellow line 230 (assuming no black component of the colors "red" and "blue").
FIG. 3A illustrates the logical imaging model of image 300 of FIG. 2 after superimposition of the TRAPPING MAP 320, in which the "blue" rectangle 220 is the first object imaged and the "red" rectangle 210 is the second object imaged, partially
obscuring or "clipping" the first rectangle 220. The appearance of the resulting image 300 is shown in FIG. 3B. In FIG. 3A and 3B, the TRAPPING MAP is shown as a solid black outline; in practice, the stroke width, offset, and fill color of the outline
320 is determined by pre-established criteria or by user 122 through a user interface to the trapping module 124 of FIG. 1.
FIG. 4 is an explosion of the trapping module 124 of FIG. 1 showing the processing steps. The source image file 120 containing the STRUCTURED GRAPHIC IMAGE representing the document page layout is input to a DISPLAY LIST generator 400, which
converts the source image to an object DISPLAY LIST ordered according to the sequence in which the objects are to be imaged. The DISPLAY LIST generator 400 makes use of information specific to the data format of the source image file 120 to perform the
"disassembly" of the image data to form the object DISPLAY LIST 420. All graphic elements of the source image are added to the DISPLAY LIST as closed, borderless polygons filled with a color. For example, ruled lines are described as closed polygons
formed by rectangles with one dimension very much smaller than the other.
For the purpose of discussion only, the data format of the source image file 120 is considered to be the PostScript level 2 language of Adobe Systems, Inc., or a functional equivalent thereof. The DISPLAY LIST generation process of module 400 is
accomplished by a standard PostScript level 2 interpreter, making use of a set of PostScript procedure definitions prepended to the source image file 120 to redefine the standard PostScript imaging operators in order to write the GRAPHIC OBJECT
DESCRIPTIONS making up the DISPLAY LIST 420 to a data file instead of performing their usual rendering and rasterization operations. In this case the disassembly data 410 is a data file making up the sequence of PostScript source statements making up
this preamble.
The TRAPPING MAP generator 430 places the GRAPHIC OBJECT DESCRIPTION of the DISPLAY LIST within a defined space representing the two-dimensional medium to which the image is to be output, with each object clipping those objects placed before it
in this space and being clipped by those placed after it. When all objects have been so placed, the boundaries between regions of different fall color are identified, and the coordinates of the start and end points of the set of line segments defining
these boundaries can be combined with stroke width, offset, and fill information contained in an auxiliary TRAPPING CONTROL DATA SET 440 to generate the TRAPPING MAP 320.
The trapping user interface 450 provides for graphical display and modification of currently specified information in the TRAPPING CONTROL DATA SET 440. The interface permits display of the source image 120 with and without a CANDIDATE TRAPPING
MAP 444 superimposed upon it, and allows for runtime specification (by means of keyboard entry or mouse-based "tool" operations) of parameters defining any or all of the following:
1. The degree of automatic trap decisions to be used in production processing, ranging from fully automatic (no human intervention) to fully manual (each border between regions of different fill color to be user-specified as to trapping
options);
2. Rules to be used for automatic trap decisions based upon individual color combinations, luminescence of individual colors in comparison to others, or other criteria;
3. Parameters used for determining trap characteristics, either for control of automatic operation, or manual trap specification;
4. Identification of a set of rules and/or parameters with a user-given name to be saved as a data set within the trapping system for later recall and application by reference to the user-given name;
5. Selection of any boundary between color regions of the image and interactive edit of that boundary by direct tool manipulation to expand one color region into that of another, and specifying stroke, offset, and fill characteristics directly
to achieve a candidate trap for the selected boundary; and,
6. Selection of any boundary between color regions of the image and display for that boundary of all effects of misregistration of the printing plates used to print the image, both with and without application of a given candidate trap to the
selected boundary.
The user interface 450 permits as one optional mode the iterative modification and display of the trapped result without committment to a final version until the results are satisfactory to the user 122, at which time the resulting TRAPPING MAP
320 is combined with the source image file 120 using a merge procedure 460 dependent upon the external format used for the source image file 120 and the resulting trapped image file 126. Supplementary information to support the merging of the source
image file 120 and the TRAPPING MAP 320 is provided by an image assembly data set 470. In the preferred embodiment of the invention, the external format is PostScript level 2. The image merge procedure 460 accordingly converts the TRAPPING MAP object
definition into the appropriate sequence of PostScript procedure calls and inserts this sequence of PostScript statements into those of the source image file 120 such that the TRAPPING MAP is the last object to be imaged.
FIG. 5 is an explosion of the TRAPPING MAP generator 430 of FIG. 4, showing the processing steps by which the object DISPLAY LIST 420 is used to obtain the final TRAPPING MAP 320 under control of the trapping user interface 450. The first step
in this process is to generate the polygon map of all graphic objects of the object DISPLAY LIST 420. The boundaries which delineate (polygon) regions of different fill colors are processed 530 to become the BOUNDARY MAP 540. This boundary map is used
in either an automatic or an interactive (iterative) process in which the trapping control data 440 are applied to each of the line segments making up the BOUNDARY MAP 540 to determine the line width, offset and fill characteristics. In the automatic
mode, a one-time application of the trapping control data 440 to the BOUNDARY MAP 540 produces the final TRAPPING MAP 320. In the interactive (iterative) mode, the result of this application is the CANDIDATE TRAPPING MAP 444 which is displayed on the
user interface 450 and subject to user modification by interactive modification of the trapping control data 440 and repeating the generation of the CANDIDATE TRAPPING MAP 444. The iterative loop can be repeated until satisfactory results are obtained,
and the final TRAPPING MAP 320 is generated instead of the CANDIDATE TRAPPING MAP 444.
GENERATION OF THE BOUNDARY MAP
In FIG. 6, the polygon map of the graphic image of FIG. 2 is shown. The two polygons of the image have GRAPHIC OBJECT DESCRIPTIONS in the DISPLAY LIST based upon four vertices each, designated as a, b, c, and d for the "red" polygon 210 of FIG.
2, and e, f, g and h for the "blue" polygon 220 of FIG. 2. Since the "blue" polygon 220 is imaged first, it appears first in the DISPLAY LIST.
The logical content of the object DISPLAY LIST 420 is given in TABLE 1:
TABLE 1 ______________________________________ ORIGINAL OBJECT DISPLAY LIST Winding Object Vertex line Number Object char. ______________________________________ 1 e e-f +1 "Blue" fill f f-g +1 g g-h -1 h h-e -1 2 a a-b +1 "Red" fill b
b-c +1 c c-d -1 d d-a -1 ______________________________________
The DISPLAY LIST data of TABLE 1 provides information for the set of polygons, each of which is identified by a POLYGON NUMBER representing the order imaged, along with its interior fill color. The description contains a list of vertices, and
characteristics of the line connecting each vertex to its successor in the list. For each vertex, the X,Y coordinates defining the point are given (herein "X" is taken to be the horizontal coordinate and "Y" the vertical coordinate), as are the starting
and ending coordinates of each line defined. The WINDING NUMBER of a line segment is used for indication of the line direction as it encloses the filled region of a polygon. A line segment has a WINDING NUMBER value of +1 if the line extends from a
lower Y-coordinate to a higher Y coordinate, and -1 if the line extends from a higher Y coordinate to a lower Y coordinate. For horizontal lines, which receive special treatment in the method, the WINDING NUMBER is +1 if the line extends from a lower X
coordinate to a higher X coordinate, and -1 otherwise.
The generation of the BOUNDARY MAP involves clipping the polygons of the DISPLAY LIST according to the stacking order, and associating each boundary between regions of different color remaining after the clipping operation with the objects
between which it forms a boundary. There are many methods for clipping polygons known in the art. The preferred embodiment makes use of an improved procedure hereinafter referred to as the DERMER TRAP METHOD, based upon a method described by Bala R.
Vatti in "A Generic solution to Polygon Clipping", Communications of the ACM, July 1992, Vol. 35, No. 7, chosen for computation efficiency. In the DERMER TRAP METHOD, the Vatti method has been extended to be able to handle an arbitrary number of
polygons, and tag information has been added for the BOUNDARY MAP application, as will be seen in the following discussion.
FIG. 7 shows the two primary data structures utilized in the DERMER TRAP METHOD. The first is a SCAN BEAM TABLE shown in FIG. 7A. A SCAN BEAM is defined as the area between two successive horizontal lines from a set of horizontal lines drawn
through all the vertices. In FIG. 7A, lines A through H represent horizontal lines drawn through vertices a through h respectively. The first SCAN BEAM in the set is therefore A-E, representing the area between the two horizontal lines A and E drawn
through vertices a and e. The SCAN BEAM TABLE is obtained by sorting the Y-values of all vertices used in the ORIGINAL IMAGE and contained in the DISPLAY LIST.
The second data structure utilized in the DERMER TRAP METHOD is a LOCAL MINIMUM TABLE shown in FIG. 7B. Each polygon of the OBJECT DISPLAY LIST is processed in sequence and added to the LOCAL MINIMUM TABLE as a linked list of polygon line
segments sorted in ascending order of vertical coordinate. All edges originating or terminating at each local minimum vertex are organized as a succession from bottom to top, with each edge linked to a successor edge until a local maximum is reached.
In FIG. 7B two local minima corresponding to vertices a and e form initial nodes for links as shown. The first line segment a-b originates at vertex a. Line segment b-c originates at vertex b and terminates at the local maximum at vertex c. Accordingly,
segment b-c is the SUCCESSOR EDGE of segment a-b, and segment b-c has no SUCCESSOR EDGE since it terminates at a local maximum. Each entry in the LOCAL MINIMUM TABLE consists of all the available information for the indicated line segment, including
coordinates, WINDING NUMBER, polygon reference number, and pointers to previous and successors in the table.
FIGS. 8 through 11 illustrate the processing steps carried out for the the DERMER TRAP METHOD. Starting from the bottom and moving to the top, the method processes the polygon edges one SCAN BEAM at a time, maintaining at all times an ACTIVE
EDGE TABLE of edges which are active within the SCAN BEAM being processed. At the bottom of each SCAN BEAM new local minima are added to the ACTIVE EDGE TABLE. Inside each SCAN BEAM intersections between edges are processed. At the top of each SCAN
BEAM terminating edges are either deleted, or replaced by their SUCCESSOR EDGES (if any) in the LOCAL MINIMUM TABLE.
The overall processing flow for the method 520 is shown in FIG. 8. The first step is the creation of an empty BOUNDARY MAP 800, followed by creation of the SCAN BEAM TABLE 810 by sorting all Y-coordinates of line segments as described above,
followed by the creation of the LOCAL MINIMUM TABLE 820. The main processing loop 830 takes place beginning with the bottom SCAN BEAM and working to the top. For the SCAN BEAM i extending from Y.sub.i to Y.sub.i+1, line segments corresponding to new
local minima are added to the ACTIVE EDGE TABLE 840, intersections occuring within the SCAN BEAM are processed 850, and edges which terminate at the top of the SCAN BEAM 860 are processed. As a new line segment is added to the ACTIVE EDGE TABLE, a
boundary is opened if it forms a border between different polygons, as determined below. After this processing, test 870 checks to see if there are additional SCAN BEAMS to be processed. If so, the previous Y.sub.i+1 value becomes the new value of
Y.sub.i (box 872), and the loop 830 is repeated for the next SCAN BEAM. Otherwise, exit is taken from the procedure, horizontal edges (if any) are processed 880 as described below, and the set of boundaries formatted 890 to complete the BOUNDARY MAP.
FIG. 9 shows the geometry for processing data for a single SCAN BEAM, shown with data corresponding to SCAN BEAM E-B for example. Except in the special case of horizontal lines (to be discussed further below), all active edges within a given
SCAN BEAM extend from the bottom line to the top line defining the SCAN BEAM, and are sorted in order of increasing value of the X-coordinate at the bottom line of the SCAN BEAM. In the example, the first active edge is a-b, extending from the
intersection 910 of the line segment a-b with the line E defining the bottom of the SCAN BEAM. The second active edge d-a extends in similar fashion from its intersection 920 with line E and instersection 930 with line F. The third and fourth active
edges e-f and h-e originate at the vertex e, and are therefore newly added to the ACTIVE EDGE TABLE as of this SCAN BEAM. Edge a-b termintates at the upper line B defining the SCAN BEAM. Finally, an intersection j1 occurs between edges d-a and e-f,
detected by the fact that the X-value 940 of edge e-f is less than the corresponding value 930 of edge d-a.
Associated with each edge of the ACTIVE EDGE TABLE is a POLYGON STACK which shows in order the polygons imaged to the left of the edge, and the cumulative WINDING NUMBER for the edges (traversed left to right in the ACTIVE EDGE TABLE) up to the
edge. Only the highest-numbered polygon is unclipped and imaged in the ORIGINAL IMAGE on the left side of that edge. The POLYGON STACK is a sequence {POLYGON NUMBER: WINDING NUMBER, . . . }. Similarly, two consecutive edges in the ACTIVE EDGE TABLE
having a higher-numbered polygon on the POLYGON STACK indicate that the line corresponding to the first such edge is "hidden" since a covering fill color exists on both sides. In the SCAN BEAM E-B shown in FIG. 9, for example, the initial entries for
the ACTIVE EDGE TABLE and POLYGON STACK (at the bottom of the SCAN BEAM) are as follows:
______________________________________ ACTIVE EDGE TABLE: { a-b d-a e-f h-e } POLYGON STACK: {none} {2:1} {none} {1:1} ______________________________________
Thus, line a-b has only background to its left, line d-a borders polygon 2 (the "red polygon") to its left with a cumulative winding number of 1, line e-f has only background to its left, and line h-e borders polygon 1 (the "blue polygon") to its
left. Accordingly, boundaries are open for line a-b ("white" to "red"), d-a ("red" to "white"), e-f ("white" to "blue") and h-e ("blue" to "white").
The active edges in the ACTIVE EDGE TABLE are maintained in order of increasing X-value at the lower line Y.sub.i defining the SCAN BEAM. Edges where X-values at Y.sub.i are the same are ordered by X-value at Y.sub.i+1. Any processing step
which causes active edges to be added or removed from the ACTIVE EDGE TABLE causes the POLYGON STACKS of any intervening edges to be updated such that they always provide the above information.
FIG. 10 shows the flow chart for the step 850 of FIG. 8 for processing intersections which occur within a given SCAN BEAM extending between Y-values Y.sub.i and Y.sub.i+1. The first step is to identify intersections 1010 by comparing the
X-values at the upper line Y.sub.i+1 defining the SCAN BEAM as described above for FIG. 9. Since the active edges in the ACTIVE EDGE TABLE are maintained in order of increasing X-value at the lower line Y.sub.i defining the SCAN BEAM, the upper edges
are similarly ordered unless an intersection has occurred. The list of intersections found in step 1010 is sorted 1020 by increasing Y-value, and a loop performed 1030 in which each intersection is processed. The entries for the intersecting edges are
switched 1040 in the ACTIVE EDGE TABLE, reflecting the new left-right ordering of edges above the intersection point within the SCAN BEAM. Finally, the POLYGON STACK information is updated 1050 according to the data associated with the edges above the
intersection. Accordingly, in the example o | | |
