Clipping in 3D

[Rockthesmurf]

Hi there,


So a question got asked in another thread about how to clip in 3D, so I thought I'd start a thread with a couple of ideas in. Perhaps others will have better ideas, which can be contributed, but if nothing else maybe it'll be a start. Please forgive (and help correct) and mistakes I have made!


So, there are quite a few ways you can clip in 3D, but I'll give a little explanation of a couple of somewhat common ones. Firstly, clipping a sphere in world space, against the camera frustum. Secondly, clipping an axis aligned bounding box in view space.


Generally when clipping you will want to have a bounding volume around each of your render entities. This bounding volume is often a sphere or a axis aligned bounding box. A sphere is useful because it doesn't matter if you rotate your object, the sphere still stays the same. Depending on the object being rendered a box maybe a better (tighter) fit around the entity, but it really does depend on what is being rendered.


Sphere test, in world space, against camera frustum


So, if you have a sphere that fits (as tightly as possible) around each of your entities, the process to determine if the bounding sphere (and therefore the entity contained within) is outside of the camera frustum should be along the lines of:

// Get the bounding data for your element to be rendered.

const BoundsData & bounds = element.GetBounds( );


// Project the center of the bounding sphere into world space

Vector4 worldSpaceCenter = element.GetWorldSpaceTransform( ) * bounds.Sphere.Center;


// Get a pointer to the cameras six clipping planes

const Plane * clippingPlanes = camera.GetClippingPlanes( );


// Flags.

float distance;

bool outSide = false;


// Loop through clipping planes.

for ( int i = 0; i < 6; ++i )

{

    // Work out distance from world space center of sphere to clipping plane

    distance = clippingPlanes[ i ].Normal.DProd( worldSpaceCenter ) + clippingPlanes[ i ].Distance;


    // If the distance is negative the center is on the 'other' side of the clipping plane (so outside the frustum).

    // But if the center is only just outside, there will still be part of the sphere inside. So, we want to make sure

    // it is outside by an amount greater than the radius of the sphere.

    if ( distance < -bounds.Sphere.Radius )

    {

    	// Fully outside, cull.

    	outSide = true;

    	break;

    }

}


if ( ! outSide )

	element.Render( );

Hopefully the code comments explain what is going on, but the pseudo steps boil down to:

• Get center of sphere in world space
  
• Get the distance of the center to each clipping plane
  
• If any of the distances are less than the negative radius of the sphere, the sphere is fully outside of the given the plane therefore should not be rendered
  

​AABB (axis aligned bounding box), in view/clip space







So, if instead of creating a bounding sphere, we create an axis aligned bounding box that tightly fits around our entities. We could go down the route of clipping in view/clip space. Lets dive straight in with some code:

// Get clipping matrix, which is a concatenation of the elements world space transform and the viewProj matrix.

clippingMtx = element.GetWorldSpaceTransform( ) * viewProjMtx;


// Get bounds for element (in local space, as we have concatenated the world matrix to the viewProj).

Vector4 minBounds, maxBounds;

element.GetLocalBounds( minBounds, maxBounds );


// Project min/max bounds into clip space.

Vector4 projectedMinBounds = clippingMtx * minBounds;

Vector4 projectedMaxBounds = clippingMtx * maxBounds;


// Flags.

bool draw = true;


// Check if any of our bounds fall on the 'wrong' side of the screen.


if ( projectedMinBounds.x > projectedMinBounds.w || projectedMaxBounds.x < -projectedMaxBounds.w ||

	projectedMinBounds.y > projectedMinBounds.w || projectedMaxBounds.y < -projectedMaxBounds.w ||

	projectedMinBounds.z > projectedMinBounds.w || projectedMaxBounds.z < -projectedMaxBounds.w )

{

    draw = false;

}


if ( draw )

    element.Render( );

Once again, hopefully the code comments give away most of what is going on, however the actually clip test itself (testing the XYZ's against the W) probably could do with a little more explanation. So, when performing perspective projection (taking 3D objects and working out to get them onto a 2D screen), you have to do the following:

Vector4 projectedPosition = viewProjMatrix * worldSpacePosition;

projectedPosition /= projectedPosition.w;

So after multiplying the world space position by the view projection matrix, you need to perform a homogeneous divide, essentially dividing the X, Y and Z components by the W. This will then give you a screen space position, where the screen goes from -1 to +1 in each axis. As the screen goes from -1 to +1 in each axis, you can find out if the object is off screen by finding out it the 'max' bound of the object (in any dimension, x, y or z) is less than -1, or if they 'min' bounds of the object (again, in any dimension, x, y or z) is greater than +1. But if we look a little more carefully:


projectedPosition.x /= projectedPosition.w;


That is the same as:


projectedPosition.x *= ( 1.f / projectedPosition.w );


And then if we were to clip our projected position (in -1 to +1 space), we'd be checking:


if ( projectedPosition.x < -1) { /* Clip */ }


So if we combine those lines, we get:


if ( projectedPosition.x * ( 1.f / projectedPosition.w ) < -1 ) { /* Clip */ }


Or in more algebraic form:


a * ( 1 / b ) < -1


If we multiply both sides of the equation by b, we get:


a * 1 < -1 * b


Or


a < -b


So if we switch back to our projected position:


if ( projectedPosition.x * ( 1.f / projectedPosition.w ) < -1 )


Multiple both sides by projectedPosition.w


if ( projectedPosition.x * 1.f < -1 * projectedPosition.w )


Or


if ( projectedPosition.x < -projectedPosition.w )


So we end up with a simple of test for if x < -w, so all this work was to show we don't actually need to do X/W, instead we can rearrange the equation to avoid the divide. Why do that? Well just to save on the amount of work we have to do. When rendering a large world, clipping can be rather expensive, so any optimisations that can be made here are always welcome.


The end (at last)


Okay, so maybe that has turned into a load of waffle, but hopefully it gives some basic idea of how to do clipping. There must be millions of hits on Google that will explain it in a much better way, but at least if you ask a question here you'd like to find someone who can help.


Steve

 

[Cloudef]

Hmm, no replies yet? This is pretty handy little piece of information.


Maybe GLES board would been better even that it sin't directly related to OpenGL, but is 3D math anyways.


Also as a tip, I think flipcode has some information about the subject as well, thought they might be quite old articles.


That's where I learned a bit about lightmapping (not the technique, generating them)


Anyways, thank you.

 

[pmprog]

I replied back in the original thread - I'm still struggling to understand it I think I need to find somewhere shallower to enter the 3D pool

 

[sebt3]

I replied back in the original thread - I'm still struggling to understand it I think I need to find somewhere shallower to enter the 3D pool

get used to gl/gles api drawing 2d stuff. At some points the concept behind the api will be clearer. and you will understand this (well that my plan )