TY - JOUR

T1 - 3D extension of Bresenham's algorith and its application in straight-line interpretation

AU - Liu, X.

AU - Cheng, K.

N1 - Original article can be found at:http://www.metapress.com/content/0954-4054/ Copyright MetaPress. [Full text of this article is not available in the UHRA]

PY - 2002

Y1 - 2002

N2 - Conventional straight-line generating algorithms, such as the digital differential analyser (DDA), Bresenham's algorithm and the mid-point algorithm, are suitable only for planer straight lines on the coordinate planes, of which Bresenham's algorithm is the most efficient. In this paper, the authors have extended Bresenham's algorithm to spatial straight lines. Given a spatial straight-line segment with two end-points, the authors have applied Bresenham's algorithm to the projections of the line segment on two of the three coordinate planes, which is determined by the largest of the coordinate lengths of the line segment, thereby obtaining a three-dimensional extension of the algorithm. In a case study, the authors calculated the distance between each sample position and the given line segment. The result reveals that the actual error at each sample position is smaller than the maximum theoretical error, and the performance of the three-dimensional extension of Bresenham's algorithm is as good as that of Bresenham's original planer algorithm. One of its potential applications is the three-dimensional step straight-line interpolation used in computer numerical control (CNC) systems of machine tools and rapid prototyping machines. Application of the algorithm is contrasted with that of the traditional DDA step straight-line interpolation algorithm. The result confirms that the three-dimensional extension of Bresenham's algorithm is much better than the DDA straight-line interpolation algorithm.

AB - Conventional straight-line generating algorithms, such as the digital differential analyser (DDA), Bresenham's algorithm and the mid-point algorithm, are suitable only for planer straight lines on the coordinate planes, of which Bresenham's algorithm is the most efficient. In this paper, the authors have extended Bresenham's algorithm to spatial straight lines. Given a spatial straight-line segment with two end-points, the authors have applied Bresenham's algorithm to the projections of the line segment on two of the three coordinate planes, which is determined by the largest of the coordinate lengths of the line segment, thereby obtaining a three-dimensional extension of the algorithm. In a case study, the authors calculated the distance between each sample position and the given line segment. The result reveals that the actual error at each sample position is smaller than the maximum theoretical error, and the performance of the three-dimensional extension of Bresenham's algorithm is as good as that of Bresenham's original planer algorithm. One of its potential applications is the three-dimensional step straight-line interpolation used in computer numerical control (CNC) systems of machine tools and rapid prototyping machines. Application of the algorithm is contrasted with that of the traditional DDA step straight-line interpolation algorithm. The result confirms that the three-dimensional extension of Bresenham's algorithm is much better than the DDA straight-line interpolation algorithm.

U2 - 10.1243/0954405021519979

DO - 10.1243/0954405021519979

M3 - Article

SN - 0954-4054

VL - 216

SP - 459

EP - 463

JO - Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture

JF - Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture

IS - 3

ER -