Optimized line intersection with height field

Post Reply
CookieMonster
Posts: 49
Joined: Sun Jan 29, 2012 10:01 pm

Optimized line intersection with height field

Post by CookieMonster »

This is not a complete description of the modification since I have modified more things in the height field class. Just see processTrianglesAlongLine as pseudo code for how to improve the speed for line intersections.
The code assume that btScalar is defined as float since that is what I use.

Some math functions that I used in the line drawing algorithm.

Code: Select all

float MaxFloat(float A, float B) {
	if (A > B) {
		return A;
	} else {
		return B;
	}
}

float MinFloat(float A, float B) {
	if (A < B) {
		return A;
	} else {
		return B;
	}
}

int ClampInt(int Min, int X, int Max) {
	if (X < Min) {
		return Min;
	} else if (X > Max) {
		return Max;
	} else {
		return X;
	}
}

// Returns A when Ratio = 0
// Returns (A + B) / 2 when Ratio = 0.5
// Returns B when Ratio = 1
float Lerp(float A, float B, float Ratio) {
	return (A * (1 - Ratio)) + (B * Ratio);
}

// Returns 0 when Value = A
// Returns 0.5 when Value = (A + B) / 2
// Returns 1 when Value = B
float InverseLerp(float A, float B, float Value) {
	float C = B - A;
	if (C == 0.0f) {
		return 0.5f;
	} else {
		return (Value - A) / (B - A);
	}
}
A helper function in my modified height field class that sends a quad from x,j back to the listener.

Code: Select all

void MyHeightField::processQuad(btTriangleCallback* callback,int x,int j) const {
	btVector3 vertices[3];
	bool Checker;
	Checker = m_useDiamondSubdivision && !((j+x) & 1);
	if ((m_flipQuadEdges && !Checker) || (!m_flipQuadEdges && Checker)) {
		//first triangle
		getVertex(x,j,vertices[0]);
		getVertex(x+1,j,vertices[1]);
		getVertex(x+1,j+1,vertices[2]);
		callback->processTriangle(vertices,x,j);
		//second triangle
		getVertex(x,j,vertices[0]);
		getVertex(x+1,j+1,vertices[1]);
		getVertex(x,j+1,vertices[2]);
		callback->processTriangle(vertices,x,j);
	} else {
		//first triangle
		getVertex(x,j,vertices[0]);
		getVertex(x,j+1,vertices[1]);
		getVertex(x+1,j,vertices[2]);
		callback->processTriangle(vertices,x,j);
		//second triangle
		getVertex(x+1,j,vertices[0]);
		getVertex(x,j+1,vertices[1]);
		getVertex(x+1,j+1,vertices[2]);
		callback->processTriangle(vertices,x,j);
	}
}
This is the method that I call instead of processAllTriangles when doing line intersections with the height field.

Code: Select all

void MyHeightField::processTrianglesAlongLine(btTriangleCallback* callback,const btVector3& lineStart,const btVector3& lineEnd) const {
	// Divide by local scaling
	btVector3	localLineStart = lineStart * btVector3(1.0f / m_localScaling[0], 1.0f / m_localScaling[1], 1.0f / m_localScaling[2]);
	btVector3	localLineEnd = lineEnd * btVector3(1.0f / m_localScaling[0], 1.0f / m_localScaling[1], 1.0f / m_localScaling[2]);
	
	// Add the center because the array don't have any negative index
	localLineStart += m_localOrigin;
	localLineEnd += m_localOrigin;
	
	float realStartX;
	float realStartJ;
	float realEndX;
	float realEndJ;
	switch (m_upAxis) {
	case 0:
		realStartX = localLineStart.getY();
		realEndX = localLineEnd.getY();
		realStartJ = localLineStart.getZ();
		realEndJ = localLineEnd.getZ();
		break;
	case 1:
		realStartX = localLineStart.getX();
		realEndX = localLineEnd.getX();
		realStartJ = localLineStart.getZ();
		realEndJ = localLineEnd.getZ();
		break;
	default:
		realStartX = localLineStart.getX();
		realEndX = localLineEnd.getX();
		realStartJ = localLineStart.getY();
		realEndJ = localLineEnd.getY();
		break;
	}
	float DX = realEndX - realStartX;
	float DJ = realEndJ - realStartJ;
	int startX = ClampInt(0,getQuantized(MinFloat(realStartX,realEndX)) - 1,m_heightStickWidth - 1);
	int endX = ClampInt(0,getQuantized(MaxFloat(realStartX,realEndX)) + 1,m_heightStickWidth - 1);
	int startJ = ClampInt(0,getQuantized(MinFloat(realStartJ,realEndJ)) - 1,m_heightStickLength - 1);
	int endJ = ClampInt(0,getQuantized(MaxFloat(realStartJ,realEndJ)) + 1,m_heightStickLength - 1);

	if (AbsFloat(DX) < 3 && AbsFloat(DJ) < 3) {
		// Sample within AABB
		for(int j=startJ; j<endJ; j++) {
			for(int x=startX; x<endX; x++) {
				processQuad(callback,x,j);
			}
		}
	} else if (AbsFloat(DX) > AbsFloat(DJ)) {
		// Sample along X using startX and endX in the outmost loop
		for(int x = startX; x < endX; x++) { // From start to less than end so that n to n + m gives m iterations
			float VA = Lerp(realStartJ,realEndJ,InverseLerp(realStartX,realEndX,(float)x));
			float VB = Lerp(realStartJ,realEndJ,InverseLerp(realStartX,realEndX,(float)(x + 1)));
			startJ = ClampInt(0,getQuantized(MinFloat(VA,VB)) - 1,m_heightStickLength - 1);
			endJ = ClampInt(0,getQuantized(MaxFloat(VA,VB)) + 1,m_heightStickLength - 1);
			for(int j=startJ; j<endJ; j++) {
				processQuad(callback,x,j);
			}
		}
	} else {
		// Sample along J using startJ and endJ in the outmost loop
		for(int j = startJ; j < endJ; j++) { // From start to less than end so that n to n + m gives m iterations
			float VA = Lerp(realStartX,realEndX,InverseLerp(realStartJ,realEndJ,(float)j));
			float VB = Lerp(realStartX,realEndX,InverseLerp(realStartJ,realEndJ,(float)(j + 1)));
			startX = ClampInt(0,getQuantized(MinFloat(VA,VB)) - 1,m_heightStickWidth - 1);
			endX = ClampInt(0,getQuantized(MaxFloat(VA,VB)) + 1,m_heightStickWidth - 1);
			for(int x = startX; x < endX; x++) {
				processQuad(callback,x,j);
			}
		}
	}
}
A modified version of rayTestSingle is calling processTrianglesAlongLine for height fields using the line's local start and end points instead of it's axis aligned bounding box.

Code: Select all

concaveShape->processTrianglesAlongLine(&rcb,rayFromLocal,rayToLocal);
This implementation seems to work fine during testing but I just wrote it.
Reply to this thread if you can see something wrong with the code.
Post Reply