Skip to content

Blazingly fast rendering using Polygon Mesh Processing when possible#3641

Closed
ochafik wants to merge 151 commits intoopenscad:masterfrom
ochafik:fast_csg
Closed

Blazingly fast rendering using Polygon Mesh Processing when possible#3641
ochafik wants to merge 151 commits intoopenscad:masterfrom
ochafik:fast_csg

Conversation

@ochafik
Copy link
Contributor

@ochafik ochafik commented Feb 2, 2021

Experimental fast-csg feature for 10x faster rendering (or more... or less :-D) of lots of challenging models (see some benchmarks here)!

This PR introduces the class CGALHybridPolyhedron, a lazy hybridization of CGAL::Polyhedron_3 / CGAL::Surface_mesh (using corefinement functions for CSG ops) and CGAL::Nef_polyhedron_3 (as a fallback for cases not supported by corefinement functions).

As mentioned by @thehans, CGAL's Polygon Mesh Processing libraries (PMP) provide much faster CSG operations (union, intersection, difference) than the Nef polyhedron. Unfortunately, they also have strict input requirements: any shared vertices edges between two unioned polyhedra or mis-oriented faces and they just bail out.

This PR has being chunked and sent as separate PRs, now available in nightly builds. This blog post summarizes the process and some next steps:

Known / open issues:

Some notes:

  • The grid is gone (it's still there for minkowski operations, though, which only indirectly use the new code paths).
  • Currently requires CGAL 5.1+ (because Polyhedron_3 + corefinement doesn't work well together before) but compiles fine with older versions (the fast-csg feature is then compiled away). A new github CI workflow builds and tests with various versions of CGAL (fast-csg-specific tests are disabled when its' not available). Now that there's a Surface_mesh codepath, might be able to lower the CGAL version requirement: stay tuned!
  • Weird performance of Lazy numbers from Epeck kernel is mitigated by calling CGAL::exact as suggested by @sloriot in this thread. In general, calling that after transforms, corefinement operations and upon conversion from nef to polyhedron/surface mesh, but in the case of surface meshes I'm calling exact during corefinement after a face is done being split up (which creates new numbers) rather than after. This makes some rare models faster.
  • The hybrid polyhedron uses a different kernel (CGAL::Epeck) than the current nef. After CGAL 5.2, it's possible to use the same kernel, to saves many conversions (and memory for the nef fallback cases). The switch is done automatically based on the version of CGAL. The 5.2.x behaviour (w/ x > 0) isn't tested in CI yet as the 5.2.x branch isn't building out of the box on Ubuntu 18.04 (boost version issue?) and CGAL 5.2.1 hasn't been released yet.
  • Altered some signatures to return shared pointers
  • Generalized a few existing utils so they can operate on the CGAL::Epeck kernel (which seems, with its inaccurate Epick sibling, to be the only kernels that work well with PMP's corefinement functions until after 5.2.0)
  • Made sure to split the object files into many cgalutils-* so this builds fine in all environments with older GCC or limitations of RAM
  • No more green display on faces that result from differences. Tests which expectations have rightly changed because of that are run with and without the feature so they can run with binaries that lack the feature.
  • Using PMP::orient_to_bound_a_volume as PMP::orient can leave polyhedra corrupted (will attempt to file a reproductible bug to CGAL)
  • The initial code adapted from Optimize disjointed unions & differences (+ introduce caching of costly nef<->polyset conversions) #3636 was trying also detects fast-union cases by keeping track of the bounding boxes of unioned bodies (and then just concatenate disjoint polyhedra). It doesn't seem this beneficial with corefinement anymore, it had some annoying quadratic time search and needed reimplementing for surface meshes (Iso_cuboid3 sharing a single vertex don't seem to count as intersecting, but dumb concatenation of surface meshes doesn't work in that case: vertices need to be unique)

Future work:

  • Simplify facets after corefinements once Add coplanar decimation CGAL/cgal#5461 lands (thanks @rcolyer for spotting increase, e.g. cube(1); translate([0.5, 0, 0]) cube(1); goes from 6 (12 triangles) to 44 (before, after)
  • Fix the few remaining tests that I couldn't enable fast-csg on (they're still run without the feature, see annotated list in tests/CMakeLists.txt), and generally address bug reports from users
  • Edit: tried it, there's no point / that's not where the time is spent. Have a version of minkowski with the new kernel (the "native" nef minkowski is already wired, but not the custom alternative from CGALUtils, which currently incurs unnecessary conversions)
  • Abandon CGAL::Polyhedron_3 to only use CGAL::Surface_mesh. It's definitely faster!
  • Wireframe rendering? Currently CGALHybridPolyhedron is converted to a PolySet at GeometryEvaluator's root.
  • Retire CGAL_Nef_polyhedron and use a single kernel to rule them all
  • CGALHybridPolyhedron::dump

Olivier Chafik added 4 commits February 2, 2021 22:45
…ing CGAL packages (*massive* speedup)

Uses blazing fast PMP csg operations, with in-place updates as much as possible.

Detects non-manifold meshes not handled by PMP and reverts back to Nefs (to avoid costly checks, convex polysets are trusted, but also introduced --enable=trust-manifold to allow speedups on large STL imports, for instance).

Also includes "fast-union" trick introduced in openscad#3636 (concatenate disjoint bodies)

Speed improvements in the 10x to 100x range for my various grid patterns.

More improvements to come when Polyhedron will become a Geometry subclass (should be able to cache a read-only version of them), and chain CSG operations instead of converting to PolySet as currently done.
@thehans
Copy link
Member

thehans commented Feb 2, 2021

Linking to original issue #2360 for reference.

Olivier Chafik added 24 commits February 3, 2021 00:32
… earlier versions)

Most of the functionality still seems possible in 4.x (e.g. is_non_manifold_vertex available from 4.14), but that's too many hoops to go through for this initial version.
…ate_non_manifold_vertices

instead of quadratic calls to PMP::is_non_manifold_vertex
Difference sped up by union their subtracted terms.
Exact mode converts to Nefs instead of PolySet. It's transitional as the new poly class will soon become a Geometry, so conversion will only happen at the top of the visitation
Also, handle CGALPolyhedron in createNefPolyhedronFromGeometry
Also, a few helpers:
- ResultObject.asMutableGeometry
- Geometry.{transform, resize}
Note that GeometryEvaluator force-converts to PolySet at the root level for now, for higher compatibility w/ exports
@ochafik
Copy link
Contributor Author

ochafik commented Feb 9, 2022

This is now mostly all in from other PRs, time to close this one! (see high-level summary in this blog post)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants