Octree simplification by QEFs


Dual contouring uses a quadratic-error-function (QEF) to position a vertex inside each octree-node (cube) where the implicit distance-field that defines our geometry changes sign. The vertex is positioned so that the QEF is minimized. This allows for an octree simplification strategy where we combine all the QEFs of the eight child-nodes, and see if we can replace the eight vertices they define with with a single vertex one level up in the octree.

This image shows the dual contouring code run on the same input data with various levels of simplification. Even a small threshold value of 0.001 reduces the number of triangles more than ten-fold. Too large a threshold produces jagged edges. Note that dual contouring of the original dataset where each leaf-node is at the same (maximal) depth of the tree produces only quad polygon output. When we simplify and collapse some nodes to non-maximal depth the algorithm also produces triangles - where a collapsed node is adjacent to nodes deeper in the tree.