Octree with Marching Cubes

Update 3: this leads slowly towards a better and faster cutting simulation. Here's an example with Tux:

Update2: this looks slightly better now (a ball translated in a few steps towards the right). Image and c++ code by fellow OCLer Jiang from China.

Update: in a cutting simulation the stock is updated by removing voxels which fall inside the cutter. Here I'm trying it with a spherical shape positioned at (0,0), and then moved slightly along the X-axis. The white dots are corners of octree nodes, and the cyan triangles are produced by marching cubes. It works quite well, but on the border between the two cutter instances the distance-field is somehow wrong, and marching-cubes doesn't come up with the right triangles, leaving gaps instead.

Earlier I was building an octree volume-representation of a shape using a simple bool isInside(Point p) predicate function to determine which cubes are in and which are out. If instead a distance-function double distance(Point p) which is negative inside the volume, zero exactly on the surface, and positive outside, is used, then the Marching Cubes algorithm (this is a better explanation, someone should make the wikipedia page as good!) can be used to triangulate the octree. This leads to much more visually pleasing results at reasonable maximum tree-depths.

The same Hong-Tzong Yau of Taiwan who wrote a very reasonable drop-cutter paper in 2004 has more recently come out with a 2009 paper on cutting simulation using an octree and Marching Cubes.

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.