Implementation of Winged Edge in Lua

Question

I am working on a game with an irregular grid and I was recommended to use the Winged Edge data structure. Reading what it's used for seems straight forward enough but I simply cannot figure out how to implement it.

What my ultimate goal is to be able to detect which faces I am clicking on, and which faces are adjacent to the clicked face. Could someone possible walk me in the right direction?

Answer 1

After some further reading and discussion, I managed to write a pretty snazzy Winged Edge library. It is licensed under the MIT license so if anyone wants to use it, you're more than welcome!

https://github.com/karai17/Lua-Winged-Edge

The way this works is as follows:

The key feature of Winged Edge is how every set of data references every other set of data. Each vertex lists all of the edges that are connected to it, each edge lists connected vertices and faces, and each face lists connected vertices and edges. The usefulness of this will be come more apparent below.

First I parsed a Wavefront Object file to get a list of vertices and faces. Each vertex has XYZ coordinates, and each face has a list of vertices it is connected to:

obj.vertices = {
    { x=0, y=0, z=0 },
    { x=1, y=0, z=0 },
    { x=1, y=1, z=0 },
    ...
}

obj.faces = {
    { 1, 2, 3 },
    { 1, 2, 4 },
    { 3, 4, 5, 6 },
    ...
}

I then created three tables for my winged edge (WE) object: vertices, edges, and faces. I parsed the vertices and created WE vertices:

WE.vertices = {
    { edges={}, position={ 0, 0, 0 } },
    { edges={}, position={ 1, 0, 0 } },
    ...
}

I then parsed the faces to create WE edges and WE face, filling in all the references. The edges have a special case, not only do they reference the faces they are connected to, but they also reference the previous and next edges for each face. This is extremely important as it allows you to traverse the edges of a face to find the faces adjacent to the current:

WE.vertices = {
    { edges={ 1, 2, 3 }, position={ 0, 0, 0 } },
    { edges={ 2, 3, 4 }, position={ 1, 0, 0 } },
    ...
}

WE.edges = {
    { vertices={ 1, 2 }, faces={ face=1, prev_edge=3, next_edge=2 } },
    { vertices={ 2, 3 }, faces={ face=1, prev_edge=1, next_edge=3 } },
    { vertices={ 3, 1 }, faces={ face=1, prev_edge=2, next_edge=1 } },
    ...
}

WE.faces = {
    { edges={ 1, 2, 3 }, vertices={ 1, 2, 3 } },
    { edges={ 2, 3, 4 }, vertices={ 2, 3, 4 } },
    ...
}

With the data structure set up like this, you can create a function that checks which faces an edge belongs to, and traversing through those edges can allow you to gather up all of the faces adjacent to any particular face, and where they are in space.

What I used this for was to check which faces surrounded a face that I click on to determine if I am allowed to activate that face based on some game logic, like if any of the surrounded faces were already activated. Another use of this is for flood filling faces.

For any further details such as exact execution, you are welcome to snoop around the code linked above. :)