Huh? What’s that? “Time off for Christmas”… No idea what it means!

Yep, that’s right.
While everyone else is probably busy lapping up rice pudding or practicing their vocal skills for the big day, we are still busy on our project… Or at least still messing around with it.

Yesterday we implemented bomb, among several other things, and today came the vortex. These 2 aren’t actually meant as being part of the physics system per se, but rather as tools or toys to play around with to see how the rigid body you are building will react. Unfortunately, I don’t think we have a video of the PhysicsBomb (as we imaginatively named it), but we do have a video of the Vortex. It’s still work in progress so there are still some bugs as you may be able to see, but even so, it does look rather nice.

It’s actually quite annoying to be this far with the project now and have so many (seemingly) great, fun ideas but knowing we soon have to end the developement and do the report. We still have a few bugs here and there to fix and some small features to implement but overall we’re very close to finishing. I know I said that last time as well, but the more you work, the more ideas for new work you get

Anyways…
I and the rest of the group wish you all a merry christmas, and we leave you (for now) with a video.
And, as tradition would have it, it once again comes in both a good direct download version and a poor youtube version. The download version is ~11mb. Enjoy 2:30 minutes of Vortex testing

http://www.daimi.au.dk/~u051394/vortex.avi

Video postponed

So we started making the video, but ran into some bugs

 So after fixing the bugs, and strangly enough finding new features to implement, and then implement them, we ended up with no video.

 But we have then just made a small preview of what to come

http://www.daimi.au.dk/~vester/waterBridge.AVI

and again the bad quality youtube stuff (hint: get the ones we link to, you can read the GUI)

Coming into the homestretch

Where’s the new video? It’s been a whole week!

Well, truth is we actually coded this week rather than make videos, so we got quite far with the project.
So far actually, that we  should reach the end of our ‘to do’ list tomorrow and thus actually be finished with coding.
Expect an extensive video demonstration once we have the final code, but for now we have to ask you  for just a little more time.

We now face the same challenge many large game developers also face; not knowing how to compile our code in a way that is executable. . .

That is all for now, but soon everything will be revealed. Stay tuned.

A few of our many features

Since the last video a lot of things have been changed so another video was due. However I’m apparently not as good with video encoding as Mikkel
Unfortunately the cursor is not as visible as I had thought so I’ll briefly explain here what to look for.

• Endless grids in the orthogonal viewports with an arrow pointing back to the center of the scene.
• Easy menu buttons to select, deselect, copy and delete.
• Click and drag selectioning.
• Dynamic menues that change depending on the context and can show new constraint types with all their parameters automatically.

http://www.daimi.au.dk/~u051394/features.avi

Again, you’ll get a youtube version, though this of course is not in a desirable quality.

More updates will hopefully follow soon.

Where are we?

Just a little showoff of what we can do now, and how great our project is

http://www.daimi.au.dk/~vester/bridge.avi

The file is in XviD format, and roughly 10 mb.

Here we show how to make a ridgid body for a bridge, and map it to a model…

And a youtube, in worse quality

GUI

We have had alot of troubles finding a GUI that worked with our project and OE. We were trying Guichan in the beginning. We never got Guichan to load a font though, resulting in a very boring GUI, of just one color.

After the midway showoff, we decided to try CEGUI the soundeditor guys used. They seemed not to have the troubles we had, and after talking with them we implementet it in our project. That resultet in alot of other problems, but now with text. Most of our problems comes from the fact that we have more than one viewport, and we load modules through a statehandler.

We found a lightweight gui called AntTweakBar. This one took 30 minutes to get into cmake, and draw out first gui.. Nice.. It’s wery simple to setup, and has alot of nice features to tweak values, which is exactly what we want.
Using it as a normal static GUI brought us into editing the library. In our new version we can pin a bar, so it cant be moved or resized, we can specify one bar to always be behind, option user not to be able to resize any window. Ofcource we also changed the graphics so icons not in used, wasen’t drawed.
These changes will be sent to the library creator when we are done with the project, so others can enjoy these new features.

We still have some things to change in the library, when we have selected more than one particle, it shouldn’t write a x value, if they arent exactly alike. We’re also trying to make a new option to label a variable (ie. if an int is 1, we can write “on”).

The last week we have used most of our time to map all our features to the gui, and we almost have them all there, meaning we soon can get back to work on the features of the actual editor. 

Mouse selection in a 3d environment.

One of the things we were very aware of from the beginning was how to handle manipulation of a 3d environment using only 2d input.
After some extrensive searching on the internet for keywords we thought were describing of what we wanted (which it turned out they weren’t) we came across a site with a running demo and source code that we then spent an hour or two dissecting the code and then started implementing a basic selection tool for our editor.
 
/*** Find the screen coordinates and the z-buffer value.
* for the pixel drawn at the given position
*
* @param position The position we wish to find screen coordinates for.
*/
Vector<3,double> IEditor::ProjectToScreen(Vector<3,float> position) {
       //Needs to retrieve OpenGL transformation matrices before projection
       double modelMatrix[16];
       double projMatrix[16];
       int viewport[4]; 
       Vector<3,double> result = Vector<3,double>();
       glGetIntegerv(GL_VIEWPORT, viewport);
       glGetDoublev(GL_MODELVIEW_MATRIX, modelMatrix);
       glGetDoublev(GL_PROJECTION_MATRIX, projMatrix);
       gluProject(position[0],position[1],position[2],
              modelMatrix, projMatrix,viewport,
              &result[0],&result[1],&result[2]);
       result[0] = result[0] – viewport[0];
       result[1] = result[1] – viewport[1];
       return result;
}

This link has the basic info on the gluProject function which takes care of all the complicated stuff.
Here’s how the implementation looks in our project: As this is a general function for mouse code and not limited to the context of rigid bodies we’ve placed it in the general editor class. The 3 arrays are needed just to store information about the current state of the scene and as such do not need to be fully understood. We tell gluProject an (x,y,z) coordinate in our worldspace that we wish to find the screen coordinates for (the parameter “position” here), feed it the 3 arrays and give the address of the variables where the result will be stored. The change to result[0] and [1] are to find the local coordinates as we use more than one viewport. One thing to remember when mapping this to th mouse though is that while the mouse coordinates have the origin set in the upper left corner, OpenGL uses the lower left corner. result[2] is used to store the z-buffer value of the point and can therefore be used to determine which object is closest, but is generally not needed. There is a very similar funtion for finding world space coordinates from a screen coordinate – gluUnProject. For an in depth article on glUnProject see NeHe article 13.

Topic for the second quarter

Rigid body editor (“Rigiditor“)

Disclaimer: We will start out with the most fundamental elements of the project, and then – time permitting – build additional features on top of that. We’ll try to make sure we have a working project early on, so that we don’t risk ending up without a project if we run of out time in the end. Keeping that in mind, the following discusses the optimal implementation of the project.

Project description
In the second part of the course we want to create a rigid body editor, and implement functionality to load and use the created rigid bodies.

In the editor it should be possible to place particles interactively, and bind them together with constraints. So you could place a particle, extend it to a stick and extend the stick to a rigid body. It should also be possible to manipulate the positions and properties of already placed particles. The editor will have multiple different views, for the user to be able to see from different perspectives.

The graphical user interface will allow for the particles and constraints to be enriched with special properties, such as constraint inequality, dynamically changing constraint rest length, altering the mass of particles and adding magnetic properties. Properties such as constraint inequality will be useful for avoiding rigid bodies collapsing if creating a pin joint or hinges. If should also be possible to use scripts for changing constraint rest length or to handle special events such as collisions (ie. make the rigid body deform, or trigger an explosion).

When you want to test if the created rigid body has the desired properties in a real environment, it should be possible to “run” a demonstration level where the rigid body will react according to the physical evironment and the internal constraints. It should be possible to add forces to (chosen) particles in order to test how the rigid body handles. After the test run is completed, the user will be returned to the rigid body creation interface and will be able to make changes based on the experiences from the test.

The user will be able to export the rigid body to a file, and load that file with a custom file loading module. The populated rigid body data structures will then be available for the user, and can be used in whatever context he wishes. He could for instance construct a bone skeleton to be used for bone animation, or a tetrahedon to be used to simulating debris in a particle system simulation of an explosion. The rigid body will still have the properties set up in the editor, and will thus behave as desired.

Why this project
We’ve chosen this topic because we’ve been quite fascinated by the ease, expressiveness and possibilities of rigid body systems. This is highly thanks to the brilliant article by Thomas Jacobsen, and to all our work and experinces with the system.
We think of this project as feasible for the time available, but still a highly general and extremely useful addition to a huge variaty of game development efforts.

Features (Listed in order of importance, and thus expected order of implementation)

• A working bare-bones rigid body editor
• Functionality to save and load rigid bodies
• Multiple views in the editor
• Physics (collision with statics)
• GUI in the editor
• Additional properties for particles and constraints
• Selection of particles with mouse
• Scripting
• Collision between rigid bodies
• Collision with self

Possible problems

• Labelling of particles:
  We need some way for the end user of the rigid body to be able map something (geometry or other) to certain rigid body particles, and we thus need some way of referring to the particles we need. We discussed this at great length, and decided that being able to label particles was the most feasible solution.
• Orientation of particles:
  In order to use the particles for things like skeleton animation, we need an orientation for each particle in addition of the position. Otherwise we’re unable to determine which way an albow and hand are rotated in respect to each other.

References

• Advanced Character Physics (http://www.teknikus.dk/tj/gdc2001.htm)
• Rigid bodies (http://www.physics.georgetown.edu/~jkf/class_mech/rigidbody.ps)
• Motion with constraints, constrained dynamics, particle dynamics (http://www.cs.cmu.edu/~baraff/sigcourse)
• Techniques for Real-Time Rigid Body Simulation (http://cs.brown.edu/research/pubs/theses/ugrad/2003/ktegan.pdf)
• Nonconvex Rigid Bodies with Stacking (non-real-time)(http://graphics.stanford.edu/papers/rigid_bodies-sig03/)
• Rigid Body (http://en.wikipedia.org/wiki/Rigid_body)
• Rigid Body Collisions (http://www.myphysicslab.com/collision.html)
• Fast Frictional Dynamics For Rigid Bodies (http://www.research.rutgers.edu/~kaufman/ffdfrb.html)
• Dynamic Simulation of non-penetrating Flexible Bodies (http://www.cs.cmu.edu/~baraff/papers/sig92.pdf)
• Physically Based Modeling
  http://www.cs.cmu.edu/~baraff/sigcourse/index.htm

Assignment, Week 6

CarMoveEventHandler:
Our CarMoveEventHandler has the responsibility to move our cars around on the track. In order for this to work, we need to know a RigidBox, a SDLInput for keyboard control and last the waypoint class to create waypoints at runtime. This headerfile is a module which is tick-dependent since we need to move independently of the cpu. Since we include the IModule, we need to implement the Process method, which is called at every tick. When a button is pressed, forces are added to the corresponding particles in the rigidbox. In particular, the up arrow adds a forward directional force to all particles. The back arrow does the same but at half the force. When we press left and right we add a sideways force to the forward left and right pairs of particles. When we press enter, we reset the cars position. This is done for debugging purposes, or in the case where the car crashes.

Changes to the GameFactory class:
In the GameFactory class, we’ve added a followcamera and a interpolated viewing volume. These changes has made a great impact on how the presentation is at present. An example is when we reset our car’s position the the start, the followcamera moves smoothly towards the car from where we reset it. If we do not use the interpolated viewingvolume, we would simply set the position the the car instead of moving to it.

Waypoints:
We’ve made a new class named Waypoints, that has the responsibility to create, delete and to push and pop waypoints to and from a deque we have created.
We use a input/output stream to save and load waypoints from file in our sourcefolder. It is possible to save and load at runtime by using our CarMoveEventhandler class. We have mapped the insert, home, delete and end buttons to waypointcontrol. The set of waypoints that we use for the AI was made by taking our cetatta for a ride, and then place waypoints one at a time while we were hovering through the track.

AI:
Given a dequeue of waypoints and the rigidbox of a vehicle, as described earlier, an AI controls the vehicle as a regular movement handler would, based on certain constraints. The AI class generates a vertical plane that includes the position of the vehicle and the position of the “current” waypoint. This “current” waypoint is set either when we construct the AI (but not in the constructor), or when we arrive at (or near) our previous current waypoint. The first waypoint is set in the SetWaypoint method, which is called from the GameFactory class. We’ve set the distance that defines “nearness” to waypoints at 150 units, which mean that even if a waypoint is passed at the very edge of the road, it still counts as having been “visited”. When a waypoint is visited in this way, it is popped from the dequeue and the next waypoint is selected as current.

The generated plane is compared to a point described by the position of the car plus a direction vector of a certain length. In this way we can see whether we are pointing to the left or right of the plane, and turn the car accordingly. The vehicle is constantly moving forward whether it is turning or not. We’ve set the optional parameter epsilon for the ComparePointPlane to 0.01 so that the car does not constantly turn back and forth across the line (described by the plane) between itself and the waypoint, but spends at least some time driving straight forwards.

Assignment, Week 5

Hybrid Quad+BSP tree builder
We wish to merge capabilities of BSP trees and Quad trees in a single tree structure, ie. first dividing our scene into quads to quick narrow the scope of faces we examine during collision detection according to our position and second divide those quad nodes into bsp trees to check collision against.
Rather than modifyingour existing classes we create a new class, a HybridBuilder, to handle this responsiblility. This also ensures better encapsulation and makes it easy to change back and forth between tree types on demand. Our HybridBuilder takes an ISceneNode as a parameter and constructs a quad tree from it. It then uses the visitor pattern to travel through the quad tree and saves all the geometry nodes it finds in a dynamic vector. When the visitation is done we create a bsp tree from the backmost node in the vector, remove and add to the parent node the geometry node and top bsp node in the bsp tree respectively and then pop node just converted.
We started by simply converting each GeometryNode as soon as we found them and handle the calls to the parent node, but since this changes the objects while we are visiting them this was not a preferable solution and in fact it wouldn’t even compile on Windows machines.
We don’t actually have complete encapsulation though. Since the renderer takes a long time visiting all the bsp nodes we add a geometry node to the quad nodes. This extra node is set in the HybridBuilder,and we then remove the code to visit bsp nodes from the renderer. This way our collision detection can still use the bsp nodes while we gain a significant performance boost.

Rigid box

The rigid box should function as a model of a box that reacts to physics. The physics “box” is constructed from a number of interconnected “sticks”, each of which is constructured from two particles and a constraint on the distance between those two particles. Thus, we’re actually manipulating particles, but the changes we apply need to maintain the stick constraints, and thus we get the very nice physical properties as described in the (very inspirational) article, “Advanced Character Physics”, by Thomas Jacobsen.

So, the box is actually modelled from 9 particles; one for each of the eight corners of the box, and one in the center of the box. We have a total of 32 constraints, 24 between the corners, and an additional 8 constraints from the center to the corners. We initialize the position of the particles to the relative positions of the box, which is scaled according to the bounding box of the containing geometry. The rest length of the constraints are initialized to be the distance to its connected particles in order to sustain an optimal box shape (ie. the initial box size and shape).

At each time step we execute the following functions:

• Drag: Add a drag effect to each particle, to ensure that we have a realistic stopping motion/friction. We have also added a resistance force to limit our max speed to within a reasonable amount.
  
• AccumulateForce: Add gravity to each particle
• Verlet: Calculate the new position of the particle based on the old position, the acceleration and the time step
• SatisfyConstraints: Makes sure that we satisfy the stick constraints
• CheckCollision: Traverses through the physics scene to check for collisions between the scene and the rigid box (more on this later)
• CalculateTransformation: Calculate the orientation of the box by creating a three axis from corners of the box
• ResetForces: Resets the acceleration of the particles to zero

In the CheckCollision-function we check for collision. We do this by extending the rigid box class to also be an ISceneNodeVisitor, and thus being able to travers the scene graph.
We start by visiting quad nodes (if any), and checking if any particles lie within the quad node. If even just one does, we need to visit the sub tree of the quad node to check for collision. We then visit BSP nodes (if any), where we examine each particle against the divider of the BSP node. We do this to determine in which order we should traverse the BSP tree (ie. back to front or front to back).
The real meat of the collision detection comes we visit some actual geometry. Here we compare each constraint against each face in the geometry. If the constraint (ie. the line between the two particles that the constraint is made of) intersects with a face in the geometry, then we have a constraint/geometry collision. To to restore to a satisfying condition we use projection between the face and the point that had caused the the intersection. To get the point of the projection we use the intersect function in the Face class. An intersect between the face and the line between the point itself and another point defined as an offset from the point by a vector in the direction of the normal to the face will be in the exact point we need. However we will not always get a result from this call.

As seen here particle A can be projected to neither of the faces. Instead we can project it to the plane defined by the faces. This functionality is also included in the face. This yeilds another problem though.

Here we actually don’t wish to project either particle to the plane of the intersected faces. It would be ideal to have functionality to decide which intersection method is needed in each individual case and we have made several attempts at this however, as most of them iterate over all faces and particles and use the cpu-costly intersection method in the face the runtime speed tended to be very slow and thus inappropriate. In the end we had to settle for simply always using PlaneIntersection to handle the projection and live with the bumps and oddities from that decision.

Our rigidbox can mess up, if we suddently add too much force to the box. This is because of the satisfycontraints method iterating through all the constraints, and first fixes one, then later messes it up again when fixing another one. Often this will fix it self if we add alot of force again, but sometimes we get a box thats moved around axises, meaning that we stear around a wrong axis. If we had more time, we would make a fix to reset the box, if the constraints was too streched. Another approch couldbe to respawn the vehiecle at the last visited waypoint.