Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Grizwald

Finding edge vertices

This topic is 5649 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

ok, given an irregularly shaped patch of a heightfield, how can i find the vertices on the very outside. I will only be testing for "outsideness" on the XZ plane. If you need some clarification just let me know. All help appreciated. [edited by - Grizwald on April 2, 2003 5:28:22 PM]

Share this post


Link to post
Share on other sites
Advertisement
What do you mean by outsideness? I have some code I can dig out and explain that will generate indices for the vertices along the 4 edges of a heightfield, given the length and height. Example of what my code does:

6--7--8
| \ | \ |
3--4--5
| \ | \ |
0--1--2

(excuse the crude picture)
My code will generate 6,3,0, 0,1,2, 2,5,8, 6,7,8 (which are the vertices on the edges).
And it works for anything retangular shaped. As for "irregular shaped", I think you're gonna need to clarify a little more, maybe give a picture of what you are trying to do.

Hope that helps

-------------------
Realm Games Company

[edited by - greatone on April 2, 2003 5:39:42 PM]

Share this post


Link to post
Share on other sites
simple. For each triangles, store the list of negihbouring triangles, and scan every triangles and and find the neighbours in the list


  

struct cTri
{
int V[3]; // vertex indices

int T[3]; // triangle neighbours


cTri(int V0=-1, int V1=-1, int V2=-1)
{
V[0] = V0;
V[1] = V1;
V[2] = V2;
T[0] = -1;
T[1] = -1;
T[2] = -1;
}

bool TryToLink(cTri& Tri, int ThisIndex, int TriIndex)
{
for(int i = 0; i < 3; i ++)
{
// edge already linked

if (T[i] != -1)
continue;
int ip1 = (i+1)%3;
for(int j = 0; j < 3; j ++)
{
if (Tri.T[j] != -1)
continue;

int jp1 = (j+1)%f;

// the edge is shared between the triangles

if (T[i] == Tri.T[jp1] && T[ip1] == Tri.T[j])
{
T[i] = TriIndex;
Tri.T[j] = ThisIndex;
return true;
}
}
return false;
}
}
}



main()
{
int Tnum; // num triangles

cTriangle TerrainTri[Tnum]; // the terrain triangles

......
......
......
......

cTri* Tris = new cTri[Tnum];

for (int i = 0; i < Tnum; i ++)
{
Tris[i] = cTri(TerrainTri[i].Index[0], TerrainTri[i].Index[1], TerrainTri[i].Index[2]);
}

for(int i = 0; i < Tnum; i ++)
{
for(int j = i+1; j < Tnum; j ++)
{
Tris[i].TryToLink(Tris[j], i, j);
}
}

......
......
......
......




now, once you have the tri links initialised, the ones with a T[] set to -1 are the triangles at the edge of the terrain. The corresponding vertices on the triangles are therefore on the edge as well. Furthermore, if a triangle has two T[] set to -1, then the corresonding vertex is one of the corners of your terrain.

Share this post


Link to post
Share on other sites
quote:
Original post by Grizwald
ok
oliii, does that work for concave patches also? thanks for that tid-bit though


would work for any kinds of mesh really. It will tell you which triangles have a edge not linked to anything, so a boundary triangle, boundary edges, boundary vertices...

If you want to differenciate concave edge to convex edges, you need the triangles normals, and do


            

class cTriangle
{
int V[3];
int T[3];
Vector Normal;

cTriangle(const Vector* Vertices, int V0, int V1, int V2)
{
V[0] = V0;
V[1] = V1;
V[2] = V2;
T[0] = T[1] = T[2] = -1;
Vector E = Vertices[V1] - Vertices[V0];
Vector F = Vertices[V2] - Vertices[V1];
Normal = E ^ F; // cross product

Normal.Normalise();
}

bool IsEdgeConvex(const Vector *Vertices, const cTriangle* Triangles, int edge) const
{
if (T[edge] == -1)
return false;

Vector Et = Normal ^ Triangles[T[edge]].Normal; // cross product

Vector E = Vertices[V1] - Vertices[V0];
return (Et * E >= 0.0f); // dot product

}
};



also, you have to have your triangles all winded anti-clockwise. If an edge is skewed between two neighbouring triangles, the tris won't be linked.

to be really thourough, you can try


        
void TryToLink(cTri& Tri, int ThisIndex, int TriIndex)
{
for(int i = 0; i < 3; i ++)
{
// edge already linked

if (T[i] != -1)
continue;
int ip1 = (i+1)%3;
for(int j = 0; j < 3; j ++)
{
if (Tri.T[j] != -1)
continue;
int jp1 = (j+1)%f;
// the edge is shared between the triangles

if (T[i] == Tri.T[jp1] && T[ip1] == Tri.T[j] ||
T[i] == Tri.T[j] && T[ip1] == Tri.T[jp1])
{
T[i] = TriIndex;
Tri.T[j] = ThisIndex;
}
}
}
}


note : the return false was at the wrong place in the previous code.

note 2 : jeez that source annotation is buggy... :
[edited by - oliii on April 4, 2003 8:09:28 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!