US6285805B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
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
Assignee: Uniloc 2017 LLC
•
Filing: 1999-01-25
•
Granted: 2001-09-04
•
Expires: 2019-01-25
Abstract
Abstract The present invention is a computer system and method for determining the closest point on a shape (2 dimensional or 3 dimensional surface) to any general query point. The system has one or more central processing units (CPUs), one or more memories, and one or more geometric model portions stored in one or more of the memories. The geometric model portions have a plurality of line segments (polygons), each of the line segments (polygons) being between a first and a second endpoint (having a polygon boundary). The line segments and end points (polygons and polygon boundaries) are connected to form a shape (in 3 dimensions, a surface) with one or more parameters. Parameters can include geometric position, time, temperature, pressure, flow, color, texture, or any other descriptive value. A multiresolution process that creates one or more models of the shape (surface). The models having a hierarchy of resolutions. Each model has one or more model line segments (model polygons) that approximate one or more of the line segments (polygons). Each model line segment (model polygons) is associated with an error. A distance process, for every model line segment (polygon), determines a distance between a closest point on one or more of the model line segments and a query point. The distance represents one or a combination of two or more of the parameters. The process further determines a confidence level in terms of an upper bound and a lower bound of an envelope enclosing the segment (polygon). The closest point is 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. A priority process orders the model line segments (polygons) according to their respective lower bounds and if a maximum error for every one of the model line segments is less than a threshold. The priority process also selects the smallest distance as the minimum distance between the query point and the shape.
Inventors
- 👤 Andre Gueziec
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 20:36
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/60; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
314 words
A system for determining a closest point on a shape to a query point comprising: one or more memories for storing 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 a shape including one or more parameters; and one or more central processing units (CPU's) for executing: a multiresolution process that creates one or more models of the shape, the one or more 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 model line segment is associated with an error; a distance process that for every model line segment determines 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, the distance process further determining an upper bound and a lower bound of an envelope enclosing the 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 converging to each other; and a priority process that orders 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 a minimum distance between the query point and the shape.
Claim 2
Independent Claim
314 words
A system for determining a closest point on a shape to a query point comprising: one or more memories for storing 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 a shape including one or more parameters; and one or more central processing units (CPU's) for executing: a multiresolution process that creates one or more models of the shape, the one or more 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 model line segment is associated with an error; a distance process that for every model line segment determines 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, the distance process further determining an upper bound and a lower bound of an envelope enclosing the 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 converging to each other; and a priority process that orders 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 a minimum distance between the query point and the shape.
Claim 3
Dependent Claim
32 words
A system, as in claim 1 , where, if one or more of the maximum errors is greater than the threshold the priority process, selects a model shape with a higher resolution.
Claim 4
Dependent Claim
42 words
A system, as in claim 2 , where, if one or more of the maximum errors is greater than the threshold the priority process, selects a model with a higher resolution for the segments having the maximum error greater than the threshold.
Claim 5
Dependent Claim
19 words
A system, as in claim 2 , where the model shape selected is the next in the hierarchical order.
Claim 6
Dependent Claim
20 words
A system, as in claim 2 , where the model shape selected is not the next in the hierarchical order.
Claim 7
Dependent Claim
20 words
A system, as in claim 1 , where the priority process orders the model line segments in a priority queue.
Claim 8
Dependent Claim
22 words
A system, as in claim 1 , where the maximum error is the sum of the lower error and the upper error.
Claim 9
Dependent Claim
32 words
A system, as in claim 1 , where the parameter distance represents any one and more of the following: a physical distance, a color, a texture, or a distance between data values.
Claim 10
Dependent Claim
13 words
A system, as in claim 1 , where the query point is moving.
Claim 11
Dependent Claim
40 words
A system, as in claim 9 , where the query point is on a second shape and the query point is moved until a minimum shape distance, within a shape tolerance, is determined between the shape and the second shape.
Claim 12
Independent Claim
296 words
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.
Claim 13
Independent Claim
296 words
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.
Claim 14
Dependent Claim
40 words
A system, as in claim 11 , where the query point is on a second surface and the query point is moved until a minimum surface distance, within a surface tolerance, is determined between the surface and the second surface.
Claim 15
Dependent Claim
47 words
A system, as in claim 11 , where there are more than one query point, and the query points in a query sequence and the system selects a sequence of smallest distances, each of the smallest distances associated with the respective query point in the query sequence.
Claim 16
Dependent Claim
20 words
A system, as in claim 11 , where the query point is selected by a user using an input device.
Claim 17
Dependent Claim
18 words
A system, as in claim 11 , where the geometric model portion is acquired from an imaging device.
Claim 18
Dependent Claim
39 words
A system, as in claim 15 , where the imaging device includes any one or more of the following: a digital camera, a medical imaging system, a x-ray system, an ultrasound system, a CT scanner, a digital video camera.
Claim 19
Dependent Claim
29 words
A system, as in claim 11 , where, if one or more of the maximum errors is greater than the threshold, selecting a model shape with a higher resolution.
Claim 20
Dependent Claim
39 words
A system, as in claim 17 , where, if one or more of the maximum errors is greater than the threshold, selecting a model with a higher resolution for the segments with the maximum error greater than the threshold.
Claim 21
Dependent Claim
19 words
A system, as in claim 17 , where the model shape selected is the next in the hierarchical order.
Claim 22
Dependent Claim
20 words
A system, as in claim 17 , where the model shape selected is not the next in the hierarchical order.
Claim 23
Dependent Claim
20 words
A system, as in claim 11 , where the priority process orders the model lines segments in a priority queue.
Claim 24
Dependent Claim
22 words
A system, as in claim 11 , where the maximum error is the sum of the lower error and the upper error.
Claim 25
Dependent Claim
18 words
A system, as in claim 11 , where the upper bound is parallel to the model line segment.
Claim 26
Dependent Claim
18 words
A system, as in claim 11 , where the lower bound is parallel to the model line segment.
Claim 27
Dependent Claim
32 words
A system, as in claim 11 , where the parameter distance represents any one or more of the following: a physical distance, a color, a texture, and a distance between data values.
Claim 28
Dependent Claim
13 words
A system, as in claim 11 , where the query point is moving.
Claim 29
Dependent Claim
40 words
A system, as in claim 26 , where the query point is on a second shape and the query point is moved until a minimum shape distance, within a shape tolerance, is determined between the shape and the second shape.
Claim 30
Dependent Claim
44 words
A system, as in claim 11 , further comprising: a robotic manipulator with a controller for moving the robotic manipulator; one or more input devices for selecting one or more query points; and one or more imaging devices for creating the geometric model portion.
Claim 31
Independent Claim
293 words
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.
Claim 32
Independent Claim
293 words
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.
Claim 33
Dependent Claim
307 words
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.
Claim 34
Dependent Claim
307 words
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.
References Cited (Backward Citations)
US5189709A
Cited
US5715166A
Cited
US5566292A
Cited
US5655063A
Cited
US6104404A
Cited
US5892515A
Cited
US6137910A
Cited
US6108006A
Cited
US6128767A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-09-03 | 2005-03-05 | 2005-09-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-09-03 | 2009-03-05 | 2009-09-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-09-03 | 2013-03-05 | 2013-09-04 | $7700.00 | Window Closed / Lapsed |