graytrace.cpp

一个非常有用的开源代码

		GRayTraceReal x, y;
		pRay->GetTextureCoords(&x, &y);
		x *= m_pTextureImage->GetWidth();
		y *= m_pTextureImage->GetHeight();
		y = m_pTextureImage->GetHeight() - y;
		m_colors[Texture].Set(m_pTextureImage->InterpolatePixel((float)x, (float)y));
		return &m_colors[Texture];
	}
	else
		return &m_colors[eType];
}

void GRayTraceMaterial::SetColor(ColorType eType, GRayTraceColor* pCol)
{
	m_colors[eType].Copy(pCol);
}

void GRayTraceMaterial::SetColor(ColorType eType, GRayTraceReal r, GRayTraceReal g, GRayTraceReal b)
{
	if(eType == Emissive)
		m_colors[eType].Set(1, r, g, b);
	else
		m_colors[eType].Set(1,
				MAX((GRayTraceReal)0, MIN((GRayTraceReal)1, r)),
				MAX((GRayTraceReal)0, MIN((GRayTraceReal)1, g)),
				MAX((GRayTraceReal)0, MIN((GRayTraceReal)1, b))
			);
}

void GRayTraceMaterial::ComputeColor(GRayTraceScene* pScene, GRayTraceRay* pRay, bool bAmbient, bool bSpecular)
{
	if(bAmbient)
	{
		pRay->m_color.Copy(pScene->GetAmbientLight());
		pRay->m_color.Multiply(GetColor(Ambient, pRay));
	}
	else
		pRay->m_color.Set(0, 0, 0, 0);

	// Real lights
	int nLights = pScene->GetLightCount();
	int n;
	for(n = 0; n < nLights; n++)
		pScene->GetLight(n)->ComputeColorContribution(pScene, pRay, this, bSpecular);
}

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

int GRayTraceObjectSorterFunc(void* pThis, void* pA, void* pB)
{
	GRayTraceVector a, b;
	((GRayTraceObject*)pA)->GetCenter(&a);
	((GRayTraceObject*)pB)->GetCenter(&b);
	int nDim = *(int*)pThis;
	if(a.m_vals[nDim] < b.m_vals[nDim])
		return -1;
	else if(a.m_vals[nDim] > b.m_vals[nDim])
		return 1;
	else
		return 0;
}

//static
GRayTraceBoundingBoxBase* GRayTraceBoundingBoxBase::BuildTree(GPointerArray* pObjects)
{
	// Make a leaf node if we can
	if(pObjects->GetSize() <= MAX_OBJECTS_PER_BOUNDING_BOX)
	{
		GRayTraceBoundingBoxBase* pBoundingBoxBase = new GRayTraceBoundingBoxLeaf(pObjects);
		delete(pObjects);
		return pBoundingBoxBase;
	}

	// Find the biggest dimension
	double dBiggestRange = 0;
	int nBiggestDim = -1;
	double dRange;
	int i;
	GRayTraceObject* pFirst;
	GRayTraceObject* pLast;
	GRayTraceVector vFirst, vLast;
	for(i = 0; i < 3; i++)
	{
		pObjects->Sort(GRayTraceObjectSorterFunc, &i);
		pFirst = (GRayTraceObject*)pObjects->GetPointer(0);
		pLast = (GRayTraceObject*)pObjects->GetPointer(pObjects->GetSize() - 1);
		pFirst->GetCenter(&vFirst);
		pLast->GetCenter(&vLast);
		dRange = vLast.m_vals[i] - vFirst.m_vals[i];
		if(dRange > dBiggestRange)
		{
			nBiggestDim = i;
			dBiggestRange = dRange;
		}
	}

	// Split into two arrays
	if(nBiggestDim != 2)
		pObjects->Sort(GRayTraceObjectSorterFunc, &nBiggestDim);
	int nSize = pObjects->GetSize();
	int nLesserSize = nSize / 2;
	GPointerArray* pOther = new GPointerArray(nSize - nLesserSize);
	for(i = nSize - 1; i >= nLesserSize; i--)
	{
		pOther->AddPointer(pObjects->GetPointer(i));
		pObjects->DeleteCell(i);
	}

	// Make an interior node
	GRayTraceBoundingBoxBase* pLesser = BuildTree(pObjects);
	GRayTraceBoundingBoxBase* pGreater = BuildTree(pOther);
	return new GRayTraceBoundingBoxInterior(pLesser, pGreater);
}

//static
GRayTraceBoundingBoxBase* GRayTraceBoundingBoxBase::MakeBoundingBoxTree(GPointerArray* pObjects)
{
	// Make a copy of the object list
	int i;
	int nObjectCount = pObjects->GetSize();
	GPointerArray* pObjectListCopy = new GPointerArray(nObjectCount);
	for(i = 0; i < nObjectCount; i++)
		pObjectListCopy->AddPointer(pObjects->GetPointer(i));

	// Build the tree
	return BuildTree(pObjectListCopy);
}

bool GRayTraceBoundingBoxBase::DoesRayHitBox(GRayTraceVector* pRayOrigin, GRayTraceVector* pDirectionVector)
{
	GRayTraceVector point;
	if(pDirectionVector->m_vals[0] != 0)
	{
		point.Copy(pDirectionVector);
		point.Multiply((m_min.m_vals[0] - pRayOrigin->m_vals[0]) / pDirectionVector->m_vals[0]);
		point.Add(pRayOrigin);
		if(point.m_vals[1] >= m_min.m_vals[1] && point.m_vals[2] >= m_min.m_vals[2] &&
			point.m_vals[1] <= m_max.m_vals[1] && point.m_vals[2] <= m_max.m_vals[2])
			return true;
		point.Copy(pDirectionVector);
		point.Multiply((m_max.m_vals[0] - pRayOrigin->m_vals[0]) / pDirectionVector->m_vals[0]);
		point.Add(pRayOrigin);
		if(point.m_vals[1] >= m_min.m_vals[1] && point.m_vals[2] >= m_min.m_vals[2] &&
			point.m_vals[1] <= m_max.m_vals[1] && point.m_vals[2] <= m_max.m_vals[2])
			return true;
	}
	if(pDirectionVector->m_vals[1] != 0)
	{
		point.Copy(pDirectionVector);
		point.Multiply((m_min.m_vals[1] - pRayOrigin->m_vals[1]) / pDirectionVector->m_vals[1]);
		point.Add(pRayOrigin);
		if(point.m_vals[0] >= m_min.m_vals[0] && point.m_vals[2] >= m_min.m_vals[2] &&
			point.m_vals[0] <= m_max.m_vals[0] && point.m_vals[2] <= m_max.m_vals[2])
			return true;
		point.Copy(pDirectionVector);
		point.Multiply((m_max.m_vals[1] - pRayOrigin->m_vals[1]) / pDirectionVector->m_vals[1]);
		point.Add(pRayOrigin);
		if(point.m_vals[0] >= m_min.m_vals[0] && point.m_vals[2] >= m_min.m_vals[2] &&
			point.m_vals[0] <= m_max.m_vals[0] && point.m_vals[2] <= m_max.m_vals[2])
			return true;
	}
	if(pDirectionVector->m_vals[2] != 0)
	{
		point.Copy(pDirectionVector);
		point.Multiply((m_min.m_vals[2] - pRayOrigin->m_vals[2]) / pDirectionVector->m_vals[2]);
		point.Add(pRayOrigin);
		if(point.m_vals[0] >= m_min.m_vals[0] && point.m_vals[1] >= m_min.m_vals[1] &&
			point.m_vals[0] <= m_max.m_vals[0] && point.m_vals[1] <= m_max.m_vals[1])
			return true;
		point.Copy(pDirectionVector);
		point.Multiply((m_max.m_vals[2] - pRayOrigin->m_vals[2]) / pDirectionVector->m_vals[2]);
		point.Add(pRayOrigin);
		if(point.m_vals[0] >= m_min.m_vals[0] && point.m_vals[1] >= m_min.m_vals[1] &&
			point.m_vals[0] <= m_max.m_vals[0] && point.m_vals[1] <= m_max.m_vals[1])
			return true;
	}
	return false;
}

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

// virtual
GRayTraceObject* GRayTraceBoundingBoxInterior::FindClosestIntersection(GRayTraceVector* pRayOrigin, GRayTraceVector* pDirectionVector, GRayTraceReal* pOutDistance)
{
	if(!DoesRayHitBox(pRayOrigin, pDirectionVector))
		return NULL;
	GRayTraceReal lesserDist = 0;
	GRayTraceReal greaterDist = 0;
	GRayTraceObject* pLesser = m_pLesser->FindClosestIntersection(pRayOrigin, pDirectionVector, &lesserDist);
	GRayTraceObject* pGreater = m_pGreater->FindClosestIntersection(pRayOrigin, pDirectionVector, &greaterDist);
	if(!pGreater)
	{
		*pOutDistance = lesserDist;
		return pLesser;
	}
	if(!pLesser)
	{
		*pOutDistance = greaterDist;
		return pGreater;
	}
	if(lesserDist < greaterDist)
	{
		*pOutDistance = lesserDist;
		return pLesser;
	}
	else
	{
		*pOutDistance = greaterDist;
		return pGreater;
	}
}

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

GRayTraceBoundingBoxLeaf::GRayTraceBoundingBoxLeaf(GPointerArray* pObjects)
{
	m_nObjectCount = pObjects->GetSize();
	m_pObjects = new GRayTraceObject*[m_nObjectCount];
	m_min.Copy((GRayTraceReal)1e30, (GRayTraceReal)1e30, (GRayTraceReal)1e30);
	m_max.Copy((GRayTraceReal)-1e30, (GRayTraceReal)-1e30, (GRayTraceReal)-1e30);
	int i;
	for(i = 0; i < m_nObjectCount; i++)
	{
		m_pObjects[i] = (GRayTraceObject*)pObjects->GetPointer(i);
		m_pObjects[i]->AdjustBoundingBox(&m_min, &m_max);
	}
}

//virtual
GRayTraceBoundingBoxLeaf::~GRayTraceBoundingBoxLeaf()
{
	delete[] m_pObjects;
}

// virtual
GRayTraceObject* GRayTraceBoundingBoxLeaf::FindClosestIntersection(GRayTraceVector* pRayOrigin, GRayTraceVector* pDirectionVector, GRayTraceReal* pOutDistance)
{
	if(!DoesRayHitBox(pRayOrigin, pDirectionVector))
		return NULL;

	// Find the closest intersection
	GRayTraceReal distance;
	GRayTraceReal closestDistance = (GRayTraceReal)1e30; // todo: unmagic this value
	GRayTraceObject* pClosestObject = NULL;
	int n;
	for(n = 0; n < m_nObjectCount; n++)
	{
		distance = m_pObjects[n]->ComputeRayDistance(pRayOrigin, pDirectionVector);
		if(distance < closestDistance && distance > MIN_RAY_DISTANCE)
		{
			closestDistance = distance;
			pClosestObject = m_pObjects[n];
		}
	}
	*pOutDistance = closestDistance;
	return pClosestObject;
}

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

GRayTraceTriMesh::GRayTraceTriMesh(GRayTraceMaterial* pMaterial, int nPoints, int nTriangles, int nNormals, int nTextureCoords)
{
	m_pMaterial = pMaterial;
	m_nPoints = nPoints;
	m_pPoints = new GRayTraceVector[nPoints];
	m_nTriangles = nTriangles;
	m_pTriangles = new int[3 * nTriangles];
	if(nNormals > 0)
	{
		if(nNormals != nPoints)
			throw "The number of normals is not equal to the number of vertices";
		m_pNormals = new GRayTraceVector[nPoints];
	}
	else
		m_pNormals = NULL;
	if(nTextureCoords > 0)
	{
		if(nTextureCoords != nPoints)
			throw "The number of texture coords is not equal to the number of vertices";
		m_pTextureCoords = new GRayTraceReal[2 * nPoints];
	}
	else
		m_pTextureCoords = NULL;
	m_bCulling = false;
}

/*virtual*/ GRayTraceTriMesh::~GRayTraceTriMesh()
{
	delete[] m_pPoints;
	delete[] m_pTriangles;
	delete[] m_pNormals;
	delete[] m_pTextureCoords;
}

void GRayTraceTriMesh::SetPoint(int nIndex, GRayTraceVector* pPoint)
{
	GAssert(nIndex >= 0 && nIndex < m_nPoints, "out of range");
	m_pPoints[nIndex] = *pPoint;
}

void GRayTraceTriMesh::SetTriangle(int nIndex, int v1, int v2, int v3)
{
	GAssert(nIndex >= 0 && nIndex < m_nTriangles, "out of range");
	int* pTri = &m_pTriangles[3 * nIndex];
	pTri[0] = v1;
	pTri[1] = v2;
	pTri[2] = v3;
}

void GRayTraceTriMesh::SetNormal(int nIndex, GRayTraceVector* pNormal)
{
	GAssert(nIndex >= 0 && nIndex < m_nPoints, "out of range");
	m_pNormals[nIndex] = *pNormal;
}

class EdgeRecord : public HashTableNode
{
protected:
	int m_v1;
	int m_v2;
	GIntArray m_triangles;

public:
	EdgeRecord(int v1, int v2) : HashTableNode(), m_triangles(4)
	{
		SetEdge(v1, v2);
	}

	virtual ~EdgeRecord()
	{
	}

	GIntArray* GetTriangles() { return &m_triangles; }

	void SetEdge(int v1, int v2)
	{
		if(v1 < v2)
		{
			m_v1 = v1;
			m_v2 = v2;
		}
		else
		{
			m_v1 = v2;
			m_v2 = v1;
		}
	}

	virtual unsigned int Hash(int nBucketCount)
	{
		return (m_v1 * 7387 + m_v2) % nBucketCount;
	}

	virtual bool Equals(HashTableNode* pThat)
	{
		EdgeRecord* pOther = (EdgeRecord*)pThat;
		return ((m_v1 == pOther->m_v1) && (m_v2 == pOther->m_v2));
	}
	
	void AddTriangle(int i)
	{
		m_triangles.AddInt(i);
	}
};

void GRayTraceTriMesh::ComputeTriangleNeighborSides(GPointerQueue* pQ, GNodeHashTable* pEdges, int* pFaces, int i)
{
	GAssert(pFaces[i] != 0, "Expected to already know the facing direction of triangle i");
	EdgeRecord tmp(-1, -1);
	int j, k, l, n;
	for(j = 0; j < 3; j++) // j = which side of the main triangle
	{
		tmp.SetEdge(m_pTriangles[3 * i + j], m_pTriangles[3 * i + ((j + 1) % 3)]);
		EdgeRecord* pEdge = (EdgeRecord*)pEdges->Get(&tmp);
		GAssert(pEdge, "No record of this edge");
		GIntArray* pTriangles = pEdge->GetTriangles();
		for(k = 0; k < pTriangles->GetSize(); k++) // k = which neighbor index
		{
			n = pTriangles->GetInt(k);
			if(n == i)
				continue; // It's the same triangle
			if(pFaces[n] != 0)
				continue; // That triangle has already been done

			// Find the first matching vertex
			for(l = 0; l < 3; l++) // l = which vertex on the neighbor
			{
				if(m_pTriangles[3 * n + l] == m_pTriangles[3 * i + j])
					break;
			}
			GAssert(l < 3, "Expected neighbor to have matching vertex");

			// Determine whether the triangles face the same way
			if(m_pTriangles[3 * n + ((l + 1) % 3)] == m_pTriangles[3 * i + ((j + 1) % 3)])
				pFaces[n] = -pFaces[i];
			else
			{
				GAssert(m_pTriangles[3 * n + ((l + 2) % 3)] == m_pTriangles[3 * i + ((j + 1) % 3)], "Expected a matching side");
				pFaces[n] = pFaces[i];
			}

			// Add the neighbor to the queue
			pQ->Push((void*)n); // todo: not 64-bit compliant
		}
	}

}

class GTriangleIndexArray : public GIntArray
{
public:
	GTriangleIndexArray() : GIntArray(4) {}
	virtual ~GTriangleIndexArray() {}
};

void GRayTraceTriMesh::ComputePhongNormals()
{
	// Compute all the triangles that share a common edge
	EdgeRecord tmp(-1, -1);
	EdgeRecord* pEdge = NULL;
	GNodeHashTable htEdges(true, MAX(67, m_nTriangles * 6 + 1));
	int i, j;
	for(i = 0; i < m_nTriangles; i++)
	{
		for(j = 0; j < 3; j++)
		{
			tmp.SetEdge(m_pTriangles[3 * i + j], m_pTriangles[3 * i + ((j + 1) % 3)]);
			pEdge = (EdgeRecord*)htEdges.Get(&tmp);
			if(!pEdge)
			{
				pEdge = new EdgeRecord(m_pTriangles[3 * i + j], m_pTriangles[3 * i + ((j + 1) % 3)]);
				htEdges.Add(pEdge);
			}
			pEdge->AddTriangle(i);
		}
	}

	// Determine which way all the triangles face (0 = don't know yet, 1 = a-b-c, -1 = c-b-a)
	int* pFaces = new int[m_nTriangles];
	ArrayHolder<int*> hFaces(pFaces);
	memset(pFaces, '\0', sizeof(int) * m_nTriangles);
	GPointerQueue q;
	while(true)
	{
		if(q.GetSize() > 0)
			i = (int)q.Pop(); // todo: not 64-bit compliant
		else
		{
			// Find a triangle for which the direction is not known
			for(i = 0; i < m_nTriangles; i++)
			{
				if(pFaces[i] == 0)
					break;
			}
			if(i >= m_nTriangles)
				break; // we're done

			// Set it to an arbitrary direction
			pFaces[i] = 1;
		}
		ComputeTriangleNeighborSides(&q, &htEdges, pFaces, i);
	}

	// Make lists of all the triangles that touch each vertex
	GTEMPBUF(GTriangleIndexArray, arrVertexTriangles, m_nPoints);
	for(i = 0; i < m_nTriangles; i++)
	{
		for(j = 0; j < 3; j++)
			arrVertexTriangles[m_pTriangles[3 * i + j]].AddInt(i);
	}

	// Make the vertex normals