Uniform sampling of a triangle by dividing it into smaller parts?

Question

To sample a triangle ABC uniformly, I can use the following formula:

P = (1 - sqrt(r1)) * A + (sqrt(r1)*(1 - r2)) * B + (r2*sqrt(r1)) * C

where r1 and r2 are random numbers between 0 and 1. The more samples you take, the better. But what if I want to get a better distribution, while keeping then number of samples low?

For example if I had a square, I can implicitly divide it into an N x N grid and generate a random sample inside the smaller grid squares. Like this:

float u = (x + rnd(seed)) / width;
float v = (y + rnd(seed)) / height;

The point is I force the sampling to cover the entire grid at a lower sample resolution.

How can I achieve this with a triangle? The only way I can think of is to explicitly subdivide it into a number of triangles using a library like Triangle. But is there a way to do this implicitly like with a square, without having to actually divide the triangle?

It is a bit unclear what you're asking. So you sample uniformly on the plane in the triangle defined by points A, B and C, correct? So you have the routine which you call and get back point (x, y). `But what if I want to reduce the number of samples?` You cannot reduce number of samples upfront? Why? — Severin Pappadeux, Sep 17 '17 at 20:33
I don't want to rely on completely random sampling. It would require a large amount of samples to get a good distribution all over the triangle. — Moody, Sep 17 '17 at 21:00
So are you talking about variance-reduction techniques here? — sascha, Sep 17 '17 at 21:06
@sascha but it is uniform in triangle distribution, where is the importance to sample from? — Severin Pappadeux, Sep 17 '17 at 22:15
ok, if you don't want many samples, how subdivision suppose to help you? You still have uniform-over-part as a requirement, right? Basically, if you have 100 samples in the big triangle. You subdivide it into 2 smaller triangles and sample 50 points in each part. I don't see what would behave differently. Ok, lets ask for clarification - what exactly is computed over this triangle? You'er doing something with those sampled coordinates, right? — Severin Pappadeux, Sep 17 '17 at 22:19
The samples represent origins of rays that I project from the triangle. Yes you are correct that dividing it into 2 triangles would not change anything. But if you divide it into 1000 triangles, you force rays to be generated everywhere. For example you force rays to generate at the very edge of the triangle, instead of **hoping** that random sampling would generate rays at the edge. I hope that clarifies things? — Moody, Sep 19 '17 at 11:50

score 2 · Accepted Answer · answered Sep 27 '17 at 23:18

OK, I had some thoughts and believe using quasirandom numbers could improve "uniformity" of the points-in-the-triangle coverage without doing subdivision into smaller triangles. Quasirandom sampling using Sobol sequences could provide a lot better coverage as seen in the Wiki article.

Here is 200 points in triangle using standard RNG (whatever it is in Python)

And here is picture with 200 points sampled from Sobol 2D sequence

Looks a lot better to me. Python code to play with

import os
import math
import random

import numpy as np
import matplotlib.pyplot as plt

import sobol_seq

def trisample(A, B, C, r1, r2):
    s1 = math.sqrt(r1)

    x = A[0] * (1.0 - s1) + B[0] * (1.0 - r2) * s1 + C[0] * r2 * s1
    y = A[1] * (1.0 - s1) + B[1] * (1.0 - r2) * s1 + C[1] * r2 * s1

    return (x, y)

if __name__ == "__main__":
    N = 200

    A = (0.0, 0.0)
    B = (1.0, 0.0)
    C = (0.5, 1.0)

    seed = 1
    xx = list()
    yy = list()
    random.seed(312345)
    for k in range(0, N):

        pts, seed = sobol_seq.i4_sobol(2, seed)
        r1 = pts[0]
        r2 = pts[1]

        # uncomment if you want standard rng
        #r1 = random.random()
        #r2 = random.random()

        pt = trisample(A, B, C, r1, r2)
        xx.append(pt[0])
        yy.append(pt[1])

    plt.scatter(xx,  yy)
    plt.show()

    sys.exit(0)

That is a very nice method. It looks just like what I need. Thanks for the help! — Moody, Sep 28 '17 at 16:48

score 0 · Answer 2 · answered Sep 17 '17 at 21:07

0

I'd suggest using Poisson disk sampling (short academic paper link, pretty visualization link, wiki link, code link) to generate a configuration within the bounding box of your triangle and then cropping to the area bounded by the triangle.

I suggest starting with the short academic paper. The principle at work here is pretty easy to understand. There are many variations of this idea floating around out there, so get a handle on it and find the one that works for you.

answered Sep 17 '17 at 21:07

Richard

56,349
34
180
251

Richard, it is not about sampling uniformly in triangle. @Moody uses correct formula to sample points uniformly in triangle, check https://stackoverflow.com/questions/4778147/sample-random-point-in-triangle and references therein – Severin Pappadeux Sep 17 '17 at 22:13

Uniform sampling of a triangle by dividing it into smaller parts?

2 Answers2