⚙️ Tech Breakdown: Collision Sliding

Cute Illustration

I’ve begun consolidating my various demos and prototypes into a single Unreal Engine project.

A big feature to resolve with this port is how collision is handled. Let’s discuss collision handling in general, and how to start implementing it in Unreal in particular. This will be a code-heavy post (C++).

Unreal Engine Screencap

The gang is looking pretty Unreal.

In my Unity-based Character-Control demo I handled all collision using the Rigidbody component. This has the advantage of being quick & easy for early prototyping, because all the collision-handling and interactions with other moving-objects mostly “just works.”

Physical Character Control

It’s not physics if you don’t have boxes bouncing around.

The drawback is that rigidbody collision responses are generic. Unless you’re making a physics-sandbox game, it’s hard to dial-in tight controls. So for the port I want to start writing my own collision handling.

The full implementation of a colliding character controller is beyond the scope for one blog post, but we can at least start with a simple foundation: sliding.

Slide Figure

We sweep forward to an impact, and decompose the remainder into the “tangent” which lies along the surface.

To implement this in Unreal, I started by declaring a helper object. This technique keeps code modular while still portable to different parts of the game (we can embed them in Actors, Components, Anim Nodes, Blueprint Library Functions, etc), as well as being easy to copy-paste between projects without bringing a lot of other cruft with them.

class FSlide
{
public:

	// out start position
	FVector Position = FVector( 0.0f );

	// the desired offset vector
	FVector Remainder = FVector( 0.0f );

	// the shape to slide
	FCollisionShape Shape = FCollisionShape::MakeSphere( 20.0f );

	// the rotation of the shape
	FQuat Rotation = FQuat::Identity;

	// parameters used by unreal's collision-query system
	FCollisionQueryParams QueryParams = FCollisionQueryParams::DefaultQueryParam;
	ECollisionChannel Channel = ECC_Pawn;

	// Advance Position/Remainder to the next impact
	bool TryStep( const UWorld* World, FHitResult& Hit );

private:

	// Will be relevant later ;)
	FVector PrevNormal = FVector( 0.0f );
};

Before diving into the details of this function, let’s write a quick little test actor. I’ve omitted a complete code-listing for brevity, but everything happens in Tick():

/*virtual*/ void ATestSlidePawn::Tick( float DeltaTime ) /*override*/
{
	Super::Tick( DeltaTime );

	// Only update when player has control
	if( !Controller )
	{
		return;
	}

	UWorld* World = GetWorld();

	// gamepad stick inputs
	const FVector2D CamInput ( GetInputAxisValue( NAME_CamX ), GetInputAxisValue( NAME_CamY ) );
	const FVector2D MoveInput ( GetInputAxisValue( NAME_MoveX), GetInputAxisValue( NAME_MoveY ) );

	// use the right-stick to rotate the camera
	FRotator ControlEuler = Controller->GetControlRotation();
	ControlEuler.Yaw += CamInput.X * 120.0f * DeltaTime;
	ControlEuler.Yaw = FRotator::NormalizeAxis( ControlEuler.Yaw );
	ControlEuler.Pitch -= CamInput.Y * 100.0f * DeltaTime;
	ControlEuler.Pitch = FMath::Clamp( ControlEuler.Pitch, -70.0f, 70.0f );
	Controller->SetControlRotation( ControlEuler );

	// compute a desired velocity by mapping the left stick relative to the camera
	const FQuat CamRot = ControlEuler.Quaternion();
	const FVector Vel = CamRot *  FVector( 500.0f * MoveInput.Y, 500.0f * MoveInput.X, 0 );

	// perform the slide
	FSlide Slide;
	Slide.Position = GetActorLocation();
	Slide.Remainder = Vel * DeltaTime;
	Slide.QueryParams = FCollisionQueryParams( NAME_Test, false, this );

	// cap out at three impacts
	FHitResult Hit;
	for( int It = 0; It < 3 && Slide.TryStep( World, Hit ); ++It )
	{
		if( Hit.bStartPenetrating )
		{
			// Stuck! Draw a red warning sphere
			DrawDebugSphere( World, Slide.Position, Slide.Shape.GetSphereRadius() + 5.0f, 16, FColor::Red );
			break;
		}
		else
		{
			// Impact! Draw the surface normal
			DrawDebugDirectionalArrow( World, Hit.ImpactPoint, Hit.ImpactPoint + 65.0f * Hit.Normal, 10.0f, FColor::Green, false, 0.5f );
		}
	}

	// update the actor and camera positions
	SetActorLocation( Slide.Position );
	CameraComp->SetWorldLocationAndRotation( Slide.Position - CamRot * FVector( 300, 0, 0 ), CamRot );
}

Here’s a naive first-stab at the FSlide::TryStep() function:

bool FSlide::TryStep( const UWorld* World, FHitResult& Hit )
{
	// early out?
	if( Remainder.IsNearlyZero( KINDA_SMALL_NUMBER ) )
	{
		return false;
	}

	// sweep forward
	const bool bHit = World->SweepSingleByChannel( Hit, Position, Position + Remainder, Rotation, Channel, Shape, QueryParams );
	if( !bHit )
	{
		Position = Hit.TraceEnd;
		Remainder = FVector( 0.f );
		return false;
	}

	// stuck?
	if( Hit.bStartPenetrating )
	{
		Remainder = FVector( 0.0f );
		return true;
	}

	// update position and remainder
	Position = Hit.Location;
	Remainder *= ( 1.f - Hit.Time );
	Remainder = FVector::VectorPlaneProject( Remainder, Hit.Normal );

	return true;
}

Seems to do everything in the picture: we use Unreals’ SweepSingleByChannel method to cast for an impact in the scene, and then either fully or partially advance based on whether we get a hit. Let’s take it for a spin:

First Test

Derp.

As soon we we touch collision, we get stuck. Wat?

The problem is precision. Positions in Unreal Engine 4 are represented using single-precision floating-point numbers, which on a good-day only get you about 6-8 digits (or “significant figures”). Because of these tiny errors, if we get too-close to a surface we actually start overlapping it a little bit, which causes SweepSingleByChannel to report the bStartPenetrating condition.

Unreal Engine 5 eases this situation somewhat by using double-precision floats, but the issue persists.

Let’s try “pulling back” slightly from surfaces when updating position when we advance to create a gap for the error.

FVector PullBackMove( const FVector& Move )
{
	// magic number I found elsewhere in the Unreal Engine source code
	const float Epsilon = 0.125f; 
	const float Dist = Move.Size();
	return Dist > Epsilon ? Move * ( ( Dist - Epsilon ) / Dist ) : FVector( 0.0f );
}

Then we change how the position is updated.

// new position update
//Position = Hit.Location;
Position = Hit.TraceStart + PullBackMove( Hit.Location - Hit.TraceStart );

This actually does a pretty good job. We’re not getting stuck on simple surfaces, but we can still get stuck rubbing against complex mesh-geo collision.

Second Test

Better.

The issue is that the pull-back doesn’t work at glancing angles. And there’s also a broader issue: sometimes you can’t avoid little overlaps, e.g. if you have moving world geometry that encroaches on your shape independently of precision. What we really need is to detect and depenetrate from initial overlaps before sweeping.

The FHitResult contains minimum-separating-vector information in its Normal and PenetrationDepth fields when it raises the bStartPenetrating condition, but it’s actually kind of useless because it only reports a single result, whereas shapes can logically have multiple initial overlaps – especially in narrow corners.

Depenetration Figure

A pathological, but not uncommon, case – there are multiple initial overlaps, and their separation-vectors all oppose each other.

Unreal provides the SweepMulti variant specifically to gather infomation to solve this case.

When bStartPenetrating is raised, the results-array contains all the initial overlaps.
When the sweep succeeds it finds exactly-zero-or-one blocking impact (at the end of the results), but also reports all the other overlaps along the path, which can be used to detect trigger-volumes with the same queries used for collision-responses.

To use this, first we’ll want a helper function to “inflate” a shape, because when we depenetrate we want to use a shape with a thin “skin” which will leave an airgap for the resweep.

FCollisionShape InflateShape( const FCollisionShape& Shape, float Amount )
{
	// helper function to add a "skin" to a shape
	switch( Shape.ShapeType )
	{
	case ECollisionShape::Capsule: 
		return FCollisionShape::MakeCapsule( Shape.GetCapsuleRadius() + Amount, Shape.GetCapsuleHalfHeight() + Amount );
	case ECollisionShape::Sphere:  
		return FCollisionShape::MakeSphere( Shape.GetSphereRadius() + Amount );
	case ECollisionShape::Box:     
		return FCollisionShape::MakeBox( Shape.GetBox() + Amount );
	default: 
		return Shape;
	}
}

With that in hand, here’s a wrapper for SweepMultiByChannel which detects initial penetration, wiggles us free, and then resweeps if needed.

bool DepenAndSweep( const UWorld* World, FHitResult& Hit, const FVector& Start, const FVector& Delta, const FQuat& Rot, ECollisionChannel Channel, const FCollisionShape& Shape, const FCollisionQueryParams& Params )
{
	// "Scratchpad" for result list, to avoid reallocating results for each sweep
	// (NOTE: makes this function not threadsafe!)
	static TArray< FHitResult > Hits;
	Hits.Reset();

	// sweep with inflated skin
	FCollisionShape Inflated = InflateShape( Shape, 0.25f );
	const bool bSkinHit = World->SweepMultiByChannel( Hits, Start, Start + Delta, Rot, Channel, Inflated, Params );

	// no hits, even with skin?
	if( !bSkinHit )
	{
		Hit.Init();
		Hit.TraceStart = Start;
		Hit.TraceEnd = Start + Delta;
		Hit.Location = Start + Delta;
		Hit.Time = 1.0f;
		return false;
	}

	// have initial overlaps?
	int NumInitialOverlaps = 0;
	for( const FHitResult& It : Hits )
	{
		if( It.bStartPenetrating )
		{
			++NumInitialOverlaps;
		}
	}
	if( NumInitialOverlaps == 0 )
	{
		Hit = Hits.Last();
		return bSkinHit;
	}
	
	// iteratively resolve penetration
	FVector Fixup( 0.0f );
	for( int Iter = 0; Iter < 16; ++Iter )
	{
		float ErrorSum = 0.0f;
		for( const FHitResult& It : Hits )
		{
			if( It.bStartPenetrating )
			{
				// take the dot-product of the Fixup and the Normal to determine how much
				// of the penetration has already been taken care of.
				const float Error = FMath::Max( 0.0f, ( It.PenetrationDepth + 0.125f ) - ( Fixup | It.Normal ) );
				ErrorSum += Error;
				Fixup += Error * It.Normal;
			}
		}
		// If we've found a solution, stop iterating.
		if( ErrorSum < KINDA_SMALL_NUMBER )
		{
			break;
		}
	}

	// resweep from new start
	return World->SweepSingleByChannel( Hit, Start + Fixup, Start + Fixup + Delta, Rot, Channel, Shape, Params );
}

We use numeric iteration to resolve the fixup because there’s no cheap analytical solution. Having nested inner-loops like this might smell like bad perf, but the calculations are so cheap that a modern CPU won’t even break a sweat.

UPDATE: @ctangora assures me that this resolver is actually equivalent to a Gauss-Seidel Method, and she’s much smarter than me, so I trust her. ❤️

Footage with Depenetration

Success!

It’s technically still possible to get stuck, even with this method, but it’s highly unlikely and content-dependent, so those bugs can be fixed on a case-by-case basis. On Solar Ash, e.g., we’d see Rei get stuck about once every two hours or so during QA, so we just added a little white-noise to stuck positions and they’d pop-out within a few frames.

Between the articulated moving platforms, detailed mesh collision, and changing gravity you can imagine how wild the collision issues were.

And that’s about it for sliding. Note that this code is not meant to be used verbatim, but as a starting point. As your controls are developed, you’ll add different responses to different surface-types and movement-modes. E.g. a grounded character will treat the floor, walls, and ceilings differently.

One last cool trick before I wrap this up. As implemented so far, you’ll see some jitter when you try and slide between surfaces that meet at an acute angle. The solution is to recognize that in this case we actually want to slide along the seam in between them. Our helper stores the PrevNormal each step to compute this. Here’s a full listing along with the subtituted call to DepenAndSweep:

bool FSlide::TryStep( const UWorld* World, FHitResult& Hit )
{
	// early out?
	if( Remainder.IsNearlyZero( KINDA_SMALL_NUMBER ) )
	{
		return false;
	}

	// sweep forward
	const bool bHit = DepenAndSweep( World, Hit, Position, Remainder, Rotation, Channel, Shape, QueryParams );
	if( !bHit )
	{
		Position = Hit.TraceEnd;
		Remainder = FVector( 0.f );
		return false;
	}

	// stuck?
	if( Hit.bStartPenetrating )
	{
		return true;
	}

	// update position
	Position = Hit.TraceStart + PullBackMove( Hit.Location - Hit.TraceStart );

	// remainder is either projected onto the impact plane, or the seam between two acute impact-planes
	// dot-product to check the angle
	// cross product to calcuate the seam
	const FVector Seam = ( PrevNormal | Hit.Normal ) < KINDA_SMALL_NUMBER ? ( PrevNormal ^ Hit.Normal ) : FVector( 0.0f ) ;
	Remainder *= ( 1.f - Hit.Time );
	Remainder = Seam.IsNearlyZero( 0.1f ) ? 
		FVector::VectorPlaneProject( Remainder, Hit.Normal ) : 
		Remainder.ProjectOnTo( Seam ) ;
	PrevNormal = Hit.Normal;

	return true;
}

Until next time, happy sliding!

2023-02-13

https://blog.littlepolygon.com/posts/sliding/ Max Kaufmann

#tech