Clip coordinates problem... or to put it better, the lack thereof.

[Dr_D]

Ok, so I've been following the math on this page, and trying to recreate it all on the CPU, even as will be exponentially slower. I'm not concerened about that, I'm just trying to become a better all around graphics programmer. Anyway, I don't understand exactly how they're handling the clip coordinates. What I'm doing... is simply missing something, as I have vertices that are being projected to infinity, where there is no chance to clip those when they are close to the eye, as they are wildly out of range. Here is some code... if that may help anyone help me. Thanks guys.

Code: [Select]

   dim as single w = any
dim as vec4f pvec  'clip coordinates
dim as vec3f ndvec 'normalized device coordinates

for i as integer = 0 to Model->max_vertices - 1

with model->tvertices[i]
lx = .x
ly = .y
lz = .z
end with

'generating clip coordinates here... doesn't seem quite clear to me...
                'mar() = view matrix * model matrix
with pvec
.x = lx*mar(0) + ly*mar(4) + lz*mar(8) + mar(12)
.y = lx*mar(1) + ly*mar(5) + lz*mar(9) + mar(13)
.z = lx*mar(2) + ly*mar(6) + lz*mar(10) + mar(14)
.w = lx*mar(3) + ly*mar(7) + lz*mar(11) + mar(15)
end with
               
                'just keeping the reciprocal under control...
if pvec.w > 0 then
w = 1f / pvec.w
else
w = 1f
end if

'normalized device coordinates
ndvec.x = pvec.x * w
ndvec.y = pvec.y * w
ndvec.z = pvec.z * w

'screen coordinates calculated now and stored back in model's pvertices array
                'everything is still raw in here for clarity and my own sanity...
                'tscrh = screen width, tscrh = screen height

with model->pvertices[i]
.x = (tscrw * ndvec.x) + (ndvec.x + tscrw)
.y = top-((tscrh * ndvec.y) + (ndvec.y + tscrh))
.z = ((zFar-zNear)/2) * ndvec.z + ((zFar+zNear)/2)
end with
next

[Jim]

It doesn't look like you are actually doing any clipping yet.  Once you're in the clip coordinate space you need to clip the polygons against the view frustum.  That's not shown the on the page you're working from, but it will remove any vertices with a z which lies behind the camera, vertices with a z between the camera and the near clip plane, and vertices which lie a long way from the camera in x,y and z.
Having done that your vertex projection should no longer go out of range.  I think what's happening at the moment is you have some tiny (less than 1) and/or zero or negative z values and some large x,y values which when you do the projection sends it way out of range.
ie.   bigX/tinyZ = overflow

Jim

[hellfire]

Jim pointed out one part of the problem: division doesn't work for w=0.
But you can't project vertices with w<0 either.
Just imagine a polygon crossing w=0, the vertices with w<0 jump over to the other side due to the sign flip.
So there's no way around clipping such polygons at some w>0 using Sutherland-Hodgman *before* dividing by w.

Note that clipping can result in some numerical troubles, too.
Eg when a vertex lies exactly on a frustum-plane, the clipper will produce two identical vertices which make it hard to calculate slopes or texture gradients.

[Dr_D]

Thanks for the links & stuff guys. For the most part, I think I should be able to get away with just clipping to the near plane. I'm not really worried about full frustum clipping... unless I run into more problems later. Theoretically, it should be ok as the triangle functions wont ever allow and out of bounds writing. Anyway, reading about that algorithm helps a lot too. Thanks again guys... if I make anything cool enough I'll post it.

[hellfire]

I'm not really worried about full frustum clipping.

The code of your polyfiller becomes much tighter if you don't have to care about clipping in there.
Discarding invisible polygons is just a bit-operation once you have the clip-flags.
And once your coordinates are guaranteed to be inside the screen it's pretty save to work with integer math.
On the other hand left, right and bottom clipping is basically for free inside the polyfiller.

[Jim]

You may get still away with not clipping exactly, and just culling polygons with vertices outside a larger volume.  PS1, PS2 and PSP do this, and have "guard band" of +-1024 or +-2048 on the screen coordinates where the triangle rasterizer will still work (the scanline renderer can skip the off-to-the-left-pixels with a quick multiply and early-out on the off-to-the-right ones).  Usually this means you have to tessellate your models a little more, so you don't have really 'long' triangles.

<edit>
I'm with Hellfire though, if you clip exactly you have far less things to worry about later.  You know your projection code will work, you know all the triangles lie on screen, so no 2d clipping at all.  That means the really iteration-intensive bit of filling in pixels scanlines needs no 'if' checks in it potentially saving lots of cpu.

Jim

[hellfire]

You may get still away with not clipping exactly, and just culling polygons with vertices outside a larger volume.  PS1, PS2 and PSP do this, and have "guard band" of +-1024 or +-2048 on the screen coordinates

Actually all modern GPUs use this guard-band approach, thus avoiding most of the clipping process.
That's because 3d-clipping creates new vertices which makes memory-prefetching and vertex-caching much trickier.
In a CPU-rasterizer that's not much of an issue, though.
And no matter how large your guard-band is there are always a few polygons left which fall beyond it - so you need the clipping-code anyway...

[Dr_D]

(the scanline renderer can skip the off-to-the-left-pixels with a quick multiply and early-out on the off-to-the-right ones)

Actually, that's what I'm doing now... it does a multiply for pixels off screen to the top as well... it just muls everything by the negative value of y, where y is off screen. There aren't many check in the triangle rsaterizers now, but there are enough to keep someone with my limited asm skills from getting both loops in. That sounds very tempting to totally remove those checks and muls from the triangles. I'm still working, but I have to admit I'm having trouble even getting things clamped to the near plane... or 0, for that matter right now.


Ok... so here's a question with substance. If I clip vertices to the near plane, how do I determine which vertices should actually be drawn from there as anything behind the eye will have a z value of zNear? You mentioned a bit operation. My guess is you're testing if all 3 vertices are behind the eye and then skip that triangle completely if true? I'm using an indexed array setup for this, wavefront(OBJ), so that might not be the best storage method for this method of rendering.

[hellfire]

If I clip vertices to the near plane, how do I determine which vertices should actually be drawn

Let's assume a triangle which crosses the near clipping plane:

The triangle is defined counter-clockwise by 3 vertices (v1,v2,v3).
The vertices v1,v2 are on the positive side of the clipping plane and v3 is outside.

All you have to do is to process each edge:
1. edge (v1,v2)
Both vertices are inside, there's no need to clip.
Just keep the first vertex (v1).
Don't care about the second vertex, it get's processed with the next edge.

2. edge (v2,v3)
One of the vertices is inside, the other one is outside (doesn't matter which one), it needs to be clipped.
The first vertex (v2) is inside, keep it again.
Create a new vertex "n1" (*).

3. edge (v3,v1)
Again needs clipping.
Don't keep the first vertex (v3) because it's outside.
Create a new vertex "n2".

You now have a properly clipped quad (v1,v2,n1,n2).
If your rasterizer processes triangles only, split the quad into two triangles (v1,v2,n1), (v1,n1,n2).

(*)
The new vertices lie on an edge between two vertices v1 and v2.
Any point "n" between the two vertices can be described as
n= v1 + t * (v2-v1)   with t= 0..1
In case of z-clipping you want your new vertex at n.z= nearClip:
nearClip = v1.z + t * (v2.z - v1.z)
=> t= (nearClip-v1.z) / (v2.z - v1.z)

You mentioned a bit operation. My guess is you're testing all 3 vertices are behind the eye and then skip that triangle completely if true?

Yes, that would remove all triangles behind the near clipping plane.
It is more efficient to remove all triangles that are outside of view-frustum, though.
The frustum is build from six planes. For each vertex create a bit-set which tells whether the vertex is beyond any of the planes, eg:

Code: [Select]

TOP = 1
BOTTOM = 2
LEFT = 4
RIGHT = 8
FRONT = 16
BACK = 32
v1.clip = TOP | BOTTOM | RIGHT;
v2.clip = BOTTOM;
v3.clip = BOTTOM | LEFT;To test whether a polygon is out of the frustum just "and" the clip-flags of its' vertices.
It's invisible if any of the bits remains, eg:
v1.clip & v2.clip & v3.clip = BOTTOM
-> the triangle is outside

Since your on-screen-coordinates are all -1..+1 you just have to check whether x/z and y/z are in range which turns out very easy:
x < -z: LEFT
x > z:  RIGHT
y < -z: TOP
y > z: BOTTOM

And it's actually faster to transform all vertices and perform the cliptest in clip-space than trying to cull early with arbitrary planes to save some vertex-transformations.

[Dr_D]

Thanks for the lengthy, detailed response dude. You rock! I had a similar idea, but didn't know if it was even worth going to all the trouble to test. I will have to modify my current system a bit to make it work with edges, as it now uses and indexed vertex system.

[Stonemonkey]

Hi, with the exception of near plane clipping I've mostly used 2d clipping of the triangles which combines nicely with sub pixel accuracy and when removing the clipping but keeping the sub pixel calcs I couldn't find any difference in speed. There is one problem I've always had with this method though that the texturing could jump around a bit on very large (skybox with 2 tris per face surrounding a city) triangles that were clipped to the near plane.