Boolean operations on Meshes

[GoogleCodeExporter]

Some people think it's a good idea...
First step would be to create an uniformized software vertices/indices buffer 
and have every mesh generator output to it.

Original issue reported on code.google.com by michael.broutin@gmail.com on 11 Oct 2010 at 9:49

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Original comment by michael.broutin@gmail.com on 8 Nov 2010 at 8:51

• Changed title: Boolean operations on Meshes
• Added labels: Priority-Low
• Removed labels: Priority-Medium

[GoogleCodeExporter]

Original comment by michael.broutin@gmail.com on 1 Feb 2011 at 2:11

• Added labels: Difficulty-Hard

[GoogleCodeExporter]

I imagined an algorithm for that... I still need to implement it.

Here are the main steps :
- find all intersection segments between mesh 1's triangles and mesh 2's 
triangles
- retriangulate triangles that have been intersected
- group intersection segments to create "contours"
- for each contour, determine which side of it should be kept and which side 
should be discarded (depends on whether it's an intersection, union...)
- use adjacency information on the triangles to propagate from one contour to 
another

Original comment by michael.broutin@gmail.com on 29 May 2012 at 8:39

• Changed state: Started
• Added labels: Priority-Medium
• Removed labels: Priority-Low

[GoogleCodeExporter]

Step 1 implemented (finding intersections)

Original comment by michael.broutin@gmail.com on 1 Jun 2012 at 9:37

[GoogleCodeExporter]

Algorithm is fully implemented, but a lot of cases lead to infinite loop.
Next things to fix :
- Triangulate correctly even with 2 identical vertices.
- Triangulate correctly even with 3 aligned vertices. (in particular with the 
addconstraints phase)

Original comment by michael.broutin@gmail.com on 5 Jul 2012 at 11:45

[GoogleCodeExporter]

Got another handful of tests working.
Trying to recreate this test case : 
http://en.wikipedia.org/wiki/File:Csg_tree.png
But:
- Cylinder U Cylinder doesn't work when both cylinder have same size. This is 
because the progression is blocked by the two joined intersections.
- Box - (Cylinder U Cylinder) leads to infinite loop, got to figure out why.

Original comment by michael.broutin@gmail.com on 15 Oct 2012 at 7:46