Toolbox.GetConvexHull slower in release mode than debug

[speciesUnknown]

This is a very odd thing. This method is slower in release mode, but not so in debug. I have no idea why. I am using the default settings for optimisation and have not modified anything in the project files for either my game project or BEPU, so, what could be causing these issues? Here is a console dump from the application (since the debugger and any form of profiler affects the issue ive used good old fashioned console output to test the timings)

I currently have 8 unique convex hulls (and by extension GetConvexHull is called 8 times). When I run the game in debug mode either with or without the debugger attached, I get times in the order of 100ms, and if I run it with a release build with the debugger I get the same; however, in release mode, without the debugger, the time taken for the most complex hull shoots up to the region of 2500ms. I can determine this accurately without using a debugger by wrapping calls to ConvexHull constructors with Stopwatch calls. (I'm calling this from two places but only wrapped the one, so there are 6 results not 8 )



Release build, no debugger:

Code: Select all

Milliseconds Taken for call to new ConvexHullShape with 1949 vertices of input data is 2355
Milliseconds Taken for call to new ConvexHullShape with 193 vertices of input data is 13
Milliseconds Taken for call to new ConvexHullShape with 105 vertices of input data is 27
Milliseconds Taken for call to new ConvexHullShape with 1836 vertices of input data is 723
Milliseconds Taken for call to new ConvexHullShape with 1284 vertices of input data is 2986
Milliseconds Taken for call to new ConvexHullShape with 593 vertices of input data is 133
Press any key to continue . . .

Release build, with debugger:

Code: Select all

Milliseconds Taken for call to new ConvexHullShape with 1949 vertices of input data is 210
Milliseconds Taken for call to new ConvexHullShape with 193 vertices of input data is 4
Milliseconds Taken for call to new ConvexHullShape with 105 vertices of input data is 3
Milliseconds Taken for call to new ConvexHullShape with 1836 vertices of input data is 63
Milliseconds Taken for call to new ConvexHullShape with 1284 vertices of input data is 119
Milliseconds Taken for call to new ConvexHullShape with 593 vertices of input data is 58

Debug build, no debugger:

Code: Select all

Milliseconds Taken for call to new ConvexHullShape with 1949 vertices of input data is 230
Milliseconds Taken for call to new ConvexHullShape with 193 vertices of input data is 5
Milliseconds Taken for call to new ConvexHullShape with 105 vertices of input data is 3
Milliseconds Taken for call to new ConvexHullShape with 1836 vertices of input data is 67
Milliseconds Taken for call to new ConvexHullShape with 1284 vertices of input data is 140
Milliseconds Taken for call to new ConvexHullShape with 593 vertices of input data is 54

Debug build, with debugger:

Code: Select all

Milliseconds Taken for call to new ConvexHullShape with 1949 vertices of input data is 3914
Milliseconds Taken for call to new ConvexHullShape with 193 vertices of input data is 8
Milliseconds Taken for call to new ConvexHullShape with 105 vertices of input data is 4
Milliseconds Taken for call to new ConvexHullShape with 1836 vertices of input data is 102
Milliseconds Taken for call to new ConvexHullShape with 1284 vertices of input data is 216
Milliseconds Taken for call to new ConvexHullShape with 593 vertices of input data is 79

[Norbo]

That's interesting. I've managed to reproduce it, but to a much smaller degree with the sample pointset used.

I vaguely suspect it has something to do with something somehow preventing certain operations from resulting in 'bad' floats (NaN's, infinities, denormals). It's odd that both the Release/NoDebugger and Debug/WithDebugger exhibit the behavior; some of the Debug/WithDebugger extra cost can certainly be attributed to the regular extra overhead, but 17x is excessive. Those two builds also seem to rule out the independent action of either optimizations or the debugger as the primary culprit.

Given that I could not observe the effect on a pointset with many internal points, I would guess that the more surface points in the original pointset, the more this problem occurs. This corresponds to a difficult case for the convex hull algorithm both computationally and numerically. If the closeness of thresholds or degeneracy of intermediate geometry is too great, perhaps it could occasionally flip out.

Do your meshes fit this hypothesis? That is, do the meshes that suffered the most (like the fifth and first one) tend to have mostly surface points that would either never get pruned or would be harder to reach by the algorithm, and do the least affected meshes tend to have more internal points?

By the way, some general/unrelated information: the cost convex hull collision detection increases roughly linearly with the number of points in the final convex hull. It's recommended that the final point set used for collision detection be as simple as possible for performance reasons (30 points would be on the high end).

[Norbo]

Well, at least part of my theory is wrong. I tried out a spherical pointset in which every single point makes it into the final set. The run times are consistent with regular expectations (release/nodebugger is fast, debug/debugger is slow, but not horrifically slow, and the intermediate builds gave intermediate times).

Despite being the worst case for final vertex count, the sphere does not stress thresholds much; it may still be related to excess coplanarity in the original point set.

When I mentioned I reproduced it, I should have said that I reproduced a minimal version of the release/nodebugger results. All the debug/debugger results I've seen so far are still within expectations.

The convex hull algorithm implementation is ancient relative to most of the codebase, so I'm sure there are some oddities hiding out in it somewhere. I may end up just rewriting the whole thing at some point; there's huge room for optimizations and improvements. I've got to go to sleep now, but in the mean time, any details you can provide about the mesh (or perhaps the offending mesh files themselves) might help.

[Norbo]

I got around to testing coplanarity. It does indeed appear related; the final generated geometry in release/nodebugger is visibly different (and worse) than the other options. Multiple triangles are clearly degenerate.

The results appear to be best in debug/debugger and debug/nodebugger, with release/debugger having a few more issues, and release/nodebugger being the worst.

Could you try visualizing the resulting convex hull to see the final mesh topology? This can be done in the demos quickly by grabbing the points, running the convex hull algorithm on them (Toolbox.GetConvexHull can be called directly), and taking the resulting vertices and indices into a mesh like so:

Code: Select all

            var mesh = new TriangleMesh(new StaticMeshData(hullPoints.ToArray(), indices.ToArray()));
            game.ModelDrawer.Add(mesh);

Do you observe the same sort of degradation in quality from debug/debugger to release/nodebugger in your meshes?

[Norbo]

I've fiddled around with the GetConvexHull method in the latest development version: http://bepuphysics.codeplex.com/SourceC ... evelopment

How does it look now for your meshes? My test cases no longer show the odd performance issue nor do they show degenerate triangles. The hull still isn't perfectly optimal, but it looks better (no degeneracies).

[speciesUnknown]

I'll try out the new build in a few minutes, but first, here are the two meshes Im using. Note that I'm creating seperate convex hulls for each submesh, because objects in my game must be articulated. In each case, I'm making a seperate convex hull out of the body, turret and barrel.

The tank:
http://dl.dropbox.com/u/6974724/tank3.x

The laser turret:
http://dl.dropbox.com/u/6974724/lasercannon.x

If you need me to, I'll map out which submesh is applicable to which data point.

[speciesUnknown]

The new code is a lot faster, its far closer to what I was expecting originally, in particular, a release build w/o debugger attached is as I would expect.

Great job norbo, bepu is getting better and better with your attention.