Class TOctreeNode

DescriptionHierarchyFieldsMethodsProperties

Unit

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

  • TObject
  • TOctreeNode

Overview

Fields

Public TreeSubNodes: array [boolean, boolean, boolean] of TOctreeNode;

Methods

Protected procedure PutItemIntoSubNodes(ItemIndex: integer); virtual; abstract;
Public function ItemsCount: integer;
Public procedure AddItem(ItemIndex: integer);
Public constructor Create(const ABox: TBox3D; AParentTree: TOctree; AParentNode: TOctreeNode; ADepth: integer; AsLeaf: boolean);
Public destructor Destroy; override;
Public function SubnodeWithPoint(const P: TVector3Double): TOctreeSubnodeIndex; overload;
Public function SubnodeWithPoint(const P: TVector3Single): TOctreeSubnodeIndex; overload;
Public procedure SubnodesWithBox(const ABox: TBox3D; out SubnodeLow, SubnodeHigh: TOctreeSubnodeIndex);
Public function FrustumCollisionPossible(const Frustum: TFrustum): boolean;
Public procedure PushChildrenFrontToBack(List: TOrderedList; const Position: TVector3Single);
Public procedure PushChildrenBackToFront(List: TOrderedList; const Position: TVector3Single);
Public procedure PushChildren(List: TOrderedList);

Properties

Protected property InternalParentTree: TOctree read FParentTree;
Protected property InternalParentNode: TOctreeNode read FParentNode;
Public property ItemsIndices: TIntegerList read FItemsIndices;
Public property IsLeaf: boolean read fIsLeaf write SetLeaf;
Public property MiddlePoint: TVector3Single read fMiddlePoint;
Public property Box: TBox3D read fBox;
Public property BoundingSphereCenter: TVector3Single read FBoundingSphereCenter;
Public property BoundingSphereRadiusSqr: Single read FBoundingSphereRadiusSqr;
Public property Depth: integer read fDepth;

Description

Fields

Public 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

Protected 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).

Public 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.

Public 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.

Public 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.

Public destructor Destroy; override;
 
Public 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.

Public function SubnodeWithPoint(const P: TVector3Single): TOctreeSubnodeIndex; overload;
 
Public procedure SubnodesWithBox(const ABox: TBox3D; out SubnodeLow, SubnodeHigh: TOctreeSubnodeIndex);
 
Public function FrustumCollisionPossible(const Frustum: TFrustum): boolean;

Simple check for frustum collision.

Public procedure PushChildrenFrontToBack(List: TOrderedList; const Position: TVector3Single);

Push children nodes (use this only for non-leafs) into the List.

Public procedure PushChildrenBackToFront(List: TOrderedList; const Position: TVector3Single);
 
Public procedure PushChildren(List: TOrderedList);
 

Properties

Protected property InternalParentTree: TOctree read FParentTree;
 
Protected property InternalParentNode: TOctreeNode read FParentNode;

Parent node of the octree. Nil for the root node.

Public 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.

Public 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.

Public 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.

Public 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.

Public 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.

Public property BoundingSphereRadiusSqr: Single read FBoundingSphereRadiusSqr;
 
Public property Depth: integer read fDepth;
 

Generated by PasDoc 0.13.0 on 2014-08-30 12:10:37