Apparently I'm not Charles Bloom

Yesterday I posted a rant out of frustration at a frequent number of emails I get from people on the Internet. I often get asked questions by people, who from the content of their question, clearly don't know how to program in C++ hardly at all. It's difficult to figure out how to respond to that sort of thing.

Here's the deal. I'm a nice guy. It's not just a put on, or an act, or a pose, or anything like that. I'm genuinely a nice person. I really like to help people out, not just in programming, but in life in general. I also really like to teach and I absolutely don't mind people asking me programming questions.

All that said, there are certain types of questions, like those that indicate you don't know how to program at all, that completely leave me at a loss.

After I posted my rant yesterday an Anonymous (yep you heard it, anonymous) person left a comment chastising me for being so rude and obnoxious to people who just wanted to learn from a professional software developer.

Well, anonymous comments on my blog are yet another one of my pet peeves that often make me launch off on a rant. Seriously, if you ever really want me to answer a question, don't leave an Anonymous comment! Take a moment and enter an email address so I can respond to you directly.

Nevertheless, the guy who left the comment was right. It is inappropriate and out of character for me to curse out beginner programmers who simply want to learn something.

I edited yesterday's post, removed the F-bombs and personal insults, but left the basic tone and content the same. With this post I would like to apologize. I do encourage people, even beginners, to learn from my code snippets. To be frank, that is often whey I write them! Especially 'FloatMath' which is an amazing repository for various and sundry math functions.

So, feel free to ask me questions and I promise I won't be insulting. However, if you are such a beginner that you can't understand some very basic and simple things about C++ programming, I have to be honest, there isn't much I can tell you until you bone up on your skills. And, if that is the case, I will try to say so politely instead of going off on a rant.

I like to rant, just like Charles Bloom does, but I don't like the repercussions. The things I wrote on my blog yesterday I would never say to someone's face. Thus the weird dichotomy of Internet communications.

Once again I apologize to anyone who might have been offended by my post. I genuinely want to help programmers, even beginner programmers, solve their problems. My main motivation in this site, besides simply sharing useful code with developers who have shared useful code with me (such as Charles Bloom one of the most generous open source developers out there) is to educate.

If you are disappointed that I backed off my rant, then I strongly recommend you subscribe to a news feed of Charles Bloom's website as I'm sure you will find your daily dose of rank ranting over there.

Holy Crap??? My very own Charles Bloomesque Rant

( The snippet form of the best fit plane code can be found here. It supports both single and double precision floating point numbers and even has an example 'main' in it for the truly technically challenged)

bestfit.h
bestfit.cpp)

(Note: The following rant has been edited from it's original by the author.)

Holy crap. I pride myself on being able to provide source code which is extremely (and I mean *extremely*) easy for people to adopt and use.

That is why I put everything in 'snippet' form; and by that I mean one header, one CPP, with no external dependencies of any kind. I provide code that is not dependent on special templates or data types.

The one piece of code that people come to this site for a lot, is the code snippet I provided for computing a best fit plane.

Now, I didn't even actually write this code myself. David Eberly did on his Magic Software site. I love David Eberly to death, he provides more amazing free source code to the community than nearly anyone else. That said, David does commit the horrific crime of providing code that can *only* be used within the context of his personal suite of template/type libraries. It is virtually impossible to just extract one useful math routine out of his code base without having to adopt every vector, matrix, quaternion, template, and every other dependency all of his code requires.

In fact it took me the better part of the day to convert his 'best fit plane' routine into code snippet form.

Now, it simply amazes me how many questions I get from people who can't understand how to use my code-snippet version!??!

I have even had a number of people email me with the question "I don't get it, where is 'main'?".

Really? Seriously?

This is one tiny isolated routine, one snippet of code. Drop it into your own program, call it, and be done.

If you don't know how to even use a code snippet in the first place, you might not be at the right web site...

So, hey, maybe I'm wrong here.....

So let's check back.

Here is the only thing the header file contains for the best fit plane code snippet:

----------------------------------------------------------

bool fm_computeBestFitPlane(size_t vcount, // number of input data points
const float *points, // starting address of points array.
size_t vstride, // stride between input points.
const float *weights, // *optional point weighting values.
size_t wstride, // weight stride for each vertex.
float plane[4]);

-----------------------------------------------------------------

So...what's the problem? What is there not to understand? I can understand not understaning the 'weighting' part, because I didn't really explain that. But, the rest, really!???

Ok, now in baby steps.....

Let's say you have a set of 3D data points. Woops....just realized I might be talking past my audience.

3D means 'three dimensional' as in representing a location in three dimensional space, typically represented as the notation X, Y, and Z.

Each point in space is three floating points numbers.

Example: float this_is_a_point_in_space[3] = { 3, 4, 5 };

Got that?

Understand?

Ok, now let's represent 2 points in space.....

float this_is_two_points_in_space[6] = { 3, 4, 5, 8, 1, 4 };

Now, lots of people don't use just a float array to represent their points. They often use data structures.

They might have a structure like:

struct Point
{
float x;
float y;
float z;
};

Thus, they might represent two ponts as:

Point this_is_two_points[2];

Get it? Follow me?

And...sometimes...people have structures that contain data in addition to just the points!

For example:

struct Vertex
{
Point position;
int color;
};

Follow me?

You can represent your points in a variety of ways *in your code* but one thing is always common. A point, in 3 space, is three floating point numbers in the order of X, Y, Z.

Thus... in my routine, you pass the address of the x component of your first point and the stride (stride is the distance between the first X and the next X in bytes).

The return value is a plane. What do I mean by that?

There are four components to a plane equation typically expressed as A,B,C, and D.

Now, my routine returns the results of the plane equation as four floating point numbers representing A,B,C, and D.

What follows are several examples of how you can call my mysterious and cryptic code:

--------------------------------------------------------------------------------

float points[9] = { 3, 4, 2, 8, 1, 4, -4, 4, 3 }; // float array with 3 data points in the form of x,y,z

float plane[4]; // will contain the computed plane equation result

fm_computeBestFitPlane(3, // we have 3 data points.
points, // the address of the X component of the first data point.
sizeof(float)*3, // The stride (distance in bytes) between one point and the next.
NULL, // pass a null pointer for weights
0, // pass a zero for weight stride.
plane); // the address of the plane equation to store the result.

-------------------------------------------------

Ok, now here is an example presuming your code has data types such as 'Vertex' and 'Plane'.

Vertex vertices[3];
Plane p;

fm_computeBestFitPlane(number_of_points,
&mVertices.mPoint.x,
sizeof(Vertex),
0,
0,
&p.A); // the address to store the plane equation results in the form A,B,C,D

-------------------------------------------------------------------

On a final note, the field for weights is an optional set of weighting values corresponding with each vertex. They are unitless and simply serve as relative weighting components.

If you want the plane fitting code to weigh some vertices more strongly than others, then you would pass a larger weight value at that index location.

Since the weighting thing is entirely optional I won't bother to explain it further. Personally, I think it is self-evident.

Look, to adopt a number of these code snippets requires a minimum technical knowledge about programming in C++

Telnet : A code snippet that embeds a telnet client or server into your application

This might well be the single most useful code snippet I have ever published. I took some old code that was originally written as part of Novodex Rocket, later to become PhysX Rocket, and re-packaged it into snippet form. This code was largely written by my friend James Dolan, though some of it is mine as well. Back when I was at Ageia we open-sourced the Rocket application and this code was part of that release.

The only thing keeping this snippet from being widely useful is that, currently, it only builds on Windows or XBOX machines. I have not yet ported it to Linux, Apple, Iphone, etc. It would be extremely useful on those platforms. If anyone wants to volunteer to revise the code so that it conditionally compiles for those targets I would greatly appreciate it!

What this code snippet does is that it allows you to embed a telnet server, or client, into any application. Simply include the source into your project (telnet.cpp and telnet.h).

Somewhere on startup in your code call:

TELNET::createTelnet("localhost",23)

This will create an instance of the telnet client/server system. The first time you start it up on your machine, it should find port 23 free, and it will be created as a server. The second time you launch it, it will see that port 23 is used, and instead it will launch as a client. You can launch as many clients as you want and, of course, they don't have to be on the same machines.

You can also just use an ordinary telnet client of any flavor and connect to your application.

So, what is this good for? It allows you to send debug commands and receive log spew from any application, without having to write any GUI interfaces. This is especially useful for console games or anything running on an embedded system. Think of it as a 'back door' way to poke commands into a running application and receive debug spew back out again.

You can also use it as a quick and dirty way to do network communication.

The code itself could be a little cleaner but, hey, it works. I took what was previously about a dozen source files and combined them into one single large CPP file of roughly 2,000 lines in length.

However, that is all about implementation and what you care about is the interface.

Below is the entire header file for the telnet system.


namespace TELNET
{

class Telnet
{
public:
virtual bool isServer(void) = 0; // returns true if we are a server or a client. First one created on a machine is a server, additional copies are clients.

virtual bool haveConnection(void) = 0; // returns true if we (as a client) successfully connected to the server.

virtual bool sendMessage(unsigned int client,const char *fmt,...) = 0; // send a message to the server, all clients (client=0) or just a specific client.

virtual const char * receiveMessage(unsigned int &client) = 0; // receive an incoming message (client=0) means it came from the server, otherwise it designates a specific client.

virtual const char ** getArgs(const char *input,int &argc) = 0; // parse string into a series of arguments.

protected:
virtual ~Telnet(void) { };
};

Telnet * createTelnet(const char *address="LOCALHOST",unsigned int port=23);

void releaseTelnet(Telnet *t);

};

extern TELNET::Telnet *gTelnet; // optional global variable representing the TELNET singleton for the application.



You can download the source directly from this location:

telnet.h
telnet.cpp

Or, I recommend you sync to the Google code repository as it is guaranteed to always be the most current.

More commentary about multiplatform development for mobile devices; including Iphone

I received the following emails from developer Benjamin Lee who confirmed that my strategy of doing multiplatform development by using Visual Studio on the PC was a good approach.

John,

I stumbled across your blog. Kudos for you for doing your dev on the PC. We actually do the same here. Our SDK runs on PC, Mac, and the iPhone. It runs nearly identical on all platforms, using the same datasets too. Aside from the obvious input differences, the only other differences we occasionally find are render issues, since the PC may render scenes slightly differently.

If your stuff already works well with the iPhone, then being able to have pretty stable Mac running code would be no problem. We could probably do the same with the Mac, but I have one mactoppie and the screen size is way too small to get any effective work done.

Thanks posting an interesting blog.

Ben

and a follow up:

John,


And as you mentioned in your comment to anon on your "iphone development framework" post ... since you wanting to support more platforms, your method is really the way to go. To do otherwise is the long way around.

We developed the PC SDK first. Then ported to Mac. Then ported to iPhone. The iPhone port took less than a day. We will probably port to the Wii next. But I expect that port to be very quick.

You could also cite that other advantages are that you can do much better memory leak testing on the PC. While Instruments can be used (and we do test up against it), the PC provides a much better environment for memory counting (at least for us since like you, we were not Mac or iPhone people).

Ben

Iphone development framework

This is a follow up to my last post. This past week I did, in fact, create a little framework that let's me develop for the Iphone primarily using Visual Studio under windows. The process went very smoothly and the only difficulty, besides learning the Macintosh and Xcode, was that it was the first time I have programmed OpenGL.

This framework is really just a starting point. It has kind of a minimal implementation I needed to get my isometric game level to show up on the screen.

Obviously I cannot make my game open source, since somebody would just steal it and upload it as their own to the App store, but I do plan to make the framework itself open source. If I can get more developers to contribute to it, then it could become something quite useful.

Even if no one else bothers to contribute to it, I am still proud to release it as a proof that this is a valid approach to developing for the Iphone.

The Google Code location is here.

If you are comfortable with SVN, you can just sync anonymously to this repository:

http://isogame-iphone.googlecode.com/svn/trunk/

If you aren't in to the whole SVN thing, you can just download the directory all zipped up from this location.

http://code.google.com/p/isogame-iphone/downloads/list

To check it out, under Windows, go to the compiler/vc8 directory and load 'WorldViewer.sln'

It should build fine, if you are using 2008, just let it autoconvert the solution and project files. Also you can disable any hooks to source control that might pop up.

Once you build and run the project, hit '1' through '4' on the keyboard to load several test isometric game levels.

Use 'W', 'A', 'S', 'D', to scroll around the map and the SPACEBAR will toggle between landscape and portrait.

Meanwhile, on your Macintosh, just go to the directory /app/WorldViewer and load the Xcode project located there.

Build and run it on your simulator and you will see the same exact application, using all of the same source code, running.

The bulk of the interface that comprises the framework is in two header files.

/include/IphoneGraphics/IphoneGraphics.h
/include/IphoneGame/IphoneGame.h

The single location that the Iphone or Windows app talks to the framework is exclusively through the pure virtual interface defined in 'IphoneGame.h'

This framework is far from complete, it is only provided here as a 'proof of concept'. If you are interested in using this framework as a starting point for a project and you intend to improve it, let me know and I will see about adding your as a member of the Google Code project.

I need a game level designer

Does anyone know of a young person who would enjoy doing some game level design for fun? I am starting work on the Iphone and I plan to specialize in 2d isometric scrolling games. I am using the level design tool called 'World Creator 2.5' to create my game levels.

If you know of a young person interested in getting a chance to work on a real game, for experience and to improve their resume, please let me know. A familiarity with World Creator 2.5 is a major, major, plus.

Please email me if you are interested in the opportunity.

Am I the only one developing their Iphone apps on the PC?

So, I have only just started programming for the Iphone. I got my MacMini and set it up. I loaded and built a bunch of sample applications and got myself familiar with the development environment.

I'm not really here to say anything all that critical about Xcode or the Iphone development system in particular. The point here is one of familiarity. I'm pretty old school, I mean really, really, old school. Even though I am on Windows XP developing graphics based applications using Visual Studio, I still spend the vast majority of my day in a DOS command prompt running an ancient text editor, called Qedit, that I have been using for over twenty years.

The bottom line is that I am set in my ways, and I see no compelling reason to switch to a new development environment that I am unfamilar with. Where are my macros, hot keys, batch files, etc. etc. ?

So, the very first thing I decided to do when I started programming the Iphone was to write the bulk of the game using C++ and OpenGL on my PC.; with just a tiny bit of conditional compilation, I can run the same code on both systems.

In addition to getting fast iteration cycles and being able to use tools I am familar with, there are some other advantages.

The Iphone game I am working on is going to take advantage of the Blue-Tooth mulitplayer game features that will come out in OS3.0. Dealing with all of the code to synchronize the game multiplayer is going to be quite complex, and I would hate to have to download a copy of the app to two different Iphone/Ipod touches just to test and debug it.

On the PC I simply fire up two copies of the game, in two copies of visual studio. I have the apps talk to each other using some kind of simple interprocess communication, and then I can debug all of the multiplayer code very rapidly.

Could I do this on a Mac? Maybe, but it would take me a long time to figure it out.

This seems such a natural way to develop code, I'm suprised more people aren't doing it as well. Isolate your OS specific code around some wrappers, write the entire application in C++ with just the absolute fewest minimal hooks from Objective C.

Needless to say, I will be making this entire framework open source as it progresses, and I'm curious to see if anyone else finds it useful.

Does this make sense to anyone else?

Texture Packing : A code snippet to compute a texture atlas

I am providing a code snippet that computes a texture atlas. This code snippet does not do any image processing, it merely figures out an efficient packing of rectangles into a single larger rectangle. It is up to the user to copy the bitmaps themselves.

One feature of the algorithm is that it will rotate source rectangles by 90 degrees if it makes them pack more efficiently. Because of this you will need to be prepared to rotate your source U/V co-ordinates to account for this.

This code snippet will optionally return an enclosing rectangle that is a power of two multiple. Also it will, optionally, add a one pixel border around each texture if specified.

I wrote this code snippets so that I can combine a bunch of tiled textures into a single texture for an Iphone game I am working on. It seems to work, but I have no guarantees that it is optimal or robust. If you use it, and improve it, please let me know.

Here is how you use it. Simply include the header file 'TexturePacker.h' and add the source file 'TexturePacker.cpp' to your project. This code has no external dependencies.

TexturePacker.h
TexturePacker.cpp

First create an instance of the TexturePacker interface.

TEXTURE_PACKER::TexturePacker *tp = TEXTURE_PACKER::createTexturePacker();
//
// Next inform the system how many textures you want to pack.
//
tp->setTextureCount(10);
//
// Now, add each texture's width and height in sequence 1-10
//
tp->addTexture(wid,hit)
//
// Next you pack them .
//
int unused_area = tp->packTextures(width,height,true,true)
//
The return code is the unused surface area. It also returns the width and height of the rectangle needed to contain all textures.

If you want to force your output texture to be a power of two, set that option to true.
If you want a one pixel border around your textures set that parameter to true.

Finally, to retrieve the results, for each texture 0-(n-1) call 'getTextureLocation'.

This will return the x,y position of the texture in the texture atlas, and the width and height (should be the same as the original)

Now, this is very important, if the call to getTextureLocation returns true, it means that the texture was rotated 90 degrees to make it better fit into the available space. You should rotate your U/V co-ordinates accordingly.


The algorithm for packing textures as as follows:

Step #1 : Find the longest edge and total area of all source textures.

Step #2 : Create a single large rectangle big enough to fit all textures; round up to the nearest power of two if necessary. Add this rectangle as a node in the 'free list'.

Step #3 : Place each texture, first by finding the texture with the largest area and longest edge that has not yet been placed.

Step #4 : .. Look through the free nodes list, and if a free node is exactly the same size, then use it.
Otherwise, find a free node that is furthest down and to the left of the co-ordinate space (growing up and to the right while we stack)
Always insert the node so that the long edge lays down, preventing as much as possible the texture-atlas from growing vertically.
If a placed node has been rotated 90 degrees (width/height swapped) flag it as so.

Step #5 : If the texture we are inserting shares an edge with the free node, then simply shrink the free node down to make up the difference.

Step #6 : If the texture doesn't share any edge then split the rectangle in two, allocating a new free node and adding to the node list.

Step #7 : See if any nodes can be combined back into one; do this until no more rectangles can be collapsed.

Step #8 : Repeat until all textures have been inserted.

Step #9 : Find the maximum height we ended up using and return that as the actual height. Clamp the height to the nearest power of two if needed.

Step #10 : Iterate through the results and copy your textures to a single large texture-atlas.
This code does not do the image copying, that is done by your own application.

If you use this snippet, and especially if you improve it, let me know.

Nvidia PhysX APEX Cloth Integration for GDC 09

Here is a video clip showing the APEX cloth integration I did for GDC09. I currently work at Simutronics on the MMO game engine called HeroEngine. My friends working on the PhysX SDK did a really cool clothing module and I was the first person who got a chance to integrate it into a game engine. I think the results turned out pretty well.

Best Fit Plane : Best Fit AABB : Best Fit OBB : Best Fit Sphere : Best Fit Capsule

(A concrete example of two best fit spheres.)


Today I put together a code snippet that contains just my 'best fit' routines. Probably the most common thing people come to this website for. They have been isolated into a single CPP and header file inside the namespace 'BEST_FIT'.

These are simply copies of the same routines which are found in the larger snippets collection called 'FloatMath'.

There is one new function I haven't previously posted which is a best fit capsule routine. The best fit capsule is derived by first computing the best fit OBB and then orienting the capsule along its longest edge and computing the radius by examining the maximum distance along the two shorter edges.

The capsule returned is in the exact format used by the PhysX SDK; which assumes that the Y axis of the capsule represents 'height' and the X/Z plane is the radius.

It is important to note that if the returned capsule height is a negative number, that means it could not be represented as a capsule and, instead, you should treat it as a sphere with the radius returned. Also, intentionally, there is a chance some points of the input cloud could extend outside of the capped spheres at then ends of the capsule. I did this on purpose because my primary use for the capsule fitting code is for automatic ragdoll generation and that kind of error is more than acceptable. I doubt it would matter in most use cases, but you should be aware of the limitation.

As in my previous source snippets, these routines should allow you to directly use your existing vector, matrix, and quaternion classes, unless they are particularily non-standard.

A vector is assumed to be a float pointer representing X, Y, and Z
A quaternioni is assumed to be a float 4 pointer to a quaternion in the format X, Y, Z, W
A matrix is assumed to be a float 16 pointer to a 4x4 matrix in the traditional D3DX format.

If you represent your quaternions or matrices differently, you will want to translate the results on the way in and out, otherwise you can just cast your existing classes to a float pointer and you should be able to use the routines directly.

Here is a direct link to the BestFit source code snippet:

BestFit.h
BestFit.cpp

Here is a direct link to the latest version of the FloatMath code snippet library, which has grown somewhat large over time, but now includes some more powerful geometric primitives.

FloatMath.h
FloatMath.cpp
FloatMath.inl

------------ Important note as of March 11, 2009

The best fit sphere routine has been updated to be exact, per Charles Bloom's recommendations. I will update the OBB routine relatively soon, I'm going to try out Bloom's convex hull routine and see if it is appropriate as a pre-process stage for the OBB point cloud.

FastXml : An extremely lightweight stream oriented XML parser

In the past when I needed to parse an XML file I have been using TinyXML; which is a nice XML system and quite robust. However, most of the time, when I want to parse an XML file I really just need to treat it as a raw stream of data and I don't need any support for parent/child relationships or other hierarchical information.

And, while TinyXML is kind of tiny, it's still a fair amount of source code somewhere around 6,000 lines or so. It also isn't particularly fast.

Today I wrote an XML parser that is extremely non-robust. It pretty much assumes perfectly formed XML data and I don't know if I have taken every single use case into account. It does manage to parse all of my sample data that I needed, and, for me, that was enough.

FastXml is only about 350 lines long and is very fast. It parses 'in place' like my in-place parser and guarentees that all elements, text, and attributes are persistent pointers; something your application may be able to take advantage of.

Here are links to the source code:

FastXml.h
FastXml.cpp

Updated CodeSuppository

I updated the CodeSuppository Repository on Google Code today. It includes a working version of the MeshImporter system and allows you to import meshes in a variety of formats and perform various geometric operations on them.

I need to spend more time on documentation and such, but I just wanted to get the code current.

Intel's giant screw up with the Intel Threading Library TBB

I got in a discussion on a forum about the Intel Threading Library and now that discussion turned into a rant. I have now decided to cross post that rant here to my blog. (I encourage you to read the entire thread of discussion on the Ogre3d forums, because there is a lot of interesting follow-up conversation. And, by the way, the purpose of this rant is to shame Intel into fixing their ridiculous licensing decision on a handful of header files.)

A very legitimate question to me would be, John, why did you write the JobSwarm threading library when Intel already has an awesome open source threading library called TBB?

Yeah, good question.

Here's the answer why......

-------------------------

>>This exception is actually very unrestrictive, in fact, that exception makes the licence of TBB less restrictive than LGPL. It is definitely usable in commercial applications and does not enforce GPL on your own code....

We must not be reading the same thing. According to the announcement, TBB is under GPL2. On their site they refer to a commercial version and a commercially 'aligned' version whatever that is supposed to mean. At the end of the day it is released under GPL.

Please read the GPL license located here: http://www.gnu.org/copyleft/gpl.html

It is a massive and dense document that would require an attorney to figure out. Now, I'm not an attorney but, but let me tell you this, our attorneys tell us that under no circumstances can we use any GPL code in any way shape or form in any of our projects here at work. I don't care what little 'caveat' Intel shoved into their readme file so long as it has the word 'GPL' anywhere near it, I cannot touch it at my job period.

Realize that all of the source I release is also used by me at my job. I consult with my employer and we make selective decisions as to what code we will release open source and what we will not. We release open source for a variety of reasons: generating good karma, generally being a nice guy, and hoping that we will benefit from improvements and bug fixes made by others, or from software created by others that incorporates our code.

By comparison, here is the MIT license. I don't need to provide a separate link because it is so short and sweet one is not needed. It says the source is free, do with it as you will, and don't blame me if something goes wrong. That, in my opinion, is the only license any true 'open source' project should be in. It certainly should be no more than a paragraph or two, a couple of hundred words at best, and not a massive document such as GPL.

By the way, I am not alone in my opinion on this topic. Here is a link to a developer who says almost word for word the same thing I just said. http://www.linuxjournal.com/article/5935

If you can't tell by now, I’m really annoyed that Intel has this fantastic threading library that they ‘want everyone to use’ but then release it under GPL; a license that prevents virtually any commercial software developer from using it; based on company policy if nothing else.

(WHAT IS EVEN WORSE IS THAT OPEN-SOURCE DEVELOPERS CAN'T USE IT EITHER! BECAUSE GPL IS A VIRUS AND EVEN IF MY OPEN-SOURCE PROJECT IS MIT THE MOMENT I PUT GPL CODE INTO MY PROJECT IT IS NOW INFECTED WITH THIS DISGUSTING VIRAL MEME THUS MAKING MY PROJECT USELESS!!!)

As I assume you know, it is corporate policy at virtually all companies that no GPL code can be used period. And, because of the damage GPL issues have raised, now many companies won’t allow any open source code of any kind, no matter what the license. Which makes the job of a commercial software developer a giant pain in the ass when he has to completely rewrite open source code just so that his company now ‘owns it’.

I know of one major company in particular that I do consulting for that has this restriction. I know from personal experience just how frustrating this can be. Until Intel removes the phrase 'GPL license' from TBB it will never be adopted by virtually any commercial projects.

The MIT license:

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Code Suppository Respository to move to Google Code

IMPORTANT ANNOUNCEMENT AS OF JANUARY 10, 2009!!



I will be leaving this page up, with the existing links for a while; perhaps another few months. However, the CodeSuppository Respository is officially moving to Google Code

I will be performing all of my open source development on Google code in the future and will, eventually, be removing all code from this particular page.

The first three projects released on Google code are:

JobSwarm : A lightweight, lock-free, multithreaded job scheduling system (often called ‘microthreading)

MeshImport : (Early alpha/design phase at this time) An open source plugin system designed to handle general purpose mesh data transfer between application components. Supports meshes, skeletons, bone weightings, and animation data. While similar to the OpenAssetImport library, MeshImport has a separate DLL plugin for each importer, thus making it easy for developers to create custom importers for their own projects, and allowing you to keep some importers open source and others proprietary. MeshImport is currently in early alpha, but will be getting a lot more support very soon. Another important feature of the MeshImport system is that it does not assume the data resides on a physical file on disk (a bad assumption made by the OpenAssetImport library.) One of the MeshImport plugins will, however, support the OpenAssetImport library to rapidly ramp up a lot of additional formats.


CodeSuppository: This will be the main location for the entirety of my complete collection of code snippets. They will be wrapped in a DirectX9 interactive application framework so that you can visually see and demonstrate each of the individual features. An initial release is now available which does, in fact, include almost all of the source for my various code snippets. However, I have not yet had time to write specific demo implementations for each samples. Those will come online as a I find time. There are samples for a few of the most useful, and frequently referenced, snippets on this site. Best Fit OBB, Best Fit Plane, and Convex Hull.

If you want to be a contributing member to any of these projects, please send me an email to: jratcliffscarab@gmail.com. Include your Google member name as well as information about yourself; website, qualifications as a developer, and interests. In general I will be willing to allow trustworthy and competent developers contribute to these projects.

CodeSuppository moving to Google Code

Over the coming weeks (months?) I will be moving all of my 'CodeSuppository' resources over to Google Code. If you want to be a contributor to any project, just send me an email with your Google account along with a little information about you.

So far, I have only moved the 'JobSwarm' multithreading jobscheduler to Google code. David Pangerl from the algorithms list took it upon himself to finish up the lock-free queue which now seems to be stable and working nicely.

The next task needed for the JobSwarm code base is for someone to revise the source so it will build on Linux, which would be nice.

Where is the JobSwarm project going in the future? As I begin to use it more for 'real work' in my own personal project I expect there will be enhancements and/or new component layers.

Things that might get added are:

* Job batches
* Job priorities
* Job and Job batch dependencies
* Inter-Job communication
* A lock-free tiny memory allocator for individual job processing.
* A message based system for managing the flow of control of job completion events.

The JobSwarm project is currently located here on Google code You can either sync directly to the source code using SVN or download the pre-built binary packages.

SVN: svn checkout http://jobswarm.googlecode.com/svn/trunk/ jobswarm-read-only

JobSwarm : A microthreading framework with lockless FIFO

(I'm trying to use Google Code for the first time. You can try getting the code from there at this link. Please read the latest post about JobSwarm on this site.)

I used part of my Christmas break to implement a system that I have been wanting for a long time. I call it a 'JobSwarm'. What it is, is a micro-threading library that can handle tens of thousands of extremely tiny jobs with almost no overhead.

In the sample program provided I compute a fractal by decomposing it into 65,536 individual jobs, each one representing 64 pixels of a 2kx2k image.

The usage pattern for the JobSwarm is as follows.

First, you create a JobSwarmContext. This is a single instance of the JobSwarm system. When you create a JobSwarmContext you tell it how many physical threads you want to use. You can either create a single JobSwarmContext for your entire application, or you can create different ones in various subsystems.

When a JobSwarmContext is released any currently executing jobs will have to be completed before the method can return.

To use the JobSwarm you simply inherit the pure-virtual interface 'JobSwarmInterface' and implement three methods.

They are:

job_process
job_onFinish
job_onCancel

You find this interface in the header file 'JobSwarm.h' and enclosed in the namespace 'JOB_SWARM'.

A simple example of how to use this is in 'fractal.cpp' and in the class 'FractalJob'.

The three methods are implemented as follows:

job_process : This is the actual 'work' this job is supposed to do. This code will operate in a seperate thread and, therefore, must be entirely thread safe.

job_onFinish : This is a method which is called when your job has completed. This method is invoked in the main thread (the thread which owns the JobSwarmContext). This allows you to do anything with results you may have computed during the 'job_process' call.

job_onCancel : This is a methd which is called when your job was cancelled. This method is called from the main thread.

To manage the job swarm you use the following methods on the JobSwarmContext.

createSwarmJob : This creates a single job to be processed.

cancel : This cancels a previously posted job. It is very important to note that this only marks the job to be cancelled! You cannot destruct the job until you recieve the 'job_onCancel' callback.

processSwarmJobs : This is a 'pump' loop method which is called from the main thread. This call allows completed and/or cancelled jobs to be despooled. This is a very lightweight call but if you forget to invoke it none of your job completion events will ever occur.

setUseThreads : By default the job swarm system runs using hardware threads. However, for debugging and/or performance comparison tests, it can be toggled on and off on the fly. Setting 'useThreads' to false does not close out the hardware threads themselves, it simply moves the 'work' of the individual jobs into the main thread when you call the 'processSwarmJobs' pump method.

I am releasing this JobSwarm code for a reason. First, I hope other people might adopt it and improve the code and I would, thereby, benefit from it. I was also frustrated in my efforts to find a very tiny and simple micro-threading solution by searching on the net.

This system could use some improvements. For example, in addition to needing a true lock-free FIFO, it also might be nice if it supported job priorities.

It also might be interesting to support inter-job communication, if that sort of thing made sense and/or was useful.

I am making this code available in two forms.

First, as a small console application with just a tiny amount of source code.

You can download it from JobSwarm.zip

The source included with 'JobSwarm.zip' is as follows:

fractal.cpp and fractal.h : A very simple fractal routine which can solve the fractal in a linear fashion or by breaking it up into 65,536 distinct 'jobs'.

JobSwarm.cpp and JobSwarm.h : The main JobSwarm system. Has no OS dependent code in it.

LockFreeQ.cpp and LockFreeQ.h : Provides a lock-free circular queue for a single provider / single consumer system. Also provides an API for a lock free FIFO, however the implementation currently does use locks.

main.cpp : The console demo/test app.

pool.h : A double linked list template class used by the JobSwarm to manage jobs. Minimizes memory allocations.

sgif.cpp and sgif.h : A snippet of code to save a block of memory as a GIF image.

ThreadConfig.cpp and ThreadConfig.h : A wrapper layer to hide OS dependencies for threading related calls. Intended to be multi-platform but the current implementation is only for Windows.

The second application is a larger framework called 'ThreadFrac', which provides an interactive graphics application which allows you to visually see the performance differences when toggling the job swarm on and off on multi-core machines.

You can download and install it from ThreadFrac.exe

I look forward to bug-fixes, improvements, and feedback from the development community.

Thanks,

John

--------------------- Revision update January 3, 2009 --------------

I made the following important revisions to the JobSwarm.zip download.

• I removed the source files 'fractal.cpp' and 'fractal.h'
• I revised the 'main.cpp' to act as a much simpler example program on how to use the JobSwarm system. Simply look through and/or step through the code that is there.
• I created two separate examples of how to use the JobSwarm system.
• First : One class with a callback interface is created for each separate job. This may be the most common use case but requires more setup and memory allocation in some use cases.
• Second: A single class receives callbacks for all of the 'jobs' and it uses the user data and user id field to figure out just what needs to be calculated in that context.
• I added support for a userData and userId field for jobs. This extra meta data is available as an optional additional information to pass into the job service callbacks.
• I fixed a crash bug that would happen occasionally when trying to deconstruct the JobSwarmContext
• This version was built with VC2008. If you have an earlier version of VC you won't be able to load the solution and project files. Simply create a new console app and add the source files, that is all you need to build the example program.
• 
  

Thanks to everyone who previously downloaded the sample and gave me feedback. It was all very useful.

CodeSuppository.exe : A Graphics/Demo framework for the Code Suppository Code Snippets

As promised, here is a new demo framework called 'CodeSuppository.exe'

This framework provides a graphical demonstration of various code snippets on this site.  The project installs to \Program Files\CodeSuppository

The source file \Program Files\CodeSuppository\app\CodeSuppository\CodeSuppository.cpp  is specifically designed to visually demonstrate the usage of various code snippets.  This initial release only demonstrates explicitely two snippets.  The best fit OBB routine and the best fit plane.

Over time I will revise this to include more and more demos.

---------Note: I just re-uploaded the code, and I also improved the OBB fitting algorithm.  It now uses the best fit plane technique to derive a rotation matrix to fit the point cloud and then only rotates the points on a single axis of rotation to converge to the best fit solution.  

How to use the OBB fitting code

I have received a number of emails from people who are confused about how to use my various code snippets. 

I have decided that, in the future, I am going to present my code snippets in the form of a single large graphics application.  At first you might think this defeats the purpose of the 'snippets' concept, but really I don't think it does.  The code will still be in snippet form, but will come packaged in a framework that demonstrates the usage pattern.

For example, some poeple have complained that my OBB fitting code doesn't work.  I know this is not true, because I use the OBB fitting routine in production code all of the time.  It's most likely they are just using the routine incorrectly.

But placing the code snippet in a graphics framework, I can actually draw a point cloud and the resulting OBB produced so that people can get a clear visual demonstration that it is, in fact, working.

Sometime in the next couple of weeks I will be uploading my code snippets in this single package format.

A lot of the math based code snippets are now folded into a single piece of source called 'FloatMath'.   The design of FloatMath is that, even though it is a single large source file, individual code snippets and routines can be extracted from it.  Or, you can just use the whole file if you prefer.  It is turning out to be an excellent reference for a wide variety of math and geometric computation routines.

The FloatMath library has been refactored so that it supports both 'float' and 'double' types of all of the routines.  

It is comprised of three source files.

FloatMath.h         : which contains the prototypes for all of the routines.

FloatMath.inl       : which contains the conditionally compiled implementation

FloatMath.cpp    : which includes FloatMath.inl twice to produce both the 'float' and the 'double' implemnetations of each method.

I have also uploaded a small zip file that shows how to call the OBB fitting routines.

obb.zip

---------Note: I just re-uploaded the code, and I also improved the OBB fitting algorithm.  It now uses the best fit plane technique to derive a rotation matrix to fit the point cloud and then only rotates the points on a single axis of rotation to converge to the best fit solution.  

Instant Messaging API code snippet

On the post I made yesterday I presented a code snippet for sending an email in your application. Today I am including a code snippet that lets you send and receive messages using an Instant Messaging application.

All this snippet really does is provide a simple and convenient wrapper for the AIM Developer SDK. I have read the license that is included and it seems pretty open and allows for the redistribution of source and binaries.

The wrapper is provided with a single header file and single CPP for implementation as all true snippets should be. However, since it is dependent on the AIM SDK it does require the AIM SDK header files, link libraries, and run-time DLL components (all included in this download).

This download includes a fully built executable console chat-client as well as the source code and project files to build it. Obviously this is a Windows only feature (as was the SendMail submission yesterday).

The wrapper uses a version of the PIMPL pattern that I have become pretty happy with. It exposes just two standard C style methods, one to create an 'InstantMessage' interface and one to release it. The pointer you get back is a pure-virtual interface that only exposes the public methods and nothing more.

When constructing the InstantMessage system you will need to pass a pointer to an 'InstantMessageInterface' so that you can receive incoming messages. You will also need to pump the InstantMessage class to give it a chance to process incoming messages and state change events.

The public interface is completely generic and could, theoretically, be mapped to other instant messaging systems. The main use-case for this implementation is for server status monitoring. I am using it to have live servers fire of chat messages to me based on state changes and other important events.

Here is a link to the the zip file containing the source code, binaries, and everything you need to embed instant messaging capabilities (using AIM) in your application.

Here is the header file for the Instant Messaging wrapper layer
------------------------------------------------

#ifndef INSTANT_MESSAGE_H

#define INSTANT_MESSAGE_H

// This is a wrapper API to handle instant messaging on top of AOL instant messenger or AIM
// Requires the AIM instant message SDK to build.
//
// Please be aware of all of the licensing issues associated with using the AIM SDK
//
// This wrapper was written by John W. Ratcliff. Please send bug-fixes feedback to jratcliff@infiniplex.net

enum InstantMessageState
{
IMS_NONE,
IMS_OFFLINE,
IMS_DISCONNECTED,
IMS_QUERYING_DCS,
IMS_CONNECTING,
IMS_CHALLENGING,
IMS_VALIDATING,
IMS_SECURE_ID,
IMS_SECURET_ID_NEXT_KEY,
IMS_TRANSFERRING,
IMS_NEGOTIATING,
IMS_STARTING,
IMS_ONLINE,
IMS_WILL_SHUTDOWN,
IMS_SHUTDOWN,
IMS_PAUSED,
};


class InstantMessageInterface
{
public:
virtual void notifyInstantMessageState(InstantMessageState state) = 0;
virtual void receiveInstantMessage(const wchar_t *from,const wchar_t *message) = 0;
};

class InstantMessage
{
public:

virtual bool connect(const char *userName,const char *password) = 0; // connect using this user id and password.
virtual bool disconnect(void) = 0; // dissconnected
virtual bool pump(void) = 0; // pump the instant message system on this thread, handles event processing.

virtual const char * getInstantMessageStateStr(InstantMessageState state) = 0; // conver the instant message enum into a string.

virtual bool sendInstantMessage(const wchar_t *userId,const wchar_t *msg) = 0; // send an instant message to a buddy (unicode string)
virtual bool sendInstantMessage(const char *userId,const char *fmt,...) = 0; // send an instant message to a buddy using the printf style syntax

};


InstantMessage * createInstantMessage(InstantMessageInterface *imi);
void releaseInstantMessage(InstantMessage *im);

#endif

SendMail : Send mail using embedded Blat

I am uploading today a code snippet of somewhat questionable value. This is a true snippet, in that it is composed of a single .CPP and .H file. In a simple one line API call you can send an email from your code. You can download the source, project, and executable using this link SendMail.zip

My specific use case for this is that I need to be able to get notifications from a remote server when it is in a bad state. What I really want to do is just send an instant message. However, after searching the Internet, I realized that it was going to be extremely difficult to find a true code snippet which could do such a thing. Theoretically Jabber would allow me to do this, but all of the source code libraries for Jabber are simply massive and include insane amounts of graphics/UI code. Even the one or two console versions of Jabber are still overwhelming.

If anyone knows of an implementation of an instant messaging API that allows me to simple use the form of send message 'from' this person 'to' this person with 'this subject' and 'this text', that would be awesome.

In the meantime I have resorted to sending emails. Blat is a simply awesome full public domain console email program. You can use it either as a console executable or as a DLL.

What I have done is created a single CPP file that not only provides a simple wrapper routine to send an email but also contains, embedded within it, the Blat DLL. Simply add this one CPP and header file to your project and you can transmit an email message in your program.

The DLL is loaded directly from memory, not from a file on disk, using the routing MemoryModule written by Joachim Bauch. See his full article here.

Like I said, this may be of questionable value but if you are looking for a completely turnkey way of just sending an email from inside your program this will do it. You could always just add the blat source code to your project, which is an entirely viable option, but there is a lot of source in Blat and this form might be easier to use.

The file 'SendMail.h' provides two methods. The first is as follows:

bool sendMail(const char *mail_server, // mail server to use for sending the email message.
const char *from, // email address of the sender
const char *to, // email address to send to.
const char *subject, // the subject line of the email.
const char *body, // the body text of the email.
const char *attachment); // an optional attachment file.

The second option is to just invoke the Blat dll function directly. In which case you will need to familiarize yourself with the full Blat command line interface which has a lot of options.

bool sendBlat(int argc,const char *argv[]); // refer to the Blat documentation for the full set of command line arguments.

Another cool way to use this program is to send SMS text messages to your mobile phone.

Sending SMS through email is very, very easy. If you can be reminded through email, you can now be reminded through SMS.

If you know the correct email address, you can also send these messages to your cellular phone. Here are the email addresses for the 6 most popular cellular phone carriers:

T-Mobile:phonenumber@tmomail.net
Virgin Mobile:phonenumber@vmobl.com
Cingular:phonenumber@cingularme.com
Sprint:phonenumber@messaging.sprintpcs.com
Verizon: phonenumber@vtext.com
Nextel: phonenumber@messaging.nextel.com

where phonenumber = your 10 digit phone number

D3DXQuaternionRotationYawPitchRoll

I am going to refrain from a full blown rant here. That said, I cannot reiterate enough how f**king annoying it is that Microsoft goes as far out their way as possible to make it difficult for people to develop multi-platform code using their tools. When Microsoft released Visual Studio 2005 and had the unmitigated gall to issue a warning message for 'printf' I about blew a gasket. Now my code is littered with '#pragma warning(disable:4996)' to prevent VS2005 from throwing warnings everywhere for 100% perfectly ANSII C compliant code!!!!!!!!!!

Another problem we encounter is when people start using the D3DX library; which is not provided with source code. Recently I have needed to refactor some source that made use of the D3DX library for various math routines.

One problematic routine in particular is 'D3DXQuaternionRotationYawPitchRoll' which, for whatever reason, and at this point I don't even care, Microsoft implemented in a non-standard way. Since you don't get source code to D3DX there is no easy way to figure out what they did (turns out they flipped a couple of signs during the computation). Stepping into the disassembly just uncovers a whole bunch of cryptic SSE instructions that are not that illuminating.

Finally a very helpful Microsoft engineer posted the solution on the DirectX mailing list. I am going to repost the solution here so that anyone else who ever needs to know the formula has it.

Here is the correct formulation for D3DXQuaternionRotationYawPitchRoll.

----------------------------------------------------------------

void QuaternionRotationYawPitchRoll(float yaw,float pitch,float roll,float quat[4])
{

float sinY, cosY, sinP, cosP, sinR, cosR;

sinY = sinf(0.5f * yaw);
cosY = cosf(0.5f * yaw);

sinP = sinf(0.5f * pitch);
cosP = cosf(0.5f * pitch);

sinR = sinf(0.5f * roll);
cosR = cosf(0.5f * roll);

quat[0] = cosY * sinP * cosR + sinY * cosP * sinR;
quat[1] = sinY * cosP * cosR - cosY * sinP * sinR;
quat[2] = cosY * cosP * sinR - sinY * sinP * cosR;
quat[3] = cosY * cosP * cosR + sinY * sinP * sinR;
}

Code Snippet to Render a 3d oriented Arrowhead for debug visualization

Today in true code-snippet form I am releasing a handy little debug function that will generate an oriented 3d arrowhead as 24 triangles. This routine will properly orient the arrow head so it faces the correct direction of the line segment it is associated with.

The API is implemented as a single function call that accepts a starting and ending location, and a size for the arrow head. It returns the triangle count and a const float pointer array of triangles as nine floats, x1,y1,z1, x2,y2,z2, and x3,y3,z3. Simply pass these triangles off to your favorite debug rendering library and you will get nicely formed and oriented debug arrow heads that make visualizing ray segments much easier.

The image above shows the debug visualization of the arrow head in my split mesh tool. Note that the interior of the arrow head is slightly hollowed out, which improves the debug visualization in my opinion.

The source files can be downloaded here:

ArrowHead.h
ArrowHead.cpp

SplitMesh in development release

I have just uploaded an extremely early developer release of my SplitMesh tool. You can download and install it using this link.

Let me give you a really quick walk-thru. The download is only about 8mb and comes with a handy Windows installer. Once it is installed, go to the start menu and run SplitMesh.exe

Once the program has started up you will see a series of yellow concentric circles on the screen that represents the current split plane. You can move the split plane up and down using the Plane-D offset slider. You can also use the combo box to change the main axis of the split plane. Even though this demo just lets you set up the X, Y, and Z axis, the code doesn't care what the plane equation is. On a future drop I will have some sliders that let you freely orient the split plane on all axes.

The next thing you need to do is import a Wavefront OBj file to experiment with. I have provided several with the install. Simply browse to "\Program Files\SplitMesh\media\PhysXViewer"

You might start by loading the file 'sphere.obj'. The character model 'beshon.obj' (pictured above) is also interesting to play with.

There are a number of checkboxes that allow you to selectively turn on and off the various visualizations of the exploded split mesh.

This release has the source code in it but, as I said, it is still in an early stage of development and does not represent what the final source will look like.

The finished version will be provided as a single CPP file which will allow you to split any mesh into two perfectly capped/closed meshes in a single API call.

This version has a number of bugs in it which I am still working on. I just released this build because it is kind of fun to play with the interactive visualization of the split mesh.

Right now my main blocking points are:

(1) Sometimes when I walk the edges to come up with perfectly matched polygonal rings, it fails. You will see this indicated at times when the split mesh is not properly capped.

(2) This version does not yet deal with holes. An example of a whole would be if you cut say a drinking glass in half. This is still a major todo item.

(3) Sometimes it classifies convex polygons as concave; I'm not quite sure why yet.

In the visualization if you see a capped surface in green, this indicates that it the polygon was properly identified as a convex surface. The triangulation will fan out from the center of the polygon.

If you see a split surface colored in a more reddish tint, this indicates that the polygon was detected as being concave and was sent through a more robust triangulation routine that can handle this case. I note that there are some cases where I still flag convex polygons as concave; I haven't quite figured this one out yet.

Here are the features I intend to add to the tool and the order of their release.

Release version #1:

(1) Should handle all cases for split meshes *without* holes.

(2) Will come with a single CPP file 'SplitMesh.cpp' and a header that prototypes a method that will allow you to split a mesh by a plane in a single function call.

(3) Will come with a simple console application 'SplitMeshObj', which will read a Wavefront OBJ file in, split it by a plane, and write two Wavefront OBJ files out. The only source required will be SplitMeshObj.cpp, SplitMesh.cpp and SplitMesh.h

(4) It will include the full interactive graphics demo as above to experiment with your own meshes.

(5) It will include a revised copy of the ConvexDecomposition library which will use the new SplitMesh routine to produce much more efficient and effective convex decomposition solutions.

Release #2

(1) Will handle splits with holes.

(2) Will allow the user to add perlin noise to the split surface to create jagged or rough edged splits.

(3) The convex decomposition library will be revised to return not only the convex hull pieces, but also the corresponding fracture graphics.

Release #3

(1) Will add support for textures, U/V co-ordinates, and user provided per-vertex interpolants.

(2) Will be integrated into the Nvidia PhysX SDK to demonstrate real-time fracture of graphics models, using the convex decomposition library and the create dynamics toolkit.

SplitMesh

Just a heads up about something I am working on. I am pleased that my convex decomposition library has been useful for some developers. However, one thing has really bugged me about that tool since it was never really finished. In the current version, when the decomposition process occurs, I do not create closed meshes. Because of this, as you recurse deeper trying to find the optimal solution the algorithm ends up converging on the interior sections of the splits, thereby creating a hollow objects.

Clearly this is not the desired result in the general case. If each split were treated as a closed mesh, then you could recurse more deeply and converge more accurately towards an optimal solution. I never got around to finishing this step but, this week, I am going to take another crack at the problem.

The main reason I maintain a 'code suppository' is so that I can insert code capsules in the anus of the Internet (otherwise known as Blogger) as an attempt to repay the development community for the massive amounts of source code I have begged, borrowed or stolen in the past.

In that vein, I always try to find something suitable in the public domain before I resort to the painful process of coding it myself. However, in all of my searching I have yet to find a simple routine (i.e. a 'snippet') which you can submit a triangle mesh and a splitting plane and get two closed meshes as a result.

I did find an excellent published paper on the topic and I intend to code my implementation fairly closely to it. I sent an email to the paper's author, asking him if he wouldn't mind just 'giving' me the source code but this blatant attempt at begging resulted in a deafening inbox silence.

At this point, I'm looking forward to just writing it myself as I am kind of excited about implementing it as a true source code 'snippet'.

In addition to improving my convex decomposition library the split mesh routine will also prove invaluable for implementing real-time fracture. While the convex decomposition process will produce excellent physics models for fracturing objects, you are still left with the technical challenge of producing the fractured graphics model to match; replete with jagged edges where the object has been smashed in two.

My idea is that first I will perform a clean plane split producing two closed meshes nicely sliced. I will then take the polygonal surfaces at the slice boundary, project them into 2d, tessellate the surface, and apply a perlin noise function on it. Finally I will apply U/V coordinates and map a nice looking texture that represents the internal surface of the broken object.

This should produce nice rough looking broken surfaces and by tweaking the material properties, UV mapping, and perlin noise function can be made to look like broken rock, or jagged edges, whatever your artist might design.

I hope the implementation will be fast enough that this process can occur in real-time and allow for interactive fracture of dynamic objects in a game.

Again, I plan to do this little project entirely open source and public domain, so I have only two questions.

(1) If you have already written something that does this and are willing to share, save me some time and let me know!?

(2) If you find the code useful, won't you do something nice for me? Karma only works if you pay it forward from time to time.

I will be at the ION conference in Seattle next week to give a presentation. I hope to visit with some of you then.

Compression / Decompression : Comparing Apples to Apples

With pretty much every developer there comes a time when you need to use a compression library; not because you want to ‘zip’ up a massive archive but more because you want to compress some game data on the fly before you transmit it over the network, or to shrink the size of a local cache or something. And, like pretty much every developer, you end up wandering through a maze of open source libraries on the internet, each of which has entirely different API, source code layout, and license agreement. Just figuring out to call ‘compressData’ (if you even can) is often hours of wading through documentation and dealing with build/configuration issues.

For your convenience I am releasing a small code snippet that I wrote when I was trying to evaluate a replacement compression library than the one we are currently using. The simple fact of the matter is that I don’t believe any other programmer should have to waste the same amount of stupid time I did wrestling these libraries into a convenient form.

http://www.amillionpixels.us/test_compression_1.0.exe

Here is the complete API to my wrapper interface:

// Block compression/decompression library wrapper by John W. Ratcliff http://www.codesuppository.blogspot.com/

enum CompressionType

{

CT_INVALID,

CT_CRYPTO_GZIP, // The CryptoPP library implementation of GZIP http://www.cryptopp.com

CT_MINILZO, // The MiniLZO library http://www.oberhumer.com/opensource/lzo/

CT_ZLIB, // The ZLIB library http://www.zlib.net/

CT_BZIP, // The BZIP library http://www.bzip.org/

};

void * compressData(const void *source,int len,int &outlen,CompressionType type=CT_ZLIB);

void * decompressData(const void *source,int clen,int &outlen);

void deleteData(void* mem);

CompressionType getCompressionType(const void *mem,int len);

const char *getCompressionTypeString(CompressionType type);

};

This release supports four open source compression libraries. The CRYPTOPP implementation of GZIP, MINILZO, ZLIB, and BZIP.

This API simply supports block memory compression and decompression. You can compress a block of memory using any one of the four compressors. The compressed memory has a small header on it that indicates which compressor was used, the size of the uncompressed memory block, and a CRC so that it can easily and safely decompressed.

The test application, called ‘test_compression’, loads a roughly 10mb XML file and runs it through each compressor and decompressor and measures the performance characteristcs of each. The results are as follows:

Testing Compression rate and speed with various compressors.

---------------------------------------------------------------

Compress:CT_CRYPTO :FROM: 10,436,335 TO: 2,498,433 23% 1,170 MS

Compress:CT_MINILZO :FROM: 10,436,335 TO: 3,940,072 37% 97 MS

Compress:CT_ZLIB :FROM: 10,436,335 TO: 3,299,771 31% 157 MS

Compress:CT_BZIP :FROM: 10,436,335 TO: 2,270,695 21% 1,544 MS

---------------------------------------------------------------

Testing Decompression speed with various decompressors.

---------------------------------------------------------------

Decompress:CT_CRYPTO :FROM: 2,498,433 TO: 10,436,335 258 MS

Decompress:CT_MINILZO :FROM: 3,940,072 TO: 10,436,335 42 MS

Decompress:CT_ZLIB :FROM: 3,299,771 TO: 10,436,335 69 MS

Decompress:CT_BZIP :FROM: 2,270,695 TO: 10,436,335 390 MS

As expected, MINILZO is the fastest. Unfortunately MINILZO uses a GPL license and cannot be used in commercial products. The rest have licenses which are more flexible. Check the links for each package to see if it is right for you. I did include the ‘CryptoPP’ library for completeness though but, to be frank, I am not very impressed with this package as the compression and decompression rates are very poor. As you would expect BZIP gets the best compression rate but does not perform as quickly.

I am fairly impressed with ZLIB, especially because you can use it in a streaming mode as well, which is excellent for network communications layers. (FYI, the assembly language version of the ZLIB decompressor is hardly any faster than the optimized C code and was not included here.)

You might wonder why I’m even bothering to post this little snippet. Beside the fact that I hope to save other programmers a little bit of time in the future, I encourage any other developers of compression libraries to drop them into this framework so we can stop comparing apples to oranges when it comes to these technologies. A large XML file is a typical use case for the kind of data a game developer might want to squeeze out some space savings for. I am also happy to modify the installer and include more standardized sample data if that is relevant.

I started to add in support for the LZMA library, however they only offer a simple sample decompressor while the compression code is a lot more difficult to extract into a single C style API call.

This demo comes with an easy to use installer and a solution and project file for visual studio 2005. All of the compression code itself is multi-platform and only the little demo app makes any OS specific calls. The libraries are each included as raw source, each located in their own directory. None of the source has been removed (except for test code) so you are not required to use the compression libraries via the wrapper layer.

If anyone feels compelled to add additional compression libraries to this test framework please let me know and I will make a point to include it in a new drop.

Thanks, I hope somebody finds this useful.

John

Spatial Awareness System

This is the first release of my Spatial Awareness System on March 13, 2008. (The download is small (200k) and includes a basic installer.)

A 'Spatial Awareness System' is a tool which keeps track of relationships between a large collection of objects represented by 3d co-ordinates (as floats).

The typical use for a spatial awareness system (SAS) is for AI and network traffic culling. In AI you may have a limited range that the entity is supposed to be aware of. Take for example a gun turret with a limited sight distance. The awarness system will automatically collect the set of objects which are within this range. The AI code can either iterate over this awareness list directly or respond to discrete events when objects come into and out of the awareness range.

For network traffic you may want to reduce bandwidth by only transmitting packets for objects that are within a certain distance relative to other objects in the world.

To use the spatial awareness system simply #include the file 'spatial_awareness_system.h'

Spin up an instance of a spatial awareness system by using the factory method.

Example: SPATIAL_AWARENESS_SYSTEM::SpatialAwarenessSystem *sas = SPATIAL_AWARENESS_SYSTEM::Factory::Create(strategy,this);

'strategy' is one of three possible spatial awareness system implementations to choose from. They are:

SAS_BRUTE_FORCE : Implements the brute force N-squared approach where every object is compared to every other object each frame. This is very slow and only used for testing purposes.

SAS_LAZY_KDTREE : Uses a KdTree to help maintain the awareness state. It is called 'lazy' because the KdTree is only updated every 16 frames. This can produce some infrequent false negatives but never false positives.

SAS_SAP_SYSTEM : Uses Pierre Terdiman's Sweep and Prune algorithm (www.codercorner.com) as the main engine for maintaining awareness.

The 'this' pointer refers to an implementation of the SpatialAwarenessObserver pure virtual class that will receive event notifications as objects enter and leave awareness.

The objects for which awareness is being maintained are referred to by a unique 64bit guid. If you wish, you can cast an object pointer to this GUID if necessary.

The test application is located in the directory 'SphereTest'. Simply load 'SphereTest.sln' into Visual Studio. (There is nothing windows specific about the code, other than the demo app, and the spatial awareness system itself should theoretically compile and run on any OS.)

After you build and run the application you can hit the 'R' key to toggle the visual display of the awareness data. Rendering is disabled by default since simulations with extremely large object counts can take a long time to display.

Pressing the 'M' key will write out a text file called 'sas_memory.txt' that shows all memory allocations performed by the current SAS

Press ESC to exit the application.

The command line argument passed in controls the number of objects to be simulated. A maximum of 65535 objects are allowed. For real-time visualization it is best to keep the count under 2,000 otherwise rendering is too slow and the number of connections fill the screen. Simulations on the order of tens of thousands of moving objects runs surprisingly fast. Objects with an awareness range of zero do not maintain awareness of other entities, yet, other entities are aware of it.

To experiment with the demo program you need to load the file 'ENTITY.CPP' and make some small code changes.

The first #define EVENT_BASED controls whether the objects are rendered by iterating the awareness, or by tracking create/delete events. Iteration is much faster but the option is there to debug that all of the create/delete events are being handled correctly.

The next #define ALLOW_DELETES controls whether objects are constantly created and deleted.

The next line defines which of the three SAS strategies to employ.

The #define LIFETIME controls the random lifespan given to objects which are being created/deleted.

I would consider this kind of alpha software at this point.

The brute force and lazy kdtree versions seem to be stable and work correctly in all test conditions.

The Lazy KdTree is fairly high performance and doesn't have performance or memory issues except in pathological cases where every object is nearly aware of every other object.

The sweep and prune implementation appears stable, high performance, and has a reasonable memory footprint. In this release, there appears to be a glitch or two when object deletions are enabled. I am still tracking this down.

The reason I am releasing this code is because, first it is built upon some other open source code and I felt it only fair to make it available. The second, and most important reason, is that I am looking for feedback, bug fixes, improvements, suggestions, and anything else I can learn from the rest of the development community on solving this particular problem.

For questions or feedback, please write to:

John W. Ratcliff
mailto: jratcliff@infiniplex.net

FIRST Robotics

My son, Alex, is a freshman in high school and just joined the FIRST robotics team. The robotics team is right now in the big competition season rush. I really cannot understand why they only give these guys six weeks to produce a complex robot but that is what the rules are.

I have decided to help out the team by mentoring students who are focused on computer programming. Since I already have a coding snippets website, I look forward to posting some snippets of robot control code here in the future.

Right now I'm just getting my feet wet trying to understand the whole development environment process for the robotics controller but once I get the hang of it I hope to be doing some innovative stuff soon.

DFRAC alpha release : An Interactive Mandelbrot Explorer Program

Over the holidays I worked on a Mandelbrot exploration program. This is an alpha-pre-release. It requires a Windows machine with DirectX 9 to run. You may not be able to see the 3d graphics view on some older graphics cards. You can install the program using this link. It is only a 2mb installer. This does include source code, but much more work is expected to be done on it.

Dfrac_1.0.exe

You can read the documentation online at this link: Dfrac.htm

Here are some screenshots from the program, showing some 3d and 2d views.

Fast A*Star implemenation by Justin Heyes-Jones

Justin Heyes-Jones has a great implemenation of the AStar path finding algorithm on the Internet. He is an AI enthusiast and has contributed a lot of resources to the development community. You can find his website here.

When I decided to evaluate Justin's Astar implementation I found nothing wrong with it and went ahead and did a full integration. The only thing I did change was to make a wrapper interface around his heavily templated class. This is purely a matter of programming style. I like to use pure-virtual interfaces wherever possible and hide the implementation details behind a set of simple C calls using the PIMPLE paradigm (pointer to implementation).

My wrapper is prototyped in the following simple header file: FastAstar.h

The implementation which includes two template classes by Justin embedded as well as my own wrapper code can be found here: FastAstar.cpp

Justin uses a fast allocator template when implementing the Astar algorithm and the performance is extraordinarily fast.

MeshCleanup

This post presents a generally useful code snippet. It deals with a fairly common problem of trying to clean up a potentially bad triangle mesh. Here is what it does:

(1) Detects duplicate triangles and removes them.
(2) Detects degenerate triangles and removes them.
(3) Detects double sided triangles and extrudes them into a solid shape.

The implementation is fast because it uses a hash_map to avoid having to iterate comparing every triangle winding order to every other triangle.

Simply pass it an indexed triangle mesh in and you get a cleaned up indexed triangle mesh back out.

Here is the source:

MeshCleanup.h
MeshCleanup.cpp

It requires a few of the snippets previously uploaded to compile. They are:

VertexLookup.h
VertexLookup.cpp
FloatMath.h
FloatMath.cpp
IntPtr.h

FloatMath revisited

Ever since I started doing this snippets thing I have been creating a floating point math library that does not have dependencies on any templates or classes. This library uses a flat C style interface and accepts only float pointers as inputs and outputs.

This library has not been created for completeness or thoroughness. Instead, I am adding one routine to it at a time on an as needed basis. As it grows it is slowly becoming an awesome reference implementation for lots of common basic math operations.

I will be sure to keep updating it as time goes on. Here is the latest incarnation.

FloatMath.h
FloatMath.cpp

Vertex Lookup Revisited

I made a post about this previously on this web log. After making my original post I received some feedback about some problems with my approach.

I believe I have no addressed those issues and I am uploading a new implementation. It shares the same API but is implemented in a completely different way.

The purpose of this routine is to weld vertices together when building an indexed triangle list. The brute force way to do this is to iterate through all previously defined vertices and measure the distance to each and return as matching only those vertices which are within the distance threshold supplied. My previous technique of using delta x, delta y, and delt z, comparisons does not entirely work doe to certain edge conditions. The only valid way is to perform a true range based search.

Since this is exactly what a Kd-Tree does, this new implementation uses a Kd-Tree to compute the array indices. I have been using it this past week on some heavy duty meshing code and I am confident that this takes care of all edge conditions.

VertexLookup.h
VertexLookup.cpp

KdTree for fast range searching

There are a lot of sources on the Internet for Kd-Trees and here is just one more. I don't suppose there is anything all that special about my Kd-Tree implemenation but if you just need one ready made, go ahead and use it.

I don't support removing objects from the tree. I will have to do some research on that. A Kd-Tree can be built pretty fast though and, in the past, I have just rebuilt them from time to time to take into account changes.

Kd-Trees are an ideal data structure for fast range searching. One important note when building a Kd-Tree is that you should insert your nodes more or less at random if they might possible have any ordering in them to begin with.

This Kd-Tree implementation is hard coded for three dimensions of space. To declare it you simply would do the following:

KdTree mTree;

To add elements to it you simply would do as follows:

mTree.add(x,y,z,radius,myData);

The 'radius' represents the radius of the object you are inserting. For a point, just set it to zero. This first upload doesn't do anything with the radius yet, but I will revise it later.

The 'userData' is a pointer to the object that is being represented or you could cast an integer if it represents an array index.

To find the closest object to a point call 'getNearest'.

To find the N number of closes points, in sorted order, call 'search'.

Here is the implementation. KdTree.h

Hash Map stdext::hash_map

I know I haven't posted anything in a while; what can I say, I've been busy. Recently I had to turn in a deadline for a book chapter in AI Wisdom 4. In doing so I wrote a few new snippets and I thought I would take this afternoon to publish them.

The first snippet is just a simple template class that demonstrates the most common usage of an STL hash_map. Semantically a hash_map works pretty much just like a regular STL map but instead of using a red-black tree it maintains a hash table which allows most lookups to be retrieved in a single step. So long as you don't need to retain a specific ordering for a container, simply needing fast random access, then a hash_map is always the best way to go.

Pretty much the most common usage of a hash_map is to associate some integer key (often a GUID) with a pointer to a class. I made a small template that implements this most common usage in a fairly simple API. It is called 'IntPtr'.

For example, if you wanted to map a set of integers to a set of pointers to a class called 'Foo' you would declare it as follows:

IntPtr<> mFooHash;

To look up an instance of class Foo by a value you would say: Foo *f = mFooHash.get(v);
To make an association between a Foo pointer and an interger it would be:

mFooHash.set(foo,v);

To iterate the container you would say:

Foo *f = mFooHash.begin();
while( f )
{
f = mFooHash.next();
}

There is no specific destructor for this template and it assumes you own the memory associated with the 'Foo' pointers. You must remember to destruct them yourself. There is another version of the template called 'IntInt' which just provides a mapping between one integer type and another.

I have been informed, by someone I trust knows what he is talking about, that you can use 64 bit long integers in an STL hash_map and they are guaranteed to be unique. This can be quite useful when associated very large GUIDS with pointers to a class.

If you have never messed around with the STL hash_map container this is a good place to begin experimenting with it. It is a very powerful container and is extremely fast.

Here is a link to the source and I will also update the repository page.

intptr.h

The Code Suppository Repository

Even though I like the idea of having a coding Blog it has become clear that this is a terrible way to actually provide software.

I had to stay home from work this morning because we are getting new carpeting installed. Since I had some free time I finally got around to a task I have been wanting to take care of for a long time. Today I created 'The Code Suppository Repository'. This is a simple web page that contains links to *current* versions of all of the code snippets I have posted on this blog. I made sure that all of the links are current and hyperlinked each piece of software with it's corresponding blog entry. They are listed in chronological order as they appeared on this site.

Probably the most important thing is that I revised every piece of source to be current with the latest versions I maintain for myself. One question I had was what to do about the dead links the in the previous blog posts, or the posts which relate purely to earlier releases of software that are no longer relevant. I have decided to just leave the blog the way it is but, from now on, always use the provided download page to get the latest version of anything.

This was enough work just for today, but I fully intend to keep posting code snippets in the future. Maybe I'm the only one who finds them valuable, I don't know, but personally I couldn't get much done without my collection of 'snippets'.

As for the CreateDynamics release. I don't expect to see a new releases any time soon. I don't have the bandwidth at this time. Nevertheless, the release I have up here is functional to the extent that it demonstrates most of what I presented at GDC and I think that is good enough for now.

One final time, here is the permanent location for 'The Code Suppository Repository'. Always use this to get the latest version of any code snippet or application.

New release of CreateDynamics with an installer

I was finally able to scrape together of an installer for CreateDynamics to go along with my GDC presentation. This is only a 7mb download with a full installer!

Before you can run the executable you must have a recent version of DirectX 9.0 on your machine.

You must also have a copy of the Ageia PhysX System Software. You can download it from their site, or use this local link.

To build the source you must have the October 2006 DirectX 9.0 SDK installed to the default directories.

You must also have a copy of the Agiea PhysX SDK 2.4.4 or 2.7.0 installed.

I haven't provided a build configuration for 2.6 but all you have to do is change some include paths. The 2.7.0 SDK introduces the soft body feature and I am hopeful it will be part of the public release soon.



To extract and use just the CreateDynamics plugin and/or the ConvexDecomposition source library requires neither.

Please read the release notes after you install.

This demonstrates how to generate multiple collision model versions from a single art asset, including static representations, convex decomposition, ragdolls, fake softbodies, and pre-fracture assets.

The tool needs a ton of features as well as bug fixes. It doesn't currently support cloth or tetrahderal soft bodies. The tetrahedral soft bodies are demonstrated in the 2.7.0 SDK release.

I will update these as I make bug fixes and/or find the time.

Update should be ready to release tomorrow

Today I got the project revised so that it can generate the following versions of physics assets automatically:

Raycast
Static
Dynamic
Compound
Fake Soft Body
Pre-Fracture
Ragdoll

For now I do not have cloth and softbodies hooked back up again. If you want to play around with the soft body stuff, then just get the 2.7.0 SDK from Ageia and check out the sample application called 'PhysXViewer'.

The only reason this drop isn't uploaded now is that I need to create an installer. The open-source component of this project is embedded within a much larger proprietary system that is being developed for my employer. In the past I have found it way too much of a hassle to manually extricate an open source build from this larger code base.

Sometime tonight or tomorrow I will create an installer script that cherry picks only the open source components and will provide a proper installer with the basic features you would expect.

This first drop is still a little rough around the edges but it does showcase the techniques I presented at GDC and is open source.

Over the upcoming months I will continually refine the user interface and code base, as well as provide documentation.


Here are the slides. First as a small download, this contains just the slides and the exact spoken text of the talk in a Word Document file.

http://aarm.mywowbb.com/~jratcliff/GDC2007_SMALL.zip

To download the slides with the accompanying video clips use this link. Download size approx. 100mb

http://aarm.mywowbb.com/~jratcliff/GDC2007.zip

I'm back from GDC

I just got back from GDC. My presentation went very well. Even though it was the last talk on the last day, my room was completely full and people were standing all along the walls. I was really pleased to find out that David Wu came to my talk, sat through the whole thing (which I presumed sounded like sitting in a Kindergarten class to him) and then even came up and gave me some personal feedback at the end!

I number of people I know only via email and phone calls were there and I was really sorry I didn't have more time to chat with them. Since my talk was on Friday, and my I was under major GDC crunch for my employer the week before, I ended up having to use almost all of my time at GDC working on my presentation. I didn't finish it until 1pm the day of the talk! I didn't get to see a single presentation the whole week and only breifly got to walk the show floor.

In addition to getting my presentation done I felt it was really important to provide a new release of the CreateDynamics toolkit that would immedaitely show off everything I was talking about. I got really close, but not quite all of the way.

I hope to have a new upload sometime this week.

Heading to GDC

I'm heading out to GDC today. I will be giving a presentation on Friday at 4pm about the work I have done on CreateDynamics. It is my intention to upload a new code drop by then.

Unfortunately I have been equally busy at my job getting things ready for GDC so I haven't had much time to work on the software. The entire framework is getting completely refactored using a plug-in architecture as well as taking advantage of Project Builder for build management.

It is, in many respects, a lot better than any of my previous releases. On the other hand, many things that used to work are now broken. The code is all still there, but it has to get refactored to fit into the new framework cleanly.

Right now I plan to spend most of GDC week sitting in the speakers lounge working on both my presentation as well as the software upload. If it turns out I am unable to get a new software drop out, then it will have to wait until I return from GDC to get it uploaded.

I am hopeful I will be able to get this new version released this week and quickly follow up with some improvements going forward. I will explore the idea of setting up a 'Source Forge' page to make it easier for people to locate code drops.

Thanks,

John W. Ratcliff
Cell phone: 314-276-2180
Skype Phone: 636-486-4040
IM (skype preferred): jratcliff63367
Same handle applies for Yahoo and AOL IM
Email: jratcliff@infiniplex.net

TinyXML

Well, I made my previous post about the 'FileInterface' wrapper class but I don't think anyone understood why it was useful; so, I'm going to try again.

This time I'm uploading the actual use-case I created it for.

TinyXML is an absolutely awesome open-source 'code snippet'. You can find the official site here.

This is a modest amount of multi-platform source code, using no STL containers, that is robust, fast, stable, and provides an excellent way to load, modify, and save XML files. It doesn't support XREF's but, other than that, it is incredibly useful.

The only problem I found with TinyXML is that it couldn't read or write to a buffer in memory. All of the code uses standard ANSI file-io routines ('fputc', 'fprintf', etc.). Rather than trying to dramatically modify the implementation I simply performed a global 'find-replace' on all of the file-io calls to revector them to my previously posted 'FileInterface' code snippet.

This upload includes the modified TinyXML that uses the file interface routines. It will either read from a normal file like usual, or it will stream from a buffer in memory. I have also placed all of TinyXML in a namespace 'TINYXML' just to make sure it doesn't clash with any other code you might have in your application.

Finally, I have included a small console application that will load an XML file using this technique and dump out the results using either a recursive or non-recursive descent of the nodes.

Here is the link to the small download called TestTinyXML.zip

This project is built with VC6 (yes, you heard me right VC6 is the only way to create code snippets) and you can happily auto-convert the workspace to VC7 or VC8. Of course, when you convert it to VC8 fucking Microsoft Studio will bitch at you and tell you that 'printf' AND ALL OTHER STANDARD ANSI C LIBRARY CALL are 'invalid'.

Microsoft has a lot of nerve generating a warning message for a 'printf' statement. I sometimes feel like I am the only programmer left in the world who cares about multi-platform and standard ANSI-C/C++ compatibility.

Reading .INI files

I guess nobody downloaded my last code snippet because I didn't receive any emails telling me the link was bad. I fixed a couple of typos and re-uploaded it.

The snippets I am uploading today is something that programmers have to do all of the time which is to read and digest .INI files.

A .INI file basically looks like this:

[RENDER]
option1=value1
option2=value2
[KEYBOARD]
key1=value1
key2=value2

etc.

There is usually a comment symbol such as ';' '!' or '#' which, if seen as the first non-whitespace character treats the whole line as a comment.

In my implementation if you have [RENDER] then some other blocks and go back to [RENDER] again, it adds any new values to that.

My implementation supports non-key value entries as well.

[RENDER]
This is some stuff I'm adding that isn't key value pair.
key1=value1

In this case the line of text 'This is some stuff..' would be returned as a key with no value.

You can have spaces in your section headers, so [RENDER THIS THING] is a valid.

One feature of my implmentation is that all of the return values point back to the original file so the pointers are completly persistent and you can take advantage of this by either caching the pointers, or at least passing them around and not worry that they will dissapear on you.

Also, since the parser does no memory copies, it is extremely fast. I can digest a many, many, megabyte .INI file virtually instantaneously.

The implementation exports the functionality through simple C style function calls and opaque pointers.

Here is the header file. KeyValueIni.h

The implementation includes an example program that shows how to call the routines and iterate on the data. It is commented out with the pre-processor define TEST_MAIN.

The implementation is located here as: KeyValueIni.cpp

FileInterface : A useful code snippet

Here is a genuinely useful code snippet. The purpose of this code is to allow you to rapidly refactor a library that performs direct file-IO so that it can support reading and writing to and from a buffer in memory.

The best way to describe its usefulness is in the case I used it for. I suppose many of your are familiar with TinyXML. This is a superb open source XML parser that is very fast, stable, and robust.

The only small problem with TinyXML is that is assumes you are loading a file from disk. However, often times your XML resource is simply something you have loaded into a buffer in memory.

Using this code snippet 'FileInterface.h' you can rapidly refactor massive amounts of source code by performing a find replace on all of the STDIO file routines (fopen, fclose, fwrite, fread, fprintf etc.)

The only routines you have to do additional work on is 'fopen'. The refactored fopen has an option for you to pass in a buffer in memory and a length. If you do not pass this in, then the interface will do standard file IO. If you do pass a buffer then all reads or writes will happen relative to that buffer.

There is an additional option for write access whereby you can choose not pass a destination buffer but rather one will be allocated and grown for you.

To access this feature you open the file with the option "wmem".

Here is an example usage:

FILE_INTERFACE *fph = fi_fopen("test", "wmem" );
fi_fprintf(fph,"This is a test.");
fi_fclose(fph);

To retrieve the buffer that was created you call 'fi_getMemBuffer' before the file is closed.

size_t len;
void *mem = fi_getMemBuffer(fph,len);

To read from a buffer in memory you would use this pattern:

FILE_INTERFACE *fph = fi_fopen("test,", "rb", mem, len);

To read from a file on disk, simply don't pass the memory buffer.

I have found this snippet to be quite useful, I hope you do to.

Here is the header file: FileInterface.h
Here is the implementation: FileInterface.cpp

Stupid Utility Program : FileCode

I am uploading a remarkbly simple utility program that I had to re-write today. I have written this stupid utility so many times I can't remember and it annoys me that I have to keep doing it. I figure if I upload it here I won't have to search for a copy in the future. It's only a few dozen lines of code, but that is a few dozen lines I don't want to have to write again.

All this utility does is convert an arbitrary file into a character array as source code. This is useful if you have a program that needs access to a few files, but you don't want to distribute the files themselves. Instead you can just embed the files directly into the source code and the distributable can be self-contained.

Here is the source that reads in an arbtrary file and outputs a source and header file for it.

Here is the utility as a console program.

I wrote it this morning because I have a graphics library that needs access to a texture and a shader file but I didn't want to have to require them as data assets on disk.

Minor Update for Erwin Coumans

This is a very minor update and uses the same link. I added support to import and export the results from CreateDynamics in COLLADA 1.4.1 format again per Erwin's request.

Here's the link.

A Major new release of the CreateDynamics library and PhysXViewer

This is a major new release of the CreateDynamics Toolkit and PhysXViewer that represents a significant code cleanup. The new download is only 10mb and is complete; most of that 10mb is the binary executables, documentation, and a little bit of sample data.

!!!You cannot run this unless you have installed the PhysX SystemSoftware from Ageia!!!

This requires at least version 6.12.02 or higher. If you don't already have the system software installed you can get it from the Ageia website or from this link. Sadly, while I got the build of CreateDynamics down to just 10mb, the system software is 22mb.

Before I get into the contents of this upload I want to say a few things. First of all, I would like to announce that I no longer work for Ageia full time. I am still providing support, especially for the NxuStream serialization library, but the bulk of my time is going to be spent at my new job working for Simutronics on their Hero Engine. My first projects will involve using the CreateDynamics tool kit to make 'physics ready' all of their game assets. I have loved working for Ageia but I have also been very anxious to actually incorporate all of this technology into an actual game. I still plan to be working closely with Ageia in the future to help assist them in deploying new technologies as they become available.

The results of this project is going to be presented at GDC 2007 as a 60 minute programming lecture.

I have removed the previous source drops from this site and everything you need is contained in this single download.

One final personal note. While I am certainly having fun doing this project and I hope that it helps other programmers, if nothing else, as a learning aid, I do have a favor to ask. If you have a PayPal account please consider donating a few dollars to my son's youth group. He has a website to solicit donations (using the pay-for-a-pixel approach). In fact, all of the content for this project is hosted there.

Please click on this link to A Million Pixels US Move your mouse over the page and find a spot that you would like to purchase. There are still many $4 spots left. If you are feeling generous, like Erwin Coumans was, consider making a larger donation. You will be recognized on the site and the blog for your generous donation. My son's youth group needs to raise funds for their charitable activities and various functions. Just last month the group held a large Thanksgiving feast for over 35 people as a show of gratitude and fellowship with the community. If you appreciate all of this great free source code please show a kindness and forward a few bucks his way.


This new version provides just some of the following:

* An open source physics viewer called (PhysXViewer) that is built off of the DirectX 9.0 samples framework. This should be much easier to step through and understand.

* The latest version of the NxuStream serialization library.

* A source code library that demonstrates how to integrate NxuStream assets, skinned meshes, and softbodies into a game. Works through a set of pure virtual interfaces to allow you to easily adapt it to your own game engine.

* Full soft body support with the 2.7.0 SDK release of PhysX. This SDK has not yet been released to the public so this functionality is conditionally compiled away. As soon as the SDK and system libraries are released the build will support the volumetric soft body feature.

* The prototype 3D Studio Max plug-in of for convex decomposition is included in this build.

* CreateDynamics has been revised to be able to auto-generate skinned meshes. It creates an inferred skeleton directly from a static mesh.

* A bug was fixed in the convex decomposition library that improves the quality of the split meshes.

* A skeleton pruning algorithm was implemented to better automate the processing of complex skeletal meshes to rag doll models.

For more detailed information about the release here are some links to the documentation I have available.

The ChangeList with a lot of detailed information about this release.

The NxuStream FAQ

The PhysXViewer documentation (note, mostly about the SoftBody feature not yet avaialble.)

CreateDynamics documentation (quite a bit out of date but still useful.)

Auto-Generatd Skinned Meshes

Well, I finally got around to working on my automatic skeletonization and skinning code. You have seen my previously posted stuff on automatic convex decomposition. Well, a week or so ago I had a day to spend on automatic skeletonization and it turned out really well! I got amazing skeletons from my decompositions. I won't describe the algorithm entirely here, especially since I will be presenting on it at GDC.

I did want to upload a video showing just one example of how it can work. I have many test cases that all look very promising. However, it takes quite a while to create a movie file so I am just uploading this one.

On another point, I am creating a new sample application using DirectX that was built from the ground up. No Rocket source code at all. It will be an excellent learning tool and includes support for skeletal deformed meshes.

In the video I am uploading here you see a chair that was originally just a basic WaveFront OBJ file and raw mesh. I performed the convex decomposition on it, then inferred a skeleton. Next I automatically generated a skinned mesh by inferring bone weightings to the nearest rigid bodies. Finally, I let the simulation run and skinned the mesh based on the real-time simulation of the rigid bodies.

In this example you see what started out as a solid chair but in the simulation it appears to have been turned into melted plastic.

My thinking is that auto-generated skinned meshes against a constrained system can act as a 'poor-man's' soft body. One of the big advantages is that all of the skinning happens on the GPU so your only limiting factor is solving the constraints and the rigid body collisions. Of course, you also get self-collision pretty much for free.

Additionaly the constraint limits and strengths could be modified in real-time to make objects stiffen up or melt away.

Here is a link to the video clip as a WMV file

Yet another Update for CreateDynamics

• 
  
  I am uploading a new drop of the CreateDynamics toolkit primarily so that it is in sync with the latest tools plugins from Feeling Software. This version provides binaries both for the 2.4.4 PhysX SDK and the 2.6.2 PhysX SDK. The build configuration of the source code have been resivsed accordingly as well.
  
  There are also some minor bug fixes to NxuStream but nothing radical.
  
  I am planning on taking two weeks of vacation over Christmas so I can finally make some serious progress on some of the outstanding technology I want to develop.
  
  My primary goals are:
  
  Auto-generation of constrained systems based on a convex decomposition (effectively automatic skeletons)
  
  Auto-Generation of skinned meshes from static meshes with bone weighted bindings against the auto-generated skeleton. This will allow me to create a fake softbody system, similar to how a ragdoll works, in an automated fashion. The artist doesn't have to create a skeleton or create a deformed mesh. This will happen automatically.
  
  I want to finally get my 3d Studio Max plug-in version of the ConvexDecomposition code completed.
  
  I want to add support for creating closed meshes whenever I perform a split performing convex decompostion. This will fix outstanding bugs. It will increase stability. It will prevent the algorithm from generating hollow interiors. It will allow the tool to recurse much more deeply to find more exacting solutions.
  
  If want to implement a run-time library that automatically handles fractured models. This is different that using fixed joints for breaking. The library will 'listen' to the contact reports against the shapes in an object. If a contact is strong enough then that piece will be 'broken' off and let fly; the remaining shapes will be placed into a new actor. The piece that goes flying off will inherit the force from the original contact so that it will fly off realistically.
  
  The final piece in the puzzle is to auto-generate fracture *graphics*. This is a really tough problem and I may not have working for a while.
  
  It turns out that I have had a presentation accepted for the Game Developers Conference in March 2007. I have a 60 minute lecture about automatic generation of physics models. I want to get as much of this technology developed as possible over Christmas so that I can be fully prepared to make my talk.
  
  I will include the release notes I typed up for this version. The reason you haven't seen much in the way of major progess is that I have been working on a number of other projects at work. Currently I am writing some editing tools for an amazing piece of technology that I'm not sure I am allowed to talk about in public yet.
  
  ---------------------------------------------------------------------
  CreateDynamics Changes with Release #8: November 10, 2006
  
  Changes:
  
  
• Revised version of NxuStream
• Minor bug fixes, added support for soft bodies.

• New System Software installer compatible with 2.6.2
• A new system softer installer ‘PhysX_6.11.01_SystemSoftware.exe’ was included so that this version can run against the latest SDK release.

• New executable folder and launch batch files.
• The old executable folder ‘CreateDynamics’ still exists and runs against the 2.4.4 public release SDK.
• A new executable folder has been created called ‘CreateDynamics262’ which contains binaries compatible with the 2.6.2 release of the PhysX SDK.
• To run the 2.4.4 version of the modified rocket application launch ‘CreateDynamics.bat’
• To run the 2.4.4 version of the PhysXViewer application (source code provided) run ‘PhysXViewer.bat’
• To run the 2.6.2 version of the modified rocket application launch ‘CreateDynamics262.bat’
• To run the 2.6.2 version of the PhysXViewer application (source code provided) run ‘PhysXViewer262.bat’

• New build configurations
• If you are a licensee and have access to the official 2.6.2 SDK then you can now build the PhysXViewer source code. When you load the solution file \CreateDynamics\src\PhysXViewer\PhysXViewer.sln you will see that there are two new build configurations that target the 2.6.2 SDK.
• The default ‘debug’ and ‘release’ configurations still target the 2.4.4 public SDK.
• A Note about the PhysXViewer
• The purpose of the PhysXViewer is to be an open source application that is the ‘official’ tool to view NxuStream data exported from Max, Maya, or from your own product.
• Currently it can import NxuStream files in XML, binary, and COLLADA.
  I have been unable to spend the time on this tool that I would have liked. It does not currently have mouse dragging, debug visualization, or graphics bindings. These are fairly essential for this to be a usable tool.
• You can run the CreateDynamics toolkit however and load and save data.
• The reason the source is included is as a learning tool. All of the source have now been placed in distinct libraries with minimal dependencies.
  

Some bug fixes to CreateDynamics and NxuStream

I had to upload a new build of CreateDynamics.zip because I found out I had broken the conversion to boxes, spheres, and capsules because of a few typos. These are fixed now. I also have revised to the latest version of NxuStream which compiles without warnings even in .NET 2005 and has a number of bug fixes. I have had a QA team running a lot of data through it and it is getting better all of the time.

If you are working the source code or downloaded the previous drop, I recommend you download this revision. The link is the same, I have not been keeping previous builds online.

You can download the revision here.

CreateDynamics and NxuStream update

I am uploading my first revision to NxuStream in about six weeks. Suprisingly the biggest change to this version is that the bulk of the NxuStream serialization code is now auto-generated. Once I finished the last version of NxuStream a few weeks ago I was suddenly faced with an enormous maintenence problem. (It is important to note that these changes were only to the internal implementation. The public interface did not change.)

I inherited the original implementation from someone else and didn't think it would be the right thing to do to rewrite it from scratch. It turns out, had I done that, the whole thing would have taken a lot less time. In the end, with this release, none of the code from the very first original implementation remains. The code which streams data to and from either an XML or binary file was rewritten and is much cleaner.

The biggest problem I faced was that this code is trying to serialize roughly 950 discrete data items. It also has to work across multiple versions of the SDK and take into account not only new features but also deprecated items or something as simple as a name change. The previous implementation did all of this maually. What I mean by that is a computer programmer had to write the load code, save code, import code and export code for every single data item as well as the complete constructor and destructor with all memory cleanup for every class. On top of that all of the enumerated values had to be able to be mapped to and from ASCII strings.

If a single new data item had to be added this caused a programmer to have to manually change code in numerous source files. A single typo or oversight and the build would be broken or, more likely, simply be in error and no one would notice for a long time. Debugging these typos was exhausting and having to manually revise documentation more so.

People who know me know that I am an impatient man. Once I started having to do this process myself I realized it was a losing proposition. I have better things to do with my life than manually maintain a bunch of source code that just does data manipulation and management.

Now, as a game developer, I always try to find a data driven approach to a problem. This, however, was a bit different. I needed to generate an enormous amount of source code which had a certain degree of complexity and a lot of special cases. At first I took a look on the Internet for automatic code generators from an XML schema. While there are many products that do this (and it validated for me that this approach wasn't completely stupid) none of them were going to map to a highly customized API with a lot of special case situations.

First I wrote a tool that could parse an XML schema and extract the data I needed. Since I already had an schema to begin with this gave me a good head start. Once I had extracted all of the data I needed I suddenly realized that I didn't have much use for the schema to begin with. Instead I built a comma seperated value spreadsheet that I could just edit manually in a text editor.

The most difficult part after that was to scan through every header file to make 100% certain I had replicated every single data item perfectly. This was exhausting work but I was willing to do it because I knew it was something I would only have to do *one* time. Once I had my spreadsheet laid out I went about reading it in and turning it into code. I iterated on this for some weeks until it worked completely with all versions of the SDK. I even added automatic validation routines to so that if any of the serialization data in the SDK was out of sync with the implementation it would alert me immediately.

I also had the tool auto-generate full doxygen compatible documentation as well as an XML schema file.

The previous implementation used inheritance which proved to be a problem because the structures needed to read and write data to and from a file is not identical to the source. Mostly this problem was related to having to serialize pointers or containers. For this implementation I chose to use object mirroring. Every single class and enumeration in the NxuStream code base exists in its own namespace but still has the same identical name as the one it is replicating.

The vast majority of the data can simply be copied automatically between the two mirrored items. In the cases where there was data that could not be copied automatically I wrote a piece of source code I called 'NXU_CustomCopy.cpp' that contains only the code necessary to replicate data items that couldn't be handled automatically. This is the only code I have to maintain manually now. I did spend a lot of time making the latest version be backwards compatible with the previous release. If you have existing content using the last release you should still be able to load it with this build. Read the release notes for more information about this.

Going forward, now that this system is complete, I can rest assured that there will never be any memory leaks. There will never be a case where a typo calls an item to either load of save incorrectly. There will never be any data items that I 'forgot' to copy. In the future, when a new data item gets added to the SDK, I will (in almost all cases) simply have to update the data template and regenerate the code; having complete assurance that it all works perfectly.

Putting this to bed now allows me to work on the things I really want to work on. These include the PhysXViewer (which I intend to become the 'official' viewer for NxuStream data and COLLADA physics). I want to improve the convex decomposition library to make closed surfaces whenever it does a split. This will fix an outstanding bug and produce better hulls. It will also get me one important step closer to auto-generating fracture geometry. I still want to use the results of the convex decomposition library to automatically generate a constrained system to do a form of inexpensive soft-body; where the model is simulated with a rigid body engine but skinned using a GPU. And, of course, I want to do more work with the GrannyPhysX integration to demonstrate how to attach cloth to characters and do physically driven character animation.

I added a new application with this release that shows how to use the CreateDynamics toolkit directly in your own plug-in as source code. It also provides shell source to demonstrate how to make it process data directly from your own engine.

Here is some of the documentation with further details about this and previous releases. This documentation is also included in the full download.

Here is the full download of the CreateDynamics toolkit.
Here is the root readme.txt
Here is the change list documentation that lists all of the new stuff in the build.
Here is the Excel spreadsheet that shows all of the serialized data items. This is used to auto-generate the source code for serialization now.
The auto-generated doxygen compatible documentation. (right click and do save as)
Here is the previous NxuStream FAQ.
Here is the original CreateDynamics documentation.
The data layout as an XML schema file (probably doesn't validate though, just for documentation).

I have also been working to get the 3D Studio Max physics plugin and the Maya Nima plug-in updated to use this version of NxuStream. We have that working and it should be released fairly soon.

I am also still trying to get my own 3d Studio Max plug-in to work but I am stuck because I can't get the objects to show up in the Max scene when I pass in my transforms. I have tried formulating my transform a bunch of different ways and have asked for some help but still no luck. It's very annoying that something so small like this can be a blocking factor. To get the rest of the 3D Studio Max create dynamics plug-in working would only take me a few hours if I could get it to accept my transforms.

The source code to the plug-in is included with this drop. If you know max and can help me debug it I would appreciate it.

Build instructions and Blog Comments

(Photo caption: This photograph has absolutely nothing to do with the following post. However, Jessica Alba sure is pretty to look at ain't she?)

I just received a comment on my previous blog posting. Thanks! Now, send me a freaking email! It is great to leave comments on blogs, especially if it is something you want to share with others. However, you really need to send me a personal email. Blog comments are generally anonymous and I have no way to contact you other than making a fresh blog post. And, as much as I enjoy posting new photographs of pretty girls, it is isn't the most efficient communication channel.

Regarding the last blog comment where someone said they couldn't build the source. You must change the #include paths to point to wherever your own install of the 3D Studio Max SDK is. By default the project file points to my own personal install which is not going to be the same as yours. Change the include path under C++ properties, the linker option, and the resource properties.

This 3D Studio Max plug-in is definitely a work in progress. I am just now learning about how to program the Max SDK and the learning curve is brutal. I spent two hours yesterday just trying to set a freaking matrix transform and I still never got it to work right (even though I exported the data to disk and verified that my source transforms were fine, it's just a 'max thing').

Recently I have been getting some bug reports that people are encountering crash problems with certain meshes or settings. I am right now working on resolving these problems. I am thrilled that people are finding the tool useful. Originally I expected people just to use it for rocks, trees, tables, chairs, and that sort of thing (which it generally seems to do a good job with). However, now I am finding out that people are trying to use it for entire level geometry!!

It was not designed for that but now that I see people want to use it that way I will continue to work on it.

The main reason the tool is limiting for such purposes is that it doesn't generate internal faces. I am now working on a tool that generates solid geometry after a split. This will prevent it from creating hollow interiors and conform much more accurately to the original mesh.

I also am encountering problems when it attempts to recurse extremely deeply. I will continue to post updates as I make progress. That said, this is not my 'official project' and is mostly a hobby thing so I can only work on it as I make time available.

Thanks, and please remember to email me directly with questions.

Convex Decomposition 3d Studio Max 6 and above Plug-In (with source code)

(Photo caption: My friend John Miles when he and I were taking a day trip in his Ferrari 308.)

I only had a little bit of time today to mess with my Convex Decomposition plug-in. This is my first 3d studio max plugin and I could not have written it without the help of my good friend Robert Sitton.

I am hoping to spend a lot more time improving it in the coming weeks but I figured since this is at least functional I can release it and get feedback. I am also hoping some Max plug-in gurus might help me improve it.

Here is the link to the plug-in and source code. (137k download)

Just copy the plug-in 'MESHFW.DLU' into your 3d Studio Max plug-ins folder.

I have revised the source code to build against the Max 6 SDK. That means this plug-in should work against all versions of Max 6 and higher.

To use the plug-in just select an object you want to perform convex decomposition to. Go to the 'Utilities' page and select the plug-in called 'Mesh Framework'.

You will be presented with a simple user interface that will let you control the recursion depth and thresholds.

After clicking on the button to run it, it will perform the decomposition and insert the results of the approximate convex decomposition into the scene and delete the original mesh.

If you don't like the results just hit Control-Z for an undo and try it again.

Things the plug-in needs to do that I could use help on is:

* The results of the convex decomposition should all be placed into a 'group' so that they can be manipulated as a single object.

To build the source just load the solution file with .NET 2006. You will *have* to change the include paths to whichever Max SDK version you have on your machine.

I added some code that I thought was going to 'group' all of the objects together but it doesn't appear to be working. Take a look at 'CreateDynamics.cpp' and search on the word 'group' in the source code. If anyone has a bug fix for this it would be much appreciated.

I, myself, will add the ability to produce approximations of boxes, spheres, and capsules, in addition to convex hulls.

If you have time to take a look at this I welcome the feedback.

New release of CreateDynamics, PhysXViewer and NxuStream

Every time I make a post I like to include a photograph that somehow vaugley relates to the content. However, for this update, I just couldn't think of anything so I used a picture of my friends Simon and Christa from last summer.

I just recently returned from GameFest. My talk with David Moore of Rad Game Tools went fine but there was a very small audience. It's hardly a surprise since we were scheduled against a presentation on the latest version of the HSL compiler; heck I wouldn't have gone to my own talk myself.

Since I spent so much time on the content I will go ahead and make it available here as well.

If you just want the slides only in a small download use this link. (3mb)
If you want the slides with the rather huge embedded movies, use t his link. (75mb)

Most of my time has been spent finalizing the NxuStream data format. I have also been working on some documentation. Some of it you can access online and the rest is in the zip file itself.

Here is a link to the API documentation.

Here is a link to the NxuStream XML schema.

Here is a link to the NxuStream FAQ that I am working on. If you have additional 'FAQ' questions please email them to me so I can revise the document.

I am sorry that I have not made significant progress with the CreateDynamics toolkit itself or the new viewer application 'PhysXViewer'. I simply couldn't find time to work on these tools until the NxuStream data format was complete.

My next little project is going to be to put the ConvexDecomposition library into a 3D Studio Max plug-in. As I become more comfortable programming in the Max SDK I hope to add more seamless support between CreateDynamics + PhysXViewer + NxuStream + COLLADA + 3D Studio Max.

Finally, here is the link to the full CreateDynamics.zip file. This contains the CreateDynamics toolkit, PhysXViewer, NxuStream, ConvexDecomposition, and a number of Samples and demos.

This download is only 39MB. After you unzip it you can run 'CreateDynamics.bat' which will launch a custom version of Rocket that lets you play around with the toolkit. If you run 'PhysXViewer.bat' it will launch the PhysXViewer application (source provided). The PhysXViewer application doesn't have mouse dragging or other necessary features but, as I said, I hope to be getting back to that soon. Ultimately I will be transitioning away from the Rocket application and developing all of these tools within the context of the much smaller (and simpler) PhysXViewer framework.

If you do not already have the PhysX 2.4.4 run-time installed on your machine then run the installer provided 'PhysX_2.4.4_FC4_SystemSoftware.exe'.

GameFest updated build

I'm heading out of town to attend GameFest and visit with my friends at Rad GameTools. My presentation at GameFest is going to be about the CreateDynamics toolkit I am working on. I wanted to get a revised build put together before I left just so you could get the 'latest' version and I could get some feedback on it.

Here is the link to a full version of the CreateDynamics toolkit. In previous posts I uploaded individual components. I have not revised those links yet, so this download represents the 'current version' of the various sub-components in the system.

The major changes to this build are:

(1) Support of scene/model instancing in both NxuStream and COLLADA.
(2) A lot of improvements, bug fixes, and samples for the NxuStream code.
(3) Pre-notification events for object creation.
(4) The ability to construct a collection one object at a time.

I won't get into the details of all of the changes I made but I have worked through many bugs over the past couple of weeks. I didn't make any significant changes to the actual create dynamics code, but I really look forward to getting back to that as soon as this file format stuff is fully put to bed.

The major things I have left to work on are:

(1) User property fields for all data objects.
(2) Lots of documentation.

Not all of these components require the PhysX 2.4.4 SDK to build. After you unzip the file, if you do not already have the PhysX 2.4.4 run-time component installed, you should run the provided system installer. This is *not* the SDK, just the run-time libraries.

The following components build *without* the PhysX SDK:

* CreateDynamics [DLL plug-in to auto-generate physics from graphics data]
* ConvexDecomposition [Stand-alone convex decomposition library]
* DAE2XML [Demonstration application showing how to parse COLALDA 1.4.1 physics (needs to be revised with the support for physics models instancing physics models that is already in the NxuStream code]
* DecomposeSample [Console application demonstrating how to use ConvexDecomposition as a library]
* PhysXRagdoll [A console application demonstrating how to load and run the CreateDynamics tool as a plug-in DLL]

The following components require the PhysX 2.4.4 SDK installed (to the default directories) to build. You may also need the DirectX SDK to build the PhysXViewer sample application. You can get the PhysX 2.4.4 SDK from the Ageia website.

* LegacyNxuConvert [Converts old legacy physx format (core dump) (ssa) to NxuStream]
* NxuConvert [Converts between XML, BINARY, and COLLADA forms of NxuStream data]
* NxuStream [The NxuStream library source code.]
* PhysXViewer [A prototpye application for viewing physics. Not very functional yet. Mostly provided to demonstrate the run-time binding to the Granny SDK. Much more work must be done on this application.]
* Samples\SampleSceneExport [An OpenGL sample application that shows how to import, export, and instantiate physics data and simulate it.]

The following libraries will compile but with functionality disabled unless you are a Granny licensee:

* Grimp [Converts Granny data into a generic form for CreateDynamics to operate on]
* GrannyPhysX [The Granny to PhysX run-time binding layer]

If you would like the latest drop of the NxuStream code just by itself you can use this link. This includes an OpenGL sample application that shows how to import, export, and instantiate physics data using the NxuStream library.

This is only a 2.5mb download and should compile out of the box with .NET 2003 and the PhysX 2.4.4 SDK installed on your machine (assuming you used the default directories).

Right now the biggest problem with all of this stuff is lack of documentation. I will really get cranking on documentation when I return from GameFest a little over a week from now.

PhysX NxuStream file format

How to get your physics data actually into a physics engine

While COLLADA 1.4.1 appears to a viable general purpose physics file format it may not be appropriate for a specific targeted physics SDK. The PhysX SDK uses the concept of 'descriptors' in its API to represent dynamics data. NxuStream is a pure reflective object model of these descriptors. What this means is that whatever the descriptor looks like in the API is exactly what it looks like in the XML file as well. The NxuStream library will load, save, and instantiate physics assets usng the PhysX SDK based on either COLLADA or NxuStream source. Additionally, the file can also be loaded and saved in binary format. The binary format can save out 'cooked' data which will load much faster than raw triangles.

This version is probably in late alpha, early beta phase. It requires the PhysX 2.4.4 SDK to be installed on your machine. The PhysX 2.4.4 SDK is publically available at the Ageia website and I strongly recommend you check it out. If you don't use this physics SDK then this post is probably not very relevant to you.

To my chagrin I have spent the past two weeks trying to seamlessly convert between COLLADA 1.4.1 physics and the native PhysX SDK format. It seems to me to be a ridiculous amount of time to spend on just parsing a stupid file format.

Currently the NxuStream library is incorporated into your own software simply by adding the source to your project. It requires that you have include paths set to the PhysX SDK. Similar to compiling a Direct3D application.

The source is wholey contained in a namspace 'NXU' and should not conflict with anything else in your application.

To use it, all you have to do is include a single header file 'NXU_Helper.h'. A physics asset is referred to as an 'NxuPhysicsCollection'. This helper API lets you load a file in any of the 3 possible formats (NxuStream XML, NxuStream Binary, and COLLADA). You can then simply instantiate the asset relative to a root transform. There is also a 'save' method that will let you save it out in any of the three formats.

The deliverable contains:

NxuStream.xsd
NxuStream.xsx : An XML 'schema' for NxuStream

Directories:

NxuConvert : Contains a console application that converts from one format to another.
NxuStream : Contains the NxuStream source code.


Example usage:

"NxuConvert beshon.xml beshon.dae" converts a file from NxuStream XML to COLLADA 1.4.1

The NxuStream API in NXU_Helper.h is as follows:

loadCollection : Loads a physics asset from disk.
instantiateCollection : Instantiates an asset relative to a root transform.
releaseCollection : Frees up the memory associated with the physics asset.
coreDump : A convenience function to save either the entire PhysX SDK or a single NxScene to a file on disk.
extractCollectionSDK: Copies the contents of the SDK to a collection.
extractCollectionScene: Copies the contents of a single NxScene to a colleciton.
releasePersistentMemory: Some persistent memory is allocated by the library to retain relationships between instantiated physics objects and their name to prevent multiple creations. It also needs a small amount of peristent memory for name fields. The application calls this routine on exit or when a reset of the SDK occurs.

A user has the option of provided an error reporting interface so they can find out if and why anything failed. The application can also pass in an interface that notifies them *before* an object is created. This allows them to tweak the descriptor or decline to have the entity created. They are then notified when a physics object is successfully created so they can bind the userData field to their own internal game object.

I have tried to keep the public interface simple. The implementation can be a bit overwhelming because the SDK can represent so much and so many types of data. Also, this code has gone through a lot of evolution and was touched by many programmers.

Still to be done are transmission of custom user properties, asset instancing, the ability to load or save from an area in memory and just general cleanup.

This code, already available on the PhysX website is provided here to show how one goes from COLLADA to a proprietary format or from a propietary format back to COLLADA. It also shows the full round-trip of not only loading assets but also instantiating them on a physics SDK.

This flow of control system is integral to run-time binding of physics assets to game engines. For example, while working on the GrannyPhysX library, which binds the PhysX SDK to the Granny run-time engine, we used the NxuStream concept of a 'collection' to bind the individual bones in the graphics skeleton to specific rigid bodies and constraints in the physics engine.

You can download this pre-release version of NxuStream here.

PhysXViewer

The PhysXViewer allows you to use a graphics front end to experiment with the CreateDynamics toolkit. You can also import and export between COLLADA 1.4.1 physics and PhysX NxUStream. I am working on a new version of the PhysXViewer which is much more lightweight. This version is based on the Rocket application which, unfortunately, has grown quite large over the years. The new PhysXViewer will not be ready for release for probably another month or so. In the meantime you can run this custom version of Rocket.

I fully expect that there are bugs with the COLLADA 1.4.1 physics imoprter and exporter. This is a pretty tricky format and it can be interpreted in a wide number of ways. However, I am working with other members of the COLLADA community to keep it in conformance. The goal, ultimately, is that you will be able to seamlessly interact with COLLADA physics data using Max, Maya, SoftImage, as well as the Feeling COLLADA viewer, Bullet Viewer, and the PhysXViewer.

If you want to load either COLLADA physics data or NxuStream data directly into the PhysX SDK all you will need is the public 2.4.4 release of the SDK and the NxuStream library which is provided at the Ageia website.

The PhysXViewer is about a 39mb download. Largely because it includes a great deal of sample data. If I removed all of the sample data and documentation it would be a very small download. However, it also woudln't be nearly as interesting either.

You can downoad it from this link.

For a quick and easy demonstration of how to use it, follow these steps.

After you unzip it you will need to install the PhysXSDK 2.4.4 core run-time libraries if you do not already have them installed on your machine.

Run: PhysX_2.4.4_FC4_SystemSoftware.exe to install the run-time SDK components.

Next, run the batch file 'PhysXViewer.bat'.

Click on the button 'Dynamics Page'

Under the combo 'graphics mesh' select 'character.bin'

Then click the button 'create dynamics'.

There is more documentation provided in the ZIP.

The CreateDynamics Toolkit

Automatic Generation of Dynamics Data from Graphics Meshes, including Rag Doll models from Skeletal Deformed Meshes and Approximate Convex Decomposition.

The CreateDynamics toolkit is delivered both as source code and as a DLL plug-in. Unlike some of the previous offerings, there is a substantial amount of source code in this project. Could it be cleaned up? Yes, I'm sure it could. However, I have limited amounts of time and sometimes I have to take functionality over aesthetics.

The key thing is you get source. That means you can rebuild it. The second key thing is you get a plug-in, so you can use this as a 'tool' without having to worry about the source at all.

After this shaky introduction I suppose you are wondering what the heck does it do?

What is the CreateDynamics Toolkit? CreateDynamics is an open source library that automatically generates dynamics data from static or deformed skeletal meshes. It can be used as a DLL plug-in or the source can be linked directly into your own application.

What formats does it accept? For deformed skeletal meshes CreateDynamics can read the Unreal PSK file format or Granny 2 files generated from the Rad Game Tools exporter. You must be a licensee of Granny to have access to the exporter and sources.

For static mesh data it accepts Unreal PSK, Granny 2, and Wavefront OBJ files. You can also submit your own raw static data directly through the API. There is not yet a public interface to submit raw skeletal deformed meshes. However, if this is a feature people would like to have it can be added. (You must be a Granny licensee to build the source with Granny support.)

What kind of dynamics data does it generate? CreateDynamics can interpret a deformed skeletal mesh and infer a constrained ‘rag doll’ model from it. It can convert the input geometry into a format suitable for cloth simulation. Finally, it can perform approximate convex decomposition to produce efficient collision models for mesh data. Collision fitting supports convex hulls, boxes, spheres, and capsules.

Future versions will provide improved support for constrained systems and cloth modeling.

What data formats does it produce? CreateDynamics generates output data in PSCL, COLLADA and NxUstream formats. PSCL stands for the ‘physics scripting language’ which is used by the PhysX Rocket application. It is easily human readable and generally useful for debugging. No source code library is provided to read PSCL for a game engine. If there is a strong need for such a tool it might be made available.

The format promoted by Ageia is ‘NxUStream’ which is a reflective object model of the PhysX SDK stored in either XML or binary form. A complete XML schema is provided. The CreateDynamics toolkit exports data in XML form and can then be converted into binary for your target platform by running the tool NxuConvert. The file name extension adopted for PSCL is ‘.PSC’. NxUStream uses ‘.XML’ for XML and ‘.NXB’ for the binary version. COLLADA files have the extension of ‘.DAE’.

Can I generate my own file format? Yes. There is a single source file in the CreateDynamics library which writes the output data to disk. It is a relatively simple and straightforward task to modify this source to save the data out in any format you see fit. The source file is called ‘Accumulate.cpp’ and is located in ‘\CreateDynamics\AutoPhysX’.

Does CreateDynamics output COLLADA physics? The CreateDynamics toolkit now has basic support for COLLADA physics import and export. Use the import and export options under the file menu to load and save a COLLADA .dae file. This can be imported in other tools using COLLADA-DOM, FCollada or your custom parser. COLLADA physics content can be created using various tools like Maya, Max, XSI and Blender 2.42.

What features will future versions of CreateDynamics support? Future versions of the CreateDynamics toolkit might provide support for pre-fractured assets and automatic generation of deformed skeletal meshes for soft-body simulations. Since each of these features must operate on both the graphics data as well as the physics data they present significant architectural design challenges

While it is relatively simple to produce a ‘fractured object’ representation by taking advantage of the aggregate convex decomposition library, it is much more difficult to produce the graphics representation of the object at the appropriate split boundaries. Automatically generating a deformed skeletal mesh is a more straightforward project; but selecting a format for the graphics representation is an open question.

Better support for cloth conversion as well as improved user interfaces and API would be likely feature improvements as well.

Does CreateDynamics work with 3D Studio Max or Maya? Not currently. While it is certainly a long term goal to integrate the features of CreateDynamics into these production tools it is not ready for that yet. We feel it is better to make a version of the tool available to developers for early feedback and give them the opportunity to integrate it into their own tools pipeline. By providing it in open source form, as well as a DLL plug-in, we hope to engage the development community in the evolution of this project.

How can I use CreateDynamics as a stand-alone production tool? CreateDynamics has been integrated into a stripped down version of PhysX Rocket. It provides a graphics front end that allows you to easily experiment with the features of the tool. CreateDynamics can also be used as a console application from the command line. One of the most exciting opportunities provided by the CreateDynamics library is the ability to batch convert a large number of game assets based on a set of scripted rules.

How do I convert my own assets with PhysX Viewer? Simply drop a PSK, GR2, or Wavefront OBJ file into the directory ‘\PhysXViewer\data\mesh’ and it will show up in the menus.

Where do I find my output? After converting an input graphics mesh into a dynamics asset the DLL will produce two output files; one in PSCL and one in XML. Rocket runs the PSCL version by default since it can bind with the source graphics. To run the NxUstream file directly select the checkbox ‘use nxustream’. If you do this you will only see the dynamics assets.

If you were to convert a file called ‘test.obj’ you would get as outputs

‘\CreateDynamics\data\pscl\test.psc’
‘\CreateDynamics\data\pscl\test.xml’
‘\CreateDynamics\data\pscl\test.dae'

How do I adjust the dynamics settings for CreateDynamics? CreateDynamics is a ‘rules’ based system. The library reads an ASCII text file that defines the physics properties to be applied when converting a data asset. When using the PhysX Rocket tool this file is generated based on the current settings of the graphics user interface; using checkboxes, sliders, and combo boxes. Future releases of CreateDynamics will provide an improved front end. Additionally, you can design your own user interface relative to your own tools chain. The main point is that, regardless of the front-end user interface, CreateDynamics decides how to apply conversion rules based on a data driven script system.

The ‘rules’ system accepts wild-card strings to apply dynamics properties to a specific bone or set of bones in a deformed skeletal mesh.

What is the status of CreateDynamics? CreateDynamics is currently in an ‘alpha’ release state. It is being provided to developers because feedback is needed to help steer the project going forward. Is this a useful tool? What are the most important features? What changes would you like to see to the API? What do you believe are the most important features for future development? Currently the approximate convex decomposition seems to perform very well. While it does run slowly, still it produces very high quality collision models. The rag doll generation shows great promise since it can generate a first approximation dynamics model in seconds, however, a great deal more work is needed to tweak rag doll models and fix all cases where it might fail. Sample data is provided so that you can experiment with the tools for yourself. All sample data is courtesy of Simutronics Corporation. This sample data is still under their copyright and may only be used for testing inside this tool.

Does CreateDynamics support binding to graphics data? No. CreateDynamics only represents the physics model. You will need to retain a semantic binding between your graphics representation and the physics model on your own. The ‘name’ field of the mesh and all of the constrained bodies is retained and allows you to perform late binding between the NxActor and your skeletal mesh. For users of the Granny library from Rad Game Tools we have developed a run-time library that will synchronize a Granny Model to an NxUStream physics collection on the fly. A sample application that shows how to convert a Granny Model into a rag doll or blended animation is available from Rad Game Tools.

Is CreateDynamics a multi-platform library? No. Since most tools for game development run on the Windows platform CreateDynamics is provided in that form. While, theoretically, there is no reason the source could not be recompiled and targeted to other platforms it has only been developed and tested on Windows to date.


What comes with this download?

(The CreateDynamics toolkit.)

In my next post I will include a 'viewer' application with a nice GUI front end for CreateDynamics. However, this posting is designed to show how to use it as a developer. The build directory layout looks like this.

AutoPhysX : Contains the library that converts mesh data to physics data based on rules.
CreateDynamics: Contains the solution file and source to produce the DLL plug-in.
ConvexDecomposition: Contains the approximate convex decomposition library.
granny: If you are a Granny licensee this is where you would place 'granny.h' and 'granny2.lib'
grimp: Contains source to load Granny files (only available to Granny licensees)
PhysXRagdoll : Contains a console app that demonstrates how to use the plug-in.
psk: Contains source to load a PSK skeletal deformed mesh.
snippets: Contains source to generally useful utilities.

The demo application directory PhysXRagdoll contains:

beshon.bin : A sample skeletal deformed mesh in Rocket .BIN format.
character.bin : A sample skeletal deformed mesh in Rocket .BIN format.
character.rul : Custom rules to be applied to the 'character.bin' skeleton.
CreateDynamics.dll : The release build of the CreateDynamics plug-in.
CreateDynamics.txt : Debug log output.
CreateDynamicsDEBUG.dll : The debug build of the CreateDynamics plug-in.
deer_bound.bin : A sample skeletal deformed mesh in Rocket .BIN format.
homer.psk : A sample skeletal deformed mesh in PSK format.
hornbug.bin : A sample skeletal deformed mesh in Rocket .BIN format.
ob_chair_gothic.obj : A chair model in Wavefront OBJ format.
ob_chair_wood.obj: A chair model in Wavefront OBJ format.
ob_chess_table.obj: A chess table in Wavefront OBJ format.
ob_nice_table.boj: A table in Wavefront OBJ format.
ob_work_table.obj: A table in Wavefront OBJ format.
physxragdoll.cpp : Source to the console appliation demonstrating usage.
PhysXRagdoll.exe : The console appilcation. Example: "PhysXRagdoll character.bin"
PhysXRagdoll.sln : The .NET 2003 solution file to the console application.
PhysXRagdoll.vcrpoj : The .NET 2003 project file.
rules.rul : The default rules.
wavefront.cpp : A utility to load a Wavefront OBJ file.
wavefront.h : Header file for the Wavefront OBJ file reader.

Approximate ConvexDecomposition

I had previously made a couple of posts on this topic, but now I am ready to release this as a functional library. First of all, I apologize for the source code. It does not meet the exact strict requirements of most of my 'snippet' code. It makes heavy use of the STL and even has some semi-dead code in it from some experimentation I was working on.

That said, lots of the source *is* in snippet form and the library, as a whole, is usable as a production tool. In fact, this library is already being used by a couple of major game developers in a production environment.

This tool is kind of funny. I never ended up doing what I intended to do. About half-way through, when I was getting quite frustrated, I tried something brute force and the brute force solution ended up working, probably, nearly as good as the elegant solution I was looking for.

Here is a link to a series of papers from Algorithms and Applications Group at Texas A&M University. This work was done by Jyh-Ming Lien and Nacy M. Amato. There a number of publications and some great research to be found here. What you absolutely will not find is any working tools or source code!

My original intention was to more or less follow the algorithm presented in these papers. I made a decent start but I eventually got stuck. My final implementation is much, much, simpler than what is presented here. However, my simple approach seems to work fairly well.

In essence all my algorithm does is build an OBB tree and wrap hulls around the leaf nodes. The 'brute force' aspect is that after generating many leaves I then run an algorithm to 'merge' them back together. So, in essence, is makes way too many cuts but then does a 'cleanup' phase that stitches them right back together again if it turns out that the cut was not needed. The end result look nearly as good as if I had made 'the perfect cut' in the first place.

I also have an optimization in the algorithm not to split the mesh if there is no significant 'concavity' found. One important feature of the technique is that it does not require the input mesh data to be a closed mesh.

Here is how my recursive algorithm works.

(1) Compute the 'volume of concavity' of the input mesh. This is done by wrapping the source mesh in a convex hull. Then, each triangle in the mesh is 'projected' into the surrounding hull by taking the nearest facing normal into account. The volume of the tetrahedron formed is added to the 'sum total' of concavity. If this is the first time into the routine we save the total volume of the convex hull for the entire mesh. The reason we compute this volume by projecting individual triangles is so that we can handle open meshes. We also exit if we have reached our maximum recursion depth.

(2) We compare the 'volume of concavity' as a percentage of the total volume of the input hull. If this volume is below a threshold we consider it 'convex enough' and do not recurse further. The reason we compare against the total volume of the hull is so that we can avoid wasting time on extremely concave yet relatively small features on the source mesh (tiny bumps that are quite concave but not significant to the whole.)

(3) If the mesh is significantly concave then we split it. Now, had I implemented the original algorithm by Jyh-Ming Lien and Nancy M. Amato here is where I would have done 'feature extraction'. In fact, I spent over three days doing this. I did do an excellent job of identifying 'concave features'. However, I was never able to come up with an algorithm that would compute the 'perfect' split plane based on these features. I did get some good results, but I had a lot of failure cases as well. An additional challenge of this kind of feature extraction would have required the split to only affect triangles that had direct connectivity to the 'feature'. Meaning, you might want to cut off one part of the mesh, but not split the plane through the whole thing.

At any rate, I ended up giving up on that approach. A lot of the old code to do feature extraction is still in the source, but I don't do anything with the data other than return the volume of concavity.

Instead, I compute the best fit oriented bounding box for the input mesh. I then compute a split plane on the longest edge of the OBB.

(4) Now that I have a split plane I run through the mesh and put the triangles on one side of the plane in a left mesh and the triangles on the other side in the right mesh. If a triangle straddles the plane it is split and each fragment is added to the correct side. Then, the left mesh and the right mesh are each passed recursively back to step number one.

(5) Once we have gotten this far we now have a ton of convex hull pieces. The final step is the 'brute force cleanup' phase. It involves sorting all of the convex hull pieces by 'volume'. Our goal is to merge the largest volume pieces with the largest volume pieces to begin with. We run through all pieces, sorted by volume, and compute the volume of piece A and the volume of piece B. Then, we compute a new hull that encompasses both piece A and piece B combined. We then compare the volume of the combined hulls with the sum of the volume of the two pieces. If the volume of them merged is within a user provided percentage threshold we throw away the two pieces and retain the combined hull.

Wash, rinse, repeat. This procedure is run over and over again until no two hulls can be merged. The 'merge percentage threshold' is the twitchiest value. If you make it 10% you might get too many hulls but make it 12% and you might get too few. You need a viewer application that will let you rapidly preview the output since this is basically an aesthetic and design decision to decide which result you want to keep.

If this implementation ran faster it would be easy to have the algorithm converge on a specific solution. You could just say 'I want to many hulls' and it would automatically adjust parameters to achieve that result. However, currently, the implementation is quite slow. I have every reason to believe it could be made many times faster, but I just wasn't worried about real-time operation when I originally wrote it.

(6) The final step is to send the results back to the application. It is at this point that your own application/tool should do something clever. Once you are returned a convex hull piece you can attempt to do primitive collision fitting. You might try to fit an oriented bounding box, sphere, or capsule. You can then convert the hull into a primitive shape for more efficient simulation. My tool 'CreateDynamics' allows you to do this particular optimization.

(7) The last step is to save the output into a format that is suitable for use by a tool or game engine. The provided console sample application will save out the data in both COLLADA 1.4.1 format and PhysX NxuStream. It also saves out a Wavefront OBJ file just so you can get a visualization of the approximated result.

Future work. I no longer believe I have to do 'feature extraction' to get the kind of results I want, but there is still an issue. Currently it is a desirable feature that this tool does not require closed meshes to produce valid output. However, this has the sometimes undesirable side effect of creating hollow objects. If you let the algorithm recurse too deeply it will keep converging on the 'skin' of the mesh and produce a hollow object. For example, if you run it on the Stanford Bunny to a deep enough recursion depth you get a nice hollow rabbit. At first I thought this was a bug but then I came to realize that since I was dealing with an 'open mesh' this was the correct topology.

To fix this problem I need to have a special case for closed meshes. Whenever a split is performed I will have to generate the internal faces so that the left and right mesh will each still be closed. This is kind of a nasty piece of code to write, but it is still on my todo list. I have to do this anyway because one of my future projects is to produce 'fracture' artwork for destructible meshes.

Finally, I would ask one of my readers to help me out. It would be truly awesome of this tool worked directly inside of 3D Studio Max and/or Maya as a plug-in. It would help me out a lot of if one your plug-in gurus could integrate the library. If you are interested in doing such a project, please let me know!

Here is documentation for the deliverables in ConvexDecomposition.zip


After you unzip the file you will see two directories.

ConvexDecomposition : Contains the source that builds the library.
DecomposeSample: A console application and demo assets showing how to use the tool.

DecomposeSample contains:

chair.dae : A COLLADA 1.4.1 physics file generated by the tool.
chair.obj : A Wavefront OBJ file of a chair mesh.
chair.xml : A PhysX NxuStream file generated by the tool.
chess_table.dae : A COLLADA 1.4.1 physics file generated by the tool.
chess_table.obj : A Wavefront OBJ file of a chair mesh.
chess_table.xml : A PhysX NxuStream file generated by the tool.
DecomposeSample.cpp : Source for the console app showing how to use the library.
DecomposeSample.exe : The console app that loads a Wavefront OBJ and converts it.
DecomposeSample.sln : A .NET 2003 solution file.
DecomposeSample.vcproj : A .NET 2003 project file.

Usage: Test (options)

Options:

-d : How deep to recursively split. Values of 3-7 are reasonable.
-c : Percentage of concavity to keep splitting. 0-20% is reasonable.
-p : Percentage of volume delta to collapse hulls. 0-30% is reasonable.
-v : Maximum number of vertices in the output hull. Default is 32.
-s : Skin Width inflation. Default is 0.

DAE2XML : COLLADA 1.4.1 physics to PhysX NxuStream converter

The following code 'snippet' demonstrates how to load a COLLADA 1.4.1 file using the TinyXML parser. Once the COLLADA file is loaded it is then parsed so that the physics specific data can be extracted. Finally, the physics data is saved back out again in the PhysX NxuStream XML file format.

You might wonder why anybody would want to do such a thing. Yes, you might wonder indeed.

COLLADA is a proposed industry standard file format for 3D asset exchange. While this certainly a wonderful objective, to date, actually integrating COLLADA into a production pipeline has remained somewhat of a challenge.

Reading a COLLADA file is easy. It is XML afterall and there are a number of XML libraries in the world. Converting that XML data into a set of C++ classes held in containers has been a major sticking point. There are currently two libraries to read COLLADA data into a set of C++ classes. One is called COLLADA-DOM and the other is called Fcollada.

At first this might sound like a good thing. Hey, I can get hold of a library that does all of the 'difficult' part of converting the XML into classes that I can operate on. However, that isn't quite what is going on. Sure, the contents of the COLLADA file are now in a bunch of C++ classes, however what has that really bought you? You still have to interpret that data and, unfortunately, that is the really difficult part.

When I first tried to add COLLADA support I was going to use one of these libraries. In fact, I did get Fcollada going. However, once I realized that I *still* had to 'interpret' all of the data myself, I began to seriously rethink things. Now, not only did I have to struggle with interpreting the data I also had to learn an API. One problem with both Fcollada and COLLADA is that they are quite massive code bases.

What I wanted was something that was very light weight. And, out of the massive COLLADA specification, the only thing I wanted access to was the dynamics data itself.

I began writing my own COLLADA interpreter and, in general, it went fairly smoothly. The only major challenge was having to read the geometry data for triangle meshes and convex hulls. That is always the problem with COLLADA however.

I did finish my implementation and it reads 100% of the COLLADA 1.4.1 physics specification, including constraints. I also had to add some of my own extentsions in 'extra' tags for really essential dynamics data that was missing from the schema.

Now that I have finished the COLLADA parser I now recognize and understand the overall pattern. Were I to re-write it from scratch it would be a bit smaller and more efficient. Nevertheless, it works and if a whole slew of switch statements don't bother you, they aint' gonna bother me either.

My implementation clocks in at around 4,000 lines of code. It only reads the data associated with physics and ingores everything else. It *could* be used as a framework for interpreting more of the graphics elements in COLLADA. Since it had to read all of the geometry data for triangle meshes and convex hulls it would be fairly straightforward to extend it for graphics meshes as well.

The next big question, I suppose, is why am I releasing this on this site?

I am releasing it because of the degree of frustration I went through trying to 'get COLLADA to work'. This code is primarily being released as a 'learning tool'. If there are other developers interested in grabbing COLLADA physics data, and only COLLADA physics data, then this makes an excellent reference implementation.

COLLADA tries to support a lot of features. I can't even begin to list all of the things it tries to support. However, my own personal interest is merely using it as a data transport layer for physics content.

To date, I believe COLLADA is pretty much the only ever officially published attempt at a 'physics standard' for the industry. If that is the case, then I wanted to at least be able to read that format in.

I am quite certain that this code has bugs and errors of interpretation. That is ok. I will continually revise from time to time. I would like to thank Erwin Coumans who works on the Bullet Physics Library and Christian Laforte of Feeling software for their tremendous help getting this to work.

I am currently collaborating with two other developers who are writing their own COLLADA physics viewers. By exchanging our assets back and forth we are going to quickly be able to formalize the proper interpertation of COLLADA physics assets.

This file format that this tool saves out in is called 'NxuStream'. This is a reflective object model of the PhysX SDK data structures. It demonstrates the concept of going from a 'generic physics representation' to a specific run-time model. Conceptually it doesn't matter if the code saves out NxuStream or, instead, sends the appropriate physics data to your own application. I placed all of the 'save' code at the bottom of the file so it could easily be modified by other tools developers.

Here is the list of source files provided:

DAE2XML.cpp : A simple console application showing how to use the converter.
DAE2XML_Asc2Bin.cpp : An ASCII to binary converter utility.
DAE2XML_ColladaPhysics.cpp : My code that interprets COLLADA 1.4.1 physics data.
DAE2XML_hull.cpp : A version of 'StanHull' wrapped in a namespace.
DAE2XML_tinystr.cpp : TinyXML string manager.
DAE2XML_tinyxml.cpp : TinyXML classes.
DAE2XML_tinyxmlerror.cpp : TinyXML error manager.
DAE2XML_tinyxmlparser.cpp : Tiny XML parser.

All of this source is wrapped in a namespace 'DAE2XML' so that it can peacefully co-exist with other code in your application.

The usage is as follows:

Include "DAE2XML_ColladaPhysics.h"

DAE2XML::ColladaPhysics *cp = loadColladaPhysics("test.dae");
saveNxuStream(cp,"test.xml");
releaseColladaPhysics(cp);

You will note that the class 'ColladaPhysics' is a container for all of the previously interprted COLLADA physics data. You can easily make a new routine to save that data out in the format your own application may need.

You can also add methods to perform callbacks to your application supplying the data in any format you wish.

The download includes several sample COLLADA physics files (there are no graphics in the files). They are:

chair.dae : A chair converted into a set of aggregate convex hulls.
character.dae : An auto-generated rag doll model.
chess_table.dae : A chess table converted into a set of aggregate convex hulls.
deer_bound.dae : A deer model turned into a rag doll model containing only boxes.
hornbug.dae : A stiff rag doll of a six legged horned bug.

A number of 'extra' tags have been added to the COLLADA source data to carry critical, but missing, data that is not currently in the COLLADA spec. The biggest addition was for the drive model in the six degree of freedom constraint.

I will soon be providing a link to a physics viewer that can display both COLLADA physics and NxuStream format physics data.

Here is a link to the project:

DAE2XML.zip : This is a small download, only 335k even with sample data.

Schema files for NxuStream:

NxuStream.xsd
NxuStream.xsx

The main COLLADA web site.
The Khornos Group that manages the COLLADA DOM.
Feelilng Software that provides COLLADA importers, exporters, and FCollada.
The PhysX SDK
The Bullet Physics library and COLLADA physics viewer from Erwin Coumans (I am working with Erwin to make sure we can seamlessly exchange data between our two viewers.)
Bullet Physics Forums

Asc2Bin

Today's code snippet is a routine that I find extremely handy any time I am trying to parse in some data, especially something like some XML text values.

What ASC2BIN does is convert a stream of ASCII data into an exactly formated binary representation.

So, by example, let's say you wanted to read three floating point numbers into a vector.

With ASC2BIN you would simply do the following.

Asc2Bin("0.25 0.5 1.0", 1, "fff", &vector.x );

The first parameter is the ASCII soure data. The second parameter is how many items you expect. In this case, one vector. The third parameter is the input type. Here it is 'fff' which indicates you are expecting three floating pont values. The last argument is the destination location. If you pass in a null pointer Asc2Bin will allocate memory for you. If it returns NULL then it failed to find sufficient input data to populate the data.

As a variation, say you were expecting three float vectors.

Asc2Bin("0 1 2 3 4 5 6 7 8",3,"fff", &vector[0].x );

Now, let's say you don't know how many float vectors there are in the input. You can use this varation.

int count;
void *mem = Asc2Bin("0 1 2 3 4 5 6 7 8", count, "fff");

This version will allocate memory for the results and tell you how many it found.

Now, lets say you wanted to read in 4 one byte hex values.

You could do the following:

unsigned char result[4];

Asc2Bin("98BFEAFF", 1, "x1x1x1x2", result );

The notation 'x1' indicates a one byte hex value. If you don't include spaces in the source, then each hex value must be the correct width.

Let's say you wanted to parse some name fields.

You might use this:

const char *names[4];

Asc2Bin("John Larry Moe Curly",1,"pppp", names );

The results will point to the first letter in each name field of the source dat. It is quite important to note that the names will not be zero byte terminated since the source is a const char pointer. You must search for the whitespace yourself.

This format can also be used for reading FVF style data. FVF stands for 'flexible vertex format'. Let's say you have a vertex that looks like this.

struct vertex
{
float position[3];
float normal[3];
float texel[2];
unsigned int color;
unsigned char bones[4];
float weights[4];
};

You could read an array of these vertices from ASCII source using the following code.

"fff fff ff x4 bbbb ffff"

'x4' stands for a hex value 4 bytes wide. 'b' represents an unsigned byte sized value.

One additional feature is that the the maximum and minimum floating point value can be represented in ASCII as the following varations 'FLT_MIN', 'FLT_MAX', 'FLTMIN', 'FLTMAX', 'INF', '-INF'.

I dunno, maybe I'm the only one who thinks this is useful. However, I use it all of the time and it is sure a lot nice than 'sscanf', if you ask me.

Here is the header file: Asc2Bin.h
Here is the implementation: Asc2Bin.cpp

I demo main is at the bottom of the implementation to show how to use all of the options. Turn the pre-processor define DEMO_MAIN to zero if you want to add the routine to your own project.

Best Fit Oriented Bounding Box

There was recently a discussion on the Algorithms mailing list on this topic. The standard way to find the best fit OBB is to compute the covariance matrix or something like that. However, rumor has it that this method does not produce an optimal bounding volume.

Finally someone on the list said the 'best way' was to just use a brute force technique of spinning the point cloud around looking for the minimal volume. I was surpised that the 'best way' was the most crude technique but rather than argue about it I just implemented it.

I have used this routine in production code and it seems to work fine, but it is a bit slow. I'm sure there are refinements that can be made to the algorithm that attempts to narrow down the best rotation angle. If you make such refinements please email me the corrections.

This routine computes the 'best fit' oriented bounding box of an input point cloud by doing an exhaustive search. It spins the point cloud around searching for the minimal volume. It keeps narrowing down until it fails to find a better fit. The only dependency is on 'float_math.h' and 'float_math.cpp'


The inputs are:

vcount : number of input vertices in the point cloud.
points : a pointer to the first vertex.
pstride : The stride between each point measured in bytes.

The outputs are:

sides : The length of the sides of the OBB as X, Y, Z distance.
matrix : A pointer to a 4x4 matrix. This will contain the 3x3 rotation and the translation component.
pos : The center of the OBB
quat : The orientation of the OBB expressed as quaternion in the form of X,Y,Z,W


Please email bug fixes or improvements to John W. Ratcliff at mailto:jratcliff@infiniplex.net

If you find this source code useful donate a couple of bucks to my kid's fund raising website at www.amillionpixels.us

Here are the sources:

bestfitobb.h
bestfitobb.cpp
float_math.h
float_math.cpp

Float Math

Even though I have previously posted some matrix, vector, and quaternion code on this site, this one is a bit different.

I am uploading a code snippet that I will continually update from time to time. It is a little library I called 'Float Math', which provides vector, matrix, and quaternion functions without the use of classes, structures, or templates. The methods all use a standard C syntax.

All inputs are in the form of a 'const float *' and all outputs are a 'float *'.

You might wonder why such a thing is useful. Well, it allows a person to easily use it as reference material. Additionally you can just drop it into your own code base without conflict with any math libraries you might already be using. In virtually all cases a developer can simply cast their own vector, matrix, or quaternion class to a pointer and use these routines.

The routines provided here are by no means complete. I am adding methods to it one at a time, as I need them. When I upload more complex geometric code in the future I will try to limit my math functions only to 'float_math' and nothing else. As I revise 'float_math' from time to time the list of useful utility functions will simply grow.

'float_math' makes three basic assumptions.

It assumes that a point or vector is 3 floats in the form of X,Y, and Z. If you have a math library that doesn't express a point or a vector as 3 floats I am surprised. I know you might ask, but what about double precision? Yes indeed, what about it? As a game developer I work in 32 bit floats. The code is simple enough to modify to suit your needs, so go ahead and change it if you want.

It assumes that a matrix is 'float *' that represents a 4x4 matrix compatible with OpenGL or Direct3D.

It assumes that a quaternion is 4 floating point numbers in the form of X,Y,Z,W.

That's it.

Here is the header file: 'float_math.h'
Here is the implementation: 'float_math.cpp'

Even as I update the files, these links will stay the same.

Gestalt

In July of 1988 I published an algorithm called 'Gestalt' in Dr. Dobbs Journal. The term 'Gestalt' refers to the ability of the human mind to filter data and find patterns even if the source is full of holes.

At the time I wrote the article I was frustrated that I could make a single typo in a program and the compiler would generate hundreds of error messages, even though, it was fairly obvious what I 'meant'. Had the compiler simply continued with the best assumption I would have received only that warning and been able to continue to see valid results past that. The main reason I developed it initially, with the help of my friend John Oberschelp, was to assist in educational software; not only for a spellchecker but also to be able to tell that a student got the answer to a question correctly even if it was slightly misspelled.

Back then it was generally frustrating that computers were never forgiving in any way. Now, almost twenty years later, we are just finally getting used to having software figure out 'what we meant' when we make a simply typographical error. If you are like me, you probably use 'Google search' as a quick and dirty way to spell check from time to time. You can find some kind of an official looking algorithms link here.

My original implementation was written in 8086 assembly language, which was really quite strange and bizarre. Later is was ported to a nice simple recursive C routine. I needed the routine today and decided to search the internet for the source (one of the nice things about releasing source on the Internet is that you always have a very wide archival backup mechanism).

Here is an absurd implementation I published that shows how to convert a big pile of text from filthy words into 'cleaned up' alternatives. It is somewhat amusing.

I also found an implementation that looks a lot like mine, but I'm not sure it is exactly identical. There is a discussion about that in the thread associated with the article.

My source to a routine called 'FuzzyCompare' is here. Simply call FuzzyCompare instead of strcmp and it will return a percentage match in the range of 0-100.

gestalt.h
gestalt.c

WildCard

I know I haven't posted anything for a while. I've been busy and I haven't been able to work on my convex decomposition code either. However, I am trying to package up my automatic rag doll generation code in the next week. This is source code that was previously released before with the Rocket application but I am refactoring it so that it can be used either as a library or a console application. The main features I am adding are the ability to customize the rag doll by pruning or collapsing bones and select shape types.

To implement this I am using a response file that lets you make expressions that will produce effects like 'all bones with the string (neck) in it will be assigned a ball and socket with these limits', etc. To specify the preceeding you would add the following line to your input response file.

*neck* joint=ballsocket swing1limit=35 swing2limit=30 twistlowlimit=-40 twisthighlimit=40

This would assign any bone with the string 'neck' in it to a ball and socket joint (three degrees of angular freedom) with a swing1 limit of 35 degrees, a swing2 limit of 30 degrees, and a twist low limit of -40 degrees and a twist high limit of 40 degrees.

Once you have a basic set of rules in place (pelvis, neck, spine, wrist, etc.) you can reliably auto-generate an approximate rag doll from any skeleton very easily. One of the key features is the bone collapse function which will do things like fold finger bones into the parent to create a more appropriate 'mit' shape for the end of a hand.

The version I will upload on this site will work with Unreal Tournament PSK files which contain mesh deformation and skeletal information. You can find any number of PSK exporters on the internet. I have another internal version that works with Granny from RadGameTools. The Granny version will only be made available to licensees of that product.

While working on the bone filtering code yesterday I had to ressurect some source I wrote so long ago I can't remember when I wrote it. Perhaps I released it previously on the old code suppository or perhaps never.

I remember the first time I just wanted to do a DOS style wild card search. As always, before I write any code at all I search the internet for existing source code that serves that purpose. When I did I found a bunch of references to something called a 'Regular Expression analyzer'. Apparnetly this is a wildly powerful string search mechanism that is also wildly difficult to figure out how to use.

I found a C implementation written originally by Henry Spencer in 1986 and later modified by Larry Hunter and Peter Carp. This version I downloaded was last modified by Mark Kantrowitz on July 19th, 1994. The C code compiled fine so I went ahead and used it.

As is my habit I put a C++ wrapper around the regular expression analyzer, but it only provided one method called 'match'. This was all I needed at the time but if you wanted access to more string matching features you would need to add new wrapper methods.

Finally, this wasn't my goal either. I'm a pretty old school DOS user and if I just wanted to find al files that ended in .txt, I was used to typing '*.txt" as my search request. However, in the Regular Expression syntax this same simple search becomes: "^.*\.txt$".

Forgive me if I think that is just a little bit more of a pain in the ass to type or remember. So, I wrote a wrapper around the regular expression class called 'WildCard' that translates the standard DOS style wildcard syntax '?' (single character match) and '*' (wild card match) to the regular expression semantic under the hood.

To use this, simply include 'wildcard.h'

Example:

WildCard wc("*.txt");

bool match = wc.Match("foo.txt");

Ok, so maybe this isn't rocket science but it does fall into the category of a 'snippet' and I do find it useful from time to time.

I hope to have the rag doll stuff up and available for testing in about a week.

However, *I NEED TEST MODELS*!

I have a bunch of test data from my friend David Whatley already. He gave me a bunch of the 3d models from his game 'Hero's Journey'. The thing is..they all work just fine. I need some a greater variety of 3d models to test all of the more difficult cases I might encounter. Even though the 'rules system' is fairly robust I still need more tests to make sure it is fully configurable.

Finally, if you ever find that even one of my snippets is useful then you are morally obligated to donate a few bucks towards my son's fundraising website. Please donate at least $4 to 'A Million Pixels US' whenever you can. All you need is a PayPal account and with one mouse click the whole thing can be over quite painlessly.

Here are the source files:

creg.h : Header file for Henry Spencer's regular expression analyzer.
creg.c : C implementation file for Henry Spencer's regular expression analyzer.

regexp.h : header C++ wrapper for the regular expression
regexp.cpp : C++ implementation of regular expression wrapper.

wildcard.h : DOS style wild card wrapper for regular expression.
wildcard.cpp : DOS style wild card wrapper for regular expression.

Windows Message

I know, you all thought this site was dead again, but it is not. I just don't find time often enough to update it. Today I decided to upload a code snippet that I worte, with the help of my friend James Dolan, a while back. It's a small code snippet and I think it is very useful.

How often do you ever just want to 'send a message' to another application or (more often) a DLL? If you are a tools programmer, that can be pretty often. Who wants to write a bunch of networking code or other garbage just to send a message around. A common use case is if you have a DLL plug-in and you would just like to 'tell it something'.

This code snippet is designed for that purpose. It uses Windows messaging to send information between any two components running on the same machine. It does this by creating a hidden window of a certain name and takes advantage of the 'copy data' mechanism.

What is special about this is simply the interface.

To send a message to any other software component you simply invoke 'sendWinMsg'. You pass it the name of the component you want the message to go to (effectively the 'name' of the hidden window) and an arbitrary text message using the 'printf' semantic.

If you wish to be a receiver of messages you simply inherit the base class 'WinMsgReceive' and provide a 'receiveMessage' method to get the answers. You must also called 'checkWinMsg' from time to time to pump the Windows message queue.

You can find the prototype here as 'WinMsg.h'

And the implementation is here as: 'WinMsg.cpp' If you don't have an 'stdafx.h' file in your applicaiton then just delete that #include.

For a complete demo program you can compile and run, download 'WinMsg.zip' here.

The demo program is a console application that you can use to poke messages at your application.

Here is an example of how to use it.

Launch the first copy as: 'WinMsg window1 window2'
Now, launch a second copy as: 'WinMsg window2 window1'

You will then be able to send and receive messages back and forth between the two of them.

Obviously sending Windows messages is pretty programmer 101 stuff. What I like about this snippet is that the public interface is reduced to something as simple as a 'printf' statement and it completely hides the Windows garbage from the rest of your application. A person could implement this same system using other forms of interprocess communication and still keep the public interface exactly the same.

Welding

General Purpose Welding Template by Ignacio Castaño using the STL and a hash_map.


Ignacio Castaño generously donated a useful code snippet to the Code Suppository. Actually he put it on his own coding website as well.

Ignacio is a 3D tools and technology engineer at Nvidia and makes frequent contributions to the development community. He is also active on the the algorithms mail list. His most recent experience, prior to working for Nvidia, was as a developer at OddWorld Inhabitants. Prior to that he worked for Relic Entertainment, Nebula Technologies, and was a lead grpahics programmer at Crytek. You can find Ignacio's complete resume here.

After I posted my first snippet on performing a vertex lookup table Ignacio emailed me and said he had a much better implementation that used a hash approach. Today he emailed me a revised implementation that uses the STL so that it can map to the 'snippet' form.

What is cool about his templated implementation is that you can use it to removed duplicates from any data set, not just vertices. Since it does an exact match, if you want to collapse your vertices based on an espilon value I recommend you round them off prior to submitting them to the routine. The operation returns a new re-ordered list of input data with all duplicates removed and re-indexes an index buffer that references those source vertices.

He includes a demonstration usage within the .CPP file, so this single .H and .CPP will compile, link, and run as is.

Ignacio says that it is very important that I credit Pierre Terdiman and Ville Miettinen for their input on the implementation. There was a discussion on the algorithms mail list some time agou about the 'best' and 'fastest' way to remove duplicates from an arbitrary data set and the hash approach, apparently, won out. It's certainly going to be faster than the STL set I used in my previous implementation. However, what I do prefer about my old one is that you don't have to call a discrete 'reorder' operation. Mine reorders on a vertex by vertex basis, so you can use it as a part of a general 'mesh building' tool. That said, I'm sure his implementation could be refactored to have a similar usage pattern.

If it has never occured to you as a problem to remove a set of duplicates from an input data stream, well now you have the answer anway.

Here is the header file: 'weld.h'
and here is a usage demonsration of the templated class: 'weld.cpp'

Thanks Ignacio!

Approximate Convex Decomposition

Well, once I fixed those couple of bugs from yesterday I made a lot of progress today. In fact, I am beginning to become really pleased with the results. First of all, this implementation is still not using my 'optimal split plane' code. I will be working on that again tomorrow. Instead it is computing a split plane simply based on the longest axis of the AABB. This results in bad split decisions all over the place and way more hull fragments than you want.

So, why do the hulls above look so good? Because I added an optimization / cleanup phase at the end that re-combines hulls if they turn out to be convex when collapsed. What I do is produce all of the convex hulls based on recursively slicing concave pieces. Now I have a list of leaf nodes, each one a convex hull. I then sort all of those hulls by volume, the largest volume to the lowest. Next I try to combine each hull with all others in the list, checking to see if the sum of the volume of both is nearly equal to the sum of the volume of each separately. If the volumes are nearly the same (within a threshold provided by the user), then they can be combined into a single hull. I keep doing this until I can no longer collapse any leaf nodes.

To produce the approximate aggregate hulls it has three tuning parameters.

(1) The maximum recursion depth.

(2) The concavity threshold. This is represented as a percentage of volume relative to the original hull.

(3) The percentage volume approximation which is acceptable before two leaf hulls will be collapsed.

The series of images above represent different recursion depths and tolerance values. I am very pleased with the quality of the results.

Please remember that the ultimate goal of this effort it three fold.

(1) Produce good approximate aggregate collision volumes from arbitrary meshes (closed or open, either way!) This tool will work either as a command line console app (so you can batch process every art asset you have), inside of 3D Studio max or Maya as a plug-in, or simply as a library for your own application. The parameters are user tunable and an artist or game designer can make a choice as to which one of the approximations is most appropriate for the needs of their application.

(2) Skeletonize the hulls. I haven't yet decided on the ultimate algorithm for this, but the general ideal is to create a connectivity graph of all of the leaf nodes so that they can be turned into constraints. This will automatically produce a ragdoll-like skeleton for an arbitrary solid mesh (with no artist intervention). Finally, it will tesselate the source artwork and autogenerate a deformed mesh with 4 bone weightings to the nearest constraints for every vertex. This will produce auto-generated soft-bodies which can be skinned on a GPU and simulated as a set of constrained rigid bodies on a physics engine.

(3) Finally, to use the tool to decompose closed meshes for pre-fracture. This tool will be responsible for generating the internal faces for the mesh whenever a split plane is performed. It will also be able to synthesize a fractal noise pattern to make the internal faces look rougher, like broken stone. The user will be able to supply a source material for the internal faces. The result will include both a physics and a set of graphics models that can represent breakable objects. Currently it is very time consuming process for an artist to manually create fractured objects. And, even if they use a commercial tool, still getting this hooked up to a physics engine is a major challenge.

If you want to see the full resolution image of the series of approximation you can click on this link.



I was rather proud of how well my tables and chairs were decomposing so an artist friend of mine decided to give me a real challenge. He sent me this very high resolution twisted helix model. I ran the decomposition routine on it and was very pleased to see it produce a really awesome looking convex decomposition of about 48 pieces. Then I decided to start really pushing the tolerance levels to see how coarse I could make it but retain high fidelity collisions. I was amazed when I got the following result with only 22 hulls.

I made a windows movie file to show the quality of the physics simulation that runs against it. The movie file shows the helix rolling along the ground (very smoothly) and switches between the graphics representation and the physics approximation. Remember that all models shown here were created simply by passing a raw triangle mesh to a single routine with a single button click on my PhysX Rocket application.

Here is a link to the windows movie file.

If you have the Bink video player from Rad Game Tools you can download the full resolution version here.




Here is a nice looking approximation of a fairly complicated table. Clicking on any of these pictures will bring up a higher resolution image. Each seperate hull is 'color coded' by assigning a different random texture.



Here is an approximation of a complex chair. Imagine in your minds eye this object being used for pre-fracture.



Here is an auto-generated crude approximation of the high resolution source model of a cat.

3D models courtesy of Simutronics Corporation from 'Hero's Journey'.

I am fairly pleased with the results. All of the code that is being written for this little project is being done in 'snippet' form. And, I promise, that the end result will work with a single C API call. I will probably write a 3D Studio Max plugin as well.

My next tasks are:

(1) Find the best possible splitting plane

(2) Auto-generate OBB box primitives instead of hulls if they are a better approximation.

(3) Allow the user the option of asking for capsules instead of boxes or hulls. (Good for auto-generated ragdolls)

(4) Track down a bug which somtimes decomposes meshes into hollow objects. (If I decompose the Stanford bunny with a lot of recursion it is hollow inside. Since everyone knows I like solid-chocolate rabbits, I need to fix this issue).

Once it has these features, take care of edge conditions, and flush out any possible crash problems, I think it is ready to be a production tool. It is already pretty stable and I have run a lot of test data through it. Other than the problem with hollowing out some objects if I recurse too deeply it is is working pretty well in the general case. Today we made a tree with a bunch of proxy polygons which were supposed to represent 'billboarded' leaves. The algorithm cranked on it just fine and produced an excellent approximation. The fact that the algorithm does not require closed meshes it a major feature in my opinion.

The soft-body stuff may not be made public right away. Especially since it will be so dependent on graphics code which will touch on file formats and custom vertex shaders. Nevertheless, rest assured that I will try to always write in 'snippet' form so that you can cull any gems out of the code you might find useful.

Finally, when this whole thing is complete I would like to publish it as a 'Graphics Gem' somewhere. My effort here was originally inspired by a Siggraph paper I read a few years ago. However, that paper is filled with so much advanced mathematics that the only thing I understood from it was the pretty pictures. Today I am uploading my own pretty pictures and I promise that when I explain my algorithm there will be absolutely *no* fancy math whatsover. How could there be? I don't understand it.



I would like to add this little postscript and thanks. Erwin Coumans, who runs the very popular physics themed website 'Continuous Physics' and message forums, generously and spontaneously donated $50 to my fundraising website. This is truly above and beyond the call of duty. I will be sure to send him several 'Willy Wonka' chocolate bars as thanks for his generous spirit. It just goes to show that the Internet *can* be a tool to build a community. No, it's not like Erwin and I have sat in lodge together or anything. Nevertheless, here is a guy who read my posts and felt compelled to donate to a worthy cause.

Sure, I'm sprinkling all of my source code snippets with hyperlinks to my fundraising website, but, so what? I'm going to be giving away some truly useful source code over time. While it is true that, other than StanHull (which I didn't even write I just wrapped), I haven't released a single original thing yet to date. However, I really think this aggregate convex hull tool is going to be generally useful and I believe that simply the process of 'snippifying' other people's source code (such as David Eberly's plane fitting routine) is of real value.

To date Erwin is the largest contributor to my sons youth group and was the first to purchase the few available rectangular advertising spots at a full 100x50 pixel resolution. Thanks Erwin!!!

I am humbled and thankful for Erwin's generous and spontaneous donation to this worthy cause. If you find, some day, that you use one of my code snippets and it saves you a little bit of time and effort, then please follow the example of Erwin and throw a few bucks towards a worthy cause by donating to 'A Million Pixels US' to support Missouri Masonic Youth groups.

Bug fixes and progress update on Convex Decomposition

The original raw source artwork which was loaned to me by my friend David Whatley of Simutronics from his game 'Hero's Journey'.



The auto-generated aggregate convex hull representation.

I still have work to do on finding the best approximate split plane. This implementation just performs a straight axis-aligned bounding volume decomposition. However, it has the following optimization. At each stage it computes the 'volume of concavity' by projecting each source triangle onto the surrounding hull and computing the tetrahedral volume. The sum of this volume is a score of overall 'concavity' and is then represented as a perctantage of the volume of the original hull. It will keep recursively subdividing so long as the percentage of concavity is greater than a threshold percentage provided by the user.

Except for computing a better split plane, I'm pretty happy with these results.

My next task is to infer a skeletal model between all of these convex hull pieces and compute a constraint system to simulate soft-body effects by skinning the original mesh. This will require me to auto-tesselate the original source mesh and automatically compute the bone weighting contribution based on the nearest constraints. I have done this technique previously before in PhysX Rocket with my cloth and rope demo. The difference here is that I will be decomposing and skeletonizing and arbitrary 3d mesh.

While working on this project I discovered two bugs.

My sample code to do a 'vertex lookup table' that I uploaded earlier did not have an espilon value in the compare operator. Therefore if two points were nearly identical (but not exactly down to many decimal places) they would not be matched up. I have revised the code to reflect a default epsilon value of 0.0001.

You can still find it here as 'vlookup.h' and 'vlookup.cpp'

I received an email from Ignacio Castano suggesting a more optimal implementation for a vertex lookup system using a hash table. He sent me a code snippet, however it will not compile standalone since it is dependent on other source. He did say he might update it to use the STL and I will post it here if and when he does. For now, here is a copy of the partial implementation he emailed me.

Here is a copy of the email I got that came with the code-snippet:

Hey John,
I've attached a small code snippet that you might find useful. It's
based on a discussion at the GD algorithms mailing list between Pierre Terdiman
and Ville Miettinen, in a thread called "A better method of removing duplicate
vertices..." in July 2002.
Pierre used radix sort to weld vertices, while
Ville used a hash, it turned out that Ville's solution was slightly faster and
he provided a small code example to prove it. I took that code, templatized it
and also modified it to provide an xref array similar to the one produced by the
radix sort.
I use that code very often, not only for welding vertices, but
also to weld other things, like edges or faces. In general, I use it anytime I
want to unify an array of elements where there could be duplicates.
If you
think that could be used for a code snippet post, I could update it to use stl
containers and functors instead of my own. Let me know if you are
interested.
BTW, another interesting algorithm is how to weld vertices that
are within a certain radius in an efficient way.
--
Ignacio
Castaño
castanyo@yahoo.es

The second bug I encountered was with my triangle splitting code. It turns out that it can produce degenerate triangles (triangles with duplicate positions). However, I did *not* revise the code because it is actually faster and more efficient to remove the duplicate positions after you run them through the VertexLookup code. After you turn the vertex positions into indices, just check for duplicates and don't add that triangle or face if there are.

That's all for today. I will still upload my bounding volume code when I get a free moment. I also will upload a copy of my aggregate convex hull code as soon as I am satisfied with the initial implementation and have it converted into 'snippet' format.

Since building an aggregate convex hull requires quite a bit of code there will not be just a single .CPP and .H file. Instead it will be a library. However, the entire library will be in a namespace and you will be able to invoke the hull generation process with a single standard C function call. You will simply pass it an interface pointer to receive the results back as the component hull pieces are assembled.

LookAt Sim Dietrich

I was fortunate enough to visit with my friend Sim Dietrich last week. In fact we even got to do a little bit of paired programming together, which was a great honor and privilege for me. I have been listening to Sim speak at conferences for the past ten years or so and he has been a great source of inspiration.

I was really encouraged to find out that he reads my 'Code Suppository' and agrees with my concept of providing code snippets in a form that have no dependencies on any other code.

Today's submission is an excellent example of that principle. In a day or so I am going to be uploading the axis-aligned bounding volume hierachy code I promised before. It has been 'good to go' for some time, but I honestly don't believe I can release it without a small sample app that shows its usage. I plan to create a sample application that builds an array of a million objects over an 8 kilometer range. These objects will be placed into the AABV tree and I will fly a camera through that space using the frustum class previously posted for culling purposes.

To provide this application I will need to be able to orient my objects, create a world to view matrix, and compute a projection matrix. It's damned hard to find references for these three common operations that are not dependent on either GLUT or D3DX. Well, now you have one...

Here is the prototype in 'lookat.h'
And here is the implementation in 'lookat.cpp'

Some Google videos from my last game project

I wrote the 3d engine for a game called "Plantside" when I worked for a company called 'Sony Online Entertainment'. Actually, the company I went to work for was called 'Verant Interactive'. They created a game called 'Everquest' which was a big success. The president of the company is a friend of mine named John Smedley.

John not only offered me a job but also set up an office near my home in Lake Saint Louis. I was hired in October of 2000 and I slowly tried to build a team. It was a real challenge, though we did have an impressive demo video at E3 2001. (In fact, I have a really cool collection of screenshots somewhere that show the progression of the game visualization. If I can find them someday I might upload them.)

It would be a lengthy story for me to describe the entire evolution of this project and I don't feel like repeating it here, or at least certainly not now. The reason I am posting this message is because I, like many, have become a big fan of 'Google Video'. Just this evening I finally thought to type in 'Planetside' and found a bunch of marketing videos that show the evolution of the technology as well as a number of fan videos.

For the record, I was responsible for the entire 3D engine, effects sytem, character animation, collision detection, and most of the tools. That was in addition to setting up the Saint Louis office, building and managing the initial team. The Planetside engine was written to take maximum advantage of the fixed function pipline. It has virtually no shaders and the couple it does have were written in some early draft version of CG. I created a tool set that would let you recombine the fixed function pipline in almost any permutation interactively. These tools were made availalbe via a relatively sophisticated yet simple to use suite of dialog boxes that allowed artists to change the properties of every material surface, particle effect, animation setup, or pretty much anything else, in real-time and submit the results through source control. In general the bulk of the engine was data driven.

The game engine looks pretty dated by modern standards and was fairly dated at the time it shipped. However, it was able to support a massive number of players at interactive framerates in truly giantic worlds; features that are still generally lacking in most modern game engines. I wrote an article for "Massively Multiplayer Gems" describing some of the optimization techniques I used to render so many characters, vehicles, and weapons, on the screen at once.

So, that is all I really wanted to say. I love that you can now embed Google video's directly into your website. I think it is even cooler that I can embed video from an actual game engine I wrote straight into my resume. Not that I'm actively looking for a job or anything, but it is cool that you can include it.


Here is a link to a news story that was done about my involvement in the project.

St. Louis Business Journal.

And, here is one where I got the *cover* of the Saint Louis Business Journal shortly after we started the project.

Maybe I shouldn't be so proud that I want to take credit for an outdated, fixed-function pipeline, game engine. Nevertheless, I worked longer and harder on that project than anything I have ever done before. And, even though it didn't necessarily compete visually with other FPS games back then, much less today, the experience of having three hundred guys with tanks, airplanes, weapons, and all manner of vehicles fighting in a massive combat arena did seem like something special then and, I still think it is today.

Heck, I was (I think) the first person to write a 'salad system' where you create the illusion of an infinite array of blades of grass by fading them in and out parametrically on the fly.

Here are some Google videos from Planetside.












Video from a really, really, early version of the game engine.

DFRAC

About ten years ago I released a DirectDraw fractal program on the Internet, or compuserve, or whatever existed back then. A while back I saw that it still existed in the bit stream so I went through my ancient archive backup CD's until I found a copy of it.

I have just zipped it up and it uploaded it in raw form. It actually *does* compile with Visual Studio 6 even today! I don't know if it compiles and links with .NET, but I'm not sure it's particularily relevant since I plan to rewrite it any way.

You might wonder what makes a fractal program unique or special or anything. However, this one had a few interesting design goals. First of all, it was written at a time when processors were measured in the low tens of Mhz not in Gghz speeds. Drawing a fractal took a damn long time.

The design goals for this fractal program were:

* Draw as much of the fractal as possible as fast as possible first.

* Compute the relative 'difficulty' of the fractal and be able to spawn portions of the fractal off to be computed over a network.

* Take advantage of a proof discussed in "Scientific American" to dramatically speed up fractal computation.

* Take advantage of optimized floating point assembly code to speed up the fractal inner loop.

* Allow the user to pan and zoom the fractal while it was still drawing.

* Since a fractal took so long to draw make the drawing process itself visually entertaining.

* Allow the user to capture fractal locations and create spline interolated movies from a set of data ponits.

* Allow the user to easily switch between preview mode and high-resolution mode.

This was one of the first programs I ever wrote that used DirectDraw or the Windows GUI.

Amazingly it still compiles and runs. The DirectDraw surface gets a little messed up at times, but mostly it renders ok.

In a 'Scientific American' article somebody mentioned a 'proof' that if you can create any bounded surface in a fractal image that has the same value on the edges, then all of the interior points have the same value as well. I don't know how they 'proved' that, but I took advantage of the technique.

This program begins by drawing borders around the image and recursively subdividing it a couple of times. As it computes the border it assigns a 'computation difficulty' score to it. The portions of the screen, subdivided into rectangles and remaining to be calculated, are then placed on a priority queue 'to be solved'. Whenever a rectangle has the same value across the entire border it just gets 'filled in' immediately.

This version doesn't have the code but, at one time, a friend of mine and I made a custom build that used NETBIOS to transmit the fractal problem over a network and get the results back. It was a very early distributed processing system. Back then, with such slow processors, this proved to be a major benefit. We would get really cool results as packets came over the network with the answers. The fractal image would 'fill in' all over the place based on network solutions.

I am first uploading this code 'as is', which is a pile of horrific and ugly C and assembly code from a decade ago.

What I plan to do is rewrite this demo with the following changes:

* Make it multi-threaded so that fractal computations can be shared across multiple processors.

* Rewrite the code in reasonably clean C++ using STL for the priority queue.

* Switch to DirectX 9 and Direct3d for the rendering.

* Render the fractal in full 3d as triangles and let the user interactively spin it around.

I think this will be a really entertaining code snippet in its refactored form.

Until then, here is the original ancient demo.

Volume of a convex triangle mesh

Today's code snippet is a routine that computes the volume of a convex triangle mesh.

The prototype for the routine is as follows:


float computeMeshVolume(const float *vertices,unsigned int tcount,unsigned int *indices);

You can download implementation one here:
And implementation two here:

Map Palette

Color Palette Maker and Loader utility.

I find this code snippet to be of value from time to time. This is the first code snippet that comes with an executable 'utility'. What the utility does it lets you easily select a handful of colors. It will then linear interpolate between your color selections, creating a lovely gradient. You can simply select as few as five or six colors and get a very interesting color gradient.

Gradients can be used for a variety of graphics effects in game and tools. The are used when rendering fractal images, particle effects, debug visualization, terrain compositing and a lot of other things. A common technique that needs a color palette is to index into one based on the height value of a terrain sample. However, before you apply that color you modulate the index based on the instantaneous slope value of the terrain at that location. This produces a nice 'marbaling' effect, similar to what you see in the photograph above or the following synthesized image.



When you use the palette tool you can load and save '.PAL' files which are just a simple text file that lists some colors at 8 bit RGB values. You can always just edit the text file manually if you wish. A comment character is '#'.

If you want to load and use a color gradient you simply include 'mappal.h' and create an instance of the MapPal class.

That's all there is to it. It's nothing amazing but I find when I happen to need a quick gradient for some reason this gets the job done.

You can download the MaPal source, with a sample palette, and the palette utility here as mappal.zip.

Here is an example that loads a palette file called 'test.pal' and then retrieves the entire color gradient both as floating point and as 8 bit RGB values.

MapPal mp("test.pal");
for (int i=0; i<255;>

Vertex Lookup

Vertex Lookup system to rapidly build Indexed Triangle Lists from raw Triangle Point Data.

This snippet shows how to 'hide' the complexity of the STL by wrapping some useful piece of functionality around a handful of discrete API calls.

This API allows you to create an indexed triangle list from a collection of raw input triangles. Internally it uses an STL set to build the lookup table very rapidly.

Here is how you would use it to build an indexed triangle list from a raw list of triangles.

(1) create a 'VertexLookup' interface by calling

VertexLook vl = Vl_createVertexLookup();

(2) For each vertice in each triangle call:

unsigned int i1 = Vl_getIndex(vl,p1);
unsigned int i2 = Vl_getIndex(vl,p2);
unsigned int i3 = Vl_getIndex(vl,p3);

save the 3 indices into your triangle list array.

(3) Get the vertex array by calling:

const float *vertices = Vl_getVertices(vl);

(4) Get the number of vertices so you can copy them into
your own buffer.

unsigned int vcount = Vl_getVcount(vl);

(5) Release the VertexLookup interface when you are done with it.

Vl_releaseVertexLookup(vl);

Teaches the following lessons:

How to wrap the complexity of STL and C++ classes around a simple API interface.
How to use an STL set and custom comparator operator for a complex data
type.
How to create a template class.
How to achieve significant
performance improvements by taking advantage of built in STL containers in just
a few lines of code.
You could easily modify this code to support other
vertex formats with any number of interpolants.

You can find the header file here as 'vlookup.h'

You can find the implementation here as 'vlookup.cpp'

Best Fit Plane

A Code Snippet to Compute The Best Fit Plane Equation to a set of weighted input data points.

I believe this to be a remarkably useful code snippet. First of all, I DID NOT WRITE THIS SNIPPET I MERELY 'REFACTORED' IT!

This snippet was written by David Eberly and is published on his website Geometric Tools. As soon as you finishing donating a few bucks on my fundraising website, then run out and purchase some of David Eberly's excellent books!





David Eberly is a prince. He has the most incredible resource for geometric computation on the Internet. His site is a hundreds times, nay a thousand times, more useful than this lame little code blog will ever be. David Eberly has been inserting suppositories into the Internet for as long as I have and he's been using extra-strength code capsules to do it. David has an extremely generous source code license agreement, allowing for use in both commercial and noncommercial projects.

This code snippet accepts an input array of 3d data points and an *optional* array of per vertex 'weighting' values. Weightings are relative so there is no requirement they fit within some specific range. This method will perform a least squares approximation to the set of input points and output the best-fit plane equation that conforms to the point cloud.

You can read about the algorithm on David's website here and you can find his original implementation here.

David's library is great and easy to use. The only thing is, like a lot of libraries, it is very powerful and very general purpose. That means if you just want to make use of a single feature you have to inherit a very large infrastructure of code to get at that functionality.

What I did was extract out only the code necessary to perform this single function. The code was wrapped in a namespace inside the implementation to avoid name clashing with anything in your application.

You can find the prototype for the function here as 'bestfit.h'
You can find the implementation for the function here as 'bestfit.cpp'

Plane Triangle Splitting

This snippet demonstrates how to perform Plane-Triangle Splitting.

I believe this code snippet is truly generally useful. It is especially handy for building BSP trees. This routine accepts a triangle and a plane as input. It allows the user to set the vertex 'stride' for the input triangle. It is intended purely for geometry processing and doesn't handle interpolants.

The routine will decide if the triangle is fully in front of the plane, fully behind the plane, or straddles it. If it spans the plane then the triangle will be split into two polygons, a front and a back. Realize that a split triangle will produce a triangle fragment and a tetragon(polygon with 4 vertices). The buffers you provide should have room for four output vertices.

You also get to specify an epsilon tolerance threshold to gracefully handle almost exactly co-planer triangles. Extremely thin slivers will cause problems for collision detection routines and a reasonable epsilon will minimize that artifact.

You can find the header file with prototype of the single function call here as 'planetri.h'.
You can find the implementation here as 'planetri.cpp'

Stoopid Semi-Useful Plane Equation Functions

In keeping with the theme of the last post I am today going to upload several discrete functions that can be used by themselves or as a whole. These functions are so basic and so simple it might be pointless to upload them. However, since I use them on a daily basis they must be good for something.

What I believe makes them useful in this context is that they have no dependenices on any other code. If you want a reference implementation or just want to copy paste some quickie routines statically into your code, either way these fit the bill. I am uploading them individually first because they will be used in future snippets. I am getting fairly closed to having my first pass implementation of the aggregate convex hull generator working. When I upload that as a tool (with a single C style function call and a virtual interface to receive the hulls back to your application), I will discuss the entire algorithm in detail.

I hope you know what a plane equation is because when doing geometric computations you work with points, lines, and planes on a regular basis. Here are a few functions that represent typical operations with planes. As I said, the only thing 'unique' about these functions are that they have no dependencies on other code and accept 'const float *' as input.

You can just view the source code here.

Snippet #1 : Distance between a point and a plane.

// compute the distance between a 3d point and a plane
inline float distToPt(const float *p,const float *plane)
{
return p[0]*plane[0] + p[1]*plane[1] + p[2]*plane[2] + plane[3];
}

Snippet #2 : Side of Plane Test, true if in front (positive half-space) within an episilon

// Returns true if the 3d point is in front of the Plane within a user specified 'epsilon' value.
bool getSidePlane(const float *p,const float *plane,float epsilon)
{
bool ret = false;

float d = p[0]*plane[0] + p[1]*plane[1] + p[2]*plane[2] + plane[3];
if ( (d+epsilon) > 0 ) ret = true;

return ret;
}


Snippet #3 : Compute the Plane Equation from a set of 3 points.

// compute the plane equation from a set of 3 points.
// returns false if any of the points are co-incident and do not form a plane.
// A = point 1
// B = point 2
// C = point 3
// plane = destination for plane equation A,B,C,D
bool computePlane(const float *A,const float *B,const float *C,float *plane)
{
bool ret = false;

float vx = (B[0] - C[0]);
float vy = (B[1] - C[1]);
float vz = (B[2] - C[2]);

float wx = (A[0] - B[0]);
float wy = (A[1] - B[1]);
float wz = (A[2] - B[2]);

float vw_x = vy * wz - vz * wy;
float vw_y = vz * wx - vx * wz;
float vw_z = vx * wy - vy * wx;

float mag = sqrtf((vw_x * vw_x) + (vw_y * vw_y) + (vw_z * vw_z));

if ( mag > 0.000001f )
{

mag = 1.0f/mag; // compute the recipricol distance

ret = true;

plane[0] = vw_x * mag;
plane[1] = vw_y * mag;
plane[2] = vw_z * mag;
plane[3] = 0.0f - ((plane[0]*A[0])+(plane[1]*A[1])+(plane[2]*A[2]));

}
return ret;
}


Snippet #4 : Intersect line segment with a plane.


// inertesect a line semgent with a plane, return false if they don't intersect.
// otherwise computes and returns the intesection point 'split'
// p1 = 3d point of the start of the line semgent.
// p2 = 3d point of the end of the line segment.
// split = address to store the intersection location x,y,z.
// plane = the plane equation as four floats A,B,C,D.
bool intersectLinePlane(const float *p1,const float *p2,float *split,const float *plane)
{

float dp1 = p1[0]*plane[0] + p1[1]*plane[1] + p1[2]*plane[2] + plane[3];
float dp2 = p2[0]*plane[0] + p2[1]*plane[1] + p2[2]*plane[2] + plane[3];

if ( dp1 > 0 && dp2 > 0 ) return false;
if ( dp1 < 0 && dp2 < 0 ) return false;

float dir[3];

dir[0] = p2[0] - p1[0];
dir[1] = p2[1] - p1[1];
dir[2] = p2[2] - p1[2];

float dot1 = dir[0]*plane[0] + dir[1]*plane[1] + dir[2]*plane[2];
float dot2 = dp1 - plane[3];

float t = -(plane[3] + dot2 ) / dot1;

split[0] = (dir[0]*t)+p1[0];
split[1] = (dir[1]*t)+p1[1];
split[2] = (dir[2]*t)+p1[2];

return true;
}

This Site is Not Dead

NO THIS SITE IS NOT DEAD!

I know you might think I made a few posts and then forgot about this site, but that is not the case at all. I threw a giant party this weekend and, before that, I was on a bunch of stoopid (TM) deadlines for GDC (if you don't know what GDC stands for, well then that is your problem.)

Today I finally got a chance to spend a little time on my automatic aggregate convex hull generator. I made a lot of progress, but it isn't done yet. As I am writing it I am also developing a number of 'snippets' that I fully intend to upload soon.

Maybe I'm the only one how thinks 'snippets' are cool. For example, one of my 'snippets' is just refactored code from one routine published by David Eberly in his giant 'Magic Software' library. So, what makes it 'useful' if all I did was republish his code? What makes it useful is that I will provide is as a single header file with a prototype of a single C style function call that has all of the entire implementation encapsulated and embedded ina single .CPP and that in a namespace to avoid clashing with your own application.

Is that useful? I think it is. In fact, I think it is very useful. All I freaking wanted to do was find the nearest approxoximation to a plane against a *weighted* set of input data points. There's enough mathematics to make your brain explode out there on the Internet and there are any number of libraries, including 'Magic Software', but *nowhere*, and I mean *nowhere* is there a freaking routine that just accepts an array of points and returns a plane equation as four floating point numbers representing Ax+By+Cz+D.

So, do I think that is useful? Hell yeah, I think that is useful. And, that is why I will upload it as a code 'snippet'. I will also upload a snippet that returns a 4x4 transformation matrix that represents the best approximate oriented bounding box for a point cloud. I will have another snippet that intersects a single triangle with a plane and outputs one or two polygons representing the 'split' against that plane (suitable for building BSP treees). I will have another snippet that returns an index lookup for a set of points in 3space, suitable for building indexed triangle lists in real-time.

These are just stoopid(TM) little useful snippets of code that have no external dependencies and can either be just 'dumped' into an existing application or easily massaged to fit your own data structures; all with no input or output requirements more complex than a 'float *'.

Don't get me wrong. I love Dave Eberly to death. His library is the second coming and more useful than a wallet full of singles at a strip-club, I'm just saying that sometimes you would like just one single useful routine extracted from tens of thousands of lines of code that are each dependent about the other. You know, its like sometimes you just want a lap dance, you don't necessarily want to go all of the way. That's what I'm saying here..

Ok, maybe that analogy sucks.

I just want to say that I *will* be posting new snippets soon and, no, this site is not 'dead'. I intend to use it as a vehicle to insert code nodules into the asshole of the Internet for as long as I shall live. Which, I hope, to be at least another couple of decades or so.

In the meantime. If you ever find any of my code-suppositories useful, then I ask you to go to this site, click a pixel with your mouse, and throw a couple of bucks towards my kids youth group. Look, it's not like I'm selling you candy, or magazines, or anything else useless. I'm just asking for a small cash donation. And, in return, you receive so much more. You get a piece of internet advertising that will draw traffic to your site from curious wanderers. You will be acknowledged in a Web Log that will live on for years to come.

Only 201 people can even donate to begin with and roughly 20 of those spots are already gone. You might as well join some of the world famous game developers and artists who have already been enshrined in our hall of records.

Or, you can just tell me to go to hell. I don't care. All I'm saying is I will probably upload a new code suppository sometime tomorrow, Monday at the latest.

What did you do for me?

Matrix, Vector, and Quaternion Library

This post is really just a continuation of the last one. I am including, along with my vector template class, also my matrix and quaternion classes. The same comments as the last post apply here. There is nothing particularily new or special about these classes. They are 'nice to use' if you don't already have something you are in love with.

You will find them the most valuable simply as working reference implementations. I didn't write these. I cobbled them together from various other math libraries and/or graphics gems over the years. They do work, and I did discover and fix a few bugs in some previous reference implementations. There are some useful utility functions, like building a 'look at' matrix, or easily converting between various angle formats and quaternion to matrix and matrix to quaternion, etc. Chances are in some future code snippets I upload, when I absolutely have to have some math libraries, I will probably use these. I will try to encapsultate the public interfaces and may even put the whole thing in a namespace to avoid name clashing with your own math libaries.

Currently I am working on an automatic aggregate convex hull generator. If you don't know what that is, well I'm not going to explain it right now. However, I assure you, it is one damned useful utility to have!

Here is the link: MathLib.zip

Vector Library

I was going to upload my axis-aligned-bounding volume hierarchy code today but, when I reviewed it, I realized that it really needs a small app to at least show how to invoke the methods. Nevertheless, it is still a useful extension of the frustum class presented yesterday and I will present it relatively soon.

So, instead, today I am uploading 'my' vector library. 'My' vector library is 'mine' in the same sense that a water fountain at the library is 'mine'. There are literally thousands of vector libraries and classes on the Internet. Lord knows, you don't actually need another one. I didn't write this one. Instead I copy/pasted useful snippets of source from other vector libraries over a long period of time and massaged it to fit my own idiosyncratic habits. To be quite honest that is what makes it useful.

I have three math files to upload in snippet form; vector, matrix, and quaternion. Each one builds on top of the other. All three, I believe, are bug free. I don't recommend you actually use this code in your own application but, then again, I don't recommend that you do not use it either. (Get that?)

I do use a templated class for this vector library. You can construct a Vector3d(float) or a Vector3d(double) or a Vector3d(int), it's your call; though I don't guarentee that every method works in every permutation. I'm not really that big a fan of operator overrides because unless they are blatantly obvious (like adding two vectors together) I would just as well invoke a method that says exactly what is happening (like .Dot). For example, I could make an operator override that, when you add two numbers together, actually makes them subtract; or do anything else for that matter. And, it is for this reason that operator overrides often obfuscate code rather than make it more clear.

The quaternion and matrix classes to follow build on top of the vector class and are actually nice pieces of reference material. So, no, I don't recommend you actually 'use' these vector libraries unless, for some reason, you got this far in life and don't already have one. But, feel free to use them as a reference.

You know, one of these days somebody is going to have to standardize a vector, matrix, and quaternion library for the industry as a whole. Somehow I just don't think that is ever going to happen.

On a final note, I was pleasantly surprised today when world famous game developer Brian Sharp spontaneously donated money to the site I set up to raise money for my son's youth group. How cool is that? It just goes to show, you do something nice and it comes around back at you.

Here is the link to my vector library.

Frustum Testing using the Plane Extraction Method

Today's snippet is a truly useful piece of code. This is an implementation of Klaus Hartman's plane extraction technique for frustum culling. This implementation is highly optimized and designed to be called when doing a recursive descent through an axis-aligned bounding volume tree (though you can call is just one AABB at a time). The implementation is completely self-contained and uses no vector or matrix classes. Just 'const float *'. I spent a lot of time optimizing this implementation and I am pretty sure it is extremely, extremely, fast! To avoid a bunch of floating point compares in the original source code it builds a jump table against all of the permutations of extrema tests. I really don't remember the details, but you can have fun stepping through the source. I spent a lot of time in Vtune with this code and if you want to frustum test a ton of AABB's it is very fast; use it with a hierachical bounding volume tree where you recursively pass the clip flags from previous calls into it and you can cull literally hundreds of thousands of game objects against a view frustum almost instantaneously.

For almost any game engine you should simply be able to cast your view*projection matrix to a 'const float *' and pass it in. The code extracts the plane equations automatically. You typically set this once at the top of the frame and the plane equations are cached. When you set the plane equations it pre-computes an array that maps to a jump table to avoid floating point compares that were in the original implementation.

Tomorrow I will release a generic axis-aligned bounding volume tree that can be used with this frustum class. The bounding volume tree will only be useful if you build it against a static scene. However, it is optimized for recursive descent.

I have released this routine in the past, but I see no reason not to post it here where people can find it.

Finally I should explain the name of this website. The resason this website is called a code suppository (as opposed to a 'repository') is because this is where I insert source code into the anus of the Internet. I remember when I had my first code suppository on Flipcode, one day I received an email from someone who kindly thanked me for the source code and then gently suggested "I'm not sure you know what the word 'suppository' means."

After I finished laughing, I inserted some more code into the bloodstream of the black hole that has since become the death shroud of that site.

Here is the source code:

The header file: 'Frustum.h'
The implementation: 'Frustum.cpp'
A shared header file that enumerates the view state: 'viewest.h'

Cohen-Sutherland Clipping

Today's code snippet is a cohen-sutherland clipper. You might ask, why the heck do you even need a cohen-sutherland clipper? Afterall, there are 19,000 hits on the internet for cohen-sutherland clipping alone. It is covered in every single text book and most experienced developers know how to write one off the top of their head.

However, since this is a snippets website there is still a reason for posting this worried dogbone. The cohen-sutherland clipping algorithm is something every graphics programmer has to learn and understand. Even though the algorithm itself is fairly straightforward, it is very difficult to make an implementation which is not dependent on container classes, linked lists, or hard coded vertex declarations.

This implementation isn't necessarily even all that useful (though I have used on occasion) but I think it is a great reference for people learning the algorithm. Also, if you just need a version for your own engine it is easy to do a 'find replace' and make it work on your own data structures.

This implementation will clip an arbitrary polygon (up to 64 vertices) composed of an array of float3 vectors against an arbitrary axis aligned bounding volume. It uses no containers, linked lists, etc. It is very high performance and can be used for geometric clipping purposes in real-time (I have used it for a variety of collision detection needs). Additionally you can use it to clip a ray against an AABB. Finally, since it is a fairly modest implementation it should be relatively easy to adapt it to your own data structures. I didn't make a method that clips against an arbitrary set of planes, but the concept is the same.

Here is the header file: clipper.h
and here is the implementation: clipper.cpp

Legal Talk

A lot of people are asking about the specific legal status of the source code I am uploading here. Most of the source code I am including here came from the "Open Dynamics Framwork Project" which was an open source physics tool. My company had their lawyer print up a fancy bit of legal text which I guess applies here. I should have included it in the previus source code. This code is not 'newly' released. This code was released a number of times on a website called 'www.physicstools.org' that is now dead. This code is still released as part of a large physics sample application that is distributed by my employer. That code has been and continues to be 'free' with the following copyright notice embedded in it.

It sounds all very legalish, but all it really says is that it is 'free' and that you should include a copyright notice to a group that no longer really exists. I imagine we should probably revise the text to reflect the current status of the project. However, since the code I am uploading here comes from that original drop, then the text just states the same thing it did in the first place.

I revised 'StanHull.zip' to contain this copyright notice. (I didn't actually 'remove it' in the first place I just forgot to put it in when the code got refactored into a single CPP.) Some source code I will upload here is just 'mine'. I wrote some code when I left Sony Online Entertainment and before I started with my current employer. This source code is just good-old-fashioned 'free'. Meaning, use it as you will and don't blame me if something doesn't work. The 'InPlaceParser' falls under that category.

In the future I will be sure to make the status clear and include the 'Open Dynamics Framework' legal text for source that applies. In the coming days I have probably at least twenty code snippets to upload. Almost all of that code is contained in the previous releases of 'ODF Rocket'. However, I like to upload them as 'snippets' to show how they can be used in a stand-alone fashion.

I love finding useful source code on the Internet. However, one of my biggest pet peeves is that you can rarely use the code 'as-is'. Hell, more than half the source code on the internet begins the first line with '#include windows.h'. Ahem......thanks but no thanks. Now it has gotten so bad that if you use .NET 2005 and and compile a 'hello world' app, the compiler will scream at you for daring to use 'printf'. My god, what is the world coming to?

I think there is a certain elegance in delivering a code 'snippet' that requires one header file with an absolutely minimum number of dependencies and public API calls and a single self-contained CPP file. This means I don't like to provide source that is dependent on custom vector template classes. In fact, most of the code snippets I will be uploading fall into that category. They will show how to do something 'useful' that just accepts a 'const float *' as input. I figure anybody can cast their personal vector class to a 'const float *'. I know I have been able to do this successfully over the years.

Some of my source code really needs templates. In that case I use STL. STL stands for the *STANDARD* template library. I know some people don't like it. Well, then don't use that code snippet. However, it is truly a standard and if you are going to use templates or you have to use templates and you want to provide source that can be included in various projects, then I strongly recommend you do use the STL. There is a missconception that STL is slow. It is only slow if you use it incorrectly. There is a missconception that STL is bloated. Again, this is only the case if you use it incorrectly. If you only use containers of pointers to things (not containers of things themselves) and put 'factory' wrappers around your STL bindings, you can get high performance with a limited amount of code bloat. On the other hand, if you put STL containers in every single header file and interface and if you fire off copy-constructors every two lines of code then, yep, STL is going to perform like crap and bloat your code like crazy.

Oh yeah, I just realized another purpose of this blog. It lets me rant about my own personal opinions on software development. Did I ever mention that I think inheritance of anything other than a pure-virtual interface is evil? Let' save that discussion for another day..............


/*----------------------------------------------------------------------
Copyright (c) 2004 Open Dynamics Framework Group
www.physicstools.org
All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided
that the following conditions are met:
Redistributions of source code must retain the above copyright notice, this list of conditions
and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
Neither the name of the Open Dynamics Framework Group nor the names of its contributors may
be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE INTEL OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-----------------------------------------------------------------------*/

The InPlaceParser

Today's code snippet is a utility that I find extremely useful. I use it constantly, since it is such a common thing that C++ programmers do all of the time. Then again, maybe it is just a little too old school; you will have to decide for yourself.

What this code snippet does is loads a text file, parses it into a series of lines and turns each line into an 'argc/argv' format. It allows you to specify soft seperators (like spaces and tabs) and hard seperators like commas, parenthesis, etc. You can specify any particular character as a comment symbol which will be treated as an end-of-line character. I like to use '#'. I wouldn't use this parser to compile code, but it is very useful for any time you want to parse a little script with a series of commands in it. I use it for my physics scripting language called 'PSCL' or to parse a wide variety of INI and script files. It does handle strings in quotes, but it doesn't support escape sequences or multiple quotes.

Now, here is what makes this text parser unique or special. I call this the 'In-Place-Parser' because it parses the file 'in place'. It has no memory copies when it parses. After you parse a text file the original file is destroyed. When you recieve a callback for each individual file the argument pointers are *persistent* and can be cached for other uses! I have never heavily profiled this code but just by the way it is written, and my own use of it, I believe it to be extremely fast.

You can decide for yourself, but the next time you just need to parse a text file into a series of lines and those lines into arguments, I strongly recommend this code snippet; especially if that text file is *huge*.

InParser.zip

John Ratcliff's Code Suppository Blog : StanHull

I used to have a website on FlipCode called 'John Ratcliff's Code Suppository'. On that site I would upload interesting little bits of code snippets from time to time. However, FlipCode decided to shut down and I haven't had any place to post useful snippets of code anymore.

I do have a personal Weblog but I generally avoid discussing computer related topics on that forum. Fortunately Blogger lets you create multiple blogs per account so I have decided to post software related material here.

The reason I am doing this today is because I keep getting asked for some old convex hull code I posted a long time ago. Since I originally posted that code my collegue Stan Melax wrote a dramatically improved implementation that was released as part of the open source project 'Open Dynamics Framework' which eventually became an application called 'Rocket'.

Stan wrote a really awesome convex hull algorithm that is well designed for collision volumes. It includes a feature called 'skin width' that lets you inflate the hull around the input point cloud. This is often useful for collision detection purposes where you want to have a small skin around your collision model to keep the graphics from appearing to penetrate. This is also a common requirement for physics solvers that use penalty methods. Stan's code also supports a maximum number of vertices which will be considered for the final hull.

I can't take any credit for the hull code, but I did put a wrapper around it. My wrapper 'cleans up' the input point cloud. It eliminates duplicate vertices. Many hull programs have problems with vertices that are very near each other (creating slivers) and also have problems generating a hull based on the scale of the input data. My cleanup code 'normalizes' the input point cloud into a cube and then eliminates all nearby vertices based on a normal epsilon.

After your hull comes out not all of the original input vertices may be referenced so my code then re-indexes the hull to only include vertices that were actually touched. This uses a cleverly named method called 'BringOutYourDead'.

I made a quick little console application that demonstrates how to use the hull code. It reads in a Wavefront OBJ file, accepts various command line switches, and writes out the hull as a Wavefront OBJ as well.

The code was built using Visual Studio 6, but you should be albe to let it auto-convert to any of the other versions of Visual Studio.

I will post other code snippets, with their explanations, on this blog from time to time.

Here is the first entry: StanHull.zip