Sign in to follow this  
Marty666

tesselation.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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[i].Verts[0]] + Verts[Faces[i].Verts[1]])/2);
a0.SetLength((Verts[Faces[i].Verts[0]].GetLength() + Verts[Faces[i].Verts[1]].GetLength())/2);
a1 = ((Verts[Faces[i].Verts[1]] + Verts[Faces[i].Verts[2]])/2);
a1.SetLength((Verts[Faces[i].Verts[1]].GetLength() + Verts[Faces[i].Verts[2]].GetLength())/2);
a2 = ((Verts[Faces[i].Verts[2]] + Verts[Faces[i].Verts[0]])/2);
a2.SetLength((Verts[Faces[i].Verts[2]].GetLength() + Verts[Faces[i].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[i].Verts[0];
f.Verts[1] = indexes[i].Verts[1];
f.Verts[2] = indexes[i].Verts[2];
newfaces.push_back(f);
f.Verts[0] = Faces[i].Verts[0];
f.Verts[1] = indexes[i].Verts[0];
f.Verts[2] = indexes[i].Verts[2];
newfaces.push_back(f);
f.Verts[0] = indexes[i].Verts[0];
f.Verts[1] = Faces[i].Verts[1];
f.Verts[2] = indexes[i].Verts[1];
newfaces.push_back(f);
f.Verts[0] = indexes[i].Verts[1];
f.Verts[1] = Faces[i].Verts[2];
f.Verts[2] = indexes[i].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[i]);
}
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[i] = Verts[i] * (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[i].GetLength() < 1) {Verts[i].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[i].Verts[0]];
glVertex3f(v->x*Radius, v->y*Radius, v->z*Radius);
v = &Verts[Faces[i].Verts[1]];
glVertex3f(v->x*Radius, v->y*Radius, v->z*Radius);
v = &Verts[Faces[i].Verts[2]];
glVertex3f(v->x*Radius, v->y*Radius, v->z*Radius);
}
glEnd();
}


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this