5

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

sajis997
  • 1,279
  • 1
  • 10
  • 15

1 Answers1

3

In general, I recommend the book Real-Time Collision Detection.

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.
IneQuation
  • 892
  • 4
  • 10
  • Yes this tracing works, but if the object was sealed in the first place wouldt the contour have a sidedness? – joojaa Apr 14 '16 at 09:17
  • 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 Apr 14 '16 at 09:23
  • 1
    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 Apr 14 '16 at 09:43
  • 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 Apr 14 '16 at 10:37
  • 1
    that's whats i was alluding winding rules can handle this for you but tracing is less work. – joojaa Apr 14 '16 at 10:40
  • 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 Apr 23 '16 at 13:04