Shadow projection

<h1>Basic Shadow projection</h1>
written by Phaetos (phaetos@gaffga.de) on 26.03.2003

partially rewritten on 05.04.2003




<div style="background-color: #f0f0f0:">
This is version 2 (Date: 05.04.2003) of this article. It replaces the old one which contained some calculation
errors. I've went through the calculation a few times again and I do hope now that there are no errors
anymore. But if you still find some, please tell me. Thanx!


At this point I want to thank everybody who checked my first-version!


I got some eMails telling me about the errors. You might wonder, why the example program still worked,
but this was due to the fact that both, the program and my hand-written calculations,
were a bit old, and I made the errors when converting my notes to HTML for this article.

</div>


<h2>Introduction</h2>
Well this is basically just another document on how to create projected shadows, but I will show
you how the matrix used to create the shadow projection is correctly derived instead of just showing
how it works. So if you follow carefully my calculations you will completely understand why this
really works


First have a look at the scenario we are going to use: In the following image you see a ray of
light that starts at the light-source L, goes through a point of the shadow-throwing object
P finally reaching its destination in the point P' on the ground plane. The vector
n is the normal vector of the plane.



<table frame="box" border="0" align="left">
<tr><td>
[img]/articles/shadowprojection/fig1.png[/img]

</td></tr>
<tr><td>
<font size="-1">Figure 1: The scenario of the shadow projection</font>
</td></tr></table>

This approach might seem a bit "strange" as we want to create a shadow and not draw all
vertives on the ground, but thats exactly what we need to do. A shadow is mathematically
spoken just a projection of an object onto a plane seen from a light source.

Because nearly every projection can be represented using a matrix, we will now derive
a matrix that does exactly this projection for us. We want a matrix that turns every object
we draw into a shadow of itself.<br clear=all>


We assume the following:



Let L be the position of the light

P the position of a vertex of the object we want to shadow

E a point of the plane (not seen in the figure)

n the normal vector of the plane




The straight that goes from the light source through our point is:

[img]/articles/shadowprojection/1.png[/img]

(this is just the standard straight-formula)





The plane that our shadow will be projected on is:

[img]/articles/shadowprojection/2.png[/img]

(this is the Euler-form of a plane as far is remember the name)





Now we insert the straight formula into the plane formula:

[img]/articles/shadowprojection/3.png[/img]

(so we get the point where the light ray and the plane intersect)





Solving to lambda we get:

[img]/articles/shadowprojection/4.png[/img]





Now we enter lambda into the straight formula from the beginning to get
the shadow point P'

[img]/articles/shadowprojection/5.png[/img]

(P' is now the shadow-projected point. This means if P was a tiny sphere
floating in space, and we would light it using our Light L, we would get a shadow
at the Point P')





We now already have the correct projection, but we still need to turn this into
a matrix. To do so, we split P' into the three coordinates. To make the
notation somewhat easier we define:

[img]/articles/shadowprojection/6.png[/img]
and [img]/articles/shadowprojection/7.png[/img]




These two Variables make it easier now to read the formulas, they serve no other
purpose. Now we use these two additional variables in our current formula:

[img]/articles/shadowprojection/8.png[/img]



We can simplify this a bit more:

[img]/articles/shadowprojection/9.png[/img]

and

[img]/articles/shadowprojection/10.png[/img]

At this point, we can not calculate any further while keeping the vectors, so we
split every vector into its x, y and z coordinate:
[img]/articles/shadowprojection/12.png[/img]

The scalar product can be written as:

[img]/articles/shadowprojection/13.png[/img]

So we get

[img]/articles/shadowprojection/14.png[/img]

Bringing everything to the same denominator:

[img]/articles/shadowprojection/15.png[/img]

Extracting the braces:

[img]/articles/shadowprojection/16.png[/img]

Combining for Px, Py and Pz

[img]/articles/shadowprojection/17.png[/img]

As you remember, a projection is calculated as shown:

[img]/articles/shadowprojection/18.png[/img]



We now have to choose the correct values for the matrix' values. If you
experiment a bit, you'll get it quite fast.


We need to find the corresponding values for the m-values that solve these equations:

(Left side is the matrix-multiplication-form, the right or own formula)

[img]/articles/shadowprojection/19.png[/img]




The solution you should get is:

[img]/articles/shadowprojection/20.png[/img]






I hope this article makes shadow projection somewhat clearer; okay this is really really
basic stuff, but it was not this easy for me to figure out how to calculate the matrix and
maybe there is someone out there who is happy to get one or two hints in the right
direction.



Here you can finally see a screenshot of my example program running:



<table frame="box" border="0" align="left">
<tr><td>
[img]/articles/shadowprojection/proggy.png[/img]

</td></tr>
<tr><td>
<font size="-1">Figure 2: My shadow projection example program</font>
</td></tr></table>
<br clear=all>


I invite you to download my example program here and to experiment a lot with it.
Please note, that this program is written under and for Linux, but it may compile
under Windows with a few adjustments.




Best wishes and happy 3D-ing
<h2>Phaetos</h2>


</body>
</html>

Running perfectly smoothly on my system.
Compiled flawlessly

Great job mate.

Looks like this community is going to scale some real heights

Slightly busy right now. I'll surely play around with the code and have a blast pretty soon

wow!

where are you getting all these from? or do you just have a LOT of spare time

Thank you very much for this wonderful and awesome article. I'm half way through and I am AMAZED. I will finish it today. Thank you!

first, great work! it's awesome!

I would like to make a suggestion for all of us. it's more of an Idea, really.

I consider phateos' article as a teaching article.
I consider nkharrat's article as an informational article.

I have found that lessons taught in parts are "digested" easier and are remembered than lessons given in "whole".

let me use phateos' (awesome) article as an example.

first page:
- intro to topic.
- a list of things that will be covered light, point from object, point on surface and normal vector (L, P, P', and n).
- links to (in this case) vector tutorials.
- links to matrix tutorials
- link to 2nd page.

second page:
- "figure 1"
- maybe another figure depicting real objects, like a flash light for L, a car for P, the shadow of the car for P' and the normal vector
- descriptions as to what role L, P, P`, and n are.
- link to 3rd page

third page
- how to find the X vector
- maybe some easy excersize(s)
- link to the 4th page

fourth page
- properties of a plane
- the role X vector plays
- substitution of X vector into the equation of the plane
- how to solve lambda
- maybe some easy excersize(s)
- link to 5th page

fifth page
- the role of P'
- how to find P'
- review of projection (matrix)
- solutions
- closings
- demos
- the end!

why are we doing it this way? I've noticed that if you provide information on a single "sheet", the reader will take it all in. if a reader doesn't understand a section, the reader will continue reading, granted that there's more information to be read.

by putting in links to the next pages, you force the reader to "digest" what the reader's currently reading. if the reader already understands, the reader can then go to the next page. but for the reader that doesn't quiet understand, they will stay until they do understand.

I am not criticizing, in any way or form, phateos' article - it's an awesome article. I will definitely study it as I will be using shadows in my project. I just wanted to make a suggestion that maybe all of us [whether contributing to this site or elsewhere] to consider the approach mentioned above.

First: Thank you all for your nice replies! I really enjoyed your feedback and most of all:
It really motivates me to write even more!

donBerto: Critics are alway welcome! Thats the only way to improve something! So keep going

Your idea with multiple pages is good. I don't like those really big articles too much, either. But
our software limits us in this way a bit. I already offered Apex to assist in developing new PHP functions.

What do you meant with the examples? I wouldn't find it useful if the current formula was just
filled in with some numbers... The resulting numbers don't give a hint whats going on in the calculation.

Maybe we need a complete article-framework that handles most of the article functionality. So not
every article-writer needs to implement the page-switching, or even style sheets. They all should be
provided by the software. The article author could be provided with an image-upload function so she/he
can set everything online on its own.

Maybe if Apex agrees I will assist in extending the boards functionality.

Greetings
Stefan

I think this article should also be posted in tutorials.

[from nkharrat's post]
I am assuming that apex will take this article and post it in tutorials or articles, wherever.

I imagine that posting an article here in the forums would be VERY restrictive in terms of being able to format completely up to the writer. hopefully phateos and apex can work something out to give a *little* bit of freedom.

in terms of examples/excersizes, something like:

excersize 1:

if vector 
L = <0, 10, 10>,
P = <1, 8, 0>,
P' = <0, 0, 0>

and lambda = 1,

what is X?

something trivial/easy just so the reader can work it out and fully test if the reader really understands.

you can have on the following page detailed solution for further understanding.

something like that...

I have a general knowledge of MySQL/PHP so if you need help on that part, feel free to ask.

Thank donBerto for your suggestion.

I am not sure if you saw the page or not, but check out this link (on the main page):

http://devmaster.net/index.php?showpage=ar...etitle=Articles

and click on Phaetos article. It that was you're talking about? When posting the article on the forum, it is added there in the list automatically. The forum btw, the forum allows html code when posting articles. To post an article, just let me know, and I'll provide the link.

The reason why I integrated all that into the forums is to allow a commenting system where each article has its own thread, instead of manually creating a new thread when an article is submitted.

I'm not sure if I answered your question....

that's one of the things I find most impressive about this site .

I think that you might have got the shadow projection matrix wrong. I multiplied out the matrix with the P vector and I got (Pxnx+Pyny+Pznz-d) for the fourth value. So normalizing the vector means you have to divide by this value. The problem is that you divide by three different values in your equations (Pxnx -d) etc. none of which are the normalizing constant that I got. If I've made a mistake can you show me where I've gone wrong.

I think that you might have got the shadow projection matrix wrong. I multiplied out the matrix with the P vector and I got (Pxnx+Pyny+Pznz-d) for the fourth value. So normalizing the vector means you have to divide by this value. The problem is that you divide by three different values in your equations (Pxnx -d) etc. none of which are the normalizing constant that I got. If I've made a mistake can you show me where I've gone wrong.

I hope I understand you right: You mean you take a Point P = (x y z 1) and you multiply the shadow matrix with it. So you get a vector
where the fourth value is (Pxnx + Pyny + Pznz - d). You expected the fourth value to be 1 or so?
This is no problem. The division is done within OpenGL. OpenGL always normalizes the resulting vector before drawing it. And that is the only way
in matrix projections to incorporate divisions at all...

Or do have problems with the step where I make a matrix out of the formulas? In this case, please tell me a bit more details, so I can help you.

Greetings
Stefan

Here is the shadow matrix used by Direct3D. It has an advantage. If the light's W is 1, it is a point or spot light, if the light's W is 0, it is a directional light. The matrix works for both.

P = normalize(Plane); // normalize() makes sure the normal is a unit vector
L = Light;
d = dot(P, L) // P.a*L.x + ... + P.d*L.w

-P.a * L.x + d *-P.a * L.y * * *-P.a * L.z * * *-P.a * L.w *
-P.b * L.x * * *-P.b * L.y + d *-P.b * L.z * * *-P.b * L.w *
-P.c * L.x * * *-P.c * L.y * * *-P.c * L.z + d *-P.c * L.w *
-P.d * L.x * * *-P.d * L.y * * *-P.d * L.z * * *-P.d * L.w + d

Important! You must transpose this matrix to convert to OpenGL notation.

Oops. Unfortunately, the minus signs are missing in the D3D docs. I edited the text above to include them.

The problem that I have is that you take the projection matrix and multiply with the point P (x y z 1) and you get a new vector that has (Pxnx + Pyny + Pznz - d) as the fourth value. This is of course fine as you now need to normalise the vector. Normalising the vector is done by dividing all of the values by this fourth value. So the P'x value will be

(Px(Lxnx +c) - Lxd - Lxc) / (Pxnx + Pyny + Pznz - d)

instead you have:

(Px(Lxnx +c) - Lxd - Lxc) / (Pxnx - d)

and similar for the P'y and P'z equations.

Aaaaaaahh!!! Thanks mjw599!!

Yes, I found a big error: When splitting the equation for P' into the three coordinates
I have n(P-L) in the denominator where n,P and L are vectors.
Then I do NOT get nxPx-d in the denominator, but nP-d, because nP is the scalar
product of n and P and therefore a number, not a vector. So I get in each
of the three components always the same denominator of nP-d.

I will fix my article as soon as possible.

Thanks you all for reviewing that much detailed! *wow*

Greetings
Stefan

As I just saw, Apex did upload my calculation fix. Thanks Apex!

I hope that the calculation now makes some more sense

Greetings
Stefan

no problem Phaetos; anytime....

the calculations make more sence now

i really like the article! I'm pretty interested in knowing why things work as they do. And so I'm always happy if somebody explains the mathematics behind the scene.

However after splitting the P'-Formula I couldn't follow you anymore. Where you say you're "changing the above Formulas a bit" you seem to do a lot more. To get the new formulas you have to replace n dot P with nx * Px to be able to factor out the Px. I really don't see why you can do that! As n dot P = nx * Px + ny*Py + nz * Pz this would only be correct if Py and Pz are 0. But I don't see why you can assume that?

And another question: Is there a mathematical approach for the puzzle solving? If I've a formula P' = f(P) describing the Projection , how can i set up the matching projection-matrix? There should be one, shouldn't it?

-lith

Please note that due to some errors (shame on me; really!) I replaced the
shadow projection article with a new one which should not contain any errors anymore, because
I have checked the calculation several (!) times.

Thank you all for your replies and I am looking forward to any comments!

Phaetos

Great! Now I can follow easily - everything seems to be alright! Thx alot for this valuable article!

The only question left, which might not be in the scope of your article: Is there a mathematical approach for the puzzle solving? some general algorithm that leads you from the P' = f(P) formula to the matching projection article?

-lith