[SDK] Geosphere code and algorithm


#1

Hi,
I created a code for procedural creating Geosphere mesh. I know that there is a gsphere.cpp in sdk examples but I didn’t want to copy that, its also looks a bit complicated.

I read some articles about geospheres , for example I found this very informative:

My Geosphere subdivides each triangle into four new triangles every sundivision. That algorithm differs from the 3ds max, because the the 3ds max algorithm divides every trinagle into n segments - so it is possible to get more fined subdivisions, not only by 4.

My Geosphere code uses some STL containers like map and pair - that are very helpful but I think can lower the performance…

so any way… maybe you fond this code useful… don’t hesitate to optimize it or give ideas…

myGeosphere class declaration:

#include <map>

class myGeosphere
{
	public:
		void BuildGeosphere(Mesh& _mesh, int _iteration, BOOL _smooth);

		void BuildIcosahedron(Mesh& _mesh, BOOL _smooth);
		int GetSetMiddlePoint(std::map<std::pair<int, int>, int>& _mpm, Mesh& _old, Mesh& _new, int& _next, int _a, int _b);
};

definitions:

void myGeosphere::BuildGeosphere(Mesh& _mesh, int _it, BOOL _smooth)
{
	// using std for std::map and std::pair
	using namespace std;

// if iteration <= 1 return base icosahodron
if (_it <= 1) BuildIcosahedron(_mesh, _smooth);
else
{
	Mesh old_mesh, new_mesh;
	BuildIcosahedron(old_mesh, _smooth);
	map<pair<int, int>, int> middle_point_map;

	int old_verts_num, old_faces_num, new_faces_num, new_verts_num, new_faces_counter, next_index;

	int sm = 0;
	if (_smooth) sm = 1;

	// subdivide triangles
	for (int i = 0; i < _it - 1; i++)
	{
		middle_point_map.clear();

		old_verts_num = old_mesh.getNumVerts();
		old_faces_num = old_mesh.getNumFaces();

		new_faces_num = old_faces_num * 4;
		new_verts_num = new_faces_num / 2 + 2;
		new_faces_counter = 0;
		next_index = old_verts_num;

		new_mesh.setNumVerts(new_verts_num);
		new_mesh.setNumFaces(new_faces_num);
		new_mesh.setSmoothFlags(_smooth);

		memcpy(new_mesh.verts, old_mesh.verts, sizeof(Point3)*old_verts_num);
		memcpy(new_mesh.faces, old_mesh.faces, sizeof(Face)*old_faces_num);

		for (int f = 0; f < old_faces_num; f++)
		{
			int a = GetSetMiddlePoint(middle_point_map, old_mesh, new_mesh, next_index, old_mesh.faces[f].v[0], old_mesh.faces[f].v[1]);
			int b = GetSetMiddlePoint(middle_point_map, old_mesh, new_mesh, next_index, old_mesh.faces[f].v[1], old_mesh.faces[f].v[2]);
			int c = GetSetMiddlePoint(middle_point_map, old_mesh, new_mesh, next_index, old_mesh.faces[f].v[2], old_mesh.faces[f].v[0]);

			new_mesh.faces[new_faces_counter].setVerts(old_mesh.faces[f].v[0], a, c);
			new_mesh.faces[new_faces_counter].setEdgeVisFlags(1, 1, 1);
			new_mesh.faces[new_faces_counter].setSmGroup(sm);

			new_mesh.faces[new_faces_counter + 1].setVerts(old_mesh.faces[f].v[1], b, a);
			new_mesh.faces[new_faces_counter + 1].setEdgeVisFlags(1, 1, 1);
			new_mesh.faces[new_faces_counter + 1].setSmGroup(sm);

			new_mesh.faces[new_faces_counter + 2].setVerts(old_mesh.faces[f].v[2], c, b);
			new_mesh.faces[new_faces_counter + 2].setEdgeVisFlags(1, 1, 1);
			new_mesh.faces[new_faces_counter + 2].setSmGroup(sm);

			new_mesh.faces[new_faces_counter + 3].setVerts(a, b, c);
			new_mesh.faces[new_faces_counter + 3].setEdgeVisFlags(1, 1, 1);
			new_mesh.faces[new_faces_counter + 3].setSmGroup(sm);
			new_faces_counter += 4;
		}

		old_mesh = new_mesh;
	}
	_mesh = new_mesh;
}

Matrix3 mat(1);
_mesh.ApplyUVWMap(MAP_SPHERICAL, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0, mat);
}

void myGeosphere::BuildIcosahedron(Mesh& _mesh, BOOL _smooth)
{
	_mesh.setNumVerts(12);
	_mesh.setNumFaces(20);
	_mesh.setNumTVerts(0);
	_mesh.setNumTVFaces(0);
	_mesh.setSmoothFlags(_smooth);

int sm = 0;
if (_smooth) sm = 1;

_mesh.setVert(0, Point3(0.0, 0.0, 1.0));
_mesh.setVert(1, Point3(0.894427, 0.0, 0.447214));
_mesh.setVert(2, Point3(0.276393, 0.850651, 0.447214));
_mesh.setVert(3, Point3(-0.723607, 0.525731, 0.447214));
_mesh.setVert(4, Point3(-0.723607, -0.525731, 0.447214));
_mesh.setVert(5, Point3(0.276393, -0.850651, 0.447214));
_mesh.setVert(6, Point3(0.723607, 0.525731, -0.447214));
_mesh.setVert(7, Point3(-0.276393, 0.850651, -0.447214));
_mesh.setVert(8, Point3(-0.894427, 0.0, -0.447214));
_mesh.setVert(9, Point3(-0.276393, -0.850651, -0.447214));
_mesh.setVert(10, Point3(0.723607, -0.525731, -0.447214));
_mesh.setVert(11, Point3(0.0, 0.0, -1.0));
_mesh.faces[0].setVerts(0, 1, 2);
_mesh.faces[0].setEdgeVisFlags(1, 1, 1);
_mesh.faces[0].setSmGroup(sm);
_mesh.faces[1].setVerts(0, 2, 3);
_mesh.faces[1].setEdgeVisFlags(1, 1, 1);
_mesh.faces[1].setSmGroup(sm);
_mesh.faces[2].setVerts(0, 3, 4);
_mesh.faces[2].setEdgeVisFlags(1, 1, 1);
_mesh.faces[2].setSmGroup(sm);
_mesh.faces[3].setVerts(0, 4, 5);
_mesh.faces[3].setEdgeVisFlags(1, 1, 1);
_mesh.faces[3].setSmGroup(sm);
_mesh.faces[4].setVerts(0, 5, 1);
_mesh.faces[4].setEdgeVisFlags(1, 1, 1);
_mesh.faces[4].setSmGroup(sm);
_mesh.faces[5].setVerts(1, 10, 6);
_mesh.faces[5].setEdgeVisFlags(1, 1, 1);
_mesh.faces[5].setSmGroup(sm);
_mesh.faces[6].setVerts(2, 6, 7);
_mesh.faces[6].setEdgeVisFlags(1, 1, 1);
_mesh.faces[6].setSmGroup(sm);
_mesh.faces[7].setVerts(3, 7, 8);
_mesh.faces[7].setEdgeVisFlags(1, 1, 1);
_mesh.faces[7].setSmGroup(sm);
_mesh.faces[8].setVerts(4, 8, 9);
_mesh.faces[8].setEdgeVisFlags(1, 1, 1);
_mesh.faces[8].setSmGroup(sm);
_mesh.faces[9].setVerts(5, 9, 10);
_mesh.faces[9].setEdgeVisFlags(1, 1, 1);
_mesh.faces[9].setSmGroup(sm);
_mesh.faces[10].setVerts(6, 2, 1);
_mesh.faces[10].setEdgeVisFlags(1, 1, 1);
_mesh.faces[10].setSmGroup(sm);
_mesh.faces[11].setVerts(7, 3, 2);
_mesh.faces[11].setEdgeVisFlags(1, 1, 1);
_mesh.faces[11].setSmGroup(sm);
_mesh.faces[12].setVerts(8, 4, 3);
_mesh.faces[12].setEdgeVisFlags(1, 1, 1);
_mesh.faces[12].setSmGroup(sm);
_mesh.faces[13].setVerts(9, 5, 4);
_mesh.faces[13].setEdgeVisFlags(1, 1, 1);
_mesh.faces[13].setSmGroup(sm);
_mesh.faces[14].setVerts(10, 1, 5);
_mesh.faces[14].setEdgeVisFlags(1, 1, 1);
_mesh.faces[14].setSmGroup(sm);
_mesh.faces[15].setVerts(11, 7, 6);
_mesh.faces[15].setEdgeVisFlags(1, 1, 1);
_mesh.faces[15].setSmGroup(sm);
_mesh.faces[16].setVerts(11, 8, 7);
_mesh.faces[16].setEdgeVisFlags(1, 1, 1);
_mesh.faces[16].setSmGroup(sm);
_mesh.faces[17].setVerts(11, 9, 8);
_mesh.faces[17].setEdgeVisFlags(1, 1, 1);
_mesh.faces[17].setSmGroup(sm);
_mesh.faces[18].setVerts(11, 10, 9);
_mesh.faces[18].setEdgeVisFlags(1, 1, 1);
_mesh.faces[18].setSmGroup(sm);
_mesh.faces[19].setVerts(11, 6, 10);
_mesh.faces[19].setEdgeVisFlags(1, 1, 1);
_mesh.faces[19].setSmGroup(sm);
}

int myGeosphere::GetSetMiddlePoint(std::map<std::pair<int, int>, int>& _mpm, Mesh& _old, Mesh& _new, int& _next, int _a, int _b)
{
	// using std for std::map and std::pair
	using namespace std;

// creating std::pair container that will create key from given indexes
pair<int, int> indexes_key;

// for example: (1,2) and (2,1) should be treat as the same key
if (_a < _b)
	indexes_key = make_pair(_a, _b);
else
	indexes_key = make_pair(_b, _a);

// checking if given pair od indexes is in the map
if (_mpm.count(indexes_key))
{
	// if it exist return the middle point index of that pair of indexes
	auto result = _mpm.find(indexes_key);
	return result->second;
}
else
{
	// if not exist calculate it and add to vertex list of new mesh verts and middle_point_map
	Point3 point1 = _old.getVert(_a);
	Point3 point2 = _old.getVert(_b);
	Point3 middle_point = (point1 + point2) / 2;

	middle_point = FNormalize(middle_point);

	// add new vertex to new mesh vertex list
	_new.setVert(_next, middle_point);

	// add new vertex to middle point map
	_mpm[indexes_key] = _next;

	int next_value = _next;
	_next++;

	return next_value;
}

return 0;
}

to build myGeosphere use:

void myObject::BuildMesh(TimeValue t)
{
    ......
	myGeosphere gs;

    // ex. two subdivisions and smoothing
	gs.BuildGeosphere(mesh, 2, TRUE);
    ........
}