<p>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.</p>
<p>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.</p>
<p>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.<br />
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.</p>
<p><a href="https://i.sstatic.net/FUAiH.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FUAiH.jpg" alt="source:Umenhoffer, Szécsi, Szirmay-Kalos - Hatching for Motion Picture Production (2011)" /></a><br />
source:Umenhoffer, Szécsi, Szirmay-Kalos - <a href="https://www.researchgate.net/publication/220506553_Hatching_for_Motion_Picture_Production" rel="nofollow noreferrer">Hatching for Motion Picture Production (2011)</a></p>
<p>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.</p>
<p>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)</p>
<blockquote class="spoiler">
<p>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&gt;1).</p>
</blockquote>
<p><strong>The question is this</strong>: 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)?</p>
<p>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 <a href="https://www.researchgate.net/publication/220506553_Hatching_for_Motion_Picture_Production" rel="nofollow noreferrer">paper</a> from which I've taken the algorithm outlined above state (section 4.1.1, §3)(bold typeface added by me for emphasis):</p>
<blockquote>
<p>The faces of the model of the mesh are roughly arranged in a 1D
face array <strong>by proximity</strong>. 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 <em>summed</em>
<em>area tree</em>, in which leaf values are triangle surface areas <strong>in</strong>
<strong>the same order as</strong> they appear <strong>in the face array</strong>.</p>
</blockquote>
<p>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.</p>
<p>Here a spoiler where you can read up the algorithm as described by the authors:</p>
<blockquote class="spoiler">
<p>In order to deﬁne 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. stripiﬁcation) [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&gt;1).</p>
</blockquote>
<p>Link to the full text of the paper: <a href="https://www.researchgate.net/publication/220506553_Hatching_for_Motion_Picture_Production" rel="nofollow noreferrer">Hatching for Motion Picture Production</a>. The relevant part is only section 4.1.1.</p>
<p>Thank you for any input.</p>

CC BY-SA 4.0
2021-03-07T18:18:09.497Z
Probably the QMC properties are maintained better if there is better locality in the mapping from UV space to triangles. It's a similar issue to how QMC prefers mappings without too much distortion to stretch/squeeze the sample pattern. If you cut up the domain into lots of tiny pieces and rearrange them randomly, you'll be moving the samples closer to white noise. Consider the case when triangles are small enough that there's on average 1 sample or fewer per triangle.
Nathan Reed
CC BY-SA 4.0
2021-03-07T18:54:31.067Z
The order matters. Consider the fact that the low-discrepancy sequence that you use has been optimised w.r.t. the star discrepancy in the uni hypercube. One can construct area preserving discontinuous mappings that destroy any semblance of discrepancy effectively resulting in an almost random sequence exhibiting the worse convergence inherent to random sequences. In the ideal scenario one would optimise a low discrepancy sequence in the target integration domain, but that is typically computationally expensive. This is why one relies on mappings that try to not destroy the sequence properties.
lightxbulb
<algorithm><mathematics><computational-geometry><sampling><monte-carlo>
Is this way of transforming QMC samples into barycentric tri coordinates agnostic to mesh-topology?
Herbert Jensch
# Is this way of transforming QMC samples into barycentric tri coordinates agnostic to mesh-topology?

(Asked by: username_0 on 2021-03-07)

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)](https://i.sstatic.net/FUAiH.jpg)](https://i.sstatic.net/FUAiH.jpg)  
source:Umenhoffer, Szécsi, Szirmay-Kalos - [Hatching for Motion Picture Production (2011)](https://www.researchgate.net/publication/220506553_Hatching_for_Motion_Picture_Production)

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](https://www.researchgate.net/publication/220506553_Hatching_for_Motion_Picture_Production) 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 deﬁne 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. stripiﬁcation) [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](https://www.researchgate.net/publication/220506553_Hatching_for_Motion_Picture_Production). The relevant part is only section 4.1.1.

Thank you for any input.

**Tags:** algorithm, mathematics, computational-geometry, sampling, monte-carlo

> **Comments:**
> **username_1**: Probably the QMC properties are maintained better if there is better locality in the mapping from UV space to triangles. It's a similar issue to how QMC prefers mappings without too much distortion to stretch/squeeze the sample pattern. If you cut up the domain into lots of tiny pieces and rearrange them randomly, you'll be moving the samples closer to white noise. Consider the case when triangles are small enough that there's on average 1 sample or fewer per triangle.  
> **username_2**: The order matters. Consider the fact that the low-discrepancy sequence that you use has been optimised w.r.t. the star discrepancy in the uni hypercube. One can construct area preserving discontinuous mappings that destroy any semblance of discrepancy effectively resulting in an almost random sequence exhibiting the worse convergence inherent to random sequences. In the ideal scenario one would optimise a low discrepancy sequence in the target integration domain, but that is typically computationally expensive. This is why one relies on mappings that try to not destroy the sequence properties.  

---

## 0 answers

