   Speeding up Map Rendering
  I have thought about a way to speed up rendering my map.My map is made up of tiles which are represented by Rectangles.I am using D3D8 for an API and render these Rectangles as unlit and untransformed vertices in triangle lists.What I thought of to speed up is to divide the map into Regions which contain an Index Buffer to store the indices into the map VB and a Rectangle to detect if they are visible.To set up the index buffers I have to know how many tiles are contained within a region.How can this be done?I tried a triangle-point collision test making the tile a rect and checking it thus against the bounding rect of the region but this didn`t seem to work.So let me show you what I did, perhaps you can find out what`s wrong or what can be done better.First of all the required structures://A Map Region:struct MapRegion {int iContainedTiles[Map_Layers];int iTextureIndex;LPDIRECT3DINDEXBUFFER8 IndexBuffer[Map_Layers];RECT3D BoundingRect;};//A Rectstruct Rect3D {D3DVECTOR UpperLeft;D3DVECTOR UpperRight;D3DVECTOR LowerLeft;D3DVECTOR LowerRight;};  So I made a rect out of the tile (this code is a bit confusing because I have to watch out if the Map is a tile or an isometric map) bool CMap::TileInRect(DWORD dwMapX, DWORD dwMapY, LPRECT3D pRect) {RECT3D TileRect;if(MAP_TILE == m_Header.byMode) {TileRect.UpperLeft.x = dwMapX * m_Header.fGeometryWidth;TileRect.UpperLeft.y = dwMapY * -(m_Header.fGeometryHeight);TileRect.UpperLeft.z = m_Header.fZoom;TileRect.LowerLeft.x = dwMapX * m_Header.fGeometryWidth;TileRect.LowerLeft.y = dwMapY * -(m_Header.fGeometryHeight) - m_Header.fGeometryHeight;TileRect.LowerLeft.z = m_Header.fZoom;TileRect.UpperRight.x = dwMapX * m_Header.fGeometryWidth + m_Header.fGeometryWidth;TileRect.UpperRight.y = dwMapY * -(m_Header.fGeometryHeight);TileRect.UpperRight.z = m_Header.fZoom;TileRect.LowerRight.x = dwMapX * m_Header.fGeometryWidth + m_Header.fGeometryWidth;TileRect.LowerRight.y = dwMapY * -(m_Header.fGeometryHeight) - m_Header.fGeometryHeight;TileRect.LowerRight.z = m_Header.fZoom;}else {TileRect.LowerLeft.x = (m_Header.fGeometryWidth / 2.0f) * (dwMapX - dwMapY) - (m_Header.fGeometryWidth / 2.0f);TileRect.LowerLeft.y = (m_Header.fGeometryHeight / 2.0f) * (dwMapX + dwMapY) - m_Header.fGeometryHeight;TileRect.LowerLeft.z = m_Header.fZoom;TileRect.UpperLeft.x = (m_Header.fGeometryWidth / 2.0f) * (dwMapX - dwMapY) - (m_Header.fGeometryWidth / 2.0f);TileRect.UpperLeft.y = (m_Header.fGeometryHeight / 2.0f) * (dwMapX + dwMapY);TileRect.UpperLeft.z = m_Header.fZoom;TileRect.LowerRight.x = (m_Header.fGeometryWidth / 2.0f) * (dwMapX - dwMapY) + (m_Header.fGeometryWidth / 2.0f);TileRect.LowerRight.y = (m_Header.fGeometryHeight / 2.0f) * (dwMapX + dwMapY) - m_Header.fGeometryHeight;TileRect.LowerRight.z = m_Header.fZoom;TileRect.UpperRight.x = (m_Header.fGeometryWidth / 2.0f) * (dwMapX - dwMapY) + (m_Header.fGeometryWidth / 2.0f);TileRect.UpperRight.y = (m_Header.fGeometryHeight / 2.0f) * (dwMapX + dwMapY);TileRect.UpperRight.z = m_Header.fZoom;}//Prüfen ob sich die Rechtecke überschneiden//Das Rechteck wird in 2 Dreiecke zerlegt und das gegen das Tile geprüftTRIANGLE Triangle;Triangle.LowerLeft = pRect->LowerLeft;Triangle.LowerRight = pRect->LowerRight;Triangle.UpperCenter = pRect->UpperLeft;if(TrianglePointCollision(&(TileRect.LowerLeft), &Triangle)) {return true;}if(TrianglePointCollision(&(TileRect.LowerRight), &Triangle)) {return true;}if(TrianglePointCollision(&(TileRect.UpperLeft), &Triangle)) {return true;}if(TrianglePointCollision(&(TileRect.UpperRight), &Triangle)) {return true;}Triangle.LowerLeft = pRect->UpperLeft;Triangle.LowerRight = pRect->LowerRight;Triangle.UpperCenter = pRect->UpperRight;if(TrianglePointCollision(&(TileRect.LowerLeft), &Triangle)) {return true;}if(TrianglePointCollision(&(TileRect.LowerRight), &Triangle)) {return true;}if(TrianglePointCollision(&(TileRect.UpperLeft), &Triangle)) {return true;}if(TrianglePointCollision(&(TileRect.UpperRight), &Triangle)) {return true;}return false;}  The code converts a tile into a rectangle and checks its edge points against the rectangle which is split into 2 triangles to perform the test.Now the code for the collision test.I have got 2 methods.A fast method which seems to return true every time and a slow method wich selects exactly the wrong tiles...//Slow version:bool TrianglePointCollision(D3DVECTOR * pPoint, LPTRIANGLE pTriangle) {D3DVECTOR V1, V2, V3;float fAngle;V1 = NormalizeVector(VectorSubtract(*pPoint, pTriangle->LowerLeft));V2 = NormalizeVector(VectorSubtract(*pPoint, pTriangle->LowerRight));V3 = NormalizeVector(VectorSubtract(*pPoint, pTriangle->UpperCenter));fAngle = acos(DotProduct(V1, V2)) + acos(DotProduct(V2, V3)) + acos(DotProduct(V3, V1));if(fabs(fAngle - 2.0f * D3DX_PI) < 0.0001f) {return true;}return false;}//Fast version:bool TrianglePointCollision(D3DVECTOR & rPoint, TRIANGLE & rTriangle) {D3DVECTOR V1, V2;V1 = CrossProduct(VectorSubtract(rTriangle.UpperCenter, rTriangle.LowerRight), VectorSubtract(rPoint, rTriangle.LowerRight));V2 = CrossProduct(VectorSubtract(rTriangle.UpperCenter, rTriangle.LowerRight), VectorSubtract(rTriangle.LowerLeft, rTriangle.LowerRight));if(DotProduct(V1, V2) < 0.0f) {return false;}V1 = CrossProduct(VectorSubtract(rTriangle.UpperCenter, rTriangle.LowerLeft), VectorSubtract(rPoint, rTriangle.LowerLeft));V2 = CrossProduct(VectorSubtract(rTriangle.UpperCenter, rTriangle.LowerLeft), VectorSubtract(rTriangle.LowerRight, rTriangle.LowerLeft));if(DotProduct(V1, V2) < 0.0f) {return false;}V1 = CrossProduct(VectorSubtract(rTriangle.LowerRight, rTriangle.LowerLeft), VectorSubtract(rPoint, rTriangle.LowerLeft));V2 = CrossProduct(VectorSubtract(rTriangle.LowerRight, rTriangle.LowerLeft), VectorSubtract(rTriangle.UpperCenter, rTriangle.LowerLeft));if(DotProduct(V1, V2) < 0.0f) {return false;}return true;}  Perhaps some of you can help me.So this is the goal:I have got a tile which is represented by 4 untransformed vertices. All tiles have the same Z value.Every bounding rect should have this z-value, too.I need to know if a tile is contained within such a rectangle.   