I'm working on a CPU voxel raytracer in Python. With the amount of costly calculations involved everything must be as efficient as possible especially storing and fetching point data in space. I started by storing 2D and 3D data in dictionaries indexed by string positions, eg: data["4,16"] == "solid". Since converting positions to and from string is costly while dictionaries are slower than lists, I'm in the process of moving to the more efficient system of storing everything in an ordered array and using index to determine which position an entry refers to. I already have this working successfully in 2D:
# Returns x, y position from index i based on width
def index_vec2(i: int, width: int):
return math.floor(i % width), math.floor(i / width)
Say you have a 4x4 square: If the array contains 16 entries, you easily know index 3 represents position x == 3, y == 0 then index 4 is position x == 0, y == 1. The function only needs the rectangle width to deduce this, height isn't necessary as there's no need to ensure the whole area is filled or extra entries don't spill out.
I'm trying to expand the same concept to 3D: You pass an i index to the function, in this case it needs to know both width and height to also calculate the depth. I'm struggling a bit as the math is more complex with a third axis... if I force my mind on it for a few more hours I might figure it out, but it also seems beneficial to have an answer here for others attempting the same thing.
# Returns x, y, z position from index i based on width and height
def index_vec3(i: int, width: int, height: int):
return math.floor(i % width), math.floor(i / width), math.floor(i / (width * height))
Currently this seems to report X and Z accurately, but I can't figure out what to do with Y. Initially it starts out well, increasing once per number of times i exceeds the width. Problem is that once we pass into the next Z layer, Y doesn't return back to 0 and start all over again, it keeps climbing all the way up to 15. Using for i in range(0, 64): index_vec3(i, 4, 4) (simulates iterating a 4x4x4 cube) I get the following result:
0,0,0
1,0,0
2,0,0
3,0,0
0,1,0
1,1,0
2,1,0
3,1,0
0,2,0
1,2,0
2,2,0
3,2,0
0,3,0
1,3,0
2,3,0
3,3,0
0,4,1
1,4,1
2,4,1
3,4,1
0,5,1
1,5,1
2,5,1
3,5,1
0,6,1
1,6,1
2,6,1
3,6,1
0,7,1
1,7,1
2,7,1
3,7,1
0,8,2
1,8,2
2,8,2
3,8,2
0,9,2
1,9,2
2,9,2
3,9,2
0,10,2
1,10,2
2,10,2
3,10,2
0,11,2
1,11,2
2,11,2
3,11,2
0,12,3
1,12,3
2,12,3
3,12,3
0,13,3
1,13,3
2,13,3
3,13,3
0,14,3
1,14,3
2,14,3
3,14,3
0,15,3
1,15,3
2,15,3
3,15,3
How can I improve my math and what's the simplest form to achieve a third axis? Only rule is no loops or increments which would cheat the optimization and negate performance benefits, each axis must be determined by transforming i with simple math based on the width and height. Hopefully it's simple enough to remain a one-liner but that's not mandatory.
def index_vec3(i,width,height):
z,remainder=divmod(i,width*height)
y,x=divmod(remainder, width)
return (x,y,z)