I have had this idea for a long time about some tool to follow the steps of a complicated algorithm in some way other than stepping through it in the debugger, trying to mentally visualize what's going and frenetically scribbling unrecognizable geometrical figures on envelopes and old receipts.

A simple visualization sandbox is useful for visualizing the result, but it's really hard to visualize intermediate steps. GJK is a good example of a complex, iterative algorithm that has a visual representation at every step. A typical demo application would visualize the resulting closest points, normal, etc, but not the internal steps of the algorithm itself, so if something goes wrong, you're screwed. The typical way to deal with it is to write parts of the algorithm in an isolated visualization environment and then lift them over to the real implementation when they are "tested". However, for visualization code to be useful, it needs to stay in the actual implementation so when real-world problems start coming in, they can be tracked down quickly.

To do this properly, you would need to step the algorithm from the outside - that is, make an extra API to control it and poll the relevant information from the outside. Such an API would likely be substantially larger than the original API itself, and it's definitely not something you would want to ship.

Another approach would be to add visualization code to the algorithm implementation, but this does not tie in very nicely with modern rendering engines. Say you want to use OpenGL for rendering. It would be convenient to draw lines, points, text, etc and then wait for some input event before going any further. However, the way OGL (or D3D) works, you fill a back buffer and won't see it until the entire frame is drawn. There might be a way to go around this, but it would be hard to integrate into any other application. I was for a moment considering running the rendering loop in a separate thread and feed the visualization thread with commands from the algorithm thread and also include a pause command, that would block until the user wants to step further.

The solution I finally settled on was to use an event stream that is filled in by the algorithm implementation using macros and a visualization framework for rendering the stream. Hence, the algorithm runs all the way from beginning to end, recording visualization events along the way. There is a pause event which indicates that the visualization framework should wait for user input.

I also needed something for removing graphics that was previously added. Say you have the normal of a plane, and the plane is changing every iteration. One way to do that would be to start referencing all the events and add explicit remove events, but that would quickly get quite messy. Instead, I added push and pop commands, so a subset of the graphics can be visualized and then removed before going any further. My visualization app can walk both forwards and backwards in the recorded event stream, which makes it easy to follow what's going on. It turned out to be quite useful and it doesn't bloat the code too much, typically something like this:

DEBUG_PRINT("Computing stuff");
for(int i=0; i<10; i++)
{
...
computePoint(p);
computeNormal(n);
DEBUG_PUSH();
DEBUG_PRINT("Point and normal at iteration " + i);
DEBUG_POINT(p);
DEBUG_LINE(p, p+n);
DEBUG_PAUSE();
DEBUG_POP();
}

This has proven to be really useful for debugging GJK, EPA, MPR, etc. I use automatic unit testing on distance queries, save the state for failing configurations and load them up in the debugger to manually inspect what went wrong. It gives a pretty clear view on various precision problems, termination critera, etc that would be very hard to get an intuitive understanding of otherwise.


My visualization app in the middle of a penetration depth calculation.

The downside of my approach is that you can't combine it with stepping through a regular debugger. It would be quite nifty to see the graphical representation updating while stepping through the code in the debugger. I guess I could pass the event stream over a network socket to a different process, but that sounds just a tad too ambitious for my needs at the moment :)