Anterior nesta lição, explicamos que vetores (ou pontos) podem ser escritos como matrizes (uma linha, três colunas). Note, no entanto, que também poderíamos tê-los escrito como matrizes (três linhas, uma coluna). Tecnicamente, estas duas formas de expressar pontos e vetores como matrizes são perfeitamente válidas e escolher um modo ou outro é apenas uma questão de convenção.
Vetor escrito como matriz: \( V=\begin{bmatrix}x & y & z\end{bmatrix}\)
Vector escrito como matriz: \V==begin{bmatrix}x=y=zend{bmatrix})
No primeiro exemplo ( matriz) expressamos o nosso vector ou ponto no que chamamos de ordem de fila: o vector (ou ponto) é escrito como uma fila de três números. No segundo exemplo, dizemos que pontos ou vetores são escritos em ordem coluna-maior: escrevemos as três coordenadas do vetor ou ponto na vertical, como uma coluna.
Lembrar que expressamos pontos e vetores como matrizes para multiplicá-los por matrizes de transformação (por uma questão de simplicidade trabalharemos com elas ao invés de matrizes). Aprendemos também que só podemos multiplicar matrizes quando o número de colunas da matriz da esquerda e o número de linhas da matriz da direita são os mesmos. Em outras palavras, as matrizes e podem ser multiplicadas umas com as outras, mas as matrizes e não podem. Note que se escrevermos um vector como uma matriz podemos multiplicá-lo por uma matriz (assumindo que esta matriz está à direita dentro da multiplicação), mas se escrevermos este vector como uma matriz então não podemos multiplicá-lo por uma matriz. Isto é ilustrado nos exemplos seguintes. As dimensões internas (3 e 3) das matrizes envolvidas na multiplicação são as mesmas (em verde) então esta multiplicação é válida (e o resultado é um ponto transformado escrito na forma de uma matriz):
$$* = \begin{bmatrix}x & y & z\end{bmatrix} * \begin{bmatrix}c_{00}&c_{01}&{c_{02}}\\c_{10}&c_{11}&{c_{12}}\\c_{20}&c_{21}&{c_{22}}\\\end{bmatrix} =\begin{bmatrix}x’&y’&z’\end{bmatrix}$$
The As dimensões interiores (1 e 3) das matrizes envolvidas na multiplicação não são as mesmas (em vermelho), pelo que esta multiplicação não é possível:
$$*rightarrow {begin{bmatrix}xxxxx{bmatrix} *begin{bmatrix} c_{00}&c_{01}&{c_{02}}} c_{10}&c_{11}&{c_{12}} c_{20}&c_{21}&{c_{22}}}}end{bmatrix}$7789> Então o que fazemos? A solução para este problema não é multiplicar o vetor ou o ponto pela matriz, mas a matriz M pelo vetor V. Em outras palavras, movemos o ponto ou vetor para a direita dentro da multiplicação:
Precisamos ser cuidadosos sobre como estes termos são realmente usados. Por exemplo, a documentação do Maya diz que “as matrizes são pós-multiplicadas no Maya”. Por exemplo, para transformar um ponto P do espaço objeto para o espaço-mundo (P’) você precisaria ser pós-multiplicado pela worldMatrix. (P’ = P x WM)”, o que é confuso porque na verdade é uma pré-multiplicação, mas eles estão falando sobre a posição da matriz em relação ao ponto neste caso em particular. Isso é na verdade um uso incorreto da terminologia. Deveria ter sido escrito que em Maya, pontos e vetores são expressos como vetores principais e que portanto são pré-multiplicados (significando que o ponto ou vetor aparece antes da matriz na multiplicação).
A tabela seguinte resume as diferenças entre as duas convenções (onde P, V e M respectivamente significam Ponto, Vetor e Matriz).
|
Ponto de ordem principal |
\(P/V=\begin{bmatrix}x & y & z\end{bmatrix}\) |
Esquerda ou prémultiplicação |
P/V * M |
| >
Coluna-ordem maior |
\(P/V==begin{bmatrix}x {bmatrix}x {bmatrix}) |
Direito ou pósmultiplicação |
M * P/V |
Agora que aprendemos sobre estas duas convenções você pode perguntar “não se trata apenas de escrever coisas no papel?”. Sabemos como calcular o produto de duas matrizes A e B: multiplique cada coeficiente dentro da linha corrente de A pelos elementos associados dentro da coluna corrente de B e resuma o resultado. Vamos aplicar esta fórmula usando as duas convenções e vamos comparar os resultados:
| Reta-maior ordem | |
|---|---|
|
$${ \begin{bmatrix}x & y & z\end{bmatrix} *begin{bmatrix}a & b & c {d & e & f {g & h & i}end{bmatrix} }$$ |
$$$${l}x’ = x * a + y * d + z * g\\\y’ = x * b + y * e + z * h\z’ = x * c + y * f + z * i}end{array} $$ |
| Column-major order | |
|
$$${begin{bmatrix} a & b & c \d & e & f \g & h & i \end{bmatrix} * \begin{bmatrix}x\\y\\z\end{bmatrix} }$$ |
$$$${\i}{l}x’ = a * x + b * y + c * z\i’ = d * x + e * y + f * z\z’ = g * x + h * y + i * z\end{array} }$$ |
Multiplicar um ponto ou um vector por uma matriz deve dar-nos o mesmo resultado quer utilizemos ordem de linha ou de colum-major. Se você usar uma aplicação 3D para girar um ponto por um certo ângulo ao redor do eixo z, você espera que o ponto esteja em certa posição após a rotação, não importa qual convenção interna o desenvolvedor usou para representar pontos e vetores. Entretanto, como você pode ver na tabela acima, multiplicar um ponto (ou vetor) maior e maior de uma linha pela mesma matriz não nos daria claramente o mesmo resultado. Para voltarmos ao normal, precisaríamos de transpor a matriz usada na multiplicação coluna-máxima para termos a certeza de que x’, y’ e z’ são iguais (se precisar de se lembrar qual é a transposição de uma matriz, verifique o capítulo sobre Operações com Matrizes). Aqui está o que obtemos:
| Pedido principal da coluna | |
|---|---|
|
$${ \begin{bmatrix}x & y & z\end{bmatrix} *begin{bmatrix}a & b & c {d & e & f {g & h & i}end{bmatrix} }$$ |
$$$${\i}{l}x’ = x * a + y * d + z * g\\i’ = x * b + y * e + z * h\z’ = x * c + y * f + z * i}end{array} $$ |
| Column-major order | |
|
$$${\begin{bmatrix} a & d & g \b & e & h \c & f & i}end{bmatrix} * \begin{bmatrix}x\\y\\z\end{bmatrix} }$$ |
$$$${\i}{l}x’ = a * x + d * y + g * z\\i’ = b * x + e * y + h * z\z’ = c * x + f * y + i * z\end{array} }$$ |
Em conclusão, passar da ordem de linha-maior para a ordem de coluna-maior envolve não só trocar o ponto ou vetor e a matriz na multiplicação mas também transpor a matriz, para garantir que ambas as convenções dêem o mesmo resultado (e vice-versa).
Destas observações, podemos ver que qualquer série de transformações aplicadas a um ponto ou a um vector quando se utiliza uma convenção de ordem de coluna ou de grandeza pode ser escrita em ordem sequencial (ou ordem de leitura). Imagine, por exemplo, que você quer traduzir o ponto P com a matriz T e depois girá-lo em torno do eixo z com Rz e depois em torno do eixo y com Ry. Você pode escrever:
$$P’=P * T * R_z * R_y$$
Se você fosse usar uma notação de coluna, você precisaria chamar a transformação em ordem inversa (que pode ser contra-intuitiva):
$$P’=R_y * R_z * T * P$$
Então você pode pensar, “deve haver uma razão para preferir um sistema a outro”. Na verdade, ambas as convenções são correctas e dão-nos o mesmo resultado, mas por algumas razões técnicas, os textos de Matemática e Física geralmente tratam os vectores como vectores de coluna.
Ordem de transformação quando usamos matrizes colum-major é mais semelhante em matemática à forma como escrevemos avaliação e composição de funções.
A convenção de matrizes row-major, no entanto, torna as matrizes mais fáceis de ensinar, razão pela qual a usamos para Scratchapixel (assim como para Maya, DirectX. Elas também são definidas como o padrão nas especificações do RenderMan). Entretanto algumas APIs 3D, como OpenGL, usam uma convenção de colunas-maiores.
Implicação em Codificação: Does it Impact Performance?
Há outro aspecto potencialmente muito importante a levar em consideração se você precisar escolher entre row-major e column-major, mas isto não tem nada a ver realmente com as convenções em si e como uma é prática sobre a outra. Tem mais a ver com o computador e com a forma como ele funciona. Lembre-se de que estaremos lidando com matrizes. Tipicamente a implementação de uma matriz em C++ parece assim:
Como você pode ver os 16 coeficientes da matriz são armazenados em uma matriz bidimensional de floats (ou duplas, dependendo da precisão que você precisa. Nossa classe de Matriz C++ é um modelo). O que significa que na memória os 16 coeficientes serão dispostos da seguinte forma: c00, c01, c02, c03, c10, c11, c12, c13, c20, c21, c22, c23, c30, c31, c32, c33. Em outras palavras, elas estão dispostas contiguamente na memória. Agora vamos ver como esses coeficientes são acessados em uma multiplicação vetorial-matriz onde os vetores são escritos em ordem de fila:
Como você pode ver os elementos da matriz para x’ não são acessados sequencialmente. Em outras palavras, para calcular x’ precisamos do 1º, 5º e 9º flutuador da matriz 16 flutuadores da matriz. Para calcular y’ precisamos acessar o 2º, 6º e 10º flutuador desta matriz. E finalmente para z’ precisamos do 3º, 7º e 11º flutuador da matriz. No mundo da computação, acessar elementos de uma matriz em uma ordem não seqüencial, não é necessariamente uma coisa boa. Na verdade, na verdade, potencialmente degrada o desempenho do cache da CPU. Não vamos entrar em muitos detalhes aqui, mas vamos apenas dizer que a memória mais próxima à qual a CPU pode acessar é chamada de cache. Este cache é muito rápido de acessar, mas só pode armazenar um número muito limitado de dados. Quando a CPU precisa acessar alguns dados, ela primeiro verifica se eles existem no cache. Se a CPU acessa esses dados de imediato (cache hit), mas não o faz (cache miss), primeiro precisa criar uma entrada no cache para ele, depois copiar para esse local os dados da memória principal. Este processo é obviamente mais demorado do que quando os dados já existem na cache, então idealmente queremos evitar que a cache falhe o máximo possível. Além de copiar os dados particulares da memória principal, a CPU também copia um pedaço dos dados que vivem bem ao seu lado (por exemplo, os próximos 24 bytes), porque os engenheiros de hardware descobriram que se o seu código precisasse acessar um elemento de um array, por exemplo, era provável que ele acessasse os elementos que o seguiam logo depois. De fato, em programas, nós frequentemente fazemos loop sobre elementos de um array em ordem sequencial e esta suposição é, portanto, provável que seja verdadeira. Aplicado ao nosso problema de matriz, acessar os coeficientes da matriz em ordem não sequencial pode, portanto, ser um problema. Assumindo que a CPU carrega a flutuação solicitada na cache mais as 3 flutuações próximas a ela, nossa implementação atual pode levar a muitas falhas na cache, já que os coeficientes usados para calcular x’ y’ e z’ estão separados por 5 flutuações na matriz. Por outro lado, se você usar uma notação de ordem de coluna maior, computar x’, por exemplo, requer acesso ao 1º, 2º e 3º elementos da matriz.
Os coeficientes são acessados em ordem sequencial, o que também significa que fazemos um bom uso do mecanismo de cache da CPU (apenas 3 cache falham em vez de 9 no nosso exemplo). Em conclusão, podemos dizer que do ponto de vista de programação, implementar nossa multiplicação ponto ou vetor-matriz usando uma convenção de ordem colum-major pode ser melhor, em termos de performance, do que a versão usando a convenção de ordem row-major. Na prática, porém, não temos sido capazes de demonstrar que este foi realmente o caso (quando você compila seu programa usando as bandeiras de otimização -O, -O2 ou -O3, o compilador pode fazer o trabalho para você otimizando loops sobre arrays multidimensionais) e temos usado com sucesso a versão de ordem de ordem maior linha sem qualquer perda de performance em comparação com uma versão do mesmo código usando uma implementação de ordem de maior coluna.
Row-major e Column-Major Order in Computing
Por uma questão de completude, vamos mencionar também que os termos row-major e column-major order também podem ser usados em computação para descrever a forma como os elementos de arrays multidimensionais são dispostos na memória. Em ordem de fila, os elementos de uma matriz multidimensional são dispostos um após o outro, da esquerda para a direita, de cima para baixo. Este é o método utilizado pelo C/C++. Por exemplo a matriz:
$$$M = \begin{bmatrix}1&2&3\\\4&5&6\end{bmatrix}$$
poderia ser escrita em C/C++ como:
e os elementos desta matriz seriam dispostos de forma contígua na memória linear como:
Em ordem de colunas, que é usada por linguagens como FORTRAN e MATLAB, os elementos da matriz são armazenados na memória de cima para baixo, da esquerda para a direita. Usando o mesmo exemplo de matriz, os elementos da matriz seriam armazenados (e acessados) na memória da seguinte forma:
Saber como os elementos de uma matriz são dispostos na memória é importante especialmente quando você tenta acessá-los usando o deslocamento de ponteiro e para a otimização do loop (explicamos anteriormente neste capítulo que isso poderia afetar o desempenho do cache da CPU). No entanto, como só vamos considerar C/C++ como nossa linguagem de programação, o ordenamento por colunas (aplicado à computação) não é de grande interesse para nós. Estamos apenas mencionando o significado dos termos em computação, para que você esteja ciente de que eles podem descrever duas coisas diferentes, dependendo do contexto em que são usados. Você deve ter cuidado para não misturá-los. No contexto da matemática, eles descrevem se você trata vetores (ou pontos) como linhas de coordenadas ou como colunas e o segundo, e no contexto da computação, eles descrevem a forma como uma certa linguagem de programação armazena e acessa elementos de array multidimensional (que matrizes são) na memória.
OpenGL é um caso interessante a esse respeito. Quando a GL foi inicialmente criada, os desenvolvedores escolheram a convenção de vetor de linha-maior. Os desenvolvedores que estenderam o OpenGL pensaram que deveriam voltar para o vetor coluna-maior, o que eles fizeram. Entretanto por razões de compatibilidade, eles não queriam mudar o código para a multiplicação ponto-matriz e decidiram mudar a ordem na qual os coeficientes da matriz eram armazenados na memória. Em outras palavras, OpenGL armazena os coeficientes em ordem coluna-máxima, o que significa que os coeficientes de tradução m03, m13 e m23 de uma matriz usando vetor coluna-máxima têm índices 13, 14, 15 na matriz flutuante, assim como os coeficientes de tradução m30, m31 e m32 de uma matriz usando vetor linha-máxima.
Sumário
As diferenças entre as duas convenções estão resumidas na tabela a seguir:
| Vetor principal de linha (Matemática) | Coluna-major vector (Matemática) | |
|---|---|---|
|
\(P/V=\begin{bmatrix}x & y & z\end{bmatrix}) |
(P/V=\begin{bmatrix}x {bmatrix}x {bmatrix}) |
|
|
Pre-multiplicação \(vM\) |
Pós-multiplicação \(Mv\) |
|
|
A ordem de chamada e a ordem em que as transformações são aplicadas é a mesma: “take P, transform by T, transform by Rz, transform by Ry” é escrito como \(P’=P*T*R_z*R_y\) |
A ordem de chamada é a inversa da ordem em que as transformações são aplicadas: “take P, transform by T, transform by Rz, transform by Ry” é escrito como \(P’=R_y*R_z*T*P\) |
|
|
API: Direct X, Maya |
API: OpenGL, PBRT, Blender |
|
|
As linhas da matriz representam as bases (ou eixos) de um sistema de coordenadas (vermelho: eixo x, verde: eixo y, azul: eixo z) $${\begin{\bmatrix} \color{red}{c_{00}}& \color{red}{c_{01}}&\color{red}{c_{02}}&0\\ \color{green}{c_{10}}& \color{green}{c_{11}}&\color{green}{c_{12}}&0\\ \color{blue}{c_{20}}& \color{blue}{c_{21}}&\color{blue}{c_{22}}&0\\0&0&0&1 \end{bmatrix} } $$ |
As colunas da matriz representam as bases (ou eixos) de um sistema de coordenadas (vermelho: eixo x, verde: eixo y, azul:eixo z) $${ \begin{bmatrix} \color{red}{c_{00}}& \color{green}{c_{01}}&\color{blue}{c_{02}}&0\\ \color{red}{c_{10}}& \color{green}{c_{11}}&\color{blue}{c_{12}}&0\\ \color{red}{c_{20}}& \color{green}{c_{21}}&\color{blue}{c_{22}}&0\\0&0&0&1\end{bmatrix} }$$ |
|
|
Os valores de tradução são armazenados nos elementos c30, c31 e c32. $${\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\Tx&Ty&Tz&1\end{bmatrix} $$ |
Os valores de tradução são armazenados nos elementos c03, c13 e c23. $$$${\begin{\bmatrix}1&0&0&Tx\0&1&0&Ty\0&0&1&Tz\0&0&0&0&0&1}end{bmatrix} }$$ |
|
|
Transpor a matriz para usá-la como uma matriz ordenada por coluna |
Transpor a matriz para usá-la como uma matriz ordenada por coluna > |
Transpor a matriz para usá-la como uma matriz ordenada por colunamatriz maior ordenada |
| Matriz maior (Computação) | Matriz maior (Computação) | |
|
API: Direct X, Maya, PBRT |
API: OpenGL |
Um leitor postou uma pergunta no Stackoverflow sugerindo que a tabela acima era confusa. O tópico é confuso e apesar da nossa melhor tentativa de lançar alguma luz sobre o assunto, muitas pessoas ainda ficam confusas sobre ele. Pensamos que a nossa resposta sobre o Stackoverflow poderia trazer outra visão sobre a questão.
Você tem a teoria (o que você faz em matemática com caneta e papel) e o que você faz com a sua implementação (C++). Estes são dois problemas diferentes.
Matemática: você pode usar duas notações, seja coluna ou linha principal. Com o vetor de linha maior, no papel, você precisa escrever a multiplicação vetorial-matriz vM onde v é o vetor de linha (1×4) e M a sua matriz 4×4. Porquê? Porque matematicamente só pode escrever *, e não o contrário. Da mesma forma, se usar coluna, então o vector precisa de ser escrito verticalmente, ou em notação (4 linhas, 1 coluna). Assim, a multiplicação com uma matriz só pode ser escrita da seguinte forma: . Note que a matriz é colocada na frente do vetor: Mv. A primeira notação é chamada de esquerda ou pré-multiplicação (porque o vetor está no lado esquerdo do produto) e a segunda (Mv) é chamada de direita ou pós-multiplicação (porque o vetor está no lado direito do produto). Como você vê os termos derivam de se o vetor está no lado esquerdo (na frente, ou “pré”) ou no lado direito (depois, ou “post”) da matriz.
Agora, se você precisa transformar um vetor (ou um ponto) então você precisa prestar atenção à ordem de multiplicação, quando você os escreve no papel. Se você quiser traduzir algo com a matriz T e depois girar com R e depois escalar com S, então em um mundo maior coluna, você precisa escrever v’ = S * R * T * v. Em um mundo maior linha você precisa escrever v’ = v * T * R * S.
Isso é para a teoria. Vamos chamar isso de convenção vetorial de linha/coluna.
Computador: então vem o ponto quando você decide implementar isso em C++ dizer. O bom disto é que C++ não lhe impõe nada sobre nada. Você pode mapear os valores dos coeficientes da sua matriz na memória da maneira que você quiser, e você pode escrever o código para executar uma multiplicação de matriz por outra matriz da maneira que você quiser. Da mesma forma como você acessa os coeficientes para uma multiplicação vetorial-matriz depende completamente de você. Você precisa fazer uma distinção clara entre como mapear seus coeficientes na memória e quais convenções você precisa usar do seu ponto de vista matemático para representar seus vetores. Estes são dois problemas independentes. Vamos chamar a esta parte o layout de linha/coluna principal.
Por exemplo, você pode declarar uma classe matriz como um array de, digamos, 16 flutuadores contíguos. Tudo bem. Onde os coeficientes m14, m24, m34 representam a parte de tradução da matriz (Tx, Ty, Tz), então você assume que a sua “convenção” é row-major mesmo que você seja aconselhado a usar a convenção de matriz OpenGL que é dita ser column-major. Aqui a possível confusão vem do fato de que o mapeamento dos coeficientes na memória é diferente da representação mental que você está fazendo a si mesmo de uma matriz “column-major”. Você codifica “linha” mas foi-lhe dito para usar (de um ponto de vista matemático) “coluna”, daí a sua dificuldade em fazer sentido se você faz as coisas certas ou erradas.
O importante é ver uma matriz como uma representação de um sistema de coordenadas definido por três eixos, e uma tradução. Onde e como você armazena esses dados na memória é completamente da sua responsabilidade. Assumindo que os três vectores que representam os três eixos do sistema de coordenadas são nomeados AX(x,y,z), AY(x,y,z), AZ(x,y,z), e o vector de tradução é denotado por (Tx, Ty, Tz), então matematicamente se usar o vector de coluna que tem:
$$M = \begin{bmatrix} AXx & AYx & AZx & Tx\\ AXy & AYy & AZy & Ty \\\ AXz & AYz & AZz & Tz \ 0 & 0 & 1 & 1\end{bmatrix}$$
Os eixos do sistema de coordenadas são escritos verticalmente. Agora se você tiver se você usar row-major:
$$M = \begin{bmatrix} AXx & AXy & AXz & 0\\ AYx & AYy & AYz & 0 \ AZx & AZy & AZz & 0 \ Tx & Ty & Tz & 1\end{bmatrix}$$
Os eixos do sistema de coordenadas são escritos horizontalmente. Então o problema agora quando se trata do mundo dos computadores, é como armazenar estes coeficientes na memória. Você também pode fazer:
Diz-lhe qual convenção você usa? Não. Você também pode escrever:
or:
Again, isso não lhe dá uma indicação particular de qual convenção “matemática” você usa. Você está apenas armazenando 16 coeficientes na memória de diferentes maneiras e isso é perfeitamente bom desde que você saiba qual é essa maneira, para que você possa acessá-los apropriadamente mais tarde. Agora tenha em mente que um vetor multiplicado por uma matriz deve dar-lhe o mesmo vetor, quer você use uma notação matemática de linha ou coluna. Assim o que é realmente importante é que multiplique as coordenadas (x,y,z) do seu vector pelos coeficientes certos da matriz, o que requer o conhecimento de como “você” decidiu armazenar o coeficiente de matriz na memória:
Escrevemos esta função para sublinhar o facto de que, independentemente da convenção utilizada, o resultado da multiplicação do vector * matriz é apenas uma multiplicação e uma adição entre as coordenadas de entrada do vector e as coordenadas de eixo do sistema de coordenadas AX, AY e AZ (independentemente da notação utilizada, e independentemente da forma como as armazena na memória). Se você usar:
Você precisa chamar:
Se você usar:
Você precisa chamar:
onde ml é a matriz da mão esquerda e mr a da mão direita: mt = ml * mr. No entanto note que nós não temos usado parênteses para os índices de acesso porque não queremos sugerir que estamos acessando elementos armazenados em um array 1D aqui. Estamos apenas a falar dos coeficientes das matrizes, tal como escritos em papel. Se você quiser escrever isto em C++, então tudo depende de como você armazenou seus coeficientes na memória como sugerido acima.