• News

• Industries

• Learning & Support

• Community

• Marketplace # Mesh partitioning

I’m trying to make a voxel style game using octrees, but I seem to be having trouble in regards to implementing a lookup algorithm an old contact of mine recommended I do.

Here’s a message about it he sent me last year:

I’ve struggled with finding vertex normals for the longest time, but I think I’ve gotten the hang of it now. I tried implementing a non-visual test programto try doing as he suggests, but there seems to be a problem after applying the normal:

``````
#include <cmath>
#include <iostream>

struct vertex
{
float x, y, z;

float length() const
{
return std::sqrt(x*x+y*y+z*z);
}
};

struct triangle
{
vertex v;
};

static vertex cross(vertex &v1, vertex &v2)
{
vertex val;
val.x = (v1.y*v2.z)-(v2.y*v1.z);
val.y = (v1.z*v2.x)-(v2.z*v1.x);
val.z = (v1.x*v2.y)-(v2.x*v1.y);
return val;
}

static vertex normal(triangle &t)
{
vertex c1, c2, c3, val;

// get cross products of all sides
c1 = cross(t.v, t.v);
c2 = cross(t.v, t.v);
c3 = cross(t.v, t.v);

// find average
val.x = (c1.x+c2.x+c3.x)/3;
val.y = (c1.y+c2.y+c3.y)/3;
val.z = (c1.z+c2.z+c3.z)/3;

// normalise the averages
float mag = val.length();
val.x /= mag;
val.y /= mag;
val.z /= mag;

return val;
}

static vertex*** partition(int size, triangle &t)
{
vertex ***grid = new vertex**[size];
vertex n = normal(t);

for (int x = 0; x < size; x++)
{
grid[x] = new vertex*[size];
for (int y = 0; y < size; y++)
grid[x][y] = new vertex[size];
}

for (int i = 0; i <= 2; i++)
{
vertex p = t.v*;
p.x += n.x;
p.y += n.y;
p.z += n.z;
p.x /= size;
p.y /= size;
p.z /= size;
unsigned fx = std::floor(p.x);
unsigned fy = std::floor(p.y);
unsigned fz = std::floor(p.z);
grid[fx][fy][fz] = t.v*;
std::cout << fx << ", " << fy << ", " << fz << " = "
<< t.v*.x << ", " << t.v*.y << ", " << t.v*.z << "
";
}

return grid;
}

int main()
{
triangle t;
t.v = {4.99f, 2.09f, -2.75f};
t.v = {-4.48f, 3.07f, 1.08f};
t.v = {1.07f, -1.62f, 2.06f};
vertex ***grid = partition(5, t);
//vertex n = normal(t);
//std::cout << n.x << ", " << n.y << ", " << n.z << "
";
return 0;
}

``````

If you try to run this, it likely segfaults because one of the indices being assigned is waaay out of bounds. The way I read how to find the vertex normal was to take the cross products of each side of a triangle face, average them, and then divide each axis by the magnitude (square root of x*x + y y + zz). I’m guessing I missed a step. Linear algebra is a bit difficult, so I tend to learn it better when I look at code instead of math formulae.