4
\$\begingroup\$

I have a bunch of voxel having an int value inside a 16^3 grid. I want to merge individual voxels with the same int value together in order to create the least possible amount of boxes the fastest way possible.

Here is my algorithm (kotlin) :


fun convert (grid: VoxelGrid): List<Box> {
    val dim = grid.dimension
    val boxes = mutableListOf<Box>()

    for (width in dim - 1 downTo 1) {
        for (height in dim - 1 downTo 1) {
            for (depth in dim - 1 downTo 1) {
                val dims = Vec3(width, height, depth)
                for (x in 0 until (dim - width)) {
                    for (y in 0 until (dim - height)) {
                        for (z in 0 until (dim - depth)) {
                            val min = Vec3(x, y, z)
                            val box = Box(min, min + (dims))

                            if (!contains(boxes, box)) {

                                val voxels = box.voxels()
                                val first = voxels[0]
                                val value = grid[first.x, first.y, first.z]
                                if (value != 0 && voxels.all {
                                            grid[it.x, it.y, it.z] == value
                                        }) {
                                    boxes.add(box)
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    return boxes
}

private fun contains(boxes: MutableList<Box>, other: Box): Boolean {
    for (existing in boxes) {
        if (existing.intersects(other)) {
            return true
        }
    }

    return false
}

Here is a link to the helper classes

This works, but for a 16^3 grid (the last test case) it takes around 8s to complete which is way too long.

In order to optimize, I think that before calling convert(), I could group every voxel by their int value, then compute the AABB for each group and only call the algorithm for each AABB. This could work pretty well but for values that are spread out around the original grid.

Is there any other way to optimize this?

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Try to determine the complexity of the algorithms you are implementing. The code you wrote above has a complexity of O(N⁹), where N is equal to grid.dimension. This is because you have 6 nested for loops, and then voxels.all{} which itself also has to loop over all three dimensions of the box voxels.

Grouping voxels by their int value is a good idea. You correctly worry about the case of voxels with the same value being spread out. The solution to that is to divide the box into connected voxels with the same int value. For example, if you had only one dimension, then if you have the values [0, 1, 2, 2, 1, 2], then you would divide this into 5 groups: [0], [1], [2, 2], [1] and [2]. It should be possible to do this in O(N³) time.

Now that you have a set of smaller shapes, the function that decomposes those shapes into boxes should run a lot faster. The question is now whether you want to have that function as fast as possible, or as accurate as possible. The function as you wrote does not necessarily result in the least amount of boxes. Apart from the fact that it doesn't actually try out boxes in a strict order from largest to smallest, even trying the largest boxes first won't necessarily result in the least amount of boxes being produced. Take for example this 2D array:

1 0 0 1
1 1 1 1
1 0 0 1

The voxels with value 1 form a H-shape. If you remove the largest possible box, you end up with:

1 0 0 1
x x x x
1 0 0 1

Now you are left with 4 1x1 boxes, so in total this will result in 5 boxes for the H-shape. If instead you would start by taking out the left and right side, you are left with the middle bar, resulting in just 3 boxes. Finding the solution with the least amount of boxes is actually an NP-complete problem, and an algorithm that would produce that solution would take even longer to run that yours. Given that your algorithm already does not give acceptable performance, you should instead focus on implementing the fastest algorithm that produces acceptable results.

The common approach is to start by finding strips of adjacent voxels in the x-direction. Then try to find adjacent strips with the same size and x-position in the y-direction, and merge them into squares. Finally do the same in the z-direction and merge adjacent squares into boxes. This should be O(N³) as well. If you know that some shapes are more common than others, you could tweak this algorithm to reduce the number of boxes.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you for your detailed answer. I didn't do any studies, so the O(N) notation and all the complexity theory seems quite O(N^N) to me. " Apart from the fact that it doesn't actually try out boxes in a strict order from largest to smallest" how so ? I am iterating in the reverse order to test each boxes dimensions, am I missing something ? \$\endgroup\$
    – Vinz243
    Aug 6, 2019 at 7:22
  • \$\begingroup\$ So I should do a graph where each node represents a voxel and each vertex a connection between two voxels of the same value. Your strip algorithm seems interesting, although it really comes down to the actual shape of the voxels. Anyway, I was thinking about using several algorithm optimized for a specific shape and then try the slow generic approach (original algorithm) if the other results do not meet a threshold \$\endgroup\$
    – Vinz243
    Aug 6, 2019 at 7:25
  • \$\begingroup\$ About the order of largest to smallest: suppose dim is 10, then your outer three loops will try out a box of size (9, 9, 1) before one of size (9, 8, 9). \$\endgroup\$
    – G. Sliepen
    Aug 6, 2019 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.