Equally distribution on triangle surfaces

Question

I would like to implement a random placement for objects like trees stones etc. on a triangles surface. The important part is to have an equally probability to place an object on this surface. That means, that for example to randomly place a tree in the middle should not be higher than placing it at a corner / edge.

The second requirement is to program this placement algorithm onto the GPU by using OpenGL/GLSL. So randomly generate a position and loop as long as it is not inside the triangle is no option because of branching... I need to place tons of objects per frame...

I had the idea of using Barycentric coordinates where the three scalars are randomly generated. but it turned out, that the middle and the lines from the middle to the middle of an edge is more probably than hitting a corner. The good thing about Barycentric coordinates is, that the surface of the 3D triangle is always hit, so the generated position is not above or outside the triangle. Another plus is, that to calculate the Barycentric coordinate is extremely fast during using multiplication of 3D vectors with scalars and addition of vectors with vectors.

here is my C++ code to generate random positions on the triangles' surface.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>

struct Vector3D
{
public:

    Vector3D()
    {

    }

    Vector3D(double x, double y, double z)
    {
        this->x = x;
        this->y = y;
        this->z = z;
    }

    void operator*=(double factor)
    {
        x *= factor;
        y *= factor;
        z *= factor;
    }

    void operator+=(double factor)
    {
        x += factor;
        y += factor;
        z += factor;
    }

    Vector3D operator*(double factor)
    {
        Vector3D result;
        result.x = x * factor;
        result.y = y * factor; 
        result.z = z * factor; 
        return result;
    }

    Vector3D operator+(Vector3D v2)
    {
        Vector3D result;
        result.x = x + v2.x;
        result.y = y + v2.y;
        result.z = z + v2.z;
        return result;
    }

    double x;
    double y;
    double z;
};


Vector3D getBarycentricPosition(Vector3D p0, Vector3D p1, Vector3D p2, double scalar0, double scalar1, double scalar2)
{
    return (p0 * scalar0) + (p1 * scalar1) + (p2 * scalar2);
}


void main()
{
    Vector3D p0(1, 0, 0);
    Vector3D p1(0, 1, 0);
    Vector3D p2(0, 0, 1);

    std::ofstream writefile("C:/Data[![enter image description here][1]][1]/barycentricTest.obj");
    if (writefile.is_open())
    {
        for (unsigned int i = 0; i < 100000; ++i)
        {
            //generate random values
            double random0 = rand() % 1000;
            double random1 = rand() % 1000;
            double random2 = rand() % 1000;

            //
            double powFactor = 1.0f;
            random0 = pow(random0, powFactor);
            random1 = pow(random1, powFactor);
            random2 = pow(random2, powFactor);

            int sum = random0 + random1 + random2;

            //scalar0 + scalar1 + scalar2 = 1 !!
            double scalar0 = static_cast<double>(random0) / static_cast<double>(sum);
            double scalar1 = static_cast<double>(random1) / static_cast<double>(sum);
            double scalar2 = static_cast<double>(random2) / static_cast<double>(sum);

            Vector3D p = getBarycentricPosition(p0, p1, p2, scalar0, scalar1, scalar2);
   
            //write to .obj file to see results in blender
            writefile << "v " << p.x << " " << p.y << " " << p.z << std::endl;
        }
        writefile.close();
    }
}

By looking at the code, you'll recognize, that there is the double powFactor. I tried to bring the probability of the corners a little bit up.

Here are some images with different powFactor values.

powFactor = 1.0 So without influencing the algorithm

powFactor = 1.3

Like you can see, to pow with 1.3 looks good inside, but the corners / edges are over weighted...

Is there a fast algorithm (branching free) which gives good results?

Answer 1

Barycentric coordinates need to sum to 1.0, so pick two of them (say $u, v$) randomly from [0, 1] and then set the third as $w = 1 - u - v$. This will give you random points that are evenly distributed with respect to area, in a parallelogram consisting of two copies of the triangle. Then, you can reflect across the triangle edge to bring both copies of the triangle together. This can be done by checking if $u + v > 1$, and if so, reflect by setting $u' = 1-u,\, v' = 1-v$ and then recalculate $w$.

See also: Generate random points in a triangle.