Nesting order of quality?

[jbergen]

As I understand it, the nesting function is supposed to sort the solutions in order of quality (best first).
Is the sorting broken, or am I missing something?
See the attached results for example.
Why are solutions that were unable to place all the parts valued at a higher quality than those with all parts placed?
Why are solutions that use more surface area considered a higher quality?

It would make more sense to me if the sorting was done by Not Placeable first, followed by Size, both sorted low to high.
Or maybe add the ability to use the column headers to choose the sorting order.

Nesting_001.png (110.95 KiB) Viewed 2254 times

[CVH]

Hi,

This doesn't seems to be right ...
Is it possible to add the source document for testing?

Please indicate your OS and QCAD/CAM version.
Please list your Application Preferences for CAM .. Nesting and the used tool Options.

Size is probably a bounding box around all placed items and may include voids.
Not placed = zero should indeed be a better solution than not placed some.
Next goal should be more compact based on total area of all pieces vs area of bounding box.

From your list it seems that the weight of some solution parameter if off.

Regards,
CVH

[jbergen]

Certainly. Happy to do so.

QCAD/CAM version = 3.29.3.0
OS = Linux Mint 21.3
Laptop = Dell Inspiron 5559 CPU I7

In Application Preferences > CAM > Nesting I have
Number of threads = Auto
Maximum number of iterations = 1000
Weighting of primary alignment = 1.0
Hull resolution for blocks = 20
Place small parts into holes of other parts = checked
Align part angles to axis = unchecked

My nesting parameters are:
Quantity multiplier = 1
Rotations = 4
Sheet Margin = 12
Margin = 12
Tolerance = 1
Alignment = Left-Bottom
Strategy = Hull

To reproduce:
open attached dxf file
box select all parts on the left
Menu: CAM > Nesting
Enter nesting parameters as per above
Click each of the 3 rectangles on the right (they represent three 4x8 sheets of plywood)
Right click to start nesting

[andrew]

Please set the nesting strategy to "Align" instead.
The "Hull" algorithm is indeed flawed and will likely be removed from future versions.

[CVH]

Not really convinced.
Although I have limited access to QCAD/CAM using a trial version ...
I still see the "Align" strategy lists results with fewer placed parts higher in the list.

One thing that throws me off is that nesting starts with calculating xxxx NFPs (No-Fit Polygon).
The value of xxxx varies: 7528, 4887, 5099, 4928, 5593 .... And that every time I start over new with the downloaded file.

As far as I know:
- An NFP is something between two shapes and most of the basic NFP algorithms only use polygons.
- The NFP from shape A around shape B and that of B around A are identical but rotated 180 degrees.
- We can thus base the number of NFPs to be defined on combinations rather than on permutations.
And then I would presume that the combinations of 2 from N parts must be even and a fixed value ...

I know that a selection of multiple drawing entities is ordered at random but that should not make a difference for the number of combinations.
And then I see several nesting algorithms sorting parts based on size.
QCAD reports 64 parts, some have holes and many of these are polylines with bulging segments.
In 7 of the 16 holes the smallest parts (B2") can't be fitted with a margin of 12.
Holes can be treated as extra free space, as extra sheets what results in 12-19 sheets.

But then it should be even more complicated than plain combinatoric, pre-aligning is turned off but Rotations = 4.
Meaning that each part may be rotated 3 times 90 degree independent of all other and that would influence the NFP for any combination.
But C(64x4, 2) = 32640 and that makes no sense ...?!
Once a single piece is placed in a trial the free area changes what would influence the placement of all others.
Something as 'inner NFPs'.


@ jbergen:
The calculation time suffers mostly from quite complicated and especially from curved shapes.
For example: 'STERN' has 397 vertices and the NFP with a simple shape like 'CASE' has already 419 vertices.
Let's take C(64 ,2) = 2016 times an average of 200 vertices and we are talking about over 400k vertices.
There are segments less than 1.8mm long for an overall size of 4.4 meter.
Is there a sound reason why the parts are described in such fine details?
See App.Prefs. .. Modify .. Explode for the preferences of the Explode (XP) method.

May I remark that the larger parts 'B2' are not closed polylines, the gaps are just over 0.20... large (See near red start marker).

Some parts are not fully symmetrical.
These curved polylines probably originate from splines and then the orientation may matter when exploding to polylines.
This is because bi-arc fitting is not preformed optimal, QCAD halts refining when it meets the tolerance condition.
I would mirror the resulting polylines from one half and merge them together.

I also note that there are already 3 text entities on the bottom sheet.
Wondering why the panels are 1.6 shorter and 0.8 narrower than standard imperial size panel.
The sheet size accuracy would not matter with a 12 units margin or is there another reason ...

I took the liberty to use 2-3 of your shapes for another test:
https://www.qcad.org/rsforum/viewtopic. ... 489#p43489

Regards,
CVH

[jbergen]

CVH
Thank you, this is excellent information.

I was unaware of the App.Prefs>Modify>Explode setting and what it does. It was set to the default of 0.01. I noticed that converting splines to polylines was creating a huge number of vertices but I didn't know how to change that. Now I do, thank you! There is no need for such a high level of precision for the splines on this wooden boat. There is for the puzzle joints on the bow & stern panels, but they are arcs not splines. I increased the setting from 0.01 to 0.50 and that reduced the number of vertices in Stern from 397 to 41. I replaced all of the splines in the model accordingly.

I closed the gaps in B2. My mistake. It's easy to overlook gaps that small, or is there a way for Qcad to find them? I also missed deleting the 3 text entities on the bottom sheet when I deleted a previously unwanted nesting.

These changes sped up Nesting noticeably.

B3, and some other parts are not symmetrical by design.

The panels measure 1219.2 x 2438.4 mm or precisely 4x8 ft since I'm in the US. I didn't round them off to 1220 x 2440 as is typically done elsewhere.

I'm attaching the updated dxf file if additional testing is desired.

andrew
I changed the Nesting Strategy from Hull to Align and got much better results. It produced way more results with no unplacable parts, produced them more quickly, and the sorting quality is much better. I'll be using Align from now on.

The sorting quality is also vastly improved when using Align. There are still instances where a solution with more unplacable parts or a larger size was rated higher quality than one with fewer unplacable parts or a smaller size. I don't know how the algorithm determines "quality" or size. If you're open to suggestions, I would suggest that clicking on the column headers of #, Size, and Not Placeable would sort the solutions by that column, and that the # column indicates the quality (#1 is highest quality).

Workspace 1_003.png (348.93 KiB) Viewed 1991 times

[CVH]

Hi,
Glad to help you out.
The calculation speed gain is mostly the result of the simplified design of the parts.
Also beneficially in a later CAM stage there an offset of very short tangentially connected arc segments may mathematically fail.
(https://www.qcad.org/rsforum/viewtopic. ... 152#p41472)

With non-symmetric I pointed to the polylines originated from splines in the older version.
E.g. the 'STERN' and the 'BOW' part seen along the axis of the model.
Best noticeable at the wider part near the 'puzzle' joint.
Or the top side of part 'B1' ... 50 arcs at the left side and 46 at the right while the length is practically the same.

... or is there a way for Qcad to find them?

Not really but there are methods ...
First, if you use Polyline from Selection (OC) to merge segments together it will be logically closed when the result is geometrically closed.
So when you expect a closed shape with OC then the 'Closed' property of the resulting polyline would be 'Yes'.
The OG method does not logically close if so.

Second, OG has a connection tolerance option and it will consider things being connected when the gap is smaller.
A word of caution: It does not trim pair-wise, it simply moves one endpoint so it coincides with the other.
Depending the situation this fast fix might distort the part at that position.
The OC method tolerance and gap closing preference can be found under App.Prefs. .. Draw .. Polyline from Selection
Same word of caution + The gap closing segment may induce a path jump and that will be more pronounced when larger.

One can also look for logically open polylines with the Selection Filter ... menu View .. Selection Filter (GF).
The method I prefer because then I can decide myself how to close the gap.

Regards,
CVH