Generation of circular and elliptical arcs | |
| Author | Setiabudi, Djoni Haryadi |
| Call Number | AIT Thesis no. CS-91-4 |
| Subject(s) | Computer graphics Computer-aided design |
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of Engineering School of Engineering and Technology |
| Publisher | Asian Institute of Technology |
| Abstract | Ten important algorithms of circle generation and six algorithms of ellipse generation were analyzed both analytically and experimentally in this study. The methods considered were: Bresenham, Kappel, Double-step, DDA (Digital Differential Analyzer), Difference and NURBS (Nonuniform Rational B-Spline). The main criteria used in comparing the algorithms concerned were the speed and accuracy. The implementation of drawing arcs on the screen was based on the eight-way symmetry concept for circle and four-way symmetry for ellipse. Furthermore, the problem in accuracy of intersection between a circle and a straight line and between two circles was also considered using a unified representation. There are two formulations of the intersection between a straight line and a circle. The first formulation uses an initial point of the line outside the circle, the second formulation uses the midpoint of the line between the intersection points as the initial point. For circle-circle intersection, there are three formulations. The first formulation uses the radical axis intersecting with one of the two circles. The second formulation uses the radical axis intersecting with the orthogonal circle obtained by adding the weighting equations of the two circles. The third formulation uses the radical axis intersecting with the orthogonal circle obtained by adding the equations of the two circles. From the study, the following conclusions can be made : 1. The datatype used for the methods is the main role of the speed performance. The Kappel algorithm for generating ellipse can be improved significantly by changing the datatype from real to integer. 2. The time spent for generating the points of the arcs is much shorter than the time for displaying the pixels on the screen. 3. NURBS methods give the best visual looking appearance. 4. Incremental methods have the highest speed performance among all of the three categories, incremental, parametric and approximation. 5. For the rounding error the Bresenham method gives the least errors, but for the real error the NURBS gives the least errors. 6. From the two formulations of the intersection between a straight line and a circle, the first formulation requires less numerical calculations. 7. From the three formulations of the intersection between two circles, the first and the third formulations give higher accuracy and the second formulation is more efficient. |
| Year | 1991 |
| Type | Thesis |
| School | School of Engineering and Technology (SET) |
| Department | Other Field of Studies (No Department) |
| Academic Program/FoS | Computer Science (CS) |
| Chairperson(s) | Huynh Ngoc Phien |
| Examination Committee(s) | Bohez, Erik L.J. ;Zhao, Ming |
| Scholarship Donor(s) | Petra Christian University Surabaya, Indonesia |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 1991 |