I need some help with a clipping routine for my 3D projection program. Up until now, I have done without clipping, and therefore been able to use a simple structure to hold my polygons like this: float polygon[3][3]; //[vertices][x, y ,z] I have decided not to tessellate the clipped polygons, but make my program able to rasterize polygons with more than three edges. So here is my question: what is the best structure for handling/storing clipped/unclipped polygons? This is what I am thinking: -If all three vertices of a polygon were clipped, the resulting polygon would have a maximum of 6 edges. I could use: float polygon[6][3]; but this would waste memory for polygons that have only 3 vertices. -I could dynamically allocate memory for each polygon, but dynamically allocating memory always seems to slow things waaay down, so I would like to avoid this if possible. So what is the best way to store polygons in memory? I will load polygons from a file, transform them, clip them in world space, convert them to screen space, then rasterize the resulting convex n-gons. Thanks

Is there a practical way to do this with a linked list? or should I use some arranement of structures?

A triangle has 3 vertices before clipping. With each clip plane, you can introduce 1 extra vertex, making it 9 vertices in total. The resultant convex polygon can be represented as a triangle fan if you wish. It may be more efficient to transform the clip planes into mesh space, and clip there? On the PSP I clip in mesh space, but on the PS2 I clip in homogenous space, so it will depend on your situation as to which best suits you.

As for storing the geometry, I only store the clipped polygons temporarily for rendering and I suggest you do the same. You could simply have an array of 18 vertices (9 vertices times 2, because you'll need input and output buffers) as I do.

Hope this helps?

Quote:Original post by Rompa
As for storing the geometry, I only store the clipped polygons temporarily for rendering and I suggest you do the same. You could simply have an array of 18 vertices (9 vertices times 2, because you'll need input and output buffers) as I do.

This here is the problem that I am trying to deal with. When you say store temporarily, do you mean that I should use dynamic memory allocation, using calloc() and then free() or cpp's new and delete[] commands? because I tried that when making my edge list, and the dynamic memory allocation per frame slowed it down to a crawl =/

as far as where to clip, I think what you call mesh space, I all world space. So I think I know what you mean.

That article seemed like one big complicated mess to me... he may be right, but he sure isn't trying very hard to teach anyone else =/

I think I got something out of it though. I have been holding my polys as follows:

__declspec(align(16)) struct POLYGON
{
float vertices[3][3];
float texcoord[3][2];
float normal[3];
bool visible;
};

but it seems that according to this article, I should have all my vertices in one big array, and then simply index them in the POLYGON structure. Is this correct?

struct VERT
{
float x, y, z;
};
struct POLYGON
{
VERT *index_v1, *index_v2, *index_v3;
};
VERT vertices[10000];
POLYGON polygons[3000]

polygons[0].index_v1 = &vertices[0];
polygons[0].index_v2 = &vertices[1];
polygons[0].index_v3 = &vertices[2];

[Edited by - CPPNick on January 18, 2009 1:21:02 PM]

no one? are you serious? I thought this question was really easy...is there anyone here that has actually made a complete commercial 3d game? or is it just a bunch of noobs asking other noobs questions? lol..

I've coded clippers for the PSP and PS2 for commercial games. The location of the temporary "array" of clipped vertices differs depending on the platform, but they're always statically "allocated" as we know the maximum number of vertices that can possibly be generated. There's no reason to use alloc() or anything like that.

I clip into the temporary structure then send the clipped primitives to the render device right then and there (as a triangle fan primitive). You should have very few clipped primitives compared to the rest of the scene if you use the guardband, so the overhead of sending the clipped primitives is generally pretty small unless you're uber low-poly and then fill rate is probably going to be your bottleneck.

Also, I should point out that getting upset with people not responding is probably not going to help your cause. I do this for a living during the day, and as such don't necessarily have time (or even want) to check these forums each day and others are no doubt in the same situation.

It's not necessary to clip all triangles before rasterizing them. So you could just use a static array for temporary storage (e.g. 16 polygons of maximum 9 points).

Also note that you don't have to clip texture coordinates and other vertex attributes. Gradients can be computed using the original camera space vertices, using the 'plane equation' approach. So the clipped polygons can be just x,y,z coordinates.

Quote:...is there anyone here that has actually made a complete commercial 3d game?

Almost everyone actually uses an existing engine or Direct3D/OpenGL for rendering so they don't have to bother about things like polygon clipping. Do you have any specific reason to write a software renderer?

This thread also belongs more in the Graphics Programming and Theory forum, and as Rompa already pointed out it's best to be more patient when asking people to help you for nothing in return...

I'm sorry if I got a little frustrated and cried noob =D

Thanks though guys, I think I know what I'm gonna do now =)
and even though I can program 3 different languages better than my english, this is, sadly, just a hobby. things may change in the distant future, but I can't afford university right now =(


p.s. while we're on topic, I felt that I should share this with you =D