Following on from the previous post in Part II, this post will detail the methodology for ‘Grid Block’ support generation, which is one of the most commonly utilised support structure used especially in the selective laser melting process.

The definition of a volumetric block support region is illustrated shown below for an example topology optimised bracket. These are projected volume regions that extend vertically dowwards from the original overhang surface, that conforms exactly with the input mesh.

Prior to starting this work, two approaches for generating ‘*block*‘ based support structures seem to exist. However, these approaches did not seem satisfactory especially when it came to their use using cost models.

The first approach identified, typically employed in FDM based processes, obtains the support or overhang regions and then generated a 2D polygon region that is the flattened or projection of this surface. The polygon is incrementally generated for each slice layer and a combination of boolean operations and offsetting operations are used to detect self intersections with existing geometry to modify its shape. It’s a robust method and can generate support features to aid manufacturing. The limitation of this approach is it cannot generate a volume, or an explicit mesh geometry. Rather a discretionary of the geometry containing slices representing the region with a sparse infill.

The second approach would appear to voxelise or generates a levelset of the geometry. Under support regions, the voxel grid is filled to create the in-fill support regions. The volume region can be re-constructed into a support structure and a truss structure can be generated inside. This method is not able to generate clean meshes of the support volume and requires a discretisation of the original geometry.

The following method proposed uses a hybrid mesh approach in order to generate clean meshes using fairly conventional boolean CSG library. The actual support structure generated uses relies on using 2D polygons to generate complex features such as perforation holes or structures.

### Overall Support Module Structure Summary

The overall support module, in its current state for version 0.5, is split into the following structure. The generation of supports is performed by a utility ‘*generator*‘ class `BaseSupportGenerator`

and incidentally their derived classes:

`BlockSupportGenerator`

– Generates block support regions`GridBlockSupportGenerator`

– Generates grid truss block support suitable for SLM

These classes perform the overhang and support analysis to extract the overhang surfaces. From the overhang surface, the support volumes are then generated using these to provide the inputs used to generate specific support objects that may have a specific style. For the objects representing the actual support structures, and regions, these are split into the following classes:

`SupportStructure`

– Base class defining a part’s surface requiring support`BlockSupportBase`

– Generates support block volumes for providing a region to support`GridBlockSupport`

– Generates a support with a grid trust suitable for SLM

### Overhang and Support Area Identification

The first step, widely available amongst all CAD and pre-processing software is overhang identification. Determining the face angles is a trivial process and in PySLM may be obtained using the following function `pyslm.support.getSupportAngles`

. The function takes the trimesh object and calculates the dot product of the surface normal across the mesh. Upon obtaining the dot product, the angle between the vectors is calculated and for convenience is converted from rads to degrees. Further explanation is provided in a previous post.

```
# Normal to the Z Plane
v0 = np.array([[0., 0., -1.0]])
#Identify Support Angles
v1 = part.geometry.face_normals
# Calculate the angle (degrees) between the face normals and the Z-plane
theta = np.arccos(np.clip(np.dot(v0, v1.T), -1.0, 1.0))
theta = np.degrees(theta).flatten()
```

Upon obtaining the surface angles, the overhang mesh regions can be extracting from the originating mesh, similar to that used in `pyslm.support.getOverhangMesh`

. A comparison to a threshold overhang or support angle is made and used as a mask to extract the face indices from the mesh in order to obtain a new mesh. It is common that the overhang regions are disconnected. These can optionally be split using `trimesh.split`

, which uses the internal connectivity of vertices in the mesh in a connected-component algorithm to isolate separate regions.

```
# Extract a list of faces that are below the critical overhangeAngle specified
supportFaceIds = np.argwhere(theta > 180 - overhangAngle).flatten()
# Create the overhang mesh by splitting the meshing when needed.
overhangMesh = trimesh.Trimesh(vertices=part.geometry.vertices,
faces=part.geometry.faces[supportFaceIds])
if splitMesh:
return overhangMesh.split(only_watertight=False)
```

Splitting the mesh is far more convenient in terms of processing the support structures. It also improves the performance by reducing the projected area when performing ray intersections to identify an approximate volume.

For convenience, the overhang angles of any mesh can be show in 3D using the `pyslm.visualise.visualiseOverhang`

function.

## Identifying Support Volumes

Providing a robust method for obtaining the projected support volume is not a straightforward task, especially without sophisticated boolean operation tools. Through some experimentation with the given software libraries available, the following process offered a satisfactory result without a reasonably long computational cost.

### Summary of method

The following operations are performed to generate block supports:

- Support regions (3D mesh surface) are separated into meshes
- Each support region mesh is flattened into a polygon and the contour is offset
- Surface region is extruded to z=0
- Intersection test using a Boolean Mesh Intersection operation is performed to check if self-intersection with part
- If self-intersection exist a ray-projection height map is created
- Side surfaces are removed from the intersection
- Ray projections are made separately on upward facing and downward facing faces and the height map is built up

- The gradient of the height-map is used to separate regions are extracted outlines of separate support regions
- For each support region:
- Triangulate the polygon regions into a mesh
- Rays are projected along Z in both directions from the mesh vertices to obtain the required extrusion height
- The triangulated polygon is extruded in both directions using the extrusions heights with an offset

- The extruded prisms are intersected with the original part mesh to obtain the final support volumes.

### Flattening the Polygon Regions

The class `BlockSupportGenerator`

encompasses the functionality for generating support volumes and the implementation resides in `BlockSupportGenerator.identifySupportRegions`

.

Inside the function, the support regions are flattened into a polygon `BaseSupportGenerator.flattenSupportRegion`

. This method extracts the outline or the boundary of the support region and flattens via projection by setting z=0along the coordinates. The paths are then translated into Shapely.Polygon objects.

```
""" Extract the outline of the overhang mesh region"""
poly = supportRegion.outline()
""" Convert the line to a 2D polygon"""
poly.vertices[:, 2] = 0.0
flattenPath, polygonTransform = poly.to_planar()
flattenPath.process()
flattenPath.apply_translation(polygonTransform[:2, 3])
polygon = flattenPath.polygons_full[0]
```

The polygon region is generated it provides the elementary building block for generating a support structure. This can be used to offset to prevent collision with self intersecting features. Internally, offsetting is useful to perform to regions so that any self-intersections with the geometry are clean.

### Region Extrusion and Self-Intersection Check

The first pass of the proposed algorithm requires performing a boolean intersection to identify if there are any self-intersections. The polygon regions require extrusion. Near-net shape extrusion is accomplished using a custom function `pyslm.support.extrudeFace`

. Unfortunately, this is not available within Trimesh, so instead it had to be implemented manually. This function extrudes a region of connected faces within a polygon, to set position or each individual face offset by an extruded distance.

```
# Extrude the surface to Z = 0
extrudedBlock = extrudeFace(supportSurface, None, 0)
# Extrude a triangle surface (Trimesh) based on the heights corresponding to each surface triangle
extrudedBlock = extrudeFace(surface, None, heightArray)
```

Having obtained an extruded prism from the support surface, a self-intersection test is performed with the original part. If no self-intersection takes place, this means the support structure has connectivity with the build platform. Under this situation, this drastically simplifies the number of steps required.

The intersection test requires a Boolean CSG operation. Quickly profiling a couple of tools available, from experience trying available solutions, the Cork Library was found to be both a reasonably accurate and high performance tool for manifold 3D geometries (i.e. those already required for 3D printing). The Nef Polyhedra implementation in the CGal library is renowned to be an accurate and robust implementation but slow. Due to these reasons, the PyCork library was created to provide a convenient wrapper across all platforms to perform this.

```
# Below is the expanded intersection operation used for intersecting a mesh
# cutMesh = pyslm.support.geometry.boolIntersect(part.geometry, extrudedMesh)
meshA = part.geometry
meshB = extrudedMesh
vertsOut, facesOut = pycork.intersection(meshA.vertices, meshA.faces, meshB.vertices, meshB.faces)
# Re-construct the Trimesh
cutMesh = trimesh.Trimesh(vertices=vertsOut, faces=facesOut, process=True)
# Identify if there is a self-intersection
if cutMesh.volume < BlockSupportGenerator._intersectionVolumeTolerance: # 50
# The support does not self intersect
else:
# The support intersects with the original part
```

In the situation that there is no intersection (or the volume is approximately zero), the support volume simply extrudes towards the build-plate. If a self-intersection occurs with the part, further calculations are required to process the block support.

## Self-Intersecting Support Structures

If the support-self intersects this is far more challenging problem to deal with. Through a lot of experimentation, the most reliable method determined involved using a form of ray-tracing to project the surfaces down. This has two benefits:

- Separating support regions across different heights
- Providing a robust method for generating cleaner support volumes with greater options to customise their behaviour

The ray projection test is useful generally, as it can also be used to provide a support generation map for the region, as shown in the previous post.

Originally the ray projection method was done using Trimesh.Ray, where rays are projected from each support face at a chosen ray projection resolution `BlockSupportGenerator.rayProjectionResolution`

. A grid is formed with seed points for the rays and these are projected upwards and downwards onto the previous self intersected support mesh. The ray intersection test is performed on upward facing surfaces extracted from the existing intersected mesh, in the previous region.

Later this was updated to use a GLSL GPU process for identifying this at a much higher resolution at significant reduction in computational cost as discussed in a previous post.

From the ray projection map, individual support block regions can be separated based on taking a threshold of the image gradient, using the gradThreshold function. Using simple trigonometry, the threshold to determine disconnected regions in the intersecting support are determined by the resolution of the ray projected image and the overhang angle, with an added ‘*fudge-factor*‘ thrown in.

Regions are separated based on this threshold using the isocontour method offered in Skimage’s`find_contours`

function. This is useful because it can identify supports regions connected only to the build-platform (desirable) and self-intersecting regions with the original part. Additionally, self-intersecting support regions with difference heights can also be isolated. These are useful in some marginal scenarios, but were more simpler methods breakdown.

The regions are identified by taking a threshold based on the choice of overhang angle using the `BlockSupportGenerator.gradThreshold`

.

```
def gradThreshold()
return 5.0 * np.tan(np.deg2rad(overhangAngle)) * rayProjectionDistance
# Calculate the gradient of the ray-projected height map for the support region
vx, vy = np.gradient(heightMap)
grads = np.sqrt(vx ** 2 + vy ** 2)
# A blur is used to smooth the boundaries
grads = scipy.ndimage.filters.gaussian_filter(grads, sigma=BlockSupportGenerator._gausian_blur_sigma)
"""
Find the outlines of any regions of the height map which deviate significantly
"""
outlines = find_contours(grads, self.gradThreshold(self.rayProjectionResolution, self.overhangAngle),
mask=heightMap > 2)
# Transform the outlines from image to global coordinates system
outlinesTrans = []
for outline in outlines:
outlinesTrans.append(outline * self.rayProjectionResolution + bbox[0, :2])
```

Once the outlines are obtained. The boundaries are created into polygons, offset, optionally smoothed and then translated into triangular meshes using `triangulate_polygon`

. Care must be taken when using spline-fitting to smooth the boundary as this can result in profiles not conforming to the original overhang region. The triangulation procedure internally can use either the earbox-cut algorithm or constrained Delaunay via the Triangle Library. The points of the polygon mesh are projected upwards and downwards on a subset of the previous intersected mesh to located the approximate volume before performing the final boolean operation.

```
# Create the outline and simplify the polygon using spline fitting (via Scipy)
mergedPoly = trimesh.load_path(outline)
mergedPoly.merge_vertices(1)
# Simplification and smoothing of the boundary is perform to provide smoother boundaries for generating a truss structure later.
mergedPoly = mergedPoly.simplify_spline(self._splineSimplificationFactor)
outPolygons = mergedPoly.polygons_full
"""
Triangulate the polygon into a planar mesh
"""
poly_tri = trimesh.creation.triangulate_polygon(bufferPoly, triangle_args='pa{:.3f}'.format(self.triangulationSpacing))
# Use a ray projection method onto the original geometry to identify upper and lower boundaries
coords = np.insert(poly_tri[0], 2, values=-1e-7, axis=1)
ray_dir = np.repeat([[0., 0., 1.]], coords.shape[0], axis=0)
# Find the first location of any triangles which intersect with the part
hitLoc, index_ray, index_tri = subregion.ray.intersects_location(ray_origins=coords,
ray_directions=ray_dir,
multiple_hits=False)
```

The same process is repeated, and an extruded prism is generated based on the ray-projection regions. Simplification of the interior triangulation is done in order to minimise the time to perform the intersection.

Finally, to obtain the ‘exact’ conforming intersected mesh, once again this is intersected with the previous mesh to obtain the final support volume region conforming to the original geometry.

As it can be observed, there are many steps to obtain the exactly conforming support volume with the original mesh. For the majority of most geometries that would be printed, this method is adequate, although not full-proof. There are a few cases where this algorithm will fail due to the use of a ray projection algorithm and relying on line-of-sight. For example, a continuous spiral or 3D helix structure with large connected surfaces will not be identifiable from the support generation algorithm. Without developing a specific mesh intersection library, it is difficult to identify alternative ways around this. Admittedly this is beyond my ability.