Генерация случайных точек на поверхности меша

Задача: сгенерировать N равномерно распределенных точек по поверхности произвольного триангулированного меша.

Общая идея решения: выбираем треугольник с вероятностью, пропорциональной его площади, и уже внутри выбранного треугольника берем равномерно распределенную случайную точку.

Как выбрать треугольник с вероятностью, пропорциональной его площади?

Воспользуемся методом, который называется inverse cdf sampling. Подробно можно почитать здесь.

Представим, что у нас есть случайная величина и она может принимать 4 возможных дискретных значения v1, v2, v3 и v4 с вероятностями p1, p2, p3 и p4 соответственно.

p1 + p2 + p3 + p4 = 1

Сконструируем дискретную функцию cdf, где cdf[i] = p0 + p1 + ... + pi.

И теперь используя cdf мы можем замапить равномерно распределенную случайную величину на наши дискретные случайные величины v0, v1, v2, v3 с соответствующими вероятностями

/// <summary> Inverse cdf sampling </summary>
/// <param name="cumulativeProbabilities">дискретная cdf. 
/// cumulativeProbabilities[0] - p0, где p0 - вероятность, что выпадет случайная величина с индексом 0 
/// cumulativeProbabilities[1] - p0 + p1, где p1 - вероятность, что выпадет случайная величина с индексом 1 
/// cumulativeProbabilities[2] - p0 + p1 + p2, где p2 - вероятность, что выпадет случайная величина с индексом 2 
/// ...
/// cumulativeProbabilities[cumulativeProbabilities.Length - 1] = p0 + p1 + p2 + ... + pLast = 1</param>
/// <param name="randomValue">равномерно распределенная случайная величина</param>
/// <returns>индекс выпавшей случайной величины</returns>
public static int InverseSample(float[] cumulativeProbabilities, float randomValue) {
   int maxIndex = cumulativeProbabilities.Length - 1;   
   int minIndex = 0;   
      
   for (int i = 0; i < cumulativeProbabilities.Length; i++) {      
       int index = minIndex + (int)(0.5f * (maxIndex - minIndex));      
       var pr = cumulativeProbabilities[index];      
       if (randomValue <= pr) {         
           maxIndex = index;      
       } else {         
           minIndex = index + 1;      
       }      
       if (minIndex == maxIndex) return maxIndex;             
   }
   
   throw new Exception("Something was wrong");
}

Теперь остается сконструировать cumulativeProbabilities для наших треугольников и, используя обычный random и метод InverseSample, получать индексы треугольников с вероятностью, пропорциональной их площади.

float totalArea = 0;
for (var i = 0; i < triangles.Length; i++)
{    
    var triangle = triangles[i];    
    var triangleArea = CalculateTriangleArea(triangle);
    totalArea += triangleArea;
}  
var cumulativeProbabilities = new float[triangles.Length];
float probabilitySum = 0;
for (var i = 0; i < triangles.Length; i++)
{    
    var triangle = triangles[i];    
    var triangleArea = CalculateTriangleArea(triangle);
    var probability = triangleArea /totalArea;
    probabilitySum += probability;
    cumulativeProbabilities[i] = probabilitySum;    
}  
var triangleRandom = new Random(seed);
for (int i = 0; i < N; i++) {
    var index = InverseSample(cumulativeProbabilities, triangleRandom.NextFloat());
    var trianlge = triangles[index];
    ...
}
         

Как сгенерировать равномерно распределенную случайную точку внутри треугольника

float3 v0 = triangle.v0; // 1я вершина
float3 v1 = triangle.v1; // 2я вершина
float3 v2 = triangle.v2; // 3я вершина

var random = new Random(seed);
var r1 = random.NextValue();
var r2 = random.NextValue();
float sqrtR1 = math.sqrt(r1);
// Получим барицентрические координаты
w0 = 1 - sqrtR1;
w1 = (1 - r2) * sqrtR1;
w2 = r2 * sqrtR1;

var randomPoint = w0*v0 + w1*v1 + w2*v2; //Результат

https://t.me/lab_sborki