diff options
Diffstat (limited to 'Runtime/Geometry/BoundingUtils.cpp')
| -rw-r--r-- | Runtime/Geometry/BoundingUtils.cpp | 443 |
1 files changed, 443 insertions, 0 deletions
diff --git a/Runtime/Geometry/BoundingUtils.cpp b/Runtime/Geometry/BoundingUtils.cpp new file mode 100644 index 0000000..7c9b361 --- /dev/null +++ b/Runtime/Geometry/BoundingUtils.cpp @@ -0,0 +1,443 @@ +#include "UnityPrefix.h" +#include "BoundingUtils.h" +#include "Plane.h" +#include "AABB.h" +#include "Intersection.h" + +// -------------------------------------------------------------------------- + +void GetFrustumPoints( const Matrix4x4f& clipToWorld, Vector3f* frustum ) +{ + clipToWorld.PerspectiveMultiplyPoint3( Vector3f(-1,-1,-1), frustum[0] ); + clipToWorld.PerspectiveMultiplyPoint3( Vector3f( 1,-1,-1), frustum[1] ); + clipToWorld.PerspectiveMultiplyPoint3( Vector3f( 1, 1,-1), frustum[2] ); + clipToWorld.PerspectiveMultiplyPoint3( Vector3f(-1, 1,-1), frustum[3] ); + clipToWorld.PerspectiveMultiplyPoint3( Vector3f(-1,-1, 1), frustum[4] ); + clipToWorld.PerspectiveMultiplyPoint3( Vector3f( 1,-1, 1), frustum[5] ); + clipToWorld.PerspectiveMultiplyPoint3( Vector3f( 1, 1, 1), frustum[6] ); + clipToWorld.PerspectiveMultiplyPoint3( Vector3f(-1, 1, 1), frustum[7] ); +} + +void GetFrustumPortion( const Vector3f* frustum, float nearSplit, float farSplit, Vector3f* outPortion ) +{ + outPortion[0] = Lerp( frustum[0], frustum[0+4], nearSplit ); + outPortion[1] = Lerp( frustum[1], frustum[1+4], nearSplit ); + outPortion[2] = Lerp( frustum[2], frustum[2+4], nearSplit ); + outPortion[3] = Lerp( frustum[3], frustum[3+4], nearSplit ); + outPortion[4] = Lerp( frustum[0], frustum[0+4], farSplit ); + outPortion[5] = Lerp( frustum[1], frustum[1+4], farSplit ); + outPortion[6] = Lerp( frustum[2], frustum[2+4], farSplit ); + outPortion[7] = Lerp( frustum[3], frustum[3+4], farSplit ); +} + +static bool ClipTest( const float p, const float q, float& u1, float& u2 ) +{ + // Return value is 'true' if line segment intersects the current test + // plane. Otherwise 'false' is returned in which case the line segment + // is entirely clipped. + const float EPS = 1.0e-10f; + if( p < -EPS ) { + float r = q/p; + if( r > u2 ) + return false; + else { + if( r > u1 ) + u1 = r; + return true; + } + } + else if( p > EPS ) + { + float r = q/p; + if( r < u1 ) + return false; + else { + if( r < u2 ) + u2 = r; + return true; + } + } + else + { + return q >= 0.0f; + } +} + +static bool IntersectLineAABB( Vector3f& v, const Vector3f& p, const Vector3f& dir, const MinMaxAABB& b ) +{ + float t1 = 0.0f; + float t2 = 1.0e30f; + bool intersect = false; + if (ClipTest(-dir.z,p.z-b.GetMin().z,t1,t2) && ClipTest(dir.z,b.GetMax().z-p.z,t1,t2) && + ClipTest(-dir.y,p.y-b.GetMin().y,t1,t2) && ClipTest(dir.y,b.GetMax().y-p.y,t1,t2) && + ClipTest(-dir.x,p.x-b.GetMin().x,t1,t2) && ClipTest(dir.x,b.GetMax().x-p.x,t1,t2)) + { + if( 0 <= t1 ) { + v = p + dir * t1; + intersect = true; + } + if( 0 <= t2 ) { + v = p + dir * t2; + intersect = true; + } + } + return intersect; +} + +inline bool ClipPolysByPlane( UInt8 numPoints, const Vector3f* __restrict input, const Plane& A, UInt8* __restrict pNumOutPoints, Vector3f* __restrict output, UInt8* __restrict pNumIntermPoints, Vector3f* __restrict interm ) +{ + int i; + if( numPoints < 3 ) + { + *pNumOutPoints = 0; + return false; + } + + UInt8 numOutPoints = 0; + UInt8& numIntermPoints = *pNumIntermPoints; + + Vector3f temp; + + bool * outside = (bool*)alloca(numPoints*sizeof(bool)); + for( i = 0; i < numPoints; ++i ) + outside[i] = A.GetDistanceToPoint( input[i] ) < 0.0f; + + for( i = 0; i < numPoints; ++i ) + { + int idNext = (i+1) % numPoints; + + // both outside -> save none + if(outside[i] && outside[idNext]) + continue; + + // outside-inside -> save intersection and i+1 + if(outside[i]) + { + if( IntersectSegmentPlane( input[i], input[idNext], A, &temp ) ) + { + output[numOutPoints++] = temp; + interm[numIntermPoints++] = temp; + } + + output[numOutPoints++] = input[idNext]; + continue; + } + + // inside-outside -> save intersection + if(outside[idNext]) + { + if( IntersectSegmentPlane( input[i], input[idNext], A, &temp ) ) + { + output[numOutPoints++] = temp; + interm[numIntermPoints++] = temp; + } + + continue; + } + + output[numOutPoints++] = input[idNext]; + } + *pNumOutPoints = numOutPoints; + return numOutPoints ? true : false; +} + +void CalcHullBounds(const Vector3f* __restrict hullPoints, const UInt8* __restrict hullCounts, UInt8 hullFaces, const Plane& nearPlane, const Matrix4x4f& cameraWorldToClip, MinMaxAABB& aabb) +{ + Vector3f outputData[128]; + Vector3f intermData[128]; + + UInt8 outputDataCounts[64]; + UInt8 intermDataCounts[64]; + + const Vector3f* __restrict inputPoints = hullPoints; + const UInt8* __restrict inputCounts = hullCounts; + + Vector3f* __restrict outputPoints = outputData; + UInt8* __restrict outputCounts = outputDataCounts; + intermDataCounts[0] = 0; + for( UInt8 i = 0; i != hullFaces; ++i ) + { + const UInt8 inputCount = *inputCounts++; + ClipPolysByPlane( inputCount, inputPoints, nearPlane, outputCounts, outputPoints, intermDataCounts, intermData); + inputPoints += inputCount; + outputPoints += *outputCounts; + outputCounts++; + } + + // Project hull's points onto the screen and compute bounding rectangle of them. + Vector3f projectedPoint; + outputPoints = outputData; + outputCounts = outputDataCounts; + + for( int f = 0; f < hullFaces; ++f ) + { + const UInt8 numPoints = *outputCounts++; + for( int i = 0; i < numPoints; ++i ) + { + cameraWorldToClip.PerspectiveMultiplyPoint3( outputPoints[i], projectedPoint ); + aabb.Encapsulate( projectedPoint ); + } + outputPoints += numPoints; + } + + if( aabb.m_Min.x < -1.0f ) aabb.m_Min.x = -1.0f; + if( aabb.m_Min.y < -1.0f ) aabb.m_Min.y = -1.0f; + if( aabb.m_Max.x > 1.0f ) aabb.m_Max.x = 1.0f; + if( aabb.m_Max.y > 1.0f ) aabb.m_Max.y = 1.0f; + +} + + +// Returns our "focused region of interest": frustum, clipped by scene bounds, +// extruded towards light and clipped by scene bounds again. +// +// Frustum is +// { -1, -1, -1 } +// { 1, -1, -1 } +// { 1, 1, -1 } +// { -1, 1, -1 } +// { -1, -1, 1 } +// { 1, -1, 1 } +// { 1, 1, 1 } +// { -1, 1, 1 } + + + +void CalculateFocusedLightHull( const Vector3f* frustum, const Vector3f& lightDir, const MinMaxAABB& sceneAABB, std::vector<Vector3f>& points ) +{ + int i; + Vector3f tempPoints[3][256]; + UInt8 tempCounts[3][128]; + + Plane planes[6]; + planes[0].SetABCD( 0, 1, 0, -sceneAABB.GetMin().y ); + planes[1].SetABCD( 0, -1, 0, sceneAABB.GetMax().y ); + planes[2].SetABCD( 1, 0, 0, -sceneAABB.GetMin().x ); + planes[3].SetABCD( -1, 0, 0, sceneAABB.GetMax().x ); + planes[4].SetABCD( 0, 0, 1, -sceneAABB.GetMin().z ); + planes[5].SetABCD( 0, 0, -1, sceneAABB.GetMax().z ); + + Vector3f* __restrict pData[2] = { (Vector3f*)&tempPoints[0][0], (Vector3f*)&tempPoints[1][0] }; + UInt8* __restrict pDataCounts[2] = { (UInt8*)&tempCounts[0][0], (UInt8*)&tempCounts[1][0] }; + + Vector3f* v = *pData; + UInt8* c = *pDataCounts; + + UInt32 numFaces = 6; + + c[0] = c[1] = c[2] = c[3] = c[4] = c[5] = 4; + v[ 0] = frustum[0]; v[ 1] = frustum[1]; v[ 2] = frustum[2]; v[ 3] = frustum[3]; + v[ 4] = frustum[7]; v[ 5] = frustum[6]; v[ 6] = frustum[5]; v[ 7] = frustum[4]; + v[ 8] = frustum[0]; v[ 9] = frustum[3]; v[10] = frustum[7]; v[11] = frustum[4]; + v[12] = frustum[1]; v[13] = frustum[5]; v[14] = frustum[6]; v[15] = frustum[2]; + v[16] = frustum[4]; v[17] = frustum[5]; v[18] = frustum[1]; v[19] = frustum[0]; + v[20] = frustum[6]; v[21] = frustum[7]; v[22] = frustum[3]; v[23] = frustum[2]; + + + UInt32 numTotalPoints; + UInt32 vIn = 0; + + + Vector3f* intermPoints = &tempPoints[2][0]; + UInt8* intermCounts = &tempCounts[2][0]; + + for( int p = 0; p < 6; ++p ) + { + const Vector3f* __restrict inputPoints=pData[vIn]; + Vector3f* __restrict outputPoints = pData[1-vIn]; + + UInt8* __restrict inputCounts=pDataCounts[vIn]; + UInt8* __restrict outputCounts = pDataCounts[1-vIn]; + + numTotalPoints = 0; + *intermCounts = 0; + + UInt32 faceCount = numFaces; + for( i = 0; i < faceCount; ++i ) + { + const UInt8 numInputPoints = *inputCounts; + if(ClipPolysByPlane(numInputPoints, inputPoints, planes[p], outputCounts, outputPoints, intermCounts, intermPoints)) + { + const UInt8 outputCount = *outputCounts++; + numTotalPoints+=outputCount; + outputPoints += outputCount; + } + else + { + if(0 == (--numFaces)) + break; + } + + inputCounts++; + inputPoints += numInputPoints; + } + vIn = 1-vIn; // anyone for ping-pong ? + + // add an extra face built from all the intersection points so it catches all the edges. + const UInt8 numIntermPoints = *intermCounts; + if(numIntermPoints && (p<5)) + { + numFaces++; + *outputCounts = numIntermPoints; + memcpy(outputPoints, intermPoints, numIntermPoints * sizeof(Vector3f)); + } + } + + if(numFaces) + { // output the clipped points + + Vector3f pt; + Vector3f ld = -lightDir; + points.reserve(numTotalPoints << 1); // worst case scenario + Vector3f* __restrict inputPoints=pData[vIn]; + UInt8* __restrict inputCounts=pDataCounts[vIn]; + + for( i = 0; i < numFaces; ++i ) + { + const UInt8 numPoints = *inputCounts++; + for(UInt8 k=0;k!=numPoints;k++) + { + const Vector3f& v = inputPoints[k]; + points.push_back(v); + if( IntersectLineAABB( pt, v, ld, sceneAABB ) ) + points.push_back( pt ); + } + inputPoints += numPoints; + } + } +} + +void CalculateBoundingSphereFromFrustumPoints(const Vector3f points[8], Vector3f& outCenter, float& outRadius) +{ + Vector3f spherePoints[4]; + spherePoints[0] = points[0]; + spherePoints[1] = points[3]; + spherePoints[2] = points[5]; + spherePoints[3] = points[7]; + + // Is bounding sphere at the far or near plane? + for( int plane = 1; plane >= 0; --plane ) + { + Vector3f pointA = spherePoints[plane*2]; + Vector3f pointB = spherePoints[plane*2 + 1]; + Vector3f center = (pointA + pointB) * 0.5f; + float radius2 = SqrMagnitude(pointA - center); + Vector3f pointC = spherePoints[(1-plane)*2]; + Vector3f pointD = spherePoints[(1-plane)*2 + 1]; + + // Check if all points are inside sphere + if( SqrMagnitude(pointC - center) <= radius2 && + SqrMagnitude(pointD - center) <= radius2 ) + { + outCenter = center; + outRadius = sqrt(radius2); + return; + } + } + + // Sphere touches all four frustum points + CalculateSphereFrom4Points(spherePoints, outCenter, outRadius); +} + +void CalculateSphereFrom4Points(const Vector3f points[4], Vector3f& outCenter, float& outRadius) +{ + Matrix4x4f mat; + + for( int i = 0; i < 4; ++i ) + { + mat.Get(i, 0) = points[i].x; + mat.Get(i, 1) = points[i].y; + mat.Get(i, 2) = points[i].z; + mat.Get(i, 3) = 1; + } + float m11 = mat.GetDeterminant(); + + for( int i = 0; i < 4; ++i ) + { + mat.Get(i, 0) = points[i].x*points[i].x + points[i].y*points[i].y + points[i].z*points[i].z; + mat.Get(i, 1) = points[i].y; + mat.Get(i, 2) = points[i].z; + mat.Get(i, 3) = 1; + } + float m12 = mat.GetDeterminant(); + + for( int i = 0; i < 4; ++i ) + { + mat.Get(i, 0) = points[i].x; + mat.Get(i, 1) = points[i].x*points[i].x + points[i].y*points[i].y + points[i].z*points[i].z; + mat.Get(i, 2) = points[i].z; + mat.Get(i, 3) = 1; + } + float m13 = mat.GetDeterminant(); + + for( int i = 0; i < 4; ++i ) + { + mat.Get(i, 0) = points[i].x; + mat.Get(i, 1) = points[i].y; + mat.Get(i, 2) = points[i].x*points[i].x + points[i].y*points[i].y + points[i].z*points[i].z; + mat.Get(i, 3) = 1; + } + float m14 = mat.GetDeterminant(); + + for( int i = 0; i < 4; ++i ) + { + mat.Get(i, 0) = points[i].x*points[i].x + points[i].y*points[i].y + points[i].z*points[i].z; + mat.Get(i, 1) = points[i].x; + mat.Get(i, 2) = points[i].y; + mat.Get(i, 3) = points[i].z; + } + float m15 = mat.GetDeterminant(); + + Vector3f c; + c.x = 0.5 * m12 / m11; + c.y = 0.5 * m13 / m11; + c.z = 0.5 * m14 / m11; + outRadius = sqrt(c.x*c.x + c.y*c.y + c.z*c.z - m15/m11); + outCenter = c; +} + +void CalculateSpotLightBounds (const float range, const float cotanHalfSpotAngle, const Matrix4x4f& lightMatrix, SpotLightBounds& outBounds) +{ + float sideLength = range / cotanHalfSpotAngle; + outBounds.points[0] = lightMatrix.GetPosition(); + outBounds.points[1] = lightMatrix.MultiplyPoint3( Vector3f(-sideLength,-sideLength, range) ); + outBounds.points[2] = lightMatrix.MultiplyPoint3( Vector3f( sideLength,-sideLength, range) ); + outBounds.points[3] = lightMatrix.MultiplyPoint3( Vector3f( sideLength, sideLength, range) ); + outBounds.points[4] = lightMatrix.MultiplyPoint3( Vector3f(-sideLength, sideLength, range) ); +} + +#if ENABLE_UNIT_TESTS + +#include "External/UnitTest++/src/UnitTest++.h" +#include "Runtime/Math/Random/rand.h" + +SUITE (BoundingUtilsTest) +{ +TEST(BoundingUtilsTest_CalculateSphereFrom4Points) +{ + Rand rnd(123); + for( int i = 0; i < 10; ++i ) + { + Vector3f points[4]; + for( int j = 0; j < 4; ++j ) + { + points[j].x = rnd.GetSignedFloat()*100.f; + points[j].y = rnd.GetSignedFloat()*100.f; + points[j].z = rnd.GetSignedFloat()*100.f; + } + Vector3f center; + float radius; + CalculateSphereFrom4Points(points, center, radius); + for( int j = 0; j < 4; ++j ) + { + float dist = Magnitude(points[j] - center); + float ratio = dist / radius; + // Radius may be large compared to input range, avoid comparing absolute distances + bool correct = (ratio > 0.999f) && (ratio < 1.001f); + CHECK(correct); + } + } +} +} + +#endif |