Writeup ------- by Jeffrey Ladino ************************* * * Introduction * ************************* This document explains my quarter project for Computer Graphics COM1370 in Summer 1999. It is broken down into sections that should be read in order, but may be understood out of order also. ************************* * * Design Philosophy of This Project * ************************* The original goal of this project was to create a 2-dimensional animation of a bouncing ball. This project was to be an excercise in using many of the concepts learned in class in a program. These two goals remained unchanged throughout the implementation phase of this project. My personal design philosophy was to build up a hierarchy of classes that could be used for this project and others. The classes at the lowest level of this hierarchy implement purely mathematical concepts - matrices and vectors. More complexity, and specialization are seen when moving up this hierarchy into simple shapes, and finally complex objects. Everything from level 0 to level 2 in the hierarchy is easily reusable and applicable to many different areas. Class Hierarchy --------------- level 0 (simplest) ------------------ vector3d - 3D vectors matrix3d - 3x3 matrix class level 1 ------- transform functions in transforms.h - create matrices for common transforms like reflection, rotation, translation point2d.h - represents a point with homgenous coordinates in 2d space level 2 ------- circle2d - a circle in 2d drawn with the midpoint circle algorithm shape2d - any shape in 2d character2d - an led character in 2d level 3 ------- bb - container for a circle2d and two character2d ************************* * * Data Structures * ************************* The most important data structure to this project is the bb class. This class represents a bouncing ball. It contains a circle2d object and two character2d objects. It calls each of the lower level classes in my hierarchy as needed. Each of my classes has a consistent interface in the draw() member function. It is passed a SimpleDraw window in which to draw the object and the composite matrix transform to apply to the object before drawing. This allows me to apply any transform to an object to be drawn without side effecting the object's data. This was a VERY powerful tool that allowed me to represent objects in a way natural to me (cartesian coordinates). When it was time to draw the object, all that was required was to pass it the viewing transform. This was very helpful for P3 too. When scaling an object, I could just call that object's draw function and pass it the viewing transform times a scaling transform. This applied to every matrix operation. I could just pass in a single composite matrix of every transform I wished to apply in my call to draw. The transformed object would be drawn on the screen without changing my original object! ************************* * * Algorithms Used * ************************* - ball collision with other balls When ball A collides with ball B, the following happens. The code can be seen in bb.cpp in the collide_with() member function. 1. get the vector from the center of ball A to the center of ball B and normalize it 2. project the velocity of ball A onto the vector from step 1 3. velocity of ball A = velocity of ball A perpendicular to vector from step 1 4. repeat steps 1-3 on ball B 5. ball B velocity += step 2 result on ball A 6. ball A velocity += step 2 result on ball B - ball collision with the walls The ball's velocity is stored as a vector. This makes reacting to collisions with walls simple. The code can be seen in bb.cpp in the move() member function. If a ball hits the top or bottom walls, the Y coordinate of its velocity is simply negated. If a ball hits the left or right side walls, the X coordinate of its velocity is negated. - detection of overlapping balls at the beginning Since my balls are assigned to a random starting position, some balls overlap others at the start. Before animating them I detect overlaps with a recursive function. This operation has a high computational complexity given N balls, but fortunately N is limited to an upper bound of 99. This operation can be seen in the fix_overlaps() function in main.cpp ************************* * * Techniques from class used * ************************* *Projection - when 2 balls collide. Their velocites are broken down into components using projection -> see bb.cpp, bb::collide_with() *Rotation - the balls rotate, based on a random angular velocity *Translation - the balls translate across the screen *Matrix by Vector multiply - used in each classes draw() function -> see circle2d.cpp shape2d.cpp draw() member functions *Matrix pipeline - a viewing transform matrix is created in main.cpp to map from world coordinates to window coordinates -> see main.cpp matrix3d M *Reflection over x-axis - this matrix is part of the viewing matrix in main.cpp *Homogenous Coordinates - this allows me to use a matrices to represent every transform and allows a composite matrix to be the product of many transforming matrices *Matrix by Matrix multiply - this is used to create a composite matrix that will apply many transforms at once to a single point ************************* * * Expected Behavior of Bounce * ************************* bounce is the executable name of my project. It can be run as follows to get a printed usage funcion ./bounce -h When you run bounce with the options .bounce -n [-r ] [-w ] [-h] you can expect to see balls. Each ball has a radius of and the windowSize will be set to x . The default for is 30 and the default for is 600. See the Readme file for some good commandline options to pass to bounce. CAUTION: CCS systems have an executable named bounce in the path of most users. Be sure to type ./bounce when in my project directory to access my excutable named bounce. ************************* * * Known Defects * ************************* - balls sometimes stick to each other When running with many balls for long periods of time, 2 or 3 balls sometimes stick together for short periods. - memory leaks Some of the objects that I allocate do not get deleted. This can fill up the free store with unused, undeleted objects. This will cause this project to crash if run for long periods of time. The length of time until crashing varies depending on the memory in the machine. On my machine with 64MB RAM, it takes over 90 seconds to crash. ************************* * * Changes for future versions * ************************* - add double buffering Draw each object to a buffer in memory representing the screen, instead of drawing objects directly to the screen. Once all objects have been drawn to the memory buffer, copy this buffer to the display device to be drawn. OpenGL implements this functionality. - make 3d Use this project as a basis for 3d balls and collisions. ************************* * * Conclusion * ************************* This project has been a learning experience in computer graphics and in software development. It was a good excercise for me to develop many separate classes in separate files. This made building the project and isolating errors much easier than with a monolithic project. The concepts that I programmed into this projects are all concepts that were learned from my Computer Graphics class or my Linear algebra class. Designing, programming, and documenting this project has helped me to assimilate all of the core concepts that I have learned in my Computer Graphics class in addition to helping me become a better programmer.