2
\$\begingroup\$

In the marching squares/cubes algorithm, how is it decided if a node in the quadtree/octree will be divided further (into 2^dimension nodes)?

I read about this heuristic that uses a trilinear interpolation to decide if an octree needs to be divided further for not.

It is not clear what the line represents and against what it's tested.

\$\endgroup\$
4
\$\begingroup\$

Usually the metric used is node overhead. You can take it to the pathological case (if you can subdivide you do), but at some point the extra effort stops gaining you better results. For normal spatial partitioning octrees, that's processing overhead and memory overhead. Marching Cubes is an odd one, because the subdivision is gaining you more accuracy. The finer grained the nodes, the smaller the polygons generated, and the closer the surface generated is to the actual surface shape. But the same principles still apply - you're choosing to subdivide if the smaller nodes will get you substantially better results.

The heuristic is basically just a decision on how much better things will be if you subdivide. The threshold is just a number below which you consider the improvement in results to be trivial / insufficient to warrant the extra cost.

In marching cubes, the items (polygons) don't exist when the partitioning tree is being generated. Only the density and surface threshold is available. The triangles representing that surface are still to be generated, but the assumption is that lumpier parts of the surface will need more triangles to represent them. So the metric being used here is "how lumpy is the surface within this node". If it's flat/planar, it doesn't need subdivided, because the triangles in that node will be large and relatively flat.

I can't follow the maths exactly in your linked paper but I presume the logic is the same as any error metric. For each node you can calculate an error - if you stopped subdividing at that node and just generated the surface polygons at that resolution, how bad would the result be (in terms of error difference against the real surface). You'd be calculating 'error improvement' from subdividing, where the improvement in the error is: 'total error for all the subdivided nodes' - 'error for the parent node'

Reading further into the heuristic, it seems like they are comparing the interpolated values between the 8 corners with the actual values at the subdivided node corners. Not sure why they're interpolating trilinearly. But this seems to me like a good way of estimating lumpiness. If the surface was relatively flat, the surface values at the midpoints used for the sub-divided nodes would be very close to the values you'd get if you just interpolated from the corners of the parent nodes. If the surface was very lumpy, the actual and interpolated mid-points would be way off. How far off can be calculated - and that looks like what that graph is. v represents the distance from the estimated surface to the actual surface at that point. Higher values of v mean that the actual surface has diverged a lot from the estimated surface that you'd get if you didn't subdivide. That gives you an error metric that you can use to threshold whether or not to subdivide.

If it were that naive though, it would fall down in the case where sinusoidal variations in the surface neatly aligned with node boundaries, and happened to result in the mid-point being accurate (imagine a case where in the left side of the node, the surface bulges outwards, but on the right side the surface bulges inwards by the same amount - at the midpoint, the surface is at the same position as it would be if it were flat). I presume that's why the tangent of the surface is also considered - it's much harder for the surface to be in the right place with the right tangent and not also be flat.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.