Tag: ClipperLib

Pyclipr – Python Polygon Clipping and Offsetting Library

3D Printing Additive Manufacturing Blog PySLM 1 Comment

Pyclipr is a Python library offering the functionality of the Clipper2 polygon clipping and offsetting library and are built upon pybind . The underlying Clipper2 library performs intersection, union, difference and XOR boolean operations on both simple and complex polygons and also performs offsetting of polygons and inflation of un-connected paths. Unfortunately, the contracted name (Clipr) is the closest name to that of the previous form.

Unlike pyclipper, this library is not built using cython, which was previously integrated directly into PySLM with custom modifications to provide ordering of scan vector. Instead the full capability of the pybind binding library is exploited, which offers great flexibility and control over defining data-structures. This library aims to provide convenient access to the modifications and new functionality offered by Clipper2 library for Python users, especially with its usage prevalent across most open source 3D Printing packages (i.e. Cure) and other computer graphics applications.

Summary of key ClipperLib2 Features Relevant to AM and their use in PySLM

  • Improved performance and numerical robustness
  • Simplification of open-path clipping – no requirement to use PolyPath usage
  • Built-in numerical scaling between floating point and the internal Int64
  • Additional point attributes built-in directly (Z-attribute)

Summary of Implementation

The structure follows closely with ClipperLib2 api in most cases but has adapted some of the naming to be more pythonic and regularity during typing.

The added benefit of the original PyClipper library is that it can take numpy and native python lists directly, because these are implicitly converted by pybind into the internal vector format. A significant addition is the ability to accept 2D paths with the additional ‘Z’ attributes (currently floating points) without using separate functions, taking advantage of pythons duck typing. Open-paths and these optionally defined z attributes are returned when passing the arguments when performing the execute function for clipping utilities. Below are a summary of the key operations

Path Offsetting

Path offsetting is accomplished relatively straightforwardly. Paths are added to the ClipperOffset object and the join and end types are set. The delta or offset distance is then provided in the execute function. 

import numpy as np
import pyclipr

# Tuple definition of a path
path = [(0.0, 0.), (0, 105.1234), (100, 105.1234), (100, 0), (0, 0)]
path2 = [(0, 0), (0, 50), (100, 50), (100, 0), (0,0)]

# Create an offsetting object
po = pyclipr.ClipperOffset()

# Set the scale factor to convert to internal integer representation
pc.scaleFactor = int(1000)

# add the path - ensuring to use Polygon for the endType argument
po.addPath(np.array(path), pyclipr.Miter, pyclipr.Polygon)

# Apply the offsetting operation using a delta.
offsetSquare = po.execute(10.0)

Polygon Intersection

Polygon intersection can be perform by using the Clipper object. This requires add individual path or paths and then setting these as subject and clip. The execute call is used and can return multiple outputs depending on the clipping operation. This includes open-paths or Z attribute information.

# continued 

# Create a clipping object
pc = pyclipr.Clipper()
pc.scaleFactor = int(1000) # Scale factor is the precision offered by the native Clipperlib2 libraries

# Add the paths to the clipping object. Ensure the subject and clip arguments are set to differentiate
# the paths during the Boolean operation. The final argument specifies if the path is
# open.

pc.addPaths(offsetSquare, pyclipr.Subject)
pc.addPath(np.array(path2), pyclipr.Clip)

""" Polygon Clipping """
# Below returns paths of various clipping modes
outIntersect  = pc.execute(pyclipr.Intersection)
outUnion = pc.execute(pyclipr.Union)
outDifference = pc.execute(pyclipr.Difference, pyclipr.EvenOdd) # Polygon ordering can be set in the final argument
outXor = pc.execute(pyclipr.Xor, pyclipr.EvenOdd)

# Using execute2 returns a PolyTree structure that provides hierarchical information
# if the paths are interior or exterior

outPoly = pc.execute2(pyclipr.Intersection, pyclipr.EvenOdd)

Open Path Clipping

Open-path clipping (e.g. line segments) may be performed natively within pyclipr, by default this is disabled. Within the execute function, returnOpenPaths argument should be set true. 


""" Open Path Clipping """
# Pyclipr can be used for clipping open paths.  This remains simple to complete using the Clipper2 library

pc = pyclipr.Clipper()
pc2.scaleFactor = int(1e5)

# The open path is added as a subject (note the final argument is set to True to indicate Open Path)
pc2.addPath( ((50,-10),(50,110)), pyclipr.Subject, True)

# The clipping object is usually set to the Polygon
pc2.addPaths(offsetSquare, pyclipr.Clip, False)

""" Test the return types for open path clipping with option enabled"""
# The returnOpenPaths argument is set to True to return the open paths. Note this function only works
# well using the Boolean intersection option

outC = pc2.execute(pyclipr.Intersection, pyclipr.NonZero)
outC2, openPathsC = pc2.execute(pyclipr.Intersection, pyclipr.NonZero, returnOpenPaths=True)

Z-Attributes

The final script of note is the in-built Z attributes that are embedded within PyClipr. Z attributes (float64) can be attached to each point across a path or. set of polygons. During intersection of segments or edges, these Z attributes are passed to the resultant clipped paths. These are returned as a separate list in the output.

""" Test Open Path Clipping """

pc3 = pyclipr.Clipper()
pc3.scaleFactor = int(1e6)

pc3.addPath(openPathPolyClipper, pyclipr.Clip, False)

# Add the hatch lines (note these are open-paths)
pc3.addPath( ((50.0,-20, 3.0),
              (50.0 ,150,3.0)), pyclipr.Subject, True) # Open path with z-attribute of 3 at each path point

""" Test the return types for open path clipping with different options selected """
hatchClip = pc3.execute(pyclipr.Intersection, pyclipr.EvenOdd, returnOpenPaths=True)

# Clip but return with the associated z-attributes
hatchClipWithZ = pc3.execute(pyclipr.Intersection, pyclipr.EvenOdd, returnOpenPaths=True, returnZ=True)

Usage in PySLM

PyClipr has been refactored for use in the next release of PySLM (v0.6). This has improved readability of code and in some cases there are performance improvements due to inherent optimisations within ClipperLib2. This includes also removal of unnecessary transformations and scaling factors performed within python, that were required converting between paths generated in PySLM (shapely) and PyClipper originally. In particular, avoiding the use of PolyNodes were especially useful to avoid throughout. Modifications have been applied throughout the entire modules including the hatching and support modules. PySLM also now benefits by becoming a purely a source distribution, by distribution the clipping and offsetting functions into a separate package, therefore no additional compiling is required during installation.

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

Additive Manufacturing Blog PySLM No Comments

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.

Each hatch vector coordinate is given an individual id.During the clipping operation with the boundary, the intersection point is assigned the id from the original ‘z’ coordinate.

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.

Proudly powered by WordPress & Skyrocket Themes

MENU

Navigation