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

Class room:

  • 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.

  1. I take the first polygon in P
  2. I remove it from P and add it to li
  3. I see if it touches any other polygon in P
  4. I get those polygons, remove them from P and add them to li
  5. I see if those polygons touch other polygons in P
  6. 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.
  7. I put li in L
  8. 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.

  • $\begingroup$ Thank very much for your input! I'm going to check Weiler-Atherton's algorithm (which probably would help me to find out what missing informations I'm missing and that I have to include?). As for your second comment, I added an edit to explain a bit why I find it difficult, hope it's clearer now. $\endgroup$
    – Marouane
    May 25, 2016 at 15:45
  • $\begingroup$ I looked in your documentation. Yeah I can't call my mesh B-rep as I'm missing a lot of data. I misunderstood the Idea behind this representation. As for data complexity, actually I have buildings that I split into rooms. Those rooms are a closed space inside a solid that is made of walls. I took those walls, did a union with some solid geometry algo, and I got a solid made of polygons with orientation. I think my set of data propably doesn't allow any smart approach to this problem. Thank you very very much! $\endgroup$
    – Marouane
    May 25, 2016 at 18:21
  • $\begingroup$ 2D Resolution is a very good idea, as it would simplify the problem tremendously (at the very least it would make my algorithm way faster). I need to recheck my input data. What are recurrent things (walls should be always straight), and what data do I lose during my transformation (and that can be helpful for my problem). I appreciate a lot the time you spend helping me :) $\endgroup$
    – Marouane
    May 25, 2016 at 19:49
  • $\begingroup$ Thank you for your advice, I tried to put my post's informations in a more logical order. $\endgroup$
    – Marouane
    May 30, 2016 at 10:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.