tengo una cara 3D definido por n puntos (v1, v2, v3, ..., vn), en coordenadas 3D, y tengo un rayo de la ecuación:Ray y cara 3D Intersección
P=P0+t(P1-P0).
donde 0<=t<=1.
Ahora, ¿cómo encontrar el punto de intersección (o falta de) entre este rayo y la cara?
Además, sería genial si hay una implementación de C# existente en esto?
Editar: La cara 3D puede ser cóncava o convexa. Todos los puntos son coplanarios.
supongo que su polígono 3D es plana (de lo contrario no es realmente un polígono y no es así definido). Por lo tanto, puede encontrar una base ortonormal 2D para este plano. Lo que significa que puede usar cualquier algoritmo de triangulación 2D (puede encontrar muchas implementaciones de C# en la web) y volver a 3D usando su base ortonormal. De esta manera obtendrás triángulos 3D y podrás realizar fácilmente tu prueba de intersección de polígono de rayos ejecutando múltiples pruebas de intersección triángulo-rayo.
Otra forma es realizar un cálculo de intersección de plano de rayos. Tome el punto de intersección P, represéntelo utilizando coordenadas 2D con la base ortonormal anterior. Además, como en la solución anterior, represente su polígono en 2D utilizando la misma base. Luego ejecuta cualquier algoritmo 2D "is point in polygon" y obtendrás los resultados.
actualización: Aquí está la matemáticas Usted puede tomar cualquiera de los dos puntos en el plano P1, P2 (por ejemplo dos de los puntos del polígono) y tomar el vector u = p2 - p1. Normalízalo, y es el primer vector base. Luego toma el N normal del avión y calcula v = cross_product (u, N) y normaliza v. Este es el segundo vector de base. Tenga en cuenta que ambos vectores tienen una unidad de longitud y que son ortogonales entre sí. Por lo tanto, forman una base ortonormal.
Defina p1 como el origen del avión. A continuación, la traducción a 2D de cualquier punto Q en el polígono (q puede ser uno de los vértices del polígono, o cualquier otro punto en el plano del polígono):
x = dot_product(q - p1, u)
y = dot_product(q - p1, v)
Aquí x, y son las coordenadas en 2D es el punto.
Así que después de traducir todo para 2D y haciendo sus algoritmos 2D se puede traducir cualquier punto 2D (x, y) de nuevo a 3D como esto:
q = p1 + x * u + y * v
Aquí * es el producto escalar del vector (x, y son los escalares y u, v son los vectores).
Alex.
Lo que busca es un algoritmo de intersección de rayos-polígono, aquí hay un enlace a la entrada de gráficos gemas para ello: http://www-graphics.stanford.edu/courses/cs348b-98/gg/intersect.html
es un triángulo de rayos, no de rayos-polígono. Me doy cuenta de que podrías decir que podemos romper triangularizar un polígono. Pero en mi caso aquí la triangulación puede no ser fácil ya que estoy haciendo un polígono 3D. Además, el polígono que tengo puede ser cóncavo, por lo que la solución presente dentro de tu enlace puede no funcionar. – Graviton
@Ngu, Sí, esto no funcionará para polígonos cóncavos. Usa la solución de Alex. –
el enlace ya no funciona – Joh
Si sus puntos no son coplanarios (es decir, no se encuentran todos en un solo plano), entonces debe subdividir la superficie en un conjunto de planos y luego hacer la intersección de línea y polígono para cada plano .Mejor aún, defina una lista de triángulos y luego busque los resultados de intersección línea-triángulo.
Sin embargo, no dice si sus puntos definen un objeto facetado (es decir, formado por triángulos) o define un conjunto de puntos de control para una superficie curva. El primero es manejado por lo anterior. Si se trata de una superficie curva, creo que se trata de un problema incalculable, es decir, no hay una solución trivial al problema de determinar la intersección de una línea y una superficie curva definida por un conjunto de puntos. Lo mejor que puede hacer es usar un proceso iterativo para encontrar el punto de intersección, pero incluso esto podría conducir a búsquedas inestables (es decir, búsquedas que nunca se completan).
Creo que convertir a un conjunto de triángulos es la mejor respuesta.
los puntos son coplanares – Graviton
si los puntos son coplanarios, ¿cómo cambiaría (o simplificaría) la solución de Alex? – Graviton
@Ngu: en ese caso, primero haga una prueba de plano de línea; si esto falla, no se cruza con nada. Si pasa, use el punto de intersección para determinar el resultado. La conversión a triángulos sería más fácil, creo. También puede proyectar en 2D y contar cuántos segmentos de línea están a la izquierda (es decir, la misma Y) que el punto de intersección (impar = dentro, incluso = fuera) – Skizz
¿es posible hacerlo sin la transformación ortonormal 3D-2D? ¿Y hay alguna referencia sobre cómo hacer la transformación ortonormal? Me encantaría leerlos, ¡gracias! – Graviton
Escribiré la respuesta en el mensaje mismo. Los comentarios tienen malas capacidades de formateo :) – Alex
gracias. Eso es bueno – Graviton