Most two dimensional quasirandom methods focus on sampling over a unit square. However, sampling evenly over the triangle is also very important in computer graphics. Therefore, I describe a simple and direct construction method for a point sequence to evenly cover an arbitrary shaped triangle.

Figure 1. A new direct method for constructing an open (infinite) low discrepancy quasirandom sequence over an triangle of arbitrary shape and size. Shown are the point distributions for twelve random triangles for the first 150 points.

Outline

Low discrepancy sequences that evenly sample/cover a square have been extensively studied for nearly a hundred years. Most of these quasirandom sequences can be extended to rectangles by simple dilation without much deterioration of discrepancy.

However, this post looks at the interesting and important extension of low discrepancy sequences over an arbitrary triangle.

As far as I can deduce, very little work has been done on constructing evenly distributed points sets and sequences over triangles. Notable efforts in recent years by Basu [2014] and Pillands and Cools, [2005] and Brandolini [2013] represent the main papers – if not the only papers on this subject. For a post on Basu’s approach when applied to graphics rendering, see here.

These authors generally take a very theoretical and analytical approach to this issue and almost solely focus on either the regular or right-angled triangle/simplex. In contrast, this post is mainly intended to aid in the development of some practical techniques for graphics rendering.

This post describes a simple and direct method that requires no acceptance/rejection, no dropping or recursion; and most importantly it can be applied to triangles of arbitrary shape and size.

This post has four sections

Quasirandom Sequences in the square
Mapping the unit square to a triangle.
Reducing Aliasing
Further generalizations

1. Quasirandom Point Sequences

You might think it is easy to place 100 points in a square such that the minimum distance between neighboring points is as large possible. But what if you had to place 13 points? 47? … or how about 2019 points?!

It turns out that low discrepancy point sequences offer a systematic way to solve this problem. There are many low discrepancy quasirandom sequences including the simple Halton sequence to the more sophisticated Sobol’ sequence. Each of these particular sequences have their advantages and disadvantages. For example, Halton sequences tend to be more useful when placing objects in a region, as the local distance metrics such as nearest neighbor are well optimized. In contrast, the Sobol’ sequence tends to have more ‘clumping’, however, its global point distribution is very even, and so it has excellent quadrature properties.

There is another sequence I love to use, which has both excellent local as well as global properties. This is the $R_2$ sequence, as described in detail in my other post, “The Unreasonable effectiveness of Quasirandom Sequences”.

In brief, we define the infinite two-dimensional sequence $R_2$, such that

$$ \pmb{t}_n = \left\{ n \pmb{\alpha} \right\} \quad n=1,2,3,… $$

$$ \textrm{where} \quad \pmb{\alpha} =\left(\frac{1}{g}, \frac{1}{g^2} \right), $$

$$ \textrm{and} \; g \simeq 1.32471795572 \tag{1}$$

More details on this special value of $g$, which is often called the ‘plastic constant’ can be found on Wikipedia or Mathworld.

In summary, figure 2 shows a comparison of various low discrepancy sequences (and simple uniform random sampling for comparison). You can see, that random sampling exhibits clustering of points and that there are also regions that contain no points at all (‘white noise’), whereas a low discrepancy sequence quasirandom sequence is a method of constructing an (infinite) sequence points in a deterministic manner such that, at any stage, the placed points are evenly distributed across the entire space.

Figure 2. An illustration of the first 150 terms of various low discrepancy quasirandom sequences . Note that the all of them produce more evenly spaced points than simple uniform random (bottom left.)

2. Mapping the unit square to a triangle.

There are three well known methods to allow one to uniformly random sample from a triangle. These are:

the Parallelogram method ,
the Kraemer Method and
the inverse cumulative distribution method.

The parallelogram method is as follows.

For a triangle $\pmb{ABC}$, consider the parallelogram $\pmb{ABCA’}$.

For a point in the unit square $(r_1,r_2)$, define the point $\pmb{P} $ such that $ \pmb{P} = r_1 \pmb{AC} + r_2 \pmb{AB} $.

This point will always fall inside the parallelogram. However, if it occurs in the complementary triangle $\pmb{ABC’}$, then we need to reflect it back into the triangle $\pmb{ABC}$.

That is, if $r_1+r_2<1$, then $ \pmb{P} = r_1 \pmb{AC} + r_2 \pmb{AB} $, but if $r_1+r_2>1$, then $ \pmb{P} = (1-r_1) \pmb{AC} + (1-r_2) \pmb{AB} $.

However, it is very important to understand that just because these methods allow uniform sampling from a triangle, this does not imply that such a transform will preserve the even spacing (ie low discrepancy) of our quasirandom point distributions.

For example, for the parallelogram method, the reflection may frequently cause a point to be placed very close to another existing point. This obviously breaks the critical low discrepancy structure and the effect will be appear as aliasing/banding.

Similarly the inverse cumulative distribution method applies a non-linear distortion to the points. For the Halton and Sobol sequences this means that frequently two points are pushed very close to each other.

Figure 3 shows how well the low discrepancy is preserved for each of the different quasirandom sequences when you transform the region from a unit square to a triangle using the parallelogram method.

Figure 3. A comparison of how different quasirandom sequences are transformed to the triangle. Top is the Halton sequence, middle is the Sobol sequence and bottom is the $R_2$ sequence. Notice that in the Halton images, there is noticeable clumping of points, and in the Sobol sequence there is notable banding. In contrast, for the $R_2$ sequence the points are very evenly distributed and there is almost no discernible clumping or banding.

Of the three different methods to triangulate, and the numerous different quasirandom sequences to choose from, the parallelogram method applied to the $R_2$ sequence method is the only combination that consistently produces acceptable results in terms of preserving low discrepancy without aliasing.

The excellent results of this combination can be further seen in figure 4.

Figure 4. One can see that the transformed $R_2$ sequence provides a very simple but effective method to evenly distribute a set of $N$ points in a triangle. It works for both acute and obtuse triangles.

3. Other considerations

Aliasing.

The parallelogram method requires selecting two sides of the triangle to be picked as the basis vectors.

If the vertices are labelled in a random order, then the point patterns are typically as seen in figure 5.

*Figure 6. Resulting point patterns, if the ordering of the vertices is randomly chosen. Notice that in most cases, aliasing is clearly visible.*

However, it turns out that a judicious choice of vertex ordering, allows aliasing to be significantly minimized. Most notably, if the triangle is labelled such that $A$ is the largest angle (and thus opposite the largest side), and thus the two sides $\pmb{AB}$ and $\pmb{AC}$ are used for the two sides of the parallelogram.

If this protocol is adopted, then the resulting point patterns can be seen in figures 1, 3 and 4 above.

However, even with the particular ordering of vertices, aliasing effects can still be seen in some instances. These are most noticeable when in triangles when one of the angles is small. For obtuse angles, if the smallest angle is less than 30 degrees, some aliasing is visible, and for acute triangles, if the smallest angles is less than 20 degrees aliasing becomes visible. (If the triangles to sampled are part of a Delaunay mesh, then these aliasing issues may be minimal, as Delaunay triangulation is specifically designed to minimize the existence of small-angled triangles.)

Other shapes.

Unfortunately the parallelogram technique can not be used for other shapes, as it exploits the symmetry of the triangle. For some shapes, it is possible to get good results using the inverse cumulative distribution technique. This method is briefly described.

If we revisit figure 3, we can define point P in a manner that guarantees that it will always be inside the triangle, and therefore not require reflecting. Namely, we define $\pmb{P} $ such that

$ \pmb{P} = r_2 \sqrt{r_1} \pmb{AC} + (1-r_2) \sqrt{r1} \pmb{AB} $.

This additional $\sqrt{r_1}$ term not only ensures that the point $P$ always lies inside the triangle, but also (more importantly) that the sampling is uniform. Note that the square root is required because we need an area-preserving transformation, and area increases according to length squared.

More formally, the fractional distance to move in the direction of $\pmb{AB}$ decreases linearly from $z = 1$ to $z=0$. Thus, the cumulative fractional distance is $\int_0^1 z dx = z^2/2$, which is a function of $z^2$, and thus the inverse of this is proportional to $\sqrt{z}$.

Similarly, if we are now attempting to sample from an arbitrary shaped function, we need to use the inverse of the cumulative distribution function. Below is an example of how the $R_2$ low discrepancy sequence can be transformed onto the area bounded under the Gaussian curve whilst generally preserving even spacing between points.

In this case, let $g(z)$ be the inverse cumulative distribution function of the Normal Gaussian function. The then points $P$ will be defined as $$p(r_1,r_2) = \left( g(r_1), r_2 f (g(r_1)) \right ) $$.

If you use the inverse CDF method, it is often best to used a jittered version of a low discrepancy sequence to minmize aliasing. In the example below, i used a jittered version of $R_2$ with a jitter parameter of 0.5. (see “A simple method to construct isotropic quasirandom blue noise“).

***

Thank you to Sergeij Reich for his valuable discussion and analysis on an earlier version of this post.

My name is Martin Roberts. I have a PhD in theoretical physics. I love maths and computing. I’m open to new opportunities – consulting, contract or full-time – so let’s have a chat on how we can work together!

Come follow me on Twitter: @Techsparx!

My other contact details can be found here.

Evenly Distributing Points in a Triangle.