Dev Blog 1100 - New Year.............. I Hardley Knowear!!!

i know they ate a cheese

Of course, Bites is here.

I’ve barely been doing much level design over the past couple weeks, as I’ve been busy handling a lot of important big boy adult talking. But now, I’m back in action, and raring to go! Here’s a few levels you can expect to see in the earlier difficulties of the game. I’m tired, so you don’t get descriptions! Just look at the dang things.

level 1
level 2

Our character artist has finished rigging up Jolene the Armadillo, so you might find them in-game pretty soon!

level 2

In any case, here are some pretty awesome writeups from some of our other devs, CraftedCart and ComplexPlane.


Model/view separation

If you’ve done much GUI or web programming before, you may have come across the model-view, or model-view-controller pattern before. Simply put, this pattern separates logic into three distinct segments. The “model” houses the data, the “view” looks at the model and presents it to the user, and the “controller” lets the user do actions such as clicking buttons or entering text, and modifies the model.

Model-view-controller diagram

Thanks for the image WikiMedia/RegisFrey

So how does this apply to Rolled Out!? (and how do I use punctuation when the title Rolled Out! itself has punctuation in it? Rolled Out‽). Well we’re applying this pattern to the stage itself! We have a model, FStageData, which stores the state of the stage (like object transforms, meshes, and such), and we want to sync over this model to a view, such that the stage can be displayed in the world. Lua scripts and stage animations act like a controller in that they can modify the stage data.

How this pattern applies to the stage

What’s the point of splitting the model and the view though anyway? Well aside from keeping code organized, there’s another reason: what if you want to simulate a stage without seeing it? If physics ends up being deterministic across devices (which so far, physics determinism is looking pretty good right now), it’d be nice to be able to verify replays haven’t been fudged with for leaderboards, by replicating inputs and seeing if the end result is the same (does replaying a player’s inputs say that the they goal and get the same time/score as their leaderboard submission claims?). Being able to simulate stages/replays, without having to be tied down with chunks of Unreal’s framework that isn’t necessary for this (like needing to create a world, load maps, setup a game mode, setup a game state, only being able to access parts from the main thread, etc.) could hugely save on resources.


ComplexPlane: Faster Collision Physics

Hey again! Over the past month, I’ve been making a steady stream of improvements and tweaks to our new collision physics. As for some smaller things, I’ve worked with Bites to fix Morris’s character animation and the ball’s collision effects, but most of my work has gone towards improving the collision physics’ performance.

Spatial Acceleration Basics

If you recall, stages in Rolled Out are triangle meshes and we compute how the ball interacts with the stage by determining how it collides with the stage’s triangles. There’s something we need to contend with though: if our collision algorithm works by checking every triangle in the stage on each frame, our physics will slow down substantially as our stages grow in triangle count. Lucky for us, we can deal with this issue by using a spatial acceleration structure, which is a data structure that allows us to accurately detect ball-stage collisions without needing to check every individual triangle. An acceleration structure divides the stage into large regions, which are then divided into smaller regions, which are divided into even smaller regions, and so on. By intersecting the ball with these regions, we can eliminate the need to directly check most triangles in the stage in the first place. More on that in a bit.

Bounding Volume Hierarchies

Bounding Volume Hierarchy (BVH) Generated for Beginner 19

I ultimately decided to use a binary Bounding Volume Hierarchy (BVH) as the acceleration structure. A BVH divides the stage into two distinct sets of triangles, and creates an axis-aligned bounding box (AABB) around each of them. These two sets of triangles are generally chosen such that their bounding boxes are as large and non-overlapping as possible. This process repeats again for each new bounding box of triangles, until the lowest-level bounding boxes only contain a single triangle.

BVHs are an excellent acceleration structure for stage meshes because they are non-uniform; they can be generated to tightly encompass stages with many triangles concentrated in some regions of space, but not so many triangles in other regions of space. This is in contrast to other acceleration structures such as octrees or grid systems which are more uniform.

It requires some care to generate efficient, high-quality BVHs however, so it made sense to use some pre-existing code to do so. I chose to use NanoRT, a very small raytracing library, as it doesn’t provide much extra functionality outside of generating BVHs from triangle meshes and intersecting rays with them. In addition, NanoRT provides low-level access to its BVH data structure, which is necessary for us to implement our custom collision physics on top of it.

BVHs for Animated Stages

The BVH for a particular stage is generated just a single time prior to playing the stage; we don’t need to regenerate it on every frame. But what about if the stage has animations? Any BVH we would build for the entire stage would become invalid on each frame as the stage triangles themselves would change. We can’t just build a BVH each frame, because that’s no faster than testing each triangle individually without a BVH at all! The solution is easy, however: build a separate BVH for each animated object which moves alongside them.

So long as our stages don’t contain an excessive number of distinct animated objects, this still performs well.

BVH Traversal

To detect collisions without checking every triangle in a stage object mesh, we must traverse the mesh’s BVH. There are a couple ways to traverse the BVH depending on exactly what we’re doing, but for now, let’s say we want to figure out which triangles an arbitrary sphere is intersecting.

First, we check whether the sphere intersects either of the two top-level AABBs.
If the sphere does not intersect with an AABB, then we can completely disregard all triangles contained within this AABB. After all, if the sphere doesn’t intersect their bounding box, it certainly must not be touching any triangles contained within!
If the sphere does intersect the AABB, we repeat the process with all AABBs contained inside it. This repeats until we reach individual triangles, at which point a normal sphere-triangle intersection test may be performed.

Because we roughly eliminate half of all triangles on each iteration, we say that a BVH traversal algorithm like this runs in logarithmic time. This is much faster than checking each triangle individually, which takes linear time.

In the following sections, let’s take a closer look at how BVHs were used to implement collision physics in Rolled Out.

New CCD Method

First, we need to revisit Continuous Collision Detection (CCD). If you recall another blog post, CCD refers to detecting collisions even in situations where the ball could pass entirely through the stage in a single frame. In that post, I described a CCD method which involves projecting the ball’s center into stage triangles. This approach actually has some major issues, however. For one, it’s not particularly robust; using it, you can still teleport through stages in Rolled Out in somewhat reasonable circumstances. The larger problem, however, is that this CCD method requires testing each triangle individually, and cannot be rewritten in terms of an efficient BVH traversal as far as I am aware. In order to optimize Rolled Out’s collision physics, we must also account for CCD.

What if we instead, for a given frame, drew a line from the ball’s start position to the ball’s end position, and tested whether that line intersects the stage? Intersecting a line with a BVH to determine the triangles it intersects can be done in logarithmic time, and this is actually an extremely common operation in ray tracing code! However, this approach has a problem: while it accounts for the ball’s fast motion, it does not account for the stage’s motion:

Here, we see a case where the ball (circle) ought to have contacted the stage (square), but it didn’t. What we actually want is a way to account for the stage’s motion and the ball’s motion simultaneously. It shouldn’t matter whether you drive your car at 80mph into a brick wall or, uh, a brick wall drives 80mph into your parked car, they’re essentially the same and should behave the same.

Instead, we can trace the ball’s path relative to the stage. Here’s how it works: we take the ball’s start position, and remember where it is relative to the stage. As the stage moves, the ball’s start position moves with it. At the end of the frame, we record the ball’s end position relative to the stage, and draw a line between the relative start and end ball positions.

In this diagram, the only difference between the two sides is that the right side shows the collision from the perspective of the stage, while the left side shows it from the perspective of the world. Notice how the ball’s start position does not move at all in “local space”.

But how do we “move the ball with the stage”? Let’s talk about transforms. For our very informal purposes, a transform is a set of numbers which describes how to move a stage object to a new location and give it a new rotation. On each gameplay frame, we take each stage object’s default position+rotation and transform the stage object to where it should be in the game based on its animation. The transform itself is a local-to-world transform: it describes how to take every triangle relative to the stage object and place it in the world. We call the perspective relative to the stage object local space, and the perspective relative to the world world space.

The cool thing about transforms like these though is that we can go in reverse as well! We can take any object in world space and figure out where it lies in the stage object’s local space by applying the inverse of the stage object’s local-to-world transform (a world-to-local transformation). This is in fact precisely how we compute the ball’s start position relative to the moving stage.

1
2
3
4
5
6
7
8
9
10
11
for (auto Mesh : Meshes)
{
// Get the stage object's position and rotation in world space as a transform
// Determine it at the start of this frame, and at the end of this frame
FTransform LocalToWorldStartTransform = StageActor->GetMeshTransformAtTime(StartTime, Mesh);
FTransform LocalToWorldEndTransform = StageActor->GetMeshTransformAtTime(EndTime, Mesh);

// Transform the ball's start world space position into this stage object's local space
FVector LocalBallStartPos = LocalToWorldStartTransform.InverseTransformPosition(WorldBallStartPos);

// ...

Here in Unreal Engine code, FTransforms represents stage transforms and FVectors represent the ball’s position. We eventually determine the ball’s end position in local space as well.

Aside from improving the accuracy of CCD, transforming the ball’s position into local space is actually necessary in the first place to efficiently use the BVHs generated for stage objects. Stage object BVHs are only generated once in local space, and it would be very inefficient to somehow transform the entire BVH to world space as the stage object itself is animated; by transforming the ball’s position to local space instead, we can query the BVH as if it was in world space.

Using local space transforms and the BVH, we can perform continuous collision detection efficiently on arbitrarily large stages.

BVH Discrete and Continuous Triangle Candidate Fusion

There is another interesting problem we must contend with in order to adapt Rolled Out’s collision physics to use BVHs. In this blog post, we examined and justified an interesting collision physics property: stage triangles should be tested in a fixed ordering, and no two triangles should be tested more than once (during a single frame). This property is straightforward to maintain if you check each triangle in a row during each gameplay frame, which is essentially what the “new physics” did previously. However, checking each and every triangle is precisely what we are trying to avoid for performance! So, how do we maintain these properties while engaging the BVH?

First, we use the BVH to perform broad phase collision detection: we traverse the BVH’s AABBs to determine a set of candidate triangles which we may have collided with, excluding triangles that we definitely did not collide with. We need to do this twice: one for discrete collision, and once for continuous collision. To obtain the “discrete candidates”, we traverse the BVH by intersecting the ball sphere with the BVH’s AABBs (as an optimization, we actually intersect the ball’s AABB rather than the sphere itself). For the continuous candidates, we instead use the line formed between the ball’s start end end position in local space to intersect the BVH, as discussed in the previous CCD section.

1
2
TArray<uint32> DiscreteCands = PhysicsMesh.GetSphereIntersectCandidates(LocalBallEndPos, Radius);
TArray<uint32> ContinuousCands = PhysicsMesh.LineTrace(LocalBallStartPos, LocalBallEndPos);

Here, we’re identifying triangles by their uint32 ID number.

Next, we need to determine the “first” candidate triangle which intersected the ball. We could simply determine the triangle with the lowest ID, but if this triangle failed to actually collide with the ball (it’s just a candidate after all), we would need to determine the second-earliest triangle ID, and so on. The solution is to sort all candidate triangles into a new list. We sort the continuous and discrete candidates together in the same list, as we want to find the lowest-ID triangles among all candidates.

1
2
3
4
5
6
7
8
9
10
11
12
TArray<FaceColisCand> Cands;

for (uint32 Cand : DiscreteCands)
{
Cands.Add(FaceColisCand{static_cast<int>(Cand), false});
}
for (uint32 Cand : ContinuousCands)
{
Cands.Add(FaceColisCand{static_cast<int>(Cand), true});
}

Cands.Sort([](const FaceColisCand& Cand1, const FaceColisCand& Cand2) { return Cand1.Id < Cand2.Id; });

Next, we can iterate along the sorted Cands list until we find a triangle that the ball actually collides with. This is the narrow phase collision detection.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Narrow phase collision detection
for (auto& Cand : Cands)
{
const TArray<FTri>& Tris = PhysicsMesh.GetTris();
const FTri& Tri = Tris[Cand.Id];

FVector LocalEndPosProjOnLocalTri = FVector::PointPlaneProject(LocalBallEndPos, Tri.v0, Tri.v1, Tri.v2);
float EndPosTriDist = Tri.PointDistance(LocalBallEndPos);

// Check if candidate triangle actually represents a collision
if (Cand.bLineTraceCand) // Continuous collision candidate
{
// Cull back face intersections
if (EndPosTriDist > 0) continue;
}
else // Discrete collision candidate
{
if (EndPosTriDist <= 0 || EndPosTriDist >= Radius) continue;
if (!Tri.PointInTriangle(LocalEndPosProjOnLocalTri)) continue;
}

// Collision has been detected
LastCollidedTri = Cand.Id;

There’s one final thing we need to contend with, and that’s the fact that the ball can collide with more than one triangle in a single frame. The ball is moved to a new position each time a collision occurs, so that means that we must repeat both the broad and narrow collision phase for each collision. But, we must be very careful to not collide with the same triangle twice! To prevent this, we always ignore any triangle whose ID is less than or equal to the last collided triangle’s ID:

1
2
3
4
5
6
// Narrow phase collision detection
for (auto& Cand : Cands)
{
if (Cand.Id <= LastCollidedTri) continue;

// ...

Before any collisions occur, LastCollidedTri is -1.

As a final note, the collision algorithm described here is for “face collisions”; edge and vertex collisions work a bit differently.

Conclusion, and Stuff on the Docket

Using BVHs, our collision physics seems to run much faster, and never appears to noticably lag, even on huge stages! It’s really gratifying to see that things worked out like I hoped they would.

Up next, I would like to work on fixing special object collision (colliding with bumpers, mines, etc. doesn’t work at the moment), and I’d also like to research how we might further improve and fine-tune our rolling friction behavior.

See ya next time hopefully? I’m going back to school soon so I’ll have less time to work on the project, but hopefully I’ll still have something to share.


That concludes the first dev blog of the year. Unfortunately, we didn’t have an update to the beta prepared for today, but hopefully we will have one very soon. There’s a lot of really amazing stuff just on the precipice of completion - refactored stage structures, ball and character customization, tons of new stages, totally fixed physics, semi-functional multiplayer… it’ll be like, WHAM! POW! This is totally crazy! There’s like, seven updates in this update! …okay, maybe not seven.

I’m really hoping that Rolled Out! can be something you will look forward to in 2020, even as everything else in the world burns around us.

Thanks for reading! See you on February 1st.