KD trees are acceleration structures that store 3D points in a k-dimensional space. They provide fast lookup of elements that are close to a given location. Stored elements consist of two parts: the location vector and associated arbitrary data. All data stored in a KD tree must have the same size, but different trees may have different sizes. Sizes over about 100-200 bytes are not recommended though, to keep memory usage low and lookups fast; if more data is needed pointers to the data should be stored instead of the data itself.
KD trees are implemented as mental ray database elements. However, access and edit functions are slightly different. The main difference is that, when a KD tree is accessed or edited, a pointer to a "handle" is returned, not just the pointer in to DB element memory. This pointer (always called tree below) is only valid in the thread that has opened it - it is not possible to access a KD tree and keeping the pointer for multiple rendered rectangles because different rectangles are rendered simultaneously in different threads. For example, it is legal to access a KD tree in a shader state function in state init mode and unpinning it in state exit mode, but it is not legal to do the same in shader init or exit functions because shaders may stay initialized and in use in multiple threads until rendering finishes. mi_shaderstate_set is a good way to pass open KD tree pointers to other shaders.
Like all other data structures under shader control, KD trees cannot be used across a network of machines. Every host can create and access its own KD trees, but it cannot access or edit trees on other hosts. Although KD trees are scene elements that are identified by tags, which might indicate that they are network-transparent, they are not - there is no mechanism that synchronizes multiple writes. Any attempt to do so may overwrite some changes with others, or fail to propagate changes across the network at the right time.
miTag mi_kdtree_create(
miKdtree_type type,
miUint datasize)
The type argument must have the value miKDTREE_3D, which specifies that the tree works with 3D points in space. Future versions may allow different lookup dimensions or methods. The datasize argument is the size of the data not including the size of location coordinates, fixed for all elements of the new KD tree. The returned tag identifies the new KD tree for future accesses and edits.
struct miKdtree *mi_kdtree_edit(
miTag tag,
const void *shared_data,
miUint shared_data_size)
This opens a tree for adding new elements. The shared_data argument may point to a data structure that is stored while the KD tree is open for editing. mental ray will not use this data in any way, but pass it to the insert callback later when the tree is rebalanced (see below). The shared_data_size is the size of the structure that shared_data points to. The caller should release shared_data after mi_kdtree_edit returns, if it was allocated, because mental ray makes a copy of the data and keeps it until the next rebalancing operation (see below). Multiple simultaneous edits are allowed, mental ray resolves any conflicts automatically. However, the same tree may not be open for reading (mi_kdtree_access) an writing (mi_kdtree_edit) simultaneously, even if the conflicting access and edit happen in different threads.
miBoolean mi_kdtree_add(
struct miKdtree *tree,
const void *data,
const miScalar point[])
Add a new element to the KD tree. The tree pointer must have been obtained from a previous call to mi_kdtree_edit. The size of the stored data must agree with the data_size specified when the tree was created. The point is the 3D position where the data will be stored. This function is fast, the element is added to the buffer of elements scheduled for adding. The function returns miFALSE on failure, for example if tree comes from mi_kdtree_access instead of mi_kdtree_edit.
Since mi_kdtree_add is much faster than mi_kdtree_edit, it is a good idea to add as many points as possible inside an edit/unpin bracket. Do not edit, add, unpin for every point.
miBoolean mi_kdtree_unpin(
struct miKdtree *tree)
This function ends accessing or editing. Every call to mi_kdtree_access and mi_kdtree_edit should have a corresponding mi_kdtree_unpin. The tree pointer, which must have been obtained from an access or edit, becomes invalid. However, if the KD tree is not unpinned until the end of the job (ie. a photon bundle or a rendered rectangle), this is done automatically. This automatic unpinning should be used with care; while keeping the tree accessed or edited for a long time is efficient because the add function is faster than the access and edit functions, it does not protect the called from simultaneous access and edit, which is illegal. The function returns miTRUE; there are currently no failure modes.
typedef miBoolean ((miKdtree_insert_callback)
(void *callback_data,
void *data,
miScalar point[],
const void *shared_data));
struct miKdtree *mi_kdtree_access(
miTag tag,
miKdtree_insert_callback *callback,
void *callback_data)
Opens a KD tree for read-only lookups or iteration over all elements. Simultaneous access calls for different KD trees, identified by different tags, are legal. The returned tree pointer identifies the accessed KD tree until the the access is terminated with a call to mi_kdtree_unpin.
After a tree was edited and points were added, it requires a processing phase called rebalancing. Rebalancing is an expensive operation, and mental ray tries to defer it as long as possible, in case another point gets added later. However, accessing the tree for lookup requires a rebalanced tree, so the rebalancing phase occurs when mi_kdtree_access is called.
Rebalancing integrates each point previously stored with mi_kdtree_add, and not yet integrated by a previous rebalance, into the KD tree. If a nonzero callback argument is specified, this callback will be called for each point to integrate. The callback may modify the point and data fields of the point, which were both specified with mi_kdtree_add. The callback also receives the shared_data structure specify in the last mi_kdtree_edit call. Finally, the callback receives the opaque callback_data pointer from mi_kdtree_access; this can be used to pass a C++ this pointer to provide context. If the callback returns miFALSE, the point is rejected and not added.
For example, the callback may be used for energy renormalization. Light sources may cast photons into the scene, and store each photon into a single KD tree where it hits a surface. However, the light sources do not know how many photons will eventually be cast, so they cast each one with the light energy. When all photons have been cast, it is necessary to divide the energy of each photon in the KD tree by the number of photons for the originating light source. This would be done by the callback; the photon energy would be stored in the point data by mi_kdtree_add, and information about the light emitter (which is important to find the number of photons to divide by) would be stored in the shared_data by mi_kdtree_edit. It would be inefficient to store the light emitter identifier with each added photon.
typedef miBoolean ((miKdtree_lookup_callback)
(void *callback_data,
const void *data,
const miScalar point[]));
miUint mi_kdtree_lookup(
struct miKdtree *tree,
const miScalar point[],
miUint max_n,
miScalar max_dist,
miScalar *max_dist_used,
miKdtree_lookup_callback *callback,
void *callback_data)
This function returns points near point in the KD tree tree, which must have been opened with mi_kdtree_access. It finds the max_n closest elements, which are closer than max_dist. The distance to the most distant element found is stored in * max_dist_used, if this pointer is nonzero. The number of elements found is returned. The callback is called on each element found, with the opaque callback_data pointer. If the callback returns miFALSE, mi_kdtree_lookup returns immediately. For example, if the KD tree is used for storing photons, a simple callback could just sum the energy of all photons.
miBoolean mi_kdtree_iterate(
struct miKdtree *tree,
miKdtree_lookup_callback *callback,
void *callback_data)
This function is similar to a lookup, but it returns all points in the KD tree, instead of just those that are close to a given point. Again, the iteration stops if the callback returns miFALSE. mi_kdtree_iterate returns miFALSE on failure, for example if tree comes from mi_kdtree_edit instead of mi_kdtree_access.
miBoolean mi_kdtree_delete(
miTag tag)
Deletes the KD tree from the database. All KD tree handles must be closed by calling mi_kdtree_unpin before calling this function. The function returns miTRUE; there are currently no failure modes.
Copyright © 1986-2009 by mental images GmbH