Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Hippokrates

Speeding up Map Rendering

This topic is 5936 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!