COSC1186 Assignment Report

Alex Holkner 2107062K

• Introduction
• Quick Start
• Programs
• Scripting
• Design
• Blog

Development Blog

Resources

• Compiling GL apps on your Mac

Log

May 23

Finished the report, minus some screenshots; moved the resources from the blog into the design section of the report.

Yay! It's 4am the morning before the assignment is due and I have finally textured the orc! Looks like a bit of a punk, if you ask me.

Notice also the new scenery, it's a little more deserty, less hilly, and more overcast.

May 22

Finished off the easy bits of the report: the key bindings, the build instructions, and complete scripting language manual. Moved this blog into the report and pushed the report CVS online.

May 21

Reorganised source directories to separate data and source files. This took ages, thanks to CVS's lack of a move command. Thanks, CVS! Also started the report; wrote up a template, stylesheet and introduction.

May 20

More problems with key repeat under Linux; Vincent installed a newer version of Freeglut which fixes the bugs I experienced before, but introduces some more serious ones. Rather than muck around with this any more, I changed some of the key bindings on the marionette program to completely avoid the issue; and switched the key repeat code to use the older, less-broken Freeglut.

Ran some experiments with group behaviour: I had 80 orcs running around together in Sutherland this morning -- looks very sexy!

May 19

Have been working for 17 hours straight :-( and accomplished the following:

• Added a chase camera, which follows an orc with a certain amount of lag
• Finalized key bindings for toggling render options
• Added if/else constructs and boolean AND / OR operators to the scripting language
• Fixed up the "look in the direction of that orc" code
• Created a "duel" scenario, where two orcs hack each other to pieces for your entertainment
• Coded smooth transitions between animations -- now the orc will never "jump" from one pose to another; he will always take half a second to smoothly adjust himself.
• Fixed all the bugs introduced by the above code
• Fixed the bugs caused by the above bug fixes
• Patched a whole bunch of memory leaks; not all of them new
• Added "comment" ability to the scripts
• Reorganised main.c to clean out old code
• Added texture mapping to meshes -- this wasn't hard, but I'm not having much luck drawing convincing skin textures so I don't think I'll actually use it.
• Drank a hellava lot of coffeeeeee

Here is the head, partitioned into sections for texture mapping. Just like a regular Frankenstein's monster:

Love to go to bed now but unfortunately I have to go to a tute; at least I will be on time for once!

May 18

Doh! The assignment is due in on the 24th, not the 31st like I thought, so I've got to make up for an extra week I thought I had. I'm just working off my todo list at the moment (had to cross out a few features to get into the new deadline). Today I:

• Generalized for-each loops to work over any list
• Added an option to suppress the output of each statement (this was slowing everything down due to the console echo)
• Added all the necessary animations: attack, at-ease, threaten and charge
• Added script functions for calculating the magnitude and heading of a vector
• Wrote a simple behaviour script which gets ten orcs to wander around aimlessly, without straying too far from each other
• Fixed a serious memory leak in the scheduler
• Removed the broken lexical include statement, and replaced it with a simpler "load" function.

I also did a quick profile using gprof, but nothing stands out as being particularly bad. The results seem to be flooded with Carbon calls, which is diluting the other statistics. I will try it under Linux some other time; but it doesn't look like any one function is bottlenecking the rest. For instance, the nodeDecRef function, which is called over 500,000 times in the four second execution time, contributes to 0.0% of the processing.

May 17

Complicated problems require complicated solutions. That's my explanation for spending six hours implementing a clever abstraction on the parser I like to call a "context". This is like a local variable space, and the reason I implemented it is so I can write a nice script like this:

for each orc in clan { wait random(3.0) { play(orc, walk); } }

Which is my nifty way of getting all the orcs to walk out of step (they each start the walk animation after a random amount of time). Works for me!

May 16

Implemented some control structures for the AST. Now the scripting allows conditional statements, loops, delayed execution, intervalled execution and more sophisticated key bindings. The conditional statements are a bit weak since I haven't provided a boolean type or any comparison operators, but it works for now.

Added a scheduler, which can be accessed from the scripting language via the new control structures, or from the native code with callbacks. A priority queue is maintained which ensures events are processed in order and the correct number of times (for repeating tasks).

May 15

Time to do something which can be seen! Added a PNG texture loader and a sky cube (a cube surrounds the environment, giving a seamless atmosphere). Mmm, atmosphere...

May 14

Added multiple orc support. This wasn't much work, since I'd been writing the code in preparation for this the whole time. To improve performance the renderer will now choose an appropriate low- or high- resolution mesh dependending on the distance of the orc from the camera. The result is a smooth(ish) transition from 1000 polygon orcs to 20,000 polygon orcs moving from far away to close up.

One feature I wanted to add to the scripting language is to loop, or repeat, code blocks. Using the current implementation this was impossible, since nodes are evaulated as they are parsed. To counter this, I extended nodes to represent branches and leaves in an abstract syntax tree. Now I can delay evaluating (reducing) nodes until necessary -- for instance, until evalutaion of a repeat node.

I've said it before, but it doesn't seem to be sinking in -- I've really got to stop fiddling with the internals of the application at this late stage!

May 12

Finished the head mesh (added some ears and teeth). The mouth still doesn't look very good, but I'm not going to spend any more time until everything else is finished.

Created keyframes and animations for marching and running. That leaves only the attack animations to do, which should be much easier than the moving ones.

According to my timeline, I'll be instantiating multiple orcs tomorow!

May 11

Decided that I didn't want to lose marks for memory leaks, so I gallantly put on my memory-fighting helmet and leapt into the dragon's mouth. Now, you should understand that my memory leaks are oh so more subtle than in a typical program, because of the expression parser. The parser needs to create objects on the heap to send them to various systems for parsing, and it's not obvious when to free them. Up until now I had let a lot of them go -- after all, it's only a few bytes here and there.

Not good enough any more! So, I need a garbage collector. But to implement garbage collection, all the node objects have to be on the heap. Until now, most were allocated on the stack, for efficiency and simplicity. Well, now they're all going on the heap, after some delicate (drastic) surgery on some files I hadn't touched in a long time.

After allocating the nodes on the heap and making sure everything still works, I implemented a simple reference counting garbage collector. Much painstaking though went into devising schemes for when to increment, when to decrement, and when to "borrow" references. Luckily it all worked out eventually.

The downside to reference counting is that it can't free objects with circular references. To counter this, specific objects are not tracked: anims, geoms and joints. They are referenced in a global list which is destroyed on exit. This is no great loss, as all of these objects can be expected to survive for the duration of a session anyway.

As of this moment the program leaks zero bytes of memory! As a bonus I cleaned up some other code to eliminate some straggling compiler warnings. Oh, it looks so squeaky clean now.

P.S. While eating my cookie I devised a timeline for getting everything finished by the end of the month (due date). It's going to be pretty tight. I'm glad I've sorted out these memory bugs now; making such drastic changes to the core would've gotten stressful if I'd left it any later.

May 4

Have done a great deal more on the mesh. The arms and torso look silly, but the head is coming together okay. The total number of triangles is at about 10,000 for one orc. Not surprisingly, the frame rate dropped to around 30 on my home computer.

Up until now I have been deliberately avoiding optimization, but this seemed like a good time to start. I added code in the mesh drawer to compile a single mesh (bone) into a display list the first time it is drawn, and then re-use that compiled version for subsequent draws. The result: an immediate increase in framerate up to 150 (a 500% improvement).

I still have plenty of further optimisations up my sleeve, too.

May 3

Spent some time working on the torso mesh. I'm really hopeless at this (probably related to being useless with a paintbrush); but I got some books from the library which explain subdivision modelling, and they are helping.

May 2

Added some code to align meshes to bones (the origin); this means I can have all the meshes in one OBJ file. Each limb/bone is a separate object in the file, and is paired with a couple of markers which specify where the bone starts and ends. I am using Wings 3d to do the modelling, and it doesn't support points, so the markers are tetrahedrons, which is silly but works.

One side effect of adding meshes is that I can now see that certain bones aren't oriented in the correct direction (when they were rendered as lines, it didn't matter). So I just spent a few hours spinning them around into the correct position for the walking animation, so that the calves and shins point the right way.

Gave the orc hips! Now his legs no longer join at the groin, which looked a bit crazy when he walked.

Added key-up handlers, so the orc's motion is now controlled more intuitively by pressing and releasing the arrow keys.

May 1 (Later that day)

The OBJ loader is working -- it triangulates faces and loads normals. Doesn't do any translation so I had to reorient and scale the shoe, but now it's on the orc's foot (both of them, actually!). Here is the orc, tap-tap-tapping his shiny new shoes:

orc-shoes.mpg (2.6 MB)

May 1 (Very early morning)

I meshed a shoe! Tomorrow I will try to load it and put it on one of the orc's feet.

April 30

Finally the orc is turning properly! It seems I'm doing things the difficult way, by having his position change only after the end of each walk sequence. This has the advantage of not needing a constant offset each frame, but the disadvantage of making turning and stopping quite difficult. After much headache, and about 5 hours of work, he turns around the right point now. Excellent.

April 24

Added some more interpolation functions; now I have the whole range of Disney slow-in, slow-out, fast-in, fast-out, as well as plain old linear. This graph shows the speed of these transitions:

The orc looks much better bobbing up and down with the exp/log functions, as he has "bounce" now, but these functions just look silly with the walking animation.

April 13

Have been neglecting the walking animation but I did make a movie of it. I did this by capturing 24 PNG files every second, using Photoshop to convert them to JPEG, and then stringing them together in iMovie and exporting as MPEG4. Not surprisingly, the quality is terrible! Unfortunately iMovie doesn't want to accept any other picture formats (just seems to hang), and I've spent far too long trying to get libjpeg installed. Anyway, here is the movie; you can see I've animated only the legs at this stage, and the feet are all over the place. But it will make for a good "before" and "after" shot later :-)

orc-walk1.mp4 (315 kB)

April 11

IK solver is working now; it can get a bit touchy but with hand-holding it solves chains of toe to hip and hand to shoulder. It can't solve the foot rotation independently, but it's not a problem I'm going to spend any more time on, as it's easy enough to orient the feet with FK. I have a very basic walking animation that puts the feet in the right spots but not much else yet.

Added zoom & tracking for mouse, and finalised the instance type, so theoretically I can have multiple orcs now (untested).

April 10

Am using some of the OpenGL matrix routines (using glGetFloatv) instead of my own routines because they were getting difficult to debug. Now I can compute a "virtual bone" from one joint to another, so am well on the way with the IK solver. Most of the troubles with my matrix routines were to do with its layout, which I'd accidently done row-order instead of column-order, which conflicted with OpenGL and gave screwy results.

April 9

Started implementing a simple inverse kinematic solver in a new branch (so I can leave it for a bit later if it's not working easily). Many headaches with local/world coordinates. Still lots of code to write

April 3

Added modifier keys to the bindings, so now you can press CTRL with movement to do fine adjustment. It's still really difficult to line up feet so that they stay in the same place when the body moves. Have been reading up on inverse kinematics, but not sure if I really want to implement anything that complicated.

April 1

Was playing around with the code to make projection matrices and stumbled upon a great way to factorise large numbers in logarithmic time.

March 30

It was getting difficult to see where the orc's feet were, and to stop them floating, so I added a floor and a planar shadow. The code for the shadow is straight from SGI - I didn't have any success with the red book matrix.

March 29

Runs in Sutherland after some tweaking to the keyboard bindings and the timing functions (very slight differences under Linux). It clocks around 3 times faster in this lab than on my laptop, which is to be expected.

There is a bug with the capture to PNG which makes the image skewed if the width is not a multiple of 4. I'm not sure if this is an alignment problem with libpng or opengl. Probably not worth fixing.

Did some surgery on the geometry and animation functions, replacing angle/axis representations with quaternions, and adding translations. The next logical step would be to replace these with a straight 4x4 matrix, but I'm not sure if the extra work is worth the performance gain (if any).

March 28

Can snapshot the output and save it as PNG - which by itself is not very useful (could use any screen grab) - but I can make this save say, 24 frames every second - and string them together with iMovie (or whatever). Will upload a video when I have a decent animation!

Also fixed some memory leaks and an intermittent segmentation fault (woo). top still reports memory leaks while idling, but I can't see any in the leak report, which checks all malloc's, so I assume it's either a Cocoa or OpenGL leak. Will try it in Sutherland tomorrow and see what happens.

March 27

Finally, animation! I left this late because I wanted to make sure I had flexible data structures; each loop (e.g. "walking") is divided into a number of "anims", each of which specifies two keyframes, a time delta and an interpolation method. Currently there are three interpolators: fixed (which holds a frame, useful for keyframe editing), linear (just does linear interpolation of the angle/axis rotation) and SLERP (spherical interpolation using quaternions). It will be easy to add interpolators for non-linear transitions later.

The animation is synchronised to the system clock using gettimeofday(), so I can program the movements to take place at a certain speed regardless of the load on the CPU (it will skip frames if necessary to keep up).

There is an FPS counter on screen as well - my stick figure clocks at 700-1100 frames per second, so I guess in theory I could have around 3000 stick figures animating on screen in full motion; but we'll see about that!

My Sutherland account was finally activated, so I fixed up a few things to get it compiling under linux. Can't test it in the lab yet, will have to wait until Monday.

March 26

Added mouse support (orbit around origin, always oriented up); a status display, multiline key bindings, and fixed a bug in the insert frame algorithm. It's getting quite easy to make frames now, but I'm not very good at making them look good!

March 25

Turned on -Wall -pedantic -std=c99 and fixed up all the warnings, so no more lazy function definitions! Also cleaned up the build process a little.

March 23

Spent about 4 hours wrestling with quaternions, but I finally have sensible rotations for the keyframe editor (keys for rotating around each local axis of the bone). Before this the only way to change a keyframe was to enter a new axis/angle vector, which is hardly intuitive. Expect some exciting keyframes soon!

Note to self: C assumes functions return int even if you don't define them, so when you are a dolt and forget to include math.h, don't be surprised when all the trig results are wrong.

Promise never to be a dolt again, and get back several hours of my life.

March 22

My Mum said the orc looked anaemic, so I added some drawing parameters which can be specified on a per-bone basis. So, in the spirit of Lewis Carrol: "You won't make yourself a bit realer by crying" (-- Tweedledee).

March 21

The program is now parsing and loading geometries and keyframes from disk; both can also be modified interactively using the same expression language (which is similar to python, but limited at the moment). Here is a stick orc:

March 20

Had a look at loading the geometries/keyframes from disk. The parsing required seems fairly involved, so I've written a flex / bison stack based interpreter for specifying geometries as well as replacing the simple command interpreter I wrote before. Doesn't do much yet though...

March 19

Took a break for a week to work on some other subjects. Did manage to get the bottom half of a stick figure showing using my binary tree; it's not very impressive!

March 12

Started work on the geometry; this consists of a binary tree of which each element contains a rotation angle and length. It's not working entirely to plan, as I still need a way to change these angles along an aribitrary axis; I have a feeling I will have to implement my own matrix routines.

March 11

Now I have customised key-bindings; each key on the keyboard can map to a command interpreted by the internal CLI. For instance, to make "l" show/hide the log, execute bind l toggle log. This mechanism will be used to control everything from geometry transforms, animation, camera movement, etc. Something like bind <LEFT> transform world -0.5, but I'll need to think about that. Commands can also be loaded from a file now, which is useful for these key bindings.

March 10

Wrote some framwork code just to get started with; I'm using the same GLUT calls as the redbook robot.c demo. Added some things I think I will find useful later:

• Some text rendering routines
• A command-line interpreter that runs inside the GL window
• A formatted logging system, that can output to screen and/or file
• So far the only commands supported are "show/hide log" and "log <message>", but I think this is a better approach for changing things on the fly than a whole keyboard of controls to remember.

Here is the first screenshot. Note that the orc looks somewhat like a teapot at the moment; I should probably rectify that soon!

March 4

Jotted out this page, all ready to be blogged up! There is a quick howto on compiling GL apps on a Mac; or am I the only one sensible enough to use one?