Polygon Tessellation

[Vincent_M]

Ok, let's say I wanted to create a polygon clipping frustum for my 3D models. I have a the frustum almost created which is constructed based on the projection and view matrices. What would be a good approach to tessellate polygons?

Lets say that I have an array of vertices:

Code: Select all

sVertex vert[99];

and are drawn with GU_TRIANGLES (at the moment). If my frustum plane intersects a polygon, I can get the point(s) of intersection, but what would be a good way of inserting new vertices into my structure? Would I be better off with memory vectors?

[gauri]

Is GE's hardware clipper doing such a bad job you need to clip manually? I suggest you just feed your model to GE and let it handle all the clipping for you.
Or you plan for a software renderer?

[Jim]

You don't clip vertices, you clip triangles. So each triangle which is 3 of those vertices gets clipped and might generate some extra vertices and some extra triangles. So, I guess, if you have 50 vertices, you can start adding extra vertices at the end of that space, 51, 52, etc - just make sure you allocate more space than you need.

Jim

[jean]

Uh...99 vertices?? Inserting points of intersection with frustum? I see you're a little confused. Let's say you have an organization like one of the following:
1) 1 2 3 are the first triangle, 4 5 6 then following and so on...not so good, a gerarchical model should be preferred
2) triangle strip: 1 2 3 are the first triangle, 2 3 4 are the second and so on... a model needs to be stripped offline by particular programs
3) triangle fan: 1 2 3 are the first triangle, 1 3 4 the second, 1 4 5 the third and so on...not to say, this cannot draw a closed 3D surface, so it's unlikely to use only this...

The GPU will clip polys outside frustum and draw halfway polys the right way. If you want to improve performace, you have to implement tricks that don't even feed GPU with not used polys, or feed the least amount of data when it's required to. This last is why strips are used sometimes on GPUs that explicitly support them.
On the other side, the only algorithm that would REALLY improve sorting/culling /collision-checking a structure is BSP (or portal rendering, or my BubbleTree algorithm i'm so proud of...;) ) BUT believe me, it's a real mess. If i didn't understand the point, and your models are really made up of polys so large that tasselation is needed, you can do it offline with some modeling program or apply LOD techniques, but -again- it's not so easy. Try googling around.

jean

[Insert_witty_name]

The GPU will clip polys outside frustum and draw halfway polys the right way.

That's not really what it does.

If 2 or more points of a triangle are outside the frustum, it will be clipped by the GPU.

Obviously this is not ideal.

You need to ideally clip your triangles before this in camera space.

Google for Sutherland-Hodgman clipping.

Lots of into about clipping issues in this thread: http://forums.ps2dev.org/viewtopic.php?t=2961

[jean]

If 2 or more points of a triangle are outside the frustum, it will be clipped by the GPU.

Really?????????? X|
Sorry if i told nonsenses, but i'm used to "real" GPUs...i sometime work with openGL under win32, and there a poly is culled off the frustum only if ALL the vertexes are outside of it (that makes more sense) and drawn on screen otherwise. If some vertexes are in and some other out, then fragments (data resulting from rasterization) are discarded or not depending on 2D projection coordinates.
I guess sony's choice to discard even polys with one point inside frustum could be configurable if we got the commercial sdk. Otherwise, the only thing we could do to avoid turning off hw frustum culling and implement our is to wide the frustum (again i assume that -like in traditional openGL - camera FOV is independant for frustum culler planes) and draw smaller polygons.

[Jim]

I don't know how the PSP hardware works, but on PS1 the hardware could 'early out' of a 2d triangle that went over the right or bottom of the screen - it would just stop drawing spans at the right, and stop rasterizing at the bottom, so you got 2d clip for free. But at the left and top, the rasterizer had to iterate over the scans and pixels to do the 2d clip, so it was just as expensive as drawing it, except without actually drawing any pixels.

Jim

[jsharrad]

If you find it hard to visualize the explaination in IWN's link because the image is gone, this may be helpful:

http://emergencyexit.untergrund.net/200 ... -clipping/

McZonk explains how it works pretty well and some ideas on how to get around it.

[Vincent_M]

Is GE's hardware clipper doing such a bad job you need to clip manually?

Yeah, there are some major issues with polygon clipping here. A frustum will be needed.

You don't clip vertices, you clip triangles. So each triangle which is 3 of those vertices gets clipped and might generate some extra vertices and some extra triangles. So, I guess, if you have 50 vertices, you can start adding extra vertices at the end of that space, 51, 52, etc - just make sure you allocate more space than you need.

I meant to say triangles. The idea of adding extra space to my vertex array sounds promising. I need to establish a good vertex strip system though. I'm not sure what I should do there because different .x file plug-ins organize the indices of the vertices differently, and take different amounts of vertices to make the shape. Some are more optimized than others...

1) 1 2 3 are the first triangle, 4 5 6 then following and so on...not so good, a gerarchical model should be preferred
2) triangle strip: 1 2 3 are the first triangle, 2 3 4 are the second and so on... a model needs to be stripped offline by particular programs
3) triangle fan: 1 2 3 are the first triangle, 1 3 4 the second, 1 4 5 the third and so on...not to say, this cannot draw a closed 3D surface, so it's unlikely to use only this...

This, along with creating a frustum is exactly what I'm after. =) I was not sure what I should do first, so I've been asking around first before I start writing up how everything should work. Like I said though, different .x file exporters spit out different versions of how to organize and use vertices. For different applications.

Here is a pretty good example from the Panda 3D .X Exporter:

Code: Select all

36; // number of vertices
0.000000, 0.000000, 0.000000;, // vertex data
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;,
0.000000, 0.000000, 0.000000;;

8; // number of faces
3;0,1,2;, // the first "3;" means that there are 3 indices for this face...
3;3,4,5;, // ...and the numbers following that are the indices
3;6,7,8;,
3;9,10,11;,
3;12,13,14;,
3;15,16,17;,
3;18,19,20;,
3;21,22,23;,
3;24,25,26;,
3;27,28,29;,
3;30,31,32;,
3;33,34,35;;

I just wrote that off the top of my head. The vertex positions are all 0.0f, 0.0f, 0.0f because I couldn't remember what they were in an .x file, and I'm not home right now. Still, that is how the data is represented in an .x file for a box when exporting unoptimized vertex data. I added in the comments; they usually wouldn't be there. The vertex indices are in this order when put in an index array:

Code: Select all

0 1 2
3 4 5
6 7 8
9 10 11
12 13 14...

I wish the algorithm went as follows:

Code: Select all

0 1 2
1 2 3
2 3 4
3 4 5
4 5 6
5 7 8

I have found a way to optimize the vertex data, so that I could delete many vertices in the list, and still get the same results (my texture coordinates may be wrong though).

On the other side, the only algorithm that would REALLY improve sorting/culling /collision-checking a structure is BSP (or portal rendering, or my BubbleTree algorithm i'm so proud of...;) ) BUT believe me, it's a real mess. If i didn't understand the point, and your models are really made up of polys so large that tasselation is needed, you can do it offline with some modeling program or apply LOD techniques, but -again- it's not so easy. Try googling around.

Yeah, I wanted to add some sort of node-tree system such as a bsp tree later on, and just apply my triangle clipping too just the node my camera is in since that is the only node that will be rendered (or will it?). I've got some pretty big polygons. I was aiming for really low-poly modeling. The sad thing is that I had to add hundreds of extra vertices to my floors in 3ds Max to tessellate my floors and walls. Just about any polygon will be clipped depending on how close you get to it. If I get that frustum knocked out, I it will take a lot of processing power to transform the frustum with the camera and clip those vertices, but the good news is that I can use way less vertices in my objects, and the biggest part will be that I won't have disappearing triangles.

You need to ideally clip your triangles before this in camera space.

Google for Sutherland-Hodgman clipping.

I've looked into that, but I was not sure on how to add vertices to my array. I could add extra space in my arrays during load-time like Jim has suggested. The Sutherland-Hodgman algorithm looks promising, but I still have to get those frustum planes up and running first. I know I have to multiply my view and projection matrices together into a resultant matrix, but what is the order exactly? I think Raphael said that matrices were put together in this fashion:

PROJ*VIEW*MODEL

He also mentions that the matrices are multiplied in a right-to-left order. Is that how gumMatrixMultiply() works as well:

Code: Select all

mat a: matrix on the left
mat b: matrix on the right
mat b X mat a

@jsharrad: Thanks for the link. The frustum solution is exactly what I am trying to implement. I did not want to actually tessellate my polygons until there were a lot, but clip them at the edges of the screen, and thus making it possible to cut the guard-band down to the screen size + a 1-pixel tolerance on each side just in case. That might help speed-wise as well, but I have not tested it because the frustum isn't built yet.

This raises some important questions:

-How many extra vertices should be good?
Some polygons may be so huge that none of the vertices would be inside the screen so I would have to add four vertices, and then link them together with some sort of index algorithm I cannot even begin to think of. Then, there I would have to come up with the texture coordinate solution too. I wouldn't have an idea on how to get vertex normals set up either. I think there is a simple algorithm to set those up though.

Should I figure out how to arrange my vertices with a stripping algorithm before I move into frustum culling?

-Vertex array size?
I should make my vertex array bigger than normal for the extra vertices, but I don't know... I don't want to send extra vertices to be drawn when they should not even be used. Of course, they won't be sent if I use an index buffer that doesn't have any indices that correspond to them, right?[/code]

[Vincent_M]

Just another question to bump this up a bit: would frustum clipping be kind of processor-heavy? Even if it was, I would still really want to add that in because it clips the polygons well, and it would eliminate the need for a guard band.