Como posso concentrar pontos em áreas de maior curvatura?

Como posso distribuir pontos sobre uma superfície implícita, para concentrá-los mais densamente em áreas de maior curvatura?

Eu considerei adicionar pontos aleatoriamente e rejeitar pontos não necessários com base na curvatura, mas gostaria de saber se existe uma abordagem melhor que dê uma distribuição mais uniforme em áreas de curvatura semelhante, enquanto ainda fornece a maior densidade necessária em alta regiões de curvatura.

Estou procurando especificamente usar esses pontos para uma triangulação da superfície e não quero criar mais triângulos do que preciso para peças relativamente planas.

Isso será aplicado a formas com uma derivada conhecida para que a curvatura em um determinado ponto possa ser calculada.

Isso não precisa ser uma abordagem em tempo real.

algorithm triangulation Trichoplax
fonte

Você está procurando uma maneira mais precisa de colher amostras de uma distribuição, sem o teste montecarlo, quero dizer? Se você não se importa muito com a abordagem computacional (ou seja, você está procurando uma abordagem precisa, e não o esforço computacional), eu poderia ter uma solução, mas ela poderia ser otimizada, é claro.

User8469759

Você conhece a função analítica ou pode apenas amostrá-la? Você conhece sua derivada analítica?

Julien Guertault

@JulienGuertault Minha edição esclarece?

Trichoplax

@Lukkio Gostaria primeiro de precisão, depois a otimização pode chegar mais tarde quando a abordagem estiver funcionando.

Trichoplax

Você pode dar uma olhada nos métodos de elementos finitos , que também usam triangulação (ou mais geralmente: simplicidades) e geralmente enfrentam o problema de precisar de uma densidade de amostragem mais alta em regiões selecionadas. Eles são obrigados a ter desenvolvido algoritmos para isso.

Wrzlprmft

Respostas:

A idéia que eu tentaria aplicar seria a seguinte: Faço o exemplo da curva, mas deve ser direta para a aplicação da superfície.

Digamos que temos uma curva uniformemente parametrizada. Digamos que o parâmetro da curva é . Seu objetivo é amostrar o ponto correspondente ao valor de modo que a curvatura seja alta. $\gamma$ $s$ $s$

Se você obtiver a magnitude da curvatura , isso também será função de . Então, se você normalizar a função, você receberá uma distribuição de probabilidade. Se você obtiver a integral dessa distribuição, terá a distribuição cumulativa. Vamos chamar essa função cumulativa . $c$ $s$ $|c|$ $C(s)$

O problema de amostragem de uma distribuição fornecida pela função cumulativa é bem conhecido, portanto, basicamente, depois de ter amostrado um conjunto de valores , esse valor estará relacionado aos pontos de interesse. $s_0,s_1,\dots,s_n$

A aplicação desse método ao caso da superfície deve ser reta, pois basicamente você tem uma função de distribuição cumulativa bidimensional, mas o problema de amostragem é exatamente o mesmo.

Apenas para dar alguns detalhes, é basicamente amostragem de uma distribuição, pois a função cumulativa envolve duas etapas:

pegue um valor aleatório no intervalo , digamos $[0,1]$ $k$
resolva a equação . $C(s) = k$

Essa abordagem é exata, é claro que é cara, mas se você gosta dessa abordagem, pode trabalhar na otimização.

user8469759
fonte

Ainda não há suporte ao látex.

Joojaa

Eu estava procurando por algo que pudesse ser usado com uma superfície implícita, mesmo que não tenha uma parametrização. Sempre é possível parametrizar uma superfície implícita se a derivada é conhecida?

Trichoplax

Quaisquer perguntas que possam se beneficiar do MathJax para fórmulas podem ser adicionadas a essa meta resposta para aumentar nossas chances de obter o MathJax. (Este já foi adicionado.)

trichoplax

Lembre-se de que o que você precisa é da função de distribuição derivada da curvatura, você disse que pode derivar tudo (a propósito, que tipo de superfície você tem? Isto é, a equação). Enfim ... o que você quer dizer com "derivado conhecido"? você conhece uma fórmula explícita da derivada? ou está implícito também? (isto é, descrito por meio da equação diferencial)?

user8469759

A propósito ... se a curva / superfície é algébrica (quero dizer, expressa por equipe polinomial ou racional), existem métodos computacionais baseados em bspline / nurbs que explicam como executar a parametrização de tais curvas. Dei uma olhada aqui em docs.lib.purdue.edu/cgi/… , um método mais avançado (mesmo avançado) pode ser encontrado em um dos meus livros favoritos sobre Nurbs (o livro NURBS de Tiller).

user8469759

Um bom ponto de partida é o artigo clássico Usando partículas para amostrar e controlar superfícies implícitas , publicado em SIGGRAPH 1994.

Uma simples simulação de partículas descrita no artigo Amostrando objetos implícitos com sistemas de partículas com base física ( Computers & Graphics , 1996) para curvas também funciona para superfícies; consulte Textura dinâmica para superfícies implícitas para obter exemplos.

Para um exemplo mais recente, consulte Representação de formas e tons para superfícies implícitas ( Computers & Graphics , 2011).

lhf
fonte

A seguinte abordagem ingênua provavelmente não produzirá pontos tão bem distribuídos quanto os dados por Lhf , mas deve ser muito mais fácil de implementar e computacionalmente mais rápido:

$x$ $y$ $d(x,y)$ $x$ $y$ $x$ $y$

$A$

$x$ $d(x,x)$
$A$
$A$
1. $x$ $y$ $A$
2. $z$ $d(x,y)$ $A$
3. $z$ $d(x,y)$ $A$
  - se sim, descarte-o.
  - $x$ $z$ $y$ $z$ $z$ $A$

$A$

Wrzlprmft
fonte