I have a solid with internal holes. My solid is mostly a union between walls/floors/ceilings. Each of them is a mesh with polygons oriented counter-clockwise. Then with those polygons I do a union that serves to delete the intersection between the solids. Which leaves me with only one solid made of polygons.
In term of data I have as I have a data structure that looks like that :
Class Building Element:
- Object ID (Input)
- Implicit geometry (Input)
- Explicit geometry : calculated from implicit geometry. It's a list of polygons which is in turn an ordered list of points
- List of object ID of walls/floor... (Input)
- Explicit geometry : Union of explicit geometries of the objects listed
A room is represented by one solid, and the room is inside it and makes a hole. I want to be able to distinguish the polygons that bound the space inside from those that bound the space outside. Which would in theory split my polygons into two lists, one of the surfaces you would see if you were inside the room, and the other with surfaces visible from outside (assuming the input doesn't have any geometrical error).
Distinguishing this surfaces surely exists in literature but I can't find it. I think BSP-trees can help me solve such a problem, but I can't find out how.
Here is an example of my situation:
I have an idea on how to do it. My algorithm seems robust, but a bit stupid, I'm sure in literature there is something smarter :
First I need to get a point inside my object
- I calculate the bounding box containing my polygons
- I can then easily have a point outside if its x,y,z are superior or inferior to any other x,y,z of the bounding box
Find one external face
- From this point I do take a ray (the choice of the may be random, but a ray may fail to intersect the object. A ray between my exterior point and the center of the boundingbox should always be good)
- With ray tracing, I can find out the first polygon it touches. It may touch a vertex first. Then I'd just take one of the polygon that contains this vertex.
Split my list of polygons into smaller lists
Let's call P my list of polygons, and L a list of list of polygons, then li a list of polygons included in L.
li should include only polygons that touches each other.
Let's define what is touching each other : We define a polygon as a list of edges.
A general definition would be that two polygons (polygon1,polygon2) touch each others if ∃(edge1,edge2)∈ polygon1 x polygon2
For my simplified case : My polygons are list of points, and I know that two polygons that touches each others implies that they have a common vertex. I will use this simplified definition in practice, but it doesn't alter the methodology.
- I take the first polygon in P
- I remove it from P and add it to li
- I see if it touches any other polygon in P
- I get those polygons, remove them from P and add them to li
- I see if those polygons touch other polygons in P
- With those newly touched polygons, I repeat the step 4. But if it didn't touch anything at step 5, I go to next step.
- I put li in L
- if P still contains at least one item, I go to step 1
Only one of the sublists contain external li the external polygon I have found above. The others are internal.
When to check which sublists contain the external polygon probably depend in the data structure, but it's a matter of optimization, not robustness.