After a long break I begin to implement 2D dual contouring today. This is the result I achieved:

2D dual contouring of heart function

My implementation is based on Dual Contouring of Hermite Data and Dual Contouring: “The Secret Sauce”. The source code of this tool can be found here.

You can edit the Function parameter to contour other kinds of geometry. The input of Function parameter should be a 2D distance field function. Its zero isopleth will be contoured. You may find this page useful.

There are also some details worth noting. I use numpy.linalg.pinv to solve linear system. According to numpy’s document, pinv computes the Moore-Penrose pseudo-inverse of a matrix. Hence when we are given a linear system which is rank deficient, the solution is minimized to the origin. This may lead to a vertex outside its bounding square. In this implementation I use the mass point translation approach to resolve this problem.

This tool is tested on some simple cases and most of them works well. But there is a problem when the isopleth hits the grid point. In this case the common intersection point will be used by four adjacent squares and then have four vertices generated. This makes the shape’s topology incorrect. A slight displacement may alleviate this problem. But I am looking for a more robust solution.