 |
 |
 |
Project Write-up
| General Goals |
When working on this project we set a few generalized and more abstract goals for ourselves. We wanted to reach a certain point in development but the fluxuation in the amount of time available to spend working on the project forced us to allow a certain level of vagueness in our goals.
- real-time interface
- world rendering
- collision detection
- physics and frame rate control
- Entity Rendering and Character Structure
| Real Time Interface |
Our ideal interface design was one that would use input from the mouse and keyboard and that would maximize control over the environment as well as provide emersion. Arrow keys would control X and Z axes, the mouse would control orientation, while the Y and H keys would control the Y axis. Additional design elements included camera angle, controlled by PG_UP and PG_DN, and camera zoom/dolly, controlled by the / and + keys.
Our ideal interface design was basically realized. We experimented with different orientation schemes. The alternate orientation schemes uses the 7 and 9 keys on the number pad to control camera rotation. The C key toggles through orientation schemes.
| Keyboard Functionality |
Camera Controls |
|
|
PG_UP, PG_DN |
Camera Rotation |
|
+, - |
Camera Zoom/Dolly |
Orientation |
|
|
C |
Changes Orientation Scheme (Scheme 1 is default) |
|
Mouse |
Camera rotation in scheme 1 |
| 7,9 | Camera rotation in scheme 2 |
Movement |
|
|
Up, Down Arrow |
Forward , Back (depends on orientation) |
|
Right Left Arrow |
Left, Right (depends on orientation) |
|
Y, H |
Up, Down (Y axis) |
Graphics Detail |
|
|
F |
toggles filter: mipmap, etc. |
|
B |
toggles Alpha blend |
|
L |
toggles Lights |
We developed on the Windows API platform so Glut was not used for the keyboard callbacks, it was all Windows callbacks.
| World Rendering |
| Overview and Outside Source Explanation |
Our needs for an
environment went beyond loading in a model.
We needed a rendered environment but it was also important to have
the data in appropriate structures so as to compliment our collision detection
module. It was important to have
the vertices stored as ‘triangles’ with texture information intact all in
the same structure. We decided
to use a commercially available environment creating tool called WorldCraft
that allowed visual creation of an environment and exported the data in ASCII
format.
| File Formats and Data Structures |
The ASCII data file generated by Worldcraft had all of the information we needed and we could reformat the ASCII file easily in order to use the data in our program however we wanted. The Worldcraft ASCII file format was a .map file. Our reformat was .nmf. The files included the vertex data which we read into a tiered structure with vertices, triangles, and then sectors. The sectors contain triangles which are made up of vertices. Each tier is indexed for easy access.
| Rendering and Texture Information |
Rendering the map involves a loop that grabs the information of each triangle and then sends it to be rendered. The texture information of each triangle is stored as a number which corresponds to one of textures that has been loaded previously
| Collision |
Collision detection was a large problem that we attempted to solve with various algorithms. Our world rendering scheme helped to narrowing down the possible ways of doing real time 3D collision detection for our engine. Since our world rendering scheme uses triangles, we already had the vertices of the world triangles available to us.
| Ray Tracing Algorithm |
We initially attempted to implement a ray tracing algorithm developed by Tomas Möller and Ben Trumbore (http://www.acm.org/jgt/papers/MollerTrumbore97/). We considered this algorithm, although it was meant to be used for lights and such, because of the high efficiency and the relevance to what we were trying to accomplish. One advantage of this method is that the plane equation need not be computed on the fly nor be stored, which can amount to significant memory savings for triangle meshes. We has trouble, unfortunately, implementing the scheme into out structure so we explored other solutions.
| Sphere - Box Intersection Algorithm |
Another algorithm we explored was one that detected a collision between a sphere and a box. Calculating a box from the triangle vertices and putting the sphere around the character was the idea here. The algorithm found collisions by using trigonometry and calculus and vertices of the object involved. We discarded this algorithm for a more accurate and efficient one.
| |Lame| Collision Detection |
We found a collision detection scheme that is based around finding the plane that a given polygon (in our case triangles) lies on and detects if a point crosses that plane. The author of the article labeled it “lame” collision because it only detected plane intersections. Getting this algorithm to work was not quite as difficult. We quickly got the plane intersection to work. Narrowing the detection down to just the triangle and not the entire plane took a bit more work, though. To do this we must calculate the exact intersection point and then determine if that point was on the triangle. Some of the material we used in this part of the collision detection module was developed by Evaggelia-Aggeliki Karabassi, Georgios Papaioannou, Theoharis Theoharis, and Alexander Boehm in their Intersection test for collision detection in particle systems paper (http://www.acm.org/jgt/papers/KarabassiEtAl99/). This is our final scheme for the collision detection module.
In each of the algorithms, we wanted to be able to send the collision detection module the current physics of the character and be able to receive physics back from it. So I if the physics sent to the module would cause a collision the module would detect that and send back the appropriate physics. We did testing by loading up a single triangle map and testing the planes.
| Physics and Frame Rate |
In order for our real time environment to flow and remain being drawn in real time, we had to come up with a way to regulate frame rate and make it inversely proportionate to the screen refresh rate. We wanted a relatively stable frame rate and we wanted it at least 20fps. We also wanted constants with regard to physics.
| Physics |
If an object is moving at a certain speed, we don’t want it to slow down because the refresh rate hits a snag. We gave each object a physics module which contains velocity, acceleration, etc. When these are set, the stay constant, only the frame rate and refresh rate should fluxuate.
| Frame Rate Control |
In order to regulate the frame rate, we calculated the time delta of the refresh rate. We then used the time delta to regulate the frames so the object would move the same distance in the same period of time. So the longer between screen refreshes, the slower the frame rate, but the velocity of the object would stay the same. We had to do this for each of the aspects of the movement animation. We always want stable and predictable movement, whether the character is moving or rotating, or even when just the camera is adjusting, rotating, or zooming.
| Entity Rendering and Character Structure |
Decide
on Data Generation Format
After examining several formats of 3D geometry files it was decided
that the 3D Studio MAX ASCII file would be most appropriate for generating
characters and their animation. Vertices,
texture coordinates, normals, colors, geometry hierarchy, pivot points, and key frames
were all defined in this format.
Import
Geometry
It was decided early on that all of the character geometry would be
segmented. This means that each mobile part of the character would be
comprised of separated geometry. For example, an arm would consist of an upper
arm part, a forearm part, and a hand part all defined by separate pieces of
geometry. So, the first task was
to bring in a single part. After parsing the data, there are several ways to
display the geometric object on the screen.
The method which appears to have the least amount of overhead is to
store and display the geometry from an interleaved array.
An interleaved array is a data structure which holds an array of
oscillating data (i.e.. vertex, vertex, vertex, normal, normal, normal,
etc...). After it is stored, the object can then be displayed in two simple
function calls. glInterleavedArrays()
and glDrawArrays().
| Pseudo Code - General Drawing Scheme |
|
|
A problem occurred when importing geometry that had been mirrored in
the modeler. Vertices appeared reversed and the children of mirrored
objects were found to have
negative rotations relative to their rotations provided in the data file.
Build
Animation Hierarchy
After routines were developed to import the geometry, a routine was
needed to import multiple objects and organize them into a hierarchy.
Each object in max is allowed a parent object.
This creates a kinematics tree for translations, rotations, and
scaling. The solution for representing this in the code was to create a
function that would recurse through the hierarchy until a terminal node was
hit and then pop back to a parent node with remaining children.
Upon each instance of the function, all matrix transformations are
pushed onto the transformation stack and when the recursion ends, all
transformations are popped off.
| Pseudo Code - Recursive Tree Drawing Scheme |
|
void DrawCharacterTree(tData data) |
| Character Tree Hierarchy | ||
|
Store/Retrieve
Entities
Early on it was decided to store all of each entity’s
attributes in a binary file. As
the program stands, it can only store one entity in a file, but further
development would allow for any number of entities to be stored in an indexed
format and retrieved at random with little overhead.
Formalize
an Animation Routine
Once key frames were parsed out of the data file, the task of interpreting
them became the primary goal. Position
key frames were relatively trivial to interpret.
However, rotation key frames were quite a task to incorporate. This was
the portion of the code which consumed the most time.
Several algorithms were attempted to interpret rotation key frames.
3D Studio MAX stores rotation data in a series of summation rotations.
For instance, if an object were to rotate 360 degrees it’s key frames
could be composed of 4, 90 degree rotations.
The first algorithm attempted was to convert the summation rotations
into absolute rotations. This
involved pre-summing the angles of rotation.
After implementing this algorithm it was discovered that none of the
rotational angles provided from the MAX file were comprised of negative
angles, thus all rotations direction were determined by their axis.
After attempting several unsound methods of standardizing the axis and
changing the sign of the angle failed, another algorithm was attempted.
The current algorithm works by concurrently performing the rotations as
they originally appear in MAX. This
requires the dynamic allocation of an array with a slot for each key frame.
As a key frame is approached, the appropriate slot in the array
linearly interpolates towards that key frame.
Eventually the array reads exactly like the list of key frames. When the animation sequence wraps back to the first key frame,
all but the first key frame slots count down to zero, and the first key frame
interpolates to the first key frame of the current animation sequence (if the
animation sequence hasn’t changed then the first slot stays the same).
This algorithm has a significant flaw:
when the sequence wraps, the rotations unwind rather than moving in an
appropriate direction toward the first key frame.
If the countdown is avoided, popping occurs. A
solution to this problem was not implemented before this release of the
engine.
| Pseudo Code - Current Rotation Scheme |
|
void DrawCharacterTree(tData data) |
Scale key frames were never imported due to the problem encountered
with rotation key frames.
| Ideal Animation Sequence | ||
|
Import
Materials
The task of importing materials (colors and textures) is a significant
task. Ambient, diffuse, and specular
colors were easily parsed and incorporated, but textures were not attempted
at all. Most time was devoted to interpreting key frames. Recently
it has been discovered that, on some machines, the materials are inaccurately
represented. The materials look too close to the white end of the spectrum.
This problem has not yet been isolated. A possible culprit may be that the
actual colors are being modified.
| Screenshots | ||||
|
Effects
Special effects are the neat little perks in computer graphics. Our priority level for effects were not quite as high as the priority levels for other topics but we managed to have some effects .
Particles
The particles we used were an attempt at a lightning effect. Partially randomized triangle strips constantly redrawn in differently.
Sounds
We also added sound that are activated by the mouse buttons. We used built in windows API sound to play a .wav files. The .wav files were created by mixing some recorded sounds with some fuzz for the lightning sound effect.
Conclusion
This was an experiment in building a real-time, interactive, 3D engine.
Our engine is still far from complete. While developing, we learned a lot about how an interactive environment’s components worked together and the problems that arise. Some of the problems we encountered were similar to problems encountered by professional 3D engine developers. Data formatting, storage issues, data interpretation, and mathematical complexity were all deceivingly significant, time consuming issues in the development cycle. The scope of the project and the size and variation of the data made these aspects more complex than was initially expected. We learned a large amount by researching algorithms and trying to optimize aspects of our code. Essentially this project was about learning the structure of an interactive 3D program and about elements of OpenGL we have previously not used. Our learning experience was valuable and we do plan to complete our engine in the future. We found that trying to create a development cycle at the beginning was difficult because of the ever-changing aspects of our engine. It was also difficult to keep our expanding program modular enough to allow for simplified additions to the engine. In consequence, modules needed merging which sometimes caused logical conflicts. We still plan on perfecting our exiting code and adding more animation features, special effects, more elaborate data storage, perfected collision detection, and eventually developing content for a game using our engine.