kdtree¶
This cython module provides the ability to accelerate ray tracing of RawSurface objects in GIANT.
Description¶
One of the most common ways to represent a 3D object is a tessellated surface made up of small, planar geometry
primitives (usually triangles). This allows great freedom in specifying the shape of arbitrary objects at various
ground sample distances, however, because it usually takes many geometry primitives (on the order of tens of
thousands to millions) to represent objects with sufficient accuracy, ray tracing these surfaces can quickly become
prohibitively expensive (tracing thousands of rays against many geometry primitives requires a ton of work). Therefore,
we need a way to accelerate the ray tracing of surfaces by limiting the number of geometry primitives we need to check
for each ray. This is done through the KDTree.
A KDTree (or k-dimensional tree) is an acceleration structure where geometry primitives are split into smaller and
smaller groups as you traverse down the tree. These groups are represented by KDNode, where each node
contains either “left” and “right” children nodes (in which case it is called a branch node), or a small collection of
geometry primitives (in which case it is called a leaf node), plus an axis aligned bounding box which fully contains the
children nodes (if a branch node) or the geometry primitives (if a leaf node). In order to trace this structure then,
we first trace the bounding box of a node (which is much more efficient than tracing geometry primitives), which
tells us if we need to further consider the contents of the node of not. If the ray does intersect the bounding box
then we proceed to trace the left and right children nodes (if this is a branch) or the geometry primitives (if this
is a leaf) contained in the node. By doing this, we limit the number of ray-geometry primitive intersection tests that
we need to perform dramatically (many times to as low as <100), which saves a lot of computational efficiency (again,
since the ray-axis aligned bounding box check is so much more efficient than the ray-geometry primitive checks).
Use¶
Since the KDTree is simply an acceleration structure, you can use it anywhere in GIANT that you would use a
Surface (in fact, the KDTree inherits from the Surface to emphasize this point). To do
this, simply build your tree (by giving it the RawSurface that you want to accelerate and then calling the
KDTree.build()), and then use the resulting tree as your target geometry. The KDTree implements all
of the required methods for the Surface, including KDTree.trace(), KDTree.compute_intersect(),
KDTree.find_limbs(), KDTree.compute_limb_jacobian(), KDTree.rotate(), and
KDTree.translate().
Because it can take a while to build the tree initially, especially for particularly large surfaces, it is recommended
that you save the tree to a file after building it the first time, and then for future use load from the file. You can
do this using the KDTree.save() and KDTree.load() methods, or using the typical pickle interface from
Python.
It will likely be rare that you directly create a KDTree in your scripts and software when using GIANT, since
GIANT provides scripts that already build them for you and save the results to file, including ingest_shape,
tile_shape, and spc_to_feature_catalogue. We therefore recommend that you look at these first to see
if they meet your needs.
Classes
A class to represent a node in a |
|
A KD Tree representation for accelerated tracing of surface objects with many geometry primitives using axis aligned bounding box acceleration. |
Functions
This python/C helper function can be used to transverse a tree and find the ignore indices that should be used to ignore all facets sharing a particular vertex. |
|
get_facet(node, facet_id) |
|
This function describes the results of building a tree. |