## Preface

I am working on a new 3D racing game.

For this racing game I need a track with mounds, hills and ramps.

I am going to cover my progress in making this racing game’s physics simulation.

## The Models

At this point the track is made of a series of 3D triangles.

The 3D triangles might be constructed in a way that they form a road with mounds, turns or slopes but they don’t have to.

At this point the track geometry is used for both rendering and representing the terrain geometry in the simulation.

The track dimensions I used for testing are 110×110 square meters.

We also have the truck which has a 3D model representing it visually.

Inside the simulation the truck is made out of 5 points. The center bottom of the truck and 4 more points representing the wheels.

The truck’s size is a 2x2x5 cubic meters box.

The wheels base is 1.8×4.4 square meters.

## Steering

For the steering of the truck I am saving the truck’s absolute direction inside a single angle.

I calculate the Look vector from the angle like this:

Look = Graphics2D::Position(sin(CarAngle), 0, cos(CarAngle));

When I want the truck to rotate I add an angular speed multiplied by the frame’s time to the angle I mentioned above.

I then recalculate the Look vector every new frame.

In order for the truck to move forward we need to add the movement vector to the truck’s current position.

The truck’s movement vector is calculated like this:

Move = Look*CurrentFlatSpeed*t; Pos = Pos+Move;

We don’t want the truck’s speed to accelerate instantaneously so we add the maximum speed multiplied by the frame’s time step but divided by the latency we want it to take to reach maximum speed.

if (Input.GetThrust()) CurrentFlatSpeed += MaxFlatSpeed*t/AccelLatency; CurrentFlatSpeed = std::max(std::min(CurrentFlatSpeed, MaxFlatSpeed), 0.0);

## Terrain checks

At this point we can drive and steer the truck but we are completely ignoring the track(or terrain).

In order for the truck to “glide” on the terrain we will go over every triangle in our track mesh and test to see if the (x, z) part of the center bottom of the truck is inside the projection of the triangle on the xz plane.

(The center bottom of the truck is actually it’s position).

In order to test that we use a ray to triangle intersection test while the ray is from (truck position X, 1000, truck position Z) to (truck position X, 0, truck position Z).

If the ray intersects the triangle then the truck’s center is inside the projection of the triangle. We can then extract the height of the intersection between the ray and the triangle and use that as the new height(y axis value) of our truck.

(For the ray/triangle intersection we use MathGeoLib by clb).

This will make our truck go over the track’s topology but the truck will remain aligned as if it was on a flat surface.

In order to recalculate the truck’s alignment we do the same test we did with the truck’s center but with the 4 wheels instead.

Before we do that we calculate the absolute position of the 4 truck wheels from the truck’s wheels base rotated by the truck’s steering angle and added to the truck’s center bottom. Like so:

Look = Graphics2D::Position(sin(CarAngle), 0, cos(CarAngle)); Right = Graphics2D::Position(0, 1, 0).Cross(Look); for (unsigned int i=0; i<4; i++) WheelPos[i] = Right*WheelBase[i].x+Look*WheelBase[i].z+Pos;

We now do the same calculation over all the triangles and calculate the new height for each of the 4 wheels.

We then calculate the new Look and Right vectors of the truck from two vectors.

The Look vector will be the vector pointing from the rear left wheel to the front left wheel and the Right vector will be the vector pointing from the front left wheel to the front right wheel.

Don’t forget we want the normalized vectors.

Look = (WheelPos[0]-WheelPos[3]).Normalize(); Right = (WheelPos[1]-WheelPos[0]).Normalize();

That’s it. This will give us the following simulation result.

## Optimizations

You probably noticed that we went through all the triangles in the track for each of the 5 points in the truck model.

This might be problematic to the performance and most of the triangles won’t intersect with the truck model.

In order to optimize this we prepare a 2D array where each array cell contains a linked list.

The 2D array represents a grid on the xz plane. The grid divides the plane into squares.

Each cell of the 2D array contains a list of all the triangles that their xz plane Axis Aligned Bounding Square intersects with the square in the grid that the cell represents.

This way every square in the grid will have a list that will contain all the triangles that intersect with the square(and maybe a little bit more that don’t).

So every time we want to test a point in the truck model against the track’s triangles we only need to test it against the triangles in the list of the square the point is at.

For the sake of completion here is the code to calculate a 10 by 10 triangle test optimization grid:

std::vector<math::Triangle> TrackGeometry; std::vector<std::vector<std::list<unsigned int> > > TrackGrid; std::vector<Graphics2D::Position> & Positions = TrackMesh->GetPosition(0); std::vector<unsigned int> & Indices = TrackMesh->GetIndex(0); TrackGrid.resize(10); for (unsigned int i=0; i<TrackGrid.size(); i++) TrackGrid[i].resize(10); TrackGeometry.resize (Indices.size()/3); Min = Positions[0]; Max = Positions[0]; for (unsigned int i=0; i<Positions.size(); i++) { Min.x = std::min(Min.x, Positions[i].x); Min.y = std::min(Min.y, Positions[i].y); Min.z = std::min(Min.z, Positions[i].z); Max.x = std::max(Max.x, Positions[i].x); Max.y = std::max(Max.y, Positions[i].y); Max.z = std::max(Max.z, Positions[i].z); } for (unsigned int i=0; i<TrackGeometry.size(); i++) { Graphics2D::Position LocalMin, LocalMax; LocalMin = Positions[Indices[i*3]]; LocalMax = Positions[Indices[i*3]]; for (unsigned int k=1; k<3; k++) { LocalMin.x = std::min(LocalMin.x, Positions[Indices[i*3+k]].x); LocalMin.z = std::min(LocalMin.z, Positions[Indices[i*3+k]].z); LocalMax.x = std::max(LocalMax.x, Positions[Indices[i*3+k]].x); LocalMax.z = std::max(LocalMax.z, Positions[Indices[i*3+k]].z); } TrackGeometry[i].a = float3(Positions[Indices[i*3]].x, Positions[Indices[i*3]].y, Positions[Indices[i*3]].z); TrackGeometry[i].b = float3(Positions[Indices[i*3+1]].x, Positions[Indices[i*3+1]].y, Positions[Indices[i*3+1]].z); TrackGeometry[i].c = float3(Positions[Indices[i*3+2]].x, Positions[Indices[i*3+2]].y, Positions[Indices[i*3+2]].z); unsigned int StartX = std::min((unsigned int)(std::max((LocalMin.x-Min.x)/(Max.x-Min.x), 0.0)), TrackGrid[0].size()-1); unsigned int StartZ = std::min((unsigned int)(std::max((LocalMin.z-Min.z)/(Max.z-Min.z), 0.0)), TrackGrid.size()-1); unsigned int EndX = std::min((unsigned int)(std::max((LocalMax.x-Min.x)/(Max.x-Min.x), 0.0)), TrackGrid[0].size()-1); unsigned int EndZ = std::min((unsigned int)(std::max((LocalMax.z-Min.z)/(Max.z-Min.z), 0.0)), TrackGrid.size()-1); for (unsigned int z1=StartZ; z1<=EndZ; z1++) for (unsigned int x1=StartX; x1<=EndX; x1++) TrackGrid[z1][x1].push_front(i); } WheelsDelta.resize(4); WheelsDelta[0] = Graphics2D::Position(-0.9, 0, 2.2); WheelsDelta[1] = Graphics2D::Position(0.9, 0, 2.2); WheelsDelta[2] = Graphics2D::Position(0.9, 0, -2.2); WheelsDelta[3] = Graphics2D::Position(-0.9, 0, -2.2);

## What’s next?

Our current simulation doesn’t have much of a physics feel to it.

The car is basically glued to the terrain. We also don’t deal with ledges.

In part 2 the simulation will get more interesting.

Pingback: Racing Game Custom Physics Simulation (Part 2) | PompiDev