Thursday, March 28, 2013

Uniformly distributed points on sphere

Sooner or later everybody will need uniformly distributed points on a sphere. There doesn't seem to be a standard method for doing this, so I wrote a very simple iterative algorithm that pushes verts away from each other while continuously normalizing the point data. This will eventually find a stable state where the distance between any two neighboring points are very similar. Performance is terrible but it gets the job done, so only use this for offline stuff. There is also an option for distributing points on a hemisphere (y>0). Set the number of iterations to at least the number of input points for a good distribution.

Source code: uniformpoints.cpp

Sunday, March 24, 2013

Convex Hulls Revisited

I have written about 3D convex hull generation here before. I find it a very appealing problem because it is so well defined and to my knowledge there is no de facto standard algorithm or implementation. I come back to this topic every now and then since I need a good implementation myself.

Quickhull is probably the most popular algorithm, but it is hard to implement in a robust way. The qhull implementation has a somewhat questionable license and more significantly it is a really complex piece of software and contains a bunch of other features. I'm on a quest to create a fast, robust convex hull generator that is free to use and is self-contained in a single cpp file.

I'm currently experimenting with an algorithm based on the support mapping, often used in physics and collision detection. The support mapping for a point cloud for a given direction is the point that is farthest in that direction, which simply means finding the point with maximum dot(dir, point). The supporting point for any direction is guaranteed to be on the convex hull of the point cloud. Very convenient.

The algorithm starts with the smallest possible closed mesh - three vertices connected by two triangles facing in opposite directions. Any three points will do, as long as they are on the convex hull (supporting vertices). Each triangle is then exanded by the supporting vertex in the normal direction. This is done by splitting the triangle into three triangles, all connected to the new vertex. This expansion step may cause the mesh to become concave, so the expansion step needs to be followed by an unfolding step, where convave edges are "flipped" to make the mesh convex again.

Flipping one edge may cause nearby edges to become concave, so this step needs to be repeated until all edges are convex, effectively "untangling" any wrinkles introduced by the expansion. Below is a short clip visualising the construction of a hull through a series of expansion and unfolding steps. For clarity, there is only 12 points and they are all on the convex hull.

The interesting thing about this method is that it is based primarily on topology. Both the expansion and the unfolding step guarantee that the mesh is kept well-defined and closed, so there are no degenerate cases. The only critical computation is how to determine wether an edge is convex or not. I'm still investigating the most robust alternative here. My current one does not deal with all degenerate cases, but I'm pretty sure this can be done.

The algorithm has a number of desirable properties:
  • Can be used with a tolerance in the expansion step for automatic simplification.
  • Relatively easy to implement (mine is about 400 lines of code).
  • Handles co-planar and degenerate input data.
  • The output mesh is built entirely from the input vertices.
  • Can be modified to use any support mapping function, not just point clouds.
I'm not entirely sure this is a novel idea. I'd actually be surprised if it is, given its simplicity, but I haven't seen any references to it before. Please write a comment if you know. I'll get back with more details and a performance comparison later.

Friday, March 8, 2013

Mediocre properties

I think most games use some kind of property system as a way to expose, edit and serialize parameters for game objects. There are of course very many ways to implement it, but here is how I'm currently doing.

Each game object that is big enough to carry properties has a PropertyBag instance. The types of properties should ideally be setup per class, not per object, but that requires extra code and I always strive for keeping the amount of code to a minimum. Hence, the construction of a property bag is done in the object constructor and might look like this:

mProperties.add("density", "1.0");
mProperties.add("color", "1 0 1");

Yes, those are strings. Most game developers don't like them. I do, and I will explain why later. Now, setting up properties for every object this way is both time consuming and memory intensive, and there will most likely be lots of instances with exactly the same property configuration. Therefore, property configurations are cached on a per class class basis:

if (mProperties.init("GameObject"))
mProperties.add("density", "1.0");
mProperties.add("color", "1 0 1");

So the property definitions are not actually stored in each object, but merely a pointer to a definition which is created by the first object using it. This of course reduces memory overhead by magnitudes. The system also handles inheritance, so a derived class can add more properties to an existing definition, but the amount of data per object to store the whole definition is only a single pointer. In a derived class, the parent constructor will run first, adding properties and then each derived class adding their own in order. The init method detects this by being called several times with different strings.

Now that the property bag is configured I can start reading and writing properties using various get/set methods:

float density = mProperties.getFloat("mass");

This will convert the string "1.0" to a float and return it. If the string isn't numerical, it will still return a valid number (0.0), but issue a warning. I also have some operator overloading to allow immediate conversion from most basic types:

float density = mProperties["mass"];

The system accepts any type conversion on the fly:

mProperties["mass"] = 2.0f;
string str = mProperties["mass"]; // str is now "2.0"

This is all very flexible, but performance is somewhat questionable. I typically cache any property that is used every frame in a member variable. Therefore each game object has a loadProperties() method that gets called whenever something changes. This gives the object a chance to cache a local copy of each performance critical property:

mDensity = mProperties["density"];

So how much memory is being used? As long as an object doesn't override the default value, nothing is stored per object, hence adding more properties to a class doesn't make objects bigger unless you cache a local copy per instance for performance reasons. The system also supports template values, so in addition to default values, each object can also be assigned a certain template (another pointer). Templates are defined in a simple XML file with key/value combinations that have no knowledge whatsoever about the object type. The same template can even be assigned to property bags of totally different types if wanted.

For instance an object that want to use a more slippery form of rubber can use the rubber template, but override the friction property explicitly and only the new friction value will be stored in the object.

Using strings have two obvious problems: a) It is slow and b) Loose bindings are sensitive to typos. The first issue is seriously overrated IMO. Comparing strings is not as slow as most people claim, especially when using a custom string object with built-in storage. In most cases you only need to compare the first letter of two strings to detect a mismatch. The second issue is more worrying, but the system can easily issue warnings when asking for properties that do not exist. Then at least you will be notified of typos at runtime.

There are several benefits that I think clearly outweigh the negatives. The ability to serialize an object into XML/JSON/YAML/etc using solely the property bag is one of them (the entire level loading/saving code is 50 lines of code, and there is no additional serialization code per class), automatic property editing from a level editor is another. The editor doesn't need to know anything about what is being edited, it just presents all the properties of an object and their values as strings (another 50 lines of code to edit any property of any object in the game). Keeping the property names and their values as strings also allow for trivial scripting integration. We use Lua and have one very useful function to query any property: mgGet("") where name is the object name and property is the property name. The result is always a string, which can then be converted to whatever type seems fit (not even 50 lines of code to access any property of any object in whole game from script).

One improvement I would like to make is how the property values are stored internally. Currently I store them as strings regardless of what they represent, but a more efficient way would of course be to store them in binary form, based on what they represent. The format can be chosen either during initialization or at every set operation.

I currently consider the property bag a blueprint of the object rather than a direct mapping of the object internal state. Hence, if an objects internal state is updated at runtime I don't update the properties at that point. That way I can easily reset an entire level to the state it was at load time. There are benefits of keeping a direct mapping too, so I don't really have a strong opinion as long as it's consistent. A direct mapping certainly puts the property system under more stress. Anyone who tried?