PDA

View Full Version : Carmack's reversed vs unreversed



okapota
02-05-2002, 04:25 AM
im now writing the shadow algorithm, and while i think i understand the different methods, im still a bit confused after reading a few posts here on board.
so tell me if thats right -
Carmacks reversed doesnt need near capping, but must have closed volumes. and if my volumes are extended outside the light? should i still use closed volumes?
The unreveresd method needs near capping, but uses open volumes, i.e i should only extend sil edges, right?

LaBasX2
02-05-2002, 04:53 AM
Hi!

Yes Carmack's Reverse uses closed volumes. As far as I know, they always have to be closed. And you don't need any capping. So they are relatively simple to use. The only thing you need to pay attention to is that the shadow volumes don't intersect the far clipping plane but this shouldn't be too hard when you use attenuated lights. I'm using Carmack's Reverse in my engine and it is working perfectly. I have looked into several other shadowing methods but this one is the most simple and at the same time most powerful one I have found.

LaBasX2

ToolTech
02-05-2002, 05:00 AM
Agree. And using the MAC Algo I explained in another thread to close the far plane provides a robust implementation.

vincoof
02-05-2002, 05:02 AM
Yes unreversed algorithm works with opened volumes, and yes you only need to extend the edges. Also, you have to cap on the near clipping plane.

jeppa
02-05-2002, 06:37 AM
what is the difference from closed volumes and
open volumes???



[This message has been edited by jeppa (edited 02-05-2002).]

vincoof
02-05-2002, 07:01 AM
closed volumes are volumes which need to be, huh, closed. Eg each segment of a polygon has a neighbour polygon.

opened volumes are volumes which can contain holes.

For instance, a cube is a closed volume.
If you remove one of its faces (at least), it becomes an opened volume.

Carmack's reversed algorithm does not work with opened volumes, afaik.

dorbie
02-05-2002, 07:15 AM
It is a bit of a myth to say that traditional volumes require no far capping. Typically they should extend far enough to intersect potentially illuminated scene geometry. They WILL cast a false shadow on stuff in the uncapped region if it covers any potentially illuminated geometry as viewed from the eye position.

jeppa
02-05-2002, 07:18 AM
SOrry for my error(what->which).in my engine i use the method described on Nvidia doc(silhouette) .which are the method to make the
closed volumes???

Thanks

vincoof
02-05-2002, 07:41 AM
For silhouettes :
1- determine which polygons are facing light, and which not
2- for each polygon facing the light, every neighbour which is a polygon NOT facing the light means that the segment between the 2 polygons (the polygon facing light, and the neighbour polygon) has to be extended : draw a quad between the "neighbour" segment and the "extended" segment.

For closed volumes, you have to add the volume itself :
1- idem
2- idem
3- for each polygon facing the light, draw the polygon.
4- for each polygon NOT facing the light, draw the "extended" polygon, eg the polygon where all its vertices have been extended like the segment was extended in step 2.

hope this helps

jeppa
02-05-2002, 07:54 AM
many thanks for your help

jwatte
02-05-2002, 11:03 AM
If you're generating the volumes in a vertex shader, by using the cheesy hack of extending vertices with away-facing normals away from the light, couldn't you also use the "min" function to pull the Z component of any transformed vert in hin of the yonder clipping plane? If you compensate a bit for Z buffer resolution and the potential for radial Z buffer, you may get some artifacts where a shadow isn't long enough towards the end of the visible frustum, but that wouldn't be too bad I would think. (Or you'd just pull ALL geometry in to that point, or hide it in fog, or something :-)

okapota
02-06-2002, 05:03 AM
should the volumes be closed on both sides?
if yes, i dont see why. if the viewer doesnt see the ends of the volume, then its like they do not exist, and the shadow should still appear, you see what i mean?

vincoof
02-06-2002, 05:29 AM
volumes have to be closed on both sides because in one pass the "front" sides will be displayed and in the other pass the "back" sides will be displayed.
If you skip some of them, the volume will not be closed and the stencil will be incremented and decremented with a wrong balance.

okapota
02-06-2002, 09:26 AM
are you sure? if thats true, then i have a problem.

PH
02-06-2002, 09:39 AM
okapota,

It's always possible to create a closed volume. Imagine a single triangle - if you use the method shown by vincoof then there won't be any backfacing triangles ( and therefore the shadow volume with not be closed ). To get around this, use the triangles that are front facing wrt. the light, reverse the winding and extrude. The front facing, the extruded faces and the silhouette faces together make up the closed volume ( this method works for all types of geometry ).

okapota
02-06-2002, 10:28 AM
ok, but my problem is with my data structure, anyway ill find a way to get it done. one more thing, in order for backface culling to work the winding for all sil edges should be the same, but if i have a complex model, how can i be sure it is so? beacause it isnt, unless you sort it some how.

PH
02-06-2002, 10:41 AM
All the triangles in your meshes have the same winding ( either CW or CCW for front faces ). So all the extracted silhouette edges are directed. If the extracted edge is AB ( from A to B, this infomation comes from the triangle of which the edge belongs ) and the extended edge is A'B', then the silhouette quad is BAA'B' for CCW. Personally, I create two triangles from the quads.

[This message has been edited by PH (edited 02-08-2002).]

Kaycee
02-07-2002, 12:11 AM
Hmm, in Carmacks reverse dont you always have to close the volume?

If you use the near plane capping method then you only have to make the cap when the near plane intersects the volumes?

Is that right?

And also, doesnt that MAC algorithm eat a lot of fill rate? I guess it wouldnt matter if your game is not fill rate.

okapota
02-07-2002, 02:56 AM
i wish all the triangles in a mesh would have the same winding. but it isnt, what i do now, is going over the sil edges, and sort them, so they will create a loop.

Pentagram
02-07-2002, 03:27 AM
Can you clip your volumes to a box (closing them at the sides of the box) and still get the right result or do they have to have a trapezoid shape (It should work but I want to be shure before implementing box/volume clipping)
(Supposing the box extends further than your visible geometry of course)

ToolTech
02-07-2002, 03:31 AM
The MAC eats only fillrate for those volumes that need to be capped beyond the far plane. Most volumes don't need this. Besides You do not need to do any extra calc for traditional capping.

PH
02-07-2002, 05:19 AM
Originally posted by okapota:
i wish all the triangles in a mesh would have the same winding. but it isnt, what i do now, is going over the sil edges, and sort them, so they will create a loop.

Are you saying that some triangles in your your ordinary models have CW winding order and some CCW order ? If that's the case, then why not just fix the model ? A lot of algorithms rely on using a consistent winding order - not just shadows but a lot of fundamental things.

Paul

okapota
02-07-2002, 05:31 AM
well, yes thats what im saying. i should fix that i guess. my meshes are primitives, brushes, which i generate using the primitive planes, we cut the planes together, and form the triangles from it, ill see what i can do about this. u say that if all my triangles have the same winding, than the sil edges would have the same winding also? hey, thats quiet logical, i guess i should wind my mesh.
now i understand why there is a function for winding polygons in q3Radiant source.
thnx.

okapota
02-07-2002, 05:36 AM
and about drawing the volumes closed, should i render the back facing polys of the model in order to cap the volume, one time unextended with reversed winding, and one time extend with normal winding?
and if so, is it fast enought to use glFrontFace() to reverse the winding, or i should do it in software?

PH
02-07-2002, 05:56 AM
Assume you have a closed shadow volume ( a water tight mesh ) with all faces pointing out, then in the first pass use glCullFace( GL_FRONT ) and in the second pass use glCullFace( GL_BACK ). In each pass you have to draw the entire shadow mesh.

okapota
02-07-2002, 06:49 AM
yes i know, that wasnt my question.
never mind, ill try to what i understand, and see if it works. first ill fix the winding.

vincoof
02-07-2002, 07:25 AM
To my mind, OpenGL does it faster than you could do in software. Because you display the shadow twice, you could save one "front-face computation" pass in software but I don't think it'd be better than OpenGL.
In fact, what I'm saying is that one software cross-product is slower than two hardware cross-products.

Also, I don't know if it's faster to play with glCullFace(GL_BACK/FRONT) or glFrontFace(GL_CW/CCW). IMO, both methods are identical.
But I'd recommend using glCullFace since you're almost certain that you cull back faces by default, whereas it is arbitrary to know if a front face is either CW or CCW.

Kaycee
02-07-2002, 09:32 AM
Let me see if I got this straight.

for Carmack's Reverse
for every object
1. calculate the shadow volume by finding light facing and light backfacing polys
2. close the volume by taking the light facing polys and reversing their winding
3. if shadow volume intersects far plane, cap it by extending light facing polys preserving the original winding and projecting verts onto the far plane

for Non-reverse
for every object
1. calculate the shadow volume by finding light facing and light backfacing polys
2. if shadow volume intersects near plane, cap it by taking light facing polys reversing the winding and projecting their verts onto the near plane

So my question is, isnt the non-reverse method potentially faster? Less fill intensive?



[This message has been edited by Kaycee (edited 02-07-2002).]

Kaycee
02-07-2002, 02:26 PM
Ah I get it now. I finally finished it and I can see that Carmack's reverse is less cpu intensive, since I can avoid intersecting the volume with either the near or far plane. What was throwing me off was having my depth test as GL_LEQUAL, and because of that I was getting the front shadow cap showing up on top of the object. Do you guys use GL_LESS or do you offset the shadow with POLYGON_OFFSET??

Alright now onto beam trees. If anyone is interested I found a link about a shadow bsp
http://www.dca.fee.unicamp.br/~harlen/shadow99.pdf

source and implementation can be found here http://www.dca.fee.unicamp.br/~harlen/

okapota
02-08-2002, 08:23 AM
ok, i guess i got now. just to clarify about the closing of the volumes.
i should render the back facing polygons(from the light) with reversed winding, so they will be seen from out side, and than render the same polys, but extend and with the original winding. thats right?
and that leads me to wonder why hardware volumes isnt better, i think that for models, i will use vertex program volumes.

Kaycee
02-08-2002, 09:20 AM
Close. You do the opposite. The light facing polys are drawn with original winding. Then you extend the light facing polys and reverse winding.

I think if you make use of a beam tree to reduce overdraw of shadows you cant use hardware generated shadows. If you look at the pdf I posted you will see from their experiments that in a highly shadowed scene they had a big speedup. If there isnt too many shadows in the scene then maybe hardware shadow volumes is better.

okapota
02-08-2002, 10:51 PM
i know the method mentioned in your pdf, actually i thought about it myself some time ago, didnt know somebody else did too.
any way, if i close the volumes like you say, it will put the whole object in shadow, wont it? because the object wil be inside the shadow volume like a shadowed object, while some of its faces should be lit.

Kaycee
02-08-2002, 11:22 PM
Thats a problem I had at first too. What you do is draw your shadow volumes with glDepthFunc( GL_LESS ); That way any shadow volume polys in front of your object fail and the stencil gets incremented.

okapota
02-09-2002, 01:06 AM
how can i order the stencil to increment when depth test fails? i thought i should use glDepthFunc(GL_GREATER), and increment stencil when depth pass.

LaBasX2
02-09-2002, 01:25 AM
This is how I am drawing my shadow volumes, using Carmack's Reverse.




glDepthFunc(GL_LESS);
glStencilFunc(GL_ALWAYS, 0, 0xFFFFFFFF);

glClearStencil(0);
glClear(GL_STENCIL_BUFFER_BIT);
glEnable(GL_STENCIL_TEST);

glDisable(GL_TEXTURE_2D);
glEnable(GL_CULL_FACE);

glColorMask(0, 0, 0, 0);
glDepthMask(0);

// Draw shadow volume backfaces
glCullFace(GL_FRONT);
glStencilOp(GL_KEEP, GL_INCR, GL_KEEP);

// ...

// Draw shadow volume frontfaces
glCullFace(GL_BACK);
glStencilOp(GL_KEEP, GL_DECR, GL_KEEP);

// ...


glStencilFunc(GL_EQUAL, 0, 0xFFFFFFFF);
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);

glDisable(GL_CULL_FACE);
glColorMask(1, 1, 1, 1);
glDepthMask(1);


Hope this helps
LaBasX2

Kaycee
02-09-2002, 03:13 AM
Hmm, not sure if the bottom part of your code is right. This is what I do.




glStencilMask(0);
glStencilFunc(GL_NOTEQUAL, 0, 0xFFFFFFFF);
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
glColorMask(1, 1, 1, 1);

glEnable( GL_BLEND );
//draw overlay
glDisable( GL_BLEND );

glDepthMask(1);



EQUAL should be NOTEQUAL. You want to draw the overlay where the stencil is greater than 0. 0 means not shadowed.

Also I sometimes still get artifact shadows ontop of my objects but POLYGON_OFFSET fixed it. Not sure if there is something else that can be done. Anyone know if it is cheaper to just offset the entire shadow volume by the lights direction a tiny bit?

LaBasX2
02-09-2002, 03:39 AM
Hi!

I'm not drawing an overlay but I am drawing the complete geometry again for the lightsource; that's why I need to use GL_EQUAL. Sorry, I forgot to mention that. The code I have posted is working, I have tested it with a whole map and several lightsources.

LaBasX2

okapota
02-09-2002, 07:55 AM
well, i think i finally got it now.
only now i noticed the difference between
glStencilOp(GL_KEEP, GL_INCR_GL_KEEP);
and
glStencilOp(GL_KEEP, GL_KEEP_GL_INCR);
and bothered to check what each does, so now i see it possibile to increment when z fails, instead of passes.

okapota
02-09-2002, 08:35 AM
can you please explain me why this doesnt work -

glClearStencil(0);
glClear(GL_STENCIL_BIT);
glStencilFunc(GL_ALWAYS, 1, ~0);
glEnable(GL_STENCIL_TEST);

glDepthMask(1);
glStencilMask(0);
glStencilFunc(GL_NOTEQUAL, 0, 0xFFFFFFFF);
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
glColorMask(1, 1, 1, 1);
glBlendFunc(GL_ONE,GL_ZERO);
glEnable( GL_BLEND );
//draw overlay
glPushMatrix();
glColor3f(1.0f,0.0f,0.0f);
glLoadIdentity();
glBegin( GL_TRIANGLE_STRIP );
glVertex3f(-0.1f, 0.1f,-0.10f);
glVertex3f(-0.1f,-0.1f,-0.10f);
glVertex3f( 0.1f, 0.1f,-0.10f);
glVertex3f( 0.1f,-0.1f,-0.10f);
glEnd();
glPopMatrix();
glDisable(GL_BLEND);

i dont draw anything, but the quad, and im telling the card to draw only where the stencil is not 0, after i clear to 0. so why is quad gets drawn?? did i forget to enable or disable something?

[This message has been edited by okapota (edited 02-09-2002).]

LaBasX2
02-09-2002, 09:57 AM
I don't know if this is just a typo or a real mistake in your code:

glClear(GL_STENCIL_BIT) must be glClear(GL_STENCIL_BUFFER_BIT);

I can't see anything else that could be wrong at the moment....

@Kaycee:

I'm using perpixel lighting in my engine; everything is realtime. For every lightsource I'm first drawing the shadow and after that the perpixel lighting result. That gives perfect results without any errors that occur normally when you are just drawing an overlay (e.g. shadows passing through walls)

LaBasX2

okapota
02-09-2002, 11:55 AM
well, that was just a typo, so i still dont know what the problem is.
i also draw the shadow for each light, and than the light in unshadowed areas, this way i keep the rendering passes to minimum, but rendering all the lights, and then a quad over the scene to add shadows sound better in some way, because then shadow on shadow is darker, but i should first make this stencil buffer to start working.

Kaycee
02-10-2002, 01:36 AM
This probably isnt your problem but I am just throwing it out there. Whats your stencil mask before you clear the stencil buffer? If the mask is set to 0 then you cannot write to the stencil buffer even with a clear.

Plus you can always read the stencil buffer back and take a look at it to see if its really being cleared.

okapota
02-10-2002, 04:41 AM
no its not that, i forgot to ask a pixel format with stencil bits. http://www.opengl.org/discussion_boards/ubb/smile.gif

okapota
02-10-2002, 06:29 AM
well, now the stencil works, but still, i have a strange problem - when i resize the window, parts of the quad get drawn when it should not. and if specify it to render the quad where stencil is 0 and clear the buffer to zero before drawing the quad, it works, again until i resize the window, after the there artifacts, it draws the quad in different places, without any reason.
do you know this error?

Kaycee
02-10-2002, 10:18 PM
I tried that out with my app and it wasnt happening. Not sure what that could be. Is your viewport reflecting the changes to the window size before you clear?

okapota
02-11-2002, 12:18 AM
i think so, i clear every frame. well i think it has something to do with the mask parameter, becausei changed it, and it stopped.

[This message has been edited by okapota (edited 02-11-2002).]

okapota
02-11-2002, 02:17 AM
i was mistaken, it still happans. its something with the mask parameter. what is it? if i change it to 0, nothing happens, to 1 the artifact is seen. other apps change it to 0xfffff or ~0. what is it?

vincoof
02-11-2002, 02:45 AM
Just my 2c: when you clear the stencil buffer, you have to know how to clear it, eg set the stencil operation.

You do :
glClearStencil(0);
glClear(GL_STENCIL_BIT);
glStencilFunc(GL_ALWAYS, 1, ~0);
glEnable(GL_STENCIL_TEST);

but what's the operation ?
Please try this :
glClearStencil(0);
glClear(GL_STENCIL_BIT);
glStencilFunc(GL_ALWAYS, 1, ~0);
glStencilOp(GL_REPLACE, GL_REPLACE, GL_REPLACE);
glEnable(GL_STENCIL_TEST);

okapota
02-11-2002, 03:39 AM
first, it doesnt work. second why setting the stencilop after clearing?
any way its not that.

vincoof
02-11-2002, 04:14 AM
Right. my mistake.
I thought you drew somthing between glEnable(GL_STENCIL_TEST) and glDepthMask(1)
And if it's the case, you should be using glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP)

Anyway, you have to look at two things :
First of all, make sure you set up a stencil buffer.
You can query how many stencil buffer bits lie in video memory with glGetIntegerv on GL_STENCIL_BITS .
Secondly, as noticed, you have to make sure that the stencil mask is set to 1 at least.

Another thing you could try is replacing glStencilFunc(GL_NOTEQUAL, 0, 0xFFFFFFFF) by glStencilFunc(GL_NEVER, 0, 0xFFFFFFFF)
If it still draw something then either there is no stencil buffer (eg GL_STENCIL_BITS return 0) or your driver/card does not upport stencil testing.

Kaycee
02-11-2002, 10:48 PM
The mask parameter for the stencil buffer is different than the mask parameters for the other buffers. If you want to clear the entire stencil buffer for sure call glStencilMask( 0xffffffff ) or glStencilMask( ~0 ) before glClear(). They are the same. If you only do a glStencilMask( 1 ) then only the first bit will be cleared of each stencil value.

okapota
02-12-2002, 04:04 AM
greate, now it works. many thanx.
but i see now the in the unrevesed method, you still need closed volumes, unless you extend them very very far away,so you cant see the end. because else, you would see a shadow where the shadow volume should be capped. am i right?

Kaycee
02-12-2002, 09:51 AM
Thats right. I think people were saying that when you make your shadows you keep track of the farthest Z wrt to the camera. Then when you draw your shadows you change the projection matrix to make sure the far clip plane is just beyond this z value. You only do this when drawing the shadow volumes tho, that way you dont lose z precision for your other objects.

vincoof
02-12-2002, 10:33 AM
Kaycee : if you're talking about drawing the objects in first pass with a good z precision, and then draw the shadows in second with a bad z precision (with far clipping plane becoming very far) I'm afraid it's not possible. In fact, you can not make matching Z values for two different sets of near/far clipping planes because Z is not mapped linearily in the depth buffer.

Kaycee
02-12-2002, 12:16 PM
That makes sense. I tried it out and the shadows were messed up. Then do I keep track of the Z and draw the whole scene like that? I guess most objects would be culled beyond the original far plane so I wouldnt have to worry about precision for them.

vincoof
02-12-2002, 10:19 PM
You have two cases : either you draw everything (eg objects + shadow volumes) with a "standard" far plane, either you draw everything with a "far" far plane.
In the first case, you'll experience problems with shadow volumes capping, which is both hard and slow to implement.
In the second case, it's easy and fast but you loose Z precision.
You can not combine both methods to take advantage of each because of non-linear Z mapping ; at least I couldn't and cass seem to be confirming that. http://www.opengl.org/discussion_boards/ubb/Forum3/HTML/005442.html

The only other solution is to use the "unreversed" algorithm, which work pretty well with any far plane, and is faster, BUT you have to make sure that your shadowing objects won't project their shadow to the near plane.

[This message has been edited by vincoof (edited 02-13-2002).]

ToolTech
02-13-2002, 12:02 AM
By adding the MAC algorithm explained on http://www.tooltech-software.com you can preserve the z depth and still use the reversed method. You need to draw the shadow volume an extra pass for those volumes that extend beyond the far z plane but this is minor work in most cases..