Merge branch 'main' into perf/slicing-optimizations

Keep the G-code identical to main on Clipper2
Since main moved to Clipper2, parts of this branch no longer gave the same G-code as main: - bridge_over_infill dropped expand(limiting_area, 0.3 * flow.spacing()) as a no-op. The offset is below one unit, but Clipper2 still unites its result, which splits and merges touching polygons and so changes the anchor lines. Running it on the polygons next to the bridge gives main's anchors without the whole-layer pass. - tsp_remove_crossings stopped at the first repeated ordering, where main runs on to its pn * pn cap. The loop is periodic from that point, so it now takes only the steps to the ordering main stops on. - With a single tile, the tiled booleans now make the plain call instead of cutting the clip to the tile first. The tiled boolean test compared rings exactly. With the safety offset a tile unites only the clip polygons near it, and Clipper2 can then round a crossing 1 unit differently, so that case allows 1 unit. Comments that named ClipperLib now say Clipper, and docs/HLSD/polygon-clipping.md describes the tiled booleans. G-code of the five handy models in four configurations and of a baked texture relief is byte-identical to main. Colour-painted models still differ: segmenting each island on its own splits a colour's region into different pieces than one diagram over the layer, which on one model also changes the first layer's tool order.
2026-10-04 14:20:58 +00:00 · 2026-10-03 10:57:31 -03:00 · 2026-10-02 20:26:59 -03:00 · 2026-10-02 18:13:46 -03:00 · 2026-10-02 18:13:46 -03:00 · 2026-10-02 18:13:46 -03:00
986 changed files with 2302041 additions and 2303812 deletions
@@ -62,6 +62,23 @@ Clipper2 behaves differently by default, the wrapper adjusts it.
  clip do not leave slivers.
 - Open polylines are clipped with the non-zero rule and keep their direction.

+### Tiled booleans
+
+The sweep slows down with the number of edges crossing a scan line, so a layer
+cut into thousands of pieces makes every whole-layer boolean expensive.
+`diff_ex_by_piece()` and `intersection_ex_by_piece()` take a subject of
+non-overlapping `ExPolygons`, group them into tiles with
+`ClipperUtils::tile_expolygons()`, and run each tile in parallel against only
+the clip polygons near it, cut to the tile's box. Below 128 pieces there is a
+single tile, and they are the plain `diff_ex()` / `intersection_ex()`.
+
+The result covers the same area as the plain call. Without the safety offset
+the rings are the same. With it, each tile unites only the clip polygons near
+it, so a clip edge that the whole-layer union splits where it crosses a distant
+clip polygon stays whole, and a crossing with the subject can round 1 unit
+differently. The tiles' results are concatenated in tile order, so the order of
+the output `ExPolygons` differs from the plain call.
+
 ### Offsets

 - Before offsetting, input vertices closer than
@@ -1,323 +1,323 @@
 {
-	"result": 0,
-	"t": 1765968095,
-	"ver": 202511162200,
-	"data": [
-		{
-			"ecode": "03008041",
-			"image": "",
-			"actions": [
-				4,
-				6
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "03008060",
-			"image": "",
-			"actions": [
-				22
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "12008010",
-			"image": "c31daf51b36e446698f14c6df879ea21.png",
-			"actions": [
-				6,
-				4
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "12FF8010",
-			"image": "f87557495f2f2163a44bde8f4ddd9b8c.png",
-			"actions": [
-				4,
-				6
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "18008016",
-			"image": "",
-			"actions": [
-				4,
-				6
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "07008016",
-			"image": "",
-			"actions": [
-				4,
-				6
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "07018016",
-			"image": "",
-			"actions": [
-				4,
-				6
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "03002E0000030001",
-			"image": "",
-			"actions": [
-				52
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "03004016",
-			"image": "",
-			"actions": [
-				6
-			],
-			"device": "26A"
-		},
-		{
-			"ecode": "03008019",
-			"image": "",
-			"actions": [
-				4
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0502C026",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004003",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004040",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004042",
-			"image": "",
-			"actions": [
-				36,
-				37
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "03008000",
-			"image": "",
-			"actions": [
-				2
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0C00402D",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004037",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004015",
-			"image": "",
-			"actions": [
-				14
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004007",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0502C014",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0300800C",
-			"image": "",
-			"actions": [
-				2
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004004",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0500402E",
-			"image": "",
-			"actions": [
-				14
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05024001",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0502C012",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0502C010",
-			"image": "",
-			"actions": [
-				35
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05008092",
-			"image": "",
-			"actions": [
-				27,
-				5
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004014",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0300800D",
-			"image": "",
-			"actions": [
-				2,
-				6
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0500402F",
-			"image": "",
-			"actions": [
-				14
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004041",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0500400E",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "05004043",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "0C00402C",
-			"image": "",
-			"actions": [
-				11
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "03008017",
-			"image": "",
-			"actions": [
-				4
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "03008013",
-			"image": "",
-			"actions": [
-				2
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "03008007",
-			"image": "",
-			"actions": [
-				2,
-				5
-			],
-			"device": "default"
-		},
-		{
-			"ecode": "03008016",
-			"image": "",
-			"actions": [
-				4,
-				5,
-				6
-			],
-			"device": "default"
-		}
-	]
+    "result": 0,
+    "t": 1765968095,
+    "ver": 202511162200,
+    "data": [
+        {
+            "ecode": "03008041",
+            "image": "",
+            "actions": [
+                4,
+                6
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "03008060",
+            "image": "",
+            "actions": [
+                22
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "12008010",
+            "image": "c31daf51b36e446698f14c6df879ea21.png",
+            "actions": [
+                6,
+                4
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "12FF8010",
+            "image": "f87557495f2f2163a44bde8f4ddd9b8c.png",
+            "actions": [
+                4,
+                6
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "18008016",
+            "image": "",
+            "actions": [
+                4,
+                6
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "07008016",
+            "image": "",
+            "actions": [
+                4,
+                6
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "07018016",
+            "image": "",
+            "actions": [
+                4,
+                6
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "03002E0000030001",
+            "image": "",
+            "actions": [
+                52
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "03004016",
+            "image": "",
+            "actions": [
+                6
+            ],
+            "device": "26A"
+        },
+        {
+            "ecode": "03008019",
+            "image": "",
+            "actions": [
+                4
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0502C026",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004003",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004040",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004042",
+            "image": "",
+            "actions": [
+                36,
+                37
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "03008000",
+            "image": "",
+            "actions": [
+                2
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0C00402D",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004037",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004015",
+            "image": "",
+            "actions": [
+                14
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004007",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0502C014",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0300800C",
+            "image": "",
+            "actions": [
+                2
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004004",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0500402E",
+            "image": "",
+            "actions": [
+                14
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05024001",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0502C012",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0502C010",
+            "image": "",
+            "actions": [
+                35
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05008092",
+            "image": "",
+            "actions": [
+                27,
+                5
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004014",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0300800D",
+            "image": "",
+            "actions": [
+                2,
+                6
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0500402F",
+            "image": "",
+            "actions": [
+                14
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004041",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0500400E",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "05004043",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "0C00402C",
+            "image": "",
+            "actions": [
+                11
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "03008017",
+            "image": "",
+            "actions": [
+                4
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "03008013",
+            "image": "",
+            "actions": [
+                2
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "03008007",
+            "image": "",
+            "actions": [
+                2,
+                5
+            ],
+            "device": "default"
+        },
+        {
+            "ecode": "03008016",
+            "image": "",
+            "actions": [
+                4,
+                5,
+                6
+            ],
+            "device": "default"
+        }
+    ]
 }
--- a/Show More
+++ b/Show More
Author	SHA1	Message	Date
Rodrigo Faselli	b6140110f2	Merge branch 'main' into perf/slicing-optimizations	2026-10-03 10:57:31 -03:00
Ian Bassi	7b0e2f3ce5	Keep the G-code identical to main on Clipper2 Since main moved to Clipper2, parts of this branch no longer gave the same G-code as main: - bridge_over_infill dropped expand(limiting_area, 0.3 * flow.spacing()) as a no-op. The offset is below one unit, but Clipper2 still unites its result, which splits and merges touching polygons and so changes the anchor lines. Running it on the polygons next to the bridge gives main's anchors without the whole-layer pass. - tsp_remove_crossings stopped at the first repeated ordering, where main runs on to its pn * pn cap. The loop is periodic from that point, so it now takes only the steps to the ordering main stops on. - With a single tile, the tiled booleans now make the plain call instead of cutting the clip to the tile first. The tiled boolean test compared rings exactly. With the safety offset a tile unites only the clip polygons near it, and Clipper2 can then round a crossing 1 unit differently, so that case allows 1 unit. Comments that named ClipperLib now say Clipper, and docs/HLSD/polygon-clipping.md describes the tiled booleans. G-code of the five handy models in four configurations and of a baked texture relief is byte-identical to main. Colour-painted models still differ: segmenting each island on its own splits a colour's region into different pieces than one diagram over the layer, which on one model also changes the first layer's tool order.	2026-10-02 20:26:59 -03:00
ExPikaPaka	d80c69341c	Say what the code does, not what it replaced The timings and the runs that never finished belong in the commit messages, where they can be read against the change; a reader of the code cannot check them. Kept the cost that still explains the design. MultiPoint also spells out the consequence: a moved-from Polygon or Polyline is now really empty where it used to silently keep its points. The two wall spacing comments the parallel loop reindented are plain ASCII now, so the whole file is.	2026-10-02 18:13:46 -03:00
ExPikaPaka	4a63a7d916	Compare the tiled booleans polygon by polygon Area alone would pass on a result whose pieces were merged across tiles or which kept the cut edges of the clip. The rings are compared after rotating each to its lowest point and sorting, so only the ordering is free. The fixture now also asserts it really is split into more than one tile, which is the path being tested.	2026-10-02 18:13:46 -03:00
ExPikaPaka	de1dfd0611	Hand the island's walls over instead of copying them append(const ExtrusionEntity &) clones; the collection each island produced was deep-copied into the layer's loops and then thrown away. The no-overlap areas are moved as well.	2026-10-02 18:13:46 -03:00
ExPikaPaka	11a5971cef	Include what the new code uses The Windows build stopped on test_kdtree.cpp: it calls std::iota without including <numeric>, which libstdc++ happens to pull in anyway. Added there, and the same for <limits> and <algorithm>/<cmath> where the recent changes rely on them being included by something else.	2026-10-02 18:13:45 -03:00
ExPikaPaka	82f37ddb3a	Fix the Windows build: near and far are macros there bridge_over_infill's helper for splitting polygons by proximity named its locals near and far. The Windows headers define both as macros that expand to nothing, so "Polygons near;" declared nothing and the uses of it did not compile. Renamed; no behaviour change.	2026-10-02 18:13:37 -03:00
ExPikaPaka	fb03d1a1cb	Visit seam candidates as the search finds them Collecting every candidate within the radius into a vector cost more than the search itself. Same order, so the seams are unchanged; align_seam_points ~19.6 s at 0.1 mm / 2000k, was ~21.	2026-10-02 18:13:37 -03:00
ExPikaPaka	2b4bdead73	Run a layer's regions in parallel where they are independent detect_surfaces_type, process_external_surfaces and the vertical shells each waited on their own heaviest layer in turn. The LOTR map plate slices in ~10.5 min at 0.1 mm / 2000k, was ~11.5; ~87 s at normal settings, was ~97.	2026-10-02 18:13:37 -03:00
ExPikaPaka	b1f0d6c6f6	Move polygons instead of copying them on move MultiPoint had no rvalue constructor, so the derived move constructors bound to the const reference and copied; append reserved exactly, so collecting pieces one by one was quadratic. Colour segmentation ~3 s at 0.1 mm / 2000k, was ~40, and ordinary prints gain too.	2026-10-02 18:13:37 -03:00
ExPikaPaka	14751a8b06	Project painted faces onto the shell layers per tile Only the slices within the deepest shell offset decide the result, so the work is done per tile of the face. Top and bottom segmentation ~130 s at 0.1 mm / 2000k, was ~180.	2026-10-02 18:13:36 -03:00
ExPikaPaka	9a86d79038	Tile the booleans on layers of many pieces ClipperLib slows down with the number of edges on a scan line, and a layer cut through a fine relief has tens of thousands of pieces. detect_surfaces_type ~50 s at 0.1 mm / 2000k, was ~145.	2026-10-02 18:13:05 -03:00
ExPikaPaka	d905f1a39b	Merge colour and top/bottom regions per island The merge took anything from 3 to 38 minutes at 0.1 mm / 2000k, now ~2.5. Every region is grouped with the islands it overlaps, so the result is the same.	2026-10-02 18:12:41 -03:00
ExPikaPaka	84ec518f26	Slice fine texture relief without stalling A colour texture baked at 0.1 mm / 2000k made the top layers thousands of islands and slicing never finished. Colour segmentation runs per island, the merge subtracts piece by piece, the support check tests only nearby islands, and the travel ordering finds crossings through a grid.	2026-10-02 18:12:41 -03:00
ExPikaPaka	1fc153308f	Generate walls and split solid infill in parallel Same output, ~2.2 min for the LOTR map plate, was ~2.6.	2026-10-02 18:12:41 -03:00
ExPikaPaka	3167c3665a	Run colour segmentation and vertical shells in parallel Same output, ~2.6 min for the LOTR map plate, was ~2.9.	2026-10-02 18:12:40 -03:00
ExPikaPaka	6d34d83e78	Faster slicing of colour-painted layers A layer split into ~1000 colour fragments (a colour texture baked over a large top face) made several per-fragment loops redo whole-layer ClipperLib work, so slicing took ~33 min; it now takes ~3 min with the same output. - make_fills: clip the layer's no-overlap area to each expolygon's box before intersecting - discover_vertical_shells: small-piece filter compares only against the nearby part of the layer - bridge_over_infill: whole-layer union/diff/intersections restricted to the candidate's neighbourhood; fill boundary expanded once per spacing; anchor tree built only from lines crossing the scan range; bbox pre-check in the collision test; limiting outline taken directly instead of through expand(..., 0.3 * flow.spacing()), which offsets by 0.135 scaled units (flow.spacing() is in mm) and only cost a whole-layer pass per candidate	2026-10-02 18:11:17 -03:00