<p>In general, I recommend the book <a href="http://realtimecollisiondetection.net/" rel="nofollow">Real-Time Collision Detection</a>.</p>

<p>For your particular case, my first choice would be to use the 3D test for point-inside-mesh. I assume that the contour is a sequence of 2D segments (a sequence of vertices, essentially) and that the model mesh is "sealed", i.e. there are no holes in its surfaces that would make distinguishing the "inside" and "outside" of it impossible.</p>

<ol>
<li>Find a bounding box for your mesh.</li>
<li>Cast rays from an edge of the bounding box to the tested point. In your case, the ray would be coplanar with the slicing plane, and the point would be one of the vertices of the contour.</li>
<li>Count how many times the ray crosses mesh triangles.</li>
<li>Odd number of crossings means that the point is on the inside; even number means it's on the outside.</li>
<li>Repeat points 2-4 for all contour vertices.</li>
<li>Classify contour regions by whether their vertices are on the inside or outside.</li>
</ol>

CC BY-SA 3.0
2016-04-14T09:17:09.850Z
Yes this tracing works, but if the object was sealed in the first place wouldt the contour have a sidedness?
joojaa
CC BY-SA 3.0
2016-04-14T09:23:23.287Z
I'm not sure I follow. Isn't the point of the question to determine this sidedness? It's not like you magically get it as a parameter after the CSG slice.
IneQuation
CC BY-SA 3.0
2016-04-14T09:43:29.437Z
You do get the sidedness of  the model, 3d already has a sidedness which is almost allways the case. When you slice the model you know which side is outwards so for each loop you also know which side of it is inside (jsut record normal in 2D also). This means that if you loop around the contour clockwise (from above) and the predominate cross product of each edge is away from you then its a interior edge. But the trace trick can be faster as its a O(log(n)) operations while this test is n.
joojaa
CC BY-SA 3.0
2016-04-14T10:37:14.187Z
Ah, so you basically mean using the surface normal for that? I can see that working, but only if you have a way of knowing what "away" means. :) And while it's trivial for convex meshes (centroid should be fair enough), concave ones will be tricky. The ray trace method sidesteps this issue.
IneQuation
CC BY-SA 3.0
2016-04-14T10:40:02.013Z
that's whats i was alluding winding rules can handle this for you but tracing is less work.
joojaa
CC BY-SA 3.0
2016-04-23T13:04:45.360Z
Let me see if I have understood you correctly. Ray tracing parallel to the slicing planes seems to not only help me get the inside/ouside of the contour , but also pave a way to implement GPU slicer for 3D model made of triangular meshes.
sajis997
CC BY-SA 3.0
2016-04-14T08:11:28.427Z
2016-04-14T08:11:28.427Z
IneQuation
<p>A 3D model is sliced against a plane and the resulting 2D contour is projected onto the plane. I am looking for an efficient algorithm to identify the inside and outside region of the contour. Simultaneously I need to identify outer and inner loops within the contours. </p>

<p>Any references from articles/books is earnestly requested.</p>

<p>Thanks</p>

<vector-graphics>
inside and outside region identification from 2D contour
sajis997
# inside and outside region identification from 2D contour

(Asked by: username_0 on 2016-04-14)

A 3D model is sliced against a plane and the resulting 2D contour is projected onto the plane. I am looking for an efficient algorithm to identify the inside and outside region of the contour. Simultaneously I need to identify outer and inner loops within the contours.

Any references from articles/books is earnestly requested.

Thanks

**Tags:** vector-graphics


---

## 1 answers

### Answer by username_1 on 2016-04-14. Score: 3

In general, I recommend the book [Real-Time Collision Detection](http://realtimecollisiondetection.net/).

For your particular case, my first choice would be to use the 3D test for point-inside-mesh. I assume that the contour is a sequence of 2D segments (a sequence of vertices, essentially) and that the model mesh is "sealed", i.e. there are no holes in its surfaces that would make distinguishing the "inside" and "outside" of it impossible.

1. Find a bounding box for your mesh.
2. Cast rays from an edge of the bounding box to the tested point. In your case, the ray would be coplanar with the slicing plane, and the point would be one of the vertices of the contour.
3. Count how many times the ray crosses mesh triangles.
4. Odd number of crossings means that the point is on the inside; even number means it's on the outside.
5. Repeat points 2-4 for all contour vertices.
6. Classify contour regions by whether their vertices are on the inside or outside.

> **Comments:**
> **username_2**: Yes this tracing works, but if the object was sealed in the first place wouldt the contour have a sidedness?  
> **username_1**: I'm not sure I follow. Isn't the point of the question to determine this sidedness? It's not like you magically get it as a parameter after the CSG slice.  
> **username_2**: You do get the sidedness of  the model, 3d already has a sidedness which is almost allways the case. When you slice the model you know which side is outwards so for each loop you also know which side of it is inside (jsut record normal in 2D also). This means that if you loop around the contour clockwise (from above) and the predominate cross product of each edge is away from you then its a interior edge. But the trace trick can be faster as its a O(log(n)) operations while this test is n.  
> **username_1**: Ah, so you basically mean using the surface normal for that? I can see that working, but only if you have a way of knowing what "away" means. :) And while it's trivial for convex meshes (centroid should be fair enough), concave ones will be tricky. The ray trace method sidesteps this issue.  
> **username_2**: that's whats i was alluding winding rules can handle this for you but tracing is less work.  
> **username_0**: Let me see if I have understood you correctly. Ray tracing parallel to the slicing planes seems to not only help me get the inside/ouside of the contour , but also pave a way to implement GPU slicer for 3D model made of triangular meshes.  

---

