9

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: Example result Note: The triangulation ain't important. I just need triangles.

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

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: Confusion What am I missing??

EDIT: After some research, I knew one thing that I am missing: enter image description here

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

None
  • 609
  • 7
  • 22
  • 1
    I'm not sure I entirely understand what you are after. Do you mean cutting a model like this? http://www.mathalino.com/sites/default/files/images/conic-sections_0.jpg – Chairs Jan 05 '17 at 20:52
  • 1
    If you are just after a visual effect, I could probably whip up a shader for you. – Chairs Jan 05 '17 at 20:53
  • 1
    I need the geometry to be modified @Chairs . The result will be 3D printed. – None Jan 05 '17 at 21:05
  • 1
    How do you define the border and the holes? Just some points cannot be used to determine that. – zwcloud Jan 06 '17 at 03:16
  • 1
    I do raycasting along the cutting plane – None Jan 06 '17 at 08:12
  • This kind if algorithm is straightforward (I won't say easy) if you have the right representation of the model object to start. For this, something like winged-edge data structure is needed. See for example: https://people.cs.clemson.edu/~dhouse/courses/405/papers/winged-edge.pdf . Another point is that algorithms like this can be hellishly difficult to get correct with floating point math. Strongly consider integer or fixed point coordinates and arbitrary precision rational arithmetic. – Gene Jan 14 '17 at 19:48

3 Answers3

5

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.

Leo Bartkus
  • 1,925
  • 13
  • 17
5

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.

Community
  • 1
  • 1
kolenda
  • 2,741
  • 2
  • 19
  • 30
2

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.

code11
  • 1,986
  • 5
  • 29
  • 37