hello!
as you may know, i've been working on stencil shadows since ~ 7-8 months day&night. in my worklog is the system(by me and daredevil!) this system is using the second algorithm, but since a week it is using the third algo!
here are 3 algorithms for shadow volumes. they are not by me, but they are optimazed by me!
use it as yours!
[b]Use keys 1-3 to toggle the algorithms!
as you may know, i've been working on stencil shadows since ~ 7-8 months day&night. in my worklog is the system(by me and daredevil!) this system is using the second algorithm, but since a week it is using the third algo!
here are 3 algorithms for shadow volumes. they are not by me, but they are optimazed by me!
use it as yours!
Graphics3D 1024, 768, 32, 2 SetBuffer BackBuffer() ;Globs Dim Edge#(65000, 6) ;Volume algorithm 2 ;Volume algorithm 2: Const ETE_MaxTriang = 65000 Dim TriangleClone.ETE_Triangle(ETE_MaxTriang) ;Camera Cam = CreateCamera() PositionEntity Cam, 0, 5, -12 ;Volume mesh Global VolumeMesh = CreateMesh() Global VolumeSurf = CreateSurface(VolumeMesh) EntityColor VolumeMesh, 255, 0, 0 EntityFX VolumeMesh, 17 EntityAlpha VolumeMesh, .5 ;Light Light = CreateLight() PositionEntity Light, 0, 20, 0 PointEntity Light, CreatePivot() ;Casters c1 = CreateCube() PositionEntity c1, -6, 5, 0 EntityColor c1, 0, 255, 0 c2 = CreateCylinder() PositionEntity c2, -2, 5, 0 EntityColor c2, 0, 255, 0 c3 = CreateSphere() PositionEntity c3, 2, 5, 0 EntityColor c3, 0, 255, 0 c4 = CreateCone() PositionEntity c4, 6, 5, 0 EntityColor c4, 0, 255, 0 ;Initialise volumes(for algorithm 3 only!) InitVolumes() InitVolumeCaster(c1) InitVolumeCaster(c2) InitVolumeCaster(c3) InitVolumeCaster(c4) ;Floor c = CreateCube() ScaleEntity c, 10, 1, 10 EntityColor c, 0, 0, 255 Algorithm = 1 While Not KeyHit(1) If KeyHit(2) Then Algorithm = 1 If KeyHit(3) Then Algorithm = 2 If KeyHit(4) Then Algorithm = 3 TurnEntity c1, 1, .5, 1.5 TurnEntity c2, .5, 1.5, 1 TurnEntity c3, .5, 1, 1.5 TurnEntity c4, .5, 1, 1.5 ms = MilliSecs() ClearSurface VolumeSurf Select Algorithm Case 1 CreateVolume1(c1, Light) CreateVolume1(c2, Light) CreateVolume1(c3, Light) CreateVolume1(c4, Light) Case 2 CreateVolume2(c1, Light) CreateVolume2(c2, Light) CreateVolume2(c3, Light) CreateVolume2(c4, Light) Case 3 CreateVolume3(Light) End Select Volume_Time = MilliSecs() - ms RenderWorld Text 10, 10, "Volume time: " + Volume_Time gw2 = GraphicsWidth() / 2 Select Algorithm Case 1 Text gw2, 10, "- Shadow volume algorithm 1 -", True Text gw2, 20, "The simpliest and the slowest of all!", True Text gw2, 30, "He is creating for each shadow casting poly 6 other polygons, so", True Text gw2, 40, "a caster with 100 polys will cast 600 shadow polys. This method is very easy and VERY slow!", True Case 2 Text gw2, 10, "- Shadow volume algorithm 2 -", True Text gw2, 20, "This technique is faster than the first, because he extrudes the edges only.", True Case 3 Text gw2, 10, "- Shadow volume algorithm 2 -", True Text gw2, 20, "The fastest algorithm ever!", True Text gw2, 30, "He precalculates each shadow caster and then he creates only the edges(much more faster than algo 2!)", True End Select Flip Wend End ;==================================================================== ;===================== Shadow volume algorithm 1 ==================== ;==================================================================== Function CreateVolume1(ent, light) volume_lenght = 1000000 lx# = EntityX(light, True) ly# = EntityY(light, True) lz# = EntityZ(light, True) vpos = CreatePivot() vposend = CreatePivot() cnt_surf = CountSurfaces(ent) For s = 1 To cnt_surf surf = GetSurface(ent, s) cnt_tris = CountTriangles(surf) - 1 For tricount = 0 To cnt_tris TFormPoint VertexX(surf, TriangleVertex(surf, tricount, 0)), VertexY(surf, TriangleVertex(surf, tricount, 0)), VertexZ(surf, TriangleVertex(surf, tricount, 0)), ent, 0 v1x# = TFormedX() v1y# = TFormedY() v1z# = TFormedZ() TFormPoint VertexX(surf, TriangleVertex(surf, tricount, 1)), VertexY(surf, TriangleVertex(surf, tricount, 1)), VertexZ(surf, TriangleVertex(surf, tricount, 1)), ent, 0 v2x# = TFormedX() v2y# = TFormedY() v2z# = TFormedZ() TFormPoint VertexX(surf, TriangleVertex(surf, tricount, 2)), VertexY(surf, TriangleVertex(surf, tricount, 2)), VertexZ(surf, TriangleVertex(surf, tricount, 2)), ent, 0 v3x# = TFormedX() v3y# = TFormedY() v3z# = TFormedZ() PositionEntity vpos, v1x#, v1y#, v1z# PositionEntity vposend, lx#, ly#, lz# PointEntity vposend, vpos MoveEntity vposend, 0, 0, volume_lenght v1xe# = EntityX(vposend) v1ye# = EntityY(vposend) v1ze# = EntityZ(vposend) PositionEntity vpos, v2x#, v2y#, v2z# PositionEntity vposend, lx#, ly#, lz# PointEntity vposend, vpos MoveEntity vposend, 0, 0, volume_lenght v2xe# = EntityX(vposend) v2ye# = EntityY(vposend) v2ze# = EntityZ(vposend) PositionEntity vpos, v3x#, v3y#, v3z# PositionEntity vposend, lx#, ly#, lz# PointEntity vposend, vpos MoveEntity vposend, 0, 0, volume_lenght v3xe# = EntityX(vposend) v3ye# = EntityY(vposend) v3ze# = EntityZ(vposend) v1 = AddVertex(VolumeSurf, v1x#, v1y#, v1z#) v1e = AddVertex(VolumeSurf, v1xe#, v1ye#, v1ze#) v2 = AddVertex(VolumeSurf, v2x#, v2y#, v2z#) v2e = AddVertex(VolumeSurf, v2xe#, v2ye#, v2ze#) v3 = AddVertex(VolumeSurf, v3x#, v3y#, v3z#) v3e = AddVertex(VolumeSurf, v3xe#, v3ye#, v3ze#) AddTriangle (VolumeSurf, v1, v1e, v2) AddTriangle (VolumeSurf, v2, v1e, v2e) AddTriangle (VolumeSurf, v1, v3, v1e) AddTriangle (VolumeSurf, v3, v3e, v1e) AddTriangle (VolumeSurf, v3, v2, v3e) AddTriangle (VolumeSurf, v2, v2e, v3e) Next Next FreeEntity vpos FreeEntity vposend End Function ;==================================================================== ;===================== Shadow volume algorithm 2 ==================== ;==================================================================== Function CreateVolume2(ent, light) volume_lenght = 1000000 light_x# = EntityX(light, True) light_y# = EntityY(light, True) light_z# = EntityZ(light, True) cnt_edges = 0 cnt_surf = CountSurfaces(ent) For s = 1 To cnt_surf surf = GetSurface(ent, s) cnt_tris = CountTriangles(surf) - 1 For v = 0 To cnt_tris v0 = TriangleVertex(surf, v, 0) v1 = TriangleVertex(surf, v, 1) v2 = TriangleVertex(surf, v, 2) TFormPoint VertexX(surf, v0), VertexY(surf, v0), VertexZ(surf, v0), ent, 0 v1_x# = TFormedX() v1_y# = TFormedY() v1_z# = TFormedZ() TFormPoint VertexX(surf, v1), VertexY(surf, v1), VertexZ(surf, v1), ent, 0 v2_x# = TFormedX() v2_y# = TFormedY() v2_z# = TFormedZ() TFormPoint VertexX(surf, v2), VertexY(surf, v2), VertexZ(surf, v2), ent, 0 v3_x# = TFormedX() v3_y# = TFormedY() v3_z# = TFormedZ() p1_x# = v3_x# - v2_x# p1_y# = v3_y# - v2_y# p1_z# = v3_z# - v2_z# p2_x# = v2_x# - v1_x# p2_y# = v2_y# - v1_y# p2_z# = v2_z# - v1_z# norm_x# = p1_y# * p2_z# - p1_z# * p2_y# norm_y# = p1_z# * p2_x# - p1_x# * p2_z# norm_z# = p1_x# * p2_y# - p1_y# * p2_x# normlight_x# = (v1_x# + v2_x# + v3_x#) / 3 - light_x# normlight_y# = (v1_y# + v2_y# + v3_y#) / 3 - light_y# normlight_z# = (v1_z# + v2_z# + v3_z#) / 3 - light_z# If norm_x# * normlight_x# + norm_y# * normlight_y# + norm_z# * normlight_z# > 0 Then Edge#(cnt_edges, 0) = True Edge#(cnt_edges, 1) = v1_x# Edge#(cnt_edges, 2) = v1_y# Edge#(cnt_edges, 3) = v1_z# Edge#(cnt_edges, 4) = v2_x# Edge#(cnt_edges, 5) = v2_y# Edge#(cnt_edges, 6) = v2_z# cnt_edges = cnt_edges + 1 Edge#(cnt_edges, 0) = True Edge#(cnt_edges, 1) = v2_x# Edge#(cnt_edges, 2) = v2_y# Edge#(cnt_edges, 3) = v2_z# Edge#(cnt_edges, 4) = v3_x# Edge#(cnt_edges, 5) = v3_y# Edge#(cnt_edges, 6) = v3_z# cnt_edges = cnt_edges + 1 Edge#(cnt_edges, 0) = True Edge#(cnt_edges, 1) = v3_x# Edge#(cnt_edges, 2) = v3_y# Edge#(cnt_edges, 3) = v3_z# Edge#(cnt_edges, 4) = v1_x# Edge#(cnt_edges, 5) = v1_y# Edge#(cnt_edges, 6) = v1_z# cnt_edges = cnt_edges + 1 EndIf Next Next For a = 0 To cnt_edges If Edge#(a, 0) Then make_quad = True e1_p1_x# = Edge#(a, 1) e1_p1_y# = Edge#(a, 2) e1_p1_z# = Edge#(a, 3) e1_p2_x# = Edge#(a, 4) e1_p2_y# = Edge#(a, 5) e1_p2_z# = Edge#(a, 6) For b = a + 1 To cnt_edges If Edge#(b, 0) Then e2_p1_x# = Edge#(b, 1) e2_p1_y# = Edge#(b, 2) e2_p1_z# = Edge#(b, 3) e2_p2_x# = Edge#(b, 4) e2_p2_y# = Edge#(b, 5) e2_p2_z# = Edge#(b, 6) If e1_p1_x# = e2_p2_x# And e1_p1_y# = e2_p2_y# And e1_p1_z# = e2_p2_z# And e1_p2_x# = e2_p1_x# And e1_p2_y# = e2_p1_y# And e1_p2_z# = e2_p1_z# Then Edge#(a, 0) = False Edge#(b, 0) = False make_quad = False Exit EndIf EndIf Next If make_quad Then pe0_x# = (e1_p1_x# - light_x#) * volume_lenght + e1_p1_x# pe0_y# = (e1_p1_y# - light_y#) * volume_lenght + e1_p1_y# pe0_z# = (e1_p1_z# - light_z#) * volume_lenght + e1_p1_z# pe1_x# = (e1_p2_x# - light_x#) * volume_lenght + e1_p2_x# pe1_y# = (e1_p2_y# - light_y#) * volume_lenght + e1_p2_y# pe1_z# = (e1_p2_z# - light_z#) * volume_lenght + e1_p2_z# v1 = AddVertex(VolumeSurf, e1_p1_x#, e1_p1_y#, e1_p1_z#) v2 = AddVertex(VolumeSurf, pe1_x#, pe1_y#, pe1_z#) AddTriangle(VolumeSurf, v1, AddVertex(VolumeSurf, pe0_x#, pe0_y#, pe0_z#), v2) AddTriangle(VolumeSurf, v1, v2, AddVertex(VolumeSurf, e1_p2_x#, e1_p2_y#, e1_p2_z#)) Edge#(a, 0) = False EndIf EndIf Next End Function ;==================================================================== ;===================== Shadow volume algorithm 3 ==================== ;==================================================================== Type ETE_Mesh Field ent Field cnt_tris, tri.ETE_Triangle[ETE_MaxTriang] End Type Type ETE_Triangle Field v1.Point3D, v2.Point3D, v3.Point3D, nx#, ny#, nz# Field tri, ta, tb, tc End Type Type Point3D Field x#, y#, z# End Type Function InitVolumes() For n = 0 To ETE_MaxTriang TriangleClone.ETE_Triangle(n) = New ETE_Triangle TriangleClone(n)\v1 = New Point3D TriangleClone(n)\v2 = New Point3D TriangleClone(n)\v3 = New Point3D Next VolumeMesh = CreateMesh() VolumeSurf = CreateSurface(VolumeMesh) EntityColor VolumeMesh, 255, 0, 0 EntityAlpha VolumeMesh, .5 EntityFX VolumeMesh, 17 End Function Function FreeVolumes() Delete Each ETE_Mesh Delete Each ETE_Triangle Delete Each Point3D If VolumeMesh Then FreeEntity VolumeMesh End Function Function InitVolumeCaster(ent) Local ad1[ETE_MaxTriang], ad2[ETE_MaxTriang], ad3[ETE_MaxTriang] copy = SingleSurfaceMesh(ent) etem.ETE_Mesh = New ETE_Mesh etem\ent = ent surf = GetSurface(copy, 1) cnt_tris = CountTriangles(surf) - 1 etem\cnt_tris = cnt_tris For v = 0 To cnt_tris etem\tri[v] = New ETE_Triangle etet.ETE_Triangle = etem\tri[v] etet\v1 = New Point3D etet\v2 = New Point3D etet\v3 = New Point3D v1.Point3D = etet\v1 v2.Point3D = etet\v2 v3.Point3D = etet\v3 vert0 = TriangleVertex(surf, v, 0) vert1 = TriangleVertex(surf, v, 1) vert2 = TriangleVertex(surf, v, 2) v1\x# = VertexX(surf, vert0) v1\y# = VertexY(surf, vert0) v1\z# = VertexZ(surf, vert0) v2\x# = VertexX(surf, vert1) v2\y# = VertexY(surf, vert1) v2\z# = VertexZ(surf, vert1) v3\x# = VertexX(surf, vert2) v3\y# = VertexY(surf, vert2) v3\z# = VertexZ(surf, vert2) e0x# = v3\x# - v2\x# e0y# = v3\y# - v2\y# e0z# = v3\z# - v2\z# e1x# = v2\x# - v1\x# e1y# = v2\y# - v1\y# e1z# = v2\z# - v1\z# etet\nx# = e0y# * e1z# - e0z# * e1y# etet\ny# = e0z# * e1x# - e0x# * e1z# etet\nz# = e0x# * e1y# - e0y# * e1x# etet\tri = v etet\ta = -1 etet\tb = -1 etet\tc = -1 ad1[v] = True ad2[v] = True ad3[v] = True Next For a = 0 To etem\cnt_tris ATriang.ETE_Triangle = etem\tri[a] v1 = ATriang\v1 v2 = ATriang\v2 v3 = ATriang\v3 For b = a + 1 To etem\cnt_tris state1 = ad1<b> state2 = ad2[b] state3 = ad3[b] If a <> b And (state1 Or state2 Or state3) Then BTriang.ETE_Triangle = etem\tri[b] v2A.Point3D = BTriang\v1 v2B.Point3D = BTriang\v2 v2C.Point3D = BTriang\v3 If state1 Then If CheckLine(v1, v2A, v2, v2B) Then ATriang\ta = b BTriang\ta = a ad1[b] = False Goto SIDEA EndIf EndIf If state2 Then If CheckLine(v1, v2B, v2, v2C) Then ATriang\ta = b BTriang\tb = a ad2[b] = False Goto SIDEA EndIf EndIf If state3 Then If CheckLine(v1, v2C, v2, v2A) Then ATriang\ta = b BTriang\tc = a ad3[b] = False EndIf EndIf .SIDEA If state1 Then If CheckLine(v2, v2A, v3, v2B) Then ATriang\tb = b BTriang\ta = a ad1[b] = False Goto SIDEB EndIf EndIf If state2 Then If CheckLine(v2, v2B, v3, v2C) Then ATriang\tb = b BTriang\tb = a ad2[b] = False Goto SIDEB EndIf EndIf If state3 Then If CheckLine(v2, v2C, v3, v2A) Then ATriang\tb = b BTriang\tc = a ad3[b] = False EndIf EndIf .SIDEB If state1 Then If CheckLine(v3, v2A, v1, v2B) Then ATriang\tc = b BTriang\ta = a ad1[b] = False Goto SIDEC EndIf EndIf If state2 Then If CheckLine(v3, v2B, v1, v2C) Then ATriang\tc = b BTriang\tb = a ad2[b] = False Goto SIDEC EndIf EndIf If state3 Then If CheckLine(v3, v2C, v1, v2A) Then ATriang\tc = b BTriang\tc = a ad3[b] = False EndIf EndIf .SIDEC EndIf Next Next FreeEntity copy End Function Function CreateVolume3(light) light_x# = EntityX(light, True) light_y# = EntityY(light, True) light_z# = EntityZ(light, True) volume_lenght = 1000 For etem.ETE_Mesh = Each ETE_Mesh cnt_tris = etem\cnt_tris For v = 0 To cnt_tris etet.ETE_Triangle = TriangleClone(v) CloneTriangle(etet, etem\tri[v]) v1.Point3D = etet\v1 v2.Point3D = etet\v2 v3.Point3D = etet\v3 TFormPoint v1\x#, v1\y#, v1\z#, etem\ent, 0 v1\x# = TFormedX() v1\y# = TFormedY() v1\z# = TFormedZ() TFormPoint v2\x#, v2\y#, v2\z#, etem\ent, 0 v2\x# = TFormedX() v2\y# = TFormedY() v2\z# = TFormedZ() TFormPoint v3\x#, v3\y#, v3\z#, etem\ent, 0 v3\x# = TFormedX() v3\y# = TFormedY() v3\z# = TFormedZ() TFormNormal etet\nx#, etet\ny#, etet\nz#, etem\ent, 0 normlight_x# = (v1\x# + v2\x# + v3\x#) / 3.0 - light_x# normlight_y# = (v1\y# + v2\y# + v3\y#) / 3.0 - light_y# normlight_z# = (v1\z# + v2\z# + v3\z#) / 3.0 - light_z# If TFormedX() * normlight_x# + TFormedY() * normlight_y# + TFormedZ() * normlight_z# < 0 Then etet\tri = -1 Next For v = 0 To cnt_tris etet = TriangleClone(v) If etet\tri => 0 Then ta = etet\ta tb = etet\tb tc = etet\tc If ta > -1 Then check1 = TriangleClone(ta)\tri Else check1 = -1 If tb > -1 Then check2 = TriangleClone(tb)\tri Else check2 = -1 If tc > -1 Then check3 = TriangleClone(tc)\tri Else check3 = -1 If (check1 > -1 And check2 > -1 And check3 > -1) = False Then v1 = etet\v1 v2 = etet\v2 v3 = etet\v3 If check1 < 0 Then rax# = v1\x# + (v1\x# - light_x#) * volume_lenght ray# = v1\y# + (v1\y# - light_y#) * volume_lenght raz# = v1\z# + (v1\z# - light_z#) * volume_lenght rbx# = v2\x# + (v2\x# - light_x#) * volume_lenght rby# = v2\y# + (v2\y# - light_y#) * volume_lenght rbz# = v2\z# + (v2\z# - light_z#) * volume_lenght vert1 = AddVertex(VolumeSurf, v1\x#, v1\y#, v1\z#) vert2 = AddVertex(VolumeSurf, rax#, ray#, raz#) vert3 = AddVertex(VolumeSurf, rbx#, rby#, rbz#) vert4 = AddVertex(VolumeSurf, v2\x#, v2\y#, v2\z#) AddTriangle(VolumeSurf, vert1, vert2, vert3) AddTriangle(VolumeSurf, vert1, vert3, vert4) EndIf If check2 < 0 Then rbx# = v2\x# + (v2\x# - light_x#) * volume_lenght rby# = v2\y# + (v2\y# - light_y#) * volume_lenght rbz# = v2\z# + (v2\z# - light_z#) * volume_lenght rcx# = v3\x# + (v3\x# - light_x#) * volume_lenght rcy# = v3\y# + (v3\y# - light_y#) * volume_lenght rcz# = v3\z# + (v3\z# - light_z#) * volume_lenght vert1 = AddVertex(VolumeSurf, v2\x#, v2\y#, v2\z#) vert2 = AddVertex(VolumeSurf, rbx#, rby#, rbz#) vert3 = AddVertex(VolumeSurf, rcx#, rcy#, rcz#) vert4 = AddVertex(VolumeSurf, v3\x#, v3\y#, v3\z#) AddTriangle(VolumeSurf, vert1, vert2, vert3) AddTriangle(VolumeSurf, vert1, vert3, vert4) EndIf If check3 < 0 Then rax# = v1\x# + (v1\x# - light_x#) * volume_lenght ray# = v1\y# + (v1\y# - light_y#) * volume_lenght raz# = v1\z# + (v1\z# - light_z#) * volume_lenght rcx# = v3\x# + (v3\x# - light_x#) * volume_lenght rcy# = v3\y# + (v3\y# - light_y#) * volume_lenght rcz# = v3\z# + (v3\z# - light_z#) * volume_lenght vert1 = AddVertex(VolumeSurf, v1\x#, v1\y#, v1\z#) vert2 = AddVertex(VolumeSurf, rax#, ray#, raz#) vert3 = AddVertex(VolumeSurf, rcx#, rcy#, rcz#) vert4 = AddVertex(VolumeSurf, v3\x#, v3\y#, v3\z#) AddTriangle(VolumeSurf, vert1, vert3, vert2) AddTriangle(VolumeSurf, vert1, vert4, vert3) EndIf EndIf EndIf Next Next End Function Function SingleSurfaceMesh(ent) ret = CopyMesh(ent) If CountSurfaces(ret) = 1 Then Return ret Else FreeEntity ret ret = CreateMesh() new_surf = CreateSurface(ret) For s = 1 To CountSurfaces(ent) surf = GetSurface(ent, s) For t = 0 To CountTriangles(surf) - 1 v0 = TriangleVertex(surf, t, 0) v1 = TriangleVertex(surf, t, 1) v2 = TriangleVertex(surf, t, 2) new_v1 = AddVertex(new_surf, VertexX(surf, v0), VertexY(surf, v0), VertexZ(surf, v0)) new_v2 = AddVertex(new_surf, VertexX(surf, v1), VertexY(surf, v1), VertexZ(surf, v1)) new_v3 = AddVertex(new_surf, VertexX(surf, v2), VertexY(surf, v2), VertexZ(surf, v2)) AddTriangle new_surf, new_v1, new_v2, new_v3 Next Next Return ret EndIf End Function Function CloneTriangle(dst.ETE_Triangle, src.ETE_Triangle) dst\v1\x# = src\v1\x# dst\v1\y# = src\v1\y# dst\v1\z# = src\v1\z# dst\v2\x# = src\v2\x# dst\v2\y# = src\v2\y# dst\v2\z# = src\v2\z# dst\v3\x# = src\v3\x# dst\v3\y# = src\v3\y# dst\v3\z# = src\v3\z# dst\nx# = src\nx# dst\ny# = src\ny# dst\nz# = src\nz# dst\tri = src\tri dst\ta = src\ta dst\tb = src\tb dst\tc = src\tc End Function Function CheckLine(a1.Point3D, b1.Point3D, a2.Point3D, b2.Point3D) c1 = (a1\x# = a2\x# And a1\y# = a2\y# And a1\z# = a2\z#) c2 = (b1\x# = b2\x# And b1\y# = b2\y# And b1\z# = b2\z#) c3 = (a1\x# = b2\x# And a1\y# = b2\y# And a1\z# = b2\z#) c4 = (b1\x# = a2\x# And b1\y# = a2\y# And b1\z# = a2\z#) If (c1 And c2) Or (c3 And c4) Then Return True Else Return False End Function
[b]Use keys 1-3 to toggle the algorithms!