Project: Survey of CSG algorithms
Torsten Paul edited this page Sep 12, 2016
·
22 revisions
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.
- 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)
- Smoothing/fillets of intersection edges
- 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
- 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
Medium to High
- 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
- 3D Delaunay Triangulation on the GPU (http://www.comp.nus.edu.sg/~tants/gdel3d.html)