Skip to main content

More hull

I realized I never wrote anything about the generic convex object visualization I mentioned earlier. It actually turned out really good, and the algorithm is very simple:

1) Get the support point for each of the positive and negative coordinate axes.
2) Build an octahedron with corners at the six points (like a pyramid pointing up, on top of a pyramid pointing down. This is the starting shape.
3) For each triangle in the current shape:
Get support point in outwards normal direction.
If support point does not equal (within margin) any of the three corners,
split the triangle into three new ones, using the new point.
4) Repeat step three until convergence, or maximum number of iterations.

Splitting the triangle into three is not ideal since it encourages long thin triangles and a rather uneven triangle distribution, but in practice it works fairly well. I guess one could look into Loop-style edge splitting instead, but it would require more bookkeeping.

I add a small sphere to each support function to get the slick round edges virtually for free!



I think I'm gonna have to take back what I said about the performance of stanhull. It's actually really slow and can somtimes take several milliseconds for just a few hundred points. I'm going to try and write my own convex hull generator based on the visualization algorithm above, but with one extra step - after each triangle split, prune vertices that are inside the newly formed tetrahedron. It would not be able to generate an optimal hull without reduction, but it would be guaranteed to have valid topology and connectivity. It would also have an almost trivial implementation and perform really well.


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 into…

Stratified sampling

After finishing my framework overhaul I'm now back on hybrid rendering and screen space raytracing. My first plan was to just port the old renderer to the new framework but I ended up rewriting all of it instead, finally trying out a few things that has been on my mind for a while.

I've been wanting to try stratified sampling for a long time as a way to reduce noise in the diffuse light. The idea is to sample the hemisphere within a certain set of fixed strata instead of completely random to give a more uniform distribution. The direction within each stratum is still random, so it would still cover the whole hemisphere and converge to the same result, just in a slightly more predictable way. I won't go into more detail, but full explanation is all over the Internet, for instance here.

Let's look at the difference between stratified and uniform sampling. To make a fair comparison there is no lighting in these images, just ambient occlusion and an emissive object.


They …

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 seriali…