In the last few days I finally fixed high-dpi support in 🍊 and added proper support for MSAA. Now everything looks super crisp and smooth and you can see how dogshit the current meshing system is in full 4k glory... so, I'm pondering what to replace that with.
Great news everybody! I've decided on a promising bvh-ish data structure which I think is most logically called a "ball tree". If this is able to produce the cluster building behavior I want, then a concurrent version will eventually be needed, which would most naturally be called a "concurrent ball tree", which should not be confused with the "concurrent binary tree" and other forms of CBT.
@demofox noted! my theory is you can force FCC/HCP lattices to nest by committing to each ball in the smaller ball lattice corresponding to exactly one ball in the larger ball lattice. The goal is to build a set of convex hulls by finding neighbors that produce zero crossings along their connecting edges, and turn those hulls into triangle patches by ignoring all faces with any interior vertices and shrinkwrapping the rest to the isosurface.
@demofox the ball hierarchy is meant to be a more efficient divide and conquer strat than voxels in terms of sdf evaluations, and then if that actually works the way I want it to I have a hunch that stitching together cluster patches at different recursion depths might be doable.
@demofox I keep coming back to this idea so I figure worst case of prototyping it is I finally put a bad idea to rest and free up some brain space lol.
Or maybe the worst case is it works wonderfully and then my head is filled with all of the related ideas like "what if this but with a blue noise distribution"
@demofox the better version is probably start with a set of surface "hints" (it's CSG - I know where all the shapes are more or less) and then do sort of a fill search to find all of the starting cells, and recurse to produce finer clusters.
Here's another view with the parameters tweaked a little bit and a slightly denser sphere packing.
This is really promising! The lua prototype is able to produce all of the convex hulls fast, and then my current "surface nets" implementation takes forever to mesh it. Cropped balls get a pretty good likeness even though the prototype doesn't handle all of the cases correctly :O
I worked out some bugs in the math, and have it handling handling one of the corner cases correctly now. There's some missing convex hulls and some convex hulls that are only partially cropped, but those are just some edge cases that should be straight forward to handle.
I'm really pleased with how this is turning out! This is doing a nice job with hard edges, round convex features, concave features, pointy bits, and so on. And it does this without needing to first generate a very dense mesh
Also it seems to be pretty quick so far? I think I could get a pretty good likeness out of this with a fairly coarse sampling grid, and then gradually refine it via a cluster hierarchy thing
@aeva to me it just looks like a complication with no real benefit over dual marching cubes + QEF. the real issue is undersampling, no lattice based solution can fix that. but that's just my inner perfectionist talking. if you dig the style, go for it :)
@aeva I have no idea how this works and only a vague intuition of why it's better than cubes, but it looks amazing
maybe you could have a second layer of smaller balls to fill up the space the big ones can't?
@aeva VP trees = binary tree where at each level, you partition the universe into d(x,P) <= T and d(x,P) > T for some distance metric d and some point P and threshold T stored on the node
Add comment