Optimising and Improving PyClipper (ClipperLib) Hatch Clipping Performance for AM

In previous incarnations throughout my time, the renowned ClipperLib has been used to provide the polygon and line clipping and offsetting operations for generating the hatching used in Selective Laser Melting . This library is also used as part of the slicing engine in the popular Cura software used in the Ultimakr filament 3D printers. his opensource c++ polygon clipping library at present is very efficient, robust and arguably does its specific job very well.

The First Attempt

The first implementation was done through a custom mex extension for Matlab – infact there is actually now a mex extension available on mathworks. The clipping of hatch vectors with a polygon boundary was done on an individual basis; one hatch vector at a time. This is necessary because returned clipped lines in ClipperLib are not guaranteed to be returned in the same sequential order as they were passed due to the underlying Vatti algorithm which works using a ‘scan-line’ approach.

Unfortunately, this was very inefficient operation requiring the re-initialisation of the boundary polygon for each clipped line. Through bruteforce and persistence, this method did a satisfactory job hatching simple geometries for research purposes.

The Second Attempt

The next progression was transitioning to Python, using PyClipper. Appreciating the challenges of trying to run hatching on embedded hardware, clipping each hatch vector didn’t fair well. The second approach was to clip all the hatch vectors together to remove the overhead of re-initializing the ClipperLib state. After clipping the hatch vectors were sorted using the following method.

The inner product or dot project between the midpoint of each hatch vector and the effective vector of the hatch angle is made. The projected distance is the used to sort the relative line position. This can be seen in LinearSort class or in the following code excerpt

theta_h = np.deg2rad(hatchAngle)

# Find the unit vector normal based on the hatch angle
norm = np.array([np.cos(theta_h), np.sin(theta_h)])

midPoints = np.mean(scanVectors, axis=1)

# Project the midpoint onto the hatch angle vector
idx2 = norm.dot(midPoints.T)

# Sort the scan vectors
idx3 = np.argsort(idx2)
sortIdx = np.arange(len(midPoints))[idx3]

return scanVectors[sortIdx]

This worked fairly well. However, it has severe drawback in that it is limited to just hatching and sorting across a single region and relies on a constant hatch direction. The sorting mechanism severely constrains what approaches can be used for scan strategy design, i.e. island scan strategies.

The current approach in PySLM

The current implementation builds on a clever trick built into ClipperLib that unfortunately is not implemented in PyClipper. Within ClipperLib there is an option to include the z coordinate as part of the Point Struct by defining the use_xyz preprocessor directive. This allows the user to pass an additional 4 byte integer for each point. Infact, this can represent any information, and this can infact be the unique hatch id, which defines the order of scanning. Note: We could further modify the library to use any data-type but this is unnecessary.

During clipping, the z-component is not actually used for clipping. ClipperLib does not know which z-component should be used at the intersection between edges; the boundary or the hatch line. A function maxZFillFunc is defined in ClipperLib.cpp which resolves this ambiguity. To resolve this, a specific function finds the maximum z component from all intersecting edge points, and stores it in the new point pt generated. As a result the original index used for sorting is stored in the clipped result.

void maxZFillFunc(const IntPoint& e1bot, IntPoint& e1top, IntPoint& e2bot, IntPoint& e2top, IntPoint& pt) {
        // Find the maximum z value from all points. This provides a non ambiguious cases, as for PySLM the background
        // contour has a value of zero.
        long maxZ = -1;
        if(e1bot.Z > maxZ)
            maxZ = e1bot.Z;

        if(e1top.Z > maxZ)
            maxZ = e1top.Z;

        if(e2top.Z > maxZ)
            maxZ = e2top.Z;

        if(e2bot.Z > maxZ)
            maxZ = e2bot.Z;

        // Assign the z value to pt
        pt.Z = maxZ;
  };

void Clipper::ZFillFunction(ZFillCallback zFillFunc)
{
  m_ZFill = zFillFunc;
}

Further changes in the cython pyrex definition – pyclipper.pyx was needed to enable this functionality, hence, this needs to be compiled internally for this project.

Back in Python, the order index is assigned to each pairs of coordinates representing a hatch vector, resulting in an 2n\times3 array where n is the number of hatches:

idx = np.arange(len(x) / 2)
hatchArray = np.hstack([x,y,id])

After clipping the hatch vectors generated requiring a quick sort based on their id. Typically this isn’t expensive because most of the clipped hatch vectors are returned in the same order.

clippedLines = self.clipperToHatchArray(clippedPaths)

# Extract only x-y coordinates and sort based on the pseudo-order stored in the z component.
clippedLines = clippedLines[:, :, :3]
id = np.argsort(clippedLines[:, 0, 2])
clippedLines = clippedLines[id, :, :]

Conclusions

Throughout PySLM, the user simply has to generate a sequence of hatch vectors as the same order they wish them to be scanned. An increasing unique index is applied to each hatch vector.

This proposed technique is remarkbly simple, efficient and effective for clipping . It is very trivial but given the limit number of polygon clipping libraries available this was particularly useful.

In the future, I plan to explore storing additional data associated with the hatch vectors. This itself may not be necessary because this data can be looked up from the global hatch data array, but it may result in simplification of the code.