2

I am working on cutting meshes. What am I exactly trying to achieve is that:

Input - two meshes(procedurally generated of course)

Output - three meshes(or more, depends on the given meshes)

A - which is a meshA substract mesh B,

B - which is a common part of meshes A and B,

C - which is a mesh B substract mesh A.

enter image description here

I am using the Triangulator that for the given set of vertices creates triangles for me. All I have to do is to give him those vertices, and here goes the question. Is there any algorithm that would help me to do this? Maybe your brilliant idea that came into your mind at the time you saw this picture? I am working in Unity(C#) so anything related to Unity Tools is helpful aswell. Thanks !

EDIT:

I am using this clipping library: http://sourceforge.net/projects/polyclipping/ and everything works fine untill this case: enter image description here

I am trying to get the difference A-B and it should look like the one from Picture 2), unfortunately the output is mesh A and mesh B as in the picture 1).

What i do:

Clipper c = new Clipper();
c.AddPath(here goes the vertices of mesh A, polyType.Subject, true);
c.AddPath(here goes the vertices of mesh B, polyType.Clip, true);
c.Execute(ClipType.ctDIfference, a list of lists for my output, PolyFillType.NonZero, PolyFillType.NonZero);

I've already tried to change PolyFillTypes but it changed nothing. And here I am, asking for your advices :)

Power
  • 141
  • 1
  • 11
  • 1
    Is there the possibility of B being composed of multiple, separate shapes, or is it guaranteed that the two intersecting shapes in this Boolean operation will be convex? – Serlite Sep 04 '15 at 15:05
  • 1
    Have you tried anything? Post some of your code so that we can help you. – maraaaaaaaa Sep 04 '15 at 15:13
  • 1
    I have just started this. And before I code anything that will have an influence in my future work I think about it. I've heard about boolean operation working on 3D meshes but it didn't work for 2D meshes. – Power Sep 04 '15 at 15:56
  • 1
    Serlite - there is even possibility that B is going to be empty(if two given meshes are totally separated) and no, they are not going to be convex in every case as it will be used for painting the floor(You may want to have a star-based room shape) by putting new quads, fitting them to rooms they overlap and cutting already painted parts of floor so the old ones do not overlap the new one. – Power Sep 04 '15 at 16:00
  • 1
    You can try looking at [this SO question](http://stackoverflow.com/questions/2272179/a-simple-algorithm-for-polygon-intersection) to start getting an idea of how you might approach the problem. Unfortunately, determining the intersection of two polygons is usually a mathematically complex task, and I'm not sure if anyone has written a Unity plugin to do that yet. – Serlite Sep 04 '15 at 17:32

1 Answers1

2

It is enough to work with mesh boundaries. With that you have two polygons and problem of finding there intersection. Some external library can be used for it, like GPC.

After intersection is found just perform triangulation of these three polygons.

Ante
  • 5,350
  • 6
  • 23
  • 46