# Setting up an “Oct-Tree”

Instead of spam the same hard question like my previous one that Is difficult to get a minimum verifiable example for, I have decided to rework my path-finding and I can fix a lot of my issues with an oct-tree, not a true one but rather just subdividing my world into 8 or however many i specific in the function as this is all thats needed.

I already know what i need to do the stage after this, but I'm a not sure the best way to approach the subdivision so i get the right vector points of the subdivided cubes.

div = the number of cubes I want to create.

If I already have my 8 points,

    worldspace(Vector3 origind, float sized)
{
//  face1
ca = Vector3{ origin.GetX() + sized,origin.GetY() + sized, origin.GetZ() - sized };
cb = Vector3{ origin.GetX() + sized,origin.GetY() - sized, origin.GetZ() - sized };
//-----------------------------------------------------------------------------
cc = Vector3{ origin.GetX() - sized,origin.GetY() - sized, origin.GetZ() - sized };
cd = Vector3{ origin.GetX() - sized,origin.GetY() + sized, origin.GetZ() - sized };
//  face 2
ce = Vector3{ origin.GetX() + sized,origin.GetY() + sized, origin.GetZ() + sized };
cf = Vector3{ origin.GetX() + sized,origin.GetY() - sized, origin.GetZ() + sized };
//-----------------------------------------------------------------------------
cg = Vector3{ origin.GetX() - sized,origin.GetY() - sized, origin.GetZ() + sized };
ch = Vector3{ origin.GetX() - sized,origin.GetY() + sized, origin.GetZ() + sized };
};
~worldspace();


I can define my worldspace as worldspace(0,0,0,25) so thats a cube of 25 units, but then I want to divide it in the most efficient way into 8 = cubes lets say or so and make them into a vector.

I'd like the function to be able to specify how many subdivisions i want, I don't want a dynamic one, so I think. So I'm thinking I could do something along the lines of

semi pseudocode

createoct(div)
int divisions = div
for (int i = 1; i =< div; i++)
{
dist of ca to cb / div ?
store the new point
do the same for the other points ?
}


Am I going about this the right way ? what would be the best way to calculate the subdivisions and store their 4 seperate points as one object ? perhaps a new class ?

• What does div represent? The number of divisions per side, or the number of smaller cubes you want it to end up with? – user1118321 Aug 15 '17 at 3:14
• @user1118321 the number of smaller cubes I want to end up with. – RNewell122 Aug 15 '17 at 17:34

If you want div to represent the number of cubes then you need to ensure that div is a cube (as in, is an integer to the 3rd power). So 1, 8, 27, etc. Given that, you could do the following:

#include <stdlib.h>
#include <cmath>
#include <assert.h>
#include <vector>

struct Vector3 {
float   x;
float   y;
float   z;
};

struct Cube {
Vector3 origin;
float   sideLen;
};

void subdivideCube(const struct Cube& cube, const int numCubes, std::vector<struct Cube>& newCubes)
{
// Ensure that the input numCubes has an integer cube root
assert(std::cbrt(static_cast<float>(numCubes)) == floor(std::cbrt(static_cast<float>(numCubes))));

float numDivisionsPerSide   = std::cbrt(static_cast<float>(numCubes));
float divisionLen           = cube.sideLen / numDivisionsPerSide;

for (float x = cube.origin.x; x < cube.origin.x + cube.sideLen; x += divisionLen)
{
for (float y = cube.origin.y; y < cube.origin.y + cube.sideLen; y += divisionLen)
{
for (float z = cube.origin.z; z < cube.origin.z + cube.sideLen; z += divisionLen)
{
struct Cube newCube = { { x, y, z }, divisionLen };
newCubes.push_back(newCube);
}
}
}
}

int main()
{
Vector3 origin  = {10.0, 10.0, 10.0};
float   size    = 1000.0;
Cube    volume  = { origin, size };
int     divs    = 8;
std::vector<struct Cube>   newCubes;
subdivideCube(volume, divs, newCubes);
}