#### Archived

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

# Finding edge vertices

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

## 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 on other sites
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 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 on other sites
ok
oliii, does that work for concave patches also? thanks for that tid-bit though

##### 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]

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633677
• Total Posts
3013284
×