Improving Performance of Island Checkerboard Scan Strategy Hatching in PySLM

The hatching performance of PySLM using ClipperLib via PyClipper is reasonably good considering the age of the library using the Vatti polygon clipping algorithm. Without attempting to optimise the underlying library and clipping algorithm for most scenarios, the hatch clipping process should be sufficient for most use case. Future investigation will explore alternative clipping algorithms to further improve the performance of this intensive computational process

For the unfamiliar with the basic hatching process of a single layer, the laser or electron beam (a 1D single point source) must scan across an aerial (2D) region. This is done by creating a series of lines/vectors which infill or raster across the surface.

The most basic form of hatch infill for bulk regions is an alternating, meander, or in some locales referred to a serpentine scan strategy. This tends to be undesirable in SLM due to the creation of localised heat build-up [1] resulting in porosity, poor surface finish [2], residual stress and resultant distortion and anisotropy due to preferential grain growth [3]. Stripe or Island scan strategies are employed in attempt to mitigate these by limiting the length of scan vectors used across a region [4][5][6]. Within the layer hatch vectors for each island are oriented orthogonal to each other and the scan vector length can be precisely controlled in order to reduce the magnitude of residual stresses generated [7].

However, when the user desires a stripe or an island scan strategy, the number of clipping operations for the individual hatch vectors increases drastically. The increase in number of clipping operations increases due to division of the area into fixed size regions corresponding to the desired scan vector length (typically 5 mm)]:

• Standard Meander Scan Strategy: n_{clip} \propto \frac{A}{hatchDistance(h_d)}
• Stripe Scan Strategy: n_{clip} \propto \frac{A}{StripeWidth}
• Island Scan Strategy: n_{clip} \propto \frac{A}{IslandWidth^2}

As can be observed, the performance of hatching with an island scan strategy degrades rapidly when using the island scan due to reciprocal square. As a result, using a naive approach, hatching a very large planar region using an island scan strategy could quickly result in 100,000+ clipping operations for a single layer for a large flat. In addition, this is irrespective of the sparsity of the layer geometry. The way the hatch filling approach works in PySLM, the maximum extent of a contour/polygon region is found. A circle is projected based on this maximum extent, and an outer bounding box is covered. This is explained in a previous post.

The scan vectors are tiled across the region. The reason behind this is to guarantee complete coverage irrespective of the chosen hatch angle, \theta_h, across the layer and largely simplifies the computation. The issue is that many regions will be outside the boundary of the part. Sparse regions both void and solid will not require additional clipping.

The Proposed Technique:

In summary, the proposed technique takes advantage that each island is regular, and therefore each island can be used to discretise the region. This can be used to perform intersection tests for region that may be clipped, whilst recycling existing hatch vectors for those within the interior boundary.

Given that use an island scan strategy provides essentially structured grid, this can be easily transformed into a a method for selecting regions. Using the shapely library, each island boundary consisting of 4 edges can be quickly tested to check if it overlaps internally with the solid part and also intersected with the boundary. This is an efficient operation to perform, despite shapely (libGEOS) being not as efficient as PyClipper.

from shapely.geometry.polygon import LinearRing, Polygon

intersectIslands = []
overlapIslands = []

intersectIslandsSet = set()
overlapIslandsSet= set()

for i in range(len(islands)):
    
    island = islands[i]
    s = Polygon(LinearRing(island[:-1]))

    if poly.overlaps(s):
        overlapIslandsSet.add(i) # id
        overlapIslands.append(island)

    if poly.intersects(s):
        intersectIslandsSet.add(i)  # id
        intersectIslands.append(island)


# Perform difference between the python sets
unTouchedIslandSet = intersectIslandsSet-overlapIslandsSet
unTouchedIslands = [islands[i] for i in unTouchedIslandSet]

This library is used because the user may re-test the same polygon consecutively, unlike re-building the polygon state in ClipperLib. Ultimately, this presents three unique cases:

1. Non-Intersecting (shapely.polygon.intersects(island) == False) – The Island resides outside of the boundary and is discarded,
2. Intersecting (shapely.polygon.intersects(island) == True) – The Island is in an internal region, but may be also clipped by the boundary,
3. Clipped (shapely.polygon.intersects(island) == True) – The island intersects with the boundary and requires clipping.

Taking the difference between cases 2) and 3), the islands with hatch scan vectors can be generated without requiring unnecessary clipping of the interior scan vectors. As a result this significantly reduces the computational effort required.

Although extreme, the previous example generated a total number of 2209 5 mm islands to cover the entire region. The breakdown of the island intersections are:

1. Non-intersecting islands: 1591 (72%),
2. Non-clipped islands: 419 (19%),
3. Clipped islands: 199 (9%).

With respect to solid regions, the number of clipped islands account for 32% of the total area. The overall result is shown below. The total area of the hatch region that was hatched is 1.97 \times 10^3 \ mm^2, which is equivalent to a square length of 445 mm, significantly larger than what is capable on most commercial SLM systems. Using an island size of 5 mm with an 80 μm hatch spacing, the approximate hatching time is 6.5 s on a modest laptop system. For this example, 780 000 hatch vectors were generated.

The order of hatching scanned is shown by the blue lines, which trace the midpoints of the vectors. Hatches inside the island are scanned sequentially. The order of scanning in this case is chosen to go vertically upwards and then horizontally across using the in-built Python 3 sorting function with a lambda expression Remarkably, all performed using one line:

sortedIslands = sorted(islands, key=lambda island: (island.posId[0], island.posId[1]) )

A future post will elaborate further methods for sorting hatch vectors and island groups.

Comparison to Original Implementation:

The following is a non-scientific benchmark performed to illustrate the performance profile of the proposed method in PySLM.

Island Size [mm]	Original Method Time [s]	Proposed Method Time [s]
3	466	5.3
5	258	6.5
10	121	7.9
20	75	8.23

It is clearly evident that the proposed method reduces the overall time by 1-2 orders for hatching a region. What is strange is that with the new proposed method, the overall time increases with the island size.

Generally it is expected that the number of clipping operations n_{clip} to be the following:

n_{clip} \propto \frac{Perimiter}{IslandWidth}

Potentially, this allows bespoke complex ‘sub-island’ scan strategies to be employed without a significant additional cost because scan vectors within un-clipped island regions can be very quickly replicated across the layer.

Other Benefits

The other benefits of taking approach is making a more modular object orientated approach for generating island based strategies, which don’t arbitrarily follow regular structured patterns. A future article will illustrate further explain the procedures for generating these.

The example can be seen and run in examples/example_island_hatcher.py in the Github repository.