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?

Usually this sort of thing is done with a graph search. It is not immediately clear why you need to deal with angles at all. Usually a mesh will be described as a topology with some kind of mesh format. Like winged edge or half edge mesh. In your case I would recommend building a half-edge mesh structure. This will let you flood fill (like with a DFS for example) triangle faces to find all triangles and half-edges that comprise a compartment. The key thing here is that each triangle would be composed of two faces and six half edges. This will allow unique "sides" of edges and triangles to belong to unique compartments.

Edit: Oh and one more thing. It would be really helpful to briefly describe the "why" of your post. What are you trying to accomplish, and then describe the problem. This helps people give you better answers. I tried to figure out the why and decided you were trying to identify unique compartments in a player-made triangle soup structure.

The "why" is that my game is a realistic shipbuilding and naval combat game in which sections of a ship can be flooded or not based on whether one of their surfaces has been compromised. Construction will have various tools for playability but essentially boils down to what you said: a player-made triangle soup.

Edit: buoyancy is calculated by surface not by volume because the latter is nigh impossible with this kind of arbitrary mesh. Hence it is necessary to know which side(s) of each face are exposed to the water.

The reason I was looking for the angle calculation is that my (perhaps naive) plan was to loop through all neighbors and check each one against the previous "best" angle, such that when the loop exits we're left with the closest neighbor in the given direction. Suffice it to say I did poorly in linear algebra. If you have a better algorithm I'm all ears.

So you just want to find which faces are facing the water?

It's not that simple, because while a fully repaired ship will only have its exterior faces exposed, damage to a face can flood the compartment behind it, causing previously dry faces to start performing hydrostatic calculations. Good design involves subdividing the ship into many compartments such that damage to one doesn't flood the entire thing.

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.

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]

What exactly do you want to do with several faces radiating from one edge? With a fully constructed half-edge mesh it is possible to do a flood fill to found all islands of the topology. In your example the islands would be compartment B, and then compartment + the outer hull (since the half edges of A would connect to the outer hull triangles over the damaged edges).

Edit: There are also other mesh formats if you don't like half-edge, like winged edge for example.

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)