Saturday April 20, 2024

home | contact | Support | Slice of Java. Its simple and its powerful...

Slice of Java.

Its simple and its powerful...

Clipping - Slicing using a plane

by Ben Kenwright

This is one of my favourite subjects - it really is a simple piece of code when you break it down, and it allows you to do some really cool thing. Imagine any object, a cube, a 3D character etc...well we can use a plane to slice it into two :) Or possibly divide it into separate sections using multiple planes.

The reason its tricky, is that we have a plane, and we have triangles - but the triangle isn't always on one side or the other, usually it crosses our plane! So we have to get our our maths brain, and use a bit of maths magic to slice our triangle along the plane.

But it goes on - we don't get 2 triangles when we slice a single triangle in two....what in fact we get is 3! Well that's if we want to keep the triangles on both sides of our plane.

Cutting a triangle

What we'll do, is develop a simple function, that we can pass in a plane and a triangle, and in return we'll get the divided triangles.

When we have to start working with points and planes, it better if we have a more resonable structure to hold or data. Up to know we've only used a Triangle class to hold or list of triangles. I'll add a further class called 'Vector3' - which holds 3 float values, x,y and z.

When we are passed a triangle, it works like this. We first see if it actually cuts our plane - I mean it could be on either one side or the other, and if it is, it saves us a lot of work. So we use our trusty plane equation (which the dot product can be used for). So we have a boolean variable for each of the 3 points of our triangle... and we determine which are on one side, and which are on the other. So if all 3 are true, then all the points are on the positive side of the plane. If all of them are false, we know that the whole triangle is on the negative side of the plane.

But then if only 1 is on the positive side of the plane, then we have to cut!

So know we know a valuable piece of information. Which is that how many points are on each side of the plane. We've kept count of how many points are on the positve side of our plane. If its 1 or 2, then we clip.

Lets sort our points into some order - we'll have 3 points...pA, pB and pC....with the first points being the points inside the positive side of the plane, and the other's the one's on the negative side of the plane.

If for example, we have only 1 point on the +ve side of the plane, we would have pA as that point. If we have to points on the +ve side of the plane, pA and pB would be those points...starting to get it?...hehe...well its not that bad.

Don't worry, we'll get to the actual code that does all the hard work now :) The hard part of code has been put into a function 'PointOnPlane(..)' which helps us find those two tricky points that cut our triangle. Once we have those two points on our triangle, we can just build up the new triangles that cut the plane.

For each side of the triangle - we have two points...A to B for example. We take these two points and create a ray, which is vRay = B-A; Not so bad... upto know...its this next part that is what does the magic.

Here is a little diagram of whets happening at this point...as a diagram might make picturing this a little easier:

Ray Intersection with Plane

The first thing, we can calculate without to much worry, is angle A. As we have our planes normal (N) and our rays direction pApB. We need both of these to be normalized, so we get the angle only (cosA).

cosA = DotProduct( vnRayAtoB, vnPlaneNormal);

There ya go! It wasn't that painful the first part was it :)

The next part, we need to find the length deltaD. Not sure if my sketch makes it look harder than it is, but we use our might plane equation again to solve for this.

deltaD = DotProduct( vPointOnPlane, vnPlaneNormal) - DotProduct( pA, vnPlaneNormal );

Yup, we have these values, but we still don't' have our intersection point (pX) that you want.....don't worry, where going to solve this now. Take a careful look a the sketch above, and notice what we have now, we have deltaD, A and we need the length of the ray from pA to pX...or more better known as the hypotenuse :)

So remembering our trig days, which for me means 'sohcahtoa' - we have to use cos = adj/hyp....where hyp is our ray length form pA to our pX value.

length = deltaD / cosA;

Ta-da! We only need to do, one further things to get pX. Which is scale a vector normal of the ray from pA to pB.

pX = vnRayAtoB * length;

Hmmm...it does seem like a lot of work, but its not really if you put it into a single function, and call it when you need it. I'm sure there's a lot of optimisation that you could follow through with, like all those calculating of normals and ray direction values - possibly keeping them stored and only needing to use them once...but it made the code easier to explain and debug when I was writing it....you have the power now!

Slicing triangle by plane code:

// Amazing function - it takes a triangle, and a plane, and slices our

// triange..producing the 3 new triangles. Returns 0 if it didn't cut

// the triangle - 1 or 2 depending on how many times it cut the triangle

// on the positive side of the triangle. It uses an array of 3 triangles

// so we can also use the cut triangle(s) for something else incase we

// use this function for something special :)

// Returns 3 for all on the positive side of plane

// Returns 0 for all on the negative side of plane

// Returns 1 for 1 tri tnew[0] on positive side and tri[1] and tri[2] on neg side

// Returns 2 for 2 tri tnew[0] & tnew[1] on pos side and of course tri[2] on neg

int ClipTriangle( Triangle t,

Triangle tnew[],

Vector3 vPointOnPlane,

Vector3 vPlaneNormal )

{

// Checking - not necessary though

vPlaneNormal = Vector3.normalize(vPlaneNormal);

// Clipping

Vector3 p0 = new Vector3( t.tx0, t.ty0, t.tz0 );

Vector3 p1 = new Vector3( t.tx1, t.ty1, t.tz1 );

Vector3 p2 = new Vector3( t.tx2, t.ty2, t.tz2 );

// Okay, lets see if our triangle actually cuts the plane

float k = Vector3.dot( vPlaneNormal, vPointOnPlane );

float a0 = Vector3.dot( vPlaneNormal, p0 );

float a1 = Vector3.dot( vPlaneNormal, p1 );

float a2 = Vector3.dot( vPlaneNormal, p2 );

// Determine how many points are on the positive side of our plane

int iCount = 0;

boolean p0in = false;

boolean p1in = false;

boolean p2in = false;

if( (k - a0)> 0 ){ iCount++; p0in=true; }

if( (k - a1)> 0 ){ iCount++; p1in=true; }

if( (k - a2)> 0 ){ iCount++; p2in=true; }

//System.out.println("iCount = " + iCount );

// If our triangle is fully on one side, or fully on the other side

if( iCount==0) return 3; // All on the positive side on plane

if( iCount==3) return 0; // all on the negative side of plane

// These two vectors will hold the two points on the plane that

// actually cut the triangle.

// For example if we go from PointA to PointB on our triangle,

// and it goes through the plane, the point where A->B cuts the

// plane is called px0 for example.

Vector3 px0 = new Vector3();

Vector3 px1 = new Vector3();

// Now we have the two points on the plane that make

// up the intersection points, that we can construct

// the three new triangles from.

if(iCount==1 )

{

Vector3 pA = new Vector3();

Vector3 pB = new Vector3();

Vector3 pC = new Vector3();

if( p0in ){ pA=p0; pB=p1; pC=p2; };

if( p1in ){ pA=p1; pB=p0; pC=p2; };

if( p2in ){ pA=p2; pB=p1; pC=p0; };

px0 = PointOnPlane( pA /*vStart*/, pB /*vEnd*/,

vPlaneNormal, vPointOnPlane );

px1 = PointOnPlane( pA /*vStart*/, pC /*vEnd*/,

vPlaneNormal, vPointOnPlane );

Triangle t1 = new Triangle( pA, px0, px1, t.tc );

tnew[0] = t1;

Triangle t2 = new Triangle( pB, px1, pC, t.tc );

Triangle t3 = new Triangle( pB, px0, px1, t.tc );

tnew[1] = t2;

tnew[2] = t3;

System.out.println("p0in: " + p0in + " p1in: " + p1in + " p2in:" + p2in );

System.out.println("p0 x:" + p0.m_x + " y:" + p0.m_y + " z:" + p0.m_z );

System.out.println("p1 x:" + p1.m_x + " y:" + p1.m_y + " z:" + p1.m_z );

System.out.println("p2 x:" + p2.m_x + " y:" + p2.m_y + " z:" + p2.m_z );

Triangle ta = tnew[0];

System.out.println("newp0 x:" + ta.x0 + " y:" + ta.y0 + " z:" + ta.z0 );

System.out.println("newp1 x:" + ta.x1 + " y:" + ta.y1 + " z:" + ta.z1 );

System.out.println("newp2 x:" + ta.x2 + " y:" + ta.y2 + " z:" + ta.z2 );

return 1;

}// End if(iCount==1)

// We are here!..so two points are inside our plane

if(iCount==2)

{

Vector3 pA = new Vector3();

Vector3 pB = new Vector3();

Vector3 pC = new Vector3();

//System.out.println("p0in: " + p0in + " p1in: " + p1in + " p2in:" + p2in );

if( !p0in ){ pA=p1; pB=p2; pC=p0; };

if( !p1in ){ pA=p0; pB=p2; pC=p1; };

if( !p2in ){ pA=p0; pB=p1; pC=p2; };

px0 = PointOnPlane( pB /*vStart*/, pC /*vEnd*/,

vPlaneNormal, vPointOnPlane );

px1 = PointOnPlane( pA /*vStart*/, pC /*vEnd*/,

vPlaneNormal, vPointOnPlane );

Triangle t1 = new Triangle( pC, px0, px1, t.tc ); // red

tnew[2] = t1;

Triangle t2 = new Triangle( pB, pA, px0, t.tc ); // dark red

Triangle t3 = new Triangle( pA, px0, px1, t.tc ); // green

tnew[0] = t2;

tnew[1] = t3;

return 2;

}// End if(iCount==1)

return 3;

}// End ClipTriangle(..)

// find the distance between a ray and a plane.

public float distRayPlane(Vector3 vStart,

Vector3 vEnd,

Vector3 vnPlaneNormal,

Vector3 vPointOnPlane)

{

float cosAlpha;

float deltaD;

float planeD = Vector3.dot( vnPlaneNormal, vPointOnPlane );

Vector3 vRayVector = Vector3.subtract(vEnd, vStart);

Vector3 vnRayVector = Vector3.normalize(vRayVector);

cosAlpha = Vector3.dot( vnPlaneNormal, vnRayVector );

// parallel to the plane (alpha=90)

if ( Math.abs(cosAlpha) < 0.001f ) return Vector3.length(vRayVector);

deltaD = planeD - Vector3.dot(vStart, vnPlaneNormal);

float l = (deltaD/cosAlpha);

//float k = Vector3.dot( vnPlaneNormal, vPointOnPlane );

//float a0 = Vector3.dot( vnPlaneNormal, vStart );

//l = (k - a0)/cosAlpha;

return l;

}// End of distRayPlane(..)

public Vector3 PointOnPlane( Vector3 vStart, Vector3 vEnd,

Vector3 vPlaneNormal, Vector3 vPointOnPlane )

{

Vector3 vn = Vector3.subtract(vEnd,vStart);

vn = Vector3.normalize(vn);

float Length = distRayPlane(vStart,vEnd,vPlaneNormal,vPointOnPlane);

Vector3 px = Vector3.scale( vn, Length );

px = Vector3.add( vStart, px );

return px;

}// End of PointOnPlane(..)

The simple demo that shows the possibilities of cutting is shown when we slice a cube down the centre of the screen - I've put a black line on the screen to represent the plane. And the triangles that are cut, and that are on the negative side of the plane are shaded darker than the one's on the positive side. As I'm showing both sides of the plane getting rendered - but later one we'll use this function to clip triangles that try to go behind the camera, into our negative z.

Screenshot of applet:

You can download the full applet code below - which is a single file, clipping.java. You'll probably think its a lot of code - but the code is being designed to keep it as simple as possible, and build reusable parts - such as the 'Vector3' and 'Triangle' class...which have a number of useful functions with them.

The code that uses our Clipping code, is the final rendering stage - what I've done, is call our 'ClipTriangle' function just before rendering, and deteremine if our triangle has been clipped by the plane. If so, I use the triangles that it returns, with altered colour values - so we can see the clipping more clearly.

Applet Source Code - clipping.java (Download Source Code)

....etc....

public void RenderTriangle(Triangle t)

{

Triangle[] tnew = new Triangle[3];

tnew[0] = new Triangle();

tnew[1] = new Triangle();

tnew[2] = new Triangle();

Vector3 vPointOnPlane = new Vector3( 0, 0, 1 );

Vector3 vPlaneDirection = new Vector3( 1, 0, 0 );

int clip = ClipTriangle( t,

tnew,

vPointOnPlane,

vPlaneDirection );

// These many lines are for colour - so we can shade triangles on one side

// of the plane differently than the one's on the other.

Color cOrig = t.tc;

int red = cOrig.getRed();

int green = cOrig.getGreen();

int blue = cOrig.getBlue();

double lo = 0.7;

double hi = 0.8;

int redlo = (int)(red*lo);

int greenlo = (int)(green*lo);

int bluelo = (int)(blue*lo);

int redhi = (int)(red*hi);

int greenhi = (int)(green*hi);

int bluehi = (int)(blue*hi);

Color cOrigLo = new Color(redlo, greenlo, bluelo);

Color cOrigHi = new Color(redhi, greenhi, bluehi);

if( clip == 3 ) // All on the positive side of the plane

{

ScreenPerspective( myImage,

t.tx0, t.ty0, t.tz0,

t.tx1, t.ty1, t.tz1,

t.tx2, t.ty2, t.tz2,

cOrigLo);

}// End if(..)

else if(clip==1) // One triangle is on the positive side of plane

{

tnew[0].tc = cOrig;

tnew[1].tc = cOrigHi;

tnew[2].tc = cOrigLo;

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

{

ScreenPerspective( myImage,

tnew[i].tx0, tnew[i].ty0, tnew[i].tz0,

tnew[i].tx1, tnew[i].ty1, tnew[i].tz1,

tnew[i].tx2, tnew[i].ty2, tnew[i].tz2,

tnew[i].tc);

}// End for loop

}// End else if(...)

else if(clip==2) // Two triangles is on the positive side of plane

{

tnew[0].tc = cOrig;

tnew[1].tc = cOrig;

tnew[2].tc = cOrigLo;

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

{

ScreenPerspective( myImage,

tnew[i].tx0, tnew[i].ty0, tnew[i].tz0,

tnew[i].tx1, tnew[i].ty1, tnew[i].tz1,

tnew[i].tx2, tnew[i].ty2, tnew[i].tz2,

tnew[i].tc);

}// End for loop

}// End else if(...)

else // All on the negative side of the plane

{

ScreenPerspective( myImage,

t.tx0, t.ty0, t.tz0,

t.tx1, t.ty1, t.tz1,

t.tx2, t.ty2, t.tz2,

t.tc);

}// End else(..)

}// End of RenderTriangle(..)

....etc....

So much code for such a simple effect - but just remember its all yours! Its only using a few simple java API's to render things such as pixels. What your learning is how to program in true 3D - and you could always possibly improve upon the code, or apply the principles to DirectX and vertex shaders :) ...so much fun fun fun with code :)

Advert (Support Website)

Visitor: