0
\$\begingroup\$

I'm working on Voxel editing software, and I need to have the ability to group voxels into objects.

As for simple editing, I'm using the following data structure:

  1. Chunk - represents a fixed 3d grid of bytes (32x32x32) where each byte represents a Voxel ID that is mapped to a color (via the 1d texture of colors represented by a palette). Later I generate a culled 3d mesh from a chunk.
  2. World - represents a fixed 3d grid of Chunks (8x8x8) where each chunk is a dataset described before.

So the overall voxels count is 256x256x256 (Chunk size X World grid size)

Currently, it works pretty fast. Each chunk is updated quickly, the meshes are also rebuilt quite quickly. And overall memory usage is quite small -> 256^3 bytes = 16.5MB

But there is a task to group voxels into objects to be able to export these groups as separate objects. (Also to delete/edit groups)

The only method that comes to my mind is this: Instead of using 1 byte to describe the Voxel ID use 2 bytes: 1 for material id, and 1 for object id.

As for memory usage, this method just doubles it, so I'll need 33MB of RAM only. That's pretty good.

But from another side, I still do not understand how can I rebuild mesh pretty fast in this case. There are 16.5M of voxels in total.

Before I just generated a mesh for each chunk that was updated. (e.g. rebuilt 1 chunk per mouse click) But with a new method, I need to look up all the chunks to find voxels that are used by an object and generate a mesh using all voxels I found. So that breaks all the chunk system performance.

I do not think that this is a good solution. (Or maybe I'm missing something)

So the question is: are there any working algorithms to group voxels into objects? If yes, then what is the best one?

Or, at least, is there any way to fix my algorithm?

P.S. MagicaVoxel has groups (Outline), but I haven't found any information about how it's implemented internally.

Update:

This problem was solved in the following way:

Introduce View and Edit modes.

View - allows viewing all objects as triangulated meshes (1 Mesh per object). For each object in the scene, create a Voxel 3D Grid.

Edit - allows editing objects as a grid of voxels, where an object is rendered as a group of triangulated chunks. (Up to 512 meshes per object)

For each object in the scene, we create a 256^3 grid of voxels, where each voxel is described by a 1 byte (Material -> [1, 255], the max memory usage per object = 256^3 bytes = 16Mb)

At the same time, you can edit only a single object.

When you go from the Edit mode to View mode, the 3D grid of chunks is saved to disk. In the opposite situation (going from View to Edit mode), the 3D grid is loaded from the disk.

On the screen, any object at any time, rendered as a triangulated mesh (Greedy meshing)

Pros:

  • 3D grid can be replaced with Sparse Voxel Octree later.
  • Objects can be moved which allows placing objects close to each other, creating seamless meshes in size greater than 256^3 voxels.
  • Good memory usage, the Edited object takes 16Mb in RAM, and other objects (which are in view mode) took memory === memory that polygons (normals, etc.) took.
  • Objects can change Visibility pretty easily.
  • Objects can do bool operations between each other pretty well, such as subtraction, addition, etc. (Using their internal 3D grids)

Cons:

  • Too many meshes per Edited object (8^3 chunks = 512 Meshes in a case if all the chunks are filled)
  • Should save each object separately on the disk.
  • Freeze between changing modes (During saving/loading chunks to/from the disk)
  • Freeze when going from Edit to View (During combining all the chunks into a single mesh, to reduce meshes from 8^3 to 1)
\$\endgroup\$
4
  • \$\begingroup\$ Would it be reasonable to still use chunks for editing, and only on export would you combine chunk meshes based on object affiliations? \$\endgroup\$
    – DMGregory
    Mar 23, 2023 at 12:33
  • \$\begingroup\$ @DMGregory there are a few more features, like object highlighting, show/hide, and delete (+create as undo of delete). Part of it probably can be done runtime via some smart shader. Another part might be done runtime too. (I'm not sure) I probably should analyze your answer a bit more. (But it makes sense) \$\endgroup\$ Mar 23, 2023 at 12:52
  • \$\begingroup\$ I can't claim that to be an answer. Just a question to try to get a clearer idea of your requirements and constraints. Is it necessary for these operations for the members of an object to be a single mesh, or could an "object" be a list of meshes spread across several chunks while editing? \$\endgroup\$
    – DMGregory
    Mar 23, 2023 at 12:54
  • \$\begingroup\$ It can be spread as well, for example, show/hide can be done via showing/hiding a group of meshes. The same as highlighting (I can render a mask using a group of meshes and then outline it) Using several chunks is much better rather than rendering each voxel separately. So having multiple meshes per object is not a constraint. I was thinking about having objects with self-chunks, but then RAM usage grows to unlimited size. \$\endgroup\$ Mar 23, 2023 at 13:19

0

You must log in to answer this question.

Browse other questions tagged .