System and method for finding the distance from a moving query point to the closest point on one or more convex or non-convex shapes

A system for determining a closest point on a surface to a query point comprising:

• on or more memories for restoring one or more geometric model portions, the geometric model portions having a plurality of polygons, each of the polygons having a polygon boundary, wherein the polygons and polygon boundaries are connected to form a surface including one or more parameters;
• one or more central processing units (CPU's) for executing:
• a multiresolution process that creates one or more models of the surface, the models having a hierarchy of resolutions, wherein each model includes one or more model polygons approximately one or more of the polygons and wherein each model polygon is associated with an error;
• a distance process that for every model polygon determines a distance between a closest point on one or more of the model polygons and a query point, the distance representing one or more of the parameters, the distance process further determining an upper bound and a lower bound of an envelope enclosing the polygons, the closest point being within the envelope, the upper bound representing an upper limit of the parameter in the envelope determined by an upper error of the respective model containing the model line segment and the lower bound representing a lower limit of the parameter in the envelope determined by a lower error of the respective model, wherein the upper bound and the lower bound of the envelope are parallel to each other or convergent to each other;
• and
• a priority process that orders the model polygons according to their respective lower bounds if a maximum error for every one of the model polygons is less than a threshold, the priority process selecting a smallest distance as a minimum distance between the query point and the surface.

A method for finding a minimum distance between one or more query points and a shape in one or more geometric model portions, the geometric model portions having a plurality of line segments, each of the line segments being between a first and a second endpoint, wherein the line segments and end points are connected to form the shape, the shape including one or more parameters, the method further comprising the steps of:

• creating one or more models of the shape, the models having a hierarchy of resolutions, wherein each model has one or more model line segments approximating one or more of the line segments and wherein each of the model line segments is associated with an error;
• determining a distance between a closest point on one or more of the model line segments and a query point, the distance representing one or more of the parameters;
• determining an upper bound and a lower bound of an envelope enclosing the model line segment, the closest point being within the envelope, the upper bound representing an upper limit of the parameter in the envelope determined by an upper error of the respective model containing the model line segment and the lower bound representing a lower limit of the parameter in the envelope determined by a lower error of the respective model, wherein the upper bound and the lower bound of the envelope are parallel to each other or convergent to each other;
• and
• ordering the model line segments according to their respective lower bounds using a priority process if a minimum error for every one of the model line segments is less than a threshold, the priority process selecting a smallest distance as the minimum distance between the query point and the shape.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for finding a minimum distance between one or more query points and a shape in one or more geometric model portions, the geometric model portions having a plurality of line segments, each of the line segments being between a first and a second endpoint, wherein the line segments and end points are connected to form the shape including one or more parameters, the method further comprising the steps of:

• creating one or more models of the shape, the models having a hierarchy of resolutions, wherein each model comprises one or more model line segments approximating one or more of the line segments and wherein each of the model line segments is associated with an error;
• determining a distance between a closest point on one or more of the model line segments and a query point, the distance representing one or more of the parameters;
• determining an upper bound and a lower bound of an envelope enclosing the model line segment, the closest point being within the envelope, the upper bound representing an upper limit of the parameter in the envelope determined by an upper error of the respective model containing the model line segment and the lower bound representing a lower limit of the parameter in the envelope determined by a lower error of the respective model, wherein the upper bound and the lower bound of the envelope are parallel to each other or convergent to each other;
• and
• ordering the model line segments according to their respective lower bounds if a maximum error for every one of the model line segments is less than a threshold, the priority process selecting a smallest distance as the minimum distance between the query point and the shape.