2021 SEP – 3D Geometry Calculations
3D Geometry Hull Calculations
Software Engineering Project 2021, Semester 2
Introduction
A resource model, or ‘pit’ on a mine site is broken into many discrete geometries for the purposes of creating
and executing the extraction of the material. Maptek’s scheduling package Evolution provides reporting on
how this material is moved from the pit to the resulting destinations such as a mill or waste dump. This
movement of material requires pathfinding to be done inside the pit, as trucks will drive along the top of these
3D geometries. To perform this calculation efficiently, a reduced representation of a set of geometries is
required, as is detailed in the following sections.
Part A. Hull Calculations – 3D Projections along an axis
Given a complex 3D geometry, calculate the 2D projection aligned with an axis. This is also known as
flattening the geometry, or calculating the hull of a 3D shape. A visualization of this can be seen in the left
image, where a 3D viewer is displaying some custom 3D geometry, and the camera is aligned with the Z
axis, displaying the geometry top down (this is also known as plan view). In this scenario, projecting along
the Z axis (up or down) would yield the following hull, depicted in the image on the right.
Figure 1: Plan view of 3D geometry Figure 2: Hull of the 3D geometry (Z-axis)
Projections do not have to be aligned with the Z axis, and flattening should be able to be done along any
axis. An example of this approach being used to project along any axis can be seen here:
Figure 3: Hull projections
www.maptek.com
Important Information
● This operation may have to run for many thousands of 3D geometries
● A given geometry may have as few as 8 vertices and 6 faces (a cube), or as many as a few
thousand vertices, with a few thousand faces
● Given that this operation will run on many geometries, the processing each geometry must be able
to run in parallel
● A method of GPU acceleration is not required, but would be preferred
● This algorithm can be written in any language, but must include a C# wrapper
Known caveats
● Both geometry and hulls may be concave or convex
● The geometries provided will be whole shapes but may have holes (doughnuts) or be disjoint
● Geometry may consist of faces perpendicular to the direction of flattening
Part B. Hull Aggregation
Geometries are often situated together in flat wafers. A given wafer can contain many hundreds of individual
geometries. In Part A, we wrote the code required to calculate the hull for any given geometry. Part B
requires the resulting hulls to be aggregated together into a single hull for the entire wafer. A simple example
can be seen below.
Side on
Top Down
Geometries shrunk to show boundaries
www.maptek.com
Expected Output
In the example here, individual geometries may share vertices and edges, however they may also have very
close, but not identical vertices and faces.
Important Information
● Some vertices and edges of hulls may be shared, or may almost overlap with small rounding errors.
In this case, the vertices & edges should be aggregated together to be a single edge. If this edge is
internal, it should be removed
Known caveats
● Combined hulls may be concave or convex
● Hulls may have holes (doughnuts) or be disjoint
● Geometry may consist of faces perpendicular to the direction of flattening
Part C. Hull Simplification
The resultant combined hulls will likely have many more vertices and edges than they require to give an
adequate approximation of the combined 2D hull. In the left image below, there are 27 vertices used to
represent the shape – highlighted in blue. If we were to reduce the number of vertices by half, we could get a
close approximation of the shape, given in the right image.
Figure 4: 2D hull with 27 vertices Figure 5: 2D hull with reduced vertices
www.maptek.com
When performing this reduction, choosing the correct vertices to keep is critical. For example, if four vertices
lie along a straight line, removing one, or both of the centre vertices would cause no loss in resultant fidelity:
Figure 6: Beneficial removal unused vertices
Conversely, if the four vertices were used to represent a corner, removing one or two vertices could cause a
large change in the resultant fidelity.
Figure 7: Detrimental removal of vertices
Part C requires the creation of a tool that can take a 2D hull, and a desired vertex count, and reduce the
shape while maintaining as much fidelity as possible.
Important Information
● There are many well known algorithms that are capable of performing this simplification
● Given that this operation will only occur on the combined hull of the 2D wafers, performance is less
critical than with Part A and Part B.
www.maptek.com