En mi perfilador, encontrar coordenadas barcéntricas es aparentemente un cuello de botella. Estoy buscando hacerlo más eficiente.
Sigue el método en shirley , donde calculas el área de los triángulos formados incrustando el punto P dentro del triángulo.
Código:
Vector Triangle::getBarycentricCoordinatesAt( const Vector & P ) const
{
Vector bary ;
// The area of a triangle is
real areaABC = DOT( normal, CROSS( (b - a), (c - a) ) ) ;
real areaPBC = DOT( normal, CROSS( (b - P), (c - P) ) ) ;
real areaPCA = DOT( normal, CROSS( (c - P), (a - P) ) ) ;
bary.x = areaPBC / areaABC ; // alpha
bary.y = areaPCA / areaABC ; // beta
bary.z = 1.0f - bary.x - bary.y ; // gamma
return bary ;
}
Este método funciona, ¡pero estoy buscando uno más eficiente!
barycentric-coordinates
bobobobo
fuente
fuente
Respuestas:
Transcrito de Detección de colisión en tiempo real de Christer Ericson (que, por cierto, es un libro excelente):
Esta es efectivamente la regla de Cramer para resolver un sistema lineal. No será mucho más eficiente que esto: si esto sigue siendo un cuello de botella (y podría serlo: no parece que sea muy diferente en cuanto a cómputo que su algoritmo actual), probablemente necesitará encontrar otro lugar para ganar una aceleración
Tenga en cuenta que un número decente de valores aquí es independiente de p; se pueden almacenar en caché con el triángulo si es necesario.
fuente
p
para esta función.La regla de Cramer debería ser la mejor manera de resolverlo. No soy un tipo gráfico, pero me preguntaba por qué en el libro Real-Time Collision Detection no hacen lo siguiente más simple:
Esto resuelve directamente el sistema lineal 2x2
mientras que el método del libro resuelve el sistema
fuente
.z
dimensión () (específicamente, que no existe)?Ligeramente más rápido: calcula previamente el denominador y multiplica en lugar de dividir. Las divisiones son mucho más caras que las multiplicaciones.
En mi implementación, sin embargo, almacené en caché todas las variables independientes. Precalculo lo siguiente en el constructor:
Entonces el código final se ve así:
fuente
Usaría la solución que publicó John, pero usaría el SSS 4.2 dot intrínseco y sse rcpss intrínseco para la división, suponiendo que esté bien restringiéndose a Nehalem y procesos más nuevos y precisión limitada.
Alternativamente, podría calcular varias coordenadas barcéntricas a la vez utilizando sse o avx para una aceleración de 4 u 8x.
fuente
Puede convertir su problema 3D en un problema 2D proyectando uno de los planos alineados a los ejes y utilizando el método propuesto por user5302. Esto dará como resultado exactamente las mismas coordenadas barcéntricas siempre y cuando se asegure de que su triángulo no se proyecte en una línea. Lo mejor es proyectar en el plano alineado al eje que esté lo más cerca posible de la orientación de su triángulo. Esto evita problemas de co-linealidad y garantiza la máxima precisión.
En segundo lugar, puede calcular previamente el denominador y almacenarlo para cada triángulo. Esto guarda los cálculos posteriores.
fuente
Intenté copiar el código de @ NielW a C ++, pero no obtuve los resultados correctos.
Fue más fácil leer https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Barycentric_coordinates_on_triangles y calcular el lambda1 / 2/3 como se indica allí (no se necesitan funciones vectoriales).
Si p (0..2) son los puntos del triángulo con x / y / z:
Precalc para triángulo:
entonces las lambdas para un punto "punto" son
fuente
Para un punto dado N dentro del triángulo ABC, puede obtener el peso barcéntrico del punto C dividiendo el área del subtriángulo ABN por el área total del triángulo AB C.
fuente