KDTree

giant.ray_tracer.kdtree:

class giant.ray_tracer.kdtree.KDTree(self, surface, max_depth=10, _root=None, _rotation=None, _position=None, _bounding_box=None, _reference_ellipsoid=None)

A KD Tree representation for accelerated tracing of surface objects with many geometry primitives using axis aligned bounding box acceleration.

A KD Tree is essentially a modifier on a Surface which makes it much more computationally efficient to trace without altering the results from the trace at all (that is tracing a Surface and a KDTree built for that surface will produce equivalent results. The acceleration is performed by dividing the surface into local sub surfaces which much fewer primitives contained in them. Each sub surface is then encapsulated by an AxisAlignedBoundingBox specifying the extent of the geometry contained in it. Each one of these subsurfaces is contained in a KDNode.

The nodes are built hierarchically, so that there is one large node at the top (the root of the tree) and then exponentially divide as you descend the tree until you reach the nodes that contain actual geometry. This structure allows very efficient tracing by dramatically decreasing the number of geometry primitives that must be traced for each ray. The wikipedia article on kd trees provides a decent description of how they work (https://en.wikipedia.org/wiki/K-d_tree) though our specific implementation varies slightly from what is described there.

Conceptually, if you don’t care about the details, the tree can be treated just like any other surface in GIANT. You can use it as a target for relative opnav, or trace rays through it however you see fit. Simply provide your Surface, call the build() method, and then use the results in a SceneObject. The only real setting you may need to worry about is the max_depth which specifies how many node levels you want to make before tracing the remaining geometry. Typically you want to set this so that there are between 10-100 remaining geometry primitives inside of the final leaf nodes in the tree (this information is provided to you if you use the ingest_shape script). If you have too many geometry primitives remaining then your tree will be inefficient. If you have too few geometry primitives remaining your tree will also be inefficient (it is sometimes a case of trial and error to find the optimal number). Just remember that when adjusting this number that it is exponential.

Parameters:

• surface (Optional[Surface]) – the surface that is to be stored in the tree. This must be a RawSurface subclass

• max_depth (int) – The maximum depth when building the tree (resulting in 2**max_depth nodes)

• _root (Optional[KDNode]) – The root node for the tree. This is only used for pickling/unpickling purposes and is typically not used by the user.

• _rotation (Optional[Rotation]) – The current orientation from the world frame to the local tree frame as a Rotation. This is only used for pickling/unpickling purposes and is typically not used by the user.

• _position (Optional[numpy.ndarray]) – The current location of the center of the tree in the world frame. This is only used for pickling/unpickling purposes and is typically not used by the user.

• _bounding_box (Optional[AxisAlignedBoundingBox]) – The bounding box for the tree. This is only used for pickling/unpickling purposes and is typically not used by the user.

• _reference_ellipsoid (Optional[Ellipsoid]) – The reference for the tree. This is only used for pickling/unpickling purposes and is typically not used by the user.

bounding_box: AxisAlignedBoundingBox

The AxisAlignedBoundingBox that fully contains the surface represented by this acceleration structure.

reference_ellipsoid: Ellipsoid

The Ellipsoid that best represents the surface represented by this acceleration structure.

root: KDNode

The KDNode that serves as the root (initial branch node) of the tree. This is where all tracing begins

surface: RawSurface

The Surface that this acceleration structure was built for as initially provided.

Note that this does not get rotated/translated with the tree, so do not expect the RawSurface.vertices or RawSurface.normals attributes to be in the current frame.

max_depth: int

The maximum depth to which to build the tree.

The maximum depth puts a limit on how many branch nodes can end up in the tree as \(\sum_{i=0}^{\text{max_depth}}2^i\). In many cases however, you will end up with less than this maximum limit since we typically don’t split nodes with less than 10 primitives in them.

order

The order for the tree, which is the same as the order of the root plus the id_order of the root.

Essentially this number represents the number of digits required to uniquely identify every geometry primitive contained in the tree.

position

The current location of the center of the tree in the world frame as a numpy array.

This is used to translate the rays into the tree frame (using the opposite) which is typically more computationally more efficient than translating the entire tree

rotation

The current orientation of the tree with respect to the world frame as a Rotation

This is used to rotate the rays into the tree frame (using the inverse) which is typically more computationally more efficient than rotating the entire tree

Summary of Methods

build	This method performs the branching of the tree down to the maximum depth.
compute_intersect	This method computes the intersects between a single ray and the surface describe by this object.
trace	This python method provides an easy interface to trace a number of Rays through the surface.
find_limbs	This method determines the limb points for a surface (visible edge of the surface) that would be visible for an observer located at observer_position looking toward scan_center_dir along the directions given by scan_dirs.
compute_limb_jacobian	This method computes the linear change in the limb location given a change in the relative position between the surface and the observer.
rotate	Rotate the tree by rotation.
translate	Translate the tree by translation.
save	Use this method to dump the tree to a pickle file.
load	Load a tree from a pickle file and overwrite this instance with that tree.