Castle Game EngineIntroduction Units Class Hierarchy Classes, Interfaces, Objects and Records Types Variables Constants Functions and Procedures Identifiers |
Class TOctreeNode
Unit
CastleOctree
Declaration
type TOctreeNode = class(TObject)
Description
Octree node.
Leaf nodes store a list of indexes in ItemsIndices array. These are usuallly indexes to some array of items on TOctree. For the sake of this unit they are just some integers that uniquely describe items that you want to keep in octree leafs. The base abstract TOctreeNode class doesn't clarify what kind of items are actually kept.
Not leaf (internal) nodes have 8 children nodes in TreeSubNodes.
Each TOctreeNode also has some essential properties like Box, MiddlePoint and ParentTree.
Hierarchy
Overview
Fields
Methods
Properties
Description
Fields
 |
TreeSubNodes: array [boolean, boolean, boolean] of TOctreeNode; |
Child octree nodes, only if this is an internal node (IsLeaf = False ). When this is a leaf (IsLeaf = True ), these are all Nil .
Indexed by booleans, "true" means that given coordinate is >= than corresponding MiddlePoint coordinate. For example TreeSubNodes [true, true, true] are coordinates between MiddlePoint and Box[1].
Subnodes class is always the same as our (Self) class.
This field is read-only from outside of this unit.
|
Methods
 |
procedure PutItemIntoSubNodes(ItemIndex: integer); virtual; abstract; |
Insert given index into appropriate subnodes. This should call SubNode.AddItem(ItemIndex) for chosen TreeSubNodes (maybe all, maybe none). It all depends on what is your definition of "an octree item" – you generally want to check how given item collides with BoundingBoxes of your TreeSubNodes and call SubNode.AddItem(ItemIndex) for each SubNode that contains (al least part) of your ItemIndex.
Don't ever call this directly from subclasses of TOctreeNode. TOctreeNode internally calls it when it needs to.
You can assume here that all TreeSubNodes are <> nil. But you shouldn't assume here anything about value of IsLeaf or ItemIndices <> nil (yes, this means that this function may be internally called when the state of this object is partially invalid).
|
 |
function ItemsCount: integer; |
Number of items stored here. Same thing as ItemsIndices.Count, but has somewhat nicer name if you have Items[] property defined in a subclass. Use this only when you know that ItemsIndices <> nil.
|
 |
procedure AddItem(ItemIndex: integer); |
Insert an item into this octree node.
It takes care of the octree structure properties:
Splits a leaf node into non-leaf node if maximum number of items in leaf is exceeded (and Depth < MaxDepth).
And when you insert an item into non-leaf node, it correctly puts it into children subnodes too.
|
 |
constructor Create(const ABox: TBox3D; AParentTree: TOctree; AParentNode: TOctreeNode; ADepth: integer; AsLeaf: boolean); |
Simple constructor. Calculates MiddlePoint as a middle of the ABox, or as (0, 0, 0) if ABox is empty.
|
 |
destructor Destroy; override; |
|
 |
function SubnodeWithPoint(const P: TVector3Double): TOctreeSubnodeIndex; overload; |
In which subnode does the given point lie. Decides using MiddlePoint.
This is a simple utility, ignores what is our Box (doesn't check is P is inside Box at all), ignores if we're leaf or not.
|
 |
function FrustumCollisionPossible(const Frustum: TFrustum): boolean; |
Simple check for frustum collision.
|
 |
procedure PushChildrenFrontToBack(List: TOrderedList; const Position: TVector3Single); |
Push children nodes (use this only for non-leafs) into the List.
|
 |
procedure PushChildrenBackToFront(List: TOrderedList; const Position: TVector3Single); |
|
 |
procedure PushChildren(List: TOrderedList); |
|
Properties
 |
property InternalParentTree: TOctree read FParentTree; |
|
 |
property InternalParentNode: TOctreeNode read FParentNode; |
Parent node of the octree. Nil for the root node.
|
 |
property ItemsIndices: TIntegerList read FItemsIndices; |
Items stored at the octree node. Items are stored here (and ItemsIndices <> nil) only when this is a leaf item (IsLeaf = True ) or when ParentTree.ItemsInNonLeafNodes is True . In the latter case, we store items even in internal nodes, see TOctree.ItemsInNonLeafNodes.
Never put any items in the octree node by direct ItemsIndices.Add. Instead you must use AddItem method.
|
 |
property IsLeaf: boolean read fIsLeaf write SetLeaf; |
Is this a leaf node.
Changing this property rearranges items correctly. If you change this from False to True then all items from subnodes are correctly gathered and stored in our ItemsIndices. If you change this from True to False then subnodes are created and we insert to them our items, following the MiddlePoint rule.
|
 |
property MiddlePoint: TVector3Single read fMiddlePoint; |
Middle point of the octree node, determines how our subnodes divide the space. This is defined for leaf nodes too, since leaf nodes may have to be converted into internal nodes at some point.
Note that MiddlePoint does not need to be exactly in the middle of the octree node. This is it's default value (if you called constructor without explicitly providing MiddlePoint value), but it's not a requirement. MiddlePoint may be anywhere inside Box.
This way you can explicitly specify some MiddlePoint if you know that if will yield better hierarchical division of your scene.
When Box is empty, then value of MiddlePoint is undefined.
|
 |
property Box: TBox3D read fBox; |
Axis-aligned box in the 3D space that contains all items within this node. It's allowed that some items are actually larger and go (partially) outside of this box too (so you don't have to split one triangle into many when it doesn't fit perfectly into octree node), but it's undefined if the parts that go outside will be detected by collision routines of this node.
Special case: when this is empty, then MiddlePoint has undefined value and IsLeaf must be true.
|
 |
property BoundingSphereCenter: TVector3Single read FBoundingSphereCenter; |
Bounding sphere of this box. Right now simply calculated as the smallest possible sphere enclosing Box. So they are only a bad approximation of bounding Box, but they can be sometimes useful in stuations when detecting collision versus bounding sphere is much faster than detecting them versus bounding box.
BoundingSphereRadiusSqr = 0 and BoundingSphereCenter is undefined if Box is empty.
|
 |
property BoundingSphereRadiusSqr: Single read FBoundingSphereRadiusSqr; |
|
 |
property Depth: integer read fDepth; |
|
|