Yo estaba esperando que alguien puede señalar una fórmula eficaz para 4×4 afín a la matriz de transformación. Actualmente mi código utiliza cofactor de expansión y se asigna una matriz temporal para cada cofactor. Es fácil de leer, pero es más lento de lo que debería ser.

Nota, esto no es tarea y sé cómo hacerlo de forma manual utilizando 4×4 co-factor de expansión, es sólo un dolor y no es realmente un problema interesante para mí. También he buscado en google y me encontré con un par de sitios que te dan la fórmula ya (http://www.euclideanspace.com/maths/algebra/matrix/functions/inverse/fourD/index.htm). Sin embargo, esto probablemente podría ser optimizado por la pre-computación en algunos de los productos. Estoy seguro de que a alguien se le ocurrió la «mejor» fórmula para esto en un momento u otro?

  • ¿Por qué no utilizar algunas bibliotecas existentes? Las posibilidades son aquellos que ya están optimizados.
  • Que es cierto. Por desgracia, que la matriz de código en Java y, a continuación, compilado por GWT. La mayoría de las bibliotecas simplemente no funcionará. También es bastante estrecha de la aplicación. Sólo estoy tratando con matrices de 4×4. No quiero vincular un enorme álgebra lineal biblioteca sólo para obtener inversa() y multiplicar() funcionalidad.
InformationsquelleAutor Budric | 2010-04-12

5 Comentarios

  1. 45

    Usted debe ser capaz de explotar el hecho de que la matriz es afín a la velocidad de las cosas a través de una completa inversa. Es decir, si la matriz tiene este aspecto

    A = [ M   b  ]
        [ 0   1  ]
    

    donde a es 4×4, M es de 3×3, b es 3×1, y la fila inferior es (0,0,0,1), entonces

    inv(A) = [ inv(M)   -inv(M) * b ]
             [   0            1     ]
    

    Dependiendo de su situación, puede ser más rápido para calcular el resultado de la inv(A) * x en lugar de la realidad, la formación de inv(A). En ese caso, las cosas se simplifican a

    inv(A) * [x] = [ inv(M) * (x - b) ]
             [1] = [        1         ] 
    

    donde x es un vector 3×1 (generalmente de un punto 3D).

    Por último, si M representa una rotación (es decir, sus columnas son ortonormales), entonces usted puede utilizar el hecho de que inv(M) = transpose(M). A continuación, calcular la inversa de a es sólo una cuestión de restar la traducción componente, y multiplicando por la transposición de la 3×3 parte.

    Nota de que sea o no de la matriz es ortonormales es algo que usted debe saber desde el análisis del problema. La comprobación durante el tiempo de ejecución sería bastante caro; aunque es posible que desee hacerlo en las versiones de depuración para comprobar que sus supuestos espera.

    La esperanza de que todo eso es claro…

    • Así que la primera fórmula que se obtuvo de «blockwise inversión» (en.wikipedia.org/wiki/Invertible_matrix)? O es que hay otro truco mental? No estoy muy seguro acerca de la inv(A) * x = inv(M) * (x – b). Primero, son de diferentes tamaños – ¿se elimina una fila de Una a la izquierda o añadir una fila a la derecha? Segundo, no estoy seguro de lo que la ecuación se acerca. Tercero, no estoy seguro de lo que se está resolviendo en la ecuación. Oliver mantiene a mencionar para no computing inversas, simbólicamente, pero no sé lo que significa – necesito la inversa para hacer la transformación inversa. Si tienes tiempo me gustaría saber.
    • He editado el inv(A) * x fórmula para hacer que las dimensiones más clara. La primera fórmula fue de en.wikipedia.org/wiki/Affine_transformation. Olvidando afín transforma por un minuto, en general, cuando se está resolviendo Unx = b, desea que la solución inv(A)*b. Pero muchas veces no es necesario real forma de inv(A), acaba de calcular lo que el producto *¿ ser. De vuelta a afín transforma, en aplicaciones 3D, puede que usted no necesita realmente la inversa de la matriz, lo que desea es la inversa de la transformación de que actúa sobre (multiplicando) un vector. Si ese es el caso, entonces el uso de la fórmula podría ser más rápido.
    • Incluso si usted necesita para almacenar la matriz inversa, puede utilizar el hecho de que es afín a reducir el trabajo de computación a la inversa, ya que sólo necesita para invertir una matriz de 3×3 en lugar de 4×4. Y si usted sabe que es una rotación, la informática, la transposición es por tanto más rápido que el de la informática a la inversa, y en este caso, son equivalentes.
    • Y aquí hay una mejor explicación de lo que entiende por computación inv(A) * x: johndcook.com/blog/2010/01/19/dont-invert-that-matrix (el autor es un cartel frecuente en ELLO).
    • Claro ahora. Muy interesante.
  2. 20

    Sólo en caso de que alguien quiera ahorrar algo de escribir, he aquí una versión AS3 escribí basado en la página 9 (más eficiente de la versión de Laplace de Expansión Teorema) de los enlaces indicados anteriormente, por phkahler:

    public function invert() : Matrix4 {
        var m : Matrix4 = new Matrix4();
    
        var s0 : Number = i00 * i11 - i10 * i01;
        var s1 : Number = i00 * i12 - i10 * i02;
        var s2 : Number = i00 * i13 - i10 * i03;
        var s3 : Number = i01 * i12 - i11 * i02;
        var s4 : Number = i01 * i13 - i11 * i03;
        var s5 : Number = i02 * i13 - i12 * i03;
    
        var c5 : Number = i22 * i33 - i32 * i23;
        var c4 : Number = i21 * i33 - i31 * i23;
        var c3 : Number = i21 * i32 - i31 * i22;
        var c2 : Number = i20 * i33 - i30 * i23;
        var c1 : Number = i20 * i32 - i30 * i22;
        var c0 : Number = i20 * i31 - i30 * i21;
    
        //Should check for 0 determinant
    
        var invdet : Number = 1 /(s0 * c5 - s1 * c4 + s2 * c3 + s3 * c2 - s4 * c1 + s5 * c0);
    
        m.i00 = (i11 * c5 - i12 * c4 + i13 * c3) * invdet;
        m.i01 = (-i01 * c5 + i02 * c4 - i03 * c3) * invdet;
        m.i02 = (i31 * s5 - i32 * s4 + i33 * s3) * invdet;
        m.i03 = (-i21 * s5 + i22 * s4 - i23 * s3) * invdet;
    
        m.i10 = (-i10 * c5 + i12 * c2 - i13 * c1) * invdet;
        m.i11 = (i00 * c5 - i02 * c2 + i03 * c1) * invdet;
        m.i12 = (-i30 * s5 + i32 * s2 - i33 * s1) * invdet;
        m.i13 = (i20 * s5 - i22 * s2 + i23 * s1) * invdet;
    
        m.i20 = (i10 * c4 - i11 * c2 + i13 * c0) * invdet;
        m.i21 = (-i00 * c4 + i01 * c2 - i03 * c0) * invdet;
        m.i22 = (i30 * s4 - i31 * s2 + i33 * s0) * invdet;
        m.i23 = (-i20 * s4 + i21 * s2 - i23 * s0) * invdet;
    
        m.i30 = (-i10 * c3 + i11 * c1 - i12 * c0) * invdet;
        m.i31 = (i00 * c3 - i01 * c1 + i02 * c0) * invdet;
        m.i32 = (-i30 * s3 + i31 * s1 - i32 * s0) * invdet;
        m.i33 = (i20 * s3 - i21 * s1 + i22 * s0) * invdet;
    
        return m;
    }
    

    Esta producido con éxito una matriz identidad cuando me multiplicado varias 3D matrices de transformación por el inverso de retorno de este método. Estoy seguro de que usted puede buscar/reemplazar para conseguir esto en cualquier idioma que quieras.

    • Muchas gracias por publicar, @Robin, esto me ayudó mucho en mi proyecto de C#. He encontrado un pequeño error en el código anterior: en la definición de c5 debe leer i31 * i23. Después de la fijación de este, la inversión de matrices funciona como un encanto para mí.
    • Hola @AndersGustafsson, creo que significó la definición de c4 – gracias por la corrección – Robin va a solucionar el original.
    • Tienes toda la razón, que tonta de mí para hacer de este error tipográfico comentando un error tipográfico 🙂 Gracias por señalarlo.
  3. 19

    Para el seguimiento de pkhaler‘s y Robin Hilliard‘s excelentes respuestas de arriba, aquí es Robin ActionScript 3 código convierte en un método de C#. Esperemos que esto le puede ahorrar algo de escribir para otros los desarrolladores de C#, así como C/C++ y Java developers en la necesidad de un 4×4 matriz de función de inversión:

    public static double[,] GetInverse(double[,] a)
    {
        var s0 = a[0, 0] * a[1, 1] - a[1, 0] * a[0, 1];
        var s1 = a[0, 0] * a[1, 2] - a[1, 0] * a[0, 2];
        var s2 = a[0, 0] * a[1, 3] - a[1, 0] * a[0, 3];
        var s3 = a[0, 1] * a[1, 2] - a[1, 1] * a[0, 2];
        var s4 = a[0, 1] * a[1, 3] - a[1, 1] * a[0, 3];
        var s5 = a[0, 2] * a[1, 3] - a[1, 2] * a[0, 3];
    
        var c5 = a[2, 2] * a[3, 3] - a[3, 2] * a[2, 3];
        var c4 = a[2, 1] * a[3, 3] - a[3, 1] * a[2, 3];
        var c3 = a[2, 1] * a[3, 2] - a[3, 1] * a[2, 2];
        var c2 = a[2, 0] * a[3, 3] - a[3, 0] * a[2, 3];
        var c1 = a[2, 0] * a[3, 2] - a[3, 0] * a[2, 2];
        var c0 = a[2, 0] * a[3, 1] - a[3, 0] * a[2, 1];
    
        //Should check for 0 determinant
        var invdet = 1.0 /(s0 * c5 - s1 * c4 + s2 * c3 + s3 * c2 - s4 * c1 + s5 * c0);
    
        var b = new double[4, 4];
    
        b[0, 0] = ( a[1, 1] * c5 - a[1, 2] * c4 + a[1, 3] * c3) * invdet;
        b[0, 1] = (-a[0, 1] * c5 + a[0, 2] * c4 - a[0, 3] * c3) * invdet;
        b[0, 2] = ( a[3, 1] * s5 - a[3, 2] * s4 + a[3, 3] * s3) * invdet;
        b[0, 3] = (-a[2, 1] * s5 + a[2, 2] * s4 - a[2, 3] * s3) * invdet;
    
        b[1, 0] = (-a[1, 0] * c5 + a[1, 2] * c2 - a[1, 3] * c1) * invdet;
        b[1, 1] = ( a[0, 0] * c5 - a[0, 2] * c2 + a[0, 3] * c1) * invdet;
        b[1, 2] = (-a[3, 0] * s5 + a[3, 2] * s2 - a[3, 3] * s1) * invdet;
        b[1, 3] = ( a[2, 0] * s5 - a[2, 2] * s2 + a[2, 3] * s1) * invdet;
    
        b[2, 0] = ( a[1, 0] * c4 - a[1, 1] * c2 + a[1, 3] * c0) * invdet;
        b[2, 1] = (-a[0, 0] * c4 + a[0, 1] * c2 - a[0, 3] * c0) * invdet;
        b[2, 2] = ( a[3, 0] * s4 - a[3, 1] * s2 + a[3, 3] * s0) * invdet;
        b[2, 3] = (-a[2, 0] * s4 + a[2, 1] * s2 - a[2, 3] * s0) * invdet;
    
        b[3, 0] = (-a[1, 0] * c3 + a[1, 1] * c1 - a[1, 2] * c0) * invdet;
        b[3, 1] = ( a[0, 0] * c3 - a[0, 1] * c1 + a[0, 2] * c0) * invdet;
        b[3, 2] = (-a[3, 0] * s3 + a[3, 1] * s1 - a[3, 2] * s0) * invdet;
        b[3, 3] = ( a[2, 0] * s3 - a[2, 1] * s1 + a[2, 2] * s0) * invdet;
    
        return b;
    }
    
    • Gracias por esto, es realmente útil!
    • También, lo que confirma que el algoritmo funciona correctamente. 🙂
  4. 4

    CREO que en gran medida puede reducir el código y el tiempo por precomputing un montón (12?) 2×2 determinantes. Dividir la matriz en la mitad verticalmente y calcular cada 2×2 tanto en la parte superior y la mitad inferior. Uno de estos más pequeños determinantes se utiliza en todos los términos que usted necesita para el cálculo mayor y cada uno de ellos consigue reutilizar.

    También, no usar un factor determinante de la función de la reutilización de los sub-factores determinantes calculado para el medico adjunto para obtener el determinante.

    Oh, acabo de encontrar
    este.

    Hay algunas mejoras que usted puede hacer saber su un cierto tipo de transformar demasiado.

    • Gracias, esto me ahorra un montón de tiempo!
    • Muy rápido, buena explicación. Parece funcionar (no ejecutar en contra de una regresión completa de la prueba). Gracias de nuevo.
    • +1 para el enlace; sin embargo, creo que es un error para calcular los inversos simbólicamente… usted debe darse cuenta de cómo muchos innecesarios multiplicaciones y adiciones que se está realizando. Es probablemente aceptable mientras esta parte del código no es el cuello de botella.
    • Yo uso 4×4 para un montón de cosas, así que prefiero la inversa generalizada. Como he dicho, se puede hacer mejor con tipos específicos de transformación. El vinculado el papel todavía es útil para hacer el 3×3 inversa el interrogador parece estar usando. Y se puede hacer aún mejor todavía si sabe el 3×3 es una pura rotación – si mal no recuerdo es el inverso es el de incorporar.
  5. 1

    Creo que la única manera de calcular una inversa es resolver n veces la ecuación: a x = y, donde y se extiende por la unidad de vectores, es decir, la primera es (1,0,0,0), el segundo es (0,1,0,0), etc.

    (El uso de los cofactores (la regla de Cramer) es una mala idea, a menos que quieras una simbólico fórmula para la inversa.)

    La mayoría de álgebra lineal bibliotecas van a permitir que usted para resolver los sistemas lineales, e incluso para calcular una inversa. Ejemplo en python (utilizando numpy):

    from numpy.linalg import inv
    inv(A) # here you go
    

Dejar respuesta

Please enter your comment!
Please enter your name here