Computer Graphics for Java Programmers, Second Edition

Chapter 4. Some Classic Algorithms

Although programming is a very creative activity, often requiring entirely new (little) problems to be solved, we can sometimes benefit from well-known algorithms, published by others and usually providing more efficient or more elegant solutions than those we would have been able to invent ourselves. This is no different in computer graphics. This chapter is about some well-known graphics algorithms for (a) computing the coordinates of pixels that comprise lines and circles, (b) clipping lines and polygons, and (c) drawing smooth curves. These are the most primitive operations in computer graphics and should be executed as fast as possible. Therefore, the algorithms in this chapter ought to be optimized to avoid time-consuming executions, such as multiplication, division, and calculations on floating point numbers.

BRESENHAM'S ALGORITHM FOR LINE DRAWING

We will now discuss how to draw lines by placing pixels on the screen. Although, in Java, we can simply use the method drawLine without bothering about pixels, it would be unsatisfactory if we had no idea how this method works. We will be using integer coordinates, but when discussing the slope of a line it would be very inconvenient if we had to use a y-axis pointing downward, as is the case with the Java device coordinate system. Therefore, in accordance with mathematical usage, the positive y-axis will point upward in our discussion.

Unfortunately, Java lacks a method with the sole purpose of putting ...