Project: Multi threaded geometry rendering

t-paul edited this page Sep 11, 2014 · 5 revisions

Outline

OpenSCAD uses a specialized language to describe 3D models. This description is parsed into a tree with nodes that either represent different base geometry (e.g. cube, cylinder) or operations that define how to combine child nodes (e.g. difference, intersection). This tree is then evaluated in a bottom-up fashion to produce a top-level geometry (or in the future, multiple top-level geometries; see https://github.com/openscad/openscad/wiki/OEP2:-Implicit-Unions).

The scope of this project is to enable parallel tree traversal to be able to utilize multiple CPUs to optimize processing.

Details

To create and process geometry, we use different libraries and techniques:

  • Primitives: Generated directly in C++
  • Extrusion nodes: Calculated in C++ based on 2D CSG operation of the children
  • 2D CSG operations: Calculated using the Clipper library
  • 3D CSG operations: Using CGAL's Nef polyhedrons
  • Others: 3D Convex hulls don't use Nef polyhedrons

Primitives and subtrees are also cached to avoid recalculating already processed subtrees, and to facilitate reuse of geometry multiple places in a node tree.

Challenges:

  • CGAL is not thread-safe as it uses reference counting of vertex positions. This could be possible to work around by using a slower kernel without reference counting (see issue 391).
  • The caching infrastructure needs to be updated to be thread-safe
  • Misc infrastructure (e.g. echo and I/O) needs to be evaluated in terms of thread-safeness.
  • The state of thread-safeness of Clipper is unknown

Expected Outcome

  • Support for multi-threaded evaluation, possibly with some limitations to handle non-thread-safe library calls
  • Thread safe cache infrastructure

Project Properties

Skills

  • Programming language is C++
  • Good understanding of multi-threading
  • Ability and motivation to debug difficult problems
  • Refactoring of existing code (in collaboration with core devs) may be necessary

Difficulty

High

Additional information

Github issue: https://github.com/openscad/openscad/issues/391