Download

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[3];
};

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[0], t.v[1]);
	c2 = cross(t.v[1], t.v[2]);
	c3 = cross(t.v[0], t.v[2]);
	
	// 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[0] = {4.99f, 2.09f, -2.75f};
	t.v[1] = {-4.48f, 3.07f, 1.08f};
	t.v[2] = {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.