Jump to content
  • Advertisement
Sign in to follow this  
belfegor

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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. 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.

Edited by belfegor

Share this post


Link to post
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. 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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!