Skip to content

[fast-csg] Custom remeshing after corefinements#4117

Merged
t-paul merged 35 commits intoopenscad:masterfrom
ochafik:fast-csg-remesh3
Mar 6, 2022
Merged

[fast-csg] Custom remeshing after corefinements#4117
t-paul merged 35 commits intoopenscad:masterfrom
ochafik:fast-csg-remesh3

Conversation

@ochafik
Copy link
Contributor

@ochafik ochafik commented Feb 12, 2022

Remeshing logic that "fixes" the results of corefinement operations to avoid an explosion of number of faces that hangs many models.

fast-csg-remesh operates as follows (needs fast-csg):

  • A corefinement visitor keeps track of faces being split and copied (as suggested by @sloriot in Add coplanar decimation CGAL/cgal#5461 (comment)), giving each face a unique patch id that's inherited over copies and splits.
  • If no face was split we skip the remeshing (note: we could force remeshing of all meshes, maybe when importing them).
  • Maximal patches of neighbouring coplanar faces are then found with a flood-fill algorithm starting from descendants of split faces + exact coplanarity tests.
  • Patches that contain holes are skipped for now
  • Patch borders are found and we mark their collapsible vertices (those between collinear edges). If exactly two neighbour patches agree, those vertices will be dropped
  • Each patch is replaced with a polygon that espouses its borders, and we let CGAL triangulate it.
  • A new mesh is created with the edits, as in-place edits seem tricky.

Note: supersedes #4107 as by design it should lead to less coplanarity tests (for many faces we know they're coplanar because we know they have a common ancestor thanks to the corefinement visitor). Also this means we're not tied to the upcoming release of CGAL.

Some examples:

Model fast-csg fast-csg + remesh baseline (nef)
condensed matter (@MichaelAtOz) 383k faces, 3min28sec 177k faces, 44sec 172k 5min31sec
PushPullFeeder (@markmaker) hangs 89k faces, 44sec 47k faces, 1min30sec
minkowski example from #4113 19k faces, 38sec 9k faces, 25sec 4min26sec

And some simpler ones:

  • This goes from 644 faces to 12:
for (i=[0:2],j=[0:2],k=[0:2])
  translate([i*0.8, j*0.8, k*0.8])
    cube(1);

image

  • This goes from 40 faces to 28
cube(1); translate([0.5, 0.5, 0]) cube(1);

Screen Shot 2022-02-21 at 02 10 20

  • This goes from 44 to 12 (instead of 12 w/ nef, which is able to figure out it's now just a "cube"):

    cube(1); translate([0.5, 0, 0]) cube(1);

image

Known limitations

…k face splits)

[fast-csg] Feature fast-csg-remesh to integrate the new CorefinementVisitor

[fast-csg] Fix code after merge

[fast-csg] Try/catch around remeshing, and track triangulation edges across splits.

[fast-csg] Let remeshing exit early if no face was split

[fast-csg] Beautified

[fast-csg] Fix const-ness of arg that breaks compilation of the delegating visitor (change of signature between CGAL 5.3 and 5.4)

[fast-csg] Implement the corefinement visitor without inheriting from the signature-changing default_visitor

[fast-csg] Only remesh patches that have >1 surviving split face

[fast-csg] Simpler remesh: replace faces with a polygon we let cgal triangulate

In-place mutation of triangule mesh looks hard to nail so creating a copy

Beautify

[fast-csg] Enable remesh in tests

[fast-csg] Only copy retained vertices in remeshing

[fast-csg-remesh] Simplified and fixed logic.

Left out coplanarity tests and patches merging.
Split the visitor from the remesher, and added support for simplifying faces to the mesh edits.
Dropped the generic visitor delegate but kept the idea.

Merge remote-tracking branch 'origin/master' into fast-csg-remesh3
Olivier Chafik added 21 commits February 18, 2022 11:46
…h sides of patch border

This fixes cases of meshes becoming unclosed after remeshing. A vertex needs exactly two "marks" to be eligible for collapsing.

Ditched removeItemsAtSortedIndices helper + refactored collapsePathWithConsecutiveCollinearEdges in the process.
@ochafik ochafik marked this pull request as ready for review February 26, 2022 13:51
@thehans
Copy link
Member

thehans commented Feb 28, 2022

Here is a case which appears to generate a number of T-junctions (or maybe just degenerate faces? It claims there are 46 facets, but I only count 32 by eye)

r = [1,1,1];
render() union() {
	rotate(r) cube();
	rotate(r) translate([0.5,0,0]) cube();
}

Tjunctions

@MichaelAtOz
Copy link
Member

2021.01 also has bad triangulation for that. Slightly different, but T's & degenerate faces.
I notice different triangulation edges display with Preview(F5) with render() <- thin lines no points, v's Render(F6) with render() <- no lines on edges, no points, Render(F6) without render() <- lines on edges & points.
The F5 before F6 v's just F6 problem, different triangulation in cache.

Olivier Chafik added 8 commits March 1, 2022 19:31
…sHalfedgeOnBorder

Required a little bit of refactoring of the single-patch logic into a helper function to ensure we add the facesProcessed at the end, success or not.

Also refactored the patch-specific data structures (previously loopLocal*) into a struct for clarity.
…erimental feature b/c it's slower!!

Benchmarked:

hyperfine -L remesh ",--enable=fast-csg-remesh,--enable=fast-csg-remesh-predictibly" "./buildRelease/OpenSCAD.app/Contents/MacOS/OpenSCAD mnk.scad --enable=fast-csg --enable=fast-csg-trust-corefinement -o out.stl {remesh}"

With mnk.scad coming from openscad#4113

Mean : 38s (Baseline), 25s (remesh), 32s (remesh-predictibly)
@t-paul t-paul merged commit 03e4edb into openscad:master Mar 6, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants