Happy Holidays!

Merry Merry and Happy Happy!

Thank you for the past year, and good luck for the following one! Here's a little game to fill the idle moments during the holidays:

• Mottainai-1.0_OSX.zip (Mac only, sorry!)

See you next year!

Computational Geometry Sucks!

Computational Geometry is hard. Most of the examples out there are crap and the good stuff is without exception hard to understand.

You can usually whip up a 100 liner to solve a problems, if your input is cloud of random points. This is what pretty much all the Java code out there does, but the input data for your game is not a random point cloud!

I hate computation geometry, but yet it is so important! It drives me crazy.

I was recently looking for a robust 3D convex hull algorithm which would work for a couple of hundred points in realtime. That is, something sub 2.0 ms on a 2GHz Core Duo.

I wrote a couple of solutions myself, including one which was O(n^4) and surprisingly did not scale beyond 25 points. Finally I was hinted towards this patch for Bullet Physics, and it turned out to be a real gem!

It is fast, scales well (it's O(n log h)), and is robust too. My litmus test is a grid of 4x4x4 points. It passes that and even handles coplanar input. Pretty much all the Java code out there fails on that input.

So I took that patch, regexp'd it, copy pasted some Bullet code, deleted stuff I did not need, shuffled things around a bit, and made it output triangles and I'm finally a happy man!

Style vs. Technique

This is a very dear topic to me, I just wish I was able to output my through about it efficiently.

I recently posted a link to a paper and video in twitter:

Situation Agents: Agent-based Externalized Steering Logic

• http://www.cs.ucla.edu/~pfal/Petros_Faloutsos/Crowd_Simulation.html
• http://www.cs.ucla.edu/~mubbasir/pdfs/situation-agents-paper.pdf

I got a reply that the results are not very realistic. And it is very true, especially the formation examples look quite unrealistic indeed.

But compared to what? Some generic situation in real-life? Our generic assumption about how things should behave? Maybe you were in a similar situation yesterday and you comparing the video to that.

There was a one important lesson I learned from art school: when you critique someone's work, you better be able to explain your point of view. You have to define your point of view, your artistic vision and potentially references to existing methods.

In order to have a good critique over the above example both the presenter as well as the commenter needs to point out their artistic point of view. Otherwise the discussion is pointless.

More scientific way to justify your point of view is to hypothesize, collect data, build a model, and compare your method against it. This approach is well executed in the following research:

A Synthetic-Vision-Based Steering Approach for Crowd Simulation

• http://www.irisa.fr/bunraku/GENS/jpettre/

When the model is tuned based on the input data, the output looks and should look much like the data that was used to tune it.

My critique to the above method is that can it reproduce different kind of styles? For example if two actors would act out exaggerated situation where and a nerd and a bully avoid each other, could the method capture that style?

In my humble opinion in order to critique a technique you either have to have an artistic point of view (one that you can also explain to others) or if you compare things to realism, you better have good data! Otherwise the discussion will be just bike shedding.

Seeing potential of a method is not easy either. Ken Perlin showed an interesting picture pair during talk at Paris AI Conference this year. In one picture there was a raytraced marble sphere, picked from his original noise paper, on other picture there was a shot from a movie which had beautifully rendered stormy ocean, which was build using his noise function.

Examples are generic and try to show off the technicalities of the technique, but it takes an artistic vision to turn a technique into something worth watching.