| |
ISSN 1320-0682 | |||
| Volume 02 | April 1995 | |||
Wayne J. Cosshall
School of Computer Science & Engineering
Swinburne University of Technology
P.O. Box 218 Hawthorn, Vic. 3122 Australia
Email: wayne@saturn.cs.swin.oz.au
Mathematically created images that are produced using computers are a relatively recent addition to the range of image-making options. The problem is whether such images are useful and meaningful in either or both an art and a science context or whether they are just a curiosity - something novel but with no intrinsic value. This paper seeks to address these issues.
I define mathematically generated images as those which are produced through the application of a mathematical formula or algorithm. This algorithm must be applied to directly generate the image, such as a computer display. This last condition is necessary otherwise a photograph of ocean waves could be defined as a mathematically generated image because the shape and behaviour of the waves and the optics of the camera can be mathematically modelled. Examples of mathematically generated images range from ray traced images, via Mandelbrot sets and simulated crystal growth through to the application of cellular automata.
Ray tracing [1] is one of several methods of rendering images that is able to produce high quality results. It aims to accurately model the way that light interacts with, reflects off and is transmitted through surfaces. The correct way to do this would be to follow many rays from each light source until they either enter the simulated camera or observer's eye or exit the world. This would be highly inefficient as most of the rays traced would not in fact reach the camera and much computation would be wasted. Thus, light rays are traced in reverse from the camera/eye into the scene. This reduces the rays traced to only those that can affect the look of the image.
At its simplest, a light ray is traced backwards from the viewer, through each pixel and into the object space, as shown in Figure 1. A test is made to determine which objects the ray intersects, if any. If it does not intersect anything, then that pixel is set to the background colour. If one or more intersections does occur, the one closest to the start of the ray (observer) is determined. The surface normal at the point of intersection is found and rays are cast towards each light source. If an object is hit between the intersected object and the light source then the object is in shadow from that light source at that point on its surface. If not, then the light source contributes to the colour of the pixel. Once the ray has intersected an object, a reflected ray, and possibly a refracted ray if the object is transparent, are generated. Such rays are evaluated recursively until either a ray hits no object or a specified number of levels of recursion is reached. At this point, the colour of the ray is determined and this value is then returned up the ray tree to contribute to the colour of the ray at each intersection until the final colour of the original ray is determined. This becomes the value of the pixel. Typically, for a 1K by 1K image, 5 million rays or more may be traced.
The Mandelbrot set was first described by B. B. Mandelbrot in 1980. It is calculated by iterating the Equation [2]:
where
To produce an image from this equation, one defines the region of the complex plane of interest by defining minimum and maximum x and y values. Each screen pixel co-ordinate is then mapped onto the complex plane within these bounds to form the starting value of z. There are many ways to colour the image [2]. The one preferred by the author is to iterate the equation until either the magnitude of z goes greater than two or some iteration limit is reached. A count is kept of how many iterations have been made and this count is used to define the colour of the pixel. The points actually in the Mandelbrot set (the "lake" in the centre) will be the ones that have a magnitude less than two after the maximum number of iterations. We can see here that as the maximum iteration limit is increased, we redefine the "coastline" in more detail. This goes on indefinitely, defining the "fractal" nature of this shape.
The Kamtorus [3] is quite different from the Mandelbrot set in terms of image generation. It is generated by iterating the following equations a set number of times, drawing dots, and overlaying these for various values of a parameter called orbit:
where a is a constant parameter and orbit is varied between a starting value and an ending value in specified increments. This sort of "fractal" effectively walks over a pixel grid, turning on pixels as it goes. If a pixel needs to be set which is already set, the colour of the pixel is changed, effectively counting the number of times that pixel was visited in the walk.
Since all of the image generation schemes described above require significant computation, it is obvious to look for ways to speed up this computation. An obvious approach is to use multiple complete computing elements, each consisting of a CPU, memory (possibly in the form of a cache) and some way for the processors to communicate with each other. This is known as a multi-processor or multiple-instruction, multiple-data (MIMD) machine. Using such a computer, the program is partitioned so that different pieces of the whole problem are solved on different processing elements. The processing power is raised by increasing the number of processing elements.
There are two main organisations of MIMD machines: tightly-coupled and loosely-coupled. A tightly-coupled machine is one in which the multiple processors communicate by use of a shared main memory. For this reason they are also called shared memory computers. If executing the same program in parallel, only one copy of the code need be stored, saving memory. In addition, communication between processors is also handled by the shared memory. Bus contention occurs when two or more processors require access to the bus at the same time. This increases as more processors are added. Thus, tightly-coupled computers are usually limited to around 16 processors. The other type of MIMD computer is the loosely-coupled or message-passing computer. Here, each processor has its own main memory and communicates with the other processors by passing messages through some sort of communication channel. Because there is no bus contention, such a design can be highly scalable, allowing more processing power to be provided simply by adding more processors. A disadvantage is the need to duplicate code and data in each processor's memory. There are hybrid computers which combine both the loosely- and tightly-coupled architectures together [4].
From the perspective of image generation, parallel computers offer a number of possible problems and interesting opportunities. Depending on the particular image generation method there may be a wide range of implementation schemes possible. In this section, some of the issues involved with each of the above image types will be discussed. The emphasis is placed on parallel solutions for distributed memory parallel computers. A problem common to all applications on parallel computers is that of ensuring load balance. Load balancing is ensuring that all processors are working equally hard and that small enough units of work are being done so that, at the end, all processors stop work close together timewise. This is very important. If work is divided up coarsely and one processor gets the bulk of the computation, all other processors will finish early but the total time to run the program will be determined by the one with the most to do. The running of programs with this sort of problem is usually characterised by no increase in performance as more processors are added above a base number of processors, which is often quite small.
Raytracing offers a rich variety of possibilities [5, 6]. An important characteristic of raytracing is that the calculation of the colour of each pixel is totally independent of that of any other pixel. This suggests the use of a Master-Slave architecture. In this approach, one processor - the Master - is responsible for handing out small packets of work to the Slave processors, which are all other processors available in the system. In the case of raytracing, the packets of work can be sets of pixels to calculate. An obvious unit of work is the scanline. This, however, has some problems. In some scenes, certain ranges of scanlines (for example, the sky) will have few objects and thus be speedy to calculate. This can cause load balance problems. Also the unit of work (a scan line may have 1024 to 4096 or more pixels) is too large. Single pixels are attractive, offering very fine grain, but can be too small sometimes. The best compromise seems to be small block of pixels, such as a 4x4 block. This approach works well on distributed memory computers. On shared memory computers, other solution approaches are possible.
The Mandelbrot set is similar to raytracing in that the calculation of each pixel is totally independent of any other pixel. This means that the same approach as taken for raytracing should work well. Since the computation for each pixel can vary enormously depending on it's distance from the set, the use of single pixels as the unit of work is also not a good solution here. Thus, again, small blocks of pixels, of the order of 4x4 or 8x8 seem suitable. Again, as for raytracing, the slave processes cache the pixel values for each pixel in the block, then send a message to the master processor with the results for all pixels. This sending of the result triggers the master to send a new block of work to the slave that sent the results. On shared memory computers, a different model than master-slave, such as treating all processors as workers and allowing each to determine which pixels to calculate, becomes possible. On such computers, each processor can directly write the result pixels into the frame buffer or a buffer in memory.
Figure 2
Figure 3
Kamtorus or other "orbit" type fractals create a different situation. On any of these fractal types, a sequence of execution causes a number of pixel co-ordinates to be generated. On a shared memory machine, this is not a problem as each processor can directly update the frame buffer or image buffer. This may, however, cause severe contention problems, as the amount of computation required before each update is small. On distributed memory computers, a modified version of the raytracing/Mandelbrot solution seems a likely solution. Each processor would calculate n steps, caching the resulting pixel co-ordinates in local memory. When all n steps have been taken, a packet containing a list of pixels is sent to the master, which is responsible for updating the frame buffer. Whilst this has not yet been tried by the author, it is anticipated that this approach will not be optimal. This is due to the master being overloaded both distributing work and updating pixels due to the relatively simple computations required of the workers. This area is to be further investigated.
Figures 2 through 5 show some results of running a simple raytracer on an Intel Paragon distributed memory parallel computer. Runs were made varying the scene complexity, which provides an indication of the amount of computation required per pixel, and the number of pixels in each work allocation. Work allocations varied from 1x1, 2x2, 4x4 to 8x8 pixel blocks; that is, 1, 4, 16 and 64 pixels. They show that on this particular parallel computer, this scheme of work distribution only works well for complex scenes and that reducing the amount of message traffic by allocating work in bigger blocks helps significantly where scenes are less complex, but has little effect once scene complexity grows.
Figure 4
Figure 5
Figure 6 shows some results for the Mandelbrot set on the same computer. It shows the results from four sets of runs: two with a maximum number of iterations per pixel of 256 and two with an iteration maximum of 50,000. It can be seen that with the lower iteration limit, reflecting less computation per pixel, that there is little benefit in using more than 4 CPUs and that using 2x2 work block greatly improves performance. With the higher iteration limit, we see that there is little benefit from using 2x2 work blocks but that there is now a benefit in using more CPUs. These results confirm the conclusions drawn from the above raytracer results.
Images can be produced in a number of ways. Whether this is done by painting, drawing, print making or photography, such images can, and are, accepted as art. However, the process of acceptance of a new art medium can be fairly long. Photography, for instance, is only just coming out from under the shadow of being too easy an art form. Even for photography, which is over 150 years old, this process is not fully complete. The art world as a whole is highly conservative when it comes to accepting new art media. This is especially true when the new media has associated with it a very different way of creating and working with the medium.
Photograph 1, entitled "Between two worlds" is a combination to two fractal images created using the Fractint program. The background is a Kamtorus, as described above, and the foreground, a jellyfish-like shape, is a 3D Icon. Photograph 2, entitled "Initiation" is also a combination, this time of a Mandelcloud background and another 3D Icon. The Mandelcloud used the same formula as the Mandelbrot set, but plots the orbits instead of the number of iterations to go to infinity. Both images are created by the author.
Figure 6
There can be little doubt that mathematically created images can be art, just as images produced using any other method can be. Whether any individual image is art is a matter for critical art assessment and individual aesthetics. Perhaps the key aspects are the intention of the creator of the image, the degree of manipulation involved in its creation and whether the content of the image has anything meaningful to say. Mathematically created art is perhaps unique from other forms because, due to its nature, it encourages a crossover between art and science. This can be seen in the work of people like C. Pickover.
Photograph 1
Photograph 2
Mathematically created images are certainly science. They exist as a branch of mathematics and are useful in other areas of science, especially computer graphics and parallel computing where the simplicity of the required code makes them useful benchmarks for testing the performance of new parallel computer architectures.
Mathematically created images can also be art. We can say that just as photography can be art, so can mathematically created images. Thus, mathematical image-making becomes another medium in the art world. Just as not all photographs are art, neither will all mathematical images be art - however, some will.
Mathematically Generated Images:
Art or Science
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html wjc3.
The translation was initiated by Pam Milliken on Wed Nov 20 16:31:04 EST 1996