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.

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, :, :]


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.

Basics of Hatching in PySLM

The generation of hatch infills in PySLM is relatively straightforward and can be adapted to suit the user’s needs. Anecdotally, this was a remarkable improvement on performance and simplicity over preexisting code that was used previously during University, which used a combination of Matlab and a ClipperLib library.

The generation of hatch vectors are nearly always a series of adjacent parallel scan vectors that an infill a bounded area. There has been some unusual approaches for infills that have been tried such as spiral [1][2] and fractal [3][4][5] scan strategies. Generally, exploring different raster patterns across an SLM part remains largely unexplored due to the unavailability of opensource tools, code and open access to machine platforms now in research environments. However, potentially this could unlock the ability to micro-structural development in some metal alloys. Attard et al. demonstrates this by modifying the island size throughout the part to promote different microstructures [6].

The first step of generating the hatch is finding the region to ensure scan vector generated guarantees full coverage across the boundary for the chosen hatch angle, h_d. This is needed irrespective of scan strategy. My previous approach was rather cumbersome and required trigonometry to be used to calculate the start and end points according the chosen (\theta_h) to cover the boundary. A far simpler approach was conceived.

Basic method:

The approach simply relies on covering the entire boundary irrespective of hatch angle and letting the polygon clipping library do the actual heavy lifting.

In this method, the bounding box for a closed region is found. A rather simple calculation made by taking the min and max of the boundary coordinates – easily obtained via shapely.

The maximum extent or diagonal length, r, from the bounding box corner to the bounding centre is then calculated. In the diagram, it is observed that this forms a circular locus, which upon choosing any hatch angle, all hatch lines after rotation will be guaranteed to fully cover boundary. Remarkably simple.

The basic code can be found in hatching.py:

# Expand the bounding box
bboxCentre = np.mean(bbox.reshape(2,2), axis=0)

# Calculates the diagonal length for which is the longest
diagonal = bbox[2:] - bboxCentre
bboxRadius = np.sqrt(diagonal.dot(diagonal))

From the locus, we assume the hatch coordinate local coordinate system with an origin (-r,-r). A series of parallel hatch vectors with hatch distance, h_d, can be generated conveniently covering the entire square region . This can be done using numpy, using np.tile:

# Construct a square which wraps the radius
x = np.tile(np.arange(-bboxRadius, bboxRadius, hatchSpacing, dtype=np.float32).reshape(-1, 1), (2)).flatten()
y = np.array([-bboxRadius, bboxRadius]);
y = np.resize(y, x.shape)

Unfortunately, ClipperLib by default does not guarantee the order lines are clipped in. The naive approach is to clip these individually in a sequential order, which introduces a significant overhead. Alternatively the clipped hatch lines can be sorted. For achieving this, the PyClipper library was customized to guarantee the sequential order of the scan , which is explained in this post.

The approach to guarantee the z-order is to provide a z-coordinate which defines the order of scanning. This should be in pairs of ascending order which group the coordinates in each scan vector: i.e. 0,0, 1,1,..,2,2 etc. Finally before being clipped, an n\times3 coordinate matrix is formed.

# Generate a linear sorting according to the order of scanning.
# i.e. 0,0,1,1,..,n-1,n-1,n,n 
z = np.arange(0, x.shape[0] / 2, 0.5).astype(np.int64)

# Group the XY coordinates and z order 
coords = np.hstack([x.reshape(-1, 1),
                    y.reshape(-1, 1),
                    z.reshape(-1, 1)])

From this, a 2D rotation matrix, R(\theta_h), and translation to the bounding box centre can be applied to the coordinates of the unclipped hatch lines.

# Create the 2D rotation matrix
c, s = np.cos(theta_h), np.sin(theta_h)
R = np.array([(c, -s, 0),
              (s, c, 0),
              (0, 0, 1.0)])

# Apply the rotation matrix and translate to bounding box centre
coords = np.matmul(R, coords.T)
coords = coords.T + np.hstack([bboxCentre, 0.0])

There is one issue with the method is that using region / island based scan strategies. Many of the regions are not clipped, therefore, for large regions it can become inefficient. However, assuming a normal hatch in-fill is used, the clipping operation mostly amortises the additional cost.


1 Zhang, W., Tong, M., & Harrison, N. M. (2020). Scanning strategies effect on temperature, residual stress and deformation by multi-laser beam powder bed fusion manufacturing. Additive Manufacturing, 36(June), 101507. https://doi.org/10.1016/j.addma.2020.101507
2 Qian, B., Shi, Y. S., Wei, Q. S., & Wang, H. B. (2012). The helix scan strategy applied to the selective laser melting. International Journal of Advanced Manufacturing Technology, 63(5–8), 631–640. https://doi.org/10.1007/s00170-012-3922-9
3 Ma, L., & Bin, H. (2006). Temperature and stress analysis and simulation in fractal scanning-based laser sintering. The International Journal of Advanced Manufacturing Technology, 34(9–10), 898–903. https://doi.org/10.1007/s00170-006-0665-5
4 Catchpole-Smith, S., Aboulkhair, N., Parry, L., Tuck, C., Ashcroft, I., & Clare, A. (2017). Fractal scan strategies for selective laser melting of ‘unweldable’ nickel superalloys. Additive Manufacturing, 15, 113–122. https://doi.org/10.1016/j.addma.2017.02.002
5 Sebastian, R., Catchpole-Smith, S., Simonelli, M., Rushworth, A., Chen, H., & Clare, A. (2020). ‘Unit cell’ type scan strategies for powder bed fusion: The Hilbert fractal. Additive Manufacturing, 36(July), 101588. https://doi.org/10.1016/j.addma.2020.101588
6 Attard, B., Cruchley, S., Beetz, C., Megahed, M., Chiu, Y. L., & Attallah, M. M. (2020). Microstructural control during laser powder fusion to create graded microstructure Ni-superalloy components. Additive Manufacturing, 36, 101432. https://doi.org/10.1016/j.addma.2020.101432

Slicing and Hatching for Selective Laser Melting (L-PBF)

Much of slicing and hatching process is already taken for granted in commercial software mostly offered by the OEMs of these systems rarely discussed amongst academic research. Already we observe practically the implications direct control over laser parameters and scan strategy on the quality of the bulk material – reduction in defects, minimising distortion due to residual stress, and the surface quality of parts manufactured using these process. Additionally, it can have a profound impact the the metallic phase generation, micro-structural texture driven via physics-informed models [1], grading of the bulk properties and offer precise control over manufacturing intricate features such as thin-wall or lattice structures [2].

This post hopefully highlights to those unfamiliar some of the basis process encountered in the generation of machine build files used in AM systems and get a better understanding to the operation behind PySLM. I have tried my best to generalise this as much as possible, but I imagine there are subtleties I have not come across.

This post is to provide some reference into the generation of hatches or scan vectors are created for use in AM processes such as selective laser melting (SLM), which uses a point energy source to raster across a medium. Some people prefer to more generally to classify the family of processes using the technical ASTM F42 committee standards 52900 and 52911 – Powder Bed Fusion (PBF). I won’t go into the basic process of the manufacturing processes such as EBM, SLM, SLA, BJF, as there are many excellent articles already that explain these in far greater detail.

Machine Build Files

AM processes require a digital representation to manufacture an object. These tend to be computed offline – separate from the 3D Printer, using specialist or dedicated pre-processing software. I expect this will become a closed-loop system in the future, such that the manufacturing integrated directly into the machine.

For some AM process families, the control operations may be exceedingly granular – i.e. G-code. G-code formats state specific instructions or functional commands for the 3D printer to sequentially or linearly execute. These tend to fit with deposition methods such as Filament Extrusion, Direct-Ink-Writing (robo-casting) and direct energy deposition (DED) methods. Typically, these tends to be for deposition with a machine systems, which requires coordination of physical motion in-conjunction with some mechanised actuation to deposit/fuse material.

Machine Build File Formats for L-PBF

For exposure (laser, electron-beam) based AM processes, commercial systems use a compact notation solely for representing the scan path the exposure source will traverse . The formats are often binary to aid their compactness.

To summarise, within these build files, an intermediate representation consists of index-based referenceable parameters for the build. The remainder consists of a series of layers, that contain geometric entities (points, vectors) that are used to to control the exposure for the border or contour or raster or infill the interior region. For L-PBF processes, the digital files, commonly referred as “machine build file” comes in various flavours dependent on the machine manufacture:

  • Renshaw .mtt,
  • SLM Solution .slm,
  • DMG Mori Realizer .rea
  • EOS .sli
  • Aconity .cli+ or .ilt wrapper

Some file formats, such as Open Beam Path format can specify bezier curves [3]. Another recently proposed open source format created by RWTH Aachen in 2022 called OpenVector Format based on Google’s Protobuf schema. The format aims to offer a specification universally compatible across a swathe of PBF processes and supplement existing commercial formats with additional build-process meta-data (e.g. build, platform temperature, dosing) and detailed definition with further advancements in the process, such as multi-beam builds.

Build-File Formats

Higher level representations that describe the distribution of material(s) defining geometry – this could be bitmap slices or even a 3D model. Processes such as Jetting, BJF, High Speed Sintering, DLP Vat-polymerisation currently available offer this a reality. With time, polymer and metal processes will evolve to become 2D:, diode aerial melting [4] or more aerial based scanning based on holographic additive manufacturing methods, such as those proposed by Seurat AM [5] based off research at LLNL, and recently at University of Cambridge [6] . In the future, we can already observe the exciting prospect of new processes such as computed axial lithograph [7] that will provide us near instantaneous volumetric additive manufacturing.

For now, single and multi point exposure systems for the imminent future will remain with us as the currently available process. PySLM uses an intermediate representation – specifying a set of points and lines to control the exposure of energy into a layer.

The Slicing and Hatching Process in L-PBF

With nearly most conventional 3D printing process, it begins with a 3D representation of a solid volume or geometry. 2D planar slices or layers are extracted from a 3D mesh or B-Rep surface in CAD by taking cross-sections from a geometry. Each slice layer consist of a set of boundaries and holes describing the cross-section of an object. Note: non-planar deposition does exist for DED/Filament processes, such as this Curved Layer Fused Deposition Modeling [ref] and a spherical slicing technique [8].

For consolidating material, an exposure beam must raster across the surface medium (metal or polymer powder, or a photo-polymer resin) depending on the process. Currently this is a single or multiple point which moves at a velocity vwith a power P across the surface. The designated exposure or energy deposited into the medium is principally a function of these two parameters, depending on the type of laser:

  • (Quasi)-Continious Wave: The laser remains active switched on (typically modulated using a form of PWM) across the entire length of the scan vector
  • Pulsed Mode (Q-Switched): Laser is pulsed at set distances and exposure times across the scan vector

Numerous experiments often tend to result in parametric power/speed maps to the achieved part bulk density, that result in usually optimal processing windows that produce stable and consistent melt-tracks [9][10]. Recently, process maps are based on a non-dimensional parameter such as the normalised enthalpy approach, that more reliably assist selecting a suitable process windows [11].

Illustration of a scan vector commonly used in Laser Powder-Bed Fusion (SLM)

However, the complexity of the process extends further and is related to a many additional variables dependent on the process such as layer thickness, absorption coefficient (powder and material), exposure beam profile etc.. Additionally, the cumulative energy deposited spatially over a period of time must consider overlap of scan vectors within an area.

Scan Vector Generation

Each boundary polygon is offset initially to account for the the radius of the beam exposure, which is termed a ‘spot compensation factor‘. Some processes such as SLS or BJF account for global part shrinkage volumetrically throughout the part by having a global scale factor or deformed mesh to compensate to non-uniform shrinkage across the part.

The composition of laser scan vectors used in a slice or layer for L-PBF or Selective Laser Melting. The boundary is offset multiple times, with the interior or core filled with hatch vectors.
The typical composition of a layer used for scanning in exposure based processes. This consists of outer and inner contours, with the core interior filled with hatches.

This first initial offset is the outer-contour which would be visible on the exterior of the part. This contour will have a different set of laser parameters in order to optimise and improve the surface roughness of the part obtained. A further offset is applied to generate a set of inner-contours before hatching begins.

Depending on the orientation of the surface (e.g. up-skin or down-skin), the boundary and interior region may be intersected to fine-tune the laser parameters to provide better surface texture, or surface roughness – typically varying between Ra = 3-13 μm [12] primarily determined by the surface angle and a combination of the process variables including,

  • the powder feedstock (bulk material, powder size distribution)
  • laser parameters
  • layer thickness (pre-dominantly fixed or constant for most AM processes)

Overhang regions and surfaces with a low overhang angles tend to be susceptible to high surface-roughness. Roller re-coater L-PBF systems – available only on 3DSystems or AddUp system,, tend to offer far superior surface quality on low inclined or overhang regions. Additionally, progressive advancement and maturity of laser parameter optimisation, and those computationally driven using part geometry [13] are able to further enhance the quality and potentially eliminate the need for support structures. Depending on the machine platform, these regions are identified by sampling across two-three layers. Overhang regions obviously require support geometry, which is an entirely different topic discussed in this post.

Laser parameters in SLM (L-PBF) can be optimised based on the adjacent surface regions. Special regions, include the upskin, downskin and overhang regions
Laser parameters can be optimised based on the adjacent surface regions. Special regions, include the upskin, downskin and overhang regions needed to improve the surface roughness and reduce density in regions.

Following the generation of the contours, the inner core region requires filling with hatches. Hatches are a series of parallel scan vectors placed adjacent at a set hatch distance, h_d. This parameter is optimized according to the material processed, but is essentially related to the spot radius of the exposure point r_s in order to reduce inter-track and inter layer porosity. Across each layer these tend to be placed at a particular orientation \theta_h, which is is then incrementally rotated globally for subsequent layers, typically 66.6°. This rotation aims to smooth out the build process in order to minimise inter-track porosity, and generate homogeneous material, and in the case of SLM mitigate the effects of anisotropic residual stress generation.

The composition and terminology (hatch distance, hatch spacing, hatch angle) used in L-PBF. The Layer Geometry objects used to scan across a Layer in Selective Laser Melting (L-PBF). The various parameters such as the hatch distance and hatch angle are shown.
A general composition of the various LayerGeometry objects used to scan across a Layer. The various parameters such as the hatch distance, spacing and hatch angle are shown.

The distribution (position, length, rotation) of these hatch vectors are arranged using a laser scan strategy. The most common include a simple alternating hatch, stripe and island or checkerboard scan strategy.

Each set or group of scan vectors is stored together in a LayerGeometry, depending on the type (either a set of point exposures, contour or hatch vectors). These LayerGeometry groups usually share a set of exposure parameters – power, laser scan speed (point exposure time, point distance for a pulsed laser), focus position).

Some systems offer a greater degree of control and can control individual power across the scan vectors. Other can fine tune the acceleration and modulate the power along the scan vectors to support techniques known as ‘skywriting‘. For instance in SLM, it has been proposed that careful tuning of the laser parameters towards the end of the scan vector, i.e. turning can reduce porosity by preventing premature collapse of key holing phenomena [14]. In theory, PySLM could be extended to provide greater control of the electro-optic systems used in the process if so desired.

Hopefully, this provides enough background for those who are interested and engaged in working with developing scan strategies and material development using PySLM.


1 Plotkowski, A., Ferguson, J., Stump, B., Halsey, W., Paquit, V., Joslin, C., Babu, S. S., Marquez Rossy, A., Kirka, M. M., & Dehoff, R. R. (2021). A stochastic scan strategy for grain structure control in complex geometries using electron beam powder bed fusion. Additive Manufacturing46. https://doi.org/10.1016/j.addma.2021.102092
2 Ghouse, S., Babu, S., van Arkel, R. J., Nai, K., Hooper, P. A., & Jeffers, J. R. T. (2017). The influence of laser parameters and scanning strategies on the mechanical properties of a stochastic porous material. Materials and Design131, 498–508. https://doi.org/10.1016/j.matdes.2017.06.041
3 Open Beam Path – Freemelt, https://gitlab.com/freemelt/openmelt/obplib-python
4 Zavala Arredondo, Miguel Angel (2017) Diode Area Melting Use of High Power Diode Lasers in Additive Manufacturing of Metallic Components. PhD thesis, University of Sheffield.
5 Seurat AM. https://www.seuratech.com/
6 https://www.theengineer.co.uk/holographic-additive-manufacturing-lasers/
7 Kelly, B., Bhattacharya, I., Shusteff, M., Panas, R. M., Taylor, H. K., & Spadaccini, C. M. (2017). Computed Axial Lithography (CAL): Toward Single Step 3D Printing of Arbitrary Geometries. Retrieved from http://arxiv.org/abs/1705.05893
8 Yigit, I. E., & Lazoglu, I. (2020). Spherical slicing method and its application on robotic additive manufacturing. Progress in Additive Manufacturing, 5(4), 387–394. https://doi.org/10.1007/s40964-020-00135-5
9 Yadroitsev, I., & Smurov, I. (2010). Selective laser melting technology: From the single laser melted track stability to 3D parts of complex shape. Physics Procedia, 5(Part 2), 551–560. https://doi.org/10.1016/j.phpro.2010.08.083
10 Maamoun, A. H., Xue, Y. F., Elbestawi, M. A., & Veldhuis, S. C. (2018). Effect of selective laser melting process parameters on the quality of al alloy parts: Powder characterization, density, surface roughness, and dimensional accuracy. Materials, 11(12). https://doi.org/10.3390/ma11122343
11 Ferro, P., Meneghello, R., Savio, G., & Berto, F. (2020). A modified volumetric energy density–based approach for porosity assessment in additive manufacturing process design. International Journal of Advanced Manufacturing Technology, 110(7–8), 1911–1921. https://doi.org/10.1007/s00170-020-05949-9
12 Ni, C., Shi, Y., & Liu, J. (2019). Effects of inclination angle on surface roughness and corrosion properties of selective laser melted 316L stainless steel. Materials Research Express, 6(3). https://doi.org/10.1088/2053-1591/aaf2d3
13 Velo3D Sapphire Printer – SupportFree Technology. https://blog.velo3d.com/blog/supportfree-what-does-it-mean-why-is-it-important
14 Martin, A. A., Calta, N. P., Khairallah, S. A., Wang, J., Depond, P. J., Fong, A. Y., … Matthews, M. J. (2019). Dynamics of pore formation during laser powder bed fusion additive manufacturing. Nature Communications, 10(1), 1–10. https://doi.org/10.1038/s41467-019-10009-2