• Advertisement
Sign in to follow this  

clipping

This topic is 3703 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

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
Advertisement
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
yeah, thats what ive decided to do, as its easy to determine what planes need to be tested so most can be discarded easily :)

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
Sign in to follow this  

  • Advertisement