4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.