• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
tguen_03

stencil shadows infinite extrusion

10 posts in this topic

Hi,

recently i learned the stencil algorithm. While studying the algorithm, i came across a question, which i cant answer by myself.
The question is about the extrusion of edges to infinity. For this purpose an infinite projection matrix is used, which looks like this:

2n/(r-l) 0 (r+l)/(r-l) 0
0 2n/(t-b) (t+b)/(t-b) 0
0 0 -1 -2n
0 0 -1 0

Obviously a point (or vector) (x, y, z, w) with w = 0 gets projected by this matrix to a point in clipspace with a maximum z value of 1. Thus this point is somewhere at infinity. Ok so far, so good. My problem is, that i dont understand why the extrusion to infinity is done like in the following code:

[code]in vec4 vertexPosition; // The object-space vertex position.
uniform vec3 mvpMatrix[4]; // The model-view-projection matrix.
uniform vec3 lightPosition; // The object-space light position
void main()
{
float t = (vertexPosition.w < 0.5) ? 1.0 : 0.0;
vec4 extrudedPosition = vec4(vertexPosition.xyz - lightPosition * t, vertexPosition.w);
gl_Position = vec4(dot(mvpMatrix[0], extrudedPosition),
dot(mvpMatrix[1], extrudedPosition),
dot(mvpMatrix[2], extrudedPosition),
dot(mvpMatrix[3], extrudedPosition) );
}[/code]

The code is copied from the book
Mathematics for 3D Programming and Computer Graphics. To understand it you must know, that the vertices which shall get extruded to infinity are marked by a w coordinate of 0.

My question is: Why do we calculate the direction from the light to the vertice and multiply it with the MVP matrix to extrude the vertice.
Ad hoc i would extrude it by calculating.:

vertexPosition.xyz + (vertexPosition.xyz - lightPosition) * BIG_NUMBER

I dont see the extrusion happening. And there is something i dont understand either. As shown above, points with a w coordinate of w = 0 get projected to inifity with a z coordinate of 1. But what if the shadow must be extruded in the direction of the camera, for example if the light is in front of the camera and the object casting a shadow is between the camera and the light. Shouldn't the z coordinate be -1 then?

I hope i could make clear my thoughts to you. I spend hours to find an answer for that, but i could not found anything.
Hope you guys can help me out and make things clear to me.
0

Share this post


Link to post
Share on other sites
Hi, no responses yet.
Is there something unclear about my question ?
I thought it would be no problem to explain this to me, since everyone is using stencil shadows.
So let me know if i something is unclear, i realy must know this : )

Thanks
0

Share this post


Link to post
Share on other sites
First, you must realize the homogeneous vector (x, y, z, 0) corresponds to the point at infinity in the 3D direction (x, y, z).

The extrusion happens in object space, and then both extruded and unextruded vertices are transformed in exactly the same way by the same MVP matrix to get the positions in homogeneous clip space.

When the value of t is 0.0 (because the w coordinate of the vertex is 1.0), then the extruded vertex position does not change, and the new object-space vertex position is (x, y, z, 1.0). When the value of t is 1.0 (because the w coordinate of the vertex is 0.0), then the new object-space vertex position becomes (x - lightx, y - lighty, z - lightz, 0.0), which represents the point at infinity in the direction from the light source to the vertex position. It does not matter that the xyz part of this is not normalized.

[quote name='t_guen03' timestamp='1329321297' post='4913366']
As shown above, points with a w coordinate of w = 0 get projected to inifity with a z coordinate of 1. But what if the shadow must be extruded in the direction of the camera, for example if the light is in front of the camera and the object casting a shadow is between the camera and the light. Shouldn't the z coordinate be -1 then?
[/quote]

Points at infinity in front of the camera and points at infinity behind the camera both get a z coordinate of 1.0 in normalized device coordinates (NDC), after division by the w coordinate. Everything that was behind the camera before projection is actually in front of the camera after projection, but beyond the far plane. See slide 6 of my GDC 2007 talk "Projection Matrix Tricks" for a diagram. You can grab the PDF on this page:

http://www.terathon.com/lengyel/

With an infinite projection matrix, the yellow area above the green NDC box doesn't exist, and the red area above that corresponds to the red area behind the camera before projection. The plane z = 1 in NDC (or z = (f+n)/(f-n) for finite projections) represents both positive infinity and negative infinity at the same time. Think of space as being round and that moving through infinity takes you from positive to negative (or vice-versa) just as moving through zero does.
0

Share this post


Link to post
Share on other sites
Thanks for your reply!

[quote name='Eric Lengyel' timestamp='1329472372' post='4913844']
First, you must realize the homogeneous vector (x, y, z, 0) corresponds to the point at infinity in the 3D direction (x, y, z).
[/quote]

I refreshed my knowledge in projetive geometry and i finally see, why every direction has the similar point in homogenous coordinates. For people who are curious, here is the math:

[quote]
Point Po(x_0,y_0) is a fixed point of the line a.
Suppose, the vector [b]v[/b](a,b) is a direction vector of that line.
Then, for point P different from Po, we have:

P(x,y) is on line a
<=>
There is a real number r such that
x = x_0 + r * a and y = y_0 + r * b
<=>
P has homogeneous coordinates (x_0 + r * a, y_0 + r * b, 1) with r not 0.
<=>
P has homogeneous coordinates
(x_0 / r + a, y_0 / r + b, 1/r)

If r grows infinitely, P recedes indefinitely along that line and the homogeneous coordinates of P approach to (a,b,0).
But (a,b,0) are not the homogeneous coordinates of a point!
Now, we add to the line a one extra point. We call that point 'the point at infinity of the line a' or 'the ideal point of a'.
That special point receives, by definition, (a,b,0) and each real multiple of (a,b,0) as homogeneous coordinates.
[/quote]

Its copied from this great homepage [url="http://home.scarlet.be/math/homog.htm"]http://home.scarlet.be/math/homog.htm[/url]

[quote name='Eric Lengyel' timestamp='1329472372' post='4913844']
Points at infinity in front of the camera and points at infinity behind the camera both get a z coordinate of 1.0 in normalized device coordinates (NDC), after division by the w coordinate.
[/quote]

Then its realy like i thought, but why does the zFail method work if the points at infinity are all mapped to the far plane. I made two sketches to make clear my thoughts.

The first picture shows a scene with a light in front of the camera, a triangle between the camera and the light and a square which gets shadow by the triangle. I also drew the shadow volume how it should be.
[sharedmedia=gallery:images:1775]

The next picture shows the final result in clip space. Thus the point at infinity are mapped to the far plane, the shadow volume is flipped and the square is not shadowed anymore. Where is my error in reasoning?

[sharedmedia=gallery:images:1774]

I would realy appreciate if you or someone else could give me the last peaces of the puzzle.
Thanks!
0

Share this post


Link to post
Share on other sites
Thanks for your reply Goldberg, but these slides doesn't answer my question. Furthermore they dont use the zFail method with a inifite projection matrix. The slides describe another way, where cliping is done at the near plane and conventional zPass method is used.

But there is one thing in common with my problem. They use vectors with w = 0 to extend vertices in one direction. The slides just say, OpenGL is required to draw homogenous coordinates with w = 0 correctly. But what shall this mean. Isn't it only the projection matrix i use, which determines if my vertices are drawed correctly. With the standard projection matrix, homogenous coordinates with w = 0 get mapped to a z coordinate of (f+n)/(f-n), which is >1, thus the vertices shouldn't get drawed correctly. So i don't understand why the slides state they would.

Additionally, at the slides, directions ( vectors with w = 0 ) get extruded in the direction the direction points, but how you can see in my sketches, all directions get only extruded to the far plane and never in the direction to the near plane.

Obviously i am wrong, could someone tell me where ?
0

Share this post


Link to post
Share on other sites
[quote name='t_guen03' timestamp='1329506132' post='4913985']
Thanks for your reply Goldberg[/quote]
You're the first to address to my be my last name only :)
And I've been in these forums since 2006 ;)

[quote name='t_guen03' timestamp='1329506132' post='4913985']With the standard projection matrix, homogenous coordinates with w = 0 get mapped to a z coordinate of (f+n)/(f-n), which is >1, thus the vertices shouldn't get drawed correctly. So i don't understand why the slides state they would.[/quote]
Didn't do the math, but even if the Z coordinate > 1; this means the vertex will be behind the far plane; [b]however[/b] the interpolated values between v0 (which has w = 1) and v1 & v2 (which have w=0) will be inside the viewing frustum.
In other words, think of a giant triangle that extents so far that it reaches some sort of magical portal or black hole at which it stops growing any longer. But, since you can't see anything past that point, you don't care.

Z testing is done at pixel level not vertex level, therefore as long as one vertex is on screen and the other 2 have z > 1; it is most likely that you will still see some sort of triangle. You seem to think that if one of the vertices has z > 1 then the triangle can't be rasterized on screen, it doesn't work like that. First the triangle is interpolated; and if the interpolated pixel has z > 1; [i]only then[/i] will the pixel be discarded.
(I'm assuming you're not using the unreliable [url="http://msdn.microsoft.com/en-us/library/windows/desktop/bb174426%28v=vs.85%29.aspx"]SetClipPlane[/url] method; which shouldn't be needed to get stencil shadowing to work btw)
0

Share this post


Link to post
Share on other sites
[quote name='t_guen03' timestamp='1329493107' post='4913938']
I would realy appreciate if you or someone else could give me the last peaces of the puzzle.
[/quote]

In your last drawing, "ClipSpace", the shaded region should actually be the inverse of what you have. The shadow volume covers everything [i]except[/i] what you've shaded. Think about the normal vectors of the shadow volume's boundary. The normals point out of the shadow volume, but when the shadow volume gets flipped around like that because the camera is inside the extrusion, the normals point into your shaded region, meaning that the shaded region is outside the shadow volume.
0

Share this post


Link to post
Share on other sites
Hi,
thank your for your responses.

[quote name='Matias Goldberg' timestamp='1329533015' post='4914082']
You're the first to address to my be my last name only [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]
And I've been in these forums since 2006 ;)
[/quote]

Yey, im the first one : )

[quote name='Matias Goldberg' timestamp='1329533015' post='4914082']
You seem to think that if one of the vertices has z > 1 then the triangle can't be rasterized on screen, it doesn't work like that.
[/quote]

Yes i realy thought this way, thanks for making this clear.

[quote name='Eric Lengyel' timestamp='1329537803' post='4914096']
The shadow volume covers everything except what you've shaded.
[/quote]

But wouldn't this be false either. The shadow volume would enclose more objects then it should (Ok, in my sketch there is only one object, but if there would be more, then the shadow volume would enclose objects which were originally not shadowed)
The situation gets even worse, when you think about a shadow volume perpendicular to the z axis in eye space.

[sharedmedia=gallery:images:1777]
[sharedmedia=gallery:images:1776]

I wonder, why this behaviour is never mentioned in texts describing stencil shadows. Sketches i saw are just extruding the shadow volumes in eyespace where everything looks fine, but in clipspace i got this mess, where everything goes to the far plane.
0

Share this post


Link to post
Share on other sites
Thanks for your reply Eric.
I finally got it. I didn't consider the hardware which will create the correct vertice if clipping is needed because
-w_c <= z_c <= w_c is not fulfilled.

For people who are curious, here is my solution:

The hardware will find the last Vertice V_l in the direction given by a vector v = (x,y,z,0) starting from a Vertice V_o which is in the view frustrum and will take this Vertice to create the primitive. The Vertice V_l will have a positive w coordinate if v is pointing to the camera, since only then -w_c <= z_c <= w_c can be fulfilled, thus allowing the found point to have a negative z coordinate after the projective division. The Vertice V_l is found by interpolating the values of x,y,z,w on the line from P*V_o and P*v, where P is the projection matrix. The x,y,z values can be interpolated linearly, while the w coordinate gets interpolated by interpolating its reciprocal linearly because it stores the depth. The last Point on the line fullfiling
-w_c <= x_c <= w_c
-w_c <= y_c <= w_c
-w_c <= z_c <= w_c
is then taken.
As a result the extrusion in clipspace is not like in my sketches, but rather like in viewspace and thus correctly done.
I hope its correct what i just wrote : )

Thanks again Eric for your patience and helping me to solve my problem.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0