shadow volumes

shadow volumes

Post by j » Mon, 14 Jul 2003 03:15:04



hi,

to calculate the shadow-volume of a
sphere generated by a pointlight, I now
calculate "by hand" the circumference
of the sphere in the plane with the normal
( centersphere - lightposition ) and project
that circle onto the floor, each vertex
projected away from the lightposition.

I have the distinct feeling that this can be
done much more efficiently, by generating
a projection matrix that does the same job
for a standard-sized cylinder located at the
position of any sphere. say:
Vshadow = Mshadow * Msphere * Vcylinder
where
Vcylinder is a vertex of the standard-sized cylinder
Msphere is the 4x4 transformationmatrix of the sphere
Mshadow is the unknown projection matrix
Vshadow is a vertex of the shadowvolume
* is either Matrix-Matrix or Matrix-Vector multiplication

Unfortunately, Im not much of a mathwiz, I might
be able to figure it out eventually, but maybe its
already available and perhaps someone has something
similar just lying around, I'd love to hear from you...

thanks,

J

--
reply to J at dynamica dot org
"The first principle is that you must
not fool yourself - and you are the
easiest person to fool" -- R.Feynman

 
 
 

shadow volumes

Post by GAbriele Svel » Mon, 14 Jul 2003 23:37:39


You can find a description on how to solve your camera-inside-shadow volume here:

 - http://developer.nvidia.com/view.asp?IO=robust_shadow_volumes

and a Vertex Shader based implementation here:

 - http://www.gamasutra.com/features/20021011/lengyel_01.htm

 
 
 

shadow volumes

Post by Just d' FAQ » Tue, 15 Jul 2003 01:00:12




Quote:>Unfortunately, Im not much of a mathwiz, I might
>be able to figure it out eventually, but maybe its
>already available and perhaps someone has something
>similar just lying around, I'd love to hear from you...

Would it help if I tell you the shadow cone will have radius r at
distance sqrt(||C-L||^2 - r^2) along its center line? Where L is the
position of the light, C the center of the sphere, and r the sphere
radius. The center line of the cone is, as you noted, parallel to C-L.

From that you can write an equation for the cone. Then you can take
the data for the plane and find the conic of intersection. If you're
lucky that shadow will be an ellipse; however you can also get highly
elongated shadows in the shape of a parabola or hyperbola if the plane
is tilted enough with respect to the cone. Since these last two cases
are unbounded regions, the shadow areas are infinite. You can also get
degenerate cases; the ellipse can shrink to a point, and the hyperbola
can become a wedge.

<http://id.mind.net/~zona/mmts/miscellaneousMath/conicSections/conicSe...>

Conics have been popular every since Apollonius of Perga.

<http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Apollonius.html>

Search the web and you will find an abundance of material to help you.

 
 
 

shadow volumes

Post by j » Tue, 15 Jul 2003 19:54:29


thanks, I love parabolae too. This was however
not my question. Im sorry, it appears I was unclear.
I've got the volumetric shadow-casting implemented
according to the Carmack-MJK email and it works
beautifully. Im now optimising the volume-calculations.

Quote:>I have the distinct feeling that this can be
>done much more efficiently, by generating
>a projection matrix that does the same job
>for a standard-sized cylinder located at the
>position of any sphere. say:

I meant to say, it should be possible to derive from
the position and radius of a sphere with the
position of the lightsource a matrix that transforms
a 'unit' capped cylinder in such a way that the
transformed cylinder is indentical to the shadow
volume of a sphere with the top-cap going through
the center of the sphere, scaled to it's diameter
and oriented in the plane with normal ( light - sphere )
the lower cap should be coplanar and below the actual 'floor'
that eventally catches the shadow. Degenerate cases can be
avoided by f.i. restricting the lightsource to be above the actual floor
and a minimum distance away from the surface of the sphere. In
my case this wouldnt be a problem at all. If such a matrix can be derived,
the shadowvolume for a sphere can be stored in a display list and
transformed
by the matrix which we have to calculate. right now, I'm 'hand-calculating'
every vertex which is too slow and worse, compared to the beauty of
'Carmack's reverse' ( no pun intended ) it is sloppy.

thanks,

Jonathan

-------------------------------------------------------------
  please tear the sticker off my eddress before use
-------------------------------------------------------------




> >Unfortunately, Im not much of a mathwiz, I might
> >be able to figure it out eventually, but maybe its
> >already available and perhaps someone has something
> >similar just lying around, I'd love to hear from you...

> Would it help if I tell you the shadow cone will have radius r at
> distance sqrt(||C-L||^2 - r^2) along its center line? Where L is the
> position of the light, C the center of the sphere, and r the sphere
> radius. The center line of the cone is, as you noted, parallel to C-L.

> From that you can write an equation for the cone. Then you can take
> the data for the plane and find the conic of intersection. If you're
> lucky that shadow will be an ellipse; however you can also get highly
> elongated shadows in the shape of a parabola or hyperbola if the plane
> is tilted enough with respect to the cone. Since these last two cases
> are unbounded regions, the shadow areas are infinite. You can also get
> degenerate cases; the ellipse can shrink to a point, and the hyperbola
> can become a wedge.

<http://id.mind.net/~zona/mmts/miscellaneousMath/conicSections/conicSe...
.htm>

- Show quoted text -

Quote:

> Conics have been popular every since Apollonius of Perga.

> <http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Apollonius.html>

> Search the web and you will find an abundance of material to help you.

 
 
 

shadow volumes

Post by Just d' FAQ » Wed, 16 Jul 2003 00:35:49



>I've got the volumetric shadow-casting implemented
>according to the Carmack-MJK email and it works
>beautifully. Im now optimising the volume-calculations.

>>[snip]

>I meant to say, it should be possible to derive from
>the position and radius of a sphere with the
>position of the lightsource a matrix that transforms
>a 'unit' capped cylinder in such a way that the
>transformed cylinder is indentical to the shadow
>volume of a sphere with the top-cap going through
>the center of the sphere, scaled to it's diameter
>and oriented in the plane with normal ( light - sphere )
>the lower cap should be coplanar and below the actual 'floor'
>that eventally catches the shadow. Degenerate cases can be
>avoided by f.i. restricting the lightsource to be above the actual floor
>and a minimum distance away from the surface of the sphere. In
>my case this wouldnt be a problem at all. If such a matrix can be derived,
>the shadowvolume for a sphere can be stored in a display list and
>transformed
>by the matrix which we have to calculate. right now, I'm 'hand-calculating'
>every vertex which is too slow and worse, compared to the beauty of
>'Carmack's reverse' ( no pun intended ) it is sloppy.

I have already given everything you need to know to describe a cone.
If you want to slice it at the sphere silhouette, that plane is

  (L-C).(P-C) - r^2 = 0

where, again, L is the position of the light, C is the sphere center,
and r its radius. P is the point to be tested. The radius of the cap
circle is

  r*sqrt(1 - r^2/||L-C||^2)

and it is centered at distance

  r^2/||L-C||

from the sphere center.

Ordinarily the surface of a shadow volume is polygonal, with the near
cap formed by backfaces and the far end at infinity (or far clip). I
did not recognize this in your question, and still am not sure quite
what you expect to do.

In any case, I have given you enough information to derive a matrix
that warps a cylinder to the shape of your shadow cone, if that's what
you really want to do.

 
 
 

shadow volumes

Post by j » Wed, 16 Jul 2003 01:10:16


Thanks for your elaborate answer,
either Im so thick I dont know it, or we're
talking past eachother. Geometrically, I see
exactly what you're saying and this is what I
have implemented now, with what I call handfeeding
the vertices. I really dont see how I could work
this information into a 4x4 matrix, which brings
us back to my original query.

J

--
-------------------------------------------------------------
  please tear the sticker off my eddress before use
-------------------------------------------------------------



> >I've got the volumetric shadow-casting implemented
> >according to the Carmack-MJK email and it works
> >beautifully. Im now optimising the volume-calculations.

> >>[snip]

> >I meant to say, it should be possible to derive from
> >the position and radius of a sphere with the
> >position of the lightsource a matrix that transforms
> >a 'unit' capped cylinder in such a way that the
> >transformed cylinder is indentical to the shadow
> >volume of a sphere with the top-cap going through
> >the center of the sphere, scaled to it's diameter
> >and oriented in the plane with normal ( light - sphere )
> >the lower cap should be coplanar and below the actual 'floor'
> >that eventally catches the shadow. Degenerate cases can be
> >avoided by f.i. restricting the lightsource to be above the actual floor
> >and a minimum distance away from the surface of the sphere. In
> >my case this wouldnt be a problem at all. If such a matrix can be
derived,
> >the shadowvolume for a sphere can be stored in a display list and
> >transformed
> >by the matrix which we have to calculate. right now, I'm
'hand-calculating'
> >every vertex which is too slow and worse, compared to the beauty of
> >'Carmack's reverse' ( no pun intended ) it is sloppy.

> I have already given everything you need to know to describe a cone.
> If you want to slice it at the sphere silhouette, that plane is

>   (L-C).(P-C) - r^2 = 0

> where, again, L is the position of the light, C is the sphere center,
> and r its radius. P is the point to be tested. The radius of the cap
> circle is

>   r*sqrt(1 - r^2/||L-C||^2)

> and it is centered at distance

>   r^2/||L-C||

> from the sphere center.

> Ordinarily the surface of a shadow volume is polygonal, with the near
> cap formed by backfaces and the far end at infinity (or far clip). I
> did not recognize this in your question, and still am not sure quite
> what you expect to do.

> In any case, I have given you enough information to derive a matrix
> that warps a cylinder to the shape of your shadow cone, if that's what
> you really want to do.

 
 
 

shadow volumes

Post by Just d' FAQ » Wed, 16 Jul 2003 05:01:26



>Thanks for your elaborate answer,
>either Im so thick I dont know it, or we're
>talking past eachother. Geometrically, I see
>exactly what you're saying and this is what I
>have implemented now, with what I call handfeeding
>the vertices. I really dont see how I could work
>this information into a 4x4 matrix, which brings
>us back to my original query.

OpenGL has a GLU facility for cylinders that actually allows the two
ends to have different radii. I suspect you could use that directly.
But if not, you could might do a transform on such a cylinder to get
the cone segment you want. I'd have to think about whether you can
send one end off to infinity, if you really need that.

As I understand it, what you need to do is render this cone into the
stencil buffer twice, once for front-facing counts and again for back.
Calling gluCylinder "draws a frustum of a cone centered on the Z axis"
of a given height and with top and bottom radii. I've given you the
bottom radius; and I don't know what height will suffice, but I gave
the information needed to calculate the top radius from the height.
Now all you need is a matrix to rotate and position it. Is that your
obstacle? But you know where to translate the origin, the center of
the bottom circle; namely, to the near circle center. And the FAQ will
tell you how to first rotate to aim the Z axis as needed.

  "Subject 5.26:  How can I aim a camera in a specific direction?"
  <http://www.faqs.org/>

Otherwise I have no idea what you intend with this 4x4 matrix you keep
looking for!

 
 
 

shadow volumes

Post by j » Wed, 16 Jul 2003 17:10:41


got it.

Mark J. Kilgard has written an example called nvshadow(.zip)
where he constructs just such a matrix I was looking for.

<snip>
  /* Given: the light source position (L), the cut-out origin (O), the
     cut-out Y direction (N), the cut-out X direction (M), the ground
     plane equation, compute five points in world space to project the
     cut-out space volume into. */
  computeShadowVolume(L, O, M, N, Pbg, P);

  /* Generate a volume projection matrix from the five points in world
     space. */
  constructShadowVolumeMatrixd(P, matrix);

/* Construct a shadow volume matrix.  The code below was generated by Maple.
   The code implements an inlined 15x15 matrix inverse for the special case
   we are interested in.  No guarantees if this code is numerically stable,
   but it is good enough for nvshadow and pretty fast.

   Consult the "Reconstruction" chapter of Michael Penna and Richard
   Patterson's book _Projective Geometry and its Applications to Computer
   Graphics_ (Prentice-Hall, 1986) for more details. */
</snip>

The point being able to construct a shadowvolume-display-list ONCE,
( a 'unit' cylinder as the shadowvolume of a sphere, f.i. ) then transform
through the matrix that is to be constructed each frame so as to align it
with the shadowvolume as it would be calculated. Beats the hell out of
calling any glu-functions with all its goniometrics.

Thanks though.

J

--
-------------------------------------------------------------
  please tear the sticker off my eddress before use
-------------------------------------------------------------



> >Thanks for your elaborate answer,
> >either Im so thick I dont know it, or we're
> >talking past eachother. Geometrically, I see
> >exactly what you're saying and this is what I
> >have implemented now, with what I call handfeeding
> >the vertices. I really dont see how I could work
> >this information into a 4x4 matrix, which brings
> >us back to my original query.

> OpenGL has a GLU facility for cylinders that actually allows the two
> ends to have different radii. I suspect you could use that directly.
> But if not, you could might do a transform on such a cylinder to get
> the cone segment you want. I'd have to think about whether you can
> send one end off to infinity, if you really need that.

> As I understand it, what you need to do is render this cone into the
> stencil buffer twice, once for front-facing counts and again for back.
> Calling gluCylinder "draws a frustum of a cone centered on the Z axis"
> of a given height and with top and bottom radii. I've given you the
> bottom radius; and I don't know what height will suffice, but I gave
> the information needed to calculate the top radius from the height.
> Now all you need is a matrix to rotate and position it. Is that your
> obstacle? But you know where to translate the origin, the center of
> the bottom circle; namely, to the near circle center. And the FAQ will
> tell you how to first rotate to aim the Z axis as needed.

>   "Subject 5.26:  How can I aim a camera in a specific direction?"
>   <http://www.faqs.org/>

> Otherwise I have no idea what you intend with this 4x4 matrix you keep
> looking for!