Building Branching Structures with PCG & Geometry Script

Contents show

My indie game project, codenamed Moonflower, requires creating a small forest where huge trees and their roots form the structure of the environment. Gameplay, terrain and content placement are heavily intertwined with the trees. An ideal solution would be to create and edit these structures in-engine. If the level design process was done in a DCC, it would make sense to focus tooling there, but this project is leveraging the evolving procedural tooling in Unreal. As tools such as PCG and Geometry Script develop features such as Geometry Processing and Grammar, we can augment level editing tools to create a smoother experience with less dependencies. These outputs can then be further refined by hand or piped into Houdini to generate more detailed results.

The result of researching this topic is a plugin I call Tree Designer, which allows editing and generation of organic branching structures directly in Unreal Editor. The underlying primitive component, Graph3D, can be used for many other things such as paths, rivers, pipes, AI patrols or gameplay mechanics.

I prototyped this system in Houdini, then found ways to adapt that implementation to PCG & Geometry Script. This wouldn’t have been possible without Nebukam’s excellent PCG graph toolkit, PCGEx.

Blockout with Tree Designer, overpaint in Photoshop

Implementing Branching Structures

Splines

Splines are a popular option for procedural generation and work very well for closed shapes, paths and grid structures. However, they are an awkward way to represent a branching 3D structure for a few reasons:

One segment = One component. This isn’t a dealbreaker but represents a workflow issue: there are some extra clicks necessary to switch from editing one component’s elements to another. Also, for dense structures the component overhead may be a performance issue.
No branching. This would require a custom solution or manual readjustment of multiple splines to achieve one edit.

Scriptable Tool

Using the Interactive Tool Framework, we can create custom editor states known as Scriptable Tools. One example I’ve found this useful for is painting custom data into vertex colours and textures, such as flow maps.

Primitive Component

By creating a custom Scene Component & a Component Visualizer, we can store & manipulate data using the default editor transform gizmo, keyboard shortcuts and right-click context menus. By inheriting from Primitive Component (e.g. Splines & Static Mesh Components), we can render a proxy and select it in the scene.

For this project, I’ve decided to create a Primitive Component to represent a directional graph. With Nodes & Edges we can create a minimal data structure with built in branching. This solution provides a quick, seamless editing experience while allowing for extension through inheritance, scriptable tools, generators and content placement systems. It could also be extended with tangent handles if spline-like behaviour is needed, or simply re-sampled as interpolating curves while retaining the underlying connectivity.

C++

USTRUCT(BlueprintType)
struct FGraph3DNode {
	GENERATED_BODY()

public:

	UPROPERTY(EditAnywhere, BlueprintReadWrite)
	FVector Position;
	UPROPERTY(EditAnywhere, BlueprintReadWrite)
	FString Tag;

	FORCEINLINE bool operator==(const FGraph3DNode& Other) const
	{
		return Other.Position == Position;
	}
};

USTRUCT(BlueprintType)
struct FGraph3DEdge {
	GENERATED_BODY()

public:

	UPROPERTY(EditAnywhere, BlueprintReadWrite)
	int32 Start;
	UPROPERTY(EditAnywhere, BlueprintReadWrite)
	int32 End;

	FORCEINLINE bool operator==(const FGraph3DEdge& Other) const
	{
		return (Start == Other.Start && End == Other.End);
	}
	
};

For Nodes, we are storing a position and a tag (useful for adding meta-data e.g. broken branch, cut stump) The Graph3D class contains functions for safely editing the data structure. The base functionality is encapsulated in a plug-in, and content-specific implementations are kept in an editor module.

Prototyping in Houdini

To make something useful from a graph we need to identify elements of the structure – trunk, roots, branches and end-points.

Custom data as an Input

Instead of converting the graph structure to a mesh, I opted to directly send the data structure to Houdini via a hidden multi-parameter. Currently this is done with an editor function, which uploads the parameters with HAPI and cooks the asset.
The data can then be reconstructed in VEX, as points and edges.

Finding Branches & roots

End points can be found by checking the amount of neighbours a point has (valence or degree). From the predefined origin point, we can then naïvely classify branches and roots by checking if the end-point is above or below the origin. This could also be done by using the direction of the branch directly from the origin instead of using the end-point.

Separating The Structure

For clean mesh generation with good UVs, we need to split the graph into linear curves. It is possible to quickly mesh a network using the Polywire SOP, but intersections are prone to buckling and there will be UV artifacts. A clean mesh could then be generated with Quad Remesh & Labs Auto UV but this will lose the flow of the structure.

To break the structure up into generations of branches, first find the trunk by getting the shortest path from a root (e.g. the lowest or most centered) to the highest branch. Removing the trunk, we can then iteratively perform the same process up to a chosen depth (or until the whole graph has been traversed).

Meshing

Now each generation can be processed, adding onto the trunk. At this point more advanced intersection blending (e.g. SpeedTree) could be done by cropping the base of the branch & raycasting onto the trunk structure – however because this is a blockout tool and not for generating final art, I’m skipping that step for faster and cleaner results.

To create visual continuity, I’ve transferred normal information from the trunk to each branch:

There are alternative methods for generating a mesh, such as sweeping curves along curves, which could be useful for creating a high-poly base:

Spawning Leaf Instances

The final step is fairly straightforward – scatter points on the branches and align them, then spawn instances of leaf meshes via the unreal_instance parameter. Due to the scale of these trees, the leaf instances are essentially entire trees themselves.

This prototype functions well, but unfortunately Houdini Engine is prone to crashing and I haven’t found a robust solution. The industry standard is to implement tools directly in-engine. So, how to achieve the same results in Unreal?

PCG Implementation

Creating a Graph Structure

Unreal’s Procedural Content Generation, known as PCG, is a nascent and rapidly developing framework for processing points and meta-data. It is general purpose, works in-editor and at runtime (with limitations) and has started to expand its functionality to mesh editing with Geometry Script interop.

While Epic is starting to add pathfinding features, PCG still lacks the ability to create and operate on connectivity data – e.g. graphs. However, Nebukam has created PCGex, an extended toolkit which focuses on edge-based structures.

To create the hierarchy, I am using PCGEx’s pathfinding utilities. As in the prototype, first the trunk is identified by pathfinding between the lowest and highest nodes.
By removing those edges, we get new start points (Seeds in PCGEx) – identifiable by a reduction in neighbours.
To pick an end point (Goal in PCGEx) , I initially started with random selection – but this often increases the required iterations to fully traverse the graph. A more thorough approach could involve finding the path with the most branches. For a simple and less computationally expensive solution, I am using the end point which is furthest away from the start point. For a standard tree structure, this yields good results. If I come across use-cases where the correct end point is not the furthest away, I will add pathfinding modes (e.g. Furthest Away, Longest Path, Most Branches).

Geometry Script Sweeps In

When the PCG graph outputs the paths, they are passed to a Geometry Script function to be swept into a mesh. The workflow is to prepare a list of transforms from the PCG Point data, sweep the branch and append it to the dynamic mesh. The process is separated into hierarchy layers by tags. The branch layers can optionally boolean against the previous layer & blend the normals.

Fixing the Twist

A common issue with generating geometry along paths in 3D is the roll component of rotation flipping because of crossing an axis boundary (similar to gimbal locking).
The remedy for this is to use a reference frame – updated at each step of the path, rotating it with the difference between tangents. This gives a consistent normal vector to use to with the path tangent to construct a rotation.

Sprouting Leaves

There are various strategies for branch and leaf geometry. My initial implementation is simple: randomly select points on branches of a certain hierarchy depth, constrain the selection by branch radius and project the chosen point to the branch mesh surface (with a bounding volume hierarchy). Then, a random rotation is selected within a cone. The shape of the cone can be adjusted per-axis, random roll is an option and there is a simple overlap check to prevent ugly intersections.
Currently normals are derived from the branch mesh surface hit but I intend to add an option for generating a blob-mesh to bake normals from.
The leaves can be added directly to the visual mesh (collision is a separate mesh asset) or instanced. In cases with very dense canopies, it could be more performant to instance – with very large structures, a HLOD may be in order.

An alternative method is to start with a blob-mesh and add leaf cards to break the silhouette, described on Simon Schreibt’s blog.

Collision

This is very project & context specific, but my default approach is to create a separate collision mesh asset which holds the trunk and branches. I’ve tried using Unreal’s custom static mesh collision feature with inconsistent results, so using a separate asset & component is not ideal but does function and allows for easy editing of the collision.

Unresolved Issues

I have some minor bugs to clear up:

Branches of one-node length are culled
Nodes overlapping edges cause unwanted culling & artifacts
UV scaling is inconsistent

Creating Visualisers in C++

Here’s a high level overview of the process of visualizing and edit component data with a transform gizmo. I’ve added a few code snippets of my implementation but I’d recommend reading the engine’s source code for Primitive Components such as Splines (SplineComponent & SplineComponentVisualizer) and the base class ComponentVisualizer.

Setup

Create a class which inherits from FComponentVisualizer to manage rendering and input.
Define structs inheriting from HComponentVisProxy for each interactive element. E.g. Points, Tangents and Segments in a Spline
Register this visualiser with GUnrealEd in the module startup function.

Rendering Primitives

Override the DrawVisualization function to render the component data using the Primitive Drawing Interface. This is also where HitProxies are created with a reference to the ActorComponent and any additional data we need to handle user input on the visualisation (Commonly, an index for tracking which component is being clicked on)

C++

void FGraph3DVisualizer::DrawVisualization(const UActorComponent* Component, const FSceneView* View, FPrimitiveDrawInterface* PDI)
{
	const UGraph3DComponent* Graph = Cast<const UGraph3DComponent>(Component);
	if (!Graph) return;
	
	TArray<int32> SortedEdges;
	TArray<float> Distances;
	for(int32 i = 0; i < Graph->Edges.Num(); i++)
	{
		const FVector Start = Graph->Nodes[Graph->Edges[i].Start].Position + Graph->GetComponentLocation();
		const FVector End = Graph->Nodes[Graph->Edges[i].End].Position + Graph->GetComponentLocation();
		const FVector MidPoint = Start + ((Start - End)/2);
		const float Distance = FVector::Distance(MidPoint, View->ViewLocation);
		bool bAdded = false;
		for (int32 sortIndex = 0; sortIndex < SortedEdges.Num(); sortIndex++){
			if (Distances[sortIndex] < Distance) continue;
			SortedEdges.Insert(i, sortIndex);
			Distances.Insert(Distance, sortIndex);
			bAdded = true;
			break;
		}
		if (!bAdded)
		{
			SortedEdges.Emplace(i);
			Distances.Emplace(Distance);
		}
	}
	
	FGraph3DDisplayOptions DisplayOptions = Graph->DisplayOptions;
	
	//draw edges
	for(int32 i = 0; i < Graph->Edges.Num(); i++)
	{
		const int index = SortedEdges[i];
		PDI->SetHitProxy(NULL);
		PDI->SetHitProxy(new HGraph3DEdgeVisProxy(Component, index));
		const FVector Start = Graph->Nodes[Graph->Edges[index].Start].Position + Graph->GetComponentLocation();
		const FVector End = Graph->Nodes[Graph->Edges[index].End].Position + Graph->GetComponentLocation();
		FVector Direction = End - Start;
		const FVector Normal = Direction.GetUnsafeNormal();
		
		FLinearColor Color = FLinearColor::White;
		switch (Graph->DisplayOptions.EdgeColorMode)
		{
		case EGraph3DEdgeColorMode::Solid:
			Color = DisplayOptions.EdgeColor;
			break;
		case EGraph3DEdgeColorMode::Random:
			Color = FColor::MakeRandomSeededColor(index);
			break;
		case EGraph3DEdgeColorMode::Direction:
			Color = FColor(Normal.X * 255, Normal.Y * 255, Normal.Z * 255);
			break;
		default: ;
		}

		const float Offset = Graph->DisplayOptions.NodeScale;
		float Length = Direction.Length() - (Offset);
		float Width = Graph->DisplayOptions.EdgeWidth;
		float Thickness = Graph->DisplayOptions.EdgeThickness;
		if (SelectionState->SelectedEdges.Contains(index)) Thickness *= 2;
		FMatrix Matrix = FScaleRotationTranslationMatrix(FVector::One(), Direction.Rotation(), Start + (Normal * (Offset/2)));
		
		DrawDirectionalArrow(PDI, Matrix, Color, Length, Width, SDPG_Foreground, Thickness);
		PDI->SetHitProxy(NULL);

	}

	//draw nodes
	for (int32 i = 0; i < Graph->Nodes.Num(); i++)
	{
		PDI->SetHitProxy(NULL);
		PDI->SetHitProxy(new HGraph3DNodeVisProxy(Component, i));
		FVector Position = Graph->Nodes[i].Position + Graph->GetComponentLocation();
		float Scale = Graph->DisplayOptions.NodeScale;
		FColor Color = FColor::White;
		if (SelectionState->SelectedNodes.Contains(i))
		{
			Scale *= 1.5;
			Color = FColor::Yellow;
		}
		DrawWireSphere(PDI, Position, Color, Scale/2, 12, SDPG_Foreground, DisplayOptions.NodeThickness);
		if (Graph->RootNode == i) DrawWireSphere(PDI, Position, FColor::Orange, Scale, 12, SDPG_Foreground, 1.5);
		PDI->SetHitProxy(NULL);
	}

}

Make sure to depth-sort the rendered elements, the Primitive Drawing Interface won’t do it for you!

A visual reference for PDI drawing functions: Component Visualizers | Unrealist.org

Editing with the Transform Gizmo

Override VisProxyHandleClick and use the stored data to manage selection state. By using multiple hit proxy classes and attempting casts you can differentiate between interactive elements. Also store a reference to the actor component referenced by the HitProxy by using an FComponentPropertyPath.
Override GetWidgetLocation to place the transform gizmo using selection state.
Override GetEditedComponent to reset the active visualizer after undo/redo.
Override HandleInputDelta to apply transform gizmo inputs to component elements.

C++

bool FGraph3DVisualizer::HandleInputDelta(FEditorViewportClient* ViewportClient, FViewport* Viewport, FVector& DeltaTranslate, FRotator& DeltaRotate, FVector& DeltaScale)
{
	if (DeltaTranslate.IsZero() && DeltaRotate.IsZero() && DeltaScale.IsZero()) return false;
	UGraph3DComponent* Graph = GetEditedGraphComponent();
	if (!Graph) return false;
	
	ValidateNodeSelection();

	FVector Origin = GetMedianSelectedNodePosition();
	TArray<int32> Nodes = SelectionState->SelectedNodes;
	FModifierKeysState Modifiers = FSlateApplication::Get().GetModifierKeys();
	
	switch (SelectionState->SelectionType) {
	
	case EGraph3DSelectionType::None:
		return false;
		
	case EGraph3DSelectionType::Node:
		//Transform child nodes
		if (Nodes.Num() == 1 && DeltaTranslate.IsZero() || Modifiers.IsShiftDown())
		{
			Origin = Graph->Nodes[Nodes[0]].Position;
			Nodes = Graph->GetNodeChildren(SelectionState->SelectedNodes[0]);
		}
		break;
		
	case EGraph3DSelectionType::Edge:
		for (const int32 SelectedIndex: SelectionState->SelectedEdges)
		{
			Nodes.AddUnique(Graph->Edges[SelectedIndex].Start);
			Nodes.AddUnique(Graph->Edges[SelectedIndex].End);
		}
		Origin = GetMedianSelectedEdgePosition();
		break;
	}
	
	for (const int32 SelectedIndex: Nodes)
	{
		FVector Pos = Graph->Nodes[SelectedIndex].Position;
		Pos += DeltaTranslate;
		
		if (!DeltaRotate.IsZero())
		{
			FRotationAboutPointMatrix RotationMatrix = FRotationAboutPointMatrix(DeltaRotate, Origin);
			Pos = RotationMatrix.TransformPosition(Pos);
		}

		if (!DeltaScale.IsZero())
		{
			FScaleMatrix ScaleMatrix = FScaleMatrix(DeltaScale);
			Pos -= Origin;
			Pos += ScaleMatrix.TransformPosition(Pos);
			Pos += Origin;
		}
		
		Graph->Nodes[SelectedIndex].Position = Pos;
	}
	
	NotifyPropertyModified(Graph, Graph3DNodesProperty, EPropertyChangeType::ValueSet);
	
	GEditor->RedrawLevelEditingViewports(true);
	return true;
}

Call GEditor->RedrawLevelEditingViewports(true) after modifying component data. This invalidates the HitProxies, preventing null pointer crashes from garbage collection.

Extra functionality

Hotkeys & Right-click Context Menu

Build a command menu for quick contextual actions & map those actions to hotkeys for a streamlined workflow.

Selection Variants

Selection Focus

By default, pressing F in the editor viewport will focus on the bounds of the selected Actor. To focus on the elements selected in the component visualiser, override HasFocusOnSelectionBoundingBox and construct a bounding box by adding element positions plus some padding.

C++

bool FGraph3DVisualizer::HasFocusOnSelectionBoundingBox(FBox& OutBoundingBox)
{
	UGraph3DComponent* Graph = GetEditedGraphComponent();
	if (!Graph) return false;
	check(SelectionState);
	
	OutBoundingBox.Init();
	
	switch (SelectionState->SelectionType)
	{
	case EGraph3DSelectionType::None:
		break;
	case EGraph3DSelectionType::Node:
		for (const int32 i : SelectionState->SelectedNodes)
		{
			const FVector Pos = Graph->Nodes[i].Position + Graph->GetOwner()->GetActorLocation();
			OutBoundingBox += Pos;
		}
		break;
	case EGraph3DSelectionType::Edge:
		for (const int32 i : SelectionState->SelectedEdges)
		{
			const FVector Pos1 = Graph->Nodes[Graph->Edges[i].Start].Position + Graph->GetOwner()->GetActorLocation();
			const FVector Pos2 = Graph->Nodes[Graph->Edges[i].End].Position + Graph->GetOwner()->GetActorLocation();
			OutBoundingBox += Pos1;
			OutBoundingBox += Pos2;
		}
		break;
	}

	OutBoundingBox = OutBoundingBox.ExpandBy(25.f);
	return true;
}

Display Options

Adding a struct to the component class for all visualisation settings keeps things clean. This is used in the Primitive Component for debug drawing via a Scene Proxy (this functions in-editor and in-game), and in the Component Visualizer.

C++

USTRUCT(BlueprintType)
struct FGraph3DDisplayOptions
{
	GENERATED_BODY()

public:
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = GraphDisplay)
	float NodeScale;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = GraphDisplay)
	float NodeThickness;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = GraphDisplay)
	float EdgeWidth;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = GraphDisplay)
	float EdgeThickness;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = GraphDisplay)
	EGraph3DEdgeColorMode EdgeColorMode;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = GraphDisplay)
	FColor EdgeColor;
};

What’s Next?

I will keep developing this tool both for level design & asset generation, as use-cases emerge in my projects. It would be cool to add lots of detailed plant-generation features, but at this stage the tool serves its purpose and it may simply be faster to do more manual refinement on the results, further in the development process when levels are locked down.

My overall take-away: PCG & Geometry Script are incredibly powerful and stable!

Resources