Hi all,

I was wondering if anyone might know where to start on this problem:
Given a bunch of primitives (triangles in my case), ensure that they completely enclose at least one volume.

My initial approach was to make sure all the edges were matched up with those of other triangles, but I also wanted to allow for the faces of primitives to enclose volumes (leaving the edges free and "hanging" off the side), or for a primitive to be connected to one of the faces of the volume by only one edge.

I did some Googling on the matter and found these things related to Maya:
http://www.vfxoverfl...ary-closed-mesh
http://forums.cgsoci...p/t-754789.html

These work on the assumption that there's already a closed volume in the first place, or that having a free edge is bad, which are not necessarily true in my case.

Thinking more robustly: from a programming perspective, I thought I could begin by testing all my triangles to see if they enclose a volume. The minimum is four triangles (a tetrahedron), so I would have to test all my triangles that share three edges with others in groups of four (in all combinations), then in groups of five (in all combinations), six, seven, and so on. That method only accounts for edge-connected triangles. So this:

which is a poorly-drawn pyramid stuck to a square plate (completely enclosed, but with free edges--should pass my test) would be rejected, even though I want to accept that.

However, this triangle stuck to the top of a closed cube, also okay by my standards, would pass successfully:

But, since that figure would be made up of 9 triangles, it would take (at most) 1784 tests (http://www.wolframalpha.com/input/?i=13+choose+4+%2B+13+choose+5+%2B+13+choose+6+%2B+13+choose+7+%2B+13+choose+8+%2B+13+choose+9+%2B+13+choose+10+%2B+13+choose+11+%2B+13+choose+12+%2B+13+choose+13) to figure that out.

Note that in that last case the triangle's bottom edge spans a face that would be made up of two separate triangles--that adds an extra wrinkle to the problem, I guess.

So, not only does my method require n C 4 + n C 5 + ... + n C n - 1 + n C n tests at most (where "C" means "in combinations of" ), but it doesn't immediately take care of the other cases I want to allow for either.

Might anyone be able to come up with a better method off the top of his/her head? I'm stumped on this one.

Regards,
-- Steve.

I haven't proven this, but can't you just greedily discard any triangle that has a free edge until no such triangles remain; if you're left with more than one triangle at the end, a volume is enclosed?

E.g.,
- your pyramid-on-a-plate will shrink to just-a-pyramid and then stop changing;
- your flag-on-a-cube will shrink to just-a-cube and then stop changing.

You might need to think a little bit about special cases where lots of vertices are coplanar, but other than that... does this do what you want?

(I'm assuming your mesh is "nice" in certain ways -- no t-junctions, etc. Basically, I'm assuming it's a simplicial 2-complex.)

I was thinking about this overnight and I was going to suggest the same thing. But then I remembered I built a counter-example to this once. You basically build a Klein bottle. Take for instance the picture in that Wikipedia page and imagine that, where the intersection happens, you cut out a hole in the bulged part, so that the thin tube is unobstructed. That's a simplicial 2-complex with no free edges which does not enclose any volume.

I think I have something that would work.
(1) Do what Emergent suggested.
(2) Look at each connected component of the complex separately.
(3) Consider each triangle as having two sides and "paint" the surface (i.e., figure out the connected components of the graph whose nodes are the sides of the triangles and whose edges connect triangle sides which share an edge without any other triangles in between them). If you don't end up painting the whole thing (i.e., if that graph has more than one connected component), it means that there is an inside and an outside to your object, so there is a volume is enclosed.

I like alvaro's flood-fill approach to determine orientability, since it keeps everything totally combinatorial.

If one were to impose the additional geometric requirement that no triangles intersect (not that I suggest this), then I suppose it would not be necessary. IIRC, all (compact?) 2-manifolds-with-boundary that can be embedded in R^3 are orientable. You can start to imagine a preprocessing step (again, not that you'd want to do this) in which you split triangles so that they don't intersect, and subdivide them to eliminate t-junctions, before doing the greedy thing I described. This would come back with the answer that the immersion of a Klein bottle in 3d does contain a volume, because it isn't really a Klein bottle, but only its immersion; it has to "pass through" itself, and the surface that it "passes through" splits it into two parts, each of which contains a volume.

Now that we've gotten two different answers depending on how we looked at the question, the immediate next thing to ask is what the heck we actually mean by the phrase "enclose a volume" to begin with.

I have a suspicion that the combinatorial answer alvaro and I have been giving is going to be whether or not the 2d homology group is trivial, but this is stuff I'm just now learning so I can't confidently give you an answer. (Yet? :-) ) Alvaro, maybe you have an idea?

I like alvaro's flood-fill approach to determine orientability, since it keeps everything totally combinatorial.

If one were to impose the additional geometric requirement that no triangles intersect (not that I suggest this), then I suppose it would not be necessary. IIRC, all (compact?) 2-manifolds-with-boundary that can be embedded in R^3 are orientable. You can start to imagine a preprocessing step (again, not that you'd want to do this) in which you split triangles so that they don't intersect, and subdivide them to eliminate t-junctions, before doing the greedy thing I described. This would come back with the answer that the immersion of a Klein bottle in 3d does contain a volume, because it isn't really a Klein bottle, but only its immersion; it has to "pass through" itself, and the surface that it "passes through" splits it into two parts, each of which contains a volume.

You have to drop the "with boundary" from your statement about immersions for it to be true (counterexample: Möbius strip). But your preprocessing step already got rid of all the borders.

The problem is whether we accept an edge that is shared by three triangles. If we don't, then we are dealing with a discretization of a compact manifold, and it is true that an embedding into R^3 will be orientable and enclose a volume.

Now that we've gotten two different answers depending on how we looked at the question, the immediate next thing to ask is what the heck we actually mean by the phrase "enclose a volume" to begin with.[/quote]

I think the original description of the problem was open enough to incorporate my counterexample.

I have a suspicion that the combinatorial answer alvaro and I have been giving is going to be whether or not the 2d homology group is trivial, but this is stuff I'm just now learning so I can't confidently give you an answer. (Yet? :-) ) Alvaro, maybe you have an idea?
[/quote]

Funny you should say that. Checking whether the second group of homology is trivial or not was my first idea, but it's been too long since I studied that to be sure that it would work, and I didn't want to scare anyone away.

Whoops! I reread your earlier post, alvaro. I'd missed that you explicitly did deal with the fact that the Klein bottle immersion intersects itself (I thought you'd used an actual Klein bottle): You'd cut a hole! And still, both (1) the complex had no boundary, and (2) no volume was enclosed. Yeah, that's a really nice counterexample.

I get what's going on now, and I see the importance of not having edges shared by 3+ triangles. That situation immediately violates the combinatorial definition of orientability, since all three would have to induce opposite orientations on the edge, which is impossible because there are only two orientations.

As for the second homology group (thinking out loud)... It's cycles mod boundaries; we haven't got any tetrahedra, so it's just all the cycles. That's just the null space of the boundary operator -- i.e., that of the transpose of the triangle-to-edge incidence matrix. That matrix is the same as the incidence matrix for the upper-adjacency graph for the complex's edges (i.e., the graph you mentioned). The null space of a graph's incidence matrix has a dimension for each of its connected components. The homology group being trivial means it being one-dimensional.... means the null space of that matrix being 1-dimensional... means there being a single connected component. But, if your complex is fully connected, then so will be this graph. So, all the second homology group being trivial tells you is that your complex has a single connected component. Your counterexample has a single connected component, so this isn't enough. Hence we're looking for something besides the second homology group being trivial. Sound right?

Orientability, however, seems important... which leaves me wondering what exactly fills the blank in this sentence:
"If a simplicial complex is (1) orientable, and (2) without boundary, then _____________________."

Emergent, alvaro,

These were two great answers and a great discussion to read--I must admit I'm not following completely on the math, but the methods you've suggested make sense to me.

For the purposes of the game I'm writing, I am not concerned about the fringe case Klein bottle, but that is an interesting point since a Klein bottle doesn't enclose anything

I really like the painting solution, though. When I find the time to implement it, I'll give it a shot and [hopefully remember to] post the results.

Much thanks for the ideas--the contents of your posts and the support of this community gives me both the confidence and the willpower to finish what I started...(when I find the time!)

Best,
-- Steve.