Three dimensional extension of Bresenham’s algorithm with Voronoi diagram

Simple item page
dc.contributor.authorAu, Chi Kit
dc.contributor.authorWoo, Tony
dc.date.accessioned2010-12-07T03:45:29Z
dc.date.available2010-12-07T03:45:29Z
dc.date.issued2010
dc.description.abstractBresenham’s algorithm for plotting a two-dimensional line segment is elegant and efficient in its deployment of mid-point comparison and integer arithmetic. It is natural to investigate its three-dimensional extensions. In so doing, this paper uncovers the reason for little prior work. The concept of the mid-point in a unit interval generalizes to that of nearest neighbours involving a Voronoi diagram. Algorithmically, there are challenges. While a unit interval in two-dimension becomes a unit square in three-dimension, “squaring” the number of choices in Bresenham’s algorithm is shown to have difficulties. In this paper, the three-dimensional extension is based on the main idea of Bresenham’s algorithm of minimum distance between the line and the grid points. The structure of the Voronoi diagram is presented for grid points to which the line may be approximated. The deployment of integer arithmetic and symmetry for the three-dimensional extension of the algorithm to raise the computation efficiency are also investigated.en_NZ
dc.format.mimetypeapplication/pdf
dc.identifier.citationAu, C.K. & Woo, T. (2010). Three dimensional extension of Bresenham’s algorithm with Voronoi diagram. Computer-Aided Design, available online 3 December 2010.en_NZ
dc.identifier.doi10.1016/j.cad.2010.11.006en_NZ
dc.identifier.urihttps://hdl.handle.net/10289/4852
dc.language.isoen
dc.publisherElsevieren_NZ
dc.relation.isPartOfComputer-Aided Designen_NZ
dc.rightsThis is an author’s accepted version of an article published in the journal: Computer-Aided Design. © 2010 Elsevier.en_NZ
dc.subjectvoronoi diagramen_NZ
dc.subjectBresenham algorithmen_NZ
dc.subjectinteger arithmeticen_NZ
dc.subjectsymmetryen_NZ
dc.titleThree dimensional extension of Bresenham’s algorithm with Voronoi diagramen_NZ
dc.typeJournal Articleen_NZ
pubs.begin-page417en_NZ
pubs.elements-id37002
pubs.end-page426en_NZ
pubs.issue4en_NZ
pubs.volume43en_NZ
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Three dimensional.pdf
Size:
472.42 KB
Format:
Adobe Portable Document Format
Description:
Thumbnail Image
Name: Three dimensional.pdf
Size: 472.42 KB
Kind: Adobe PDF
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Name: license.txt
Size: 1.71 KB
Kind: License
Collections
Science and Engineering Papers