Setting up an "Oct-Tree"

Question

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
– user1118321, Commented Aug 15, 2017 at 3:14
@user1118321 the number of smaller cubes I want to end up with. — RNewell122
– RNewell122, Commented Aug 15, 2017 at 17:34

user1118321 · Accepted Answer · 2017-08-16 03:38:09Z

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);
}

Stack Exchange Network

Setting up an "Oct-Tree"

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Setting up an "Oct-Tree"

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions