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.