Sign in to follow this  
supagu

clipping

Recommended Posts

im writing a software rasterizer and its now time to implement some triangle clipping. I've determined if a triangle needs to be clipped if any of its verts are outside of the unit cube. Now, im trying to work out how to generate a clipped polygon
                       . A
                  .   .
            1  .     .
       -----.-----6 .
       | .        |.
     2.|          .5
    .  |         .|
  .    |        . |
 .    3--------.--
............... 4
B               C

note: dots indicate triangle, dashes indicate cube
here is some ascii art of the problem. now, i have worked out how to do this, but the method i've come up with seems rather expensive. start on a triangle vertex, calculate a line segment, eg. AB, see if it intersects with any lines from the cube shown. so we add 1 to a list as there is an intersection. Continue checking for intersections between the line segment 1B, results in 2 being added to the list. Then we calculate the line segment of the cube we intersected with, and follow that around till we get an intersection with the triangle again. This adds point 3 and then 4 to the list. Because we have intersected with the tri again, we start checking for intersections from the line segment 4A, which results in 5 being added to the list ... rinse an repeat till we get back to point 1. this seems rather expensive as every line from the tri needs to be checked with every line of the cube, surely there is a cheaper method than this? this is a bit simplified, as i actually need to clip the tri against a 3d cube, but you should get the idea.

Share this post


Link to post
Share on other sites
I'm not sure, but maybe if you test all lines against a plane at a time, instead of testing a line against all planes at a time, you might be able to reject more points early. I've never done this sort of thing before though, so I could be completely off.

Share this post


Link to post
Share on other sites
First classify every vertex as being inside or outside each clipping edge. Typically you use a bit per edge, so for the 3D case of clipping against a cube you have six bits - a set bit means the vertex is outside the edge. These are usually called "edge flags".

Take your polygon, AND all the edge flags together. If you get a non-zero result, the polygon is trivially rejected, with all the vertices being off one side or the other.

Now OR all the edge flags together. If you get a zero result, the whole thing is visible - no vertices are out of frustum.

Otherwise, you're in a clipping case. The dumb thing is just to clip the polygon against each edge in turn (the Sutherland-Hodgman algorithm). It actually works just fine - few branches to mispredict, simple code, and anyway 99.99% of triangles aren't clipped, so speed isn't that important.

Or you can be cleverer and test multiple edges at once and compare edge codes and so on. I always found that to be a pain, especially knowing when to add in corner vertices.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this