tesselation.

Author

145

September 21, 2004 06:10 PM

Hi all, I'm creating a little program that renders a sphere with heightmapping. The sphere is created as a octocahedron (if that's what 8 regular triangles stacked like 2 pyramids, once upsidedown is called). I tesselate the faces and normalize the vertexes to get more detail. This all works fine. For the landscape algorithm I need the different tesselation steps, because I add noise to the length of the normalized vertexes to create some hills/mountains. With every level of detail less noise is introduced (like perlin noise). The problem is that there are holes in my planet, because every edge is shared by two triangles so when it is split, that is also done twice and with the noise added it gives two different vertexes that should be the same. Does anyone know some good tesselation alghorithms or can anyone tell me what to do? Thanx, Marty

_____ /____ /|| | || MtY | ||_____|/Marty

ga

126

September 21, 2004 06:20 PM

Sounds like you're duplicating the vertices for every triangle. Just storing a list of vertices and a list of triangles with indices to the vertices and only manipulating the vertices should fix that.

Visit our homepage: www.rarebyte.de.stGA

Marty666

Author

145

September 21, 2004 06:24 PM

That's what i'm doing, but i'm creating new vertexes and triangles when i'm tesselating. I should check if i'm doing a vertex double in the tesselating algorithm or prevent doing stuff double in the algo. Both I can't figure out.

_____ /____ /|| | || MtY | ||_____|/Marty

Luke Miklos

142

September 21, 2004 10:43 PM

hehe, perhaps we can lend some quick fixes if you post some code. Otherwise... you are asking us to write it all out for you... not gonna happen :)

Whatsoever you do, do it heartily as to the Lord, and not unto men.

Marty666

Author

145

September 25, 2004 08:04 AM

Ok this is it... 0, 1 or 2 itterations is fine, then holes start to appear. There are more vertexes then there should be aswell. The problem might be in roundoff errors when checking the coordinates to see if a vertex is done double.

Marty

void cSphere::Tesselate(){	tVec3 a0, a1, a2; // to store the new vertexes where the edges are split.	int oldnumverts = numverts; // To keep track of the number of verts that we had, cause numverts is incremented	vector<tFace> indexes;	// stores the indexes of the split edge verts. [FACE][EDGE]...							// EDGE 0 = vert 0->1,		EDGE 1 = vert 1->2,		EDGE 2 = vert 2->0	tFace faceindexes;		// This one is used to store the EXISTING vert indexes...							// if it doesn't exist it will be 0.	for (int i = 0; i < numfaces; i++)	{		// averages are calculated and length is also set to average for 'Perlin' noise		a0 = ((Verts[Faces.Verts[0]] + Verts[Faces.Verts[1]])/2);		a0.SetLength((Verts[Faces.Verts[0]].GetLength() + Verts[Faces.Verts[1]].GetLength())/2);		a1 = ((Verts[Faces.Verts[1]] + Verts[Faces.Verts[2]])/2);		a1.SetLength((Verts[Faces.Verts[1]].GetLength() + Verts[Faces.Verts[2]].GetLength())/2);		a2 = ((Verts[Faces.Verts[2]] + Verts[Faces.Verts[0]])/2);		a2.SetLength((Verts[Faces.Verts[2]].GetLength() + Verts[Faces.Verts[0]].GetLength())/2);				// if no double vertexes are found these will still be 0. 		// 0 is the first vertex and it's allready there, so we don't have to worry about that.		faceindexes.Verts[0] = 0;		faceindexes.Verts[1] = 0;		faceindexes.Verts[2] = 0;				// check all the new verts if they've allready been done by a neighbour.		// the new verts start at oldnumverts, so we only need to check from there		for (int j = oldnumverts; j < numverts; j++)		{			if ((a0.x == Verts[j].x) && (a0.y == Verts[j].y) && (a0.z == Verts[j].z))			{				faceindexes.Verts[0] = j;			} // yes? save it to faceindexes.					if ((a1.x == Verts[j].x) && (a1.y == Verts[j].y) && (a1.z == Verts[j].z))			{				faceindexes.Verts[1] = j;			} // yes? save it to faceindexes.					if ((a2.x == Verts[j].x) && (a2.y == Verts[j].y) && (a2.z == Verts[j].z))			{				faceindexes.Verts[2] = j;			} // yes? save it to faceindexes.		}		if (faceindexes.Verts[0] == 0) // was it done allready?		{			faceindexes.Verts[0] = numverts; // if not we're gonna make a new one			Verts.push_back(a0);			numverts++;		}		if (faceindexes.Verts[1] == 0) // was it done allready?		{			faceindexes.Verts[1] = numverts; // if not we're gonna make a new one			Verts.push_back(a1); 			numverts++;		}		if (faceindexes.Verts[2] == 0) // was it done allready?		{			faceindexes.Verts[2] = numverts; // if not we're gonna make a new one			Verts.push_back(a2); 			numverts++;		}		indexes.push_back(faceindexes); // save the new indexes for this face's split edge verts	}	// Create all the new faces.	tFace f;	vector<tFace> newfaces;	int numnewfaces = 0;	for (i = 0; i < numfaces; i++)	{		f.Verts[0] = indexes.Verts[0];		f.Verts[1] = indexes.Verts[1];		f.Verts[2] = indexes.Verts[2];		newfaces.push_back(f);		f.Verts[0] = Faces.Verts[0];		f.Verts[1] = indexes.Verts[0];		f.Verts[2] = indexes.Verts[2];		newfaces.push_back(f);		f.Verts[0] = indexes.Verts[0];		f.Verts[1] = Faces.Verts[1];		f.Verts[2] = indexes.Verts[1];		newfaces.push_back(f);		f.Verts[0] = indexes.Verts[1];		f.Verts[1] = Faces.Verts[2];		f.Verts[2] = indexes.Verts[2];		newfaces.push_back(f);		numnewfaces += 4;	}	Faces.clear();	// copy them to the original faces vector.	numfaces = numnewfaces;	for (i = 0; i < numfaces; i++)	{		Faces.push_back(newfaces);	}	newfaces.clear();}void cSphere::AddNoise(float amount){	for (int i = 0; i < numverts; i++)	{		float n = rand()%2000 - 1000; // -1000 ... 999		n *= (amount/1000); // -amount ... amount		Verts = Verts * (n+1.0f);	}}cSphere::cSphere(int Detail, float Noise, float Persistency){	numverts = 0; numfaces = 0;	tVec3 v(0.5, 0.5, 0);	v.Normalize();	Verts.push_back(v); numverts++;	v = tVec3(0.5, -0.5, 0);	v.Normalize();	Verts.push_back(v); numverts++;	v = tVec3(-0.5, -0.5, 0);	v.Normalize();	Verts.push_back(v); numverts++;	v = tVec3(-0.5, 0.5, 0);	v.Normalize();	Verts.push_back(v); numverts++;	v = tVec3(0, 0, sqrt(0.5));	v.Normalize();	Verts.push_back(v); numverts++;	v = tVec3(0, 0, -sqrt(0.5));	v.Normalize();	Verts.push_back(v); numverts++;	tFace f;	f.Verts[0] = 0;	f.Verts[1] = 4;	f.Verts[2] = 1;	Faces.push_back(f); numfaces++;	f.Verts[0] = 1;	f.Verts[1] = 4;	f.Verts[2] = 2;	Faces.push_back(f); numfaces++;	f.Verts[0] = 2;	f.Verts[1] = 4;	f.Verts[2] = 3;	Faces.push_back(f); numfaces++;	f.Verts[0] = 3;	f.Verts[1] = 4;	f.Verts[2] = 0;	Faces.push_back(f); numfaces++;	f.Verts[0] = 0;	f.Verts[1] = 1;	f.Verts[2] = 5;	Faces.push_back(f); numfaces++;	f.Verts[0] = 1;	f.Verts[1] = 2;	f.Verts[2] = 5;	Faces.push_back(f); numfaces++;	f.Verts[0] = 2;	f.Verts[1] = 3;	f.Verts[2] = 5;	Faces.push_back(f); numfaces++;	f.Verts[0] = 3;	f.Verts[1] = 0;	f.Verts[2] = 5;	Faces.push_back(f); numfaces++;	// the code above creates two pyramids, i think it's called an octahedron. It's 8 triangles with all the edges 1.	// UnitVector makes the edges a different size, but all the points will be removed 1 from the origin.	// It's tested and works fine		for (int i = 0; i < Detail; i++) 	{		Tesselate();		AddNoise(Noise);		Noise = Noise * Persistency;	}	// Lower than 1 should be oceans, so they're put back to 1.	for (i = 0; i < numverts; i++)	{		if (Verts.GetLength() < 1) {Verts.Normalize();}	}}void cSphere::Render(float Radius){	tVec3* v;	glEnable(GL_TEXTURE_2D);	glBegin(GL_TRIANGLES);	for (unsigned int i = 0; i < numfaces; i++)	{		v = &Verts[Faces.Verts[0]];		glVertex3f(v->x*Radius, v->y*Radius, v->z*Radius);		v = &Verts[Faces.Verts[1]];		glVertex3f(v->x*Radius, v->y*Radius, v->z*Radius);		v = &Verts[Faces.Verts[2]];		glVertex3f(v->x*Radius, v->y*Radius, v->z*Radius);	}	glEnd();}

_____ /____ /|| | || MtY | ||_____|/Marty