NewsForumsCodeLogsGallerySpecsSearch

Optimize render and collision speed

BlitzMax Forums/OpenGL Module/Optimize render and collision speed

Ferret(Posted 2012) [#1]
I allready do frustum culling and want to add an octree.

Should i use different octree's for rendering and collissions?
What about terrain, use a quad tree or include it in a octree?


Kryzon(Posted 2012) [#2]
Hi. When you get to this theoretical level you have a lot of literature and online discussions to draw from.

Apart from the Game Programming Gems series, which deal with this 'scene management' subject thoroughly with practical articles (i.e. things you can actually add to your engine), you can find online resources at places like GamaSutra or more ideally, Gamedev.NET.

A few samples:
http://www.gamedev.net/topic/138216-octree-questions/
http://www.gamasutra.com/view/feature/131625/octree_partitioning_techniques.php
http://www.gamasutra.com/view/feature/131801/occlusion_culling_algorithms.php
http://www.gamerendering.com/category/scene-management/
http://www.flipcode.com/archives/Frustum_Culling.shtml

http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/?view=archive
http://www.gamedev.net/page/resources/_/technical/game-programming/?view=archive

PS: Terrains consist mostly of planar geometry. A Quadtree should be best at optimizing rendering for it.

Last edited 2012


Kryzon(Posted 2012) [#3]
You might also be interested in Klepto2's MiniB3D Extended 0.41 BETA; it seems to implement Octrees:

MB3D Ext 0.41 Beta: http://www.sherrox.com/miniB3Dext041beta.zip (has basic Octree functionality)

MB3D Ext 2: http://code.google.com/p/minib3dextended/downloads/list (does not have Octrees but has other cool stuff)


matibee(Posted 2012) [#4]
I've just come up with an octree implementation that I'm really pleased with as it avoids splitting triangles or storing duplicates:

[] Each node potentially has 8 children (obviously)

[] Each node stores a list of triangles (List1) that could not be held by the children because a) they pass through the splitting planes or b) it has no children (subdivision limit was reached)

[] Each node stores a list of ALL the triangles held by its children (List2)


Many lists, I know, but they are only lists of pointers.

Now recursing the octree, say for a view or collision volume would go like this..

Method FindTrianglesByVolume( volume, resultList )
    if volume is touching our bounds
        resultList.AddLast( List1 ) ' our contained triangles
        for each child
             child.FindTrianglesByVolume( volume, resultList )
        next
    else if volume contains our bounds
        resultList.AddLast( List1 ) ' our contained triangles
        resultList.AddLast( List2 ) ' the triangles held in our children, so no need to recurse
    end if 
End Method


Potentially retrieving hundreds or thousands of triangles just by adding a few TList pointers to another TList.

Using the octree goes like this.. (pseudocode)

resultList:TList <-- is a list of lists-of-triangles

octree.FindTrianglesByVolume( volume, resultList )
for l:TList = eachin resultList
   for t:Triangle = eachin l
       t.Draw()
    next
next


I doubt it's original but it works very well for my needs :)

I'm afraid the source is quite embedded into the rest of my project (Vertex3d, Triangle3d, fuzzy float compares etc etc) to post it all here but the basic octree code is below. It gets a lot done for a couple of pages of code.

You know, looking at the BlitzArena screenshots, I would consider (within reason) having a different octree for every material in the scene (at least give it a try, and chuck the terrain triangles in there too.) That way your code would be:

' outside your render loop
For each material
  gettriangles[ materialID ]
next 

' inside your render loop
if ( triangles[ materialID ] )
  setmaterial
  drawtriangles
end if


As currently there's no way to sort triangles by their material, you could end up needlessly changing textures etc for every other triangle. Adding sorting would probably take longer than looking up each octree individually - especially if you've got many thousands of triangles to sort and only half a dozen octrees.

And of course, these octrees are only for all your static geometry.

Have fun :)



Last edited 2012


Ferret(Posted 2012) [#5]
This is great, i went from hearing about octree's to understanding and implementing them :)

It took me a while, mainly because of an error i made in assinging meshes to nodes, took me a day to figure that one out.

It works verry well for rendering, i loaded 3600 meshes with a total triangle count of over 3 million triangles, and 40K renderd.
Still need to add collisions.

Thx!