create a shadow volume

hello!
i have got a question about stencil shaodwing!
i managed to make a stencil buffer demo, but now i have to make a function which creates shadow volumes on the fly!
how can i do that?
note: the shadow volume should only be created with the mesh edges, and not with the whole polygons of the mesh, because it wont work ;)

should look like this:

First let me say I'm not an expert in stencil shadows, not at all.
A simple solution is to clone the vertices of the mesh and move the clones away from the origin in the direction of the lights rays.
Although this will use all vertices, something you don't want, as you said. Depending on the way you are doing the stencil shadows this method may work noless.

Finding the mesh edges may require a lot of calculations that will slow down things remarkably. Probably it would be easier to use a lowpoly copy of the mesh for this.

I know some people do know how to do these things, but unfortunately they are not around or something.

Maybe you'll find some information on other forums and pages, dedicated to stencil shading.

well, i was searching my whole life for the edge recognizing code, but no, there wasn't any results :(

*cry*

I am sure there are several ways to do it. Tho it may be hard to find a GOOD one, a fast one.

http://www.gamasutra.com/features/19991115/bestimt_freitag_01.htm
http://www.caip.rutgers.edu/~kuttuva/shadow_volumes.html
http://en.wikipedia.org/wiki/Shadow_volume
http://www.gamedev.net/reference/articles/article1873.asp
http://downloads.gamedev.net/pdf/VolumeShadowsTutorial-2036.pdf
http://www.planetquake.com/q3empire/files/papers/Realtime_Shadowcasting.pdf
this one even has a link to a quake 1 modified engine that has stencil shadows in:
http://www.aceshardware.com/read_news.jsp?id=60000466

I am working on this right now. Here is my approach:

-Create a list of the normal of every triangle in the mesh. There is an equation to get the normal or plane equation from the 3 points of a triangle.

-Create a list of every edge in the mesh, consisting of an indice a and an indice b. For each triangle, check for an existing edge between the points ab, bc, and ca. Test using vertex positions, since you might have concurrent edges that use different vertices. You also need a list of which two triangle this edges falls between.

-Create a list of dotproducts between your light vector and your triangle normal. This tells you whether a triangle faces towards the light or away.

-Look for edges between a triangle that faces the light, and one that faces away. These are your outline edges.

www.planetquake.com/q3empire/files/papers/Realtime_Shadowcasting.pdf
Wow. What a bunch of crap hyperbole. This paper is laughable.

thx, i will see what to do :)

Won't you have to rebuild this list every time the light and/or mesh moves - possibly, every frame? Isn't doing this very slow?

I must admit that when i first saw this post i was convinced it was an April Fools joke as your picture looks just a litle bit phallic to me.

Off topic: Don't you need shaders to pull this off? I didn't know Blitz allowed shaders?

lol :D
but an april fools joke is that not :(...

phallic in a microsoft way.

>>Wow. What a bunch of crap hyperbole. This paper is laughable.<<
Sorry, I didn't read it all.

I thought the same, but this is how it's done. Kind of nice to do something with the CPU for a change.

JFK, no offense meant, I just was annoyed with the psuedo-acedemic tone of that paper.

This is something I made a while ago. It is rather versitile, as you can apply shadow properties with a simple function and it is easy to implement and has support for colored shadows and transparent object shadows. Unfortunately, however, it is slow. It is kinda a modified version of Halo's demo that uses types instead of arrays plus some other goodies to make it more portable (and practical). The other problem is it can take a while to load a mesh with a large number of tris because of the algorithm it uses. It is in desperate need for a rewrite but you can use it for whatever you want.

;;;;;;;;;;;;;;;;;;;;;
;Shadows............;
;Michael Scherer....;
;[Tainted Instinct].;
;;;;;;;;;;;;;;;;;;;;;



Global FPS,LastCheck,Frames
Function GetFPS()
	Frames = Frames + 1
	
	If MilliSecs() > LastCheck+1000 Then
		LastCheck = MilliSecs()
		FPS = Frames
		Frames = 0
	EndIf
	Return FPS
End Function




Graphics3D 800,600

AntiAlias True

;COLLISON TYPES
Const shadowCOL = 1, terrainCOL = 2

;SHADOWMESH/SHADOWVERTEX TYPES
Type shadowmesh
	Field entity,shadow					;the entity handle and its shadow
	Field alpha#						;for meshes that are see-through
End Type

Type shadowvertex
	Field surf,tri,index				;exact location of vertex
	Field entity						;the pivot
	Field parent						;which shadowmesh this vertex belongs to
End Type

;CREATE A SHADOWMESH
Function shadowmesh(mesh,alpha#,r,g,b)
	s.shadowmesh = New shadowmesh
	
	s\entity = mesh
	s\shadow = CopyMesh(mesh)
	EntityFX s\shadow,1
	EntityColor s\shadow,r,g,b
	EntityAlpha s\shadow,.5				;changes based on distance from light
	s\alpha# = alpha#
	
	;get all vertex positions
	For sf = 1 To CountSurfaces(s\entity)
		surf = GetSurface(s\entity,sf)
		For t = 0 To CountTriangles(surf)-1
		For i = 0 To 2
			;vert = TriangleVertex(surf,t,i)
			sv.shadowvertex = New shadowvertex
			sv\surf = sf : sv\tri = t : sv\index = TriangleVertex(surf,t,i)
			
			;sv\x# = VertexX#(surf,i) : sv\y# = VertexY#(surf,i) : sv\z# = VertexZ#(surf,i)
			sv\entity = CreatePivot()
			PositionEntity sv\entity, VertexX#(surf,sv\index), VertexY#(surf,sv\index), VertexZ#(surf,sv\index)
			
			EntityType sv\entity,shadowCOL
			;EntityRadius sv\entity,.001
			
			sv\parent = Handle(s)
		Next
		Next
	Next
	
	;eliminate redundant vertices
	For s1.shadowvertex = Each shadowvertex
		For s2.shadowvertex = Each shadowvertex
			If Handle(s1) <> Handle(s2)
				If s1\parent = s2\parent And s1\surf = s2\surf And s1\index = s2\index
					FreeEntity s2\entity
					Delete s2
				EndIf
			EndIf
		Next
	Next
	
	Return Handle(s)		;return the shadowmesh handle just in case
End Function

;THE LIGHT TYPE
Type shadowlight
	Field entity
	Field x#,y#,z#
	Field range#
End Type

;BUILD A LIGHT
Function shadowlight(x#,y#,z#,range#)
	l.shadowlight = New shadowlight
	
	l\entity = CreateLight(2)
	LightRange l\entity,range#
	PositionEntity l\entity,x#,y#,z#
	
	l\x# = x# : l\y# = y# : l\z# = z#
	l\range# = range#
	
	Return Handle(l)		;return the lights handle just in case
End Function

;a shadow mesh
cube = CreateSphere()
;ScaleMesh cube,.2,.2,.2
EntityColor cube,255,0,0
EntityAlpha cube,.5
shadowmesh(cube,.5,255,0,0)						;set it as a shadow mesh
PositionEntity cube,0,0,0

cube2 = CreateCube()
PositionEntity cube2,3,0,-3
shadowmesh(cube2,1,0,0,0)

cube3 = CreateSphere(3)
PositionEntity cube3,-3,0,-3
shadowmesh(cube3,1,0,0,0)

;a light
light = shadowlight(2,5,2,10)

lightspright = CreateSprite()	;he he lightspright, get it? just a placemarker
PositionEntity lightspright,2,5,2
tex=CreateTexture(128,128)
SetBuffer TextureBuffer(tex)
Rect 0,0,28,128
Rect 0,100,128,28
SetBuffer BackBuffer()
EntityTexture lightspright,tex
FreeTexture tex

;plane to put the shadows on
plane = CreatePlane(16)
EntityType plane,terrainCOL
PositionEntity plane,0,-5,0
tex=CreateTexture(128,128)
SetBuffer TextureBuffer(tex)
Color 0,128,0
Rect 0,0,128,128

SetBuffer BackBuffer()
EntityTexture plane,tex
FreeTexture tex


;camera to see the shadows with
Global cam = CreateCamera()
RotateEntity cam,15,0,0
PositionEntity cam,0,5,-20

;LET THE VERTICES COLLIDE WITH TERRAIN
Collisions shadowCOL,terrainCOL,2,1

SetBuffer BackBuffer()

CameraClsColor cam,0,255,255

Color 255,255,255
While Not KeyDown(1)
	PositionShadows()
	
	UpdateWorld
	RenderWorld
	
	UpdateShadows()
	
	l.shadowlight = Object.shadowlight(light)
	
	If KeyDown(205) Then MoveEntity l\entity, .1,0,0
	If KeyDown(203) Then MoveEntity l\entity,-.1,0,0
	
	If KeyDown(208) Then MoveEntity l\entity,0,0,-.1
	If KeyDown(200) Then MoveEntity l\entity,0,0, .1
	
	PositionEntity lightspright, EntityX#(l\entity),EntityY#(l\entity),EntityZ#(l\entity)
	
	TurnEntity cube2,.1,.2,.3
	TurnEntity cube3,.2,.3,.4
	
	;debugging------------------
	If CommandLine$() = "/debug"
	For l.shadowlight = Each shadowlight
		CameraProject cam,l\x#,l\y#,l\z#
		x# = ProjectedX() : y# = ProjectedY()
		WritePixel ProjectedX(),ProjectedY(),$ffff00
		
		For sv.shadowvertex = Each shadowvertex
			CameraProject cam,EntityX#(sv\entity, True),EntityY#(sv\entity, True),EntityZ#(sv\entity, True)
			Line x#,y#,ProjectedX(),ProjectedY()
		Next
	Next
	EndIf
	
	Text 0,0,GetFPS()
	
	;Screen Shot
	If KeyHit(88)
		SaveBuffer(BackBuffer(),"screen"+s+".bmp")
		s = s + 1
	EndIf
	
	Flip
Wend

;POSITION ALL SHADOW'S VERTICES
Function PositionShadows()
	;hide the shadows
	For s.shadowmesh = Each shadowmesh
		HideEntity s\shadow
	Next
	
	piv = CreatePivot()
	
	For l.shadowlight = Each shadowlight
		l\x# = EntityX#(l\entity, True) : l\y# = EntityY#(l\entity, True) : l\z# = EntityZ#(l\entity, True)
		PositionEntity piv,l\x#,l\y#,l\z#
		For s.shadowmesh = Each shadowmesh
			entdist# = EntityDistance#(s\entity,piv)
			If entdist# <= l\range#
				;since we are in the light range, show the shadow
				ShowEntity s\shadow
				
				;apply appropriate alpha level
				EntityAlpha s\shadow, (1-(entdist#/l\range#))*s\alpha#
				
				;now we position its vertices
				For sv.shadowvertex = Each shadowvertex
					If sv\parent = Handle(s)						;Make sure the vertex belongs to this mesh
						PositionEntity sv\entity,l\x#,l\y#,l\z#		;put the vertex at the light
						
						surf = GetSurface(s\entity,sv\surf)
						x# = VertexX#(surf,sv\index) : y# = VertexY#(surf,sv\index) : z# = VertexZ#(surf,sv\index)
						TFormPoint( x#, y#, z#, s\entity, 0 )
						x# = TFormedX#() : y# = TFormedY#() : z# = TFormedZ#()
						
						PositionEntity piv,x#,y#,z#
						PointEntity sv\entity,piv
						
						ResetEntity sv\entity
						
						MoveEntity sv\entity,0,0,99999
					EndIf
				Next
			EndIf
		Next
		If CommandLine$() = "/debug"
		CameraProject cam,l\x#,l\y#,l\z#
		WritePixel ProjectedX(),ProjectedY(),$ffff00,FrontBuffer()
		EndIf
	Next
	
	FreeEntity piv
End Function

;UPDATE ALL SHADOWS
Function UpdateShadows()
	For s.shadowmesh = Each shadowmesh
		For sv.shadowvertex = Each shadowvertex
			If sv\parent = Handle(s)
				surf = GetSurface(s\shadow,sv\surf)
				
				VertexCoords( surf,sv\index, EntityX#(sv\entity, True), EntityY#(sv\entity, True), EntityZ#(sv\entity, True) )
				
				If CommandLine$() = "/debug"
				CameraProject cam,EntityX#(sv\entity),EntityY#(sv\entity),EntityZ#(sv\entity)
				WritePixel ProjectedX(),ProjectedY(),$ff0000,BackBuffer()
				
				verts = verts+1
				EndIf
			EndIf
		Next
		
		UpdateNormals s\shadow
	Next
	If CommandLine$() = "/debug"
		Text 0,0,verts
	EndIf
End Function

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

Actually it's possible to do a kind of stencil shadows in plain blitz3d, if you once got a proper shadow volume, it can be done, tho without to access the stencil buffer, but basicly it's the same as stencil shadows.

Eurythmia released a little demo some time ago that demonstrated the trick. It had no shadow volumes, but it used a fake volume mesh.

It works this way: everything in the level is painted grey, 128,128,128 Only the shadow volume is say 64,64,64. Now when the shadow volume has EntityFX 17 and alpha 0.5, there will be two possible colors, byside the background color: 32,32,32 (that's where the renderer had to go through shadow volume faces only one time) and 16,16,16, (that's where it had to render 2 layers of faces: outer side and inner side). Practicly this results in zones that are intersecting with the ground etc. that will be 32,32,32 and zones that are not intersecting (16,16,16 or 128,128,128). The rendered screen is then grabed and Drawimage is used to draw the intersection parts only (using MaskImage).

Of course this could also be done using a semitransparent pixelperfect sprite that is covering the screen.

@ jfk , Interesting concept ... do you have a copy of Eurythmia's code that I can take a butchers at?

I have experimented in the past with a more optimised version of Tainted & Halo's fake stencil code but this method is only really effective when using lower poly proxy meshes to represent the shadows and with a flatish receiver mesh.

Cheers
Stevie

i am so happy to get that code from u :)

u are so nice, thx

can u bugfix i`t? i am trying to bugfix it, too...

PS: I will make a stencil shadow libary, and if i manage it, you'll get the comercial version for free :) as a present of mine!

me? well I'm trying to bugfix it, but no success since some hours, so I start thinking about some work-arounds.

Linepick is also pretty slow. It's slowlyness is exponential, so when a scene has 100 Tris it may take say 1 millisec, but when it has 200 tris then it won't take 2 ms, but eg. 4ms.

Linepick may be replaced by some clever code, I even think I remember elias_t posted something in the code archives, line intersect triangle or something.

I was also thinking about to use the old unique color identification trick, but this would require a renderworld for each light, and I guess there would be even more rounding errors.

While the silhouette tris are logically visible from the helper pivots position, they build such a thin ring around the source mesh that overlapping edges of triangles may obscure one another. If a triangles width is 1 or less pixels in this perspective, they may easily cover one another. I think that's the reason for the inconsistent pickability in the code I posted.

BTW sorry cannot find Eurythmias code right now. My copy is on an other machine. But the concept is real simple.

color all meshes grey 128,128,128, entityfx 1, alpha 1.0

color the shadow volume black, entityfx 17, alpha 0.5

-render the scene
-grab the backbuffer
-set maskcolor of this img to 128,128,128
-cls the backbuffer in color 32,32,32
-drawimage to the backbuffer
-grab it again
-set maskcolor to 32,32,32

-reset the scenes original colors and fx etc.
-render the scene normally.
-drawimage the img you grabed previously. everything but the intersecting parts will be masked. The intersected parts are the shadows.

Note: to prevent shadows on the backside of the source mesh you may have to use EntityOrder, so the source mesh will be rendered in front of the shadow volume. Not sure if this will make further troubles.

you rock baby ;)
edit: i have got toms stencil libary from here and when your code work, i'll manage to make a shadow libary and you'll get it fisrt :)

edit2: after long searching i found a function which createes a volukme BUT the volume is created not just from the edges... so it is not useful :(

Function CreateVolume(entity, light)
;entity - the entity that casts the shadow
;light - the light entity from which the light
;
;This function is included in case somebody wants to build shadow volumes and try stuff out.
;This is fairly slow because it extrudes and caps every triangle on a mesh. This means
;that 6 times more triangles need to be made for each one on the mesh.
;(I tried faster methods but trust me its not easy)
;It may be useful only for very basic geometry.


lx#=EntityX(light,True)
ly#=EntityY(light,True)
lz#=EntityZ(light,True)

	a_vol.volumes=New volumes
		a_vol\mesh=CreateMesh()
		
		;EntityBlend a_vol\mesh,2
		;EntityFX a_vol\mesh,1
		EntityColor a_vol\mesh,0,0,0
		EntityAlpha a_vol\mesh,0.001

		volsurf=CreateSurface(a_vol\mesh)
		numsurf=CountSurfaces(entity)		
		vpos=CreatePivot()
		vposend=CreatePivot()
		VolumeDepth#=1000
		
		
		
		;For surfcount=1 To numsurf-1
		surfcount=1

		While surfcount <= numsurf
			cursurface=GetSurface(entity, surfcount)
			maxtricount=CountTriangles (cursurface)
			;For tricount=0 To tricount-1
							
			While tricount < maxtricount
			v1x#=VertexX(cursurface, TriangleVertex(cursurface, tricount, 0))
			v1y#=VertexY(cursurface, TriangleVertex(cursurface, tricount, 0))
			v1z#=VertexZ(cursurface, TriangleVertex(cursurface, tricount, 0))
			TFormPoint v1x#,v1y#,v1z#, entity, 0
			v1x#=TFormedX()
			v1y#=TFormedY()
			v1z#=TFormedZ()
			
			v2x#=VertexX(cursurface, TriangleVertex(cursurface, tricount, 1))
			v2y#=VertexY(cursurface, TriangleVertex(cursurface, tricount, 1))
			v2z#=VertexZ(cursurface, TriangleVertex(cursurface, tricount, 1))			
			TFormPoint v2x#,v2y#,v2z#, entity, 0
			v2x#=TFormedX()
			v2y#=TFormedY()
			v2z#=TFormedZ()
			
			v3x#=VertexX(cursurface, TriangleVertex(cursurface, tricount, 2))
			v3y#=VertexY(cursurface, TriangleVertex(cursurface, tricount, 2))
			v3z#=VertexZ(cursurface, TriangleVertex(cursurface, tricount, 2))
			TFormPoint v3x#,v3y#,v3z#, entity, 0
			v3x#=TFormedX()
			v3y#=TFormedY()
			v3z#=TFormedZ()
			
			
			PositionEntity vpos,v1x#,v1y#,v1z#
			PositionEntity vposend, lx#,ly#,lz#,1
			PointEntity vposend, vpos
			MoveEntity vposend, 0,0,VolumeDepth#
			v1xe#=EntityX(vposend, True)
			v1ye#=EntityY(vposend, True)
			v1ze#=EntityZ(vposend, True)
			
			PositionEntity vpos,v2x#,v2y#,v2z#
			PositionEntity vposend, lx#,ly#,lz#,1
			PointEntity vposend, vpos
			MoveEntity vposend, 0,0,VolumeDepth#
			v2xe#=EntityX(vposend, True)
			v2ye#=EntityY(vposend, True)
			v2ze#=EntityZ(vposend, True)
			
			PositionEntity vpos,v3x#,v3y#,v3z#
			PositionEntity vposend, lx#,ly#,lz#,1
			PointEntity vposend, vpos
			MoveEntity vposend, 0,0,VolumeDepth#
			v3xe#=EntityX(vposend, True)
			v3ye#=EntityY(vposend, True)
			v3ze#=EntityZ(vposend, True)
			
			v1=AddVertex(volsurf,v1x#,v1y#,v1z#)
			v1e=AddVertex(volsurf,v1xe#,v1ye#,v1ze#)
			v2=AddVertex(volsurf,v2x#,v2y#,v2z#)
			v2e=AddVertex(volsurf,v2xe#,v2ye#,v2ze#)
			v3=AddVertex(volsurf,v3x#,v3y#,v3z#)
			v3e=AddVertex(volsurf,v3xe#,v3ye#,v3ze#)			

			AddTriangle (volsurf, v1,v1e,v2)
			AddTriangle (volsurf, v2,v1e,v2e)
			AddTriangle (volsurf, v1,v3,v1e)
			AddTriangle (volsurf, v3,v3e,v1e)
			AddTriangle (volsurf, v3,v2,v3e)
			AddTriangle (volsurf, v2,v2e,v3e)
			AddTriangle (volsurf, v1,v2,v3) 	;cap top
			AddTriangle (volsurf, v1e,v2e,v3e) 	;cap bottom			
			
			tricount=tricount+1
			Wend 
			;Next		
		surfcount=surfcount+1
		Wend
		;Next

FreeEntity vpos
FreeEntity vposend

End Function

yeah, that's about the same as when you use the first return in my function: simply create a volume for every triangle. The fine art is then to remove the enclosed tris. Even more efective would be to create only the needed Tris/quads, of course.

I have found elias_t's ray intersect triangle code in the archives and I assume it would work much faster than linepick, but I still try to find an idea on how to use it.

where Linepick will return the first pickable triangle that was "hit", the function by elias will only tell if the ray was intersecting a certain triangle. So theoreticly I'd have to check all triangles for every ray and return the one of those that are intersecting wich has the lowest distance from the intersection point to the pivot.

I guess that's also how Linepick works internally (thus the exponential slowdown with highpoly stuff and Linepick)

At least this Linepick replacement allows a simpler structure in general:

now we only have to store the vertex and triangle data in arrays and will then be able to generate a shadow volume using only the required sihouette triangles.

The source mesh'es triangle data must also be accessible in the arrays to allow to obscure things, like in the version using Linepick.

It's also useful that the ray intersection code doesn't care about normals, so it will work form both sides and you don't have to worry about flipped triangles.

The only question left is: will the 32 Bit accuracy be high enough to prevent the rounding errors seen with Linepick? (if it really WAS linepick that caused it).
And maybe: will it be fast enough?

I'll try to implement it this way the sooner or later.

Ok, I got it partially working with a Linepick replacement. It seems the rounding errors are occuring here too :(
Additionally it ssem I got troubles with the backface culling flag of the rit function (ray intersect triangle).

This version is faster than the Linepick version, even with this whole brute force triangle intersection scanning:
with Linepick it took 235 millisecs, with "rit" only 131ms.

Nevertheless, one thing is clear: the entire linepick (and rit) philosophy is way to slow for practical use. Using this for a scene of several thousand tris may take several seconds to complete.

So I'd suggest we stop this and try to do it the correct, official way, checking the neightbors normals etc. as described in some of the pages I linked to.

i think the error is in the routine which creates the volume, and not in the routine which cuts the unuseful polys, beacause if you return the volume after step1, you'll get the same error...

Hey guys, good work here! I'd love to see this come together. On the subject of linepicks and such, I recall that there's a wrapper for the Coldet collision engine lying around somewhere which has a pretty sweet set of ray / intersection tests. If I remember correctly it's much much faster than B3d. Might be worth checking out!

Let me know if you need me to post links -- I don't have them at the moment, but I can dig them up.

cheers,
roland

Thanks Roland. Is coldet for free? Thought it's not. well if
it is, this would be great!

BTW Xware, not sure how you meant the error is in the basic mesh? Especially, how could you see that? Anyway, practically you're right, I have found the bug, it was a wrong vertex assignenment:

there's this block where 6 potential silhouette tris are added:

   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

The second line of it should be:

   AddTriangle su2, v0_b,v0  ,v1_1b

Additionally use

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

This give s a much better result, although it still isn't perfect. In fact the rounding errors of the Z depth, caused by the 3D hardware can never be fully fixed.

Using a Linepick replacement that is using 64bit or 96bit floating point internally might solve the problem.

Plus, the speed of it is still very slow. Tho I am pleased it really works at all.
EDIT after fiddling with the infini, pick radius and pick_back, I got the sphere working correctly. Tho this is all pretty fragile.

Coldet may be a solution, for both floating point resolution and linepick speedup.

But I still think there's this unneccessary creation of enclosed tris, just to remove them after the visibility check. Although still pretty fast (byside linepick), it's not optimal.

BTW currently I am working on a third cheating version, this one is trying to utilize the ICU color detection trick. I still got some problems with rounding errors, like with the two prev. versions, but the speed of this one is much faster, 230 ms was reduced to about 5 ms. It requires an additional renderworld for every light source.

Every triangle of the shadow volume 1 (containing all potential tris) will use its unique vertex color that is representing its triangle index.
An orto camera is positioned at the helper pivots position (one step behind the light) and takes a render.
Readpixelfast is now used to determine the visibility of the triangles.

It's much faster to read eg. 64*64 pixels than checking the ray intersection of every triangle against every other triangle in the volume. This also causes no exponential slowdown compared to Linepick.

Tho, I still have to fix the rounding error roblem here, this one seems to be even trickier than in the prev. two versions (pixel precision only).

yes, thats a good idea to use coldet...thx roland :)
perhabs there are other libs for cheating to volume by :)
...

ok, but if i return the volume after creating it, without deleting the tris, the error appears, too.
and there is a "convex hull" dll in the dll archives, can u may use this^^?

I think the convex hull is used for physics libraries, someone correct me if I'm wrong. I think we don't need a convex hull, but in fact a shadow volume.

Yes coldet is for free and thanks to elias for the wrapper. I have modified it so it is using coldets Ray-Collision function instead of Linepick. The problem is: you have to define what mesh should be checked, so you need to do those ray-collision tests for every mesh in the scene, eg: to create one volume you got to do it with the volume as well as with the obscurer (source mesh).

I still can't make coldet detect the right triangles, but I already see the speed of coldet. Where the Linepick version took 230ms coldet requires only about 50 ms. Tho, complicate things pretty much (coldet volumes must be built for every shadow volume etc.)

So I really still hope I can make the ICU version work correctly ince it's the fastest yet: 5ms compared to 230.

That said, a real solution if still welcome :)

cool, thats great :)

ok here's somethin gto play with, until we get a real solution by somebody who's actually knowing what he's doing, so not by me o_O

This is the fixed version of the Linepicking Volume creator. Wit this settings it's working pretty nicely, say about 99.5% correctly, although of course still slow with high poly stuff, but you may try it with some low poly geometry and see. Maybe somebody can add a faster Linepick:

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


; make silhouette mesh / shadow volume

; works 99%, pretty slow with high poly stuff (linepick exponential slowdown).


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




Global helper=CreatePivot()
Global helper2=CreatePivot()

; you can easily destroy it when editing these parameters :)
Global infi#=50 ; length shadow volume
Global pick_radius#=0.0001 
Global pick_back#=50 ; 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
;cube=CreateCube() ; object to cast shadow
;cube=CreateCylinder(10) ; object to cast shadow
cube=CreateCone(10) ; 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


While KeyDown(1)=0
 a=(a +2) Mod 360
 PositionEntity lime,Sin(a)*4.0,4,Cos(a)*4.0
 t1=MilliSecs()
 vol=make_volume(cube,lime)
 t2=MilliSecs()
 UpdateWorld
 RenderWorld()
 Text 0,0,"tris "+TrisRendered()
 Text 0,16,"ms "+(t2-t1)
 Text 0,32,"space=pause"
 Flip
 While KeyDown(57) 
  Delay 1
 Wend 
 FreeEntity vol
Wend
End




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
 TFormPoint EntityX(lite),EntityY(lite),EntityZ(lite),0,source
 PositionEntity helper2,TFormedX(),TFormedY(),TFormedZ()
 tri_count=0
 vol=CreateMesh()
 su2=CreateSurface(vol)
 For s=1 To CountSurfaces(source)
  su=GetSurface(source,s)
  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)

   PositionEntity helper,vx0,vy0,vz0
   PointEntity helper,helper2
   MoveEntity helper,0,0,-infi
   v0_b=AddVertex(su2,EntityX(helper),EntityY(helper),EntityZ(helper))

   PositionEntity helper,vx1,vy1,vz1
   PointEntity helper,helper2
   MoveEntity helper,0,0,-infi
   v1_b=AddVertex(su2,EntityX(helper),EntityY(helper),EntityZ(helper))

   PositionEntity helper,vx2,vy2,vz2
   PointEntity helper,helper2
   MoveEntity helper,0,0,-infi
   v2_b=AddVertex(su2,EntityX(helper),EntityY(helper),EntityZ(helper))

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

   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:


 ; (cosmetics)
 remx#=EntityX(source)
 remy#=EntityY(source)
 remz#=EntityZ(source)
 rempitch#=EntityPitch(source)
 remyaw#=EntityYaw(source)
 remroll#=EntityRoll(source)
 PointEntity source,lite
 MoveEntity source,0,0,.1
 RotateEntity source, rempitch,remyaw,remroll


 vol3=CreateMesh() ; this will be the final shadow volume
 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

 ; (undo cosmetics)
 PositionEntity source, remx,remy,remz


 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

additionally here's the same function, now demonstrating how it could be used in plain Blitz to create Stencil Shadows:

; stencil shadows in plain blitzbasic

; slow as hell due to LinePicks!

; creates  a shadow volume with the help of Linepick:


; experimental (please somebody successfully replace LinePick by Coldet rayintersection function)

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


Global helper=CreatePivot()
Global helper2=CreatePivot()

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


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

; better use a nice terrain to show the stencil shadows in action
plane=CreateTerrain(64)
For j=0 To 63
 For i=0 To 63
  ModifyTerrain(plane,i,j,Rnd(0.0,1.0))
 Next
Next
ScaleEntity plane,10,7,10
TerrainShading plane,1
TranslateEntity plane,-320,-7,-320



Global camera=CreateCamera()
TranslateEntity camera,0,2,-12
TurnEntity camera,10,0,0



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


; object to cast shadow (note: highpoly stuff is extremly slow)
; -------------------------------------------------------------
;cube=CreateSphere(5)
cube=CreateCube()
;cube=CreateCylinder(10)
;cube=CreateCone(10)
RotateEntity cube,45,45,0
EntityPickMode cube,2


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



img=CreateImage(GraphicsWidth(),GraphicsHeight()) ; used to mask nonintersection parts


While KeyDown(1)=0
 a=(a +2) Mod 360
 PositionEntity lime,Sin(a)*4.0,4,Cos(a)*4.0
 TurnEntity cube,1,2,3

 t1=MilliSecs()
 vol=make_volume(cube,lime)
 t2=MilliSecs()


 ; prepare scene for stencil shadow render
 EntityFX plane,1
 EntityFX cube,1
 EntityFX lime,1

 EntityColor plane,0,0,0
 EntityColor cube,0,0,0
 HideEntity lime
 EntityOrder cube,-1


 RenderWorld() ; render shadow volume
 GrabImage(img,0,0)
 MaskImage img,0,0,0
 ClsColor 96,96,96
 Cls
 DrawImage img,0,0
 GrabImage(img,0,0)
 MaskImage img,96,96,96


 ; restore scene for normal render
 EntityOrder cube,0
 EntityFX plane,0
 EntityFX cube,0
 EntityFX lime,0

 EntityColor plane,0,255,0
 EntityColor cube,255,255,255
 ShowEntity lime
 If KeyDown(57)<>1 Then HideEntity vol

 RenderWorld() ; render the scene for the audience

 ; add stencil shadow 2D layer (pixelperfect sprite may be used instead!)
 DrawImage img,0,0

 Text 0,0,"tris "+TrisRendered()
 Text 0,16,"ms "+(t2-t1)
 Text 0,32,"space=show volume"
 Text 0,48,ReadPixel(MouseX(),MouseY()) And $ff
 Flip
 FreeEntity vol
Wend

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
 TFormPoint EntityX(lite),EntityY(lite),EntityZ(lite),0,source
 PositionEntity helper2,TFormedX(),TFormedY(),TFormedZ()
 tri_count=0
 vol=CreateMesh()
 su2=CreateSurface(vol)
 For s=1 To CountSurfaces(source)
  su=GetSurface(source,s)
  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)

   PositionEntity helper,vx0,vy0,vz0
   PointEntity helper,helper2
   MoveEntity helper,0,0,-infi
   v0_b=AddVertex(su2,EntityX(helper),EntityY(helper),EntityZ(helper))

   PositionEntity helper,vx1,vy1,vz1
   PointEntity helper,helper2
   MoveEntity helper,0,0,-infi
   v1_b=AddVertex(su2,EntityX(helper),EntityY(helper),EntityZ(helper))

   PositionEntity helper,vx2,vy2,vz2
   PointEntity helper,helper2
   MoveEntity helper,0,0,-infi
   v2_b=AddVertex(su2,EntityX(helper),EntityY(helper),EntityZ(helper))

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

   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.


; -------------------------------


; create a copy without the enclosed tris:


 ; (cosmetics)
 remx#=EntityX(source)
 remy#=EntityY(source)
 remz#=EntityZ(source)
 rempitch#=EntityPitch(source)
 remyaw#=EntityYaw(source)
 remroll#=EntityRoll(source)
 PointEntity source,lite
 MoveEntity source,0,0,.1
 RotateEntity source, rempitch,remyaw,remroll


 vol3=CreateMesh() ; this will be the final shadow volume
 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

 ; (undo cosmetics)
 PositionEntity source, remx,remy,remz


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

Ok finally here's a combination of the ICU method and the linepick method.

First it uses the ICU detection method that is pretty fast. But then there are still some enclosed Triangles left that should not be there. So I additionally use the Linepick method to get rid of them. It's a bit less accurate than the Linepick only version. However, the speed is around 9ms, compared to the linepickversion (230ms), the coldet version (50ms) and the plain ICU method(ca. 6ms, tho not accurate enough).

I have also seen as soon as I use smaller triangles (like a sphere with more segments), the rouding errors show up more oftenly. So I'd say: this may be useful for simple, rough geometry only.

Additionally there's the bitter fact that animated meshes cannot make use of this because VertexX etc. will ignore Animations and return the initial pose.

;create shadow volume with a combination of Linepick and the ICU method:
;-----------------------------------------------------------------------

; works kind of, tho meshes with lots of little triangles will produce more rounding errors



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



Global helper=CreatePivot()
Global helper2=CreatePivot()
Global icucam=CreateCamera()
CameraProjMode icucam,0
Dim icu_seen(0)

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


lidis#=4

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

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

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

cube=CreateSphere(5) ;CreateCube() ; object to cast shadow
;cube=CreateCube() ; object to cast shadow
;cube=CreateCone(10)
RotateEntity cube,45,45,0
;RotateEntity cube,245,245,0
EntityPickMode cube,2
;TranslateEntity cube,1.2,0.5,1.3

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

a#=90
While KeyDown(1)=0
 a=(a +2) Mod 360
 PositionEntity lime,Sin(a)*lidis,lidis,Cos(a)*lidis
; PositionEntity light,Sin(a)*lidis,lidis,Cos(a)*lidis
; TurnEntity cube,1,2,3
 If vol<>0 Then FreeEntity vol
 t1=MilliSecs()
 vol=make_volume(cube,lime)
 t2=MilliSecs()
 RenderWorld()
 Text 0,0,"tris "+TrisRendered()
 Text 0,16,"ms "+(t2-t1)
 Text 0,32,"space=pause"
 Flip
 While KeyDown(57) 
  Delay 1
 Wend 
Wend
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

 TFormPoint EntityX(lite),EntityY(lite),EntityZ(lite),0,source
 PositionEntity helper2,TFormedX(),TFormedY(),TFormedZ()
 litemesh=lite
 lite=helper2

 vol=CreateMesh()
 su2=CreateSurface(vol)
 For s=1 To CountSurfaces(source)
  su=GetSurface(source,s)
  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))
   
   ; create projected vertex coords
   PositionEntity helper,vx0,vy0,vz0
   PointEntity helper,lite
   MoveEntity helper,0,0,-infi
   vx0_b#=EntityX(helper)
   vy0_b#=EntityY(helper)
   vz0_b#=EntityZ(helper)


   PositionEntity helper,vx1,vy1,vz1
   PointEntity helper,lite
   MoveEntity helper,0,0,-infi
   vx1_b#=EntityX(helper)
   vy1_b#=EntityY(helper)
   vz1_b#=EntityZ(helper)

   PositionEntity helper,vx2,vy2,vz2
   PointEntity helper,lite
   MoveEntity helper,0,0,-infi
   vx2_b#=EntityX(helper)
   vy2_b#=EntityY(helper)
   vz2_b#=EntityZ(helper)

 ; add all potential shadow volume tris and set their ID color
;-   AddTriangle su2, v0  ,v1  ,v1_b
   vv0=AddVertex(su2,vx0,vy0,vz0)
   vv1=AddVertex(su2,vx1,vy1,vz1)
   vv2=AddVertex(su2,vx1_b,vy1_b,vz1_b)
   icu_code=(tri_count+10)+0
   icu_red=(icu_code And $FF0000) Shr 16
   icu_green=(icu_code And $FF00) Shr 8
   icu_blue=(icu_code And $FF)
   VertexColor su2,vv0,icu_red,icu_green,icu_blue
   VertexColor su2,vv1,icu_red,icu_green,icu_blue
   VertexColor su2,vv2,icu_red,icu_green,icu_blue
   AddTriangle su2, vv0 ,vv1 ,vv2

;-   AddTriangle su2, v0_b,v0  ,v1_b
   vv0=AddVertex(su2,vx0_b,vy0_b,vz0_b)
   vv1=AddVertex(su2,vx0,vy0,vz0)
   vv2=AddVertex(su2,vx1_b,vy1_b,vz1_b)
   icu_code=(tri_count+10)+1
   icu_red=(icu_code And $FF0000) Shr 16
   icu_green=(icu_code And $FF00) Shr 8
   icu_blue=(icu_code And $FF)
   VertexColor su2,vv0,icu_red,icu_green,icu_blue
   VertexColor su2,vv1,icu_red,icu_green,icu_blue
   VertexColor su2,vv2,icu_red,icu_green,icu_blue
   AddTriangle su2, vv0 ,vv1 ,vv2

;-   AddTriangle su2, v1_b,v1,v2_b
   vv0=AddVertex(su2,vx1_b,vy1_b,vz1_b)
   vv1=AddVertex(su2,vx1,vy1,vz1)
   vv2=AddVertex(su2,vx2_b,vy2_b,vz2_b)
   icu_code=(tri_count+10)+2
   icu_red=(icu_code And $FF0000) Shr 16
   icu_green=(icu_code And $FF00) Shr 8
   icu_blue=(icu_code And $FF)
   VertexColor su2,vv0,icu_red,icu_green,icu_blue
   VertexColor su2,vv1,icu_red,icu_green,icu_blue
   VertexColor su2,vv2,icu_red,icu_green,icu_blue
   AddTriangle su2, vv0 ,vv1 ,vv2


;-   AddTriangle su2, v1,v2,v2_b
   vv0=AddVertex(su2,vx1,vy1,vz1)
   vv1=AddVertex(su2,vx2,vy2,vz2)
   vv2=AddVertex(su2,vx2_b,vy2_b,vz2_b)
   icu_code=(tri_count+10)+3
   icu_red=(icu_code And $FF0000) Shr 16
   icu_green=(icu_code And $FF00) Shr 8
   icu_blue=(icu_code And $FF)
   VertexColor su2,vv0,icu_red,icu_green,icu_blue
   VertexColor su2,vv1,icu_red,icu_green,icu_blue
   VertexColor su2,vv2,icu_red,icu_green,icu_blue
   AddTriangle su2, vv0 ,vv1 ,vv2


;-   AddTriangle su2, v2,v0_b,v2_b
   vv0=AddVertex(su2,vx2,vy2,vz2)
   vv1=AddVertex(su2,vx0_b,vy0_b,vz0_b)
   vv2=AddVertex(su2,vx2_b,vy2_b,vz2_b)
   icu_code=(tri_count+10)+4
   icu_red=(icu_code And $FF0000) Shr 16
   icu_green=(icu_code And $FF00) Shr 8
   icu_blue=(icu_code And $FF)
   VertexColor su2,vv0,icu_red,icu_green,icu_blue
   VertexColor su2,vv1,icu_red,icu_green,icu_blue
   VertexColor su2,vv2,icu_red,icu_green,icu_blue
   AddTriangle su2, vv0 ,vv1 ,vv2


;-   AddTriangle su2, v2,v0,v0_b
   vv0=AddVertex(su2,vx2,vy2,vz2)
   vv1=AddVertex(su2,vx0,vy0,vz0)
   vv2=AddVertex(su2,vx0_b,vy0_b,vz0_b)
   icu_code=(tri_count+10)+5
   icu_red=(icu_code And $FF0000) Shr 16
   icu_green=(icu_code And $FF00) Shr 8
   icu_blue=(icu_code And $FF)
   VertexColor su2,vv0,icu_red,icu_green,icu_blue
   VertexColor su2,vv1,icu_red,icu_green,icu_blue
   VertexColor su2,vv2,icu_red,icu_green,icu_blue
   AddTriangle su2, vv0 ,vv1 ,vv2


   tri_count=tri_count+6

  Next
 Next
 EntityPickMode vol,2
 EntityFX vol,1 Or 2
 EntityColor vol,0,0,255
 RotateEntity vol, EntityPitch(source),EntityYaw(source),EntityRoll(source),1
 PositionEntity vol,EntityX(source),EntityY(source),EntityZ(source)

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

; -------------------------------

; 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

 PositionEntity icucam ,EntityX(litemesh),EntityY(litemesh),EntityZ(litemesh),1
 PointEntity icucam,source
 MoveEntity icucam,0,0,-pick_back

 Dim icu_seen(tri_count)
 ; prepare scene for ICU scan
 sz=64;127
 ; work around rounding Z errors...
 remx#=EntityX(source)
 remy#=EntityY(source)
 remz#=EntityZ(source)
 rempitch#=EntityPitch(source)
 remyaw#=EntityYaw(source)
 remroll#=EntityRoll(source)
 PointEntity source,litemesh
 MoveEntity source,0,0,.1
 RotateEntity source, rempitch,remyaw,remroll
; eo work around
 EntityColor plane,0,0,0
 EntityColor source,0,0,0
 HideEntity litemesh
 CameraViewport icucam,0,0,sz+1,sz+1

;CameraProjMode icucam,1;2 ; better? guess not
;CameraRange icucam,10,5000
;CameraZoom icucam,10

 CameraProjMode icucam,2
 CameraRange icucam,0.0002,100
 CameraZoom icucam,.0001

 CameraProjMode camera,0

 ; create ICU render and scan it for valid ID colors
 RenderWorld()
 SetBuffer BackBuffer()
 LockBuffer()
 For j=0 To sz
  For i=0 To sz
   rgb=ReadPixelFast(i,j) And $FFFFFF
   If( rgb > 0) And (rgb<=tri_count+10)
    icu_index=rgb-10
    icu_seen(icu_index)=icu_seen(icu_index)+1
   EndIf
  Next
 Next
 UnlockBuffer()


 ;PositionEntity source, remx,remy,remz
 EntityColor plane,0,255,0
 EntityColor source,255,255,255
 ShowEntity litemesh
 CameraProjMode icucam,0
 CameraProjMode camera,1

 ;Flip 0 ; use this for visual control of the ICU render
 ;WaitKey()


 ; create a new volume mesh containing the triangles with detected ICU ID colors (visible tris)

 For i=0 To tri_count-1

  If icu_seen(i)>0
   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))

   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
 Next

 ; Goto skip_combi ; use this to see the ICU product only!

 FreeEntity vol ; release old volume
 vol=vol3

 UpdateNormals vol
 EntityPickMode vol,2
 EntityFX vol,1 Or 2
 EntityColor vol,0,0,255
 RotateEntity vol, EntityPitch(source),EntityYaw(source),EntityRoll(source),1
 PositionEntity vol,EntityX(source),EntityY(source),EntityZ(source)


 ; now we create a new mesh and use the linepick method to scan trough the
 ; imperfect shadow volume mesh we just created using the ICU method.
 ; this Linepick method is more accurate, but much slower. Thanks to the
 ; ICU method we only have to scan a fraction of the first volume mesh.

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


 vol3=CreateMesh()
 su3=CreateSurface(vol3)
 su2=GetSurface(vol,1)
 tri_count=CountTriangles(su2)
 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

 .skip_combi

 ; (undo cosmetics)
 PositionEntity source, remx,remy,remz


 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

 ;so we first created a mesh containig every potential triangle required for the shadow volume mesh.
 ;then we used the ICU (Identification by Color Uniqueness) Method to make a rough copy of the 
 ;silhouette triangles (= removing enclosed Triangles). This is not very accurate: there are
 ;still some triangles copied that should not be there.
 ;so finally we scan this rough silhouette mesh and create a third mesh, containing only the 
 ;picked Silhouette Triangles.

End Function

Well right now this is the best I can do. Maybe I'll try it again from scratch one day, with a completely diffrent method, preferably the official math way and not cheats like these.

Good code! Thanks a lot!
Sad to hear that you are not developing it further, and wish I could help, but I have NO idea of where to begin with this sort of thing. Good work jfk! Thanks again!

thank you. the lack of accuracy makes the whole approach pretty useless, so it was kind of a waste of time.

Cause, when you try to use this with a loaded mesh, it simply doesn't work for some reason.

I think a proper solution is needed. Unfortunately those who did it (I remember that Stencil Shadow demo with the beethoven mesh, using the dx7test.dll, creating realtime shadow volumes too) don't seem to be willing to release the sources, or maybe they're not around. Or in the words of a guy from the past: the scientists have locked up the scripts and hidden the key.

Personally I am not very clever when it comes to 3D maths. Well maybe I'll find a simple C source that can be translated to Blitz.

Nice work JFK .. shame ( like you say ) it's too slow for in game.

Stevie



That'd be Fredborg, still have it on my desktop :)

thank u very much :) :) :)

please give me your email adress, therefore i can give you the ready system in a few weeks...
you'll get it!

if u have managed to add the coldet version, can you please give it to me?


edit: i just seen, that if i use a model of a gun or a mesh, the volume looks corrupt...?

yes, I've seen that too. at least in my shadow demo concave shapes won't work, only convex ones. The reason why is concave shapes may force the renderers ray to go trough the hull surface not 1 or to time sonly, but 3 or 4 times.

Where in true stencil shadows the counter would add one when the ray hits the outside surface of the volume and subtract 1 when it hits the inside surface (resulting in 0 or 1 for shadow or not shadow), this blitz based demo uses ALpha to produce 2 maskables shades of grey.

I have also started the implementation of volume creation using a method desribed in the papers. This method will create a list conaining the 3 neighbour triangles of every triangle. It will then determine the backface culling state of every triangle, from the viewpoint of the light. Now every nonculled triangle that has at least 1 neighbour that is culled is a potential edge triangle. Finally I have to determine if the edge triangles are obscured by other triangles. If they are not, then they are the wanted edge triangles.

The problem is: I again have to check the visibility of every triangle from the viewpoint of the light. That's the slow part again, No matter if you use Linepick, Coldet picks or even the fast ICU method.

For the ICU method a copy of the mesh must be created on the fly, with unwelded vertices, the triangles are then colored individually, just to render it, then use readpixelfast to determine what colors were rendered (=visible triangles) and finally delete the ICU mesh copy again. Basicly ICU may be faster than all math picking stuff, but it also complicates things massively and makes it unflexible.

I still hope Fredborg will release the source for the volume creation of the Beethoven Stencil shadows demo.

I stopped this since this is really trying to reinvent the wheel.

wait! i have got an idea, without any linepick functions:

you use TFormNormal and check for every triangle out whether it is culled or not, and if two triangles are conected, and the one is culled, but the other not, THIS IS AN EDGE!!! then, you can create a quad on this edge...
this would be fast, but i dont know how to make it real...
may we can make a shadow system by helping each other... :)

ps: i'm actually in holidays, so i will answer a little bit later...

cu :)

I will post the alpha of the blitz stencil shadow system tomorrow. It has code for building and updating volumes, highly optimised. Making volumes is 90% of the work in a stencil shadow system and i have been improving that part all of the time.

PS i didnt read nearly any posts in this thread.

thanks len, cant wait :)

btw: i mailed fredborg, but got no reply yet...we'll see...

i love u braincell!!!
thx :)

Where will the link to braincell's system be?
In his worklog?
In this thread?

here you go guys

http://www.blitzbasic.com/Community/posts.php?topic=58882

thanks a lot! great work!