Triangle clipping

Started by
2 comments, last by iMalc 10 years, 11 months ago

When clipping 1 triangle against 6 planes that enclose a box, i need to determine maximum point count that might come out of it.
So i can do something like this:


#define MAX_CLIPPED_POINT_COUNT ?



struct ConvexPoly

{

    Vec3 points[MAX_CLIPPED_POINT_COUNT];

    int count;

};



...

for each tri

    ConvexPoly cp;

    cp.points[0] = tri.A;

    cp.points[1] = tri.B;

    cp.points[2] = tri.C;



    for each plane

        clipTri( &cp, &cp, &plane );

    


I think that that number is 9? Or can be more?

Advertisement

Yes, assuming you reuse existing points, each clip can only increase the polygon count by one, which occurs when only one point lies on the other side of the plane.

Make sure you clip points in an order where opposite planes are done consecutively. E.g. near, far, left, right, top, bottom

I actually use a technique for clipping that I can't recall where I read about it, as it was many years ago. Basically it uses an array but appends a new copy of the resulting verticies each time it clips to a plane. It's in the same buffer, just after the previous point sequence. Crossing either way over the plane appends a new point, while inside each point is copied, and while outside each point is not copied to the new sequence. This buffer is only local to the clipping code. The original buffer need only hold 3 points, and the output buffer need only hold up to 9 points. It avoids the O(n*n) insertion of points and avoids slow linked lists too. Thus my internal clipping buffer holds up to about 80 points, but that's just cause I use it for clipping quads too.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

Thank you for the tips.

Make sure you clip points in an order where opposite planes are done consecutively. E.g. near, far, left, right, top, bottom

Looks like i already have planes in that relation/order, so i should be fine. biggrin.png

Any particular reason for this?

I have "borrowed" clipTringle function from some library, in the comments they said "Sutherland-Hodgman" algorithm.

I have contacted the author because i have doubts about order of vertices that i will not be able to create triangle-fan poly from its output, and he say it is ok.

I have done some tests it turns out to work fine.

Thank you for the tips.

Make sure you clip points in an order where opposite planes are done consecutively. E.g. near, far, left, right, top, bottom

Looks like i already have planes in that relation/order, so i should be fine. biggrin.png

Any particular reason for this?

I have "borrowed" clipTringle function from some library, in the comments they said "Sutherland-Hodgman" algorithm.

I have contacted the author because i have doubts about order of vertices that i will not be able to create triangle-fan poly from its output, and he say it is ok.

I have done some tests it turns out to work fine.

Yep, that's the name of the algorithm. It actually doesn't work properly if you don't clip opposite sides consecutively. It seems weird at first how it could possibly not work, but when you try it, you notice it occasionally clips out too much, and by trying enough examples, you eventually discover why.

The order of the verticies afterwards should be in either clockwise or anti-clockwise order, whichever order they were originally. You certainly shouldn't put the points out of order as you clip. So it should be fine for a triangle fan afterwards. I actually triangulate right after the clipping, into triangles using the fan approach in my software 3D renderer.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

This topic is closed to new replies.

Advertisement