Clipping, How To? (stuck On Tri's)

[MadDog]

If you download my test app and source your see i've got line clipping working and a very basic polygon clipping working. ( a compiled exe is in the zip for peaple without .net2003 )

ClipTest.zip

The poly clipping code is a nieve attempt, anyone able to do me a simple 'english' how to description?

All the hits in google include loads of 'im cleaver me I can do big math' type showing off. I kid you not, i've seen big equations that although may mean something to a math head all they boil down to in code is an add and an if!


Thanks.

 

[refractor]

If you download my test app and source your see i've got line clipping working and a very basic polygon clipping working. ( a compiled exe is in the zip for peaple without .net2003 )

ClipTest.zip

The poly clipping code is a nieve attempt, anyone able to do me a simple 'english' how to description?

All the hits in google include loads of 'im cleaver me I can do big math' type showing off. I kid you not, i've seen big equations that although may mean something to a math head all they boil down to in code is an add and an if!


Thanks.

The second URL in your source covers it pretty well for me.

All line clipping is doing is working out:

1. If the line is on screen fully (just draw it), off screen fully (ignore it), or partially on.. (damn we have to clip it).
2. For the partially on lines, work out the intersection(s) with the screen borders (or plan borders in 3d). Chop off whichever segment(s) wasn't/weren't on the screen.

That's it. The line intersection is the "hard part" and that's always going to involve maths. There's really no way around that. As the document says, you have two line equations and you have to solve them to find where the meeting is.

The 2d polygon case just extends from the line case. If you can clip a line then by simple extension you can clip a 2d poly.

Ok, for polygons it gets a bit more complicated as you either have to re-triangulate the polys as you have or in the case of an engine that handles n-gon rendering you have to add edges and vertices to the polygon. I.e. a diamond that's clipped by a square suddenly has 8 sides instead of four (though the extra horizontal ones a normal rasterizer wouldn't care about anyway).

In the 3d case you must clip the (now 3d) lines with planes instead but it's exactly the same principle.

Hope that's helped... your question was somewhat vague

(edit :s/half/partially/g)

 

[refractor]

Righty, me again. Looking at your code a bit more, the main thing you're getting wrong is that you're trying to clip the individual lines in the polygon and producing triangles from that.

Instead you should do work your way around the triangle, and when you find intersections with the edge of the screen, add them as extra points (and be careful with corners). That effectively gives you an n-gon instead of a triangle (or set of triangles). Your rasterizer can either deal with that, or it can simply re-split the polygon into triangles by using the new points (if you have hardware that can only play with triangles then, otherwise I'd just rasterize the n-gon).

For example the clipped area that appears when you start your cliptest.exe is incorrect. If you used the two intersections with the border and the top corner as a point then there's your other triangle.

The case where two points are out of the screen rectangle should then work too.

Hope that helped more

 

[MadDog]

Yer, sorry was in a rush when I posted. Had to walk the dog and do the shopping before the football started.

When you run the app up your see one line and a triangle. The line is testing my line code, which is working a treat. The read part shows the resulting line after clipping. All the points of the line and the tri can be dragged with the mouse.

For the tri i'm a bit of a loss as to the best way to structure the code and so create all the triangles needed to represent the clipped version of the orginal.

In this pic your see that there should be three tris to create the clipped version of the orginal but I only get one.
I could keep putting special case code to catch these buts that don't feel correct / best way.

In this next pic my code has got it very wrong, there should be five triangles!

Righty, me again. Looking at your code a bit more, the main thing you're getting wrong is that you're trying to clip the individual lines in the polygon and producing triangles from that.

Instead you should do work your way around the triangle, and when you find intersections with the edge of the screen, add them as extra points (and be careful with corners). That effectively gives you an n-gon instead of a triangle (or set of triangles). Your rasterizer can either deal with that, or it can simply re-split the polygon into triangles by using the new points (if you have hardware that can only play with triangles then, otherwise I'd just rasterize the n-gon).

For example the clipped area that appears when you start your cliptest.exe is incorrect. If you used the two intersections with the border and the top corner as a point then there's your other triangle.

The case where two points are out of the screen rectangle should then work too.

Hope that helped more

Should I be using standard line -> line intersection code and forget about trying to use the line clipping code as a base?

 

[rixed]

Here is a link to my own clipping.

The clipping occurs in 3d space, before drawing. Basically, it clips against as many planes as required, each plane beeing the borders of view frustrum. It adds vertices when needed. Clipping plane after plane greatly simplify things, I think. _and_ you do not have to project the new vertices (at least one coordinate), since you know they are on the frustrum border.

This is very basic, yet efficient enough for me (clipping consume 0% CPU).

http://cvs.gna.org/cvsweb/gpu940/bin/clip....;cvsroot=gpu940

 

[MadDog]

Here is a link to my own clipping.

The clipping occurs in 3d space, before drawing. Basically, it clips against as many planes as required, each plane beeing the borders of view frustrum. It adds vertices when needed. Clipping plane after plane greatly simplify things, I think. _and_ you do not have to project the new vertices (at least one coordinate), since you know they are on the frustrum border.

This is very basic, yet efficient enough for me (clipping consume 0% CPU).

http://cvs.gna.org/cvsweb/gpu940/bin/clip....;cvsroot=gpu940

Wow, that looks top, thanks. I'll have a good look at that later, thanks.

 

[MadDog]

rixed, would I expect that my final code will need to subit created tris against planes yet to test? Mmm, i've got a feeling thats an obvious yes.

From your code I think the method is...

start with zero points in the output data and the three in the input tri.

do trival accept or reject else do clip work as below.

if point[0] in, add it to output.
clip edge point[0] -> point[1] on right, if clipped add new point to output.

if point[1] in, add it to output.
clip edge point[1] -> point[2] on right, if clipped add new point to output.

if point[2] in, add it to output.
clip edge point[2] -> point[0] on right, if clipped add new point to output.

Make new tris from points, resubmit clipping on the top plane, then on the left plane and then last off all the bottom plane. So as we go from one plane to the next the tri count could go up.

Correct simplifcation?

 

[MadDog]

Ok, i've got my clipping working but it seems to create too many triangles. Is this to be expected?

Here is the updated app + code The code is not optimal its mainly done to make it readable. I'm more intrested in optimising the algo before optimising the code. The later can be done when i'm happy with how i'm doing my clipping.

When you run the app up your see two boxes, the left one is the box the tri is being clipped to and the right one is the line clipping test. You can move the points about with the mouse. (click and drag)

I'll be intrested in thoughts about the algo as to me it should not be creating so may polygons.

 

[MadDog]

Ok, back again with a new version of the code + app The code is smaller now, look at the function DrawTriangleClipExample2. The old way I was doing it is still there.

So the new version is more like how it should be done, I don't get excesive triangles. But now if the corner of the clip rect is in the trianlge it misses out a tri. Here is a pic, also explains a bit the display your see if you run the app.

(red lines show the borders of tris that would be rendered)

 

[refractor]

So the new version is more like how it should be done, I don't get excesive triangles. But now if the corner of the clip rect is in the trianlge it misses out a tri. Here is a pic, also explains a bit the display your see if you run the app.

Told ya to be careful with corners

The thing that's missing is which polygon you're following. You're always following the triangle, which means that you'll only get the intersections. You want to instead decide whether to follow the triangle or the clipping region.

So, if you go clockwise around the triangle, then:

if a segment enters the clipping region then add the intersection as a point and continue following the polygon.

if a segment leaves the clipping region then add the intersection and follow the clipping region (also clockwise), adding its points until you find another intersection.

HTH

 

[MadDog]

So the new version is more like how it should be done, I don't get excesive triangles. But now if the corner of the clip rect is in the trianlge it misses out a tri. Here is a pic, also explains a bit the display your see if you run the app.

Told ya to be careful with corners

The thing that's missing is which polygon you're following. You're always following the triangle, which means that you'll only get the intersections. You want to instead decide whether to follow the triangle or the clipping region.

So, if you go clockwise around the triangle, then:

if a segment enters the clipping region then add the intersection as a point and continue following the polygon.

if a segment leaves the clipping region then add the intersection and follow the clipping region (also clockwise), adding its points until you find another intersection.

HTH

I think I understand what your saying, my code was dealing with this. Turns out it was a bug to do with how I represent the edges as a linked list of points. I've tweeked the code so the first point is duplicated at the end of the linked list. Then after the clip process I have to redo this. Its a bit anoying and when I port the code to my gp2x engine i'll be able to take this out with a little short cut. But basicly what was happening was that the last edge was changing if the first edge was clipped. Doh!

Here is an update to the code + app

I've been waiting years to workout how to do clipping. The only software renderer I did on the PC years ago clipped the scan lines (pants). And then 3D hw + DX came along and did it all for me.

And the best thing is that i've got a task for work that needs this kind of clipping to speed up visulation of vast amounts of data, cool, time for a cup of coffee.

 

[rixed]

start with zero points in the output data and the three in the input tri.

(...)

Make new tris from points, resubmit clipping on the top plane, then on the left plane and then last off all the bottom plane. So as we go from one plane to the next the tri count could go up.

Correct simplifcation?

Actually this is simpler than that, because this is not limited to triangles only. I can render polygons with more than n edges so the clip_to_plane function just removes/add some points in the polygon.

If you need to have triangles instead, I suggest you still do clipping on any polygon, and transform the end result to triangle once all clipping is done. That will lead to less triangles also, probably.

 

[MadDog]

Yes, just been playing poker with some mates and one of them sugest that I also do the clip in 3D space as you do. Everything becomes a lot easier. I'll leave that till later, i've moved onto some model code so that I can get something other than cubes on screen.

Thanks for your help.