Command-Line Mesh Processing with Unreal Engine 4.26

This is the first of several tutorials that will (hopefully) teach you how to do advanced Mesh/Geometry Processing with Unreal Engine. Past Gradientspace Tutorials focused on the open-source Geometry3Sharp library that I developed in C#, and demonstrated how to do things like Mesh Simplification, Remeshing, Implicit Surface Modeling, and so on. G3Sharp became quite powerful, I used it to create the Cotangent 3D printing tool, and helped others use it to build Archform (a tool for designing dental aligners) and NiaFit (for designing 3D printable prosthetics). Quite a few other developers seemed to like it, too.

However, ultimately C# became a limiting factor for G3Sharp. I really like coding in C#, but the performance cost can be high, and critical math libraries like sparse linear solvers are missing from the C# ecosystem. The thought of porting even more WildMagic/GTEngine code, it was just too much! So, in December 2018 I joined Epic Games and started a C++ port of G3Sharp. Thanks to the hard work of the UE Geometry Team, this library - the GeometryProcessing plugin - has now far surpassed G3Sharp in capability. So, I think it’s about time to start showing you how to use it.

In this tutorial, I am going to walk you through a single example that generates all the meshes in the image below. In doing so, we will cover the main content of most of the previous GradientSpace G3Sharp tutorials, but in C++, in Unreal Engine. To avoid any UE complexity in this intro tutorial, we’re going to do everything in a simple command-line tool. But keep in mind that everything we’re going to do is available both in the Editor, and in-game at Runtime.

(Mandatory Disclaimer: your author, Ryan Schmidt, is an employee of Epic Games)

Translation for Chinese users: https://zhuanlan.zhihu.com/p/343789879

View fullsize

Preliminaries / UE4 Setup

View fullsize

Click to Enlarge

One small hurdle we have to overcome is that binary UE4 engine installations cannot build command-line executables. So, we’ll need to use the UE4 source, which you can get on Github once you have joined the Epic Games Github Organization (click link for instructions - it’s free for anyone who accepts the UE4 license agreement). This tutorial depends on code only available in version 4.26 or later, so I suggest you use the 4.26 branch (https://github.com/EpicGames/UnrealEngine/tree/4.26) directly (this tutorial should also work against the Release branch by the time you read it).

The simplest thing to do (in my opinion) is to use the Download Zip option, available under the Code drop-down button (see image to the right). Download and unzip (this will require about 1.7 GB of disk space). After that, you’ll need to run the Setup.bat file in the top-level folder, which will download another ~11GB of binary files and then run an installer that unpacks that into another ~40 GB. Unfortunately there is no more compact variant. Time for coffee!

The code for this tutorial is available on GitHub in the gradientspace UnrealMeshProcessingTools repository (click for link), in a folder named CommandLineGeometryTest in the UE4.26 samples subfolder. Again, you can download a zip of the top-level repository (click for direct link), or you can sync with a git client, too.

View fullsize

Assuming you unzipped the UE repository into a folder named “UnrealEngine-4.26”, then you’ll need to copy or move the sample code folder UE4.26\CommandLineGeometryTest to the path UnrealEngine-4.26\Engine\Source\Programs\, as shown in the image on the right. This folder contains various other command-line tools and apps that UE uses. You might be able to put it in other places, but this is where I tested it from, and where the sample HoleyBunny.obj file paths are hardcoded relative to.

For reference, I created this sample project based on the BlankProgram command-line executable that is included with the Engine (you can see it in the list on the right). This is a minimal Hello-World example program and a good starting point for any command-line executable based on UE (eg for unit testing, etc). The only modification I had to make to get things to work was to add references to several of the modules in the GeometryProcessing plugin, in the CommandLineGeometryTest.Build.cs file:

PrivateDependencyModuleNames.Add("GeometricObjects");
PrivateDependencyModuleNames.Add("DynamicMesh");

If you wanted to use these modules in other projects, you will have to do the same. Note that many parts of the Engine are not immediately available in a command-line or “Program” target type. For example in BlankProgram the UObject system is not initialized. The GeometryProcessing plugin modules have minimal engine dependencies, and do not define UObjects, so this is not a problem for this tutorial. (It is possible to initialize various engine systems, see for example the SlateViewer program.)

View fullsize

click to enlarge

Once you have the files in the right place, run the top-level GenerateProjectFiles.bat file. This will generate a Visual Studio 2019 UE4.sln file. Oh, by the way, you probably want to have Visual Studio 2019 installed, if you are on Windows. If you are on Linux or OSX, there are .command/.sh versions of the batch files I mentioned above, and this tutorial should work on those platforms, too. (GeometryProcessing has already been used in shipping games on desktop, mobile, and console platforms!!)

Open up UE4.sln, and you will find a long list of projects in the Solution Explorer subwindow. Find our CommandLineGeometryTest project, right-click on it, and select the Set as Startup Project option that appears in the context menu. Then click the Start Debugging button or hit F5. This will build for a minute or so, then pop up a command-line dialog box and print a bit of info as the tutorial runs (should only be a few seconds, though).

Note that this is not a full build of UE4. Since we are building a simple command-line app, we don’t have any dependencies on the majority of the Engine, or the Editor. A full build would take much longer - from ~15 minutes on my 24-core Threadripper to well over 2 hours on my 4-core laptop. So, make sure you don’t do a “Build Solution” or “Rebuild All”, or you are in for a long wait.

Tutorial Files

View fullsize

The sample code contains just a few files, all the code we care about is in CommandLineGeometryTest.cpp. The CommandLineGeometryTest.Build.cs and CommandLineGeometryTest.Target.cs are configuration files for the CommandLineGeometryTest UE4 module, and the CommandLineGeometryTest.h is empty.

The GeometryProcessing module does not natively support any file I/O, so the DynamicMeshOBJReader.h and DynamicMeshOBJWriter.h are necessary to read/write OBJ mesh files. The OBJ Reader is just a wrapper around the tinyobjloader library (https://github.com/tinyobjloader/tinyobjloader, source is embedded) which constructs a FDynamicMesh3 (the mesh class we will use). The OBJ Writer is minimalist, but does the basics.

CommandLineGeometryTest.cpp just contains #includes and a main() function, and I'm going to paste the entire tutorial code below. We'll step through the blocks afterwards, but I think it's instructive to skim through it all first. In less than 150 lines, this code demonstrates normals calculation, sphere and box generators, Mesh AABBTree setup and queries (nearest-point and ray-intersection), appending meshes, fast-winding-number-based resampling, implicit morphological operations, mesh simplification, isotropic remeshing, mesh hole filling, and mesh booleans (twice) ((yes, MESH BOOLEANS zomg!!)) :

// import an OBJ mesh. The path below is relative to the default path that Visual Studio will execute CommandLineGeometryTest.exe,
// when using a normal UE4.26 auto-generated UE.sln file. If things change you might need to update this path
FDynamicMesh3 ImportMesh;
FDynamicMeshOBJReader::Read("..\\..\\Source\\Programs\\CommandLineGeometryTest\\HoleyBunny.obj", ImportMesh, true, true, true);
// flip to UE orientation
ImportMesh.ReverseOrientation();

// print some mesh stats
UE_LOG(LogBlankProgram, Display, TEXT("Mesh has %d vertices, %d triangles, %d edges"), ImportMesh.VertexCount(), ImportMesh.TriangleCount(), ImportMesh.EdgeCount());
UE_LOG(LogBlankProgram, Display, TEXT("Mesh has %d normals"), ImportMesh.Attributes()->PrimaryNormals()->ElementCount());
UE_LOG(LogBlankProgram, Display, TEXT("Mesh has %d UVs"), ImportMesh.Attributes()->PrimaryUV()->ElementCount());

// compute per-vertex normals
FMeshNormals::QuickComputeVertexNormals(ImportMesh);

// generate a small box mesh to append multiple times
FAxisAlignedBox3d ImportBounds = ImportMesh.GetBounds();
double ImportRadius = ImportBounds.DiagonalLength() * 0.5;
FMinimalBoxMeshGenerator SmallBoxGen;
SmallBoxGen.Box = FOrientedBox3d(FVector3d::Zero(), ImportRadius * 0.05 * FVector3d::One());
FDynamicMesh3 SmallBoxMesh(&SmallBoxGen.Generate());

// create a bounding-box tree, then copy the imported mesh and make an Editor for it
FDynamicMeshAABBTree3 ImportBVTree(&ImportMesh);
FDynamicMesh3 AccumMesh(ImportMesh);
FDynamicMeshEditor MeshEditor(&AccumMesh);

// append the small box mesh a bunch of times, at random-ish locations, based on a Spherical Fibonacci distribution
TSphericalFibonacci<double> PointGen(64);
for (int32 k = 0; k < PointGen.Num(); ++k)
{
    // point on a bounding sphere
    FVector3d Point = (ImportRadius * PointGen.Point(k)) + ImportBounds.Center();

    // compute the nearest point on the imported mesh
    double NearDistSqr;
    int32 NearestTriID = ImportBVTree.FindNearestTriangle(Point, NearDistSqr);
    if (ImportMesh.IsTriangle(NearestTriID) == false)
        continue;
    FDistPoint3Triangle3d DistQueryResult = TMeshQueries<FDynamicMesh3>::TriangleDistance(ImportMesh, NearestTriID, Point);

    // compute the intersection between the imported mesh and a ray from the point to the mesh center
    FRay3d RayToCenter(Point, (ImportBounds.Center() - Point).Normalized() );
    int32 HitTriID = ImportBVTree.FindNearestHitTriangle(RayToCenter);
    if (HitTriID == FDynamicMesh3::InvalidID)
        continue;
    FIntrRay3Triangle3d HitQueryResult = TMeshQueries<FDynamicMesh3>::TriangleIntersection(ImportMesh, HitTriID, RayToCenter);

    // pick the closer point
    bool bUseRayIntersection = (HitQueryResult.RayParameter < DistQueryResult.Get());
    FVector3d UsePoint = (bUseRayIntersection) ? RayToCenter.PointAt(HitQueryResult.RayParameter) : DistQueryResult.ClosestTrianglePoint;

    FVector3d TriBaryCoords = (bUseRayIntersection) ? HitQueryResult.TriangleBaryCoords : DistQueryResult.TriangleBaryCoords;
    FVector3d UseNormal = ImportMesh.GetTriBaryNormal(NearestTriID, TriBaryCoords.X, TriBaryCoords.Y, TriBaryCoords.Z);

    // position/orientation to use to append the box
    FFrame3d TriFrame(UsePoint, UseNormal);

    // append the box via the Editor
    FMeshIndexMappings TmpMappings;
    MeshEditor.AppendMesh(&SmallBoxMesh, TmpMappings,
        [TriFrame](int32 vid, const FVector3d& Vertex) { return TriFrame.FromFramePoint(Vertex); },
        [TriFrame](int32 vid, const FVector3d& Normal) { return TriFrame.FromFrameVector(Normal); });
}

// make a new AABBTree for the accumulated mesh-with-boxes
FDynamicMeshAABBTree3 AccumMeshBVTree(&AccumMesh);
// build a fast-winding-number evaluation data structure
TFastWindingTree<FDynamicMesh3> FastWinding(&AccumMeshBVTree);

// "solidify" the mesh by extracting an iso-surface of the fast-winding field, using marching cubes
// (this all happens inside TImplicitSolidify)
int32 TargetVoxelCount = 64;
double ExtendBounds = 2.0;
TImplicitSolidify<FDynamicMesh3> SolidifyCalc(&AccumMesh, &AccumMeshBVTree, &FastWinding);
SolidifyCalc.SetCellSizeAndExtendBounds(AccumMeshBVTree.GetBoundingBox(), ExtendBounds, TargetVoxelCount);
SolidifyCalc.WindingThreshold = 0.5;
SolidifyCalc.SurfaceSearchSteps = 5;
SolidifyCalc.bSolidAtBoundaries = true;
SolidifyCalc.ExtendBounds = ExtendBounds;
FDynamicMesh3 SolidMesh(&SolidifyCalc.Generate());
// position the mesh to the right of the imported mesh
MeshTransforms::Translate(SolidMesh, SolidMesh.GetBounds().Width() * FVector3d::UnitX());

// offset the solidified mesh
double OffsetDistance = ImportRadius * 0.1;
TImplicitMorphology<FDynamicMesh3> ImplicitMorphology;
ImplicitMorphology.MorphologyOp = TImplicitMorphology<FDynamicMesh3>::EMorphologyOp::Dilate;
ImplicitMorphology.Source = &SolidMesh;
FDynamicMeshAABBTree3 SolidSpatial(&SolidMesh);
ImplicitMorphology.SourceSpatial = &SolidSpatial;
ImplicitMorphology.SetCellSizesAndDistance(SolidMesh.GetCachedBounds(), OffsetDistance, 64, 64);
FDynamicMesh3 OffsetSolidMesh(&ImplicitMorphology.Generate());

// simplify the offset mesh
FDynamicMesh3 SimplifiedSolidMesh(OffsetSolidMesh);
FQEMSimplification Simplifier(&SimplifiedSolidMesh);
Simplifier.SimplifyToTriangleCount(5000);
// position to the right
MeshTransforms::Translate(SimplifiedSolidMesh, SimplifiedSolidMesh.GetBounds().Width() * FVector3d::UnitX());

// generate a sphere mesh
FSphereGenerator SphereGen;
SphereGen.Radius = ImportMesh.GetBounds().MaxDim() * 0.6;
SphereGen.NumPhi = SphereGen.NumTheta = 10;
SphereGen.bPolygroupPerQuad = true;
SphereGen.Generate();
FDynamicMesh3 SphereMesh(&SphereGen);

// generate a box mesh
FGridBoxMeshGenerator BoxGen;
BoxGen.Box = FOrientedBox3d(FVector3d::Zero(), SphereGen.Radius * FVector3d::One());
BoxGen.EdgeVertices = FIndex3i(4, 5, 6);
BoxGen.bPolygroupPerQuad = false;
BoxGen.Generate();
FDynamicMesh3 BoxMesh(&BoxGen);

// subtract the box from the sphere (the box is transformed within the FMeshBoolean)
FDynamicMesh3 BooleanResult;
FMeshBoolean DifferenceOp(
    &SphereMesh, FTransform3d::Identity(),
    &BoxMesh, FTransform3d(FQuaterniond(FVector3d::UnitY(), 45.0, true), SphereGen.Radius*FVector3d(1,-1,1)),
    &BooleanResult, FMeshBoolean::EBooleanOp::Difference);
if (DifferenceOp.Compute() == false)
{
    UE_LOG(LogBlankProgram, Display, TEXT("Boolean Failed!"));
}
FAxisAlignedBox3d BooleanBBox = BooleanResult.GetBounds();
MeshTransforms::Translate(BooleanResult, 
    (SimplifiedSolidMesh.GetBounds().Max.X + 0.6*BooleanBBox.Width())* FVector3d::UnitX() + 0.5*BooleanBBox.Height()*FVector3d::UnitZ());

// make a copy of the boolean mesh, and apply Remeshing
FDynamicMesh3 RemeshBoolMesh(BooleanResult);
RemeshBoolMesh.DiscardAttributes();
FQueueRemesher Remesher(&RemeshBoolMesh);
Remesher.SetTargetEdgeLength(ImportRadius * 0.05);
Remesher.SmoothSpeedT = 0.5;
Remesher.FastestRemesh();
MeshTransforms::Translate(RemeshBoolMesh, 1.1*RemeshBoolMesh.GetBounds().Width() * FVector3d::UnitX());

// subtract the remeshed sphere from the offset-solidified-cubesbunny
FDynamicMesh3 FinalBooleanResult;
FMeshBoolean FinalDifferenceOp(
    &SimplifiedSolidMesh, FTransform3d(-SimplifiedSolidMesh.GetBounds().Center()),
    &RemeshBoolMesh, FTransform3d( (-RemeshBoolMesh.GetBounds().Center()) + 0.5*ImportRadius*FVector3d(0.0,0,0) ),
    &FinalBooleanResult, FMeshBoolean::EBooleanOp::Intersect);
FinalDifferenceOp.Compute();

// The boolean probably has some small cracks around the border, find them and fill them
FMeshBoundaryLoops LoopsCalc(&FinalBooleanResult);
UE_LOG(LogBlankProgram, Display, TEXT("Final Boolean Mesh has %d holes"), LoopsCalc.GetLoopCount());
for (const FEdgeLoop& Loop : LoopsCalc.Loops)
{
    FMinimalHoleFiller Filler(&FinalBooleanResult, Loop);
    Filler.Fill();
}
FAxisAlignedBox3d FinalBooleanBBox = FinalBooleanResult.GetBounds();
MeshTransforms::Translate(FinalBooleanResult,
    (RemeshBoolMesh.GetBounds().Max.X + 0.6*FinalBooleanBBox.Width())*FVector3d::UnitX() + 0.5*FinalBooleanBBox.Height()*FVector3d::UnitZ() );

// write out the sequence of meshes
    FDynamicMeshOBJWriter::Write("..\\..\\Source\\Programs\\CommandLineGeometryTest\\HoleyBunny_processed.obj", 
    { AccumMesh, SolidMesh, SimplifiedSolidMesh, BooleanResult, RemeshBoolMesh, FinalBooleanResult }, true);

Import and Attributes

Ok lets step through the code. The first block just reads a mesh, prints some information, and computes normals (just a reminder, as I mentioned above, FDynamicMeshOBJReader is not part of UE4, this is a class included with the sample code). Note the call to FDynamicMesh3::ReverseOrientation(). Whether this is necessary depends on your input file, but generally, UE4 uses a left-handed coordinate system, while most content tools are right-handed. This means that a right-handed mesh, when imported into UE4, will be “inside-out”, and so (for example) the positive/outward surface normal direction for that mesh would point inwards. If we ReverseOrientation() on import, and again on export, then things will be fine.

// import an OBJ mesh. The path below is relative to the default path that Visual Studio will execute CommandLineGeometryTest.exe,
// when using a normal UE4.26 auto-generated UE.sln file. If things change you might need to update this path
FDynamicMesh3 ImportMesh;
FDynamicMeshOBJReader::Read("..\\..\\Source\\Programs\\CommandLineGeometryTest\\HoleyBunny.obj", ImportMesh, true, true, true);
// flip to UE orientation
ImportMesh.ReverseOrientation();

// print some mesh stats
UE_LOG(LogBlankProgram, Display, TEXT("Mesh has %d vertices, %d triangles, %d edges"), ImportMesh.VertexCount(), ImportMesh.TriangleCount(), ImportMesh.EdgeCount());
UE_LOG(LogBlankProgram, Display, TEXT("Mesh has %d normals"), ImportMesh.Attributes()->PrimaryNormals()->ElementCount());
UE_LOG(LogBlankProgram, Display, TEXT("Mesh has %d UVs"), ImportMesh.Attributes()->PrimaryUV()->ElementCount());

// compute per-vertex normals
FMeshNormals::QuickComputeVertexNormals(ImportMesh);

There is nothing special about the logging calls, I just wanted to have a reason to mention the calls to Attributes(), which return a FDynamicMeshAttributeSet. The design of FDynamicMesh3 is quite similar to DMesh3 from Geometry3Sharp, to the point where this documentation on DMesh3 basically applies directly to FDynamicMesh3. However, one major addition that has been made in the GeometryProcesing implementation is support for arbitrary Attribute Sets, including per-triangle indexed Attributes which allow for representation of things like split normals and proper UV islands/atlases/overlays (depending on your preferred terminology). Generally, mesh editing operations in GeometryProcessing (eg like the mesh edge splits/flips/collapses, the FDynamicMeshEditor, the Simplifier and Remeshers, change tracking, etc) handle updating the Attribute Sets automatically.

Generating a Box Mesh

The next step is to generate a simple box, that we are going to append to the imported bunny a bunch of times. There are a variety of mesh generators in the /Public/Generators/ subfolder in the GeometricObjects module. FMinimalBoxMeshGenerator makes a box with 12 triangles, and we’ll use FGridBoxMeshGenerator later to generate a subdivided box. The GeometricObjects module also includes a library of basic geometry and vector-math types, templated on Real type, with typedefs for float and double. So FAxisAlignedBox3d is a 3D double-precision axis-aligned bounding box, while FAxisAlignedBox2f is a 2D float variant. Conversions to the standard FVector/FBox/etc UE4 types are defined wherever possible (implicit where safe, otherwise via casts). However generally the GeometryProcessing library will calculate in double precision if not templated on Real type.

// generate a small box mesh to append multiple times
FAxisAlignedBox3d ImportBounds = ImportMesh.GetBounds();
double ImportRadius = ImportBounds.DiagonalLength() * 0.5;
FMinimalBoxMeshGenerator SmallBoxGen;
SmallBoxGen.Box = FOrientedBox3d(FVector3d::Zero(), ImportRadius * 0.05 * FVector3d::One());
FDynamicMesh3 SmallBoxMesh(&SmallBoxGen.Generate());

You will note that nearly every type is prefixed with “F”. This is a UE4 convention, generally all structs and classes have an F prefix. Similarly the code here basically follows the UE4 coding standard (which includes quite a bit more whitespace than I generally prefer, but it is what it is).

Making an AABBTree

This is a one-liner, the constructor for FDynamicMeshAABBTree3 will automatically build the AABBTree (this can be disabled with an optional argument). The AABBTree construction is quite fast and there generally is no excuse to use something less reliable (or, horror of horrors, a linear search). Similarly copying a FDynamicMesh3 is very quick, as the storage for the mesh does not involve per-element pointers, it is all in chunked arrays (see TDynamicVector) that can be memcopied. Finally this block creates a FDynamicMeshEditor, which implements a many common low-level mesh editing operations. If you need to do something it doesn’t do, it’s generally a better idea to try and break your problem down into operations that are already implemented, even at the cost of some efficiency, as handling Attribute Set updates gets quite hairy.

// create a bounding-box tree, then copy the imported mesh and make an Editor for it
FDynamicMeshAABBTree3 ImportBVTree(&ImportMesh);
FDynamicMesh3 AccumMesh(ImportMesh);
FDynamicMeshEditor MeshEditor(&AccumMesh);

If you were to look at the code for FDynamicMeshAABBTree3, you would find that it is just a typedef for TMeshAABBTree3<FDynamicMesh3>. The AABBTree is templated on mesh type, as only a few functions on the mesh are required. The FTriangleMeshAdapterd struct can be used to wrap virtually any indexed mesh in an API that will work with TMeshAABBTree3, as well as TMeshQueries<T> which supports many types of generic mesh…queries.

AABBTree Queries

This is a large block because we’re going to do a bit of logic, but the critical parts are the calls to FDynamicMeshAABBTree3::FindNearestTriangle() and FDynamicMeshAABBTree3::FindNearestHitTriangle(). These are two of the most common queries on an AABBTree. Note that in both cases, the query only returns an integer triangle ID/index, and then TMeshQueries<T> is used to execute and return a FDistPoint3Triangle3d/FIntrRay3Triangle3d object. Those classes can also be used directly. They return various information calculated for a point-triangle distance query, or ray-tri intersection. Distance and Intersection queries in GeometryProcessing are generally implemented in this style, and the calculation objects store any useful intermediate information which otherwise might be discarded. In some cases the FDistXY / FIntrXY class has static functions that will do a more minimal computation. The AABBTree class also has a ::FindNearestPoint() helper function (but no similar ray-intersection variant).

// append the small box mesh a bunch of times, at random-ish locations, based on a Spherical Fibonacci distribution
TSphericalFibonacci<double> PointGen(64);
for (int32 k = 0; k < PointGen.Num(); ++k)
{
    // point on a bounding sphere
    FVector3d Point = (ImportRadius * PointGen.Point(k)) + ImportBounds.Center();

    // compute the nearest point on the imported mesh
    double NearDistSqr;
    int32 NearestTriID = ImportBVTree.FindNearestTriangle(Point, NearDistSqr);
    if (ImportMesh.IsTriangle(NearestTriID) == false)
        continue;
    FDistPoint3Triangle3d DistQueryResult = TMeshQueries<FDynamicMesh3>::TriangleDistance(ImportMesh, NearestTriID, Point);

    // compute the intersection between the imported mesh and a ray from the point to the mesh center
    FRay3d RayToCenter(Point, (ImportBounds.Center() - Point).Normalized() );
    int32 HitTriID = ImportBVTree.FindNearestHitTriangle(RayToCenter);
    if (HitTriID == FDynamicMesh3::InvalidID)
        continue;
    FIntrRay3Triangle3d HitQueryResult = TMeshQueries<FDynamicMesh3>::TriangleIntersection(ImportMesh, HitTriID, RayToCenter);

    // pick the closer point
    bool bUseRayIntersection = (HitQueryResult.RayParameter < DistQueryResult.Get());
    FVector3d UsePoint = (bUseRayIntersection) ? RayToCenter.PointAt(HitQueryResult.RayParameter) : DistQueryResult.ClosestTrianglePoint;

    FVector3d TriBaryCoords = (bUseRayIntersection) ? HitQueryResult.TriangleBaryCoords : DistQueryResult.TriangleBaryCoords;
    FVector3d UseNormal = ImportMesh.GetTriBaryNormal(NearestTriID, TriBaryCoords.X, TriBaryCoords.Y, TriBaryCoords.Z);

    // position/orientation to use to append the box
    FFrame3d TriFrame(UsePoint, UseNormal);

    // append the box via the Editor
    FMeshIndexMappings TmpMappings;
    MeshEditor.AppendMesh(&SmallBoxMesh, TmpMappings,
        [TriFrame](int32 vid, const FVector3d& Vertex) { return TriFrame.FromFramePoint(Vertex); },
        [TriFrame](int32 vid, const FVector3d& Normal) { return TriFrame.FromFrameVector(Normal); });
}

The final call in the block above appends the SmallBoxMesh we created above, via the FDynamicMeshEditor. The two lambdas transform the vertices and normals of the box mesh (which is centered at the origin) to be aligned with the surface position and normal we calculated using the distance/ray-intersection. This is done via a FFrame3d, which is a class that is heavily used in GeometryProcessing.

A TFrame3<T> is a 3D position (referred to as the .Origin) and orientation (.Rotation), which is represented as a TQuaternion<T>, so essentially like a standard FTransform without any scaling. However the TFrame3 class has an API that allows you to treat the Frame as a set of 3D orthogonal axes positioned in space. So for example the X(), Y(), and Z() functions return the three axes. There are also various ToFrame() and FromFrame() functions (in the case of FVector3<T> you must differentiate between Point and Vector, but for other types there are overloads). ToFrame() maps geometry into the local coordinate system of the frame, so for example ToFramePoint(P) returns returns a new position that measures the distance from P to the Frame.Origin along each of it’s three axes. FromFrame() does the inverse, mapping points “in” the Frame into “world space” (as far as the Frame is concerned). So in the code above, we are treating the cube as being “in” the Frame coordinate system, and mapping it onto the mesh surface.

A final note, the FFrame3d(Point, Normal) constructor used above results in a Frame with “Z” aligned with the Normal, and somewhat arbitrary X and Y axes. In many cases you might wish to construct a Frame with specific tangent-plane axes. There is a constructor that takes X/Y/Z, but a frequent case is where you have a Normal and another direction that is not necessarily orthogonal to the Normal. In that case you can construct with Z=Normal and then use the ::ConstrainedAlignAxis() function to best-align one of the other Frame axes (eg axis X/0) with a target direction, by rotating around the Z.

“Solidification” with the Fast Mesh Winding Number

Several previous Gradientspace tutorials [1] [2] used the Fast Mesh Winding Number to reliably compute Point Containment (ie inside/outside testing) on meshes. An implementation of the Fast Mesh Winding Number is available in GeometricObjects as TFastWindingTree<T>, where T is FDynamicMesh3 or a MeshAdapter. This data structure is built on top of a TMeshAABBTree<T>. In the code below we construct one of these, and then use a TImplicitSolidify<T> object to generate a new “solidified” mesh. TImplicitSolidify interprets the inside/outside values produced by TFastWindingTree as an Implicit Surface (see previous tutorial) and uses the FMarchingCubes class to generate a triangle mesh for that implicit.

// make a new AABBTree for the accumulated mesh-with-boxes
FDynamicMeshAABBTree3 AccumMeshBVTree(&AccumMesh);
// build a fast-winding-number evaluation data structure
TFastWindingTree<FDynamicMesh3> FastWinding(&AccumMeshBVTree);

// "solidify" the mesh by extracting an iso-surface of the fast-winding field, using marching cubes
// (this all happens inside TImplicitSolidify)
int32 TargetVoxelCount = 64;
double ExtendBounds = 2.0;
TImplicitSolidify<FDynamicMesh3> SolidifyCalc(&AccumMesh, &AccumMeshBVTree, &FastWinding);
SolidifyCalc.SetCellSizeAndExtendBounds(AccumMeshBVTree.GetBoundingBox(), ExtendBounds, TargetVoxelCount);
SolidifyCalc.WindingThreshold = 0.5;
SolidifyCalc.SurfaceSearchSteps = 5;
SolidifyCalc.bSolidAtBoundaries = true;
SolidifyCalc.ExtendBounds = ExtendBounds;
FDynamicMesh3 SolidMesh(&SolidifyCalc.Generate());
// position the mesh to the right of the imported mesh
MeshTransforms::Translate(SolidMesh, SolidMesh.GetBounds().Width() * FVector3d::UnitX());

The TImplicitSolidify code is relatively straightforward, and we could have easily used FMarchingCubes here directly. However, you will find that there are many such “helper” classes like TImplicitSolidify in the GeometryProcessing modules. These classes reduce the amount of boilerplate necessary to do common mesh processing operations, making it easier to implement “recipes” and/or user interfaces that expose certain parameters.

Mesh Morphological Operations and Mesh Simplification

We’ve now generated a “solid” mesh of our holey-bunny-plus-boxes. The next step is to offset this mesh. Offset can be done directly on the mesh triangles, but it can also be considered a Morphological Operation, sometimes referred to as ‘Dilation’ (and a negative offset would be an ‘Erosion’). There are also more interesting Morphological Operations like ‘Opening’ (Erode, then Dilate) and ‘Closure’ (Dilate, then Erode), which is particularly useful for filling small holes and cavities. These are generally quite difficult to implement directly on a mesh, but easily done with implicit surface / level-set techniques in the TImplicitMorphology<T> class. Similar to TImplicitSolidify, this class builds the necessary data structures and uses FMarchingCubes to generate an output mesh.

// offset the solidified mesh
double OffsetDistance = ImportRadius * 0.1;
TImplicitMorphology<FDynamicMesh3> ImplicitMorphology;
ImplicitMorphology.MorphologyOp = TImplicitMorphology<FDynamicMesh3>::EMorphologyOp::Dilate;
ImplicitMorphology.Source = &SolidMesh;
FDynamicMeshAABBTree3 SolidSpatial(&SolidMesh);
ImplicitMorphology.SourceSpatial = &SolidSpatial;
ImplicitMorphology.SetCellSizesAndDistance(SolidMesh.GetCachedBounds(), OffsetDistance, 64, 64);
FDynamicMesh3 OffsetSolidMesh(&ImplicitMorphology.Generate());

// simplify the offset mesh
FDynamicMesh3 SimplifiedSolidMesh(OffsetSolidMesh);
FQEMSimplification Simplifier(&SimplifiedSolidMesh);
Simplifier.SimplifyToTriangleCount(5000);
// position to the right
MeshTransforms::Translate(SimplifiedSolidMesh, SimplifiedSolidMesh.GetBounds().Width() * FVector3d::UnitX());

Marching Cubes meshes are generally very dense, and so it’s a common pattern to Simplify the mesh afterwards. This can be done in a few lines using the FQEMSimplification class, which has a variety of simplification criteria you can specify. There are also several other Simplifier implementations, in particular FAttrMeshSimplification will consider the normal and UV Attribute Overlays.

Mesh Booleans (!!!)

It’s the moment you’ve been waiting for - Mesh Booleans! In this block we first use FSphereGenerator and FGridBoxGenerator to generate two meshes, and then use FMeshBoolean to subtract the Box from the Sphere. The FMeshBoolean constructor takes a transform for each input mesh, but only supports two input meshes (ie it’s not an N-way Boolean). If you would like to use multiple input meshes, you will have to use repeated FMeshBoolean operations, but if the inputs are not intersecting it can be more efficient to combine them using FDynamicMeshEditor::AppendMesh() first.

// generate a sphere mesh
FSphereGenerator SphereGen;
SphereGen.Radius = ImportMesh.GetBounds().MaxDim() * 0.6;
SphereGen.NumPhi = SphereGen.NumTheta = 10;
SphereGen.bPolygroupPerQuad = true;
SphereGen.Generate();
FDynamicMesh3 SphereMesh(&SphereGen);

// generate a box mesh
FGridBoxMeshGenerator BoxGen;
BoxGen.Box = FOrientedBox3d(FVector3d::Zero(), SphereGen.Radius * FVector3d::One());
BoxGen.EdgeVertices = FIndex3i(4, 5, 6);
BoxGen.bPolygroupPerQuad = false;
BoxGen.Generate();
FDynamicMesh3 BoxMesh(&BoxGen);

// subtract the box from the sphere (the box is transformed within the FMeshBoolean)
FDynamicMesh3 BooleanResult;
FMeshBoolean DifferenceOp(
    &SphereMesh, FTransform3d::Identity(),
    &BoxMesh, FTransform3d(FQuaterniond(FVector3d::UnitY(), 45.0, true), SphereGen.Radius*FVector3d(1,-1,1)),
    &BooleanResult, FMeshBoolean::EBooleanOp::Difference);
if (DifferenceOp.Compute() == false)
{
    UE_LOG(LogGeometryTest, Display, TEXT("Boolean Failed!"));
}
FAxisAlignedBox3d BooleanBBox = BooleanResult.GetBounds();
MeshTransforms::Translate(BooleanResult, 
    (SimplifiedSolidMesh.GetBounds().Max.X + 0.6*BooleanBBox.Width())* FVector3d::UnitX() + 0.5*BooleanBBox.Height()*FVector3d::UnitZ());

Note that the MeshBoolean is not 100% reliable. Below I will show how to (try to) handle failures.

Remeshing

Next we apply a pass of isotropic triangular remeshing to the Boolean result. This is a standard step if you are planning on doing further mesh processing like deformations/smoothing/etc, as output of a Mesh Boolean often has highly variable triangle size/density (which constraints how the mesh can move) and sliver triangles that can cause numerical issues. The standard approach is to use FRemesher and run a fixed number of passes over the full mesh. Below I used FQueueRemesher, which produces nearly the same result, but rather than full-mesh passes, an “active queue” of meshes that need to be processed is tracked. This can be significantly faster (particularly on large meshes).

// make a copy of the boolean mesh, and apply Remeshing
FDynamicMesh3 RemeshBoolMesh(BooleanResult);
RemeshBoolMesh.DiscardAttributes();
FQueueRemesher Remesher(&RemeshBoolMesh);
Remesher.SetTargetEdgeLength(ImportRadius * 0.05);
Remesher.SmoothSpeedT = 0.5;
Remesher.FastestRemesh();
MeshTransforms::Translate(RemeshBoolMesh, 1.1*RemeshBoolMesh.GetBounds().Width() * FVector3d::UnitX());

I covered the basics of Isotropic Remeshing in a previous G3Sharp tutorial. That tutorial basically applies directly to the UE4 GeometryProcessing implementation, down to the type and field names (don’t forget to add F). However the UE4 version is quite a bit more capable, for example the FQueueRemesher is much faster, and there is also FSubRegionRemesher which can remesh a portion of a larger mesh.

Two notes about the block above. First, I did not use a Projection Target (described in the linked tutorial), so the nice crisp edges of the sphere-minus-cube will be smoothed away. Setting up a Projection Target only takes a few lines, search for any usage of FMeshProjectionTarget in the Engine code. Second, the first thing I did after making the mesh copy above is to call RemeshBoolMesh.DiscardAttributes(). This call removes all attribute overlays from the mesh, specifically the per-triangle the UV and Normal layers. The Remeshers do support remeshing with per-triangle attributes, however it is more complex because those attributes have additional topological constraints that must be preserved. The utility function FMeshConstraintsUtil::ConstrainAllBoundariesAndSeams() can be used to more-or-less automatically set all that up, but even just calling that is a bit complicated, so I thought I would save it for a future tutorial (look up FRemeshMeshOp if you want to see an example).

Hole Filling and Boolean Failure Handling

View fullsize

Finally, we are going to compute the Boolean Intersection of the smoothed-out-sphere-minus-cube with the solidified-offset-cubesbunny. This is again just a single construction of a FMeshBoolean object and a call to Compute(). However, in this case the input objects are quite complex and it’s relatively likely that the Mesh Boolean output is not fully closed.

Why? Well, Mesh Booleans are notoriously difficult to compute reliably. If you have used tools like Maya or Max over many years, you will recall that Mesh Booleans used to be extremely unreliable, and then at some points they switched to being somewhat more reliable. This is mainly due to those packages changing which third-party Mesh Boolean library they were using. There actually aren’t that many to choose from. The CGAL library has quite powerful Polyhedral Booleans, but they are very, very slow, and cannot be redistributed with a commercial game engine. Carve is used by Blender, and is quite good, but it is GPL-licensed. Cork is reasonably capable but not actively maintained. The Mesh Booleans in LibIGL use the recently-introduced Mesh Arrangements technique and are basically the current state-of-the-art, but are also somewhat slow on large meshes, and depend on some CGAL code. If you dig, you will find that the Booleans available in many commercial tools or open-source libraries are using one of these four.

Another complication with third-party mesh boolean libraries is they generally don’t support arbitrary complex mesh atttributes, like the indexed per-triangle overlays I mentioned above. So, in UE4.26 we wrote our own. One benefit to writing an implementation specifically for FDynamicMesh3 is that we could take advantage of some modern triangle-mesh-processing techniques. For example when previous Mesh Booleans failed catastrophically, ie with parts of the output disappearing, it was often because they couldn’t geometrically tell what was “inside” and “outside”. Now that we have the Fast Mesh Winding Number, this is basically a solved problem, and as a result UE4’s FMeshBoolean tends to fail in a way that is localized, and often recoverable. For example in the images above-right, the sphere mesh has a giant hole in it, usually a no-go for a Mesh Boolean, but as long as the intersection curve is well-defined, FMeshBoolean will usually work. Even if it does (lower image), the Boolean no longer really makes sense, but the failure is not catastrophic, we just get a hole where the hole is.

So, all of that is a long-winded way of saying that if your FMeshBoolean::Compute() returns false, it’s probably got some holes and you can fill them. The FMeshBoundaryLoops object will extract a set of FEdgeLoop objects that represent the open boundary loops of a mesh (another surprisingly difficult problem…) and then FMinimalHoleFiller will fill them (we also have FPlanarHoleFiller and FSmoothHoleFiller but they likely aren’t applicable in this context). Note that most of the “holes” are zero-area cracks along the intersection curve between the two objects, so it can be helpful to collapse away degenerate triangles (something the library does not do automatically, yet).

// subtract the remeshed sphere from the offset-solidified-cubesbunny
FDynamicMesh3 FinalBooleanResult;
FMeshBoolean FinalDifferenceOp(
    &SimplifiedSolidMesh, FTransform3d(-SimplifiedSolidMesh.GetBounds().Center()),
    &RemeshBoolMesh, FTransform3d( (-RemeshBoolMesh.GetBounds().Center()) + 0.5*ImportRadius*FVector3d(0.0,0,0) ),
    &FinalBooleanResult, FMeshBoolean::EBooleanOp::Intersect);
FinalDifferenceOp.Compute();

// The boolean probably has some small cracks around the border, find them and fill them
FMeshBoundaryLoops LoopsCalc(&FinalBooleanResult);
UE_LOG(LogGeometryTest, Display, TEXT("Final Boolean Mesh has %d holes"), LoopsCalc.GetLoopCount());
for (const FEdgeLoop& Loop : LoopsCalc.Loops)
{
    FMinimalHoleFiller Filler(&FinalBooleanResult, Loop);
    Filler.Fill();
}
FAxisAlignedBox3d FinalBooleanBBox = FinalBooleanResult.GetBounds();
MeshTransforms::Translate(FinalBooleanResult,
    (RemeshBoolMesh.GetBounds().Max.X + 0.6*FinalBooleanBBox.Width())*FVector3d::UnitX() + 0.5*FinalBooleanBBox.Height()*FVector3d::UnitZ() );

The GeometryProcessing Library

The examples above have shown you how to use a handful of the data structures and algorithms in the GeometryProcessing Plugin. There are many, many more, and even the ones used above have many more options and capabilities. You will find all the code in \Engine\Plugins\Experimental\GeometryProcessing\, there are four modules:

• GeometryObjects: templated vector-math and geometry types, Distance and Intersection computations, spatial data structures like AABBTrees/Octrees/Grids/HashTables, and Grids, Mesh Generators, 2D graphs and polygons, generic mesh algorithms (not specific to FDynamicMesh3), and Implicit Surfaces

• DynamicMesh: FDynamicMesh3 and related data structures, booleans and cutting, editing operations like extrusions and offsets, deformation, sampling, parameterization, baking, shape fitting, and so on. Nearly all the Mesh Processing code is here

• GeometryAlgorithms: Computational-Geometry algorithm implementations like Delaunay Triangulation, Convex Hulls, Line Segment Arrangement, and so on. This module uses the third-party boost-licensed GTEngine library in some places (included in /Private/ThirdParty/) and also Shewchuck’s Exact Predicates.

• MeshConversion: Helper classes for converting between mesh types. Currently main for converting to/from FMeshDescription, the other main mesh format used in Unreal Engine.

I encourage you to explore. If you find a class or function that looks interesting but aren’t sure exactly how to use it, you will almost certainly find some usage elsewhere in the Engine codebase. One great thing about Unreal Engine is you have the code for literally everything, including the Editor. So if you see something interesting when using the Modeling Tools Editor Mode, and want to know how to do it yourself, you can find the code in the MeshModelingToolset plugin. This is built on top of GeometryProcessing and implements nearly all the interactive in-Editor Tools.

Many of those Tools (particularly the ones that are more “set options and process” and less “pointy-clicky”) are split into the Tool-level code (in the MeshModelingTools module) and what we call an “Operator” (in the ModelingOperators module). An Operator is basically an object that executes a more complex multi-step mesh processing recipe, with higher-level parameters exposed. So for example the FBooleanMeshesOp operator ultimately runs a FMeshBoolean on two input FDynamicMesh3, however it will automatically do the hole-filling repair step above if bAttemptFixHoles is set to true. Operators are safe to run on background threads, and take a FProgressCancel object, which can be used to safely abort their computation if they take too long.

Create your own In-Editor Geometry Processing Tools

This tutorial has shown you how to use the GeometryProcessing modules in a a command-line tool. However, as I mentioned above, this plugin can be used to implement the same mesh processing in the Editor. My previous tutorial on using LibIGL in UE 4.24 to make an interactive mesh smoothing tool in the Editor already showed how to do this!! That tutorial ultimately reduced the problem to implementing a MakeMeshProcessingFunction() function that returned a TUniqueFunction<void(FDynamicMesh3&)>, ie a lambda that processed the input FDynamicMesh3. In that tutorial we wanted to call LibIGL code so we converted to/from the LibIGL mesh format. But now you know that you can also just skip LibIGL and edit the input mesh using GeometryProcessing code directly!

I have updated that tutorial for UE 4.26, there is a small addendum explaining the necessary changes. In UE 4.26 we added a new “base tool” class UBaseGeometryProcessingTool which makes the code for that tutorial much simpler.

As I mentioned, the GeometryProcessing Plugin is made up of Runtime modules, so there is nothing stopping you from using it in your games, either. I will be exploring this in future tutorials - stay tuned!