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 Rect
struct 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üft
	TRIANGLE 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.