¿Cómo puedo concentrar puntos en áreas de mayor curvatura?

11

¿Cómo puedo distribuir puntos sobre una superficie implícita, para concentrarlos más densamente en áreas de mayor curvatura?

He considerado agregar puntos al azar y rechazar puntos no requeridos en función de la curvatura, pero me gustaría saber si hay un mejor enfoque que ofrezca una distribución más uniforme sobre áreas de curvatura similar, mientras que aún proporciona la mayor densidad requerida en alta regiones de curvatura.

Estoy buscando específicamente el uso de estos puntos para una triangulación de la superficie, y no quiero crear más triángulos de los que necesito para partes relativamente planas.


Esto se aplicará a formas con una derivada conocida para que se pueda calcular la curvatura en un punto dado.

Esto no necesita ser un enfoque en tiempo real.

trichoplax
fuente
¿Está buscando una forma más precisa de tomar muestras de una distribución, sin la prueba de montecarlo? Si no le importa mucho el enfoque computacional (es decir, está buscando un enfoque preciso en lugar del esfuerzo computacional), podría tener una solución, pero, por supuesto, podría optimizarse.
user8469759
3
¿Conoces la función analítica o solo puedes probarla? ¿Conoces su derivada analítica?
Julien Guertault
@JulienGuertault ¿Se aclara mi edición?
trichoplax
@Lukkio Quisiera precisión primero, luego la optimización puede venir una vez que el enfoque esté funcionando.
trichoplax
1
Es posible que desee echar un vistazo a los métodos de elementos finitos , que también usan triangulación (o más generalmente: simplificaciones) y a menudo enfrentan el problema de necesitar una mayor densidad de muestreo en regiones seleccionadas. Están obligados a haber desarrollado algoritmos para esto.
Wrzlprmft

Respuestas:

11

La idea que intentaría aplicar sería la siguiente: hago el ejemplo para la curva, pero debería ser sencillo para la aplicación de la superficie.

Digamos que tenemos una curva uniformemente parametrizada. Digamos que el parámetro de la curva es . Su objetivo es muestrear el punto correspondiente al valor de modo que la curvatura sea alta.s sγss

Si obtiene la magnitud de la curvatura , esto también será función de . Entonces, si normaliza la función, obtendrá una distribución de probabilidad. Si obtiene la integral de dicha distribución, tendrá la distribución acumulativa. Llamemos a esta función acumulativa .s | c | C ( s )cs|c|C(s)

El problema de muestreo de una distribución dada por la función acumulativa es bien conocido, por lo que, básicamente, una vez que haya muestreado un conjunto de valores , dicho valor estará relacionado con los puntos de interés.s0,s1,,sn

La aplicación de este método en el caso de la superficie debe ser recta, ya que básicamente tiene una función de distribución acumulativa bidimensional, pero el problema de muestreo es exactamente el mismo.

Solo para dar algunos detalles, es básicamente un muestreo de una distribución dada la función acumulativa que implica dos pasos:

  1. tomar un valor aleatorio en el intervalo , digamosk[0,1]k

  2. resuelva la ecuación .C(s)=k

Este enfoque es exacto, por supuesto que es costoso, pero si le gusta, puede trabajar en la optimización.

user8469759
fuente
1
No hay soporte de látex todavía.
joojaa
Estaba buscando algo que pudiera usarse con una superficie implícita, incluso si no tiene una parametrización. ¿Siempre es posible parametrizar una superficie implícita si se conoce la derivada?
trichoplax
Cualquier pregunta que se beneficiaría de MathJax para las fórmulas se puede agregar a esta meta respuesta para aumentar nuestras posibilidades de obtener MathJax. (Este ya se ha agregado.)
trichoplax
Recuerda que lo que necesitas es la función de distribución derivada de la curvatura, dijiste que puedes derivar todo (por cierto, ¿qué tipo de superficie tienes? Es decir, la ecuación). De todos modos ... ¿qué quieres decir con "derivado conocido"? ¿Conoces una fórmula explícita de la derivada? o también está implícito? (es decir, descrito por medio de la ecuación diferencial)?
user8469759
1
Por cierto ... si la curva / superficie es algebric (es decir, expresada por polinomios o personal racional) hay métodos computacionales basados ​​en bspline / nurbs que explican cómo realizar la parametrización de tales curvas. Eché un vistazo aquí docs.lib.purdue.edu/cgi/… , se puede encontrar otro método (incluso avanzado) en uno de mi libro favorito sobre Nurbs (El libro NURBS de Tiller).
user8469759
2

Un buen punto de partida es el artículo clásico Utilizando partículas para muestrear y controlar superficies implícitas , publicado en SIGGRAPH 1994.

Una simple simulación de partículas descrita en el documento Muestreo de objetos implícitos con sistemas de partículas basados ​​físicamente ( Computers & Graphics , 1996) para curvas también funciona para superficies; vea Textura dinámica para superficies implícitas para ver ejemplos.

Para un ejemplo más reciente, vea Representación de forma y tono para superficies implícitas ( Computers & Graphics , 2011).

lhf
fuente
2

El siguiente enfoque ingenuo probablemente no arrojará puntos tan bien distribuidos como los dados por Lhf , pero debería ser mucho más fácil de implementar y computacionalmente más rápido:

Para dos puntos e , denota la distancia promedio que desea que tengan los puntos con la curvatura promedio de e , por ejemplo, alguna constante multiplicada por la inversa de la curvatura promedio de e .y d ( x , y ) x y x yxyd(x,y)xyxy

Ahora construya su colección de puntos sucesivamente:A

  1. Seleccione un punto aleatorio y agregue dos puntos, de modo que los tres puntos formen un triángulo equilátero con una longitud de borde .d ( x , x )xd(x,x)

  2. Agregue todos los puntos a y márquelos como adyacentes.A

  3. Haga lo siguiente repetidamente hasta que ya no haya adyacencias en :A

    1. Seleccionar dos puntos adyacentes y de . Marcarlos como no adyacentes.y AxyA
    2. Considere un punto que tiene una distancia de desde ambos puntos. De los dos puntos posibles, seleccione el que apunta hacia afuera de (esto necesita algo de trabajo, pero debe ser sencillo).d ( x , y ) Azd(x,y)A
    3. Compruebe si está más cerca que a cualquier punto de que aún esté adyacente a otro punto.d ( x , y ) Azd(x,y)A

      • en caso afirmativo, deséchelo.
      • si no, la marca y , así como y como adyacente y añadir a .z y z z AxzyzzA

Al final, debería ser una colección de puntos que coincidan con sus criterios. De alguna manera, acabas de crear una triangulación, pero puede ser patológica y, por lo tanto, probablemente deberías triangular los puntos nuevamente.A

Wrzlprmft
fuente