Not exactly. I want to skip drawing the interior of a "cave" (or room) that doesn't have an entrance at all (until the player creates an entrance).
Then I agree with tool_2046: You can just look the parity of the number of intersections between the surrounding surface and a generic ray from the point.
Then I agree with tool_2046: You can just look the parity of the number of intersections between the surrounding surface and a generic ray from the point.
Seems I was still unclear.
The "intersection counting" applies if we know there is a polygon (or polyhedron). I want to check if there is a closed polyhedron around a certain point or box, so that everything inside the polyhedron can never be seen. An algorithm that checks if the faces, or a subset of the faces, constitute a closed surface.
Does it matter wheather the cave has an entrance or not? Would you like to drop rendering the cave if it had an entrence but is occluded as well? Or, are you trying to perform an offline one-time generated detection wheather the cave is reachable? If the second is true, all I can think of is traversing all faces of the cave and check on each face wheather it shares a vertex with the "viable" mesh. thus, is connected to the mesh you consider player visible. I cannot see very straight right now how I would modify this idea to be used on cube elements created area like minercraft one.
If you want to determine if the mouth of the cave is visible from any given point in space you need to use PVS’s.
If you want to determine if a polyhedron is closed, it is closed if all edges share at least one other edge with another face on the polyhedron.
These are not related algorithms and do not solve similar problems.
L. Spiro
If you want to determine if a polyhedron is closed, it is closed if all edges share at least one other edge with another face on the polyhedron.
I was going to post something like this, but in general it's not true. Perhaps the OP will never be so devious as to build a level involving one of the situations where the statement fails, but the mathematician in me can't leave this alone.
Here's a counterexample: If an edge might be shared by more than two polygons, you can build something like the typical immersion of the Klein bottle in 3 dimensions:
At the place where the bottle intersects itself, cut out the little disk inside. as you see every edge is shared by at least two polygons now, and yet the surface does not separate space into an outside and an inside.
That's not how a model of a Klein bottle would look, unless all the polygons are double sided (half the model would be inside out and half would not), and if all polygons are double sided, any mesh would pass the closed test according to that criterion anyway. A hoop made out of double sided quads has every edge shared by 2 polygons (assuming you count both sides as different polygons) - it would be like a deflated torus ;)
EDIT: Is it only non-orientable single-sided surfaces which fail L. Spiro's test though?
EDIT2: I think single sidedness is the key - if you make the Klein bottle with single sided polygons you end up stitching together edges going in the wrong direction (i.e. there is a twist introduced, you stitch together polygons where on one side of the edge one polygon points upwards and the other side of the edge they point downwards), so the shape is clearly not closed.
Yes, a compact, orientable two-dimensional manifold in R^3 separates the space into an outside and an inside. The problem with L. Spiro's sentence is "share at least one other edge". That suggests that an edge could be shared between more than two polygons, and then we are not talking about oriented manifolds anymore.
I think the original question, as it was posed, makes perfect sense if you interpret the polygons as being two-sided (which is what most non-computer-graphics people call a "polygon").
I think you need to consider a graph whose nodes are the sides of the polygons (so two nodes per polygon) and whose edges represent adjacency (i.e., sharing an edge facing the same way, with no other polygons getting in the way). The connected components of this graph correspond to the borders of the volumes that the polygons separate the space into.
Even with an edge shared by just 2 polygons you can get a non-oriented surface (your Klein bottle example). I think the criterion is that every edge has to have exactly 2 polygon neighbours, and they must be oriented correctly (i.e when you consider the polygon winding [clockwise/counterclockwise], the edge directions of the neighbours (which is +1 for an edge in the same direction as the winding, -1 for opposite direction) must sum to 0).
So for a square section of the following manifold the edge B->C has edge direction +1 in clockwise triangle ABC and direction -1 in clockwise triangle DCB, so the edge direction sum is 0.
A-B
|/|
C-D
This of course rules out T-junction shaped cracks in the mesh (triangulate properly to remove them) and more than 2 polygons meeting at an edge (like the pages on the spine of a book - which is not a manifold).
EDIT: I think we are saying the same thing ;)
the klein bottle is a proper enclosed mesh, wheather we consider it to have a thickness or not. if two enclosed meshes share an edge, they form a compact enclosed mesh. There is a STL check modifier in 3ds max that allows editable mesh to be cheked for
- open edges
- spikes
- ??
- double edges
I would add that topology mathematics are always studying objects that 3d programmers call "enclosed mesh", wheather it is just an enclosed plane with 4 triangles without thickness or with it. Objects with open edges -without other side, are highly metaphysical (Mobius list has two sides as well, do not confuse what I am trying to say)
A Klein bottle isn't closed... there is no inside or outside. You can travel off to infinity without crossing a boundary from any point not on the surface via a continuous path without travelling through the manifold (it doesn't self intersect when embedded in 4d space, and can't be embedded in 3d space).
A Klein bottle is just 2 Mobius strips (opposite handedness/chirality though) with their edges glued together anyway (good luck doing that in 3d space) ;)
EDIT: As I said before, you can't make a Klein bottle mesh without making the polygons double sided or making a double cover of the surface. Similarly you can't make a Mobius strip mesh model that uses one sided polygons (without doubling up the polygons), since where you would glue the mesh the polygon faces point in opposite directions. A double cover model self intersects (since incidence == intersection), so this breaks the rule that each edge has exactly 2 neighbours.
