Spatial Management
by William Todd Scott · in Torque Game Engine Advanced · 02/23/2007 (7:59 am) · 3 replies
Hi all,
Just when I get some small amount of proficiency in one area, I find myself needing to explore another area that I know nothing about. :)
I am about to start digging into the engine's spatial management of objects and was hoping someone could either point me at a good writeup or give me a brief explanation of the structure.
Specifically, I am under the impression that the engine puts all objects in containers and also uses zones for bsp objects. I am trying to understand the following:
1) How exactly are containers partitioned (e.g. OctTree, QuadTree, et.c)? What determines the size of the container?
2) Are zones only used for BSPs? How do zones interact with containers?
I'm don't expect anyone to lay this all out for me, but a high level explanation of what is implemented will make digging through the code ALOT easier.
Thanks
Todd
Just when I get some small amount of proficiency in one area, I find myself needing to explore another area that I know nothing about. :)
I am about to start digging into the engine's spatial management of objects and was hoping someone could either point me at a good writeup or give me a brief explanation of the structure.
Specifically, I am under the impression that the engine puts all objects in containers and also uses zones for bsp objects. I am trying to understand the following:
1) How exactly are containers partitioned (e.g. OctTree, QuadTree, et.c)? What determines the size of the container?
2) Are zones only used for BSPs? How do zones interact with containers?
I'm don't expect anyone to lay this all out for me, but a high level explanation of what is implemented will make digging through the code ALOT easier.
Thanks
Todd
#2
This is really all I need to jump in. Looking through code without some concept of what is being implemented can be very time consuming. I appreciate you taking the time to help me (again).
Todd
02/23/2007 (9:37 am)
Thanks Stephen.This is really all I need to jump in. Looking through code without some concept of what is being implemented can be very time consuming. I appreciate you taking the time to help me (again).
Todd
#3
When objects move (::processTick(), etc), they need to determine if their bin participation status changes, and handle that via the Container system.
02/23/2007 (9:39 am)
One additional starting point: Objects are initially placed in a bin during their SceneObject::addToScene() call. Of course if reimplemented, look lower.When objects move (::processTick(), etc), they need to determine if their bin participation status changes, and handle that via the Container system.
Torque 3D Owner Stephen Zepp
In a nutshell, bins are simply the top level of optimization for collision tests, and are basic 2D boxes that separate objects by bin participation.
It's a hash table (not an array), but it's relatively simple in implementation.
--Each object is at minimum in one bin.
--Each object may be in more than one bin if it is on a bin threshold.
--Objects that are larger than the dimensions of a bin are placed in the "overflow bin".
When collision is being sorted, objects check collision against objects in their bin, as well as the overflow bin.
To be honest I'm not fully up to speed on the optimizations regarding zones, but it's a similar concept--just a way to optimize/minimize the total number of collision checks required.