Let;s talk about scenegraphs

We had a discussion like this on here a while ago, but I can't find it and I was busy at the time. What I am looking for is a technique to keep the world object handling limited to the AABB of the camera frustum so that a scene with 500 visible object and 10,000 total objects will handle about the same speed as a scene with 500 objects. First let me establish a few ground ideas.

You have to have a huge number of objects and a very large scene many times bigger than the camera view range before scenegraphs provide any benefit.

For our purposes the world will be considered a 2D area and the y axis (height) will be ignored. The vertical span of almost any scene is insignificant compared to the horizontal distance.

Each entity has a known AABB, center, and radius. We want to avoid even having to go through a complete list of entities, since that itself would cause considerable slowdown with thousands of objects.

Here is our scene. The red rectangle represents the area we are interested in. The black dots are entities with different radii. We want to find all entities that lie inside or partially intersect the rectangle:


I have a technique worked out that uses an array of sectors, but I am more interested in a binary search. What would be really cool is a 2-dimensional TMap where I can grab all entities between points x0,z0 and x1,z1.

Let's assume the entity radii are negligible, and just work with their positions. We can sort all entities in an X TMap by their x position and a z TMap by their Z position. We can even return all entities within a certain range on both TMaps. But how to combine the results of the X and Z axes in a fast way?

Here the blue area represents the area that any entity within would be returned in an x axis query. The green is the z result. The red is the desired combination of the two, eliminating all entities not found in the other results.


I can handle everything up to the combination of the results from the TMap. It's easy to retrieve a TMap range of nodes.

Then the final step of elimination would be a sphere test for each remaining entity against the camera frustum.

Hello.

¿Using arrays of arrays?

One array ordered by X. Each element of this array are another array ordered by Z
You select first for X and after traverse each selected elements for Z.

Bye,
Paposo

There are different approaches.

Paposos looks like a variant of a scanline algorithm which will definitely work.

A different approach would be the usage of a quad tree (as you are only interested in 2D dimensions)
If we are talking of your engine here: as you use a physics system behind, you might consider to checkout if it provides such a feature as well, otherwise you potentially do twice the same work, as physics, at least newer newton and physx, need such algorithms for fast collision testing and resting

Wouldn't you use like a BSP or Octree to divide up the space and make it easy to search? ie the Octree acts like bounding boxes?

Or maybe construct a linked list `web` of objects, linked based on their physical locations to each other, so that you are then basically doing a lookup of all connected items within a given coordinate area?

You guys are all thinking in sector-based approaches, which are easy to visualize, but sort of more complicated. With a binary search, the size of the world or the number of sectors doesn't matter. It just works automatically with no adjustment of sectors size, initialization, etc. And it doesn't have the problem of efficiency of the sector size.

The scanline approach is pretty much what I was doing before. Each entity's position is just rounded off to find which sector it is in, and that information saved. But it requires a lot of data storage and a defined world size, and the technique I am describing feels a lot cleaner and simpler.

With the binary search I am describing, all entities would always be listed in order on the x axis:

entity2 - entity3 - entity 1 - entity0 - entity4

And on the z axis:

entity1 - entity2 - entity3 - entity4 - entity0

A query of all entities within the range x0-x1 might return this:
entity3 - entity1 - entity0

And a query of all entities within the range z0-z1 might return this:
entity2 - entity3 - entity4

We would then eliminate entities 4,1,0,2 from the results, since they do not occur in both results, and we would be left with entity3 as the only one within the 2D range in question.

I like it, very fast and efficient, but how would one pick up the entities that lie outside your box but overlap ?

After thinking about it, I suppose each entity's bounding box coordinates would just be added to the list and sorted, and would work the same as each entity's origin.

It's great, I like it !

I would only consider the entity position. Even a large mesh's radius would be insignificant compared to the size of the camera frustum. It would be up to the artist to make sure an enormous building, for example, is broken up into small enough pieces. We're talking like STALKER-size buildings that span a quarter mile. If two entities occur at the same x and/or z position, you just sort them with the super/Object sort method, which I believe just compares their memory addresses or handle numbers. It wouldn't matter how those two objects were sorted, as long as it was always the same.

This could be used to retrieve the entities within any arbitrary AABB of any size, in a simpler way than octrees or things with fixed sectors sizes.

The only problem is how to test the results of the X and Z queries against each other, in a non-linear way? Maybe take the X results, insert them all into a temporary TMap sorting them by Z position, then get the objects within the Z range from that TMap? That seems like a lot of data sorting.

Maybe I can temporarily cut off the ends of the z TMap, then check each X result to see if it occurs in the trimmed z tmap. The z-check would be binary, but going through the X results would be linear, and it doesn't feel right.

I think what's really needed is some kind of 2-dimensional TMap so a 2D range of nodes can be retrieved. But the TMap source is pretty hard to visualize, and a 2D version...ugghhh. Mark, save me.

The only problem is how to test the results of the X and Z queries against each other, in a non-linear way?

So your thinking perhaps: Sort z, Step thru x and binary search z for the match?

Are the objects static or dynamic ?

I can see this working in 2d or 3d, and the sorting goes hand in hand with the binary searches, and feels right to me.

An object would just have its node position resorted any time the object moved. That would just be a matter of removing a TMap node and inserting a new one with the new position, fast enough for real-time. So static or dynamic, it would not matter. I don't think a hierarchical tree would work, because it would require rebuilding the tree any time something moved.

So close, but I can't seem to find a way to combine the axis data, either as the result of two separate binary searches, or combining them into a sort of quad search. I can't grab a 2D area quickly without sorting out a lot of outliers on either axis in a linear method.

I drew it out on paper and tried starting with the outer nodes on each axis and tracing their neighbors inwards, but it is possible to create isolated nodes, so that approach is not right.

unless I misunderstand... just take the x results and insert them into a TMap by "object"... then take the z results and see if the same object already exists... if it does, that's an object you're looking for.

Yes, that is possible. The question is whether that approach is fast enough to be of use in real-time. It would require linear sorting of perhaps 10x the number of objects within the rectangle. What it basically amounts to is a binary search on one axis followed by a linear search on the other.

Here's a test I made using a scene graph with a fixed-size array. It sorts 100,000 points onscreen and only draws those within a rectangle. As you can see, the scenegraph mode is many times faster than the linear method, but it requires tuning of the sector size and how many objects there are. There's definitely an optimal balance:
http://www.leadwerks.com/post/SceneGraph.zip

Here's the source code. It's kind of nice because it is so simple. You just create a scenegraph with the scale and subdivision you want, then insert objects of any type into it based on their x and z positions using InsertSceneNode(). You can then use ForEachSceneNodeDo() specifying a rectangle and a callback function to perform for each object within the range. This is much faster than adding all the objects to a list. If you delete an object, just use RemoveSceneNode() and if you move it, just call InsertSceneNode() again and the program will detect the old scene node and remove it automatically.

Any values that overrun the edges of the scenegraph get clamped to the scenegraph area, so you don't have to worry about going outside the allowed area. Also, the scenegraph is centered at 0. In most cases you can just create it with the scale you want (number of sectors/size of the area you want covered) and then insert your entities based on their actual x,z positions.

Strict

Rem
bbdoc:
EndRem
Type TSceneGraph
	Field grid:TMap[,]
	Field size
	Field scale:Float
	Field nodes:TMap=New TMap
	
	Method sector:TMap(grid_x,grid_y)
		grid_x=Max(0,grid_x)
		grid_x=Min(size-1,grid_x)
		grid_y=Max(0,grid_y)
		grid_y=Min(size-1,grid_y)
		If Not grid[grid_x,grid_y] grid[grid_x,grid_y]=New TMap
		Return grid[grid_x,grid_y]
	EndMethod
	
EndType

Rem
bbdoc:
EndRem
Function CreateSceneGraph:TSceneGraph(size,scale#=1.0)
	Local graph:TSceneGraph=New TSceneGraph
	Local grid:TMap[size,size]
	graph.grid=grid
	graph.size=size
	graph.scale=scale
	Return graph
EndFunction

Rem
bbdoc:
EndRem
Function InsertSceneNode(graph:TSceneGraph,o:Object,grid_x,grid_y)
	grid_x=grid_x*graph.scale+graph.size/2
	grid_y=grid_Y*graph.scale+graph.size/2
	Local map:TMap=TMap(MapValueForKey(graph.nodes,o))
	If map MapRemove(map,o)
	If Not graph.grid[grid_x,grid_y] graph.grid[grid_x,grid_y]=New TMap
	graph.grid[grid_x,grid_y].insert o,o
	MapInsert graph.nodes,o,graph.grid[grid_x,grid_y]
EndFunction

Rem
bbdoc:
EndRem
Function RemoveSceneNode(graph:TSceneGraph,o:Object)
	Local map:TMap=TMap(MapValueForKey(graph.nodes,o))
	If map
		MapRemove(map,o)
		MapRemove(graph.nodes,o)
	EndIf
EndFunction

Rem
bbdoc:
EndRem
Function ForEachSceneNodeDo(graph:TSceneGraph,grid_x,grid_y,width,height,Callback:Int(o:Object))
	Local x,y
	Local o:Object
	
	grid_x=Floor(grid_x*graph.scale)+graph.size/2
	grid_y=Floor(grid_y*graph.scale)+graph.size/2
	width=Ceil(width*graph.scale)
	height=Ceil(height*graph.scale)
	
	If grid_x>graph.size-1 Return
	If grid_y>graph.size-1 Return
	If width<=0 Or height<=0 Return
	If grid_x<0
		width:+grid_x
		grid_x=0
	EndIf
	If grid_y<0
		height:+grid_y
		grid_y=0
	EndIf
	If grid_x+width>graph.size-1 width=graph.size-1-grid_x
	If grid_y+height>graph.size-1 height=graph.size-1-grid_y
	
	For x=grid_x To grid_x+width
		For y=grid_y To grid_y+height
			If graph.grid[x,y]
				For o=EachIn graph.grid[x,y].values()
					If Callback(o)=False Return
				Next
			EndIf
		Next
	Next
	
EndFunction




'---------------------------------------------------------
' Test Program
'---------------------------------------------------------

Graphics 512,512,0

Local list:TList=New TList

Type Point
	Field x,y
EndType

Local sectors=8
Local points=10000

Local scale#=sectors/512.0

Local graph:TSceneGraph=CreateSceneGraph(sectors,scale)

Global scenex,sceney

Local p:point

For Local n=1 To points
	p=New point
	p.x=Rand(0,511)
	p.y=Rand(0,511)
	InsertSceneNode(graph,p,p.x-256,p.y-256)
	list.addfirst(p)
Next

Local modename$="Scenegraph"

Global size=128,hsize

MoveMouse GraphicsWidth()/2,GraphicsHeight()/2

Global FPSLASTUPDATETIME

Local mode,time

While Not KeyHit(KEY_ESCAPE)

	If AppTerminate() End
	
	Cls()
	
	scenex=MouseX()
	sceney=MouseY()
	
	If KeyHit(KEY_MINUS) size=Max(10,size-10)
	If KeyHit(KEY_EQUALS) size:+10

	hsize=size/2
	
	Select mode
	Case 0
		ForEachSceneNodeDo(graph,scenex-hsize-256,sceney-hsize-256,size,size,Callback)
	Case 1
		For p=EachIn list
			If pointinrect(p.x,p.y,scenex-hsize,sceney-hsize,size,size) Plot p.x,p.y
		Next
	EndSelect
	
	If KeyHit(KEY_SPACE)
		mode=Not mode
		Select mode
		Case 0 modename$="Scenegraph"
		Case 1 modename$="Linear"
		EndSelect
	EndIf
	
	time=MilliSecs()
	
	SetColor 255,255,255
	DrawText "UPS: "+FPS(),0,0
	DrawText "Mode: "+modename,0,20
	DrawText "space: toggle mode",0,40
	DrawText "-/+: change rect size",0,60
	Flip 0
	
	FPSLASTUPDATETIME=FPSLASTUPDATETIME+(MilliSecs()-time)

Wend

End

Function Callback:Int(o:Object)
	Local p:Point=Point(o)
	If Not pointinrect(p.x,p.y,scenex-hsize,sceney-hsize,size,size) Return 1
	Plot p.x,p.y
	Return 1
EndFunction

Function PointInRect:Int(x0,y0,x1,y1,w,h)
	If x0<x1 Return 0
	If y0<y1 Return 0
	If x0>x1+w Return 0
	If y0>y1+h Return 0
	Return 1
EndFunction

Function FPS#(frequency=200)
	Global FPSFRAMECOUNT
	Global FPSLASTCOUNT#
	Local time=MilliSecs()
	FPSFRAMECOUNT=FPSFRAMECOUNT+1
	Local elapsed#=time-FPSLASTUPDATETIME
	If elapsed>=frequency
		FPSLASTCOUNT=FPSFRAMECOUNT/elapsed*1000.0
		FPSFRAMECOUNT=0
		FPSLASTUPDATETIME=time
	EndIf
	Return FPSLASTCOUNT
End Function 

*ahem*

Yoink! I'll be keeping that. I'll be damned if I know how it works, but it works well.

Here's a slightly updated version. It fixes a potential crash and also uses a more intuitive scaling method.

This isn't really anything all that advanced, but it works and it's simple. If you have the right sector size relative to the camera range, there's really no limit to how big your scene can be, once it gets out of the camera range. I ran a scene with 1,000,000 objects and 300,000,000 polys and since it only drew what was in the immediate area, I got the maximum framerate.

Import leadwerks.mathex

Rem
bbdoc:
EndRem
Type TSceneGraph
	Field grid:TMap[,]
	Field size
	Field scale:Float
	Field nodes:TMap=New TMap
	
	Method sector:TMap(grid_x,grid_y)
		grid_x=Max(0,grid_x)
		grid_x=Min(size-1,grid_x)
		grid_y=Max(0,grid_y)
		grid_y=Min(size-1,grid_y)
		If Not grid[grid_x,grid_y] grid[grid_x,grid_y]=New TMap
		Return grid[grid_x,grid_y]
	EndMethod
	
	Method Draw()
		Local x,p#
		glBegin GL_LINES
		For x=0 To size
			p=Float(x)/Float(size)
			glVertex3f (x-size/2.0)/scale,0,size/2.0/scale
			glVertex3f (x-size/2.0)/scale,0,-size/2.0/scale
		Next
		For x=0 To size
			p=Float(x)/Float(size)
			glVertex3f size/2.0/scale,0,(x-size/2.0)/scale
			glVertex3f -size/2.0/scale,0,(x-size/2.0)/scale
		Next
		glEnd
	EndMethod
	
EndType

Rem
bbdoc:
EndRem
Function CreateSceneGraph:TSceneGraph(sectors,size#)
	Local graph:TSceneGraph=New TSceneGraph
	Local grid:TMap[sectors,sectors]
	graph.grid=grid
	graph.size=sectors
	graph.scale=Float(sectors)/size
	Return graph
EndFunction

Rem
bbdoc:
EndRem
Function InsertSceneObject(graph:TSceneGraph,o:Object,grid_x,grid_y)
	grid_x=Round(Float(grid_x)*graph.scale+graph.size/2.0)
	grid_y=Round(Float(grid_Y)*graph.scale+graph.size/2.0)

	If grid_x<0 grid_x=0
	If grid_y<0 grid_y=0
	If grid_x>graph.size-1 grid_x=graph.size-1
	If grid_y>graph.size-1 grid_y=graph.size-1

	Local map:TMap=TMap(MapValueForKey(graph.nodes,o))
	If map MapRemove(map,o)
	If Not graph.grid[grid_x,grid_y] graph.grid[grid_x,grid_y]=New TMap
	graph.grid[grid_x,grid_y].insert o,o
	MapInsert graph.nodes,o,graph.grid[grid_x,grid_y]
EndFunction

Rem
bbdoc:
EndRem
Function RemoveSceneObject(graph:TSceneGraph,o:Object)
	Local map:TMap=TMap(MapValueForKey(graph.nodes,o))
	If map
		MapRemove(map,o)
		MapRemove(graph.nodes,o)
	EndIf
EndFunction

Rem
bbdoc:
EndRem
Function ForEachSceneObjectDo(graph:TSceneGraph,Callback:Int(o:Object),grid_x#=0,grid_y#=0,width#=-1,height#=-1)
	Local x,y,x2,y2
	Local o:Object
	
	If width=-1
		
		For o=EachIn graph.nodes.Keys()
			If Callback(o)=False Return
		Next
		
	Else
		x2=Ceil(Float(grid_x+width)*graph.scale)+graph.size/2
		y2=Ceil(Float(grid_y+height)*graph.scale)+graph.size/2
		grid_x=Floor(Float(grid_x)*graph.scale)+graph.size/2
		grid_y=Floor(Float(grid_y)*graph.scale)+graph.size/2
		
		If grid_x>graph.size-1 Return
		If grid_y>graph.size-1 Return
		If width<=0 Or height<=0 Return
		
		If grid_x<0 grid_x=0
		If grid_y<0 grid_y=0
		
		If x2>graph.size-1 x2=graph.size-1
		If y2>graph.size-1 y2=graph.size-1
		If x2<=0 Return
		If y2<=0 Return
		
		For x=grid_x To x2
			For y=grid_y To y2
				nodes:+1	
				If graph.grid[x,y]
					For o=EachIn graph.grid[x,y].values()
						If Callback(o)=False Return
					Next
				EndIf
			Next
		Next
		
	EndIf
EndFunction



'---------------------------------------------------------
' Test Program
'---------------------------------------------------------

Graphics 512,512,0

Local list:TList=New TList

Type Point
	Field x,y
EndType

Local sectors=16
Local points=100000

Local graph:TSceneGraph=CreateSceneGraph(sectors,512)

Global scenex,sceney

Local p:point

For Local n=1 To points
	p=New point
	p.x=Rand(0,511)
	p.y=Rand(0,511)
	InsertSceneObject(graph,p,p.x-256,p.y-256)
	list.addfirst(p)
Next

Local modename$="Scenegraph"

Global size=64,hsize

MoveMouse GraphicsWidth()/2,GraphicsHeight()/2

Global FPSLASTUPDATETIME

Local mode,time

While Not KeyHit(KEY_ESCAPE)

	If AppTerminate() End
	
	Cls()
	
	scenex=MouseX()
	sceney=MouseY()
	
	If KeyHit(KEY_MINUS) size=Max(10,size-10)
	If KeyHit(KEY_EQUALS) size:+10

	hsize=size/2
	
	Select mode
	Case 0
		ForEachSceneObjectDo(graph,Callback,scenex-hsize-256,sceney-hsize-256,size,size)
	Case 1
		For p=EachIn list
			If pointinrect(p.x,p.y,scenex-hsize,sceney-hsize,size,size) Plot p.x,p.y
		Next
	EndSelect
	
	If KeyHit(KEY_SPACE)
		mode=Not mode
		Select mode
		Case 0 modename$="Scenegraph"
		Case 1 modename$="Linear"
		EndSelect
	EndIf
	
	time=MilliSecs()
	
	SetColor 255,255,255
	DrawText "UPS: "+FPS(),0,0
	DrawText "Mode: "+modename,0,20
	DrawText "space: toggle mode",0,40
	DrawText "-/+: change rect size",0,60
	Flip 0
	
	FPSLASTUPDATETIME=FPSLASTUPDATETIME+(MilliSecs()-time)

Wend

End

Function Callback:Int(o:Object)
	Local p:Point=Point(o)
	If Not pointinrect(p.x,p.y,scenex-hsize,sceney-hsize,size,size) Return 1
	Plot p.x,p.y
	Return 1
EndFunction

Function PointInRect:Int(x0,y0,x1,y1,w,h)
	If x0<x1 Return 0
	If y0<y1 Return 0
	If x0>x1+w Return 0
	If y0>y1+h Return 0
	Return 1
EndFunction

Function FPS#(frequency=200)
	Global FPSFRAMECOUNT
	Global FPSLASTCOUNT#
	Local time=MilliSecs()
	FPSFRAMECOUNT=FPSFRAMECOUNT+1
	Local elapsed#=time-FPSLASTUPDATETIME
	If elapsed>=frequency
		FPSLASTCOUNT=FPSFRAMECOUNT/elapsed*1000.0
		FPSFRAMECOUNT=0
		FPSLASTUPDATETIME=time
	EndIf
	Return FPSLASTCOUNT
End Function

I implemented a faster improved version of the above technique and added a routine that sorts any scene into batches of like meshes. Without actually rendering anything, the framerate is over 1000 FPS with one million meshes, so the sorting and culling overhead is pretty minimal.

The next step is to switch over to the instanced rendering on the GE Force 8 series. I am very curious to see what the FPS counter will read if I implement GPU batches with this scene.

I almost wet myself, will this all be integrated into LWE ?
I'd like to run that demo, can you please post it ?

Good stuff!

I'm going to implement GPU instancing, but then it will only run on the GE Force 8 series. This is not for the current engine.

Just one idea, don't know why I did not came up with this sorting method before:

Why don't you use just RadixSort / BucketSort (the books intermix them sadly a little).

Those sorting algorithms are great for sorting either strings or other elements that consists of different "bases" (numbers with 1, 10, 100, 1000 positions, strings with their positions, but as well 2D and 3D data where each coordinate is just a new basevector to a vector space).
The only thing you would need to do there is to decide on the most usefull "bucket size" ie the units in world space which form a bucket / sector


RadixSort is one of the fastest sort algorithms known, it can be programmed in a parallel way without too many problems and above all it is not comparision based like others which further reduces the workload

Hi,

BSP/Quadtree/OctTree will be as fast as anything TMap based, as they are all essentially 'log(n)' algorithms. QuadTrees and OctTrees are really just 'unrolled' BSP trees.

Done right, a binary tree based geometric algorithm will be faster than a TMap algorithm because it knows more about the data - but the complexity will be the same so it will scale the same.

However, there is a practical 'constant time' solution to this given that you're essentially working in 2D:

1) Create an x/z array of lists, where each element contains a list of entities that intersect the x/z cell.

2) At rendertime, manually render a top-down 'shadow' of the view frustum on to the array so that you can work out which array cells lie within the frustum.

3) Render the stuff within each 'visible' array cell.

This is *constant complexity*, which means it doesn't matter how big the scene, it will be the same speed (ignoring array size issues!).

Mark, that is exactly what I have done. :)

Although a hierarchal approach could potentially save time and provide finer culling in some circumstances, I have found that overall the 2D array approach is much faster. I mean, it's pretty much instantaneous. You can add a single entity to multiple cells if it spans them. To avoid "grabbing" the same entity twice, just add an iterator attached to the object, so it gets skipped if it has already been set to the current function iterator.

By the way, GPU instancing gave me a free 30-40% speed boost on the GE Force 8 series, and it was very easy to implement. The way it makes you compile an array of matrices actually gave me an idea to speed up the older batched VBO approach as well.

This is pretty cool because even if the world contains 10,000,000 objects, the renderer never even sees them, and the number of objects in lists you have to go through is pretty low. Still, I have found arrays and memcopy() to be so much faster when dealing with large numbers, it would be nice to figure out a way to use them more. Of course, I am testing with an unrealistic number of objects, so maybe I should just let it be.

Good job :)

This sounds pretty remarkable. What's it for? ....

How would you go about using your method (Leadwerks) for efficient collision detection and also how would it handle a scene where every single entity is dynamic in size, shape and position?

Also same question to you Mark, how would a frustum-shaped scanline polygon-type array traversal perform for dynamic moving objects and for collision checks?

If there are lots of empty spaces between objects then you're looking at a lot of cells only to find they are empty, right? And the more objects move around, since you're using spacial partitioning you have to remove the objects from a cell and reinsert it in another (or up to 4 others)?

Is this mainly only a good technique for static scenes?

How do you go about tweaking the sectors and size for optimal performance?