Skip to main content

Full hull

Today I was scouting around for a decent convex hull generator. It's quite surprising to me that such a clearly defined task still doesn't have a de facto standard implementation that everybody uses. I just wanted one for computing the visualization meshes, so performance is not even critical.

I looked into a couple of different ones that had clean interfaces. This one looked promising due to its simplicity, but after trying just a few point clouds it crashed on me. Convex hull generation is tricky that way "Oh, how hard can it be, just split that triangle, merge those two, test for that plane, blah blah" and then when you sit down and implement it there are all these degenerate cases, and you can't really make assumptions about anything. Our convex hull generator at Meqon was a constant pain in the ass for three years. I don't think we ever got it right. Qhull seems to be very robust, but a) it's a huge mess, b) it has a ton of features you don't want and c) it has a somewhat questionable license.

James Dolan kindly pointed me to an implementation written by my former colleague Stan Melax for a physics exporter. John Ratcliff then wrapped it up, gave it the name "stanhull" and posted it on his code suppository. It took me five minutes to integrate, it works like a charm, it has a great interface, no dependencies and it's fast. Look no more and cheers to Stan.

I have also contemplated to do an automatic visualization of implicit convex hulls using only the support function. Not that it would be super-useful, but still pretty cool to use the same code for visualizing all types of convex objects. A naive approach would be to sample the support function in a ton of different directions and just build a hull of the resulting points, but I've been thinking about a more intelligent subdivision method to avoid sampling crazy many directions and still not miss corners. Might try it tomorrow.


Comments

Popular posts from this blog

Bokeh depth of field in a single pass

When I implemented bokeh depth of field I stumbled upon a neat blending trick almost by accident. In my opinion, the quality of depth of field is more related to how objects of different depths blend together, rather than the blur itself. Sure, bokeh is nicer than gaussian, but if the blending is off the whole thing falls flat. There seems to be many different approaches to this out there, most of them requiring multiple passes and sometimes separation of what's behind and in front of the focal plane. I experimented a bit and stumbled upon a nice trick, almost by accident. I'm not going to get into technical details about lenses, circle of confusion, etc. It has been described very well many times before, so I'm just going to assume you know the basics. I can try to summarize what we want to do in one sentence – render each pixel as a discs where the radius is determined by how out of focus it is, also taking depth into consideration "somehow". Taking depth i

Screen Space Path Tracing – Diffuse

The last few posts has been about my new screen space renderer. Apart from a few details I haven't really described how it works, so here we go. I split up the entire pipeline into diffuse and specular light. This post will focusing on diffuse light, which is the hard part. My method is very similar to SSAO, but instead of doing a number of samples on the hemisphere at a fixed distance, I raymarch every sample against the depth buffer. Note that the depth buffer is not a regular, single value depth buffer, but each pixel contains front and back face depth for the first and second layer of geometry, as described in this post . The increment for each step is not view dependant, but fixed in world space, otherwise shadows would move with the camera. I start with a small step and then increase the step exponentially until I reach a maximum distance, at which the ray is considered a miss. Needless to say, raymarching multiple samples for every pixel is very costly, and this is with

Undo for lazy programmers

I often see people recommend the command pattern for implementing undo/redo in, say, a level editor. While it sure works, it's a lot of code and a lot of work. Some ten years ago I came across an idea that I have used ever since, that is super easy to implement and has worked like a charm for all my projects so far. Every level editor already has the functionality to serialize the level state (and save it to disk). It also has the ability to load a previously saved state, and the idea is to simply use those to implement undo/redo. I create a stack of memory buffers and serialize the entire level into that after each action is completed. Undo is implemented by walking one step up the stack and load that state. Redo is implemented in the same way by walking a step down the stack and load. This obviously doesn't work for something like photoshop unless you have terabytes of memory laying around, but in my experience the level information is usually relatively compact and se