KDNode¶

giant.ray_tracer.kdtree:

class giant.ray_tracer.kdtree.KDNode(self, surface=None, _left=None, _right=None, _bounding_box=None, _order=0, _id=None, _id_order=None, _centers=None)¶

A class to represent a node in a KDTree

A node represents a spatial subdivision of the geometry that is contained in the scene. It is comprised of an axis aligned bounding box, specifying the extent of the geometry contained with the node and its children, along with references to its children (if any), the geometry contained locally in the node (if any), and a unique identity for the node in the tree.

Nodes are not typically used directly by the user, instead you should interact with the KDTree, which acts as a container/manager for all of the nodes that make up a tree.

Each node is described by a unique identifier id. Typically, this identifier is encoded into a large integer of the following form

xxxxxxxxyyyyyyyy
|--id--||facet#|
|---id_order---|

where id is the id of the node, facet# is reserved to specify a facet number within the node with a length of order digits, and there are a total of id_order digits used to represent the ids. This form is used for checking that we are not intersecting the same triangle again (due to finite precision issues) when we are doing a bounce or other tracing that starts already on the surface. For more details on how this works refer to Scene.trace().

Parameters:

surface (Optional[Surface]) – the surfaces that are to be stored in the node and its children
_left (Optional[KDNode]) – The left child of this node. This is only used for pickling/unpickling purposes and is typically not used by the user
_right (Optional[KDNode]) – The right child of this node. This is only used for pickling/unpickling purposes and is typically not used by the user
_bounding_box (Optional[AxisAlignedBoundingBox]) – The bounding box for this node. This is only used for pickling/unpickling purposes and is typically not used by the user
_order (Optional[int]) – The order for this node (the maximum number of faces in the geometry for any node in the current KDTree). This is only used for pickling/unpickling purposes and is typically not used by the user
_id (Optional[int]) – A unique identifier for this node. This is only used for picling/unpickling purposes and is typically not used by the user.
_id_order (Optional[int]) – The order for this node (the maximum number of digits in any ID for any node in the current KDTree). This is only used for pickling/unpickling purposes and is typically not used by the user.
_centers (np.ndarray) – The centers of the surfaces that are being current split. This is not typically used by the user.

left: KDNode | None¶: The left child of this node (containing the geometry that is less than the median) If there are no children this will be None and this is probably a leaf node with geometry in surface.

right: KDNode | None¶: The right child of this node (containing the geometry that is greater than the median) If there are no children this will be None and this is probably a leaf node with geometry in surface.

bounding_box: AxisAlignedBoundingBox¶

The AxisAlignedBoundingBox specifying the extent of the space covered by this node and its children.

The bounding box contains both any geometry primitives contained in the node, as well as the bounding boxes of all children nodes, therefore if a ray does not intersect the bounding box of the node, it will not intersect any of its dependents (children or geometry)

has_surface: bool¶: A flag specifying whether this is a leaf node (True, contains geometry) or is a branch node (False, only contains children nodes).

surface: Surface | None¶

The surface object specifying the geometry for this node if it is a leaf node or None.

If this is a leaf node then there should be no children nodes (left and right should both be None).

id: int¶

The unique identifier for this node as an integer.

This is guaranteed to be unique for every node in a tree (it is not guaranteed to be unique across nodes in different trees).

id_order: int¶: The maximum number of digits required to represent the largest ID number for an node in any given tree. See the class description for more details of what this means.

order¶: The order represents the number of digits required to represent of the maximum number of the geometry primitives contained in any relative nodes (nodes belonging to the same tree).

Summary of Methods

`compute_bounding_box`	This method computes the axis aligned bounding box for the node based off of the provided geometry primitives.
`rotate`	Rotate this node and any child nodes by `rotation`
`split`	This method is used to "grow" the tree.
`translate`	Translate this node and any child nodes by `translation`.

Navigation

Related Topics

KDNode¶