Survey and implement CSG algorithms

[t-paul]

Outline

Constructive solid geometry (CSG) is one of the two core modeling techniques provided by OpenSCAD. Currently, 3D CSG operations are handled using the CGAL library. 2D CSG operations are handled using the Clipper library.

There is a large number of papers about the topic of CSG and related algorithms. This project is intended to provide an overview about available algorithms, their properties and a thorough comparison.

Details

• Survey existing CSG algorithms
• Compare properties of the algorithms
• Implement prototypes that could be tested inside the OpenSCAD framework
• Evaluate how more advanced modeling techniques could be realized with each algorithm (e.g. minkowski sums, convex hulls)

Future Opportunities

• Smoothing/fillets of intersection edges
  • http://implicitcad.org
  • http://www.iquilezles.org/www/articles/smin/smin.htm

Expected Outcome

• A document/paper containing the CSG algorithm survey and how it relates to OpenSCAD-specific issues.
• One or more prototype implementations integrated with OpenSCAD to demonstrate possible improvements

Project Properties

Skills

• Programming language is C++
• Admiration for math and algorithms
• Good understanding of computational geometry
• Ability to read and understand research papers
• Systematic strategy to collect and organize information

Difficulty

Medium to High

Additional information

Mentors: Marius Kintel (IRC: kintel), Torsten Paul (IRC: teepee)

CSG Research

• http://liris.cnrs.fr/mepp/
• MEPP: Exact and Efficient Booleans for Polyhedra
• Gilbert Bernstein and Don Fussell: Fast, Exact, Linear Booleans
• Sebastian Steuer: Methods for Polygonalization of a Constructive Solid Geometry Description in Web-based Rendering Environments

Other papers

• 3D Delaunay Triangulation on the GPU (http://www.comp.nus.edu.sg/~tants/gdel3d.html)

Existing libraries or software

• Cork - by Gilbert Bernstein
• libigl - blog
• Carve (see also pyPolyCSG) (on github / a fork on github)
• OpenCASCADE (see also OCE, PythonOCC, Cadmium, CADQuery )
• CSGTool
• csg.js
• csgjs-cpp
• ThreeCSG
• Babylon.js CSG
• CSG-BSP

Related software and other resources

• http://www.plasm.net

[AnisaAisha]

Hello @t-paul, I'm interested in working on this project for GSoC. Could you please guide me where to start?

[t-paul]

As the application period is already open, I'd suggest starting a draft proposal after reviewing the starting points above. Think about how to split the time into a) review/research and what criteria would be useful and b) coding example programs. For GSoC, the coding part should be a big part of cause. With an initial draft it's easier to discuss in a more interactive way on our IRC channel.