Explanation!
The Concept
For the Rutgers College General Honors Program I had to complete a Junior Project. One of the options that the project could be was an independent study in your major. I decided to choose this, and worked with Doug DeCarlo (his webpage), a professor in Rutgers' Computer Science Department. His specialty is computer graphics and their implementation. He is a member of the
VILLAGE at Rutgers.The project we decided on concerns the artist
Wassily Kandinsky. He is known for creating a series of paintings using only very basic geometric shapes. These abstract paintings seem to give the viewer's eye paths to follow through them. With this program, I hoped to recreate this effect on a computer screen. That is, create a program that would produce randomly made Kandinsky-esque paintings that would direct your eye along a certain path.
To accomplish this I would first have to come up with a path and then a grammar for drawing shapes on the path at random places. I started the project by reading various essays and chapters in books about grammars and how to create graphics from them. I also read through Kandinsky's book, Point and Line to Plane, as well as a book entitled Digital Mantras which had some plates of Kandinsky's work in it. My grammar consists of four basic types: triangle, curve, circle, and lines - See Appendix A. Each type can be drawn on different levels recursively. That is, a triangle can be replaced by three triangles, each one of those can be replaced with three more, etc... To achieve this effect efficiently I needed to utilize transformation matrices: rotational, translational, and scaling.
I decided to program this project in C on my PC using the Allegro library. The Allegro library is a shareware library that has many helpful functions for drawing to the screen and even some matrix manipulation routines. Once I had read about and understood the concepts behind the routines included in the library, I was able to make them work. As a practice program to get used to the transformation matrices, I coded a part of the final program that creates Koch snowflakes with triangles - See Appendix B. After I got that working I felt I could tackle the main project.
The Curves
So, the first question, what type of path should I create the picture based on? I chose to use a Bézier spline to create a curved path. I wanted the curves to be randomly chosen, but when they were completely random most of the curves did not look nice - See Appendix B. The four control points used to draw the curve had to be constrained somehow. I first tried to pick four points, one from each quadrant on the screen. While that did improve the curves somewhat, they were not yet perfect. The middle points could appear too close to each other and make the curve a line or all the points could be close together and make the curve too small. I wanted the curve to take up a good portion of the screen so the subsequent picture would look nice. I finally scrapped the quadrant idea and started choosing points with a hard coded grammar. I choose the first point randomly, than I pick random points until I get one that is a certain distance along the x-axis and along the y-axis from the original point. The x and y distances are randomly chosen within their constraints. This second point is suitably far enough from the first and becomes the end point of the curve.
I also constrained the x value for the first point to an extent. I found when I let it run totally wild all over the screen I did not get enough good curves so I used another random number to force it to stay in the first third of the screen 6/10ths of the time. With the beginning point chosen I start a "for loop" that goes until 10000 or until it finds a properly constrained end point. That is, where the new x is more than 340 away from the old x and the new y is more than 210 away from the old y (these numbers are based on the 640x480 resolution I used). I perform similar constraints on the two middle points, keeping them certain distances from each other and from the end points. The constraints were preconceived but the timeout limit of 10000 was basic trial and error. I tried 1000, then 5000, then 10000. The curves 10000 produced looked very well - See Appendix B. When the middle points timeout I get U shaped and ribbon shaped curves that add a nice touch to the plain but sturdy S curves. There is a fine line between randomly generating curves, some which are bad, and randomly generating perfect S curves each time. I did not want to take all the randomness out of the curves or the pictures would get boring after awhile.
The Types
So, now that I had my curves I needed to put the shape types on them in some organized manner. I started by working out a curvness variable for any point on the curve. I did this by using three points: the point I wanted the curvness for and a point on either side. I first took the points directly to each side of the center point, but found, of course, that the curvness was then always straight. By taking points a certain tolerance away from the center point I received better results. With my points, I then took the dot product of the two vectors going from the center point to either side and divided it by the product of their magnitudes. The arcos of this number gave me a curvness variable in radians. I then converted that number to the 256-degrees-to-a-circle format the Allegro library likes. A curvness of 128 became perfectly straight and I experimented to find what would constitute real curvy. I found anything under 120 gave good results when declared curvy.
I then needed to get the tangent to the curve at any point and from that retrieve an angle off the horizontal I could use for my rotational matrices. I did this by taking the arc tan of the change in y over the change in x. After achieving this I coded up a single triangle routine and tested it all along the curve. After perfecting my method and centering the triangle over the point I moved on to spacing the points along the curve. They needed to be random but still spaced nicely. I first set down in code that the first and last points would have objects on them. I then chose points randomly along it, each between 10 and 14 points from the last. This method seemed to work the best.
I used the knowledge gained from the recursion on the Koch snowflake to get the recursion on the triangles working. The one adjustment to the outline of the snowflake included taking the curvness variable into effect. This was accomplished with an if-statement changing the two rear forward facing triangles into one rear backward facing triangle if the curvness was high (straighter) and vice versa if the curvness was lower (curvy). Either way I still drew the fore forward facing triangle - See Appendix A.
I had drawn a simple curved/horn shape as a bitmap and for the curve-shape part of the grammar I loaded it in. Since the bitmap would be drawn onto the screen according to a single point, the transformational matrices would only accomplish translations, not rotations or scaling. I made the curve function accept angle and scaling variables as well as the matrix, the recursion level, and the curvness variables. This way, whatever rotations or scaling I did could be included as separate variables to be used when drawing the curve bitmap to the screen. I also had to make adjustments to the (x, y) coordinate I drew the bitmap at; moving it halfway off its center in each direction, taking into account the scaling variable. The curvness variable decided whether two curves would be drawn interlocking (for straight areas) or piggy-backed (for curved areas) - See Appendix A.
The half-circle type was the same as the curve-type, in that it needed a separate angle and scaling variable. As I decided not to worry about curvness for half circles, I disregarded that variable. The half-circle is drawn by making an arc from the angle (ang - 64) - the equivalent of 90 degrees in the real world - to the angle (ang + 64). The recursion is accomplished much like the three triangles before: three half circles replace the one, not unlike the scales on a fish - See Appendix A.
The lines-type does not make use of recursion. It simply picks one of two different choices. It can draw two angled lines of various lengths pointing along the curve or it can draw a series of four lines in close proximity forming a wedge shape. In many of the Kandinsky paintings I saw these types of formations and they definitely add a certain character to the finished piece. Here the transformation matrix becomes all-powerful and is used on each endpoint of every line drawn.
The Filler
At this point the only objects drawn on the screen are specifically set along the curve. The screen needed to be filled with other random objects to take away from the obviousness of the curve and balance the whole picture. I chose five different types of filler: curves, snow, circles, arcs, and dots. The first four I chose from equally when I needed a filler type. For each picture, three times the filler variable of filler types are drawn. Each one of those types is chosen from the above four choices. The dots type comes in at the end. When enabled, it randomly draws one-pixel dots across the screen. This serves to distribute the eye's glance away from the curve and balance the picture so the traveling of the path becomes more unconscious than conscious.
The curves filler type basically draws a random curve bitmap somewhere on the screen. It has a random scalar, angle, and position. The snow type draws a Koch snowflake of a severely reduced size at a random position on the screen. The circles type creates a blob of circles with the main circle surrounded by satellite circles. The positions for the satellite circles are picked from the 264 degrees and from a scaled down version of the main circle's radius. The arcs type just draws a random arc somewhere on the screen. None of these fillers are put on the screen according to a set system. To really begin to achieve Kandinsky caliber filler, I would have to have some type of monitoring function telling what parts of the screen need what type of filler. While not as good as that function would make it, I found the dots really helped to balance the picture.
The Interface
The interface to the Kandinsky Wonder Program tries to be a happy medium of technical fine-tuning and user pleasure - See Appendix C. The snowflake generator exists as a separate entity because it was really only a practice for using transformation matrices. However, it can produce very nice designs and pictures that can subsequently be captured. The second option, seeing a Kandinsky-esque picture, consists of the main body of the program and not only provides the picture but a host of controls that can be changed by the user. These range from recursion depth to amount of filler to a beta version of locking the seed for the random number generator - See Appendix C.
The third option from the main menu provides a slightly more interactive aspect to the picture itself without regard to the controls that made it. It places a picture on the screen and asks the user to click where he/she thinks an end of the curve may be. This is just a fun little function to make an interactive use out of the picture produced. The score is calculated by taking the smaller distance between the point clicked and the two end points, and subtracting that from 500. Perhaps in the future a stricter game routine will be implemented along with a high score list. Perhaps.
Both the picture and snowflake functions have an option to capture the screen. This entails having the user enter a number for the pic#.bmp filename the capture will be saved under. After they pick (there is no checking for existing files or anything like that) the screen, without the menu at the bottom, is saved to that file. This is especially nice for when one is trying to get screen captures for appendices or web pages.
What I Learned
I am a computer scientist who loves recursion. I uphold the theory that "to iterate is human, to recurse... divine." This project has greatly enforced that belief. It has shown the power given by recursion, and indeed needed, for use in graphics applications. The technical papers and books that I read concerning grammars and producing pictures from them all use recursion. Whether making a tree or a snowflake, recursion will be used. Along with this came a new understanding of grammars. This project coincided with the computer course Principles of Programming Languages I was taking which also discussed grammars and their rules. The course and the project worked nicely together to provide me with a hands-on understanding of the material discussed in each.
On a lighter side, while testing out this program I learned that people like, and are even amazed, when you say something is "randomly generated." They also believe that there should be a Koch snowflake screensaver. After looking at many of the curves and pictures related to them, users would quickly find the curve by looking for tell tale signs of the program's grammar instead of letting their eyes find it. To try to negate this I added the dots. These serve to spread out the overall vision of the picture and make it easier for your eye to wander. Most if not all of the constraints I attempted to impose on the creation of these pictures came from an aspired to aesthetic of what looks "good." Where I have failed, Kandinsky succeeded; creating paintings with true purpose and design. My attempts may not live up to the original, but they are a good start and an enjoyable challenge.
© 2000 Shawn Patton