Using A Spatial Partitioning Grid to Improve Performance.

For my new racing game I am using a surface made out of triangles on which the car drives.

In order to place the car on the track I need to find the triangle the car is above.

A simple way of finding this triangle is to test against every triangle in the track and find the one the car is directly above.

However, this is very wasteful CPU wise because most of the triangles are not even near the car.

In order to speed up the calculation I keep a 2D array or a grid that saves which triangles intersect with a grid cell for every cell in the grid.

This way I can test only against the triangles that are in the cell the car is also intersecting.

Notice that the same triangle might be indexed in more than one cell. It is indexed in every cell it intersects.

This guarantee that if I test a point against the triangles of a cell I won’t miss any triangle that intersects the cell.

There is a small issue when you test a line that span across several cells because then you might test against the same triangle more than once.

The solution is to return only one instance of each triangle index in the cells(by using an unordered set data structure for instance).

Here is a video of the game in which I use the grid to give context:

And here is the code of the class I use.

(Notice I also use MathGeoLib by clb but just for the triangles data structure and I also assume the grid is on the XZ plane)

 

Code on Gist.

#pragma once

#include "stdafx.h"
#include "resource.h"
#include "Graphics2D.h"
#include "Graphics3D.h"
#include "Geometry/Triangle.h"
#include "Math/float3.h"

namespace Logic {
	class SurfaceTriangleMap {
		public:
			SurfaceTriangleMap(Graphics3D::Mesh TrackMesh)
			{
				this->TrackMesh = TrackMesh;
				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((double)TrackGrid[0].size()*(LocalMin.x-Min.x)/(Max.x-Min.x), 0.0)), TrackGrid[0].size()-1);
					unsigned int StartZ = std::min((unsigned int)(std::max((double)TrackGrid.size()*(LocalMin.z-Min.z)/(Max.z-Min.z), 0.0)), TrackGrid.size()-1);
					unsigned int EndX = std::min((unsigned int)(std::max((double)TrackGrid[0].size()*(LocalMax.x-Min.x)/(Max.x-Min.x), 0.0)), TrackGrid[0].size()-1);
					unsigned int EndZ = std::min((unsigned int)(std::max((double)TrackGrid.size()*(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);
				}
			}

			math::Triangle & GetTriangle (unsigned int i)
			{
				return TrackGeometry[i];
			}

			unsigned int GetTrianglesAmount()
			{
				return TrackGeometry.size();
			}

			std::vector<unsigned int> GetPositionTriangles (Graphics2D::Position Pos)
			{
				unsigned int BaseX = std::min((unsigned int)(std::max((double)TrackGrid[0].size()*(Pos.x-Min.x)/(Max.x-Min.x), 0.0)), TrackGrid[0].size()-1);
				unsigned int BaseZ = std::min((unsigned int)(std::max((double)TrackGrid.size()*(Pos.z-Min.z)/(Max.z-Min.z), 0.0)), TrackGrid.size()-1);

				std::vector<unsigned int> IndexList;

				std::list<unsigned int>::iterator q;
				for (q = TrackGrid[BaseZ][BaseX].begin(); q != TrackGrid[BaseZ][BaseX].end(); q++)
				{
					IndexList.push_back(*q);
				}
				return IndexList;
			}

			std::vector<unsigned int> GetPositionRangeTriangles (Graphics2D::Position PosStart, Graphics2D::Position PosEnd)
			{
				unsigned int StartX = std::min((unsigned int)(std::max((double)TrackGrid[0].size()*(PosStart.x-Min.x)/(Max.x-Min.x), 0.0)), TrackGrid[0].size()-1);
				unsigned int StartZ = std::min((unsigned int)(std::max((double)TrackGrid.size()*(PosStart.z-Min.z)/(Max.z-Min.z), 0.0)), TrackGrid.size()-1);
				unsigned int EndX = std::min((unsigned int)(std::max((double)TrackGrid[0].size()*(PosEnd.x-Min.x)/(Max.x-Min.x), 0.0)), TrackGrid[0].size()-1);
				unsigned int EndZ = std::min((unsigned int)(std::max((double)TrackGrid.size()*(PosEnd.z-Min.z)/(Max.z-Min.z), 0.0)), TrackGrid.size()-1);

				if (EndX<StartX)
				{
					unsigned int KeepX = StartX;
					StartX = EndX;
					EndX = KeepX;
				}
				if (EndZ<StartZ)
				{
					unsigned int KeepZ = StartZ;
					StartZ = EndZ;
					EndZ = KeepZ;
				}

				std::vector<unsigned int> IndexList;

				for (unsigned int CountZ = StartZ; CountZ<=EndZ; CountZ++)
					for (unsigned int CountX = StartX; CountX<=EndX; CountX++)
					{
						std::list<unsigned int>::iterator q;
						for (q = TrackGrid[CountZ][CountX].begin(); q != TrackGrid[CountZ][CountX].end(); q++)
						{
							IndexList.push_back(*q);
						}
					}
				return IndexList;
			}
		private:
			std::vector<math::Triangle> TrackGeometry;
			std::vector<std::vector<std::list<unsigned int> > > TrackGrid;
			Graphics3D::Mesh TrackMesh;
			Graphics2D::Position Min, Max;
	};

}