Public Group

Triangle clipping

This topic is 2040 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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?

Edited by belfegor

Share on other sites

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.

Share on other sites

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.

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.

Edited by belfegor

Share on other sites

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.

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.

1. 1
2. 2
Rutin
21
3. 3
4. 4
A4L
15
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 9
• Forum Statistics

• Total Topics
633737
• Total Posts
3013607
×