create a shadow volume

Thanks for sharing, I got to try this asap.

Right now I have an other problem. I tried to write a very
simple solution for the silhouette volume creation. Although
my method is slow, it's nice to see how simple it could be.

Unfortunately there is a probem, that's why I am asking for
help here. Let me explain the method first:

for every triangle in the shadowcaster, two vertex-triangles
(without faces)are created in a temp. shadow volume mesh.
the 2nd tris of them is moved away from the light, by a
pseudo-infinite range. Then the 2 vertex-trs are connected
by 6 triangle faces, covering every potential quad between
the 2 tris.
Now this is a bunch of triangles, especially hen used with
eg. a sphere source mesh.

We also NEED to remove the enclosed triangles to get a
proper silhouette volume that can be used for pseudo-stencil
operations.

So a pivot is positioned just behind the light. Then a
Linepick is performed from the pivot to each Triangle of the
shadow volume. THe Source mesh is also pickable, so this way
(in theory) it will only pick silhouette (edge) triangles.

A further volume mesh is created, containing all
successfully picked tris. These should be only shilhouette
tris.

That's the theory. The linepicks may be slow, but it's so
dead simple that I had to try it.

Now, unfortunately the reality doesn't care too much about
theories, therefor it doesn't work correctly: some tris that
should be detected are missing, and some are detected that
should be fully obscured.

Here's a screenshot:


I really wonder is there a bug in my code (tho I tried to
find one for hours), or is there something wrong with my
theory, or (that's what I guess) is this caused by rounding
errors?

Here's the sourcecode, experimental of course. If anybody
can solve this problem this would be fantastic.

;create shadow volume with the help of Linepick:
;-----------------------------------------------


; make silhouette mesh / shadow volume

; works partially, pretty slow with high poly stuff (linepick exponential slowdown).
; bugous behaviour of PickedTriangle, probably due to rounding errors.

Graphics3D 640,480,32,2
SetBuffer BackBuffer()




Global helper=CreatePivot()

Global infi#=50 ; length shadow volume
Global pick_radius#=0.1 
Global pick_back#=100 ; pick from n behind light
Global divi#=3.0


plane=CreatePlane() ; map
TranslateEntity plane,0,-5,0
EntityColor plane,0,255,0

Global camera=CreateCamera()
TranslateEntity camera,0,0,-12

light=CreateLight()
RotateEntity light,45,45,45

cube=CreateSphere(5) ;CreateCube() ; object to cast shadow
RotateEntity cube,45,45,0
EntityPickMode cube,2

lime=CreateSphere() ; position of light
ScaleEntity lime,0.1,0.1,0.1
PositionEntity lime,4,4,0

volume=make_volume(cube,lime)

RenderWorld()
Text 0,0,TrisRendered()
Flip
WaitKey()
End




Function make_volume(source,lite)
 ; for every triangle create 2 tris in the shadow volume, where one is 
 ; transposed by "infi" in the direction of lightrays
 tri_count=0
 vol=CreateMesh()
 For s=1 To CountSurfaces(source)
  su=GetSurface(source,s)
  su2=CreateSurface(vol)
  For tri=0 To CountTriangles(su)-1
   vx0#=VertexX(su,TriangleVertex(su,tri,0))
   vy0#=VertexY(su,TriangleVertex(su,tri,0))
   vz0#=VertexZ(su,TriangleVertex(su,tri,0))

   vx1#=VertexX(su,TriangleVertex(su,tri,1))
   vy1#=VertexY(su,TriangleVertex(su,tri,1))
   vz1#=VertexZ(su,TriangleVertex(su,tri,1))

   vx2#=VertexX(su,TriangleVertex(su,tri,2))
   vy2#=VertexY(su,TriangleVertex(su,tri,2))
   vz2#=VertexZ(su,TriangleVertex(su,tri,2))
   
   v0=AddVertex(su2,vx0,vy0,vz0)
   v1=AddVertex(su2,vx1,vy1,vz1)
   v2=AddVertex(su2,vx2,vy2,vz2)

   TFormPoint vx0,vy0,vz0,source,0
   PositionEntity helper,TFormedX#(),TFormedY#(),TFormedZ#()

   PointEntity helper,lite
   MoveEntity helper,0,0,-infi
   TFormPoint EntityX(helper),EntityY(helper),EntityZ(helper),0,source
   v0_b=AddVertex(su2,TFormedX#(),TFormedY#(),TFormedZ#())

   TFormPoint vx1,vy1,vz1,source,0
   PositionEntity helper,TFormedX#(),TFormedY#(),TFormedZ#()

   PointEntity helper,lite
   MoveEntity helper,0,0,-infi
   TFormPoint EntityX(helper),EntityY(helper),EntityZ(helper),0,source
   v1_b=AddVertex(su2,TFormedX#(),TFormedY#(),TFormedZ#())

   TFormPoint vx2,vy2,vz2,source,0
   PositionEntity helper,TFormedX#(),TFormedY#(),TFormedZ#()

   PointEntity helper,lite
   MoveEntity helper,0,0,-infi
   TFormPoint EntityX(helper),EntityY(helper),EntityZ(helper),0,source
   v2_b=AddVertex(su2,TFormedX#(),TFormedY#(),TFormedZ#())

   AddTriangle su2, v0  ,v1  ,v1_b
   AddTriangle su2, v0_b,v0  ,v1

   AddTriangle su2, v1_b,v1,v2_b
   AddTriangle su2, v1,v2,v2_b

   AddTriangle su2, v2,v0_b,v2_b
   AddTriangle su2, v2,v0,v0_b

   tri_count=tri_count+6

  Next
 Next
 UpdateNormals vol
 EntityPickMode vol,2
 EntityFX vol,1 
 EntityColor vol,0,0,255
 RotateEntity vol, EntityPitch(source),EntityYaw(source),EntityRoll(source),1


; vol is now a shadow volume, containing the silhouette and a lot of enclosed, hidden tris.

;Return ; you may return here to watch this state...
; -------------------------------


; create a copy without the enclosed tris:


 vol3=CreateMesh()
 su3=CreateSurface(vol3)

 PositionEntity helper ,EntityX(lite),EntityY(lite),EntityZ(lite),1
 PointEntity helper,source,0
 MoveEntity helper,0,0,-pick_back


 ; check the visibility of every triangle of the shadow volume from one step behind the light 
 ; using Linepicks:
 ; only silhouette tris should be pickable here! (since the source mesh obscures inner parts, 
 ; as well as the silhouette tris will do so - at least in theory o_O)

 For i=0 To tri_count-1
  x0#=VertexX(su2,TriangleVertex(su2,i,0))
  y0#=VertexY(su2,TriangleVertex(su2,i,0))
  z0#=VertexZ(su2,TriangleVertex(su2,i,0))

  x1#=VertexX(su2,TriangleVertex(su2,i,1))
  y1#=VertexY(su2,TriangleVertex(su2,i,1))
  z1#=VertexZ(su2,TriangleVertex(su2,i,1))

  x2#=VertexX(su2,TriangleVertex(su2,i,2))
  y2#=VertexY(su2,TriangleVertex(su2,i,2))
  z2#=VertexZ(su2,TriangleVertex(su2,i,2))

  x#=(x0+x1+x2)/divi ; get a triangles interpolated center point
  y#=(y0+y1+y2)/divi
  z#=(z0+z1+z2)/divi

  TFormPoint(x,y,z,vol,0)

  he=helper
  p=LinePick(EntityX#(he),EntityY#(he),EntityZ#(he)  ,TFormedX#()-EntityX#(he),TFormedY#()-EntityY#(he),TFormedZ#()-EntityZ#(he),pick_radius#)

  If (p=vol)
   If PickedTriangle()=i ; did we pick the tris of the corresponding center point?
    v0=AddVertex(su3,x0,y0,z0) ; yes, then it must be a silhouette tris
    v1=AddVertex(su3,x1,y1,z1)
    v2=AddVertex(su3,x2,y2,z2)
    AddTriangle(su3,v0,v1,v2)
   EndIf
  EndIf
 Next

 FreeEntity vol ; release old volume
 vol=vol3
 EntityColor vol,255,0,0
 EntityFX vol,1 Or 16
 EntityAlpha vol,0.5
 RotateEntity vol, EntityPitch(source),EntityYaw(source),EntityRoll(source),1
 Return vol
End Function