AnswerBun.com

Efficiently generating mesh for self-generated voxel grid

Computer Graphics Asked by andygeers on August 27, 2021

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

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

enter image description here

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

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

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?

One Answer

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 algorithm, that has pretty good results in very reasonable time.

Answered by andygeers on August 27, 2021

Add your own answers!

Related Questions

Why does opengl use 4d matrices for everything?

3  Asked on August 27, 2021 by yoris

 

Defining “inside” and “outside” of a 3D space

2  Asked on August 27, 2021 by avatrin

 

Which perspective projection matrix to use

1  Asked on August 27, 2021 by nixcc

   

How do you apply a normal map to a 3d mesh?

1  Asked on August 27, 2021 by calvin-godfrey

   

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir