While I'll try my best to give all relevant info in all possible brevity below, please refer to the spoiler and link at the bottom of the post for the (more lengthy) original description if needed.
Suppose for a buch of triangles, I put each triangle's surface area (along with a reference to the tri itself) into the nodes of a binary search tree. Each internal node always contains the summed area of it's children. By consequence, the root node contains the summed area of all the tris at hand.
Now the topological connectivity-info and the area-values of the binary tree are used to construct a kd-tree in the unit square which (the unit square) we call sample-space.
The kd-tree's root node corresponds to the whole unit square.
The sample-space is divided by an axis-aligned split line into two subsets (one for each child-node) such as to partition it by the same ratio by which the (mesh-triangle-) area-value of the aforementioned binary tree's root-node is partitioned by those of it's child-nodes.
This way, at each level, the kd-tree subdivides the sample-space into two subsets, the area of which is proportional to the area covered by the mesh triangles represented by the corresponding nodes in the binary tree.
source:Umenhoffer, Szécsi, Szirmay-Kalos - Hatching for Motion Picture Production (2011)
All of this serves as a means of mapping the sample-space onto the mesh triangles in object space in an area-preserving way. It is used to perform quasi Monte-Carlo sampling in the sample space and use the datastructures outlined above to transform the samples from sample-space to the triangle's object space.
I have omitted the details of how the algorithm effectively translates a (u,v) sample-position in sample-space into barycentric triangle-coordinates by traversing the kd-tree here for brevity. (see the spoiler)
When we need to transform samples into the object-space, we use the kd-tree. Given the (u,v)coordinates of the sam- pled point, we start from the root of the tree, comparing the coordinate of the splitting axis to the splitting ratio. Depend- ing on the result of the comparison, we continue recursively with one of the branches, normalizing the coordinate to the cell’s [0,1]range. At a leaf, the (u,v)coordinates we get are interpreted according to the natural parametrization of the quadrilateral, or as two of the unit-sum barycentric coordi- nates on the triangle (or (1−u,1−v)if u+v>1).
The question is this: Does the order of the leaf-nodes in the binary tree matter at all for this mapping (to preserve the properties of the QMC sampling during the transformation)?
My intuition tells me 'no, it doesn't matter at all, a random order is as good as any other'. On the other hand, the authors of the paper from which I've taken the algorithm outlined above state (section 4.1.1, §3)(bold typeface added by me for emphasis):
The faces of the model of the mesh are roughly arranged in a 1D face array by proximity. In typical cases, this naturally arises from the modeling process. Otherwise, mesh optimization algorithms (e.g. stripification) [DGGP05] can be applied. First, we build a balanced binary tree, called the summed area tree, in which leaf values are triangle surface areas in the same order as they appear in the face array.
The fact the authors seem to bother about the order of the leafs in the binary tree (which they call summed area tree) and even suggest using an explicit stripification-algorithm might suggest otherwise.
Here a spoiler where you can read up the algorithm as described by the authors:
In order to define a mapping from sample-space to object- space, we need to place the mesh faces into the sample-space without distorting face area ratios, and be able to locate the face containing sample point (u,v). This is a typical prox- imity search problem, which is well supported by a kd-tree. The data structures required for the build and search pro- cesses are depicted in Figure 4. The faces of the model mesh are roughly arranged in a 1D face array by proximity. In typical cases, this naturally arises from the modeling process. Otherwise, mesh optimization algorithms (e.g. stripification) [DGGP05] can be applied. First, we build a balanced binary tree, called the summed area tree, in which leaf values are triangle surface areas in the same order as they appear in the face array. Any branch node contains the summed area of its children. The root node will contain the surface area of the complete object. Then, we partition the sample-space with a kd-tree that has the same balanced topology. Every node in the kd-tree corresponds to a node in the area tree. The unit square cell in sample-space is assigned to the root node, which is split re- cursively along the coordinate axes resulting in a binary tree of cells. At a given node, the splitting ratio is selected so that the areas of the two new cells are proportional to the summed surface areas stored in the corresponding child nodes of the area tree. Thus, the sample-space area that belongs to a set of faces will be proportional to their surface area. Where the set reduces to a single face, the face is mapped to the cell. This is trivial for quadrilateral faces, but also works well with tri- angles if we represent each triangle twice and arrange each pair as a quad (right of Figure 4). When we need to transform samples into the object-space, we use the kd-tree. Given the (u,v)coordinates of the sam- pled point, we start from the root of the tree, comparing the coordinate of the splitting axis to the splitting ratio. Depend- ing on the result of the comparison, we continue recursively with one of the branches, normalizing the coordinate to the cell’s [0,1]range. At a leaf, the (u,v)coordinates we get are interpreted according to the natural parametrization of the quadrilateral, or as two of the unit-sum barycentric coordi- nates on the triangle (or (1−u,1−v)if u+v>1).
Link to the full text of the paper: Hatching for Motion Picture Production. The relevant part is only section 4.1.1.
Thank you for any input.
