The fixed-point arithmetic has the property of performing operations with fractional numbers at an integer computational cost. Although it is not supported in a native way by the programming languages and by the generalist CPUs, it is the ideal arithmetic for applications in the field of industrial control, simulation, computer graphics, multimedia and digital signal treatment, etc. It has not been extended in many computer fields since it lacks from normalisation and support.
This thesis justifies the use of this arithmetic in computer science and concretely in the field of computer graphics. Firstly it makes an implementation and normalisation study of the arithmetic presenting relative power increments and precisions obtained in arithmetic operations, sine, exponential or logarithmic functions. Following it is applied to some examples of discrete and flight simulation.
This thesis analyses, in the field of computer graphics, the basic primitives drawing algorithms such as lines, with and without aliasing, line clipping, circles and ellipses. A state of the art study in these four fields is performed. Following, some algorithm implementations based on fixed-point arithmetic are presented. The computational cost and the precision are compared to the brute force algorithms and the traditional ones.
While the traditional algorithms use to present an average error between 0.32 and 0.45 pixels, depending on the primitive analysed, the algorithms based on the fixed-point arithmetic do not overpass the 0.25 pixels on average. This equals the minimum theoretical error generated by the brute force algorithms.
On the other hand, the algorithms based on the fixed-point arithmetic; use to improve the average speed of the traditional algorithms. Sometimes high speed-up may be obtained if parallelisation techniques are used. This is the case of the DDA algorithm parallel version with and without antialiasing. This algorithm could draw a line within a logarithmic timing cost respect to its length in pixels.
The algorithms obtained are so easy that some of them can be implemented in hardware inside a graphical processor in a very efficient manner employing a low consume of resources or implement them in a form of very fast routines in assembler inside a graphical package like OpenGL or like printer controllers. The parallelisation techniques allow using schemes SIMD easily implementable in SWAR commercial architectures like MMX or higher. The speed may be increased in a 30% more as the practical implementations suggest.