Slicing a 3D model?

Question

I want to slice a 3D model relative to an infinite plane(In WPF). I'm checking if edges intersect with the infinite plane. If true, I'll create a new point at the intersection position, so I'm getting a couple of points that I want to generate a cap on so that the model is closed after slicing. For example, if this is the cross section, the result would be as follows: Note: The triangulation ain't important. I just need triangles.

I also need to detect the holes as follows(holes are marked in red):

If it is impossible to do it the way I think(It seems to be so), the how should I do it? How do developers cap an object after being sliced?

There is also too much confusion. For example, The first picture's result may be: What am I missing??

---

EDIT: After some research, I knew one thing that I am missing:

The input is now robust, and I need the exact same output. How do I accomplish that??

Answer 1

As code11 said already you have too few data to solve this, the points are not enough.

Instead of clipping edges to produce new points you should clip entire triangles, which would give you new edges. This way, instead of a bunch of points you'd have a bunch of connected edges.

In your example with holes, with this single modification you'd get a 3 polygons - which is almost what you need. Then you will need to compute only the correct triangulation.

Look for CSG term or Constructive Solid Geometry.

EDIT:

If the generic CSG is too slow for you and you have clipped edges already then I'd suggest to try an 'Ear Clipping' algorithm.

Here's some description with support for holes: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

You may try also a 'Sweep Line' approach: http://sites-final.uclouvain.be/mema/Poly2Tri/

And similar question on SO, with many ideas: Polygon Triangulation with Holes

I hope it helps.

Answer 2

In the past, I have done this kind of thing using a BSP.

Sorry to be so vague, but its not a a trivial problem!

Basically you convert your triangle mesh into the BSP representation, add your clipping plane to the BSP, and then convert it back into triangles.

Answer 3

Building off of what zwcloud said, your point representation is ambiguous. You simply don't have enough points to determine where any concavities/notches actually are.

However, if you can solve that by obtaining additional points (you need midpoints of segments I think), you just need to throw the points into a shrinkwrap algorithm. Then at least you will have a cap.

The holes are a bit more tricky. Perhaps you can get away with just looking at the excluded points from the output of the shrinkwrap calculation and trying to find additional shapes in that, heuristically favoring points located near the centroid of your newly created polygon.

Additional thought: If you can limit yourself to convex polygons with only one similarly convex hole, the problem will be much easier to solve.