iterative determination of the shortest path between two points on a polygonoberflu00e4che

摘要

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.