[Перевод] Равномерное распределение точек в треугольнике

Григорий Воронцов23.02.2019

0 6 Время чтения: 4 мин.

Большинство двухмерных квазислучайных методов рассчитано на сэмплирование в единичном квадрате. Однако в компьютерной графике также очень важны треугольники. Поэтому я описал простой метод прямого построения для равномерного покрытия последовательностью точек треугольника произвольной формы.

Рисунок 1. Новый прямой метод построения открытой (бесконечной) квазислучайной последовательности с низким расхождением в треугольнике произвольной формы и размера. На рисунке показаны распределения точек в пятнадцати случайных треугольниках для первых 150 точек.
Последовательности с низким расхождением (low discrepancy), равномерно сэмплирующие/заполняющие квадрат, активно изучались почти сотню лет. БОльшую часть этих квазислучайных последовательностей можно расширить до прямоугольников простым растягиванием, не сильно повредив при этом расхождению.

Примечательные работы недавних лет Басу [2014], Пилландса [2005] и Брандолини [2013] представляют основные, если не единственные статьи по этой теме. Однако в этом посте мы рассмотрим интересное и важное расширение последовательностей с низким расхождением на произвольный треугольник.
Насколько я мог понять, построению множеств равномерно распределённых в треугольнике точек и последовательностей уделялось очень мало внимания.

В отличие от них, мой пост в основном предназначен для разработки практических техник в рендеринге графики. Эти авторы обычно рассматривают эту проблему под очень теоретическим и аналитическим углом, и почти всегда решают её для единичного правильного треугольника.

В посте описывается простой метод прямого построения, не требующий ни принятия/исключения, ни отбрасывания или рекурсии; и самое важное то, что его можно применять к треугольникам произвольного размера и формы.

Пост состоит из четырёх разделов:

Квазислучайные последовательности в квадрате
Наложение единичного квадрата на треугольник.
Снижение искажений
Дальнейшие обобщения

Вы можете подумать, что разместить 100 точек в квадрате таким образом, чтобы минимальное расстояние между соседними точками оставалось как можно бОльшим, будет легко. Но что если нужно разместить 13 точек? 47? А как насчёт 2019 точек?!

Существует множество квазислучайных последовательностей с низким расхождением, от простой последовательности Холтона до более сложной последовательности Соболя. Оказывается, что последовательности точек с низким расхождением обеспечивают систематический способ решения этой задачи. Например, последовательности Холтона оказываются более полезными при размещении объектов в области, потому что у неё хорошо оптимизированы такие метрики локального расстояния, как ближайшие соседи. Каждая из этих последовательностей имеет свои достоинства и недостатки. Последовательность Соболя склонна к образованию большей «скученности», однако глобальное распределение точек очень равномерно, поэтому она имеет превосходные свойства квадратуры.

Это последовательность $R_2$ , подробно описанная в моём предыдущем посте «Неожиданная эффективность квазислучайных последовательностей». Есть ещё одна последовательность, которую я люблю использовать, с отличными локальными, а также глобальными свойствами.

Если вкратце, то мы задаём бесконечную двумерную последовательность $R_2$ , такую, что

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

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

32471795572 \tag{1}$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/3da/6d1/1fc/3da6d11fc0f374a83a7c8e1ad6c8fd22.svg" alt="$\textrm{и} \; g \simeq 1.

Подробнее об этом особом значении $g$ , которое часто называют «пластической константой» можно прочитать в Википедии или Mathworld.

Как видите, эта случайная выборка демонстрирует скапливание точек. В итоге, на рисунке 2 показано сравнение различных последовательностей с низким расхождением (и простая равномерная случайная выборка для сравнения). При этом в ней есть области, вообще не содержащие точек («белый шум»), в то время как квазислучайная последовательность с низким расхождением — это метод построения (бесконечной) последовательности точек детерминированным образом так, чтобы на любом этапе размещённые точки равномерно распределялись по всему пространству.

Рисунок 2. Иллюстрация первых 150 членов различных квазислучайных последовательностей с низким расхождением. Заметьте, что все они создают более равномерно распределённые в пространстве точки, чем простое равномерное случайное распределение (внизу слева).
Существует три хорошо известных способа, позволяющих обеспечить равномерную случайную выборку из треугольника:

метод параллелограмма ,
метод Кремера и
метод инверсного распределения накопленных вероятностей.

Рисунок 3. Метод параллелограмма

Метод параллелограмма заключается в следующем.

Для треугольника $\pmb{ABC}$ рассмотрим параллелограмм $\pmb{ABCA’}$ .

Для точки единичного квадрата $(r_1,r_2)$ зададим такую точку $\pmb{P}$ , что $\pmb{P} = r_1 \pmb{AC} + r_2 \pmb{AB}$ .

Однако если она оказывается в дополнительном треугольнике $\pmb{ABC’}$ , то нам нужно отразить её обратно в треугольник $\pmb{ABC}$ . Эта точка всегда будет находиться внутри параллелограмма.

То есть если $r_1+r_2<1$ , то $\pmb{P} = r_1 \pmb{AC} + r_2 \pmb{AB}$ , но если $r_1+r_2>1$ , то $\pmb{P} = (1-r_1) \pmb{AC} + (1-r_2) \pmb{AB}$ .

низкое расхождение) наших квазислучайных распределений точек. Однако очень важно понимать, что даже хотя эти методы обеспечивают равномерную выборку из треугольника, это не означает, что такое преобразование сохранит равномерное пространственное расположение (т.е.

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

В последовательностях Холтона и Соболя это означает, что две точки очень часто подталкиваются очень близко друг к другу. Аналогично, метод инверсного распределения накопленных вероятностей применяет к точкам нелинейное искажение.

На рисунке 4 показано, насколько хорошо сохраняется низкое расхождение в каждой из различных квазислучайных последовательностей при преобразовании области из единичного квадрата в треугольник при использовании метода параллелограмма.

Рисунок 4. Сравнение преобразования различных квазислучайных последовательностей в треугольнике. Вверху показана последовательность Холтона, посередине — последовательность Соболя, внизу — последовательность . Видно, что в последовательности Холтона возникает значительная скученность точек, а в последовательности Соболя — значительное образование полос. По сравнению с ними, в последовательности точки распределены очень равномерно, и почти отсутствует заметная скученность или полосы.

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

Превосходные результаты этого сочетания можно подробнее рассмотреть на рисунке 5.

Рисунок 5. Можно увидеть, что преобразованная последовательность обеспечивает очень простой, но эффективный способ равномерного распределения множества из точек в треугольнике. Он работает и с остроугольными, и с тупоугольными треугольниками. (Цвет обозначает порядок расположения).

Искажение

Метод параллелограмма требует выбора двух сторон треугольника в качестве базисных векторов.

Если вершины помечаются в случайном порядке, то паттерны точек обычно напоминают показанные на рисунке 6.

Рисунок 6. Паттерны точек, получающиеся при случайном выборе порядка вершин. Заметьте, что в большинстве случаев явно заметно искажение.

Наиболее примечательно то, что если треугольник пометить так, что является наибольшим углом (то есть против него лежит наибольшая сторона), то стороны $\pmb{AB}$ и $\pmb{AC}$ используются в качестве двух сторон параллелограмма. Однако оказывается, что при продуманном выборе порядка вершин можно значительно снизить искажения.

Если принять такой порядок, то получаются паттерны точек, показанные выше на рисунках 1, 4 и 5.

Больше всего они заметны, когда в треугольниках один из углов очень мал. Однако даже при определённом порядке вершин в некоторых случаях всё равно заметны эффекты искажений. (Если сэмплируемые треугольники являются частью сетки Делоне, то такие проблемы с искажениями могут быть минимальными, потому что триангуляция Делоне специально предназначена для минимизации количества треугольников с малыми углами.) В случае тупоугольных треугольников, когда наименьший угол меньше 30 градусов, то заметно некоторое искажение, а в случае остроугольных треугольников, когда наименьший угол меньше 20 градусов, становится видным искажение.

Другие фигуры

К сожалению, технику параллелограмма невозможно использовать для других фигур, потому что в нём используется симметрия треугольника. Для некоторых фигур можно получить хорошие результаты с помощью метода инверсного распределения накопленных вероятностей. Ниже показан пример того, как последовательность с низким расхождением можно преобразовать в область, ограниченную гауссовой кривой с сохранением равномерного расстояния между точками.

Теги
квазислучайность Математика Работа с векторной графикой распределение точек треугольники триангуляция делоне