ezdxf + nesting optimizer?

[danbst]

What are ezdxf-based nesting (bin packing) optimizers?

Sorry if question is dumb, I'm very new to lasercutting.

[mozman]

Ezdxf is not a lasercutting library, I don't even know what "bin packing" is.

[danbst]

In lasercutting there is a common preprocess step to optimize layout of shapes in DXF file, so empty space (wasted space) is minimized. There are already libraries for optimizer algorithm (https://github.com/tamasmeszaros/libnest2d) and webservices for SVG (https://github.com/Jack000/SVGnest).

But they don't support DXF, which is used for lasercut.

[mozman]

This problem is not related to the file format and ezdxf has no solution for that.

I don't know if libnest2d has a python binding. What I see from the front page is that the solver expects polygons made of 2d vertices as input and returns polygons which hopefully also consist of 2d vertices. Your remaining task is the conversion between data formats.

[danbst]

I found that libnest2d has 2 bindings https://github.com/Ultimaker/pynest2d and https://github.com/markfink/nest2D (different licenses).

Okay, I'll try to combine one of those with ezdxf, though I have to dig deep into dxf first... As I have to handle "holes" (shapes in shapes) and "engraving layer" shapes...

[mozman]

I was interested to test this packages but I cannot install any of them, there are not pre-build packages on PyPI.

I found another (very basic) solution in pur Python py3dbp which can be installed by pip install py3dbp, with only one drawback: the solution is not what I expected:

Source entities:

Packed Items:

I add my code and the test DXF file, maybe it is a starting point for you. It shows how to get the bounding box of DXF entities and how to translate and rotate them from the source to the target location. For more sophisticated solutions look at the disassemble module, which can convert most entities into path-like objects and this path objects can be flattened into polygons as list of vertices.

binpacking.zip

[danbst]

I'm going to check your solution, but first I'll share what I've got.

My testbed DXF is this: case.dxf.txt. It is built mostly of splines.

I was able to use pynest2d. Here is my result code. I draw with turtle, simply because I know it :)

import ezdxf
from pynest2d import Item, Point, Box, nest
import turtle

def getitems(filename, scale=1):
    dxf = ezdxf.readfile(filename)
    msp = dxf.modelspace()
    items = []
    for e in msp:
        points = []
        if e.dxftype() == "LINE":  # TODO: this seems to be wrong
            points = [ (e.dxf.start[0], e.dxf.start[1]), (e.dxf.end[0], e.dxf.end[1]) ]
        elif e.dxftype() == "SPLINE":
            points = [(p.x, p.y) for p in list(e.flattening(0.1))]
        else:
            continue
        item = Item([Point(p[0]*scale, p[1]*scale) for p in points])
        items.append(item)
    return items


def drawbin(items, binid=0, scale=1):
    """ draw items from specific bin """
    for item in items:
        if item.binId() != binid:
            continue
        sh = item.transformedShape()
        turtle.penup()
        first = sh.vertex(0)
        turtle.goto(first.x()/scale, first.y()/scale)
        turtle.pendown()
        for i in range(sh.vertexCount()):
            p = sh.vertex(i)
            turtle.goto(p.x()/scale, p.y()/scale)
    turtle.update()

items = getitems('/home/danbst/code/drawings/case.dxf')
nestbin = Box(600, 400)
DIST = 10

bincount = nest(items, nestbin, DIST)

turtle.tracer(100)
drawbin(items)

turtle.mainloop()

The result is MEH.

First, I still have to find out how to manage "holes" in shapes. And second, it just doesn't place them correctly :) Don't know why yet.

[mozman]

Unfortunately there is no easy way to install pynest2d on Windows (no pre-build wheel on PyPI, no Anaconda package), there isn't even a debian package for Ubuntu available, so I can't verify your solution.

I wouldn't and won't invest a lot of time in a solution that depends on a package that's so difficult to install. And the documentation is also very shallow!

[danbst]

Also, this would be helpful for OpenSCAD, when used with lasercut module. It can layout shapes into DXF file, but usually not very compact.
https://github.com/bmsleight/lasercut#automatically-generate-files-ready-for-laser-cutter

[mozman]

The package py3dbp seems to work most of the time but is not very efficient.

This is the improved version of my script, which shows how to bundle contours and holes, but the results are not very reliable. The "fast bounding box" algorithm to detect holes works for most "usual" cases but not for extreme edge cases:

Result for bigger_first=True strategy

Result for bigger_first=False strategy

from typing import Iterable, List
import math
import ezdxf
from ezdxf.entities import DXFGraphic
from ezdxf.math import Matrix44, BoundingBox
from ezdxf.path import Path, make_path, nesting

import py3dbp
from py3dbp.constants import RotationType

UNLIMITED = 1_000_000
DEPTH = 1
WEIGHT = 0


class Bundle:
    def __init__(self, entities: List[DXFGraphic], box: BoundingBox):
        self.entities = entities
        self.bounding_box = box

    def transform(self, m: Matrix44):
        for e in self.entities:
            e.transform(m)

    def __str__(self):
        return ", ".join(str(e) for e in self.entities)

    def set_properties(self, layer: str, color: int):
        for e in self.entities:
            e.dxf.color = color
            e.dxf.layer = layer


def build_bundles(paths: Iterable[Path]) -> Iterable[Bundle]:
    def append_holes(holes):
        for hole in holes:
            if isinstance(hole, Path):
                # just for edge cases, in general:
                # holes should be inside of the contour!
                box.extend(hole.control_vertices())
                entities.append(hole.user_data)
            else:
                append_holes(hole)

    # the fast bbox detection algorithm is not very accurate!
    for polygon in nesting.fast_bbox_detection(paths):
        contour = polygon[0]
        box = BoundingBox(contour.control_vertices())
        entities = [contour.user_data]
        for hole in polygon[1:]:
            append_holes(hole)
        yield Bundle(entities, box)


def bundle_items(items: Iterable[DXFGraphic]) -> Iterable[Bundle]:
    paths: List[Path] = list()
    for entity in items:
        p = make_path(entity)
        p.user_data = entity
        paths.append(p)
    return build_bundles(paths)


def pack(items: Iterable[DXFGraphic], width, height):
    # ignoring depth and weight
    bin0 = py3dbp.Bin("B0", width, height, DEPTH, UNLIMITED)
    packer = py3dbp.Packer()
    packer.add_bin(bin0)
    for bundle in bundle_items(items):
        box = bundle.bounding_box
        # use "Item.name" as generic data storage, ignore depth and weight
        packer.add_item(
            py3dbp.Item(bundle, box.size.x, box.size.y, DEPTH, WEIGHT)
        )
    packer.pack(bigger_first=True)
    return bin0


def main(filename):
    doc = ezdxf.readfile(filename)
    doc.layers.add("PACKED")
    doc.layers.add("UNFITTED")
    msp = doc.modelspace()
    bin_width = 700
    bin_height = 700
    bin0 = pack(msp, bin_width, bin_height)
    print("packed: " + "=" * 70)
    color = 3
    for item in bin0.items:
        if color == 3:
            color = 6
        else:
            color = 3
        bundle = item.name
        bundle.set_properties("PACKED", color)
        box = bundle.bounding_box
        # move entity to origin
        bundle.transform(Matrix44.translate(-box.extmin.x, -box.extmin.y, 0))
        print(f"{str(bundle)}, size: ({box.size.x:.2f}, {box.size.y:.2f})")
        x, y, z = item.position
        m = Matrix44.translate(float(x), float(y), 0)
        if item.rotation_type == RotationType.RT_HWD:
            # height, width, depth orientation
            m = Matrix44.z_rotate(math.pi / 2) @ Matrix44.translate(
                box.size.y + float(x), float(y), 0
            )
        bundle.transform(m)

    print("unfitted: " + "=" * 70)
    for item in bin0.unfitted_items:
        bundle = item.name
        bundle.set_properties("UNFITTED", 2)
        box = bundle.bounding_box
        print(f"{str(bundle)}, size: ({box.size.x:.2f}, {box.size.y:.2f})")

    # add bin frame:
    msp.add_lwpolyline(
        [(0, 0), (bin_width, 0), (bin_width, bin_height), (0, bin_height)],
        close=True,
    )
    doc.saveas(filename.replace(".dxf", ".pack.dxf"))


if __name__ == "__main__":
    main("case.dxf")

[mozman]

The previous test file also works if bigger_first=True, the blue bounding boxes just added for debugging:

But fails if bigger_first=False: