<p>So I've been all around the houses on this looking for an answer. In the end I found a combination of techniques worked quite well:</p>
<ol>
<li><p>To take advantage of all of the 'empty space', the concept of 'surface tracking' from the Octree Decimation paper useful - you can follow the surface from cell to cell and ignore all of the cells in the middle.</p>
</li>
<li><p>The main advantage of generating the voxels ourselves is what we know two vital pieces of information: firstly, the exact position of each vertex within the cells on the 'front' surface; secondly, the 'orientation' of the mesh in each region and which way that 'front' is to be found.</p>
</li>
</ol>
<p>Putting all the pieces together I came up with this <a href="https://github.com/andygeers/DualMarchingCuboids" rel="nofollow noreferrer">Dual Marching Cuboids</a> algorithm, that has pretty good results in very reasonable time.</p>

CC BY-SA 4.0
2020-09-25T22:05:24.093Z
2020-09-25T22:05:24.093Z
andygeers
<p>I'm working on an app that lets users construct a 3D house, with the ultimate goal of it being 3D printable. I use various materials in the form of a height map constructed from an image, like this brick texture:</p>
<p><a href="https://i.sstatic.net/n6D9T.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/n6D9T.png" alt="enter image description here" /></a></p>
<p>I map the brightness of each pixel to a height, like so:</p>
<p><a href="https://i.sstatic.net/41Sk2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/41Sk2.png" alt="enter image description here" /></a></p>
<p>But when you start combining wall panels side by side and at different angles, it can quickly get messy and you can end up with a self-intersecting mesh, not to mention many more polygons than are really necessary, all of which contribute to something which the 3D Printer slicer can't cope with. It <em>looks</em> like this but the geometry isn't clean enough to print it:</p>
<p><a href="https://i.sstatic.net/u4Eg1.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/u4Eg1.jpg" alt="enter image description here" /></a></p>
<p>Now, currently everything in the app itself works directly with polygons. Since all of this ultimately is generated from grid-like data (the source images) it seems to me that some kind of voxel-based approach would be very suitable, and could potentially yield much better quality results. I have tested the approach of populating a grid directly from the source images, and that bit can be done very efficiently. But I'm having a hard time finding the right algorithm to then turn that grid data back into polygons ready for 3D printing.</p>
<p>Most algorithms for turning voxel data into a polygon isosurface assume two things, as far as I can tell:</p>
<ol>
<li>That you have no prior knowledge of the underlying geometry</li>
<li>That the geometry is a scalar field, rather than a &quot;boolean&quot; grid where the grid lines genuinely do correspond to the final geometry. There could be fine scaled details that fall between the grid lines.</li>
</ol>
<p>Whereas in my case:</p>
<ol>
<li>I have huge empty patches inside the building, but I can easily ignore those because I have a list of bounding boxes of where each wall panel exists</li>
<li>I would like to take advantage of the fact that my data actually <em>is</em> gridlike in nature. Note that I can have 'diagonals' - this simple brick texture shown here is probably a little too simplistic, e.g. some roof tile textures use a lot more in-between heights:</li>
</ol>
<p><a href="https://i.sstatic.net/CJFJH.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/CJFJH.png" alt="enter image description here" /></a></p>
<p>Obviously something as simple as marching cubes could be adapted to take advantage of point 1 easily enough (just skip over sections of the grid which aren't contained within any of my bounding boxes) but I feel like marching cubes will yield WAY more polygons than necessary.</p>
<p>Can anybody recommend any specific algorithms that might suit this scenario (where we have prior knowledge about the underlying geometry) or give me some search terms that I can use to research? I've been searching algorithms for generating isosurfaces, but my instinct tells me that what I'm working with here is actually subtly different because of the grid-like nature of the problem - e.g. are these even really &quot;voxels&quot; at all?</p>

<computational-geometry>
Efficiently generating mesh for self-generated voxel grid
andygeers
# Efficiently generating mesh for self-generated voxel grid

(Asked by: username_0 on 2020-07-15)

I'm working on an app that lets users construct a 3D house, with the ultimate goal of it being 3D printable. I use various materials in the form of a height map constructed from an image, like this brick texture:

[![enter image description here](https://i.sstatic.net/n6D9T.png)](https://i.sstatic.net/n6D9T.png)

I map the brightness of each pixel to a height, like so:

[![enter image description here](https://i.sstatic.net/41Sk2.png)](https://i.sstatic.net/41Sk2.png)

But when you start combining wall panels side by side and at different angles, it can quickly get messy and you can end up with a self-intersecting mesh, not to mention many more polygons than are really necessary, all of which contribute to something which the 3D Printer slicer can't cope with. It *looks* like this but the geometry isn't clean enough to print it:

[![enter image description here](https://i.sstatic.net/u4Eg1.jpg)](https://i.sstatic.net/u4Eg1.jpg)

Now, currently everything in the app itself works directly with polygons. Since all of this ultimately is generated from grid-like data (the source images) it seems to me that some kind of voxel-based approach would be very suitable, and could potentially yield much better quality results. I have tested the approach of populating a grid directly from the source images, and that bit can be done very efficiently. But I'm having a hard time finding the right algorithm to then turn that grid data back into polygons ready for 3D printing.

Most algorithms for turning voxel data into a polygon isosurface assume two things, as far as I can tell:

1. That you have no prior knowledge of the underlying geometry
2. That the geometry is a scalar field, rather than a "boolean" grid where the grid lines genuinely do correspond to the final geometry. There could be fine scaled details that fall between the grid lines.

Whereas in my case:

1. I have huge empty patches inside the building, but I can easily ignore those because I have a list of bounding boxes of where each wall panel exists
2. I would like to take advantage of the fact that my data actually *is* gridlike in nature. Note that I can have 'diagonals' - this simple brick texture shown here is probably a little too simplistic, e.g. some roof tile textures use a lot more in-between heights:

[![enter image description here](https://i.sstatic.net/CJFJH.png)](https://i.sstatic.net/CJFJH.png)

Obviously something as simple as marching cubes could be adapted to take advantage of point 1 easily enough (just skip over sections of the grid which aren't contained within any of my bounding boxes) but I feel like marching cubes will yield WAY more polygons than necessary.

Can anybody recommend any specific algorithms that might suit this scenario (where we have prior knowledge about the underlying geometry) or give me some search terms that I can use to research? I've been searching algorithms for generating isosurfaces, but my instinct tells me that what I'm working with here is actually subtly different because of the grid-like nature of the problem - e.g. are these even really "voxels" at all?

**Tags:** computational-geometry


---

## 1 answers

### Answer by username_0 on 2020-09-25. Score: 0

So I've been all around the houses on this looking for an answer. In the end I found a combination of techniques worked quite well:

1. To take advantage of all of the 'empty space', the concept of 'surface tracking' from the Octree Decimation paper useful - you can follow the surface from cell to cell and ignore all of the cells in the middle.
2. The main advantage of generating the voxels ourselves is what we know two vital pieces of information: firstly, the exact position of each vertex within the cells on the 'front' surface; secondly, the 'orientation' of the mesh in each region and which way that 'front' is to be found.

Putting all the pieces together I came up with this [Dual Marching Cuboids](https://github.com/username_0/DualMarchingCuboids) algorithm, that has pretty good results in very reasonable time.


---

