This is a niche problem for me that is not important, so I thought I'd see what Tech Talk had to say.

I have data that describes voxels in a 16x16x16 region. Just think of them as point values. Don't worry what they are or what other properties they have. I promise that doesn't matter.

I need to convert this data into another format, one that expresses cuboids within the regions by their opposite vertices.

My first implementation naively translates the voxels into cuboids of a single unit in length, width, and breadth. The problem is that the resulting shapes are too complex to render. I'm limited to an arbitrary maximum number of cuboids. What the maximum is doesn't matter. It's fewer than 16 cubed. If you really want a number, call it 24.

So what I need is way to merge contiguous voxels into a coordinate pair describing a cuboid whose volume contains them. It doesn't have to be fancy. Don't worry about clipping. All I care about is getting a decent first pass.

Now for the real restrictions: I need to implement this in Lua on a computer that was slow when The Matrix was in theaters. I don't know or care about 3D graphics, and I can't use any hardware acceleration or special drivers or anything like that.

4/28/2016 12:02:23 AM

So the cuboids need to only encompass voxels (and not "empty" space)?

And the cuboids can overlap, as long as it doesn't cover empty space?

Does the computer support virtual memory? Is there a meaningful storage/ram limitation?

My gut instinct is to treat 1 dimension as a binary word, and use bitwise operations and masks to find continuous segments, but i'm not really sure how performant this really is.

[Edited on April 28, 2016 at 12:49 AM. Reason : ]

4/28/2016 12:34:25 AM

Right, not empty space, and I don't care whether the cuboids overlap as long as the overall complexity goes down.

The computer can fake virtual memory if it needs to by writing work to disk temporarily. Assume one megabyte of disk storage and let's say four megabytes of RAM.

I'm not really concerned with performance. If it takes the program an hour to come up with something, I'll be a little annoyed, but it won't be a big deal.

4/28/2016 6:40:50 AM

if you've already got the distinct shapes determined, couldn't you just iterate over those and perform a best-fit check for cuboids that'd fit in them?

or i guess recursively scan over the entire area finding the greatest cubic volume each time before excluding it

[Edited on April 28, 2016 at 8:53 AM. Reason : minecraft]

4/28/2016 8:51:31 AM

I don't have distinct shapes. I have point values.

4/28/2016 8:56:22 AM

ah that's what i thought "My first implementation naively translates the voxels into cuboids of a single unit in length, width, and breadth" meant

well then i guess i'd do that second thing i said

4/28/2016 9:54:53 AM

I mean you aren't wrong, I do technically have shapes in my implementation. I'm just not interested in building off of that. I ought to be able to go straight from the voxels to the cuboids, and in any case, you're really just suggesting I solve my problem by--in so many words--solving the same problem expressed differently, which is not necessarily a bad suggestion in general but is definitely a bad suggestion in this case since, you know, expressing it differently didn't actually reveal any useful abstractions or frame the problem in any way that made me think differently about it.

* You Tried! *

[Edited on April 28, 2016 at 10:17 AM. Reason : I know that was mean, but if you find yourself typing "could you just" then....]

4/28/2016 10:14:04 AM

i'm not doing your webassign for you, champ

turn your point values into 16³ boolean array

iterate through 16x16x16, 16x16x15, 16x15x15, [...], 2x2x2, 2x2x1, 2x1x1, 1x1x1 and see if all point values are true within that volume. as the area gets smaller make sure to shift it around so you check all voxels (one check for 16x16x16, 2 checks for 16x16x15, 4 for 16x15x15 and so on).

you found a full volume full of sweet, sweet 1s? sweet! store a corner point and its HxWXD and and make sure that doesn't intersect with future volumes as you go forward

it's slow as balls but should work. it's likely not the most efficient cuboid count either but will probably be good enough. or if it's not it'll crash. what'd be the worst case scenario - (16^3)/2 roughly?

[Edited on April 28, 2016 at 10:42 AM. Reason : shenanigoats]

4/28/2016 10:40:22 AM

Since you're not looking at the minimum cuboids, then ignoring the depth and finding flat slabs for each layer is easy. You could then do a second pass and just see if any adjacent layers have the same slabs.

This should be very fast, and easy to implement. You could run it 6 times on the same 16 x16x16 array and pick the set that results on the smallest number of cuboids too.

4/28/2016 12:25:44 PM

i got bored and wrote this out in python. seems to work

4/28/2016 2:01:32 PM

I kinda like your idea, moron, especially since I expect a lot of symmetry. Merging flat cuboids between layers after that should be pretty straightforward.

It wouldn't be the end of the world if I wound up hand-tuning some results, so I'm thinking about breaking each plane into 16 4x4 grids. Then, I'll treat each position as a bit and interpret the voxels within the grid as representing a 16-bit number. If I look for 3x3 squares within those smaller grids, there are only four valid configurations, which means only four valid 16-bit values. I can emit relative coordinates for the matching grids (and any grid just filled with voxels) and get simplified shapes that way.

Grids with equivalent values that are adjacent in height can just have their shapes flattened together, so assuming I get a high density of voxels, this should be close enough (and performant enough) to work with. Neat!

BigMan157: Paste your Python implementation.

[Edited on April 28, 2016 at 2:13 PM. Reason : ///]

4/28/2016 2:12:43 PM

import pprint
import random

n = 16
#randomly fill it
voxelBox = [[[random.getrandbits(1) for k in range(n)] for j in range(n)] for i in range(n)]
voxelBoxPristine = voxelBox
cuboids = []

#pprint.pprint(voxelBox)
#print('\n')

def checkPattern(pattern):
	global n, voxelBox

	for r in range(3):
		#print(pattern)
		p_x = pattern[0]
		p_y = pattern[1]
		p_z = pattern[2]

		#shifts the shape in the n-array
		for x_start in range(n-p_x+1):
			for y_start in range(n-p_y+1):
				for z_start in range(n-p_z+1):
					#checks the individual points
					voluminous = 1
					for x_check in range(x_start, x_start+p_x):
						if voluminous:
							for y_check in range(y_start, y_start+p_y):
								if voluminous:
									for z_check in range(z_start, z_start+p_z):
										if not voxelBox[x_check][y_check][z_check]:
											voluminous = 0
											break
								else:
									break
						else:
							break
					if(voluminous):
						#store the start point of the volume with its X,Y,Z length
						found_cuboid = [x_start, y_start, z_start, p_x, p_y, p_z]
						cuboids.append(found_cuboid)
						#zero out the found volume so future checks skip it
						for x_check in range(x_start, x_start+p_x):
							for y_check in range(y_start, y_start+p_y):
								for z_check in range(z_start, z_start+p_z):
									voxelBox[x_check][y_check][z_check] = 0
						#print(found_cuboid)
						#pprint.pprint(voxelBox)
						#print('\n')
		#rotate the pattern
		if p_x==p_y and p_y==p_z:
			break
		pattern = pattern[1:] + pattern[:1]
	return


#generate patterns and check them
pattern = [n] * 3
for i in range(n,1,-1):
	pattern = [i] * 3
	checkPattern(pattern)
	pattern[2]-=1
	checkPattern(pattern)
	pattern[1]-=1
	checkPattern(pattern)
pattern = [1] * 3
checkPattern(pattern)

#biggest print out on bottom
cuboids.reverse()
pprint.pprint(cuboids)
print('Found %d cuboids' % len(cuboids))

4/28/2016 2:23:53 PM

Quote :

"It wouldn't be the end of the world if I wound up hand-tuning some results, so I'm thinking about breaking each plane into 16 4x4 grids. Then, I'll treat each position as a bit and interpret the voxels within the grid as representing a 16-bit number. If I look for 3x3 squares within those smaller grids, there are only four valid configurations, which means only four valid 16-bit values. I can emit relative coordinates for the matching grids (and any grid just filled with voxels) and get simplified shapes that way. "

Or treat each line as a bit mask, store each (blanks space)->(voxel) pattern as a vertex of the square, mask out the bits in this line, bitwise OR it with the subsequent line until it is a different value (or all 0, depending on what shape cuboids you prefer), then mark the other corner as the other vertex, set all the found values to 0, then repeat.

4/28/2016 3:08:51 PM