A Binary Space Partitioning (BSP) tree algorithm is used to quickly identify the required set of candidate mesh locations to use for generating mapping weights.
The BSP algorithm fits a uniform structured grid of two cells to the source region(s). Each cell that contains more than a predetermined number of source mesh locations is recursively subdivided into two new cells in a direction that is orthogonal to the preceding division. This continues to form a hierarchical tree structure, as shown in the figure below, until either the maximum number of levels in the hierarchy is reached or the predetermined number of source mesh locations per tree cell is reached. BSP tree cells at this level are referred to as "leaf cells."
Figure 1: Example of a BSP tree mesh on a 2D target domain, which extends naturally to 3D (source mesh locations not shown for clarity)
Each target mesh location is ultimately associated with one or more leaf cells. Efficiency is realized by associating the target mesh locations with a cell at each level within the tree hierarchy, starting with the highest (largest) cells first.
From here, the association process varies, as follows:
- Profile-Preserving Mapping
The association goes from target to source.
Once a target node is associated with a leaf cell(s), it is associated with the most suitable source element and/or nodes.
- Conservative Mapping
The association goes from source to target.
Once the source element is associated with a leaf cell(s):
For transfers to surface target regions, the source element is associated with intersecting target elements. Care is taken to appropriately consider the relative orientation and normal distance between associated source and target elements.
For transfers to volume target regions, the source element is associated with intersecting target elements.