Octree simplification by QEFs

dual_contouring_QEF_simplification_2013sep14

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.

2 thoughts on “Octree simplification by QEFs”

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.