A maioria dos métodos quase aleatórios bidimensionais são projetados para amostragem por unidade de quadrado. No entanto, triângulos também são muito importantes em computação gráfica. Portanto, descrevi um método simples de construção direta para cobrir uniformemente uma sequência de pontos de um triângulo de forma arbitrária.


Figura 1. Um novo método direto para construir uma sequência quase aleatória aberta (infinita) com uma baixa divergência em um triângulo de forma e tamanho arbitrários. A figura mostra a distribuição dos pontos em quinze triângulos aleatórios para os primeiros 150 pontos.

Breve revisão

Sequências de baixa discrepância que amostram / preenchem uniformemente um quadrado têm sido ativamente estudadas por quase cem anos. A maioria dessas seqüências quase aleatórias pode ser expandida para retângulos com um simples alongamento, sem danificar significativamente a discrepância.

No entanto, neste post, consideraremos uma extensão interessante e importante de sequências com baixa divergência em um triângulo arbitrário.

Até onde pude entender, pouca atenção foi dada à construção de conjuntos de pontos e sequências uniformemente distribuídos em um triângulo. Os trabalhos dignos de nota nos últimos anos de Basu [2014] , Pillands [2005] e Brandolini [2013] representam os principais, se não os únicos, artigos sobre esse tema.

Esses autores geralmente consideram esse problema de um ângulo muito teórico e analítico e quase sempre o resolvem para um único triângulo regular. Em contraste com eles, meu post é voltado principalmente para o desenvolvimento de técnicas práticas na renderização gráfica.

O post descreve um método simples de construção direta, que não requer aceitação / exclusão, descarte ou recursão; e o mais importante, pode ser aplicado a triângulos de tamanho e forma arbitrários.

A postagem consiste em quatro seções:

1. Sequências aleatórias ao quadrado
2. Sobreponha um quadrado de unidade em um triângulo.
3. Redução de distorção
4. Generalizações adicionais

1. Sequência quase aleatória de pontos

Você pode pensar que é fácil colocar 100 pontos em um quadrado para que a distância mínima entre os pontos adjacentes permaneça o maior possível. Mas e se você precisar colocar 13 pontos? 47? E os pontos de 2019 ?!

Acontece que seqüências de pontos com baixa divergência fornecem uma maneira sistemática de resolver esse problema. Existem muitas sequências quase aleatórias com baixa divergência, de uma sequência simples de Holton a uma sequência Sable mais complexa. Cada uma dessas seqüências tem suas próprias vantagens e desvantagens. Por exemplo, as sequências de Holton se tornam mais úteis ao colocar objetos em uma área, porque possui métricas de distância local bem otimizadas, como vizinhos mais próximos. A sequência Sable é propensa a formar mais “aglomeração”, mas a distribuição global de pontos é muito uniforme, portanto, possui excelentes propriedades de quadratura.

Há outra sequência que eu gosto de usar, com excelentes propriedades locais e globais. Esta é a sequência $$$R_2$descrito em detalhes no meu post anterior "Eficiência inesperada de sequências quase aleatórias" .

Em resumo, definimos uma sequência bidimensional infinita $$$R_2$tal que

$$

$$\ pmb {t} _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 {onde} \ quad \ pmb {\ alpha} = \ left (\ frac {1} {g}, \ frac {1} {g ^ 2} \ right),$$

$$

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

Leia mais sobre esse significado especial. $$$g$, que geralmente é chamada de "constante plástica", pode ser lida na Wikipedia ou no Mathworld .

Como resultado, a Figura 2 mostra uma comparação de diferentes seqüências com baixa divergência (e uma amostra aleatória simples e uniforme para comparação). Como você pode ver, esta amostra aleatória demonstra o acúmulo de pontos. Além disso, contém áreas que não contêm pontos (“ruído branco”), enquanto uma sequência quase aleatória com baixa divergência é um método de construir uma sequência (infinita) de pontos de maneira determinística, de modo que, em qualquer estágio, os pontos colocados sejam distribuídos uniformemente espaço.


Figura 2. Ilustração dos primeiros 150 membros de várias seqüências quase aleatórias de baixa divergência. Observe que todos eles criam pontos no espaço mais uniformemente distribuídos do que uma simples distribuição aleatória uniforme (canto inferior esquerdo).

2. A imposição de um quadrado unitário em um triângulo

Existem três métodos conhecidos para garantir uma amostragem aleatória uniforme de um triângulo:

1. método do paralelogramo
2. Método de Kramer e
3. método de distribuição de probabilidade inversa.

Figura 3. Método do paralelogramo

O método do paralelogramo é o seguinte.

Para triângulo $$$\ pmb {ABC}$considere um paralelogramo $$$\ pmb {ABCA '}$.

Para um ponto de uma unidade quadrada $$$(r_1, r_2)$definir tal ponto $$$\ pmb {P}$que $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$.

Este ponto estará sempre dentro do paralelogramo. No entanto, se aparecer em um triângulo adicional $$$\ pmb {ABC '}$então precisamos virar de volta para o triângulo $$$\ pmb {ABC}$.

Ou seja, se $$$r_1 + r_2 <1$então $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$mas se $$$r_1 + r_2> 1$então $$$\ pmb {P} = (1-r_1) \ pmb {AC} + (1-r_2) \ pmb {AB}$.

No entanto, é muito importante entender que, embora esses métodos forneçam amostragem uniforme do triângulo, isso não significa que essa transformação preservará o arranjo espacial uniforme (ou seja, baixa divergência) de nossas distribuições de pontos quase aleatórios.

Por exemplo, no caso do método do paralelogramo, a reflexão pode frequentemente resultar em um ponto muito próximo de outro ponto existente. Obviamente, isso destrói a estrutura de baixa divergência e aparece como distorção / tira.

Da mesma forma, o método de distribuição de probabilidade inversa aplica distorção não linear aos pontos. Nas seqüências de Holton e Sable, isso significa que dois pontos muitas vezes se aproximam muito.

A Figura 4 mostra quão bem a baixa discrepância é mantida em cada uma das várias seqüências quase aleatórias ao transformar uma região de uma unidade quadrada em um triângulo usando o método paralelogramo.


Figura 4. Comparação da transformação de várias seqüências quase aleatórias em um triângulo. Acima está a sequência de Holton, no meio está a sequência de Sable, abaixo está a sequência $$$R_2$. Pode-se observar que ocorre aglomeração significativa dos pontos na sequência de Holton e formação significativa de bandas na sequência de Sobol. Comparado a eles, em sequência $$$R_2$os pontos são distribuídos de maneira muito uniforme e quase não há aglomeração ou listras perceptíveis.

Dos três métodos diferentes de triangulação e de muitas seqüências quase aleatórias, o método do paralelogramo aplicado ao método de sequência $$$R_2$é a única combinação que cria constantemente resultados aceitáveis ​​em termos de manter uma baixa variação sem distorção.

Os excelentes resultados dessa combinação podem ser examinados em mais detalhes na Figura 5.


Figura 5. Você pode ver que a sequência convertida $$$R_2$fornece uma maneira muito simples, mas eficaz, de distribuir uniformemente muitos dos $$$N$pontos no triângulo. Funciona com triângulos agudos e obtusos. (Cor indica o arranjo).

3. Outros aspectos

Distorção

O método do paralelogramo requer a escolha de dois lados do triângulo como vetores de base.

Se os vértices são marcados em ordem aleatória, os padrões de pontos geralmente se assemelham aos mostrados na Figura 6.


Figura 6. Padrões de pontos obtidos escolhendo aleatoriamente a ordem dos vértices. Observe que, na maioria dos casos, a distorção é claramente perceptível.

No entanto, acontece que, com uma escolha cuidadosa da ordem dos vértices, as distorções podem ser significativamente reduzidas. Mais notavelmente, se você rotular o triângulo para que $$$A$é o maior ângulo (ou seja, o lado maior fica contra ele), então os lados $$$\ pmb {AB}$e $$$\ pmb {AC}$são usados ​​como dois lados de um paralelogramo.

Se tomarmos essa ordem, obteremos os padrões dos pontos mostrados acima nas Figuras 1, 4 e 5.

No entanto, mesmo com uma certa ordem de vértices, em alguns casos, os efeitos de distorção ainda são perceptíveis. Eles são mais visíveis quando um dos ângulos nos triângulos é muito pequeno. No caso de triângulos obtusos, quando o menor ângulo é inferior a 30 graus, é visível alguma distorção; no caso de triângulos agudos, quando o menor ângulo é inferior a 20 graus, a distorção se torna visível. (Se os triângulos amostrados fazem parte da malha de Delaunay, esses problemas de distorção podem ser mínimos, porque a triangulação de Delaunay foi projetada especificamente para minimizar o número de triângulos com pequenos ângulos.)

Outras formas

Infelizmente, a técnica do paralelogramo não pode ser usada para outras formas, porque usa simetria de triângulo. Para algumas figuras, bons resultados podem ser obtidos usando o método de distribuição de probabilidade inversa. A seguir, é apresentado um exemplo de como a sequência $$$R_2R_2$com uma baixa divergência, você pode converter para uma região delimitada por uma curva gaussiana, mantendo uma distância uniforme entre os pontos.