Patent ID: 7379062

Claim:
A computer-implemented method of determining a path along a three-dimensional object represented by a three-dimensional volume data set, the data set comprising a plurality of voxels each having a value indicating a characteristic of material represented by the voxel and arranged in a three-dimensional array, the method comprising: selecting a path start voxel s and a path end voxel e from voxels lying within the object; and determining a path from the start voxel s to the end voxel e via one or more intermediate voxels n lying within the object by using a minimum cost path finding algorithm to select the intermediate voxels n, where the algorithm prioritizes voxels for possible selection using a priority function that depends on a cost function that defines costs for paths between voxels, and on the Euclidean distance from a voxel to the end voxel e such that a smaller Euclidean distance gives a greater contribution to priority for that voxel, and the Euclidean distance is weighted by a constant k which is greater than 1; and wherein the minimum cost path finding algorithm is a modified version of Dijkstra's algorithm.