3D Clipping

[Goz]

Hi all!

Im suffering from complete mind failure at the moment and am trying to figure out what is going wrong with my 3D clipping system of quads. I am clipping against a frustum completely in world space. I work out my view frustum by multiplying the view and projection matrices together and extracting the planes as follows.

void BuildViewFrustum( const Matrix44& view, const Matrix44& proj, Vector* pFrustum )
{
Matrix44 combMat;

Matrix44::Multiply( &combMat, view, proj );

// Right clipping plane (+x)
pFrustum[0] = Vector( (combMat._03 - combMat._00),
(combMat._13 - combMat._10),
(combMat._23 - combMat._20),
(combMat._33 - combMat._30) );

//Left Clipping Plane (-x)
pFrustum[1] = Vector( (combMat._03 + combMat._00),
(combMat._13 + combMat._10),
(combMat._23 + combMat._20),
(combMat._33 + combMat._30) );

// Top clipping plane (+y)
pFrustum[2] = Vector( (combMat._03 - combMat._01),
(combMat._13 - combMat._11),
(combMat._23 - combMat._21),
(combMat._33 - combMat._31) );

// Bottom clipping plane (-y)
pFrustum[3] = Vector( (combMat._03 + combMat._01),
(combMat._13 + combMat._11),
(combMat._23 + combMat._21),
(combMat._33 + combMat._31) );

// Far clipping plane (+z)
pFrustum[4] = Vector( (combMat._03 - combMat._02),
(combMat._13 - combMat._12),
(combMat._23 - combMat._22),
(combMat._33 - combMat._32) );

// Near clipping plane (-z)
pFrustum[5] = Vector( (combMat._03 + combMat._02),
(combMat._13 + combMat._12),
(combMat._23 + combMat._22),
(combMat._33 + combMat._32) );
}

I call the clipping as follows ...

vStack[0] = *pVert0;
vStack[1] = *pVert1;
vStack[2] = *pVert2;
vStack[3] = *pVert3;
vStack[0] = *pVert0;

uNumVerts = ClipToPlane( vStack, vFrustum[5], uNumVerts );
uNumVerts = ClipToPlane( vStack, vFrustum[4], uNumVerts );
uNumVerts = ClipToPlane( vStack, vFrustum[3], uNumVerts );
uNumVerts = ClipToPlane( vStack, vFrustum[2], uNumVerts );
uNumVerts = ClipToPlane( vStack, vFrustum[1], uNumVerts );
uNumVerts = ClipToPlane( vStack, vFrustum[0], uNumVerts );

At which point my stack should contain a tri-fan that is ready for rendering. My clip function is

u32 ClipToPlane( Vector* pVecStack, const Vector& plane, u32 uNumVerts )
{
Vector vStack[12];
u32 uOutputVerts = 0;

u32 uCount = 0;
u32 uMax = uNumVerts;
while( uCount < uMax )
{
Vector v0 = pVecStack[uCount + 0];
Vector v1 = pVecStack[uCount + 1];

Vector vDiff = v1 - v0;
f32 fDir = Vector::dot3( vDiff, plane );
f32 fDot0 = Vector::dot3( v0, plane );

f32 t = (-plane.w - fDot0) / fDir;

if ( t > 1.0f || t < 0.0f )
{
// Line does not cross the plane.
// Is it inside or outside the plane?
if ( (fDot0 - plane.w) > 0 )
{
vStack[uOutputVerts + 0] = v0;
uOutputVerts++;
}
}
else
{
Vector vNew = v0 + (t * vDiff);
if ( fDir > 0 )
{
vStack[uOutputVerts + 0] = v0;
vStack[uOutputVerts + 1] = vNew;
uOutputVerts += 2;
}
else
{
vStack[uOutputVerts + 0] = vNew;
uOutputVerts++;
}
}

uCount++;
}

// Rebuild stack for return.
uCount = 0;
uMax = uOutputVerts;
while( uCount < uMax )
{
pVecStack[uCount] = vStack[uCount];
uCount++;
}

pVecStack[uCount] = vStack[0];

return uOutputVerts;
}

Im convinced the mistake im making is simple but i just cannot spot what i am doing wrong. Anyone got any ideas?

PS: I know its a bit crap posting up my code but my mind is really not working very well on this. Any ideas will be much appreciated!

[Nick]

I work out my view frustum by multiplying the view and projection matrices together and extracting the planes as follows.
Shouldn't that be the inverse view and projection matrices?

In normalized screen space (i.e. right after the projection matrix), frustum corners are (1, 1, 1, 1), (-1, 1, 1, 1), (1, -1, 1, 1), (-1, -1, 1, 1), (1, 1, -1, 1), (-1, 1, -1, 1), (1, -1, -1, 1), (-1, -1, -1, 1) (*). So back-transforming them by first multiplying with the inverse projection matrix, then the inverse view matrix, gives the frustum corners in world space. Divide x, y, z by w. You can then use them to construct frustum planes, which requires a cross and dot product (and care for orientation). Maybe it can be simplified a lot, but your approach seems a little too simple at first look.

Your clipping algorithm is also a bit odd. I basically do it like this:

Vector T[16]; // Newly clipped polygon
int t = 0;

for(int i = 0; i < numVertices; i++)
{
int j = i == numVertices - 1 ? 0 : i + 1; // Next vertex index

float di = plane.distance(V[i]);
float dj = plane.distance(V[j]);

if(di >= 0) // Inside
{
T[t++] = V[i];

if(dj < 0) // Outside
{
T[t++] = V[i] + di / (di - dj) * (V[j] - V[i]);
}
}
else
{
if(dj > 0) // Inside
{
T[t++] = V[i] + di / (di - dj) * (V[j] - V[i]);
}
}
}

I hope this helps. If not, try to systematically verify every step. This is a little too much code to verify at once. Try to visualize the frustum planes. Try clipping with a very simple plane and a very simple polygon and verify every coordinate.

Good luck!

(*) OpenGL conventions

[Goz]

Well i've used that method of extracting frustum planes for dp3 culling tests many times in the past. I kinda assumed it would work for clipping ... but maybe im wrong ...

I tried your clipping method (though I assumed that "float dj = plane.distance(V[i]);" was a typo (V[i] should be V[j]). I get exactly the same errors. So maybe you are right about my plane calculations ... Bummer.

I will keep looking at it ...

[Nautilus]

// You can use this to extract the 6 Frustum planes from
// your VP[4,4] matrix.
//
// The planes built here:
// - are not normalized.
// - face the inside of the Frustum.
//
// (D3D convention)

// Left Plane.
Left.a = VP._14 + VP._11;
Left.b = VP._24 + VP._21;
Left.c = VP._34 + VP._31;
Left.d = VP._44 + VP._41;

// Right Plane (mirror of Left Plane).
Right.a = -Left.a;
Right.b = -Left.b;
Right.c = -Left.c;
Right.d = -Left.d;

// Lower Plane.
Lower.a = VP._14 + VP._12;
Lower.b = VP._24 + VP._22;
Lower.c = VP._34 + VP._32;
Lower.d = VP._44 + VP._42;

// Upper Plane (mirror of Lower Plane).
Upper.a = -Lower.a;
Upper.b = -Lower.b;
Upper.c = -Lower.c;
Upper.d = -Lower.d;

// Near Plane.
Near.a = VP._13;
Near.b = VP._23;
Near.c = VP._33;
Near.d = VP._43;

// Far Plane.
Far.a = VP._14 - VP._13;
Far.b = VP._24 - VP._23;
Far.c = VP._34 - VP._33;
Far.d = VP._44 - VP._43;

[Goz]

Well cheers guys ... turns out nearly all my problems were caused by messing up my front face/back face check (am clipping shadow volumes on the CPU). My clipping code, while a bit retarded above, did work fine after a bit of thought had been applied to it :) A good night's sleep is so helpful sometime ;)

For the record: My, and Nautilus's, method of extracting the frustum planes is working perfectly :)

[Nils Pipenbrinck]

I wrote some stuff about that a couple of years ago:

http://www.cubic.org/docs/3dclip.htm

It's rather cryptic as I haven't really understood all non obvious details back than (e.g. 10 years ago), but anyways, the code does a pixel perfect clipping (I've used and cut'n'pasted it more than once).

These days I'd do it all in homogenous coordinates, in a unit cube, but basically the same math applies.

Nils

[Nick]

By the way, you can speed this up a little by computing the distance of all vertices to the plane beforehand by placing them in an array. Now you're doing two dot products per edge.

It's also useful to delay the division until you actually have to clip the edge.