Occlusion Culling

[Vsk]

Hi, I've serched the forum for this theme and finded that hybrid was working on this feature for the engine.
how is the estate of this work?
Irrspinzt or other irr-engine has add occlusion culling?
Thanks.

[hybrid]

No progress yet. Other topics became more important, so no progress in the next time from me. And no, there are no other active Irrlicht forks anymore, they all declared themselves completely independent of Irrlicht (but in case you want to try them anyway, lightfeather has occlusion culling).

[Halifax]

Hi, hybrid, sorry for this n00bish question, but I was looking over some occlusion coloring documents and considering trying to implement it.

I was wondering how many files, a ballpark figure, would need to be edited to implement this? Is it specific to less than 4 files? Or should I be looking at editing a very large chunk of the engine.

[FuzzYspo0N]

you need to look at the engine code, where to put it etc. ur basing ur noobish question on noobish knowledge... you dont know where it goes but wnna try implement into a complex engine? :>

maybe im being an ass, but its harder then it looks. A seperate class that all the relevant files can call might help, but thats all i can think of besides actually looking at the source.

[hybrid]

It depends on which algorithm you want to implement. For the HW occlusion culling I thought about two ways to implement. Either as a scene node (testing all childs whether they are occluded, and only registering in the next cycle if they were not), or as a culling algorithm as part of the existing ones (i.e. you could choose from not only EAC_BOX, etc, but also EAC_HW_OCCLUSION). Check both possibilities and suggest some architecture for it such that it can be discussed.

[BlindSide]

hybrid, are you suggesting that the hardware occlusion culling mode will forgo the box test altogether? Or will it include the box test? I think a combination of both, doing the box test first should work better for performance, but then again I am unsure about the performance penalties of occlusion queries.

This feature should help alot in interior scenes right? Ive seen alot of projects where you are in an empty room but the framerate is miserable because of some stuff hiding behind the walls.

[Spintz]

And no, there are no other active Irrlicht forks anymore, they all declared themselves completely independent of Irrlicht

LMAO, such a nice way to say it. This doesn't sound like declaring yourself completely independent of Irrlicht -

Don't you think it's time to keep your ideas just within YOUR community? I don't think that too many people really need this kind of postings in here, nor do they really want anything from you personally. Don't know what really keeps you here. You have your engine, your people. So have fun there and don't annoy us here.

Sounds more like an Irrlicht developer pushing away valuable contributors.

[Vsk]

Something that I never undertood, what it the minium occlusion unit?
I mean, poligons?, vetices?, entire meshes?
I think it could be polygons, in the case of course that previously a box frustum test was made for reduce the total object to check. (this test can be don for enterie mesh, like actually irrlicht does).
But I am right about my thought or no?
Thanks.

[BlindSide]

I think it is actually per-pixel, but im not 100% sure.

Basically, you send an occlusion query for a specified object, and if one pixel is on the screen then it passes.

(Ooooh, what is "Demon" )

[hybrid]

BlindSide, I thought about allowing to enable a combination of culling techniques (using a bitmask in the AutomaticCulling member). We'd sort those techniques by complexity and do all culling checks which are enabled until one succeeds or all are done. This would allow to make fast BOX tests while the expensive occlusion culling would only be done if the simple tests have failed.
Occlusion culling (those supported in the gfx vendor drivers) will cull also smaller meshes outdoors when they are completely occluded by large meshes in front. But of course indoor scenes (where lots of meshes are simply occluded because they are in a different room) will have better benefits. However, other culling techniques (such as portals and bsp) also provide good results in those cases - and hw occlusion culling needs to render the scene at least once every few frames.

[Halifax]

you need to look at the engine code, where to put it etc. ur basing ur noobish question on noobish knowledge... you dont know where it goes but wnna try implement into a complex engine? :>

maybe im being an ass, but its harder then it looks. A seperate class that all the relevant files can call might help, but thats all i can think of besides actually looking at the source.

It is not based on noobish knowledge. I know full well the general position on where they should go, but I wanted a ballpark figure until I got serious about it.

At any rate, I was considering a process presented by Insomniac Games, which is basically the algorithm that hybrid suggested. I don't think I would implement it as a SceneNode though, because that just seems like some uneeded overhead, and overall more difficult. I would implement it in the isCulled() function as you said with EAC_HW_OCCLUSION.

EDIT: Okay, scratch that. I am considering a SceneNode because the occlusion algorithm will need constant access to all the nodes to build its database. I will write some ruff documents tonight maybe and see where to go with this, and talk it over with you hybrid.

[Vsk]

[offtopic]
I didn't know that irrspinzt and irrlicht were fighted. I thought each one take stuff from each other.
[/offtopic]

BlindSide I've read some oclussion culing alg (on high level) and I belive that only one was using pixel, the rest used z buffer or other technis. but I think you reffer to the ones that make a black in white mapping for later compare to other objetc if they are occluded right?

This is an importante feuture to add to irrlicht. I'd do it, but I am short of time and realy suck with low level manage. But if I have some time I will study and try to add some occlusion algorith for irrlicht comunity.

Byt the way is the frustum box culling working properly in 1.3.1. I have some problems. ¿The fov and node camera scale could make problems in the frustum?

Thanks.

[Halifax]

Alright so here is just a ruff document on my thoughts about an occlusion culling algorithm.

Code: Select all

Occlusion Culling White Paper

Description:
	I will try to give a brief overrun of what goes on with this occlusion culler. I will also try to explain the downfalls, and possible improvements, etc. 

	Okay to start of, it would be implemented as a SceneNode. It would contain the list of the scenenodes in the scene, a list of node bounding boxes, a list of cull boxes, and that should be all. Now this tests until all nodes are either culled or drawn. The culler runs through the nodes, and takes one node as it steps over the list. It retrieves the bounding box of that node, and tests it against the cull boxes to see if it is inside any of them. If it is not then the object is drawn, and added to the cull list. Now the expensive part comes where you have to extrude the far plane of the bounding box to infinity. That is how a cull box is defined, a near plane with a far plane placed at infinity based of the axis provided by the angle the camera is looking at the box. It continues over the nodes with this process.

Expensive parts:
	- Testing the node bounding box against all cull boxes
	- Extruding the bounding box far plane

Downfalls:
	- A 2 million poly mesh could be lying behind the wall with only 2,000 polygons showing at the top and it would still be drawn. This is where artist content would come into creation. Long, moby objects should not be in the level.

Code:
For (all nodes in the scene)
	getNodeFromList
	getNodeBoundingBox
	If not (nodes in the cull box list)
		testObjectAgainstAllCullBoxes
		If (node is inside a cull box)
			continue
		Else
			drawNode
			extrudeNodeBoundingBoxFarPlane
			addNodeToCullBoxList
		EndIf
	Else
		drawNode
		extrudeNodeBoundingBoxFarPlane
		addNodeToCullBoxList
	EndIf
EndFor

Improvements:
	I list these as improvements because they are possibly quite expensive. Although the tradeoffs might even it out.

Here’s how it goes though, the problem above is that you aren’t using a sorted position list which forces you to make cull boxes. The first improvement would be to sort that list, and then instead of using cull boxes you use cull planes. That means there is no need for extruding anymore. This also gives way to the improvement that you can stop culling at any time when the plane is defined as outside of the viewing frustum! One problem still holds in the fact that you would have to hold a list of all the cull planes, and that could kill with lots of small objects, but would work fine with realistic levels. So anyway, you would just keep a list of the cull planes, and test whether a nodes bounding box is fully behind the cull plane or not.

Improvements:
	- Take away extrusion
	- Using plane-to-box tests instead of box-to-box test
	- The culler can stop if a node blocks the entire scene. (A wall hiding 2 million polys behind it)

Expensive parts:
	- Quite possibly the sorting, unless a good algorithm is used. Although an improvement to that would be just holding a Z buffer for every node, then sorting that list with Quick Sort or Heap Sort, and transverse the effects of that onto the node list.

Downfalls:
	- Still the same as the first algorithm.

Code:
sortListOfNodes
For (all nodes in the scene)
	getNodeFromList
	getNodeBoundingBox
	If not (nodes in the cull plane list)
		testObjectAgainstAllCullPlanes
		If (node is inside a cull box)
			continue
		Else
			drawNode
			addNodeBoundingBoxNearPlaneToCullPlaneList
			If (Cull Plane > Frustum Plane)
				return
		EndIf
	Else
		drawNode
		addNodeBoundingBoxNearPlaneToCullPlaneList
	EndIf
EndFor

[bitplane]

[offtopic]
I didn't know that irrspinzt and irrlicht were fighted. I thought each one take stuff from each other.
[/offtopic]

Actually it's just Spintz and Hybrid fighting as usual. I'm hoping it's just a nice bit of internet drama for us to enjoy and Spintz sticks around. I actually enjoy the bickering (I'm sure others do too) and I'd encourage it if they both didn't get so upset

On topic: I think software occlusion culling is probably best left to the software drivers, sorting polygons can't be that efficient. Maybe a BSP type node for occlusion of whole nodes would be useful, or something like Halifax describes. Also perhaps the culling types should be flags, so we can have more than one active at a time.

[hybrid]

I don't think that you can call my post "fighting", it's basically the statement found on the irrSpintz homepage, with less words.
And no, I cannot say that I'm completely independent of Irrlicht, especially not when it comes down to 3d rendering
However, I thought that we were already through with this, moreover it's again way too offtopic for this thread.
So feel free to correct any wrong statement said about any engine, the rest does not really belong here.