John Ratcliff's Code Suppository

New Implementation of the HACD Algorithm : Julio Jerez

2011-12-09T14:20:00.001-08:00

So, it turns out that Julio Jerez, author of the Newton Physics Engine, did his own implementation of Khaled Mamou's HACD algorithm (hierarchical approximate convex decomposition).

The big problem with Khaled's version is that it was extremely slow due to how he went about performing a distance calculation. Julio's implementation does not suffer from this, and is much, much faster.

In addition, I added my own merge-hulls code as an optional post process step.

You can download the new version from this Google Code Project page.

Once you are synced you can try running say the complex segmented bug model.

Run: TestHACD hornbug.obj

This will produce a 58 convex hull model saved out to the file 'ConvexDecomposition.obj'

If you want one that is even more precision you can try something like:

TestHACD hornbug.obj -c 0.1

This sets the concavity value to 0.1 from the default of 0.2.

This will produce 73 convex hulls.

However, if you want to run the post-process merge phase, you can reduce the number of hulls by the following.

Run: TestHACD hornbug.obj -m 40

That will recursively collapse the convex hulls (starting with the smallest to the largest) until there are no more than 40 hulls left.

Take a look at the resulting file 'ConvexDecomposition.obj' and you will see how nicely the convex hulls were collapsed.

This version is *extremely* fast and can be used even on meshes with high vert counts without taking forever.

While, in general, Julio's implementation seems to be working great, we have found a couple of edge cases it fails on.

In the project you will find two wavefront OBJ files, 'box-thick.obj' and 'cylinder.obj'.

'Box-thick.obj' is a hollowed out box, which Khaled's implementation handles correctly, but Julio's fails on. Same thing for the cylinder.

Hopefully we can get this tracked down soon.

To use this source code in your own project, just copy the sources from the sub-directory 'hacd'. The rest of your application only needs access to the folder 'hacd\public'.

Modify the header file 'PlatformConfigHACD.h' to change the global memory allocation routines if you want them to vector to your own methods.

GatherPictures : A console app to gather all JPEG files into one location without duplicates

2011-11-03T15:41:00.000-07:00

Today I'm providing a little console application that I wrote for my own personal needs. On the theory that if I found it useful, probably some other people might find it useful too, I'm making it available here.

The tool is provided as a ZIP file. It includes both the source code and the Windows console application. It is designed to be run from the command line, so if you are a Windoze user, this might not be the tool for you.

So, here is the problem I was trying to solve. I think many other people may have this problem too. Over the years you transfer files from various memory cards, digital cameras or Iphones. You have them on a bunch of different places on your hard drive. You have them on your computer, you have them on your wife's computer you have them on old CD-ROMs or external USB drives.

Then, one day, you would like to simply get a copy of all the photographs you have scattered around all these locations into one spot, without any binary duplicates. This tool does not do an inexact match, it won't detect images which are the same, but at different resolution or have been cropped or rotated. There are commercial tools that can perform this operation fairly well. Personally I use Visual Similarity Duplicate Image Finder.

This tool also does not do image resizing, there are many commercial tools that can do that as well.

What the tool is designed to do is collect all of my pictures, from many different sources, into one single flat directory so that I can then, easily, run these commercial tools on them to create a nice clean set of non-duplicate images ready to be copied onto a memory card to put into a digital picture frame.

There is nothing particularly special or magical about this source code. It's nothing I'm proud of in any particular way, it's just something I hacked up real quick and seems to work.

Now, here is how you use the tool. Let's say you have a bunch of pictures in a directory called 'MyPhotographs' and under that directory are many sub-directories. Now, let's say you have another directory called 'WifesPhotographs' which may, or may not, have some of the same pictures duplicated.

The way to use this tool is you create a folder where you want to 'gather' these images into.

Next, go to that directory and at the command prompt and run the GatherPictures.exe (should be placed somewhere that your default search path can find):

GatherPictures c:\MyPhotographs

This will find all JPG files in that directory and all sub-directories and copy them into your current directory giving each image a unique flat file name.

For example, if you had an image 'c:\MyPhotographs\vacation\img001.jpg'

It would get copied as the file name 'MyPhotographs_vacation_img001.jpg'

If after running 'GatherPictures' against 'c:\MyPhotographs' you run it a second time, then it will detect that all the files are the same and it won't copy anything. On the other hand, if new photographs get added to that directory, it will detect the new ones and pick them up.

You can continue to run 'GatherPictures' against any directory and it will avoid copying any binary duplicates.

Once you have 'gathered' all of your pictures you may find that you have gigs and gigs of photographs. For example, I had about 50gb of photographs in 38,000 files. One of the issues I ran into is that when I tried to run some image processing tools on this directory they crashed because they had never been designed to handle that many images. Also, there is the use case where you might want to break these up into say 8gb or 16gb chunks suitable for copying onto a memory card.

I added a new feature to 'GatherPictures' which will take all of the pictures in the source directory and copy them into sub-directories of a specified size limit. The original pictures are left alone.

The usage for this is:

GatherPictures -split

So, if you wanted to split all files into 1gb sub-folders you would use:

GatherPictures -split 1024

(A gigabyte is 1,024 megabytes)

For those who are interested, here is how the code works.

At start up the first thing it does is scan all JPG files in the current directory. It examines the size of each file and places it into a hash map. It also builds a hash map of all file names.

Next, after scanning all of the files in the source directory, it does the following.

First, it makes sure the file name doesn't match one that has already been gathered. It uses the previously built hash map to speed this up. If it matches, it skips it.

If the file name doesn't match it then looks up the binary file size against the hash map of files by size. If there is already one, or more, files of that exact size it then tests to see if it is or is not duplicate.

First, it reads the source file into memory and computes a 32 bit CRC. Next it compares that CRC to the CRC of the previously registered files. If it is the first time the file has been checked, it has to read the file into memory to compute the CRC. However, it caches the CRC so this is only done once. The next time it encounters a file of this same size, it can just use the cached CRC for an early reject.

If the CRCs match only then does it do an exact binary memory compare to see if the two files are, in fact, exactly identical.

Let me know if you find the tool useful or can think of improvements. As I said, my goal was not to replace the functionality of commercial duplicate image finder tools but, rather, I just wanted a way to collate all my image files into one single location giving each file a unique file name based on it's original source directory location.

Don't look a gift horse in the mouth

2011-08-28T11:30:00.000-07:00

My friend Charles Bloom likes to rant on his blog, and I often envy him. He lets his inner id loose in a way few others do. Personally I don't let out a good rant that often but, tonight I will.

Now, earlier in the evening I must admit that I had a few drinks and I also admit that as a rule most of my public rants are fueled by exactly that kind of behavior. But, tonight I don't think that has anything to do with it.

This blog is called the 'code suppository' for a reason. It is the place where I insert my computer software into the anus of the internet.

Now, I release open source code for a number of reasons. Let me take this opportunity to say what they are and in order of importance.

(1) The number one reason is that I do it for myself. Like many programmers I have my 'bag of tricks' code snippets which I use over and over again. No one wants to keep writing the same parser,
or similar piece of utility code over and over again. Many long time C++ programmers accumulate a personal library of goodies over the years and, frankly we publish the source for ourselves as much as anyone else. Chances are I personally go back to the code snippets hosted on this site probably more often than anyone else. I never want to ever again have to write from scratch how to compute the nearest intersection point between a line segment and another arbitrary 3d point in space. I never want to write again form scratch code to read a .INI file, handle key-value spec properties, parse an XML file, etc. etc. So, I post those code snippets primarily for my own use. If anyone else finds them useful, that is just a bonus. This is, I believe, pretty much what my friend Sean Patrick Barret does. Sean is an incredibly generous guy who has released more useful free source code snippets used by more people than almost anyone else out there. For example, I think Sean's PNG reader/writer code has probably found its way into literally thousands and thousands of software projects.

(2) The second but, to me, the most important reason that I publish open code source is out of a sense of moral obligation. Over my 30+ years as a professional software developer I have benefited greatly hundreds, if not thousands, of times from the open source work of others. And when I say 'open source I don't mean that bullshit GPL garbage. I mean really, truly free open source conforming to the BSD/MIT license. Truly free source code in every way with with no restrictions on it other than "you can't sue me if it doesn't work."

(3) The third reason I release stuff open source is in the hopes that some other programmer might find bugs in the code and contribute fixes and/or improvements. There is no better example of this than when Khaled Mamou took my approximate convex decomposition algorithm and used it as inspiration for his dramatically improved hierarchical convex decomposition code HACD. It gives me a tremendous amount of satisfaction that my work inspired someone to do something even better. And, guess what, I'm returning the favor by optimizing HACD so that it will run several orders of magnitude faster than it does today. This process of using open source to work together as a community, helping one another out, is something I find very gratifying to be a part of. Or, at least *used* to find gratifying...

(4) The fourth and final reason that I release open source code is for educational purposes. I think of it as a service to the community and also as an educational exercise. Over the years, when I have tried to get something useful in terms of available open source code I have often run into major challenges trying to extract just the specific piece of functionality that I want. Many software engineers write their code on top of rather massive template libraries; especially for data structures and mathematics. So, if you want to get just a particular routine (like say computing the best fit plane equation to a collection of 3d samples), you cannot simply get just that routine. Instead, you have to adopt 50 to 100 thousand lines of source code, including a massive library and template framework to get access to that functionality. This isn't a problem if you want their whole library, but it is is a problem if you just want that one routine or want to refactor it to work with your own data structures and math template library.

My goal is to help educate the public in what I personally believe is the ideal way to share source code with others over the Internet; as 'code snippets'. With most of my releases I try to set a good example and educate others. I have received enough positive feedback over the years to know that a lot of people really do appreciate it.

Now, it's time to get back to the rant.

I have edited this post from it's original and will replace that content with one simple request.

If someone gives away free open source, and you have questions, feedback, or suggestions for improvements, please send a polite and friendly email to the author. Chances are that author will try to be of help. If you send the author a rude and insulting email, that's probably not going to be very helpful or put them in a mood to help you.

Also, if you don't get an answer to your email, don't be upset right away. Like many people on the Internet, authors of open source work can receive hundreds of email a day, and it's easy for one of them to either get marked as spam or the person intends to give a reply, but it slips through the cracks.

And, as your mother always said, if you have nothing nice to say, you can always say nothing at all.

Raycasting using AABB (Axis Aligned Bounding Volume) trees

2011-08-18T08:02:00.000-07:00


Note: This photograph has nothing to do with this post; I just love showing off my new puppy Winston!

Today I am releasing an arguably somewhat useful code snippet which can preform high-speed raycasting against an arbitrary triangle mesh. Now, this isn't particularly unique. There are many libraries on the internet for doing this; however this may be the only one presented as an actual 'code snippet'; meaning just a single header file and a single relatively modestly sized CPP implementation.

If you need a robust general purpose raycasting and collision system I strongly recommend you use OPCODE written by my friend Pierre Terdiman. OpCode is a phenomenal library that is extremely high performance. You can also use the PhysX SDK from NVIDIA; which has a version of OPCODE internally which is also very high performance as well.

However, OPCODE does a whole lot more than just simple raycasting against a triangle mesh; it has a lot of other features and is distributed as about 100 source files comprising tens of thousands of lines of code. Again, this isn't an issue if you are working on a large project and want to add the library in.

All that said, sometimes you are working on a small utility program or tool and you just need a quick and dirty way to raycast against a triangle mesh to speed up an algorithm. In this case, you might find my implementation useful since you only need to add two small source files to your project.

This code snippet might also serve as a nice educational tool for students trying to understand how to build and use an axis-aligned-bounding-volume AABB tree.

You can download the source code from this Google Code project page.

RaycastMesh

The project includes a sample application which will load a 3d mesh, perform a million raycast operations, and save out a PNG image file showing the results.

However, to include it into your own project you need only the file 'RaycastMesh.h' and 'RaycastMesh.cpp'

Revision to TestHACD

2011-07-11T14:27:00.000-07:00

After making my post last week Khaled Mamou has made some bug fixes to his HACD implementation that takes extended mesh connectivity into account. In the previous version, if you ran convex decomposition on a single input mesh that was actually comprised of say 10 separate unique sub-meshes (I like to call them 'mesh islands') then it would always produce a minimum of 10 convex hulls.

Khaled fixed this by adding a new option called 'connectivity distance' which will merge mesh islands if they touch within this distance.

I integrated Khaled's changes into my depot as well, and also removed my hack solution which performed hull merging to get around this previous problem.

Right now my code and Khaled's are in sync, but my code drop is significantly refactored since I made it optional to build and run it either with or without the standard template library. Perhaps we can combine our efforts sometime in the future but, for now, I will just continue to manually integrate changes.

My current check-in adds support for my MeshImporter plugins which can import a wide variety of graphics file formats. I will have a new MeshImporter plugin that will support COLLADA soon. This is a windows only feature; for non-windows developers there is an option to just compile in Wavefront OBJ support.

Also, my current code drop has the beginnings of the automatic skeleton generation code. As I find time this week, I will try to complete it. This code will take an arbitrary triangle mesh, perform HACD on it, and then infer a skeleton at the points wherever two convex hulls touch each other. As a final option it can auto-generate a skinned mesh from the original non-skinned artwork. This will allow you to automatically create a ragdoll or psuedo-softbody from any arbitrary mesh.

Here is the link to my depot on Google Code. TestHACD

Here is the link to Khaled Mamou's official copy of HACD on SourceForge.

HACD : Hierarchical Approximate Convex Decomposition by Khaled Mamou Sample Application

2011-07-07T16:57:00.000-07:00

I have just created and made available a test application for people to use/experiment with Khaled Mamou's excellent HACD system.

TestHACD on Google Code

Due to requirements that I have at my job, I had to refactor the code so that it did not use any of the standard template library (STL) and 100% of all memory allocations had to be trapped by a user provided allocator. (i.e. no global new/delete, malloc, free).

One of the more challenging things to factor out regarding the STL was the use of the STL set and map containers. To accomplish this what I did was refactor a copy of the EASTL (written by Paul Pedriana). Even though Paul's EASTL is a dramatically smaller code base than the full STL implementation, I went a step further and refactored his code so that I extracted *only* the STL map/set containers and nothing else. I then put this refactored code into just three small source files where all memory allocations and data types could be trapped and revectored.

There is a single header file in the provided project 'PxSimpleTypes.h'. You can modify the data types and memory allocation macros in this one header file to make the source conform to the coding standard of your own game engine, or at least it provides a single easy location to do some global find/replace on the source to make it conform to your internal standards.

Khaled's algorithm produces absolutely amazing results much better than my version ever did. However, one thing I have yet to be able to get his to do is produce just one our two hulls.

With the provided sample mesh no matter what I set the concavity threshold to, no matter how high, I still get 14 convex hulls. I don't know if this is a limitation of his algorithm or I am not exposing all of the correct parameters at this time.

If you wish to make improvements to this code, please let me know and I will add you to the Google Code project so you can make changes. Also, sometime in the next week, I am going to revise the code to auto-generate a skeletal deformed mesh from the HACD output. I will add this to the TestHACD open source project.

Be aware that Khaled's algorithm can be extremely CPU intensive. With triangle meshes with very large vertex counts; it could possibly take an extremely lengthy period of time.

Overly Optimistic?

2011-06-04T06:36:00.000-07:00

I just had someone post a comment on the blog about my overly optimistic view of my new project. I figured I would post my answers so everyone else interested could read them as well.

>>overly optimistic/ambitious?

That's not an unfair assessment. However, I do have confidence in a few things. I'm confident that I can do this project; based on the fact that I have successfully completed similar projects in the past, more than once.

I am also confident that I am managing technical risk.

For example, one of my first requirements is not to get even any game play working. My first requirement is to get a server written that can manage 1,000 simultaneous connections and to test it with bot scripts which actually create 1,000 connections and move characters around the world.

The 'M' in MMO stands for 'massive' and if I can't achieve that, then nothing about the game client really matters.

The key to success, in my view, is to provide a unique truly massive gaming experience; the kind you could only ever get, to date, from 'Planetside' and do better. Having been the lead software engineer on 'Planetside' I would like to think I know a little bit about this.

>>have you already prioritized a list of features so that you know what to drop when you don't meet deadlines?

Yes. I'm using Agile/Scrum methodology and Rally to track everything.

>>(and have designed play tests to know that these features aren't make-or-break?)

Well, we aren't doing the project that way. This project will be in a continuous state of open beta from the day we have enough server infrastructure in place and two people can walk around the game world. The game will never officially 'ship' in that sense; but rather features will continuously be added, and game design refined through play test over time.

This is the only way any truly successful multiplayer game gets developed. If you do not always have a playable game, during the entire development process, you are taking an absurd risk in my opinion.

And, while we will never officially 'ship' the game, we will officially start charging people money for beta testing.

However, even then we have a lot of flexibility. One of the key things to test is the monetization of the game, and what works best. So monetization will be play tested and balanced just like everything else.

My design is that, from the stand point of the game mechanics, you will never play the game for 'free'. What will be free are credits to play the game, which I will hand out with abandon to anyone who is willing to help us test and tune the development process.

Once the game reaches a level that it is truly fun to play, and I feel worth charging money for, at that point I will just stop giving away so many free credits.

For example, let's say you want to beta test. Well, I can give you a $100 worth of credits to play the game (enough credits to play the game a ridiculous number of hours for five months).

Once those credits run out, if that guy is still in beta test, he is going to want some more credits to keep playing the game.

If I haven't created a game that is enough fun to accomplish this, then I will have failed.

However, this game is starting with a known, proven, and completely addictive game design. So, my confidence level is fairly high that I can find a decent sized group of people who will enjoy playing it and be willing to pay a modest amount of money for the privilege. I'm not talking about charging them some absurd amount of money in subscription fees, or annoying the shit out of them with micro-transactions and/or advertising. My initial plan is simply to charge very modest some of money per time played. Something roughly on the order of 25 cents for half an hour. But, this too, is all subject to change, refinement, and tuning as testing plays out.

This game is going to provide a unique gaming experience you simply cannot get anywhere else in any other form.

>>anyway, good luck with it all! Keen to see your demo in 2 weeks

Thanks, looking forward to getting it out!

Progress update

2011-06-03T09:25:00.000-07:00

I have made some big decisions to move this project forward in the past 24 hours; and these decisions involved committing thousands of dollars out of my own savings to get things off the ground.

First, I have formed a limited liability corporation, under the name 'Duatiu LLC', which will have 10,000 shares of stock to distribute to partners.

Second, I filed a trademark application on the name 'Duatiu'. I expect no difficulties since the name is a coined term and doesn't show up anywhere on any search engines.

Third, I have come to an agreement with partner Shawn Presser to work on Duatiu *full time* for the indefinite future. Shawn is being reimbursed for his time spent on this project as a combination of shares of stock and a modest amount of cash to help defray his own personal expenses.

This is a pretty big deal; having a talented software engineer able to work on the project full time should go a long way towards pushing the game to the next level.

Our current ball park milestones are as follows:

Within Two Weeks : A downloadable demo of the Duatiu game world. You will be able to fly a free camera and walk an avatar around the game environment. The visual production values will be close to the final product. Using precomputed radiosity, nice diffuse textures, and a high resolution detail texture, we expect the game environment itself to be very visually stunning. The game engine is being written exclusively in C++ for OpenGL. While it will initially run on Windows; it may at a future time run on a wide array of tablet operating systems. (Perhaps of interest to the programmers who follow this blog, I will be releasing my radiosity lightmapping tool completely open source at the same time.)
Within Four to Six Weeks : Be able to connect to a server, hosted on Amazon.com, and walk around the game environment and see avatars representing other playrs.
Within Three Months : Be able to play a simple basic game involving calling in supplies, operating a shield, and shooting human opponents; all in a multiplayer environment.
Within Six Months : Functional AI agents running on the server; more of the actual game play implemented.

These are just back of the napkin estimates, but it does give you a general ideal of the scope and time frame we are thinking about. I'm extremely excited that Shawn has committed to working full time on this project. I expect good things to come from this soon!

My new project 'Duatiu' is actually getting some traction after just 24 hours of announcing it!

2011-06-02T09:04:00.001-07:00

Well, I have already received quite a bit of positive feedback in the past 24 hours about this project. First, a number of my friends in the industry have promised to help me out and that has been amazing!

So far I have commitments of time from:

Shawn Presser : Who is writing the core graphics engine and has already been working on the project for several months. Shawn's contributions to this project have already been amazing. We are currently working towards our first milestone to provide a demo that will allow anyone to run a character around one of our game world environments sometime in the next couple of weeks.

Jared Freedman, An excellent game designer, developer, long time friend, and all around good guy.

Billy Zelsnack : Billy is a well known figure in the game industry and a long time friend. He has volunteered to help with the game project when he can.

Charles Bloom : It helps to have good friends in the game industry and Charles, even though he is one of the top guys in the world he still took the time yesterday just to whip up a little bit of code I needed to solve a problem. I see shares of stock in Charles's future. Plus, he's a fellow Porsche fan so we have that in common.

John Miles : What has John Miles done on this project? Nothing. Does John Miles even know that this project exists? Probably not. Have I even asked John Miles if he will work on this project? No I haven't. But, as a life long friend, I'm sure he will help me out when I need it.

Wajih-Halim : A recent college graduate in computer science who wishes to help with graphics special effects on the game.

Ben Hesketh : Runs his own successful game company and contacted me from this website because he thinks the project sounds interesting. Ben has volunteered to contribute on the server code. The website for Ben's company, Compass Engine, can be found here. And a link to his recent game 'Bounty Island' can be found here.

Robert Sitton : Robert is a long time game industry veteran and was one of my key sidekicks when developing the game 'Planetside' for Sony Online Entertainment.

Joe Bizz : Musician and sound engineer and fellow UFO enthusiast. So how that networking shit works?

RAD Game Tools : The guys at Rad Game Tools are long time friends of mine, Jeff, Mitch, David, Brian, Sean, and others. They have always been extremely helpful in supporting me and my projects and it looks like I may be able use their latest product 'Iggy' to accelerate the development process for this game. 'Iggy' is an amazing product written by the the no less amazing Sean Patrick Barrett (one of the Gods of the open source community). 'Iggy' is an embedded Adobe flash engine that virtually eliminates the need to do any custom user interface programming. The entire user interface for a game becomes a series of Flash/ActionScript/FLEX data assets. This should greatly accelerate the development of the user interface for this game. Of course, that means that now, instead of looking for a GUI programmer, I need an expert who knows how to use these tools; but that seems like a much simpler hurdle to leap.

This is a really good start to the virtual team, but I still need some more artists to join the project. Hopefully when people see the caliber of people involved they will realize they are missing the boat if they don't hop on soon.

Duatiu ; A Massively Multiplayer Online First Person Shooter written by.....you?

2011-05-31T16:20:00.000-07:00

For those who follow this blog, please check out the website and postings about a new project I'm trying to get off the ground. Feedback, but more importantly, partners wanted.

HACD : Hierarchical Approximate Convex Decomposition by Khaled Mamou

2011-05-20T13:17:00.000-07:00

Many people come to this weblog because they are searching on terms for 'Convex Decomposition'. This blog post is to announce that there is a much, much, better open source implementation than the one I did. I suppose I can take some tiny credit as my work appears to have inspired the authors of the new algorithm but that's not really saying much. All credit where credit is due and the open source implementation released by Khaled Mamou is vastly superior to the brute force approach that mine took. His is much more elegant and also solves a lot of extremely hard problems; such as objects with holes in them (something my algorithm could not deal with). His also does not suffer with the problem mine had with excessive recursion depths producing hollow interiors.

You can find the paper for this algorithm at this location:

ftp://ftp.elet.polimi.it/users/Stefano.Tubaro/ICIP_USB_Proceedings_v2/pdfs/0003501.pdf

You can download the source to HACD from this location on SourceForge

http://sourceforge.net/projects/hacd/

With this announcement I will no longer be supporting my legacy ConvexDecomposition code in any way. I am switching to using HADC in all of my projects. I recommend you do the same.

Congratulations to Khaled and Faouzi who have done a fantastic job on an important problem.

One thing I will volunteer to the community is that sometime soon, I will create an open source tool using HACD that will auto-generate skeletal deformed meshes.

If you simply look at these various screenshots you will notice that the convex decomposition naturally produces a logical skeleton for an arbitrary piece of geometry. Obviously, that skeleton isn't perfect compared to what an artist would create but it is certainly a useful approximate skeleton.

From previous work I have done on the 'create dynamics' project, I know that you can not only synthesize a skeleton but you can also auto-generate skinned bone weightings. If you then create physical collision shapes which are constrained at these joint locations you can get an extremely convincing looking softbody object; with accurate collisions, in a very CPU cheap fashion.

K-Means Clustering Algorithm

2010-12-02T10:04:00.000-08:00

I haven't uploaded a new code snippet in quite a while, not because I haven't been coding, I've just been coding in a certain unnamed behemoth game engine that doesn't lend itself to writing anything in 'snippet' form.

However, I am working on a new project for a short period of time and yesterday I needed to solve a problem that, apparently, lots of people have solved before. I have a large set of data points (in this case representing objects at different scales) and I needed to reduce it to a smaller subset of the (N) number of most significant sizes.

This is a common problem, and many developers have seen it when trying to reduce a color-space. (For example reducing an image with say 16k colors to only 256 colors used to be a common thing people needed to do).

One of the more elegant solutions to this problem is by building an octree; at least one version of this algorithm is called 'Wu Quantization'. This was popularly presented in Graphics Gems.

What I needed yesterday was something very quick and dirty and, that turned out to be the K-means clustering algorithm. You can read about it here on Wikipedia and here is another link comparing it to a different algorithm.

The algorithm itself is very straightforward.

Let's say you have 100 input data points, but you want to reduce them to say 10 clusters where the center of each cluster represents the mean of the surrounding points.

Step #1 : You seed the 10 clusters with the 10 sample points taken from the input data.

Step #2 : You set an temp array of counts to zero and temp points to zero for each cluster you are building.

Step #3 : You iterate through each of the input data points. For each point you figure out which of the current clusters it is closest to. You then add that point to the new set of centroids and increment a counter.

Step #4 : You accumulate a total distance error of each point from its nearest cluster.

Step #5 : You compute the average center position for each of the centroids and assign them as your new clusters.

Step #6 : You compute the difference between the distance error on this pass and the distance error on the previous pass. If the difference in the error is less than a tolerance passed in, you are done. If the error is still converging, then you go back to step #2 and continue the loop.

My implementation also added the ability to prune the results. Pruning is needed if all of the input points are at the same location, or there are fewer input points than clusters requested.

Another reason to prune the output is in the following example. Let's say you have 100 data points that you want to put into 10 clusters. However, all of those data points are right next to each other.

The standard K-means algorithm will still produce 10 clusters, since it is basically unit-less. However, this implementation allows you to specify a tolerance threshold that says if two clusters are practically next to each other, simply merge them.

The main reason I am posting this code snippet is because of the absolutely abhorrent code snippet I found on the internet.

Click on this link to see the C implementation version that I found on the Internet. Clear as mud right?

kmeans.c

Oh yeah, I would like to also add this. There is a link to a C++ implementation on the Wikipedia page. I downloaded that link and it uses not only the STL but BOOST as well!

Yikes. Mine has a vanilla C style function interface, accepts pointers to 1d, 2d, 3d, or 4d arrays of data points as either a const float pointer or const double pointer and uses no STL, or BOOST, or any other fluffy nonsense.

Now, here is the header file and C++ for the version that I wrote. I hope you will agree it is a lot easier to understand and use. As always, feedback welcome.

kmeans.h
kmeans.cpp

Understanding a .MAP file

2010-04-18T07:59:00.000-07:00

My friend Andy Finkenstadt helped me figure this out. Apparently the contents of a .MAP file are *not* in sorted order. I will write a follow-up to this post later.

Memory Tracking Utility

2010-03-27T13:39:00.000-07:00

Today's code snippet is a very useful tool. The default version is provided as a 32 bit windows DLL. There is no reason the code couldn't be refactored to be used on other platforms, but that wasn't a requirement for my own personal use.

This tool is used to detect and identify memory leaks when an application exits or, more commonly, used to simply identify where all of your memory allocations are coming from.

What's nice about using this tool as a DLL, rather than source code, is that it doesn't directly affect any of your existing allocation code.

This code does *not* trap memory allocations. You must already be doing that yourself. What it does is allow you to track and report on those allocations.

Ideally your application would trap every single new/delete malloc/free performed. This can be done in a variety of different ways, either by replacing the global memory allocator, or by inheriting a base allocator class.

I strongly recommend that every class in your code base inherit a default allocator class. Then, in every location where you used to do a 'new' operator, replace that with a macro expansion which calls an inherited new operator which accepts class name, file name, and line number.

The value of the Memory Tracking report is only as good as the data you feed into it. If you feed into it the class name, source code filename and line number for every allocation then the report will be able to give you some tremendous information identify when, how, and where, all of your memory allocations are occurring.

One problem with tracking all memory allocations is with templates. When you do a lot of template metaprogramming it becomes difficult to know where the source allocations are occurring. Sometimes it is useful to add additional parameters to your templates so you can better identify where the allocations are coming from.

So, here is how you actually use the MemoryTracker DLL in your application.

You need three things:

MemoryTracker.h
MemoryTrackerBinding.cpp
MemoryTracker.dll

The header file 'MemoryTracker.h' defines the pure virtual interface to the memory tracking utility. It also declares a single global variable pointer to the Memory tracking interface and a routine to initialize the DLL.

In your code, before you do any memory allocations, initialize the MemoryTracker.dll by calling 'NVSHARE::createMemoryTracker("MemoryTracker.dll'). You should pass the name of the DLL on disk, including the full path location if necessary.

The routine 'createMemoryTracker' is in 'MemoryTrackerBinding.cpp' which will perfom a load library call on the DLL and initialize it; also setting the global variable 'gMemoryTracker'.

Once the memory tracker DLL is loaded, you can now track all memory allocations performed by your project.

First, set the logging detal level. The options in 'setLogLevel' are:

logEveryAllocation : This will produce an enormous amount of data, and is not recommended unless you really need to track every single allocation at startup.

logEveryFrame : This will produce a summary of allocations and frees each frame. For this to work you need to call the method 'trackFrame' once per logical 'frame' in your application. Again, this feature is not recommended unless you are specifically wanting this data.

There are three methods for tracking your memory allocations. They are:

'trackAlloc', 'trackRealloc', and 'trackFree'.

The enum 'MemoryType' designates what was the type/purpose of each allocation. This will identify if it was a 'new' 'delete', a 'new array' or 'delete array', or a 'global new', etc. The difference between MT_NEW and MT_GLOBAL_NEW, is to indicate whether the new operator was trapped or not.

When you track an allocation you can specify the class name, or simply a tag for the purpose/type of allocation, and the file name and line number of the original C++ source code. You can do this by using the compiler preprocessor directive __FILE__ and __LINE__.

It is very important to note that these string pointers must be persistent for the lifetime of your application! You cannot, and should not, ever pass stack or temporary variables in as the parameters!

One of the most valuable options when tracking memory is 'context'. The 'context' allows you to organize your report based on its overall meaning within your application. A good example of this is if you are working with a piece of middleware, like say the PhysX SDK, which allows you to provide a user allocator override. Every time this SDK does a callback to your application for memory you can pass in as the context field 'PhysX'. Then, when you generate the memory report, you will have all of the memory used by PhyX organized separately from the memory allocated by other parts of your application.

When you application exits, and after all memory allocated should have been freed, you can call the method 'detectMemoryLeaks'. You pass it the filename of the HTML report you want saved. Also you pass the option 'reportAllLeaks'. If 'reportAllLeaks' is true then every single piece of allocated memory which was never freed will be reported in detail.

In addition to using 'detectMemoryLeaks' to generate a report on exit, you may also call it at any time in your application simply to get a general report of overall memory usage.

If you use it for this purpose it is strongly recommended that you set 'reportAllLeaks' to false, otherwise you could generate a massive data report.

The real value of this utility is the report itself. The output is sorted by class name, source code and line number, as well as context. It comes with totals and subtotals and is some very nicely formatted HTML tables as output. When I get a chance I will upload a sample report for you to take a look at.

The MemoryTracker utility is an open source project hosted on Google Code. You an find it at the following link.

If you don't care about the source code to the memory tracker tool but simply want to download the tool try these links.

MemoryTracker.h
MemoryTrackerBinding.cpp
MemoryTracker.dll

Any SIMD optimization specialist looking for some easy consulting work?

2010-03-25T10:44:00.000-07:00

Anyone in the game industry who has expertise at optimizing SIMD code for PC (SSE/3D Now,etc.) Xbox-360 Altivec, and PS3 SPU, looking for some easy money doing a short term gig, let me know.

I have a handful of vanilla C++ routines which need to be optimized for these platforms using a shared math library. It's not that I can't do it myself, it's that I am already over-committed on my time for a number of other projects. Apparently I have the ability to pay a contractor to do some of the work, so this could be easy money for somebody who really enjoys doing low-level optimization work.

Send me an email if you are interested.

MapFile : A tool to analyze .MAP files produced by Visual Studio and report the amount of memory being used by data and code

2010-03-21T12:25:00.000-07:00

It really annoys me that I had to write today's code snippet. I fully expected to be able to find an existing tool that could accomplish this basic task but after literally a couple of hours of searching the Internet for something I gave up. In the end I had to write my own tiny console application and I am making it available here so nobody else feels like they have to write it again.

Also, if anyone reading this is really good at web stuff, it would be nice to have a website that would let you upload a .MAP file and then be able to immediately view the HTML content.

The data in this version is pretty complete. For some reason when I parse all of the address data found in the .MAP file it doesn't add up to the exact byte count that is in the sections summary. Maybe somebody from Microsoft can explain why that is.

The data could probably be a little better organized and it could really benefit from some hyperlinks. That said, still all of the data you need is there.

A .MAP file is an ASCII text file that can be produced by the linker phase in Visual Studio. Under Linux the GCC compiler can also produce a .MAP file but I have no idea if the two formats are compatible. For my needs I was only concerned about builds that were done with Visual Studio. This works even if you are building for XBOX as well.

A .MAP file is essentially a 'memory map' of the executable. It describes by memory address every piece of code and data in the resulting executable file.

Unfortunately it it not very human readable. The function names in the map file are 'decorated'; meaning they have been scrambled/compressed into a machine only readable format. A DLL that comes with Windows called 'dbghelp.dll' can 'undecorate' these strings into their human readable form.

The MapFile console application will read in a .MAP file and output an HTML file called 'output.html' that contains tables representing all of the code and data sections in the executable.

The tables are sorted either by object name or by function name.

An executable is broken up into various 'section's and the HTML output is likewise broken up the same way.

You might ask, why would you need this tool? Well, I suppose that is a fair question. Let's say you are targeting an Xbox-360 console machine and your executable size is 10 megabytes. That's just huge. So, you are going to want to know where all of that data coming from. Is it code and, if so, from what source files and what functions? Is it data and, if so, what kind of data is it and where is it located?

I have set up a Google Project to host this tool. You can find it at the following link:

MapFile on Google Code

Another reason you might want to download the source code to this tool is that it demonstrates how to use two of my most powerful code snippets. The first is the 'InPlaceParser', which is an extremely high speed text parser and the second is 'HtmlTable' which is a code snippet that will output nicely formated HTMLTables with headers, sorted columns, and totals.

Both code snippets are really useful.

PhysX Rocket for 2.8.3

2010-02-23T16:36:00.000-08:00

The physics demo application, PhysX Rocket, has not been officially released in some time. However, I frequently get questions from people who still enjoy playing with it as a tinker toy. It can also be useful as a physics scripting application.

Overall, Rocket is really showing its age. It is very crufty, especially in terms of the source code.

However, if you want a copy to play with, here is the link. It is simply a ZIP file. It does not have an installer, and does not include source code.

www.amillionpixels.us/rocket.zip

NvCoreDump : Easily perform an NxuStream XML compatible core dump with PhysX 2.8.3

2010-02-23T16:33:00.000-08:00

NvCoreDump is a windows 32 bit DLL which allows any PhysX 2.8.3 based project to perform an NxuStream XML compatible core dump in a single function call.

Rather than including all of the NxuStream source code in your application, instead you can simply demand load this tiny DLL and save it out. The value, purpose, and benefit is to take simply add the ability to export the contents of the current PhysX SDK in any application by simply adding this tiny code snippet and the DLL.

This project is hosted on Google Code at the following location:

https://code.google.com/p/nvcoredump/

Simply add the source files 'NvCoreDump.h' and 'NvCoreDump.cpp' into your project. Next add the DLL 'NvCoreDump283.dll' to your binary/executable directory.

Somewhere in your project, typically when someone types a command at the console, simply call the method 'nvCoreDump' passing a pointer to the 2.8.3 PhysX SDK and a string pointer of the file name you want it saved as.

The file will be saved in XML format as NxuStream. NxuStream is a reflective object model representation of all of the internal data of the PhysX SDK, including scenes, meshes, constraints, clothing, and even fluids.

PhysX2Obj : Convert Physics Scenes into a Wavefront OBJ file

2010-02-23T16:23:00.000-08:00

Today's code snippet might prove useful to anyone who works with the PhysX SDK. This code has been compiled and tested with PhysX 2.8.3 but should work with earlier versions of the SDK with little or no modification.

In any PhysX application simply include the header file 'PhysX2Obj.h' and invoke the single method 'exportPhysX2Obj'.

You pass in a pointer to the scene you wish to export, the file name to save it as, and a bool indicating whether or not you want to export the data in world space or object space.

If you select world space, you will simply get one large Wavefront OBJ file with all of the static geometry in your game level. You can then import this Wavefront OBJ into 3D Studio Max or other tools for testing purposes.

If you select object space, it will export all of the geometry in object space and annotate the file, with comments, indicating where each object should be instantiated in the world.

Some of you might be familiar with my previous work on NxuStream; which is an XML file format that allows one to capture the state of a PhysX SDK scene. However, that format required a large code base and could only be used in the context of the PhysX SDK.

This tool is not a complete 'core dump' like NxuStream was; instead it is used primarily to export the gross game level geometry of an application so that it can be reviewed or debugged in another application.

I have set up a Google Code page to host this code snippet. You can find it here:

http://code.google.com/p/physx2obj/

You can also download the source directly using these two links. However, the Google Code project will always be the most current copy.

PhysX2Obj.cpp
PhysX2Obj.h

Tomorrow I am going to write a code snippet 'Obj2PhysX' which will read one of these object files, either in world space or object space, and instantiate it on the PhysX SDK. The code will be written in a generic enough fashion that you can also instantiate the data through some other API if you prefer.

Two more compression libraries added to the test compression tool

2009-12-03T07:15:00.001-08:00

A contributor, Mārtiņš Možeiko, just added support for two more compression libraries. They are LZMA and FastLZ. Click on the picture above to see the performance differences between the various compression libraries.

As you can see it is pretty much a tie between several of the fast LZW style compressors. I would recommend you use the one which has the most liberal license and the cleanest looking source code.

I might, sometime soon, and some additional test cases. The current test case is a 10mb XML file; which I thought was pretty representative of a big ASCII file you might hope to get some good compression out of. I should also add some binary test cases as well.

Thanks all for the contributions. And, once again, here is the link to the compression test library.

Compression Test

2009-12-02T11:59:00.000-08:00

Back in March of 2008 I made a posting about comparing various open source compression libraries. You can read the original post at this link.

I don't get a lot of feedback about this coding website. That doesn't bother me because I upload stuff here as much for myself as anyone else. Over the years I have taken advantage of a lot of source code other developers have written and posted on the Internet. It is for this reason that I feel a sincere debt that I should contribute back as often as I can.

I use the various code snippets and projects I host on this site for my own personal needs all of the time so I don't really need feedback that other people find them useful for me to continue uploading stuff.

Nevertheless, it is quite gratifying when someone does give me feedback that they found something useful. The most gratifying experience of all is when someone made bug fixes and/or improvements to something I have posted; that is the ultimate reward.

Yesterday I received an email from Anthony Whitaker who updated the compression test app to support a new format that is faster than MiniLZO and does not have a restrictive license.

Anthony also wanted me to mention that "The LZMA SDK from 7zip is also in the freeware domain. And 7zip seems quite fast (relative to Rar and Winzip)"

The new format that Anthony added is Marc Lehmann's LibLZF. This is a very impressive tiny library which is extremely fast and lightweight. It is hands down the winner of all of the compression libraries already added to the test framework.

If you feel you have a better one, feel free to modify the compression test library to support your format. Let me know if you want to be a project member of the Google Code site.

The official location of the compression test library is located here on Google Code.

For the record, the compression test library now supports:

CRYPTOPP
MINILZO
ZLIB
BZIP
and now LIBLZF

Convex Decomposition Library now available on Google Code

2009-11-30T15:35:00.000-08:00

***NOTICE ** NOTICE ** My convex decomposition library is now deprecated.

Please see this blog post for further details.

Today I refactored my convex decomposition code into the form of a 'drop in' library that people can use. Here is a link to the Google Code repository.

You need only include a single header file 'NvConvexDecomposition.h' to use the tool.

What is convex decomposition?

Convex decomposition is the process of taking an arbitrarily complex concave triangle mesh and approximating it as a collection of convex objects.

See the image above to for an example of how an approximate convex decomposition can, depending on the recursion depth and other factors, accurately represent a collision model for a triangle mesh. There are no hard and cold set of parameters to use for all triangle meshes; how detailed you make the approximate decomposition is always going be dependent on your specific use case.

Why do I need it?

Most physics engines will not allow you to represent arbitrary triangle meshes as dynamic objects. Even if the physics/collision engine does support arbitrary triangle mesh collision, it always comes at a major cost in terms of performance and memory.

Therefore, if you have complex triangle meshes that you wish to be realistically simulated in a dynamic world the best solution is to substitute it for a collection of compound convex hulls.

The physics engine will see the collection of convex hulls for collision while the graphics displays the original source triangle mesh for the viewer. Depending on how accurately your compound convex hulls match the source graphics you may, or may not, see some small artifacts. The choice of how detailed to make the approximation is almost always a design decision based on your specific use case.

How do I use it?

I am providing the Convex Decomposition library as a relatively small collection of source code that resides in its own namespace. The source code is C++ and is in the namespace 'CONVEX_DECOMPOSITION'. Even though there are a number of CPP and header files you only need to include a single header file to use the library.

Simply include 'NvConvexDecomposition.h'

Create an instance of the library:

CONVEX_DECOMPOSITION::iConvexDecomposition *ic = CONVEX_DECOMPOSITION::createConvexDecomposition();

Next, add the triangles from the original raw triangle mesh you wish to approximate.

You add them one triangle at a time, passing in three const float pointers, each representing a single X,Y,Z co-ordinate in the original triangle mesh.

Example:

for (NxU32 i=0; iaddTriangle( tris[i].p0, tris[i].p1, tris[i].p2 );

Once you have added all of the triangles you can compute the convex decomposition as follows:

ic->computeConvexDecomposition(skinWidth,
decompositionDepth,
maxHullVertices,
concavityThresholdPercent,
mergeThresholdPercent,
volumeSplitThresholdPercent,
useInitialIslandGeneration,
useIslandGeneration,
useBackgroundThreads);

The convex decomposition process can take a very long time. For this reason the default behavior is to perform the computation in a background thread.

You will have to query: 'isComputeComplete' to know when it has finished.

If you want to interrupt the computation before it is done you can call 'cancelCompute'

To find out how many convex hulls were produced you call: 'getHullCount'

You can then iterate through the hull results and grab each one as needed: 'getConvexHullResult'

When you are finished using the library, simply call:

CONVEX_DECOMPOSITION::releaseConvexDecomposition(ic);

What are the current limitations of this implementation?

The code is functional but could use the following improvements:

(1) The convex hull generator, originally written by Stan Melax, could use some major code cleanup.

(2) The code to remove T-junctions appears to have a bug in it. This code was working fine before, but I haven't had time to debug why it stopped working.

(3) Island generation once the mesh has been split is currently disabled due to the fact that the Remove Tjunctions functionality has a bug in it.

(4) The code to perform a raycast against a triangle mesh does not currently use any acceleration data structures.

(5) When a split is performed, the surface that got split is not 'capped'. This causes a problem if you use a high recursion depth on your convex decomposition. It will cause the object to be modelled as if it had a hollow interior. A lot of work was done to solve this problem, but it hasn't been integrated into this code drop yet.

When will these limitations be fixed?

It is hard to say. The current version is functional and I don't foresee having a lot of time to work on this any time soon. If a specific need arises I may get back to it sooner. I definitely want to add the acceleration structures to the raycast routine; which will speed things up. I also really want to know why the remove tjunctions code has a bug in it, since that was working fine before.

What is all of this source code, what is it for?

As I said before, you only need to include 'NvConvexDecomposition.h' and nothing else to use the library. I will, however, document what the other pieces of source code are and what purpose they serve.

NvConcavityVolume.h / .cpp : Computes the 'volume of concavity' of a triangle mesh. It does this by first computing the convex hull for this triangle mesh. Next, it examines every single individual triangle in the original mesh and 'projects it' onto both the convex hull and on itself. If the projection hits the hull, then that extruded triangle volume is added as part of the 'total concavity volume'. It the projection hits the mesh itself, it first determines if it hit an interior or exterior face. If it hits an interior face, the volume is rejected. Otherwise, it adds to the volume of concavity the projection up to the point of self-intersection. This would be easier to explain with some drawings and pictures but I don't have time to make those up right now.
NvConvexDecomposition.h / .cpp : This is the main public interface to the convex decomposition library. This is the only header your application should need to include directly.
NvFloatMath.h / .cpp / .inl : This contains a collection of common and useful math library routines which work of of either const float or const double pointers.
NvHashMap.h : This single header file contains support for both vector and hashmap container template classes. The reason this header file is used is because some of the game engine integrations that I work on do not allow the use of the STL at all.
NvMeshIslandGeneration.h / .cpp : This is a code snippet which walks the topology of a triangle mesh, effectively flood filling it along the edges, to compute all of the independent mesh islands. Let's take the simple case. You pass in a single triangle mesh which actually contains two separate boxes. By walking the topology of the mesh the NvMeshIslandGeneration code snippet would immediately identify these as two distinctly unique triangle meshes.
NvRayCast.h / .cpp : This code snippet provides based support to cast a ray against an arbitrary triangle mesh. Ideally it would use acceleration structures (such as an axis-aligned bounding volume tree). The current version does not yet have this optimization built in.
NvRemoveTjunctions.h / .cpp : This code snippet is designed to identify and remove T-junctions in the triangle mesh. After a triangle mesh has been split by a plane it is common for t-junctions to be introduced. However, if you wish to continue to walk the topology of the mesh, either to identify mesh islands or to generate capped ends, there can be no t-junctions allowed in the mesh. This routine was not working properly when I put the library together so is currently disabled.
NvSimpleTypes.h : This is a tiny header file that creates a set of platform and compiler independent standard defines for integer and floating point data types.
NvStanHull.h / .cpp : Contains the convex hull generation code written originally by Stan Melax.
NvThreadConfig.h / .cpp : This is a small code snippet that provides a platform independent abstraction for creating threads and mutexes.
NvUserMemAlloc.h : This is a simple header file that controls how memory allocation is performed by this library. The default behavior is to use malloc/free and global new/delete. However, you can modify this header file to redirect memory allocations performed by this library to vector off to your application specific memory allocator if needed.
wavefront.h / cpp : This is a tiny code snippet to read a Wavefront OBJ triangle mesh file. It is not considered part of the convex decomposition library and is only included for the sample application.
main.cpp : This is a basic sample application that shows how to use the convex decomposition library by loading a triangle mesh from a Wavefront OBJ and uses command line switches to experiment with different parameters.

How does the convex decomposition algorithm work?

The convex decomposition algorithm works as follows.

The input mesh has any possible t-junctions removed to make sure that it has a clean topology. (Currently disabled)
The input mesh is broken up into any unique mesh islands. This is collection of triangles which all share edges. (Currently only enabled on the initial triangle mesh)
For each mesh island we do the following steps.
We compute the overall volume of the triangle mesh.
Make sure we have not exceeded our maximum decomposition depth, if we have, we are done.
We compute the volume of the current part of the mes we are working on. We then calculate what percentage the volume of this piece is, relative to the volume of the entire object. It the volume is too small (based on the input parameter 'volumeSplitThresholdPercent' then we are done with this piece.
Next we compute the 'volume of concavity'. This is done by building a convex hull around this piece of the mesh and then projecting the volume of each triangle on the original mesh onto either the mesh itself or the surrounding convex hull. The sum total is represented as the 'volume of concavity'.
We compute what percentage the volume of concavity is relative ot the volume of the surrounding convex hull. This percentage is then compared against the input parameter 'concavityThresholdPercent'. If the volume percentage of concavity is below this threshold we consider it 'good enough' and accept this piece as is.
If we have determined that the mesh piece is too concave we split it in half. First we compute the best fit OBB (object oriented box) around the convex hull of this piece. We create a split plane exactly half way along the long axis. (Other techniques for performing approximate convex decomposition have focused a lot of work finding just the absolutely perfect split plane to use. As you will see later, this algorithm doesn't require that.)
Once we have split the mesh by the plan we need to cap the ends so that the two pieces do not have holes in them. If we do not cap the ends then, as we recurse more deeply we will end up producing a hollow interior. It is important to note that this feature is not yet implemented! A lot of work has been done on this process and quite likely the library will be revised to support this feature at some time in the future.
Having split the mesh at the mid-point we just keep recursively calling the routine until we have exceeded our maximum recursion depth and/or other limits specified.
The final step is critical. Since we split each piece on the long axis of its orientation there is no guarantee that we split at exactly the correct location. We make up for this by actually splitting the source mesh many more times that is necessary. The final clean-up phase called 'merging' corrects for this.
For every hull we have generated we try combining it with every other hull in the decomposition. We compute the volume of the two hulls separately and compare that to the volume of the two hulls combined. If the difference in volume is below the parameter 'mergeThresholdPercent' than we combine the two hulls into one. We continue this process until we can no longer merge any hulls. In a brute force manner this technique causes the merged hulls to converge towards the optimal split boundaries.

ThreadFrac revised

2009-11-19T15:34:00.001-08:00

Grrr...I went to run my copy of 'ThreadFrac' that was uploaded in a couple of places and it wouldn't run due to side-by-side assembly issues or some such nonsense.

I rebuilt it with an embedded manifest and it should run now.

Let me know if you have a problem; requires Windows with DX9 to run.

The reason I was looking for ThreadFrac is that I want to start messing with the new 3d equation called 'Mandelbulb'.

I'm going to write a real-time multi-threaded raytracer and add it to my ThreadFrac program when I get a chance to work on.

If you haven't seen the 'Mandelbulb' yet, check it out.

Here is the link to the revised executable for ThreadFrac.

A test application for the MeshImport library and showcasing EZMesh

2009-11-05T10:07:00.001-08:00

I spent some time this morning and created a really nice sample program to demonstrate how to use the MeshImport plugins. (Here is a link to the formal documentation for the EZ-Mesh file format. It is a work in progress but should be finished up tomorrow)

The MeshImport plugin library provides an easy mechanism to both import and export fully skeletal deformed and animated mesh content.

It supports multiple graphics file formats but I am strongly recommending the EZMesh graphics file format.

I describe the reasons for this in the enclosed readme.

The readme can be found at this link: MeshImportReadme.txt

An example of an EZ-Mesh file which describes a skeleton, an animation, and a deformed mesh, can be found at the following link. In only 34 lines of XML it is able to describe all of the components necessary to a skeletal deformed (and animated) mesh in a highly human readable format. Let's see COLLADA (or any other graphics file format) try doing that.

EXPORT.EZM

To download the sample application, with all of the necessary DLL components, use this link:

MeshImportTest.zip

You can browse the sample demonstration source code here, so see how easy it is to actually use the MeshImport library.

main.cpp

Documentation for the Ez-Mesh file format.

Here are some more important links:

Here is the link to a Google Code project containing the Mesh Import test application.

If you are interested in building the plugins, or perhaps writing a new mesh importer. I have recently updated the source in the Google Code project.

The Google Code project for the Mesh Import libraries is located here.

Once you sync, to build the project load the solution file in:

\MeshImport\compiler\vc8\MeshConvert.sln

The FBX importer is not built by default, because it is dependent on the FBX SDK from Autodesk which you must obtain here. None of the other importers contain any external dependencies.

The solution file for the FBX importer is located in:

\MeshImport\compiler\vc8\MeshImportFBX.sln

You will need to change the include paths to point to wherever you have the FBX SDK on your machine.

Bug Fixes : Improvements to 'FastXml'

2009-10-23T10:45:00.000-07:00

I made a couple of bug fixes and improvements to the 'FastXml' code snippets. 'FastXml' is a very tiny code snippet (less than 300 lines of code) that will parse an XML file *in place*. It is very fast and easy to use.

The 'in place' behavior is what makes it extremely powerful. When it calls back with elements, attributes, and data, those pointers are *persistent for the lifetime of the object*! That means you do not need to do any string copying and can cache those pointers directly if it speeds up your processing code.

The bugs which were fixed are as follows:

(1) The original version had a bug that if you had an element with no attributes or data it would fail. Example:

(2) The original version could not interpret XML comments. It now does, and will call you back with the comment data. Example:

The feature improvement is that it will now call you back when an element is closed. This is sometimes necessary when parsing data with hierarchical state. Not typically necessary if you are just parsing the XML data as a linear stream.

I have updated the source files and they are located here:

FastXml.h
FastXml.cpp

Memory allocations are not 'bad' Debunking the myth

2009-09-29T08:20:00.001-07:00

I recently had a conversation with an engineer at a game company where he expressed annoyance that his development team was using that damned STL (STLPort in particular). I asked why and he felt that way. His response was that he couldn't stand how much memory allocation that the STL was doing. He also expressed annoyance that the performance of STL map was so slow and his programmers kept using it.

This raises a couple of points. First of all, there is rarely a reason to use STL map. The STL map/set is a red-black tree. The only reason you would ever use it is if you needed to maintain a set of objects in perfectly sorted order. This use case doesn't come up a lot, though, and most people are using it just to do key/value lookups. However, if all you want is a key/value lookup you should instead be using the hash_map.

What I really want to address in this post is the myth that 'memory allocations' are 'bad'.

What does someone mean by 'bad'?

I think what the mean is as follows:

Memory allocations are slow
Memory allocations cause fragmentation
Memory allocations cause thread contention
Memory allocations have way too much overhead
Memory allocations are not cache-coherent

Developers often hold these assumptions, but are they really true?

What if none of these things were true? Then, do you really have a valid complaint about how many allocations the STL is doing, or your other container classes?

With the micro-allocator I presented in the previous post, none of these criticisms are really valid.

Myth #1 : Memory allocations are slow : With the micro-allocator I presented memory allocations, and frees, are extraordinarily fast. A memory allocation simply involves returning a free pointer from a linked list 99.9999% of the time.

One reason people sometimes think that memory allocators are slow is...because they are *when running in a debugger in a debug build*. It is important to measure real performance outside of the debugger and in a release build when considering the cost of your memory allocation system.

Myth #2 : Memory allocations cause fragmentation : The design of my micro-allocator is that you give it a budget which is equal to an estimate of the maximum amount of memory needed for micro-allocations by your application. This is allocated a single time and carved up in power of two multiples. The allocator works within this single fixed block of memory and, so long as you do not exceed the budget estimate, it will never range outside this block of memory. No fragmentation, in the sense of memory being returned from all over the address space, will occur.

Myth #3 : Memory allocations cause thread contention : Last year when I was working on my JobSwarm code snippet I spent some time making sure it worked with a lockless queue. Once I had this working I tried to create a benchmark that would show the performance benefit of a lockless queue versus a standard mutex lock. What I found, is that it was very difficult to create a scenario where any significant performance distinction could be measured. It turns out, that unless you have an application which is spending almost all of its time in contention, you can't even quantify a benefit. Add to this the fact that my micro-allocator is so fast, usually just taking a few instruction cycles, any contention from a thread lock is going to be very small unless the only thing your application does *is* memory allocation in multiple threads simultaneously.

All that said, ideally a micro-allocator should entirely avoid or minimize thread contention. There are commercial micro-allocators that do this. The most well known is The Hoard Memory Allocator. Hoard is specifically designed to be highly efficient in multi-threaded environments. Also, as we move to more and more cores and, therefore more and more simultaneous threads, minimizing thread contention is important.

For my current implementation of the micro-allocator I just threw a mutex lock around the allocation and free routines. This was a quick and lazy approach to the problem though, as I said before, I doubt it is even an issue in most scenarios. That said, I would like to optimize it to be lockless, or near lockless, in the future. (It appears that I can download an evaluation copy of Hoard so sometime in the next week or two I will try to run benchmarks between it and my micro-allocator and I will report the results.)

Myth #4 : Memory allocations have way too much overhead : Most memory allocators will stick a header block in front of every allocation. This header block will often include linked list pointers and possibly a sentinel in a debug build.

The micro-allocator I presented, however, does not introduce any additional overhead. If you allocate 8 bytes, it takes exactly 8 bytes of memory. If you allocate 16 bytes, it takes exactly 16 bytes, etc. Now, if you allocate 14 bytes, it will, in fact, return a block of memory that is actually 16 bytes in length (the nearest power of two) thus 'wasting' the 2 bytes in between.

Perhaps the micro-allocator could be considered as having 'too much overhead' in the sense that it is a power of two allocator and always rounds up to the nearest power of two boundary. However, since it works primarily in a fixed budget of memory for small allocations, this is probably acceptable.

Myth #5 : Memory allocations are not cache-coherent : My micro-allocator is a power of two allocator and, especially since it requires no header block, always returns cache aligned blocks of memory. Any allocations of small objects in a sequence will naturally end up sequentially in the same area of memory.

All allocations 16 bytes to 256 bytes in size will be perfectly aligned on a page boundary. 8 byte allocations will lie on an 8 byte boundary or, every other one, 16 bytes.

Conclusion

The point I am trying to make here is that the concerns people have about using the STL, or other containers which do per-object allocations, are largely irrelevant *if* you have a high-speed micro-allocator under the hood.

There is no need to make special containers and special small object allocators if you have confidence that your core allocator already has these behaviors built right in.

Over the course of the next few months I plan to be doing some optimizations on console platforms using the micro-allocator I wrote and will be reporting any performance numbers I come up with.

So far I have only tested it extensively on the PC and it really doesn't show any performance difference between standard malloc/free which, as I pointed out earlier, is surprisingly fast anyway.

The lesson to be learned is that you shouldn't complain about the 'cost' of lots of tiny memory allocations until you know for fact that your application is really feeling a legitimate cost. If you find that there is a significant cost by using the standard library malloc/free, don't resort to writing a bunch of custom allocators and template code until you have evaluated a high performance general purpose small object allocator like Hoard, Doug Lea's malloc, or my own micro allocator I have posted here.

A free open source micro allocator in C++

2009-09-06T11:54:00.001-07:00

My code snippet today is a free open source micro-allocator. As many of you know, using the STL (or containers in general) will cause many,many, tiny allocations to be performed. Even just in a standard game engine, you will constantly be doing lots of small allocations for objects.

Now, some people work around this by writing custom pool allocators. However, that is not really necessary. If you have an efficient general purpose micro-allocator that is 'order-N' you can bank on the fact that it is always available. Don't worry about how much a memory allocation costs if it is less than or equal to 256 bytes in size. Don't worry about it not being cache aligned or cache-coherent. That will happen automatically.

The way my micro allocator works is that you give it an initial estimate of memory usage for micro-allocations. In a large game project, it might be good to give it a megabyte or two. In fact, it is ideal if you give it the maximum amount of memory your application will ever use for micro-allocations. You can find this out by running statistics on your application. If you give it too conservative an estimate, then the performance of the micro-allocator will decrease significantly as it will begin allocating a lot of additional chunks and will need to search them for frees.

If you are sure your application tends to use say 10 megabytes for micro-allocations, then give it that much to work with initially.

The amount of memory reserve is equal to the default chunk size, times six. As there are six powers of two from 8 to 256.

It then creates six fixed pool allocators for all of the power of two multiples from 8 to 256 bytes. It will do only one original heap allocation for this initial buffer and divvy up the memory usage equally between the six buffer sizes. This initial heap is how it can quickly know whether or not an address is owned by the micro-allocator and in which fixed pool it belongs in.

If you exceed this initial size, that is fine, the pools will simply grow based on your initial chunk size passed in.

For the vast majority of the time an allocation simply returns the current free pointer. A free simply patches the free list pointer as well.

This system is similar to the LOKI memory allocator but it does not use the STL or any other external libraries. It is also thread safe.

Here is the source code. Feedback welcome.

MicroAllocator.h
MicroAllocator.cpp

You can also get the source from here on Google Code.

Here are some hard statistics about the micro allocator. First of all, I need to say that I am very impressed with the speed of the default allocator built into Microsoft Visual Studio's run-time. It is very fast indeed.

I created a stress test which adds ten million small objects to an STL list, iterates that list, and then deconstructs the list. The way the STL implements lists each object causes a memory allocation to occur.

In release build (outside of the debugger) here are the results. (It is important to note that memory allocations (either debug or release) are much slower if the Visual Studio debugger is present. This is using STLPort. The first number is using malloc/free the second number is using the micro allocator.

Construction: 579 milliseconds to 422 milliseconds.
Iteration: 44 milliseconds to 44 milliseconds
Deconstruction 431 milliseconds to 154 milliseconds

As you can see allocation time was about 30% faster. Iteration was the same. Deconstruction time was 300% faster!

Here is another piece of information showing the difference between the STL provided with Microsoft Visual Studio and STLPort. The version of STLPort which is being tested has exception handling and thread safety disabled.

Construction STD:: 676 milliseconds to STLPort 567 milliseconds
Iteration 62 milliseconds to STLPort 44 milliseconds
Deconstruction STD 451 milliseconds to STLPort 402 milliseconds

As you can see STLPort is just slightly faster than the STL which comes with Microsoft Visual Studio 2005. However, the difference could simply be accounted for by the fact that thread safety and exception handling were disabled on this build of STLPort.

Mesh Import Mesh Converter

2009-08-14T17:46:00.000-07:00

I have just revised my MeshImport library on Google Code. It's worth syncing to and checking it out.

There is a tool in the subdirectory \bin\win32 called MeshConvert.exe which will convert to and from a variety of graphics file formats.

The formats supported are:

Wavefront OBJ
Unreal PSK : Full skeletal mesh and animation support.
Ogre3d : Full skeletal mesh and animation support.
EZ-MESH : My own 'easy' (i.e. human readable) XML format for animated skeletal meshes.
FBX : The FBX format from AutoDesk.

The FBX soluition will not build until you have installed the FBX SDK from AutoDesk. I am not allowed to distribute that SDK. Also, you can only import, but not export FBX files.

VectorFont a code snippet to render a high quality vector font in any application (uses the Hershey Font)

2009-08-01T16:23:00.001-07:00

Click on the above image to see an example string printed using the code snippet presented here.

This submission is an extremely useful code snippet. It consists of one header file and one CPP that can render a high quality 3d vector font. You provide a callback interface to 'draw a line'. You can use OpenGL, Direct3D, GDI, or any other API you might choose. You merely have to implement that one callback 'drawLine' and you get a high quality vector font that you can render in 2d or 3d as you prefer. The font used is called the 'Hershey Font' and is public domain in this format.

The pure virtual interface is called "VectorFont". It has just one method 'vprintf' to printf a string through the vector font printing routine.

The first parameter is an *optional* 4x4 matrix that the data points will be transformed through. If you do not provide a transform, then the string will always be printed relative to the origin and you can do any placement you want in your own callback method.

If you want the font to appear in 3d, but always 'camera facing', then you can build a camera facing rotation transform from the origin of the text to the current eye position. You can build this transform by using the 'lookAt' code snippet I published on this site in the past.

The next parameter you pass is 'textScale'. This simply scales the font to a particular size you might wish. A default of 1 is fine to start with and you can size from there until the font fits your particular needs. Since it is a vector font, it looks good at pretty much any scale.

The next parameter is a bool called 'centered'. If this bool is true, then the text will be centered around the position you passed in.

The final parameters are simply a standard 'printf' style format string and optional additional arguments.

This is a damned useful code snippet and I would appreciate a thank you from anyone who uses it.

Here is the source: VectorFont.h
VectorFont.cpp

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

// This code snippet allows you to render a high quality vector line font.
// The font it uses is called the 'Hershey Font' (search for it on Google).
// This font is completely public domain and you are free to use it in
// your own applications.
//
//
// Here is how you use this code snippet.
//
// Step #1 : Create an instance of the VectorFont pure virtual interface.
// Step #2 : call 'vprintf' with the transform, scale, center flag, and text you wish to print.
// Step #3 : Dispatch individual line segments to your own rendering framework.
// Step #4 : Release the VectorFont class.
//
// Here is an example usage in C++
//
// class MyLineDraw : public VectorFontInterfac
// {
// public:
// virtual void drawLine(float x1,float y1,float x2,float y2)
// {
// // Right here, in this callback, draw the line using your own line draw interface, OpenGL, D3D, or whatever works for you.
// }
// };
//
//
// MyLineDraw mld; // create an instance of our callback class to draw individual line segments.
//
// VectorFont *vf = createVectorFont(&mld);
// vf->vprintf(NULL,1,true,"This is a test of the emergency broadcasting system.");
// releaseVectorFont(vf);

class VectorFontInterface
{
public:
virtual void drawLine(float x1,float y1,float x2,float y2) = 0;
};

class VectorFont
{
public:
virtual void vprintf(const float *transform, // an *optional* 4x4 matrix transform to apply to each point as the font is rendered.
float textScale, // A scaling value to apply to the vertices of the font.
bool centered, // True if you want the text centered relative to its 3space position, specified in the translation component of 'transform' or 0,0,0 if no transform provided.
const char *fmt, // A printf style format string
...) = 0; // Optional additional parameters based on the format spec.
};

VectorFont * createVectorFont(VectorFontInterface *vf);
void releaseVectorFont(VectorFont *vf);

Polygon Triangulator - Ear Clipping Method

2009-07-08T12:06:00.000-07:00

Here's a very useful code snippet. It performs polygon triangulation on a set of planer 2d or 3d data points. It supports concave polygons but not polygons with holes.

This implementation uses the standard ear clipping algorithm which decomposes the polygon into convex pieces. The API is really straightforward and easy to use.

First create an instantiation of the triangulator class:

Triangulator *t = createTriangulator();

Next, add the set of points which define the polygon contour. You can add the points as either floats or doubles; internally is uses double precision. If your polygon is 2d, just pass zero for the z component.

Example: t->addPoint(x,y,z);

To perform the triangulation itself you call:

unsigned int tcount;
unsigned int *indices = t->triangulate(tcount,epsilon);

This will return the number of triangles produced (stored in tcount) and a pointer to the array of triangle indices in the form of (a1,b1,c2, a2,b2,c2, a3,b3,c3, ....).

The value 'epsilon' is a threshold that determines whether or not a line segment in the polygon is considered co-linear or not. Since we are dealing with floating point numbers there can be inherent precision issues. Internally the triangulator operates at double precision.

If you want to retrieve the original data points, based on the index, you cal call 'getPoint'.

The implementation computes the bounding box for the input polygon and selects the two longest sides to perform the 2d triangulation against.

If you want to triangulate another polygon, just call 't->reset()' and start adding the new points.

When you are done with the triangulator class call: releaseTriangulator(t)

This code snippet uses the 'PIMPLE' paradigm (pointer to implementation) which is my favorite pattern.

The primary benefit of this code is that it is nicely packaged in snippet form.

The header file is: Triangulator.h
and the implementation in: Triangulator.cpp

Also, the FloatMath library has been revised to use this implementation internally.

FloatMath.h
FloatMath.inl
FloatMath.cpp

Apparently I'm not Charles Bloom

2009-06-13T08:10:00.001-07:00

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

2009-06-12T15:32:00.001-07:00

( 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

2009-05-22T11:22:00.000-07:00

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

2009-05-01T18:45:00.001-07:00

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

2009-04-25T13:21:00.001-07:00

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

2009-04-20T10:19:00.000-07:00

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?

2009-04-20T08:47:00.001-07:00

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

2009-04-18T16:10:00.001-07:00

This source is now officially located on Google Code here.

If I find time I will revise it to have a full sample application that loads a bunch of PNG/JPegs and packs them.

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

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

2009-04-18T07:52:00.000-07:00

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

2009-03-08T14:26:00.000-07:00

(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

2009-02-28T14:30:00.001-08:00

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

2009-02-21T16:29:00.000-08:00

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

2009-01-10T13:33:00.001-08:00

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

2009-01-10T12:59:00.001-08:00

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

2009-01-07T08:49:00.001-08:00

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

2009-01-02T10:03:00.000-08:00

(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

2008-11-28T10:53:00.001-08:00

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

2008-11-28T07:54:00.001-08:00

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

Instant Messaging API code snippet

2008-06-24T09:50:00.001-07:00

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

2008-06-23T08:21:00.000-07:00

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

2008-06-23T08:09:00.000-07:00

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

2008-05-21T09:59:00.000-07:00

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

2008-05-06T18:51:00.000-07:00

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

2008-05-05T09:05:00.000-07:00

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

2008-03-25T16:29:00.000-07:00

(Note: This library has been updated. Go to the following post to find the latest information. It is now hosted officially on Google Code.)

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

2008-03-13T09:41:00.000-07:00

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

2008-01-10T13:13:00.000-08:00

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

2008-01-02T11:08:00.000-08:00

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

2007-08-01T13:26:00.000-07:00

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

2007-06-16T13:32:00.000-07:00

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

2007-06-16T13:12:00.000-07:00

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

2007-06-16T13:05:00.000-07:00

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

2007-06-16T12:49:00.000-07:00

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

2007-06-16T12:35:00.000-07:00

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

2007-04-17T11:18:00.000-07:00

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

2007-03-14T14:53:00.000-07:00

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

2007-03-13T15:51:00.000-07:00

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

2007-03-12T08:56:00.000-07:00

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

2007-03-05T08:25:00.000-08:00

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

2007-02-02T19:28:00.000-08:00

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

2007-02-01T14:39:00.000-08:00

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

2007-01-12T08:21:00.000-08:00

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

2007-01-11T08:20:00.000-08:00

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

2007-01-08T17:35:00.000-08:00

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

2006-12-29T19:26:00.000-08:00

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

2006-12-01T15:00:00.000-08:00

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

2006-11-10T14:01:00.000-08:00

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

2006-10-25T16:11:00.000-07:00

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

2006-10-12T14:57:00.000-07:00

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

2006-09-29T11:22:00.000-07:00

(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)

2006-09-17T12:58:00.000-07:00

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

***NOTICE ** NOTICE ** My convex decomposition library is now deprecated.

Please see this blog post for further details.

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

2006-09-01T11:20:00.000-07:00

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

2006-08-11T14:56:00.000-07:00

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

2006-08-03T14:33:00.000-07:00

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

2006-08-03T13:42:00.000-07:00

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.