Iterative determination of the shortest path between two points on a polygonal surface

• US 6,392,646 B1
• Filed: 12/22/1999
• Issued: 05/21/2002
• Est. Priority Date: 12/22/1999
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Yamrom, Boris, Alyassin, Abdalmajeid Musa
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/469,750
• Time in Patent Office: 881 Days
• Field of Search: 345/418, 345/419, 345/420, 345/421, 345/422, 345/423, 345/424, 345/426
• US Class Current: 345/420
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A storage medium encoded with machine-readable computer program is used for finding the shortest path between two points on a polygonal surface. The storage medium includes instructions for causing a computer to implement a method for finding the shortest path. Given a first point and a second point on the polygonal surface, a polyline lying on the surface and passing through the two points is defined. The polyline on a polygonal mesh is analyzed to determine points lying on the polyline and on edges of the mesh. The polygonal faces of the mesh are assumed, without any loss of generality, to be triangles. If the start and end points of the polyline are not on the edges of the mesh, the faces of the polygonal surface on which the start and end points of the polyline lie are triangulated so that the start and end points become vertices of the polygonal mesh. The polyline is then modified such that it will pass through the first and second points of the polyline, creating a new polyline of a shorter length. The analysis, triangulation and modification process are repeated iteratively until a shortest possible polyline is found between the first and second points.

Claims

1. A method for finding the shortest path between two points on a polygonal surface comprising:

establishing a polyline lying on said surface and passing through a first point and second point on said surface;

analyzing said polyline on a polygonal mesh defining said surface to determine points lying on said polyline and on edges of said mesh, said mesh having polygonal faces in the form of triangles;

modifying said polyline such to pass through said first and second points of said polyline and thereby create a new polyline of shorter length than said first polyline; and

repeating the analysis, triangulation and modification iteratively until a shortest possible polyline is found between said first and second points.

2. The method of claim 1 wherein start and end points of said polyline lie on other than an edge of said polygonal mesh and including, prior to modifying said polyline:

triangulating faces of said polygonal surface upon which said start and end points of said polyline lie to become vertices of said polygonal mesh.

3. The method of claim 1 wherein one of said start and end points of said polyline lies on other than an edge of said polygonal mesh and including, prior to modifying said polyline:

triangulating a face of said polygonal surface upon which said one of the start and end points of said polyline lies to become a vertex of said polygonal mesh.

4. The method of claim 1 wherein said polygonal surface is a polygonal representation of one of the group consisting of earth'"'"'s surface, a computer graphics display, and industrial CAD parts.

5. The method of claim 1 wherein said polygonal surface is a polygonal representation of a human body part extracted from a medical modality data set from one of the group consisting of magnetic resonance, computerized tomography, and X-ray.

9. The storage medium of claim 4 wherein the polygonal surface is a polygonal representation of one of the group consisting of earth'"'"'s surface, a computer graphics display, and industrial CAD parts.

6. A storage medium encoded with a machine-readable computer program for finding the shortest path between two points on a polygonal surface, the storage medium including instructions for causing a computer to implement a method comprising:

establishing a polyline lying on said surface and passing through a first point and a second point on said surface;

analyzing said polyline on a polygonal mesh defining said surface to determine points lying on said polyline and on edges of said mesh, said mesh having polygonal faces in the form of triangles;

modifying said polyline to pass through said first and second points of said polyline and thereby create a new polyline of shorter length than said first polyline; and

repeating the analysis, triangulation and modification iteratively until a shortest possible polyline is found between said first and second points.

7. The storage medium of claim 6 wherein start and end points of said polyline lie on other than an edge of said polygonal mesh and including, prior to modifying said polyline:

triangulating faces of said polygonal surface upon which said start and end points of said polyline lie to become vertices of said polygonal mesh.

8. The storage medium of claim 6 wherein one of said start and end points of said polyline lies on other than an edge of said polygonal mesh and including, prior to modifying said polyline:

triangulating a face of said polygonal surface upon which said one of the start and end points of said polyline lies to become a vertex of said polygonal mesh.

10. The storage medium of claim 6 wherein said polygonal surface is a polygonal representation of a human body part extracted from a medical modality data set from one of the group consisting of magnetic resonance, computerized tomography, and X-ray.

11. A computer program for use with a graphics display device, said computer program comprising:

a computer usable medium capable of having computer readable program code means embodied in said medium for finding the shortest path between two points on a polygonal surface; and

computer readable program code embedded in said medium and adapted to operate a computer to perform the steps of;

establishing a polyline lying on said surface and passing through a first point and a second point on said surface;

establishing a polyline lying on said surface and passing through a first point and a second point on said surface;

analyzing said polyline on a polygonal mesh defining said surface to determine points lying on said polyline and on edges of said mesh, said mesh having polygonal faces in the form of triangles;

modifying said polyline to pass through said first and second points of said polyline and thereby create a new polyline of shorter length than said first polyline; and

repeating the analysis, triangulation and modification iteratively until a shortest possible polyline is found between said first and second points.

12. The computer program of claim 11 wherein start and end points of said polyline lie on other than an edge of said polygonal mesh and including, prior to the step of modifying said polyline:

triangulating faces of said polygonal surface upon which said start and end points of said polyline lie to become vertices of said polygonal mesh.

13. The computer program of claim 11 wherein one of said start and end points of said polyline lies on other than on edge of said polygonal mesh and including, prior to the step of modifying said polyline:

triangulating a face of said polygonal surface upon which said one of the start and end points of said polyline lies to become a vertex of said polygonal mesh.

14. The computer program of claim 11 wherein the polygonal surface is a polygonal representation of one of the group consisting of earth'"'"'s surface, an image upon said computer graphics display, and industrial CAD parts.

15. The computer program of claim 11 wherein said polygonal surface is a polygonal representation of a human body part extracted from a medical modality data set from one of the group consisting of magnetic resonance, computerized tomography, and X-ray.

16. An article of manufacture for use in a computer having an operating system and a graphics support library for finding, or a graphics display, the shortest path between two points on a polygonal surface,

said article of manufacture comprising a storage medium having computer readable program code embedded therein, said program code being adapted to operate said computer to perform the steps of:

establishing a polyline lying on said surface and passing through a first point and a second point on said surface;

analyzing said polyline on a polygonal mesh defining said surface to determine points lying on said polyline and edges of said mesh, said mesh having polygonal faces in the form of triangles;

modifying said polyline to pass through said first and second points of said polyline and thereby create a new polyline of shorter length than said first polyline; and

repeating the analysis, triangulation and modification iteratively until a shortest possible polyline is found between said first and second points.

17. The article of manufacture of claim 16 wherein start and end points of said polyline lie on other than an edge of said polygonal mesh and including, prior to the step of modifying said polyline:

triangulating faces of said polygonal surface upon which start and end points of said polyline lie to become vertices of said polygonal mesh.

18. The article of manufacture of claim 16 wherein said one of said start and end points of said polyline lies on other than an edge of said polygonal mesh and including, prior to the step of modifying said polyline:

triangulating a face of said polygonal surface upon which said one of the start and end points of said polyline lies to become a vertex of said polygonal mesh.

19. The article of manufacture of claim 16 wherein the polygonal surface is a polygonal representation of one of the group consisting of earth'"'"'s surface, said computer display, and industrial CAD parts.

20. The article of manufacture of claim 16 wherein said polygonal surface is a polygonal representation of a human body part extracted from a medical modality data set from one of the group consisting of magnetic resonance, computerized tomography, and X-ray.