Wednesday April 24, 2024

home | contact | Support | The Maths of 3D You can't have 3D without a little maths...

The Maths of 3D

You can't have 3D without a little maths...

Rasterization : Clipping

by bkenwright@xbdev.net

Its better if we don't render poly's that we can't see. But there are different types of clipping... per object....per triangle...per vertice etc. The main type of clipping that I want to discuss though, is that of slicing! Yup slicing...as when we render our triangles, those that we can't see are just not drawn... but there are dangerous ones ... as we convert our 3D world to our camera world...and its a step away from being rendered to the projection view and onto the screen. But to make things 2D for our screen we must divide by z. But what if z is zero...arggg...a divide by zero....not good. So we have to clip or cut should I say triangles that touch our near z view plane.

As remember our camera or our looking eye is located at 0,0,0...and we are moving the world around us.... it may seem that we are moving around...but in fact we are moving the world around our 0,0,0 point.

So concentrating on the z near clipping plane...... we could just throw triangles away that get to close or are outside a certain distance...but this won't work if where in a room and triangles can represent whole walls. So we determine where it cuts our plane and slice our triangle...either producing one new alternate triangle or two depending how the triangle is cut.

A quick sketch of the problem we have, with a plane representing our near z value:

We really have only two options of clipping when we break down a triangle and its cutting plane..... we just do a simple test to see if its less than or greater than some z value..... keep a count of how many vertices are inside our outside our clipping plane.

After clipping we would have:

For each triangle we need to check if any of the vertices are on the crossing boundaries of our clipping plane...and if all of the vertices are less than our near z clip value, then we don't render the triangle....else if all are within the clipping plane, we render it as normal... but if its laying on the plane...then we must cut it.

Now for simplicity I'm just going to do the near z clipping and maybe later add in clipping for the other planes....which will most likely be at the triangle level, as its we only really have to split triangles if there on the near z plane....those divide by zero errors can be bad!

The code for it isn't really as bad as you might think.... we use the parametric line equation to determine the point on the plane where our 3D line cuts....then using this new value we have our new vertices...

p = v0 + (v1-v0)*t

where t is from 0 to 1

Let me check this...

t=0;

p = v0 + (v1-v0)*0 = v0 + 0 = v0;

t=1

p = v0 + (v1-v0)*1 = v0 + (v1-v0) = v1

But how does this apply to our above situation? Well I guess its not so easy to see the way I've written it...but the x, y and z component can be broken up...and we use the z component to find t....then sub back into the others.

z(t) = z0 - (z1-z0)*t

x(t) = x0 - (x1-x0)*t

y(t) = y0 - (y1-y0)*t

The t value is the same for the 3 equations.... but we solve for z... as the new z value will be the value on the plane! z_near_clip.

Rearrange z(t) so we can find t:

z_near = z0 - (z1-z0)*t

z_near-z0 = (z1-z0)*t

t = (z_near-z0)/(z1-z0);

Use this t value to find our new x and y values on the plane:

x(t) = x0 - (x1-x0)*t

y(t) = y0 - (y1-y0)*t

Hmmmm....well it will look better in code... but I recommend you play around with that parametric equation for a line...its really simple and pops up a lot I find, and can help us out of some tricky situations.

DownloadSourceCode

To demonstrate the clipping code I quickly put together a small demo - again the triangle rendering code is a little buggy as you'll see by the colouring...but the you can easily make out the clipping/slicing of the near z plane as the two triangles rotate.

The code isn't so optimised, as it was done as an exercise/tutorial - but I'm sure with a bit of work you can tweak it here and there to make it run lightening fast, once it clicks how it works.

Why the wacky colours? Well if you choose a solid colour you can't really see the cutting as clear...so I just did different random colours for the four corners of the demo triangles...again you can add in direction shading etc using the dot product or phone lighting models...up to you :) Just didn't want to complicate the code.

Code: DownloadSourceCode

void ClipPolys( stPolys* pPolys, float near_clip_z)

{

stPolys PolysTemp;

PolysTemp.iNumTris = 0;

for(int i=0; i<pPolys->iNumTris; i++)

{

stTri* pCurTri = &(pPolys->pTri[i]);

D3DXVECTOR3* vIn[3];

int iNumVertsIn=0;

bool bV1=false; bool bV2=false; bool bV3=false;

if( pCurTri->v1.z > near_clip_z )

{

iNumVertsIn++;

bV1=true;

}

if( pCurTri->v2.z > near_clip_z )

{

iNumVertsIn++;

bV2=true;

}

if( pCurTri->v3.z > near_clip_z )

{

iNumVertsIn++;

bV3=true;

}

//If iNumVertsIn is zero here, we should reject the whole triangle

/* add later */

if( iNumVertsIn == 1 )

{

if( bV1 ){ vIn[0]=&(pCurTri->v1); vIn[1]=&(pCurTri->v2); vIn[2]=&(pCurTri->v3); }

if( bV2 ){ vIn[0]=&(pCurTri->v2); vIn[1]=&(pCurTri->v1); vIn[2]=&(pCurTri->v3); }

if( bV3 ){ vIn[0]=&(pCurTri->v3); vIn[1]=&(pCurTri->v2); vIn[2]=&(pCurTri->v1); }

//Parametric line stuff

// p = v0 + v01*t

D3DXVECTOR3 v01 = *vIn[1] - *vIn[0];

float t1 = ((near_clip_z - (*vIn[0]).z)/v01.z );

float newz1 = near_clip_z;

float newx1 = (*vIn[0]).x + v01.x * t1;

float newy1 = (*vIn[0]).y + v01.y * t1;

// Second vert point

D3DXVECTOR3 v02 = *vIn[2] - *vIn[0];

float t2 = ((near_clip_z - (*vIn[0]).z)/v02.z );

float newz2 = near_clip_z;

float newx2 = (*vIn[0]).x + v02.x * t2;

float newy2 = (*vIn[0]).y + v02.y * t2;

vIn[2]->x = newx2;

vIn[2]->y = newy2;

vIn[2]->z = newz2;

vIn[1]->x = newx1;

vIn[1]->y = newy1;

vIn[1]->z = newz1;

PolysTemp.pTri[ PolysTemp.iNumTris ] = (*pCurTri);

PolysTemp.iNumTris++;

}

// Two of the verts are outside the clip range, so we need to clip and add

// an extra triangle.

else if (iNumVertsIn == 2 )

{

if( !bV1 ){ vIn[0]=&(pCurTri->v2); vIn[1]=&(pCurTri->v3); vIn[2]=&(pCurTri->v1); }

if( !bV2 ){ vIn[0]=&(pCurTri->v1); vIn[1]=&(pCurTri->v3); vIn[2]=&(pCurTri->v2); }

if( !bV3 ){ vIn[0]=&(pCurTri->v1); vIn[1]=&(pCurTri->v2); vIn[2]=&(pCurTri->v3); }

//Parametric line stuff

// p = v0 + v01*t

D3DXVECTOR3 v01 = *vIn[2] - *vIn[0];

float t1 = ((near_clip_z - (*vIn[0]).z)/v01.z );

float newz1 = near_clip_z;

float newx1 = (*vIn[0]).x + v01.x * t1;

float newy1 = (*vIn[0]).y + v01.y * t1;

// Second point

D3DXVECTOR3 v02 = *vIn[2] - *vIn[1];

float t2 = ((near_clip_z - (*vIn[1]).z)/v02.z );

float newz2 = near_clip_z;

float newx2 = (*vIn[1]).x + v02.x * t2;

float newy2 = (*vIn[1]).y + v02.y * t2;

vIn[2]->x = newx1;

vIn[2]->y = newy1;

vIn[2]->z = newz1;

PolysTemp.pTri[ PolysTemp.iNumTris ] = (*pCurTri);

PolysTemp.iNumTris++;

stTri TriTemp;

TriTemp.v1 = D3DXVECTOR3(newx1, newy1, newz1);

TriTemp.v2 = D3DXVECTOR3(newx2, newy2, newz2);

TriTemp.v3 = (*vIn[1]);

PolysTemp.pTri[ PolysTemp.iNumTris ] = TriTemp;

PolysTemp.iNumTris++;

}

// All the verts are in the triangle - hence the whole triangle is within

// the clip range, and doesn't need clipping.

else if (iNumVertsIn == 3 )

{

PolysTemp.pTri[ PolysTemp.iNumTris ] = (*pCurTri);

PolysTemp.iNumTris++;

}

}// End for loop i

memcpy(pPolys, &PolysTemp, sizeof(stPolys));

}// End of ClipPolys(..)

Of course feedback is always welcome - as I'm always glad to hear of improvements or comments....of sneekier faster algorithms... The code above is pretty simple to follow...we first determine how many verts are in our plane (iNumVertsIn)... then we have a number of choices...if none of them are greater than the near z value...then just skip this triangle...else if we have 3 verts the whole triangle is in the view and no clipping is required.

If 1 vert is inside is greater than z near, then we must re-do our triangle vertices that are outside the plane....sort of recalculate them using our parametric equation. And finally if 2 are greater than our z near plane...then we have to calculate the two new points then fix the vertice values for the current triangle, and add an additional triangle to fill in the gap.

I've used a structure which is a static array of 100 triangle (e.g. stTri[100] )....so you might want to improve upon this if you decide to work with more triangles....also maybe add a dwCLIP variable so you would only have to test and reset the dwCLIP value.

Advert (Support Website)

Visitor: