US 9,437,014 B2Granted

Method for labeling segments of paths as interior or exterior

AssigneeMitsubishi Electric Research Laboratories, Inc.

InventorsRonald N Perry, Elena J Jakubiak

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for labeling a segment of a two-dimensional input path defined according to a nonzero winding rule as either interior or exterior is described. A winding number is initialized. A scan line that intersects the segment is identified. For each contour of the input path, winding values are accumulated into the winding number for any segments of the contour that cross the identified scan line, where the accumulation for coincident segments that cross the identified scan line at a same location as the segment is postponed. These coincident segments are marked and saved in a list. The labeling of the segment as either interior or exterior is determined from the list and the winding number.

Claims15

Dependent claims

A method for labeling a segment of an object-based input path as either interior or exterior, wherein the object-based input path is defined according to a nonzero winding rule in a two-dimensional (2D) coordinate system the object-based input path includes a set of contours, and wherein each contour includes a sequence of segments, the method comprising the steps of:

initializing a winding number to zero;
identifying a scan line that intersects the segment;
accumulating, for each contour, winding values into the winding number for any segments of the contour that cross the scan line, wherein the accumulation for coincident segments of the contour that cross the scan line at a same location as the segment is postponed until after all the contours have been processed, and wherein the coincident segments are marked, and wherein the marked coincident segments are saved in a list;
labeling the segment as interior if the list is empty and the winding number for is not zero and the winding number when updated to account for the segment is not zero;
labeling the segment as exterior if the list is empty and either the winding number is zero or the winding number when updated to account for the segment is zero;
labeling the segment as interior if the list is not empty and, after canceling out pairs of segments of the list that:
have opposite directions, the list is augmented to contain the segment, and accumulating the winding values into the winding number for any remaining non-cancelled segments in the list excluding the segment, the winding number is not zero and the winding number when updated to account for the segment is not zero;
and
labeling the segment as exterior if the list is not empty and, after canceling out pairs of segments of the list that have opposite directions, the list is augmented to contain the segment, and accumulating the winding values into the winding number for the remaining non-cancelled segments in the list excluding the segment, either the winding number is zero or the winding number when updated to account for the segment is zero, wherein the labeled segment when rendered to a pixel grid represents sub-pixel geometry, such that the obiect-based input path when rendered labels the segment within a single pixel, wherein the steps are performed in a processor.

6 more elements

A system for providing labeling of a segment of an object-based input path as either interior or exterior, wherein the object-based input path is defined according to a nonzero winding rule in a two-dimensional (2D) coordinate system the object-based input path includes a set of contours, and wherein each contour includes a sequence of segments, the system comprising:

a data storage memory unit for storing information therein about one or more lists, one or more paths and related data so as to provide labeling for the segment of the object-based input path;
a processor, coupled to the data storage memory unit, that is configured to:
initialize a winding number to zero;
identify a scan line that intersects the segment;
accumulate, for each contour, winding values into the winding number for any segments of the contour that cross the scan line, wherein the accumulation for coincident segments of the contour that cross the scan line at a same location as the segment is postponed until after all the contours have been processed, and wherein the coincident segments are marked, and the marked coincident segments are saved in a list;
label the segment as interior, if the list is empty and, the winding number is not zero and the winding number when updated to account for the segment is not zero;
label the segment as exterior, if the list is empty and either the winding number is zero or the winding number when updated to account for the segment is zero;
label the segment as interior, if the list is not empty and, after canceling out pairs of segments of the list that have opposite directions, the list is augmented to contain the segment, and accumulating the winding values into the winding number for any remaining non-cancelled segments in the list excluding the segment, the winding number is not zero and the winding number when updated to account for the segment is not zero;
and
label the segment as exterior, if the list is not empty and, after canceling out pairs of segments of the list that have opposite directions, the list is augmented to contain the segment, and accumulating the winding values into the winding number for the remaining non-cancelled segments in the list excluding the segment, either the winding number is zero or the winding number when updated to account for the segment is zero, wherein the labeled segment when rendered to a pixel grid is capable of representing sub-pixel geometry, such that the object-based input path when rendered labels the segment within a single pixel, wherein the steps are performed in a processor.

7 more elements

Dependencies are inferred from the claim text.