Occlusion culling
Community Forums/Showcase/Occlusion culling
| ||
| I have been playing around with occlusion culling lately and this is what i've come up with so far. Warning! The code is poorly commented and i think it could be greatly optimised as well. I also realised that I forgot to do depth checking, which means that objects will be culled away, even it they are in front of the occluder. But's thats easy to fix. Also note that i made the occluders semitransparent, just to show that the entities are actually culled.
Graphics3D 800,600
SetBuffer BackBuffer()
;WireFrame True
; Types and variables for Edgelist
Type Edge
Field A,B
Field Surf
Field Tri1 ; The triangle the edge belongs To
Field Tri2 ; The adjacent triangle, if one exist
Field X1,Y1,X2,Y2
Field Visible
Field PlaneDist# ; The edgelist also contains the planes
Field PlaneNX#
Field PlaneNY#
Field PlaneNZ#
Field Parent
End Type
Type vector
Field x#
Field y#
Field z#
End Type
Global CProd.vector=New vector
Global DProd#
Type Occluder
Field Mesh
Field ID
End Type
Type Entity
Field Entity
Field Occluded
Field Radius#
End Type
box = CreateMesh()
surf=CreateSurface(box)
v0=AddVertex(surf,-1,1,1)
v1=AddVertex(surf,1,1,1)
v2=AddVertex(surf,1,1,-1)
v3=AddVertex(surf,-1,1,-1)
v4=AddVertex(surf,-1,-1,1)
v5=AddVertex(surf,1,-1,1)
v6=AddVertex(surf,1,-1,-1)
v7=AddVertex(surf,-1,-1,-1)
AddTriangle(surf,v0,v1,v3)
AddTriangle(surf,v1,v2,v3)
AddTriangle(surf,v4,v7,v5)
AddTriangle(surf,v7,v6,v5)
AddTriangle(surf,v3,v2,v7)
AddTriangle(surf,v2,v6,v7)
AddTriangle(surf,v4,v1,v0)
AddTriangle(surf,v4,v5,v1)
AddTriangle(surf,v2,v1,v6)
AddTriangle(surf,v1,v5,v6)
AddTriangle(surf,v0,v3,v4)
AddTriangle(surf,v3,v7,v4)
;
HideEntity box
; Cams & Meshes
camera = CreateCamera()
PositionEntity camera,0,0,-5
CameraClsColor camera,150,150,220
Global EdgeList.Edge
; Create occluder
Global OccludeList.Occluder
OccludeList.Occluder = New Occluder
OccludeList\ID = 1
OccludeList\Mesh = CopyEntity(box)
PositionEntity OccludeList\mesh,-6,0,0
EntityAlpha OccludeList\mesh,0.8
OccludeList.Occluder = New Occluder
OccludeList\ID = 2
OccludeList\Mesh = CopyEntity(box)
PositionEntity OccludeList\mesh,-3,0,0
EntityAlpha OccludeList\mesh,0.8
OccludeList.Occluder = New Occluder
OccludeList\ID = 3
OccludeList\Mesh = CopyEntity(box)
PositionEntity OccludeList\mesh,0,0,0
EntityAlpha OccludeList\mesh,0.8
OccludeList.Occluder = New Occluder
OccludeList\ID = 4
OccludeList\Mesh = CopyEntity(box)
PositionEntity OccludeList\mesh,3,0,0
EntityAlpha OccludeList\mesh,0.8
OccludeList.Occluder = New Occluder
OccludeList\ID = 5
OccludeList\Mesh = CopyEntity(box)
PositionEntity OccludeList\mesh,6,0,0
EntityAlpha OccludeList\mesh,0.8
; Create ordinary objects
Global EntityList.Entity
For v=0 To 50
EntityList.Entity = New Entity
EntityList\Entity = CreateSphere(16)
EntityList\Radius# = 0.5
PositionEntity EntityList\Entity,Rnd(-5,5),Rnd(-5,5),Rnd(100,5)
EntityColor EntityList\Entity,Rnd(50,255),Rnd(50,255),Rnd(50,255)
Next
CenterPivot=CreatePivot()
light = CreateLight()
PositionEntity light,15,10,-15
PointEntity light,CenterPivot
; Build the Edgelists
For OccludeList.Occluder = Each Occluder
BuildEdgeList OccludeList\ID,OccludeList\mesh
Next
; The mainloop
LastTime=MilliSecs()
Color 0,0,0
UseOcclusion=0
While Not KeyDown(1)
FrameCount=FrameCount+1
If KeyHit(57) Then
UseOcclusion=1-UseOcclusion
If UseOcclusion=0 Then
For EntityList.Entity = Each Entity
ShowEntity EntityList\Entity
Next
EndIf
EndIf
;TurnEntity mesh,0,0.5,0
If KeyDown(200) Then
MoveEntity Camera,0,0.01,0
EndIf
If KeyDown(208) Then
MoveEntity Camera,0,-0.01,0
EndIf
If KeyDown(205) Then
MoveEntity Camera,0.01,0,0
EndIf
If KeyDown(203) Then
MoveEntity Camera,-0.01,0,0
EndIf
If KeyDown(201) Then
MoveEntity Camera,0,0,0.01
EndIf
If KeyDown(209) Then
MoveEntity Camera,0,0,-0.01
EndIf
RenderWorld
;Just for showing that the occluder doesn't need
;to be a static object
For OccludeList.Occluder = Each Occluder
TurnEntity OccludeList\Mesh,0,0.1,0
Next
If UseOcclusion=1 Then
For EntityList.Entity = Each Entity
EntityList\Occluded=False
Next
For OccludeList.Occluder = Each Occluder
; Skip Updating the occluder if it is out of the view
If EntityInView(OccludeList\Mesh,Camera) Then
UpdateOccluderPlanes OccludeList\ID,OccludeList\Mesh,Camera
EndIf
Next
For EntityList.Entity = Each Entity
; Skip to check if entity already is out of the viewfrustum
If EntityInView(EntityList\Entity,Camera) Then
OccludeEntity(EntityList,Camera)
EndIf
Next
EndIf
TimeTaken=MilliSecs()-LastTime
If TimeTaken>=1000 Then
LastTime=MilliSecs()
FPS=FrameCount
FrameCount=0
EndIf
Text 0,10,"FPS:" + Str(FPS)
If UseOcclusion=0 Then
Text 0,20,"Occlusion = " + "Off"
Else
Text 0,20,"Occlusion = " + "On"
EndIf
Text 0,30,"Rendered Tris:" + TrisRendered()
Text 0,40,"Press Space To Toggle Occlusion"
Flip False
Wend
End
; Functions
Function UpdateOccluderPlanes(OccID,occMesh,Cam)
; Loop through all Edges...
FirstRun=True
For EdgeList.Edge = Each Edge
If EdgeList\Parent=OccID Then
TriVis1 = TriVisible(Cam,occMesh,EdgeList\surf,EdgeList\Tri1)
TriVis2 = TriVisible(Cam,occMesh,EdgeList\surf,EdgeList\Tri2)
If TriVis1 Xor TriVis2 = True Then ; draw edge only if one triangle is visible and the other is hidden
x#=VertexX#(EdgeList\Surf,EdgeList\A)
y#=VertexY#(EdgeList\Surf,EdgeList\A)
z#=VertexZ#(EdgeList\Surf,EdgeList\A)
TFormPoint x#,y#,z#,occMesh,0
CameraProject Cam,TFormedX#(),TFormedY#(),TFormedZ#()
EdgeList\X1=ProjectedX()
EdgeList\Y1=ProjectedY()
If FirstRun=True Then
MaxX=EdgeList\X1:MinX=EdgeList\X1
MaxY=EdgeList\Y1:MinY=EdgeList\Y1
FirstRun=False
Else
If EdgeList\X1>MaxX Then MaxX=EdgeList\X1
If EdgeList\X1<MinX Then MinX=EdgeList\X1
If EdgeList\Y1>MaxY Then MaxY=EdgeList\Y1
If EdgeList\Y1<MinY Then MinY=EdgeList\Y1
EndIf
x#=VertexX#(EdgeList\Surf,EdgeList\B)
y#=VertexY#(EdgeList\Surf,EdgeList\B)
z#=VertexZ#(EdgeList\Surf,EdgeList\B)
TFormPoint x#,y#,z#,occMesh,0
CameraProject Cam,TFormedX#(),TFormedY#(),TFormedZ#()
EdgeList\X2=ProjectedX()
EdgeList\Y2=ProjectedY()
If EdgeList\X2>MaxX Then MaxX=EdgeList\X2
If EdgeList\X2<MinX Then MinX=EdgeList\X2
If EdgeList\Y2>MaxY Then MaxY=EdgeList\Y2
If EdgeList\Y2<MinY Then MinY=EdgeList\Y2
EdgeList\Visible=True
;Line EdgeList\X1,EdgeList\Y1,EdgeList\X2,EdgeList\Y2
Else
EdgeList\Visible=False
EndIf
EndIf
Next
; Calculate Midpoint
MidPointX=(MinX+MaxX)/2
MidPointY=(MinY+MaxY)/2
; Make sure every edge is in clockwise order, if not, swap the edges vertices
For EdgeList.Edge = Each Edge
If EdgeList\Parent=OccID Then
If EdgeList\Visible=True Then
If TriArea(EdgeList\X1,EdgeList\Y1,EdgeList\X2,EdgeList\Y2,MidPointX,MidPointY)<0 Then
TempHoldVertex=EdgeList\A
TempHoldX=EdgeList\X1
TempHoldY=EdgeList\Y1
EdgeList\A=EdgeList\B
EdgeList\X1=EdgeList\X2
EdgeList\Y1=EdgeList\Y2
EdgeList\B=TempHoldVertex
EdgeList\X2=TempHoldX
EdgeList\Y2=TempHoldY
EndIf
; Now calculate plane...
TFormPoint VertexX#(EdgeList\Surf,EdgeList\A),VertexY#(EdgeList\Surf,EdgeList\A),VertexZ#(EdgeList\Surf,EdgeList\A),occMesh,0
Vec1x#=EntityX#(Cam)-TFormedX#()
Vec1y#=EntityY#(Cam)-TFormedY#()
Vec1z#=EntityZ#(Cam)-TFormedZ#()
TFormPoint VertexX#(EdgeList\Surf,EdgeList\B),VertexY#(EdgeList\Surf,EdgeList\B),VertexZ#(EdgeList\Surf,EdgeList\B),occMesh,0
Vec2x#=EntityX#(Cam)-TFormedX#()
Vec2y#=EntityY#(Cam)-TFormedY#()
Vec2z#=EntityZ#(Cam)-TFormedZ#()
; CrossProduct Vec1x#,Vec1y#,Vec1z#,Vec2x#,Vec2y#,Vec2z#
Cpx#=(Vec1y#*Vec2z#)-(Vec1z#*Vec2y#)
Cpy#=(Vec1z#*Vec2x#)-(Vec1x#*Vec2z#)
Cpz#=(Vec1x#*Vec2y#)-(Vec1y#*Vec2x#)
;Normalize
TempDist#= Sqr(Cpx#*Cpx# + Cpy#*Cpy# + Cpz#*Cpz#)
Cpx#=Cpx#/TempDist#
Cpy#=Cpy#/TempDist#
Cpz#=Cpz#/TempDist#
EdgeList\PlaneNX#=Cpx#
EdgeList\PlaneNY#=Cpy#
EdgeList\PlaneNZ#=Cpz#
;EdgeList1\PlaneDist#=DotProduct(TFormedX#(),TFormedY#(),TFormedZ#(),CProd\x#,CProd\y#,CProd\z#)
EdgeList\PlaneDist#=((TFormedX#()*Cpx#)+(TFormedY#()*Cpy#)+(TFormedZ#()*Cpz#))
EndIf
EndIf
Next
End Function
Function OccludeEntity(CurrentEntity.Entity,Camera)
; Now check if object is occluded or not...
If CurrentEntity\Occluded=False Then ; If entity already is occluded, then skip this...
For OccludeList.Occluder = Each Occluder
; Skip the occluder if it's out of the viewfrustum
If EntityInView(OccludeList\Mesh,Camera)=False Then Goto SkipThisOccluder
EntityHidden=True
For EdgeList.Edge = Each Edge
If OccludeList\ID = EdgeList\Parent Then
If EdgeList\Visible=True Then
If ((EdgeList\PlaneNX#*EntityX#(CurrentEntity\Entity)+EdgeList\PlaneNY#*EntityY#(CurrentEntity\Entity)+EdgeList\PlaneNZ#*EntityZ#(CurrentEntity\Entity))-EdgeList\PlaneDist#+EntityList\Radius#)>-CurrentEntity\Radius# Then
EntityHidden=False
EndIf
EndIf
EndIf
Next
If EntityHidden=True Then
CurrentEntity\Occluded=True
;EntityColor EntityList\Entity,255,0,0
HideEntity CurrentEntity\Entity
Exit
Else
CurrentEntity\Occluded=False
ShowEntity CurrentEntity\Entity
EndIf
.SkipThisOccluder
Next
EndIf
End Function
; Function for filling the edgelist with edges
Function BuildEdgeList(OccID,Entity)
For Surfnr = 1 To CountSurfaces(Entity)
Surf=GetSurface(Entity,Surfnr)
For TriNr = 0 To CountTriangles(Surf)-1
EdgeA=TriangleVertex(Surf,Trinr,0)
EdgeB=TriangleVertex(Surf,Trinr,1)
AddEdge(OccID,Surf,TriNr,EdgeA,EdgeB)
EdgeA=TriangleVertex(Surf,Trinr,1)
EdgeB=TriangleVertex(Surf,Trinr,2)
AddEdge(OccID,Surf,TriNr,EdgeA,EdgeB)
EdgeA=TriangleVertex(Surf,Trinr,2)
EdgeB=TriangleVertex(Surf,Trinr,0)
AddEdge(OccID,Surf,TriNr,EdgeA,EdgeB)
Next
Next
End Function
Function AddEdge(OccID,Surf,TriNr,A,B)
EdgeFound = False
For EdgeList.Edge = Each Edge
If OccID = EdgeList\Parent Then
; Check if the given edge already exist in the list
; In that case just supply the triangle index
; The mesh must have shared vertices
If ((EdgeList\A = A And EdgeList\B = B) Or (EdgeList\A = B And EdgeList\B = A)) Then
EdgeFound = True
EdgeList\Tri2=TriNr
Exit
EndIf
EndIf
Next
; If the edge wasn't found, add it
If EdgeFound = False Then
EdgeList.Edge = New Edge
EdgeList\A=A
EdgeList\B=B
EdgeList\Surf=Surf
EdgeList\Tri1=TriNr
EdgeList\Tri2=-1
EdgeList\Parent=OccID
EndIf
End Function
Function TriVisible(Camera,Entity,Surface,Triangle)
If Triangle=-1 Then
; This means that the edge has no adjacent triangle
; If this occurs the mesh isn't solid(closed)
Return False
EndIf
ax#=VertexX#(Surface,TriangleVertex(Surface,Triangle,0))
ay#=VertexY#(Surface,TriangleVertex(Surface,Triangle,0))
az#=VertexZ#(Surface,TriangleVertex(Surface,Triangle,0))
bx#=VertexX#(Surface,TriangleVertex(Surface,Triangle,1))
by#=VertexY#(Surface,TriangleVertex(Surface,Triangle,1))
bz#=VertexZ#(Surface,TriangleVertex(Surface,Triangle,1))
cx#=VertexX#(Surface,TriangleVertex(Surface,Triangle,2))
cy#=VertexY#(Surface,TriangleVertex(Surface,Triangle,2))
cz#=VertexZ#(Surface,TriangleVertex(Surface,Triangle,2))
; Get vectors
v1x#=ax#-bx#
v1y#=ay#-by#
v1z#=az#-bz#
v2x#=ax#-cx#
v2y#=ay#-cy#
v2z#=az#-cz#
; Get crossproduct
cpx#=(v1y#*v2z#)-(v1z#*v2y#)
cpy#=(v1z#*v2x#)-(v1x#*v2z#)
cpz#=(v1x#*v2y#)-(v1y#*v2x#)
; Transform vector according to entity and normalize
TFormNormal cpx#,cpy#,cpz#,Entity,0
cpx#=TFormedX#()
cpy#=TFormedY#()
cpz#=TFormedZ#()
; Now we got the triangles normal
; Take the DotProduct from above normal and a distance vector
; from the camera and one of the triangles vertices
TFormPoint ax#,ay#,az#,Entity,0
camvecx#=EntityX#(Camera)-TFormedX#()
camvecy#=EntityY#(Camera)-TFormedY#()
camvecz#=EntityZ#(Camera)-TFormedZ#()
dp#=((camvecx#*cpx#)+(camvecy#*cpy#)+(camvecz#*cpz#))
If dp#>0 Then
Return True
Else
Return False
EndIf
End Function
Function TriArea(X1,Y1,X2,Y2,X3,Y3)
D = X1*Y2 + X2*Y3 + X3*Y1 - X1*Y3 - X2*Y1 - X3*Y2
Return D
End Function
;
;Cross and DotProduct functions
Function CrossProduct(x1#,y1#,z1#,x2#,y2#,z2#)
CProd\x#=(y1#*z2#)-(z1#*y2#)
CProd\y#=(z1#*x2#)-(x1#*z2#)
CProd\z#=(x1#*y2#)-(y1#*x2#)
End Function
Function DotProduct#(x1#,y1#,z1#,x2#,y2#,z2#)
DProd=((x1*x2)+(y1*y2)+(z1*z2))
Return DProd
End Function
|
| ||
| Interesting! It seems quite effective, but I haven't had time to look at the code. Good work! |
| ||
| Haven't tried the code yet, but one thing you should check in any occlusion code is what happens if one entity intersects another. They should not occlude eachother. ... Hm, impressive! :-) Now to see how you're doing it. :-) I don't suppose this works for arbitrary shapes, just cubes? I'm guessing just cubes. But even if it was just cubes, that's not bad. You'd just have to carefully set up occlusion cubes in your level. Can those cubes be rotated to any orientation? How about scaled non-uniformly? |
| ||
| Hm... you can indeed rotate the cubes andy way you wish. And it kinda looks like you may actually be able to sue any shape for an occluder, but I assume the complexity of said shape has some singificant effect on the speed? |
| ||
| Looking at the code briefly, it appears that what you're doing is creating a frustrum or a "beam" (I think Camrack used that term to describe such a system once) which you generate dynamically for each occluding object each frame. Here's an optimization you may or may not already have done... Test the colluders themselves against one another. If an occluder is occluded then everything occluded by it is also occluded by the closer volume, so you don't need to check if it is occluding anything. This will reduce the number of occluders you need to check to see if they are occluding anyhting if you have a lot of them overlapping, as you might in a real level. This being the case, that you're building planes, I guess it depends on how optimized the frustrum check is and how expensive it is to generate planes for an object. It must be pretty expensive cause this is precisely the sort of thing you need to do for shadow casting in a stencil buffer based shadow system... except you do it once for each light. Anyhow, quite a clever system. Probably been done before, but it's nice to see how fast it can be with simple occluders and a lot of entities. |
| ||
| That's a great occlution demo. Well done. That's just the sort of thing that would be great for a large city like level. |
| ||
| Here's another optimization idea. Sort the occlusion volumes nearest to farthest before testing occlusion. Doing that in addition to the other optimization I suggested of checking to see if an occlusion volume itself is occluded, makes it more likely to cull other occluders sooner rather than later. Ie, if you check an occluder in the distance first and it then turns out to be occluded by another occluded, you've done unneccessary math. |
| ||
| One last suggestion. An occluder should be smaller than an object is is standing in for. It should fit inside it. But one can also make bounding volumes which are larger than the object they contains. If the bounding volume is not occluded then the object is likely to also not be occluded. So you could first check the bounding volumes against the occluders, and then you can do a more accurate test if you wish. Though if the object you're testing is very detailed it may not be economical to test the true volume of the object against the occluders, and just go with the approximation instead. |
| ||
| Thats pretty fantastic occlusion, sweenie! I hope you continue to develop it :) |
| ||
| The big problem with this kind of occlusion method is that it relies on all occluders being convex, which is fine for levels made in Quill and CShop (as long as you can export without any surface combining going on). It probably needs to be tied in with with level creation tho. I made a similar occlusion system a while back, and something I was thinking about was whether 'wall' quads could be detected and then used as occluders. |
| ||
| I see no reason why you could not automatically divide an abritrary level up into convex chunks. I think you could just start with the first polygon and connect those that touch it in a chain until the angle between two surfaces is greater than or less than 180 degrees, whichever way you decide to calculate the angle. Hm... but if you had a sphere with a cylinder cut out of it, then with this method the entire shape would be one occluder. Is that right? Seems like it works out. And if you had a hole which only went halfway into the sphere, then the bottom cap of the hole would be a seperate occluder. Hm.... Not sure if that is neccessary or not, or if either of those is right. That would allow you to be inside of an occluder. Would that work right? Seems like it might. |
| ||
| I thought of two ways to determine if the occluder should be used or not. 1) Based on distance. The occluder must be a certain distance from the camera before it's used. The drawback of this is if the occluder is long, like a long wall or something. 2) Based on size. As i'm using a TriangleArea routine to sort the edges in clockwise order I also automatically get the area of the occluders 2D shape. If i compare the screenarea with the occluderarea i can use the occluder based on a certain percentage. For example, if the occluder covers more than 30% of the screen then use it. The occluder can be any convex shape, but the more complex the occluder is the slower it gets. I haven't tried quads yet, but with some modifications that can supported too. Currently the occludermesh must be a convex solid mesh with shared vertices. |
| ||
| We used this style of occlusion in UT2003. It's REALLY nice. The distance based optimization you talked about is really worthwhile. Once it gets a certain distance from the camera, it's so small that it's not worth calculating the occlusion for it anymore. |
| ||
| mm the example code is still 120% faster without any occlusion.. Kinda makes you wonder what use it is.. |
| ||
| Depends on the scene. If you're only occluding a few simple objects the time spent occluding them will be higher than the time you would spend to render them. Common sense, really. |
| ||
| Very nice example. I haven't dug into the code yet but I was wondering, since the view frustrum is essentially a 6 sided object like the cube, if you could use that method for frustrum culling. Sweenie 1) Based on distance. The occluder must be a certain distance from the camera before it's used. The drawback of this is if the occluder is long, like a long wall or something. Sweenie rather distance it would seem frustrum would be the limiter. If everything is hidden outside the frustrum first and removed from any list for consideration it would seem that would speed things up. |
   |