My problem is a little hard to explain, and it's pretty much unique to my project so even if I could I doubt there's a ready-made algorithm out there. In my game, I have a group of triangles, each defined by three int vectors. They form a mesh which has not only an outer skin but internal partitions dividing it into "compartments." The triangles are placed directly by the player, so they cannot be guaranteed to follow any order or convention. A partner and I devised an algorithm to assign every triangle to either one or two compartments:

1. Start from a random side (+ or - normal) of a random triangle.
2. For each edge of the selected triangle, find all other triangles which share that edge (triangles are only allowed to share an entire edge, i.e. two vertices are the same).
3. Of those triangles, find the one which is at the smallest angle to the starting triangle in the direction determined by the selected normal (from 0 to 360 degrees).
4. Determine which normal of that triangle points "into" the same compartment as the original (if the triangles are coplanar, the normals will be equal).
5. Repeat 2-4 recursively until there are no unique sides to add. At this point they must necessarily form an enclosed solid.
6. Select a new triangle side which has not yet been assigned to a compartment (but may be the opposite side of one that has) and repeat 2-5 until every side of every triangle is assigned to a compartment.

Steps 3 and 4 are what's causing me grief. It's simple enough to find all the triangles which share an edge with a given triangle by looping over the collection and testing each triangle's vertices. It's slow, but it only needs to be done once when the mesh is loaded so it won't hurt the framerate. However, once we have this subset of triangles radiating from a given edge, the task becomes harder. Here's a picture to help explain what I need to do:

[attachment=34701:triangle madness.png]

I've spent pretty much all day scrawling vectors on scrap paper and pulling my hair out but to no avail. Anyone have some advice on how to accomplish one or both of these tasks?

So what is wrong with doing a flood fill on a half edge mesh? Because the mesh isn't well-formed enough? I'm just trying to understand what problem you are trying to solve, and why.

To be honest I wasn't aware of the half-edge mesh data structure until you mentioned it. Currently my faces are just a big, dumb array of triangle structs, each with three vertices, because that translates easily into UE4's visual meshes. After doing some research, that seems like a good solution.

After continued research it seems like a "standard" half-edge mesh won't quite be sufficient as it's still designed for meshes that only comprise an outer "skin" with no internal partitions. From Wikipedia:

Each edge usually bounds two faces and it is therefore convenient to regard each edge as two half-edges. Each half-edge bounds a single face and thus has a pointer to that face.

My game needs to allow internal partitions. The simplest example would be a square prism twice as long as it is wide, with an internal face dividing it into two cube-shaped compartments. One solution would be to add a pointer to the next half-edge around the edge, effectively making it an "nth edge" data structure. However, that creates a similar problem to my original one, as it would need to figure out which partial edge to split when adding a new face to an existing cluster.

Here's another picture to help explain what I'm after. The top left shows a very simple example of the system: a 1x1x2 unit prism with a partition in the middle splitting it into two cube-shaped compartments. The top left shows the game mechanic that arises from this: damage to one compartment allows water into side A, but the partition keeps side B dry. Finally, the bottom shows how a standard half-edge mesh only accounts for one-sided faces of a single-compartment mesh, but doesn't solve the problem of several faces radiating out from an edge.

[attachment=34710:triangle madness 2.png]

The exterior and interior triangles are not distinct but rather a single two-sided triangle with zero thickness. For a player not familiar with 3D modeling, it is conceptually easier to build with two-sided surfaces the way they might create paper models in real life. When a surface is damaged, it is flagged as "not watertight," but the mesh doesn't dynamically deform to create triangles that bridge between the interior and exterior. So at some point--whether in real time during construction or all at once when the design is loaded into the game world--the game needs to construct a one-directional mesh for each compartment from the two-sided surfaces the player will be working with. If we do it in real time, here's a potential situation that could happen:

• The mesh is the 1x1x2 square prism above, minus the internal partition. The exterior and the interior are two discrete half-edge meshes.
• The player places two new triangles to create that internal partition.
• The game now needs to update the references in those existing faces to connect to either side of the new triangle, forming two compartments from the one we had before.

[attachment=34719:triangle madness 3.png]

(I didn't draw every triangle in the picture to reduce clutter)