Method for converting two-dimensional objects to distance fields
AssigneeMitsubishi Electric Research Laboratories, Inc.
InventorsRonald N. Perry, Sarah F. Frisken
Life of this patent
Estimating the term…
Abstract
A method converts a two-dimensional object to a two-dimensional distance field. The object is represented as a set of boundary descriptors and a fill rule. The set of boundary descriptors is preprocessed and a spatial hierarchy is constructed from the preprocessed set of boundary descriptors. A cache of intersections is initialized. The spatial hierarchy is queried at a set of locations to determine a set of distances at the locations. The query invokes a distance function at each location to determine an unsigned distance. A sign of the unsigned distance is determined from the cache of intersections, the location, and the fill rule. The set of distances is used to construct the two-dimensional distance field.
Claims16
A method for converting a two-dimensional object to a two-dimensional distance field, the object represented as a set of boundary descriptors and a fill rule, comprising:
- preprocessing the set of boundary descriptors;
- constructing a spatial hierarchy from the preprocessed set of boundary descriptors;
- initializing a cache of intersections;
- and
- querying the spatial hierarchy at a set of locations to determine a set of distances at the locations, the set of distances used to construct a two-dimensional distance field, the querying further comprising:
- invoking a distance function at each location to determine an unsigned distance;
- and
- determining a sign of the unsigned distance using the cache of intersections, the location, and the fill rule.
Dependencies are inferred from the claim text.