graytrace.cpp

一个非常有用的开源代码

	int nTri;
	delete[] m_pNormals;
	m_pNormals = new GRayTraceVector[m_nPoints];
	GRayTraceVector triNorm;
	for(i = 0; i < m_nPoints; i++)
	{
		m_pNormals[i].Set(0, 0, 0);
		for(j = 0; j < arrVertexTriangles[i].GetSize(); j++)
		{
			nTri = arrVertexTriangles[i].GetInt(j);
			GAssert(nTri >= 0 && nTri < m_nTriangles, "out of range");
			if(pFaces[nTri] >= 0)
				triNorm.ComputeTriangleNormal(
						&m_pPoints[m_pTriangles[3 * nTri]],
						&m_pPoints[m_pTriangles[3 * nTri + 1]],
						&m_pPoints[m_pTriangles[3 * nTri + 2]]
					);
			else
				triNorm.ComputeTriangleNormal(
						&m_pPoints[m_pTriangles[3 * nTri + 2]],
						&m_pPoints[m_pTriangles[3 * nTri + 1]],
						&m_pPoints[m_pTriangles[3 * nTri]]
					);
			// todo: scale the triNorm by the area of the triangle
			m_pNormals[i].Add(&triNorm);
		}
		m_pNormals[i].Normalize();
	}
}

void GRayTraceTriMesh::SetTextureCoord(int nIndex, GRayTraceReal x, GRayTraceReal y)
{
	GAssert(nIndex >= 0 && nIndex < m_nPoints, "out of range");
	nIndex *= 2;
	m_pTextureCoords[nIndex] = x;
	m_pTextureCoords[nIndex + 1] = y;
}

bool GRayTraceTriMesh::IsPointWithinPlanarPolygon(GRayTraceVector* pPoint, GRayTraceVector** ppVertices, int nVertices)
{
	// Find the two dimensions with the most significant component (which
	// are the dimensions with the smallest component in the normal vector)
	GAssert(nVertices >= 3, "at least three points are needed to define a planar polygon");
	GRayTraceVector plane;
	plane.ComputeTriangleNormal(ppVertices[0], ppVertices[1], ppVertices[2]);
	plane.m_vals[0] = ABS(plane.m_vals[0]);
	plane.m_vals[1] = ABS(plane.m_vals[1]);
	plane.m_vals[2] = ABS(plane.m_vals[2]);
	int d1, d2;
	if(plane.m_vals[0] >= plane.m_vals[1] && plane.m_vals[0] >= plane.m_vals[2])
	{
		d1 = 1;
		d2 = 2;
	}
	else if(plane.m_vals[1] >= plane.m_vals[0] && plane.m_vals[1] >= plane.m_vals[2])
	{
		d1 = 0;
		d2 = 2;
	}
	else
	{
		d1 = 0;
		d2 = 1;
	}

	// Count the number of times a ray shot out from the point crosses
	// a side of the polygon
	int numCrossings = 0;
	int signHolder, nextSignHolder;
	if(ppVertices[0]->m_vals[d2] - pPoint->m_vals[d2] < 0)
		signHolder = -1;
	else
		signHolder = 1;
	int nVertex, nNextVertex;
	GRayTraceReal u0, u1, v0, v1;
	for(nVertex = 0; nVertex < nVertices; nVertex++)
	{
		nNextVertex = (nVertex + 1) % nVertices;
		v1 = ppVertices[nNextVertex]->m_vals[d2] - pPoint->m_vals[d2];
		if(v1 < 0)
			nextSignHolder = -1;
		else
			nextSignHolder = 1;
		if(signHolder != nextSignHolder)
		{
			u0 = ppVertices[nVertex]->m_vals[d1] - pPoint->m_vals[d1];
			u1 = ppVertices[nNextVertex]->m_vals[d1] - pPoint->m_vals[d1];
			v0 = ppVertices[nVertex]->m_vals[d2] - pPoint->m_vals[d2];
			if(u0 - v0 * (u1 - u0) / (v1 - v0) > 0)
				numCrossings++;
		}
		signHolder = nextSignHolder;
	}
	if(numCrossings & 1)
		return true;
	else
		return false;
}

GRayTraceReal GRayTraceTriMesh::ComputeRayDistanceToTriangle(int nTriangle, GRayTraceVector* pRayOrigin, GRayTraceVector* pRayDirection)
{
	// Compute the plane equasion Ax + By + Cz + D = 0
	int* pTriangle = &m_pTriangles[3 * nTriangle];
	GRayTraceVector plane; // The plane normal is the vector (A, B, C)
	GRayTraceReal d;
	plane.ComputePlaneEquasion(&m_pPoints[pTriangle[0]], &m_pPoints[pTriangle[1]], &m_pPoints[pTriangle[2]], &d);

	// Compute distance and point of intersection
	GRayTraceReal tmp = plane.DotProduct(pRayDirection);
	if(tmp >= 0)
	{
		if(tmp == 0)
			return 0; // the ray is paralell to the plane
		if(m_bCulling)
			return 0; // the ray hits the back side of the plane
		else
		{
			// Reverse the plane normal
			plane.Multiply(-1);
			d = -d;
			tmp = -tmp;
		}
	}
	GRayTraceReal distance = -(plane.DotProduct(pRayOrigin) + d) / tmp;
	if(distance <= 0)
		return 0; // the intersection point is behind the ray origin
	GRayTraceVector point(pRayDirection);
	point.Multiply(distance);
	point.Add(pRayOrigin);

	// Determine if the intersection point is within the triangle
	GRayTraceVector* pVertices[3];
	pVertices[0] = &m_pPoints[pTriangle[0]];
	pVertices[1] = &m_pPoints[pTriangle[1]];
	pVertices[2] = &m_pPoints[pTriangle[2]];
	if(!IsPointWithinPlanarPolygon(&point, pVertices, 3))
		return 0; // the ray misses the triangle
	return distance;
}

void GRayTraceTriMesh::ComputeNormalVector(GRayTraceRay* pRay, int nIndex)
{
	int* pTriangle = &m_pTriangles[3 * nIndex];
	pRay->m_normalVector.ComputeTriangleNormal(&m_pPoints[pTriangle[0]], &m_pPoints[pTriangle[1]], &m_pPoints[pTriangle[2]]);
	if(!m_pNormals && !m_pTextureCoords)
		return;

	// Find the two most significant dimensions
	int i1,i2;
	GRayTraceReal xx, yy, zz;
	xx = pRay->m_normalVector.m_vals[0] * pRay->m_normalVector.m_vals[0];
	yy = pRay->m_normalVector.m_vals[1] * pRay->m_normalVector.m_vals[1];
	zz = pRay->m_normalVector.m_vals[2] * pRay->m_normalVector.m_vals[2];
	if(xx >= yy && xx >= zz)
	{
		i1 = 1;
		i2 = 2;
	}
	else if(yy >= zz)
	{
		i1 = 0;
		i2 = 2;
	}
	else
	{
		i1 = 0;
		i2 = 1;
	}

	// Find the weights alpha, beta, and gamma
	GRayTraceReal u1 = m_pPoints[pTriangle[1]].m_vals[i1] - m_pPoints[pTriangle[0]].m_vals[i1];
	GRayTraceReal u2 = m_pPoints[pTriangle[2]].m_vals[i1] - m_pPoints[pTriangle[0]].m_vals[i1];
	GRayTraceReal v1 = m_pPoints[pTriangle[1]].m_vals[i2] - m_pPoints[pTriangle[0]].m_vals[i2];
	GRayTraceReal v2 = m_pPoints[pTriangle[2]].m_vals[i2] - m_pPoints[pTriangle[0]].m_vals[i2];
	GRayTraceReal u0 = pRay->m_collisionPoint.m_vals[i1] - m_pPoints[pTriangle[0]].m_vals[i1];
	GRayTraceReal v0 = pRay->m_collisionPoint.m_vals[i2] - m_pPoints[pTriangle[0]].m_vals[i2];
	GRayTraceReal beta  = (u0 * v2 - u2 * v0) / (u1 * v2 - v1 * u2);
	GRayTraceReal gamma = (v0 * u1 - u0 * v1) / (u1 * v2 - v1 * u2);
	GRayTraceReal alpha = (GRayTraceReal)1.0 - (gamma + beta);
/*
	GAssert(ABS(alpha * m_pPoints[pTriangle[0]].m_vals[0] + beta * m_pPoints[pTriangle[1]].m_vals[0] + gamma * m_pPoints[pTriangle[2]].m_vals[0] - pRay->m_collisionPoint.m_vals[0]) < .001, "value is wrong");
	GAssert(ABS(alpha * m_pPoints[pTriangle[0]].m_vals[1] + beta * m_pPoints[pTriangle[1]].m_vals[1] + gamma * m_pPoints[pTriangle[2]].m_vals[1] - pRay->m_collisionPoint.m_vals[1]) < .001, "value is wrong");
	GAssert(ABS(alpha * m_pPoints[pTriangle[0]].m_vals[2] + beta * m_pPoints[pTriangle[1]].m_vals[2] + gamma * m_pPoints[pTriangle[2]].m_vals[2] - pRay->m_collisionPoint.m_vals[2]) < .001, "value is wrong");
*/	
	// todo: If beta and gamma > 0 and beta + gamma <= 1,
	// then the point of intersection is inside the triangle.
	// This could be used as a more efficient inside-outside test for triangles.
 
	// Compute the Phong normal
	if(m_pNormals)
	{
		GRayTraceVector tmpNormal(&m_pNormals[pTriangle[0]]);
		tmpNormal.Multiply(alpha);
		pRay->m_normalVector.Copy(&tmpNormal);
		tmpNormal.Copy(&m_pNormals[pTriangle[1]]);
		tmpNormal.Multiply(beta);
		pRay->m_normalVector.Add(&tmpNormal);
		tmpNormal.Copy(&m_pNormals[pTriangle[2]]);
		tmpNormal.Multiply(gamma);
		pRay->m_normalVector.Add(&tmpNormal);
		pRay->m_normalVector.Normalize();
	}

	// Compute texture coordinate
	if(m_pTextureCoords)
	{
		GRayTraceReal x = alpha * m_pTextureCoords[2 * pTriangle[0]] +
				beta * m_pTextureCoords[2 * pTriangle[1]] +
				gamma * m_pTextureCoords[2 * pTriangle[2]];
		GRayTraceReal y = alpha * m_pTextureCoords[2 * pTriangle[0] + 1] +
				beta * m_pTextureCoords[2 * pTriangle[1] + 1] +
				gamma * m_pTextureCoords[2 * pTriangle[2] + 1];
		pRay->SetTextureCoords(x, y);
	}
}

void GRayTraceTriMesh::GetCenter(GRayTraceVector* pOutPoint, int nIndex)
{
	int* pTriangle = &m_pTriangles[3 * nIndex];
	pOutPoint->Copy(&m_pPoints[pTriangle[0]]);
	pOutPoint->Add(&m_pPoints[pTriangle[1]]);
	pOutPoint->Add(&m_pPoints[pTriangle[2]]);
	pOutPoint->Multiply((GRayTraceReal)1.0 / (GRayTraceReal)3.0);
}

GRayTraceVector* GRayTraceTriMesh::GetVertex(int nIndex, int nVertex)
{
	int* pTriangle = &m_pTriangles[3 * nIndex];
	return &m_pPoints[pTriangle[nVertex]];
}

void GRayTraceTriMesh::AdjustBoundingBox(int nIndex, GRayTraceVector* pMin, GRayTraceVector* pMax)
{
	int* pTriangle = &m_pTriangles[3 * nIndex];

	// Vertex 0
	pMin->m_vals[0] = MIN(pMin->m_vals[0], m_pPoints[pTriangle[0]].m_vals[0]);
	pMin->m_vals[1] = MIN(pMin->m_vals[1], m_pPoints[pTriangle[0]].m_vals[1]);
	pMin->m_vals[2] = MIN(pMin->m_vals[2], m_pPoints[pTriangle[0]].m_vals[2]);
	pMax->m_vals[0] = MAX(pMax->m_vals[0], m_pPoints[pTriangle[0]].m_vals[0]);
	pMax->m_vals[1] = MAX(pMax->m_vals[1], m_pPoints[pTriangle[0]].m_vals[1]);
	pMax->m_vals[2] = MAX(pMax->m_vals[2], m_pPoints[pTriangle[0]].m_vals[2]);

	// Vertex 1
	pMin->m_vals[0] = MIN(pMin->m_vals[0], m_pPoints[pTriangle[1]].m_vals[0]);
	pMin->m_vals[1] = MIN(pMin->m_vals[1], m_pPoints[pTriangle[1]].m_vals[1]);
	pMin->m_vals[2] = MIN(pMin->m_vals[2], m_pPoints[pTriangle[1]].m_vals[2]);
	pMax->m_vals[0] = MAX(pMax->m_vals[0], m_pPoints[pTriangle[1]].m_vals[0]);
	pMax->m_vals[1] = MAX(pMax->m_vals[1], m_pPoints[pTriangle[1]].m_vals[1]);
	pMax->m_vals[2] = MAX(pMax->m_vals[2], m_pPoints[pTriangle[1]].m_vals[2]);

	// Vertex 2
	pMin->m_vals[0] = MIN(pMin->m_vals[0], m_pPoints[pTriangle[2]].m_vals[0]);
	pMin->m_vals[1] = MIN(pMin->m_vals[1], m_pPoints[pTriangle[2]].m_vals[1]);
	pMin->m_vals[2] = MIN(pMin->m_vals[2], m_pPoints[pTriangle[2]].m_vals[2]);
	pMax->m_vals[0] = MAX(pMax->m_vals[0], m_pPoints[pTriangle[2]].m_vals[0]);
	pMax->m_vals[1] = MAX(pMax->m_vals[1], m_pPoints[pTriangle[2]].m_vals[1]);
	pMax->m_vals[2] = MAX(pMax->m_vals[2], m_pPoints[pTriangle[2]].m_vals[2]);
}

// static
GRayTraceTriMesh* GRayTraceTriMesh::MakeQuadSurface(GRayTraceMaterial* pMaterial, GRayTraceVector* p1, GRayTraceVector* p2, GRayTraceVector* p3, GRayTraceVector* p4)
{
	GImage* pImage = pMaterial->GetTextureImage();
	GRayTraceTriMesh* pMesh = new GRayTraceTriMesh(pMaterial, 4, 2, 0, (pImage ? 4 : 0));
	pMesh->SetPoint(0, p1);
	pMesh->SetPoint(1, p2);
	pMesh->SetPoint(2, p3);
	pMesh->SetPoint(3, p4);
	pMesh->SetTriangle(0, 0, 1, 2);
	pMesh->SetTriangle(1, 2, 3, 0);
	if(pImage)
	{
		pMesh->SetTextureCoord(0, 0, 0);
		pMesh->SetTextureCoord(1, (GRayTraceReal)(pImage->GetWidth() - 1), 0);
		pMesh->SetTextureCoord(2, (GRayTraceReal)(pImage->GetWidth() - 1), (GRayTraceReal)(pImage->GetHeight() - 1));
		pMesh->SetTextureCoord(3, 0, (GRayTraceReal)(pImage->GetHeight() - 1));
	}
	return pMesh;
}

// static
GRayTraceTriMesh* GRayTraceTriMesh::MakeSingleTriangle(GRayTraceMaterial* pMaterial, GRayTraceVector* p1, GRayTraceVector* p2, GRayTraceVector* p3)
{
	GImage* pImage = pMaterial->GetTextureImage();
	GRayTraceTriMesh* pMesh = new GRayTraceTriMesh(pMaterial, 3, 1, 0, (pImage ? 4 : 0));
	pMesh->SetPoint(0, p1);
	pMesh->SetPoint(1, p2);
	pMesh->SetPoint(2, p3);
	pMesh->SetTriangle(0, 0, 1, 2);
	if(pImage)
	{
		pMesh->SetTextureCoord(0, 0, 0);
		pMesh->SetTextureCoord(1, (GRayTraceReal)(pImage->GetWidth() - 1), 0);
		pMesh->SetTextureCoord(2, 0, (GRayTraceReal)(pImage->GetHeight() - 1));
	}
	return pMesh;
}

// static
GRayTraceTriMesh* GRayTraceTriMesh::MakeCylinder(GRayTraceMaterial* pMaterial, GRayTraceVector* pCenter1, GRayTraceVector* pCenter2, GRayTraceReal radius, int nSides, bool bEndCaps)
{
	// Compute t, u, and v as the three component vectors of the MakeCylinder. w is just any
	// vector that is not parallel to t
	GRayTraceVector t(pCenter1);
	t.Subtract(pCenter2);
	GRayTraceVector w;
	if(t.m_vals[0] > t.m_vals[1] && t.m_vals[0] > t.m_vals[2])
		w.m_vals[1] = 1;
	else
		w.m_vals[0] = 1;
	GRayTraceVector u, v;
	u.CrossProduct(&t, &w);
	u.Normalize();
	u.Multiply(radius);
	v.CrossProduct(&t, &u);
	v.Normalize();
	v.Multiply(radius);

	// Make the mesh
	int nVertices = nSides * 2 + (bEndCaps ? 2 : 0);
	int nTriangles = nSides * (bEndCaps ? 4 : 2);
	GImage* pImage = pMaterial->GetTextureImage();
	GRayTraceTriMesh* pMesh = new GRayTraceTriMesh(pMaterial, nVertices, nTriangles, 0, (pImage ? nVertices : 0));
	GRayTraceVector p1(pCenter1);
	p1.Add(&u);
	GRayTraceVector p2(pCenter2);
	p2.Add(&u);
	GRayTraceVector p3, p4;
	double dRads;
	double dStep = 2 * PI / nSides;
	int nVertex = 0;
	int nTriangle = 0;
	if(bEndCaps)
	{
		pMesh->SetPoint(nVertex++, pCenter1);
		pMesh->SetPoint(nVertex++, pCenter2);
		if(pImage)
		{
			pMesh->SetTextureCoord(nVertex - 2, (GRayTraceReal)pImage->GetWidth() / 2, (GRayTraceReal)pImage->GetHeight() / 2);
			pMesh->SetTextureCoord(nVertex - 1, (GRayTraceReal)pImage->GetWidth() / 2, (GRayTraceReal)pImage->GetHeight() / 2);
		}
	}
	int nPrevVertexPos = nVertices;
	for(dRads = 2 * PI - .000000001; dRads > 0; ) // the small constant is to ensure that rounding error doesn't cause an extra side to be added
	{
		// Move forward
		dRads -= dStep;
		p3.Copy(&p1);
		p4.Copy(&p2);

		// Compute the two vertices of the new edge
		w.Copy(&u);
		w.Multiply((GRayTraceReal)cos(dRads));
		p1.Copy(&v);
		p1.Multiply((GRayTraceReal)sin(dRads));
		p1.Add(&w);
		p2.Copy(&p1);
		p1.Add(pCenter1);
		p2.Add(pCenter2);
		pMesh->SetPoint(nVertex++, &p1);
		pMesh->SetPoint(nVertex++, &p2);

		// Set the texture coordinates
		if(pImage)
		{
			GRayTraceReal y = (GRayTraceReal)(dRads * (pImage->GetHeight() - 1) / (2 * PI));
			pMesh->SetTextureCoord(nVertex - 2, 0, y);
			pMesh->SetTextureCoord(nVertex - 1, (GRayTraceReal)(pImage->GetWidth() - 1), y);
		}

		// Make the triangles
		pMesh->SetTriangle(nTriangle++, nVertex - 1, nVertex - 2, nPrevVertexPos - 1);
		pMesh->SetTriangle(nTriangle++, nPrevVertexPos - 2, nPrevVertexPos - 1, nVertex - 2);
		if(bEndCaps)
		{
			pMesh->SetTriangle(nTriangle++, nVertex - 2, nPrevVertexPos - 2, 0);
			pMesh->SetTriangle(nTriangle++, nVertex - 1, nPrevVertexPos - 1, 1);
		}

		nPrevVertexPos = nVertex;
	}
	GAssert(nVertex == nVertices, "wrong number of vertices");
	GAssert(nTriangle == nTriangles, "wrong number of triangles");
	pMesh->ComputePhongNormals();
	return pMesh;
}


// -----------------------------------------------------------------------------

/*virtual*/ GRayTraceReal GRayTraceSphere::ComputeRayDistance(GRayTraceVector* pRayOrigin, GRayTraceVector* pRayDirection)
{
	GRayTraceReal b = (GRayTraceReal)2 * (
				pRayDirection->m_vals[0] * (pRayOrigin->m_vals[0] - m_center.m_vals[0]) +
				pRayDirection->m_vals[1] * (pRayOrigin->m_vals[1] - m_center.m_vals[1]) +
				pRayDirection->m_vals[2] * (pRayOrigin->m_vals[2] - m_center.m_vals[2])
			);
	GRayTraceReal c = pRayOrigin->m_vals[0] * pRayOrigin->m_vals[0] -
				(GRayTraceReal)2 * pRayOrigin->m_vals[0] * m_center.m_vals[0] +
				m_center.m_vals[0] * m_center.m_vals[0] +
				pRayOrigin->m_vals[1] * pRayOrigin->m_vals[1] -
				(GRayTraceReal)2 * pRayOrigin->m_vals[1] * m_center.m_vals[1] +
				m_center.m_vals[1] * m_center.m_vals[1] +
				pRayOrigin->m_vals[2] * pRayOrigin->m_vals[2] -
				(GRayTraceReal)2 * pRayOrigin->m_vals[2] * m_center.m_vals[2] +
				m_center.m_vals[2] * m_center.m_vals[2] -
				m_radius * m_radius;
	GRayTraceReal discriminant = b * b - (GRayTraceReal)4 * c;
	if(discriminant < 0)
		return 0;
	GRayTraceReal dist = (b + (GRayTraceReal)sqrt(discriminant)) / (-2);
	if(dist > MIN_RAY_DISTANCE)
		return dist;
	dist = (b - (GRayTraceReal)sqrt(discriminant)) / (-2);
	return dist;
}

//virtual
void GRayTraceSphere::ComputeNormalVector(GRayTraceRay* pRay)
{
	pRay->m_normalVector.Copy(&pRay->m_collisionPoint);
	pRay->m_normalVector.Subtract(&m_center);
	pRay->m_normalVector.Normalize();
}

//virtual
void GRayTraceSphere::AdjustBoundingBox(GRayTraceVector* pMin, GRayTraceVector* pMax)
{
	pMin->m_vals[0] = MIN(pMin->m_vals[0], m_center.m_vals[0] - m_radius);
	pMin->m_vals[1] = MIN(pMin->m_vals[1], m_center.m_vals[1] - m_radius);
	pMin->m_vals[2] = MIN(pMin->m_vals[2], m_center.m_vals[2] - m_radius);
	pMax->m_vals[0] = MAX(pMax->m_vals[0], m_center.m_vals[0] + m_radius);
	pMax->m_vals[1] = MAX(pMax->m_vals[1], m_center.m_vals[1] + m_radius);
	pMax->m_vals[2] = MAX(pMax->m_vals[2], m_center.m_vals[2] + m_radius);
}

// -----------------------------------------------------------------------------

//virtual
GRayTraceReal GRayTraceTriangle::ComputeRayDistance(GRayTraceVector* pRayOrigin, GRayTraceVector* pRayDirection)
{
	return m_pMesh->ComputeRayDistanceToTriangle(m_nIndex, pRayOrigin, pRayDirection);
}

//virtual
void GRayTraceTriangle::ComputeNormalVector(GRayTraceRay* pRay)
{
	m_pMesh->ComputeNormalVector(pRay, m_nIndex);
}

//virtual
void GRayTraceTriangle::GetCenter(GRayTraceVector* pOutPoint)
{
	m_pMesh->GetCenter(pOutPoint, m_nIndex);
}

//virtual
void GRayTraceTriangle::AdjustBoundingBox(GRayTraceVector* pMin, GRayTraceVector* pMax)
{
	m_pMesh->AdjustBoundingBox(m_nIndex, pMin, pMax);
}

GRayTraceVector* GRayTraceTriangle::GetVertex(int nVertex)
{
	return m_pMesh->GetVertex(m_nIndex, nVertex);
}