Bits and Pieces

I've been sucked into Diablo 2 and other distractions lately (damn you, Blizzard), so progress has been meagre. However, I was determined today to continue progress on Synergy. I have been deliberating over integrating a physics engine into the code, and the task is daunting.

I've decided to make the task as easy as possible by setting up everything the physics tests will eventually need and fleshing out the 3DS loading more. This entailed implementing some functionality that supports environments. There's alot of different features that fall under this umbrella, including lightmaps, materials, entity spawning, and many others.

I decided decent ground work for a number of these things was beginning work on extracting material information from the 3DS files. This task proved to be another work in cryptography, as only relatively vague information is at my disposal regarding the file format.

However, after a number of hours stumbling around in the dark, I was successful: the engine loaded in a model of a simple room that had separate materials for the walls and floor. I decided to manipulate the number in the demo code somewhat to make sure all the objects sit within this new room, in preparation for implementing the physics/collision detection. Here's how it all shaped up:

Almost starting to look like a game?!

There's a lot more material information in the 3DS file I can potentially tap into, but it is not relevant at this stage in the engine. Next I will be focusing on loading in lights from 3DS files, and maybe, just maybe take a look at calculating light maps...

I've also devised an algorithm for welding points within a certain distance threshold of each other. Big deal, right? Well as far as my searching on google went, the approach appears to be brute-force O(n^2) algorithms, from what I could find (excerpt from game programming book). My approach was very simple; apply a 3-dimensional closest-pair algorithm to the vertices, with one modification: when the algorithm reaches an input of only 2 vertices, test if their distance is below the given threshold, if it is, weld them and return infinity for the distance.

This should in effect weld all vertices within the threshold in O(n log n) time, but I have yet to implement it and test its correctness.

Final Battle!

Exams are done and dusted! It's similarly epic to defeating the final boss in a game. So far I have gotten back my mark for Software Engineering; ~80%, so a D. Quite chuffed. So, besides basking in many games of Team Fortress 2, I've been noodling around ideas for what I should focus on next with Synergy.

I did some light research into physics engine libraries that are out there, and the selection is extensive. I was impressed. At this point the prime candidate looks to be Bullet. Failing that, perhaps ODE. I made an attempt to compile some of the many MSVC++6 projects that come with Bullet's SDK, some worked, some didn't. There's no binary currently in existence for the library, so I don't know exactly how to proceed. Investigate the forums, I suppose...

I decided to leave that kind of expedition to a later date, primarily because I had a headache and just didn't feel like I had the energy for it. Instead I decided to perform some optimisation on the 3DS loader function, which is still employing the crutch of the brute force algorithm to calculate smoothed normals, resulting in something close to 5 minutes stall to load in a 50000 polygon, single smooth group (worst case problem) model.

After chewing over the problem for a little while, I sketched out a rough algorithm that would run in O(fv) time, where f = number of faces and v = number of vertices. After implementing it, I found the algorithm `almost' works. Satisfyingly, however, it took about 2 seconds to load in that same 50000 poly model! A very significant speed increase. Conceptually, what the algorithm `should' be doing is exactly the same as the brute force algorithm, but somewhere in the implementation there is a deviation which I have yet to isolate.

I thought the incorrectness may have stemmed from the fact that 3DS files export duplicate vertices for the same coordinate in space. To remove this potential threat to the algorithm, I set about implementing a welding algorithm that would merge duplicate vertices into the one vertex list entry, thus compressing the total number of vertices in the mesh.

This algorithm posed some very interesting challenges. The root challenge is that it could not be less efficient than the proposed smoothing algorithm (O(fv)). From this root challenge spawns many other challenges as a result. The algorithm I sketched out is quite straight-forward, but the implementation proved to be a little trickier. The main issue was `how do you compare vertices?'

I divined the answer to this question whilst going to the toilet (details, details...). Essentially the order you compare the components of a vertex depends upon the order you sort them in, which seems obvious upon reflection. With a newly crafted comparison function, I had myself a linear-time welding function.

However, this welding function did not fix the smoothing algorithm. I've decided to leave further debugging until I've had a night's sleep, nevertheless progress is promising!

EDIT (14:14, 27/06/2008): The algorithm is working! I was missing a test for the final pass on indices to assign new normal values...I wasn't testing if the face was part of the smoothing group! How obvious. Amazing what some sleep can do. The code for the linear-time normal smoothing is pretty decent.

I've also had a look back over the mesh rendering function, and split the function depending on which shade model is enabled, meaning that rendering in Flat mode will use the face normal, rather than the normal of the first index in the face, which gives incorrect results.

I'm very happy that I managed this speed increase! Now I can consider physics integration with a clear state of mind.

Give Me Some Skin!

After suffering an 08:30 exam and the apocalyptic effects it has on my sleeping patterns, I felt I might loosen the screws in my mind by taking another look at implementing texture mapping in Synergy.

My suspicions lay in the library I was using to load texture data into OpenGL. To test this, I downloaded and integrated SOIL. So it seemed I could load in textures, but they were not mapped at all to the meshes.

Which made me realise I had left the texture mapping aspect of the SynMesh class, well, hanging. So going back over that was a simple affair, though I had to make an educated guess as to how the .3DS file's texture mapping data is actually organised in respect to polygons. It is, of course, the obvious answer, which is for each vertex in the vertex list, the texture vertex at the same relative position in the texture vertex list is that vertex's texture coordinate.

A little tweaking of SynMesh.render(), and various other spots in the demo code, and I was in business:

Bless my flesh!

Note, the skin for the tree actually isn't finished. So that's a data thing, not a processing error. Very satisfying, after the endless battle with AllegroGL just to do basic texture mapping. Tsk tsk. Here's a lit screenshot, just for fun:

Trees of Bliss

Criminally Smooth

:). I am pleased. It was a long, hard battle, with much contemplation, testing, probing and trial and error, but Synergy now sports Smoothing Group functionality!

Loading in the smoothing group info was a small mission in itself, one which began with trying to find info on how to get it out of a .3DS file. Implementing this actually spurred a revolution in my coding for being very specific about my longs (`32 or 64 bit?'), which seems to have somehow increased the frame rate of Synergy's various demos by up to 6Hz?!

Building upon the code from that tutorial I linked to in the previous post, the code for reading smoothing groups is about as simple as it gets.

I pondered for most of the day on how the process would actually work, sewing threads of ideas through the problem in my head, considering different approaches. What I finally ended up with was a brute-force algorithm with slight optimisations.

The road to reach this code was treacherous, though, with some interesting results along the way:

A World With 1 Normal

This problem was isolated and corrected relatively quickly, basically I didn't have the indices' blank normals initialised to be blank normals. So fixing that brought me to this:

Revenge Of The Cubes

Great. So some things looking lovely, others looking completely screwed. This proved to be part of a bigger problem, it also created seams:

Almost Anatomically Correct!

And generally just lead to strange lighting behaviour on flat surfaces:

Colt 1911s Never Looked So... Jaded

Although for the most part that Colt 1911 model (made by Dylan) looks very very sexy, one can quickly pick out areas which are rendered incorrectly.

I found the problem to be that the first index in a smoothing group wasn't included in part of the normal calculation! So, fixing that Synergy could now do the Colts justice:

Quantum Sexiness

Not to mention the skulls!

Mission: Accomplished

So, what's next? Study! It's time to stop getting sucked into my projects and turn my attention towards trying to get HDs for my end of semester exams. So, until next week I guess Synergy will have to wait.

Meshin' Accomplished

Yeah I know, I'm the lamest person on Earth for using that title. But I don't care, I've succeeded too much today to feel anything but empirically chuffed. Despite cleaning up baby vomit at my Day Job, my time was devoted wholly to Synergy.

After working on the SynMesh and SynModel classes last night, I was keen to get a function running that could load in mesh data from some 3D model file format. After some research I eliminated the majority of options, including all formats without bone/keyframe animation, and all formats which aren't widely accessible. That is, not supported by a wide range of modelling programs. That left me with 3D Studio Max's .3DS format. Big surprise there.

Like all great things my quest for this functionality began with a google search, which lead me to a very useful tutorial. After some copying, pasting, and butchering of this code into a form suitable for my code, I began to, with breath guarded, integrate it into the cubetopia demo, replacing my hand-coded geometry information with SynMeshes loaded from a .3DS geosphere.

Some small tweaks here and there and BAM! Meshes loaded:

Trippin' Balls

I suppose it can't really be called `cubetopia' anymore. Perhaps gala would be more fitting. A number of issues were outstanding at this point. The foremost was that there were no normals! So I set about calculating normals upon loading each face. That lead to some interesting mistakes:

Really Trippin' Balls

After becoming friendlier with the concept of vector normalisation, I got this:

Find the Lightsource

After loading in a cube mesh, I discovered the reason for this bizarre lighting was that the meshes were inside out! So, setting glFrontFace(GL_CCW) I finally achieved a well rounded result:

Lo! 'Tis a Gala Night

Feeling very satisfied with myself, I was eager to push the code and see just how far I'd actually gotten it to work. Next was a model of a tree that I was working on once upon a time, and to my delight it worked straight away, giving a pretty funky result:

Styx

I began to notice a significant delay in loading the 3DS file, so I decided to see how much this delay scaled with input size. I needed a high poly model... and then I remembered a skull I was sculpting in zbrush once upon a time. This lead to a huge delay of almost 2 minutes to load the file. It was obvious where the hangup was: the obscene amount of debug info I was printing to the console and the log file. I commented those out and the delay was vanquished, which lead me to the final product for the evening:

Synergy's High Poly Flat Shading v0.00001

Each skull is ~50k polygons, so theres 400k polys being rendered there. It is both a milestone and a map of the steps yet to take. The most obvious next step is to implement Smoothing Groups. For instance, here is the exact same model rendered in Max with smoothing groups on:

The Next Mission

Big difference. So that's about it; excellent progress for 5 hours work, in my opinion. I hope to make the same leaps and bounds tomorrow, but we'll see...