Filling areas is applied in the context of drawing thick lines where thick lines are considered as long rectangles. But filling areas and polygons is also a general technique of computer graphics that is also needed as a drawing mode. This topic contains in addition to techniques for filling areas also basic models for colours and a short introduction to handling text in images.
Filling Areas
Areas are usually bounded by polygons or closed sequences of curves. In order to fill a polygon, points inside the polygon must be distinguished from exterior ones. For polygons whose edges do not intersect, it is obvious which points should be considered as inner and outer points. For polygons with intersecting edges it is not immediately clear what its inner parts are. The odd parity rule provides a definition of inner and outer points based on the following considerations.
If one starts to move along a line from an inner point of a polygon in one direction, then a bounding edge of the polygon must be reached at some point on the line. If the polygon is not convex, then it might happen that other edges are met, when the movement along the line is continued. Since the movement along the line was started at an inner point, one changes from the inner to the outer part of the polygon when the first polygon edge is met. After the second intersection point along the line with an edge, the polygon is entered again. So each time, when the line meets an edge, a change from the inside to the outside of the polygon or vice versa takes place. Since the polygon is bounded, the last edge that is met along the line must correspond to a change from the inside to the outside of the polygon. Because the starting point was assumed to be an inner point of the polygon, the intersection point with the first edge must also represent a change from inside to outside.
Figure 4.1 illustrates the application of the odd parity rule to selected points inside and outside a polygon. For each point a line is drawn and the number of intersection points of the line with edges of the polygon is given in the figure. If the number is odd, then the point is an interior (“int”) point of the polygon, otherwise it is an exterior (“ext”) point.
Fig. 4.1 Odd parity rule
Fig. 4.2 Scan line technique for filling polygons
The odd parity rule is a useful mathematical definition of interior and exterior points of a polygon, but it is not suited for implementation, since the computational costs would be unacceptable if the rule is applied separately to each pixel. Instead, a scan line technique is applied. Scan line techniques are very common in computer graphics. They carry out computations along a line, the scan line, usually along lines parallel to one of the coordinate axes. For each pixel row, the corresponding line is considered, and the intersection points of the line with polygon edges are determined. These intersection points are sorted in ascending order with respect to their x-coordinates.This means the scan line enters the polygon at xi, leaves the polygon at x2, enters it again at x3 until it finally leaves the polygon at xn. Therefore, exactly the pixels between x1 and x2, between x3 and x4, etc. and between xn-1 and xn must be drawn for filling the polygon. The number n of intersection points must be even including the possible value zero. Figure 4.2 illustrates the principle of this scan line technique.
For the implementation of the scan line technique, some specific problems need extra attention. One of these problems is clipping. It is necessary to compute all intersection points of the scan line with the polygon. But only those pixels need to be drawn that lie within the clipping area. Therefore, drawing might not start at the first intersection point x1. Another problem occurs when the scan line intersects vertices of the polygon. These cases need special treatment. In Fig. 4.3, the scan line intersects two vertices of the polygon. At the first vertex a change from the exterior to the interior part of the polygon takes place. At the second vertex, the scan line remains outside the polygon. The treatment of vertices as intersection points requires considering the angles between the scan line and the edges that are attached to the corresponding vertices. Horizontal edges also need a special treatment.
Fig. 4.3 A scan line intersecting two vertices of a polygon
Fig. 4.4 Filling a polygon can lead to aliasing effects
Filling and drawing the outlines of polygons are usually viewed as two different drawing modes. There might be pixels that belong to the interior as well as to the boundary of the polygon at the same time, especially when the polygon is drawn with thick lines. Antialiasing can also lead to points that belong to the interior and the boundary of the polygon. In order to avoid gaps at the boundary when a polygon should be filled and its boundary should be drawn as well, antialiasing must be applied to the outer part of the edges but not to their inner parts. Polygons with long acute-angled edges might introduce new aliasing effects when they are filled. The connected interior of the polygon might be represented as a disconnected set of pixels as the example in Fig. 4.4 demonstrates.
Instead of filling an area with one colour, a texture can also be used for filling. A texture can be an arbitrary image. Very often, textures are patterns, for instance in the form of grains of wood. Before an area can be filled with a texture, the position where the texture should start must be defined. Filling then means to draw the texture and to apply clipping with respect to the area that should be filled. Since areas can have an arbitrary shape, clipping might have to be applied to a nonrect-angular region. Sometimes the image defining the texture is too small to fill the complete area. In this case, the texture must be used repeatedly like tiles to fill the whole area. Here it is also necessary to apply clipping with respect to the area to be filled, and also an anchor must be specified. The anchor defines a starting point from which the texture is laid like tiles. The brick pattern texture on the left of Fig. 4.5 is used to fill the rectangle on the right. The black circle marks the anchor.
Fig. 4.5 Filling an area with a texture
When a texture is used repeatedly for filling an area, fissures might be visible at the places where the texture is repeated. This effect can also be seen in Fig. 4.5. The horizontal fissure is more articulated than the vertical one. This effect can be avoided when a texture is used where the left and right as well as the upper and lower edges fit together perfectly. There are also techniques to modify a texture in such a way that fissures will not occur. The best modification strongly depends on the type of texture. For textures with a very regular geometric pattern like the bricks in Fig. 4.5, it might be necessary to modify the whole geometric pattern. For textures with unstructured patterns like marble, it is very often sufficient to apply colour interpolation techniques at the edges as they are described in Sect. 4.7.
Buffered Images in Java 2D
The class BufferedImage in Java 2D is very useful for various purposes in connection with images. This section demonstrates how images can be loaded, how they can be used as textures and how images can be saved directly without the need of screen dumps. The previously mentioned double buffering technique is also introduced.
A BufferedImage, a subclass of Image, is an image in the memory of the computer. The usual drawing and filling commands are available for a BufferedImage, but a BufferedImage can also be drawn on an object of the class Image. In this way, a BufferedImage can be drawn on another BufferedImage or on a window on the computer screen.
The constructor
generates a BufferedImage, whose width and height in pixels are given by the integer values width and height. The constant BufferedImage.TYPE_ INT_RGB refers to the fact that the standard colour model is used for the BufferedImage. The method createGraphics() generates a Graphics2D object for the BufferedImage.
The Graphics2D object g2dbi can be used in the same way as the Graphics2D object g2d in the context of drawing on a window on the computer screen.
Methods like g2dbi.draw(…) or g2dbi.fill(…) will draw on the BufferedImage bi instead of the window on the computer screen. Since bi is only a virtual image in the memory, the results from calling these methods are not visible directly. The method1 g2d.drawImage(bi,xpos,ypos,null); allows bi to show in the window on the computer screen. bi will be drawn within the rectangle defined by the two opposing corners (xpos,ypos) and (xpos+width, ypos+height). It is also possible to draw bi onto another BufferedImage. In this case, the Graphics2D object g2d has to be replaced by the Graphics2D object of the corresponding BufferedImage.
Double Buffering in Java 2D
It was mentioned in Sect. 2.9 that it is not recommended to carry out all computations needed for drawing within the paint method. At least for animated graphics, it is better to exclude the computations from the paint method and to draw the desired image first on a BufferedImage outside the paint method. In the paint method only the updated BufferedImage will be drawn on the screen. In this case, the paint method should be called by the repaint method in each step.
For the implementation of the double buffering technique, it is necessary to modify the class that was used so far for drawing images on the screen. The computations that were so far carried out within the paint method will be transferred to a new class. The old class for the window on the computer screen is extended by the following two attributes:
These two attributes are the BufferedImage which has to be drawn within the paint method and its corresponding Graphics2D object. The constructor should make sure that they are initialised with the corresponding instances. Since the repaint method calls the update method of the window which overwrites the complete window, and because this can lead to flickering effects, the update method should be overwritten and the corresponding BufferedImage bi should be drawn in the update method. When the window is drawn the first time, the paint method is called, so that the update method should be called there as well. Altogether, the paint and the update method should be overwritten in the following way:
Because the update method is called repeatedly for animations, its Graphics2D object g2d is defined as an attribute of the class, so that it is not necessary to generate it each time. This implementation and further details can be found in the file BufferedImageDrawer.java, which can be used as a generic class for the double buffering technique. The image sequence to be drawn is computed outside this class. The clock, already known from Sect. 2.10, will serve as an example. All calculations for drawing the clock now take place in the class DoubleBufferingClockExample.java. Since the paint method of the BufferedImageDrawer will be called in short time intervals again and again, this class is implemented as an extension of the Java class TimerTask. Any subclass of TimerTask must have a run method. This method is called repeatedly with fixed time intervals in between. The run method contains the same commands that are already known from the for-loop of the old paint method of the class NonSynchronizedClock for the clock without double buffering. Only the following changes are necessary.
• Instead of the Graphics2D object of the paint method of the window, the Graphics2D object of the corresponding BufferedImage bi is used.
• Instead of overwriting the image, i.e., the BufferedImage bi, by a white rectangle each time, before the image is updated, another BufferedImage is used as a background image. Therefore, this background image is drawn each time on bi, before the updated clock itself is drawn. The background image also contains a fixed rectangular frame around the whole scene that will not change during the animation.
• At the end of the run method the repaint method of the BufferedImageDrawer is called.
The initialisations take place in the main method and in the constructor of DoubleBufferingClockExample. The run method, which computes the image sequence and initiates the drawing of the updated image on the screen each time, is called repeatedly by
dbce is an instance of the class DoubleBufferingClockExample and delay specifies after how many milliseconds the image should be updated. The second value defines the waiting time until the run method is called the first time, i.e., the time until the animation is started.
