2.9.4 Bounding Move bounding Box
Dado um Bounds3f que é transformado por uma transformação animada, é útil ser capaz de calcular uma caixa de delimitação que engloba todo o seu movimento durante o período de tempo da animação. Por exemplo, se pudermos limitar o movimento de um primitivo geométrico animado, então podemos intersectar raios com esse limite para determinar se o raio pode intersectar o objeto antes de incorrer no custo de interpolar o primitivo ligado ao tempo do raio para verificar essa intersecção. O método AnimatedTransform::MotionBounds() executa esse cálculo, pegando uma caixa de delimitação e retornando a caixa de delimitação de seu movimento sobre o intervalo de tempo do AnimatedTransform.
AnimatedTransform 103
AnimatedTransform:: Interpolate() 106
AnimatedTransform::: MotionBounds() 108
>
AnimatedTransform::R 103
>
AnimatedTransform::S 103
Float 1062
Matrix4x4 1081
Point3f 68
Quaternion 99
Quaternion::ToTransform() 101
Ray 73
Ray::tempo 73
RayDifferential 75
Slerp() 103
Transformação 83
Translate() 87
Vector3f 60
Existem dois casos fáceis: primeiro, se as matrizes do quadro-chave forem iguais, então podemos aplicar arbitrariamente apenas a transformação inicial para calcular os limites completos. Segundo, se a transformação incluir apenas a escala e/ou tradução, então a caixa de delimitação que engloba as posições transformadas da caixa de delimitação, tanto na hora de início como na hora de fim, delimita todos os seus movimentos. Para ver porque isto é assim, considere a posição de um ponto transformado p como uma função do tempo; denotaremos esta função de duas matrizes, um ponto e um tempo por a(M0, M1, p, t).
Desde que neste caso a componente de rotação da decomposição é a identidade, então com a nossa decomposição matricial temos
onde a tradução e a escala são ambas escritas como funções do tempo. Assumindo por simplicidade que S(t) é uma escala regular, podemos encontrar expressões para os componentes de a(M0, M1, p, t). Por exemplo, para o componente x, nós temos:
where s0,0 é o elemento correspondente da matriz de escala para M0, s0,0′ é o mesmo elemento da matriz de escala para M1, e os elementos da matriz de translação são identificados de forma semelhante por d. (Escolhemos aqui d para “delta” já que t já é reivindicado para o tempo.) Como função linear de t, os extremos desta função estão no início e no fim do tempo. As outras coordenadas e o caso para uma escala generalizada seguem de forma semelhante.
〈AnimatedTransform Método Definitions〉 + ≡
Bounds3f AnimatedTransform::MotionBounds(const Bounds3f &b) const {
if (!actuallyAnimated)
return (*startTransform)(b);
if (hasRotation == false)
return Union((*startTransform)(b), (*endTransform)(b));
〈Return motion bounds accounting for animated rotation 108〉
}
Para o caso geral com rotações animadas, a função de movimento pode ter extrema em pontos no meio do intervalo de tempo. Não conhecemos uma forma simples de encontrar estes pontos. Muitos renderizadores abordam este problema por amostragem um grande número de vezes no intervalo de tempo, calculando a transformação interpolada em cada um deles, e tomando a união de todas as caixas de delimitação transformadas correspondentes. Aqui, vamos desenvolver um método mais bem fundamentado que nos permite computar de forma robusta estes limites de movimento.
Usamos um limite conservador ligeiramente mais simples que implica computar o movimento dos oito cantos da caixa de delimitação individualmente e encontrar a união desses limites.
>
〈Return limites de movimento contabilizando os limites de movimento animados rotation〉 ≡ 108
Limites3f limites;
for (int corner = 0; corner <8; ++corner)
limites = Union(bounds, BoundPointMotion(b.Corner(corner(corner)));
return bounds;
Para cada canto da caixa de delimitação p, precisamos encontrar os extremos de um sobre o intervalo de tempo da animação. Lembre-se do cálculo que os extremos de uma função contínua sobre algum domínio estão nos pontos limite do domínio ou em pontos onde a primeira derivada da função é zero. Assim, o limite total é dado pela união das posições no início e no fim do movimento, bem como a posição em qualquer extrema.
AnimatedTransform::: actuallyAnimated 103
AnimatedTransform:: BoundPointMotion() 110
AnimatedTransform::: hasRotation 103
Bounds3::Corner() 78
Bounds3::Union() 78
Bounds3f 76
Figure 2.18 mostra um gráfico de uma coordenada da função de movimento e sua derivada para uma interessante trajetória de movimento de um ponto. Note que o valor máximo da função ao longo do intervalo de tempo é alcançado num ponto onde a derivada tem um zero.
Figure 2.18. (a) Movimento da coordenada x de um ponto p em função do tempo, conforme determinado por duas matrizes de quadros-chave. (b) A derivada da função do movimento, Equação (2.12). Note que os extremos da função de movimento no intervalo de tempo dado correspondem a zeros da derivada.
Para limitar o movimento de um único ponto, iniciamos nossa derivação seguindo a abordagem usada para o caso de não-rotação, expandindo os três componentes T, R e S da Equação (2.9) como funções do tempo e encontrando seu produto. Temos:
O resultado é bastante complexo quando expandido, principalmente devido ao slerp e a conversão do quaternion resultante em uma matriz; um sistema de álgebra de computador é um requisito para trabalhar com esta função.
A derivada ∂a(M0, M1, p, t)/∂t também é bastante complexa – em sua glória algébrica completa, mais de 2.000 operações são necessárias para avaliar seu valor para um dado par de matrizes decompostas, ponto e tempo. Entretanto, dadas as matrizes de transformação específicas e um ponto específico, a é substancialmente simplificado; denotaremos a função especializada de t sozinho como aM, p(t). A avaliação de sua derivada requer aproximadamente 10 operações de ponto flutuante, um seno, e um coseno para avaliar para cada coordenada:
onde θ é o arco cosseno do produto ponto dos dois quaterniões e onde os cinco coeficientes ci são 3 vetores que dependem das duas matrizes e da posição p. Esta especialização funciona bem, já que precisaremos avaliar a função em muitos valores de tempo para um dado ponto.
Agora temos duas tarefas: primeiro, dado um par de matrizes de quadros-chave e um ponto p, precisamos primeiro ser capazes de calcular eficientemente os valores dos coeficientes ci. Então, dada a função relativamente simples definida por ci e θ, precisamos encontrar os zeros da Equação (2.12), que podem representar os momentos em que o movimento extrema ocorre.
Para a primeira tarefa, vamos primeiro fatorar as contribuições para os coeficientes que dependem das matrizes do quadro de chaves daqueles que dependem do ponto p, sob a suposição de que as caixas de delimitação para o movimento de múltiplos pontos serão computadas para cada par de matrizes do quadro de chaves (como é o caso aqui). O resultado é felizmente bastante simples – os vetores ci são funções lineares dos componentes x, y e z do ponto.
Assim, dados os coeficientes ki e um determinado ponto p do qual queremos limitar o movimento, podemos calcular eficientemente os coeficientes ci da função derivada na Equação (2.12). A estrutura DerivativeTerm encapsula estes coeficientes e este cálculo.
〈AnimatedTransform Private Data〉 + ≡
structure DerivativeTerm {
DerivativeTerm(Float c, Float x, Float y, Float z)
: kc(c), kx(x), ky(y), kz(z) { }
Float kc, kx, ky, kz;
Float Eval(const Point3f &p) const {
return kc + kx * p.x + ky * p.y + kz * p.z;
}
};
Os atributos c1 – c5 armazenam informação derivada correspondente aos cinco termos da Equação (2.12). Os três elementos da equação correspondem às três dimensões do espaço.
〈AnimatedTransform Private Data〉 + ≡
DerivativeTerm c1, c2, c3, c4, c5;
O fragmento 〈Compute termos da derivada do movimento function〉 no construtor AnimatedTransform, não incluído aqui, inicializa estes termos, via código gerado automaticamente. Dado que requer alguns milhares de operações de ponto flutuante, fazer este trabalho uma vez e amortizar sobre os múltiplos cantos da caixa de delimitação é útil. Os coeficientes ki são mais facilmente calculados se assumirmos um intervalo de tempo canônico; mais tarde, teremos de refazer os valores t de zeros da função de movimento para o intervalo de tempo real do obturador.
Dados os coeficientes ki baseados nas matrizes do quadro-chave, BoundPointMotion() calcula um limite robusto do movimento de p.
〈AnimatedTransform Método Definitions〉 + ≡
Bounds3f AnimatedTransform::BoundsPointMotion(const Point3f &p) const {
Bounds3f bounds((*startTransform)(p), (*endTransform)(p));
Float cosTheta = Dot(R, R);
Float theta = std::acos(Clamp(cosTheta, -1, 1));
for (int c = 0; c <3; ++c) {
〈Find quaisquer zeros derivados de movimento para o componente c 111〉
〈Expand caixa de delimitação para quaisquer zeros derivados de movimento encontrados 111〉
}
limites de retorno;
}
Bounds3f 76
DerivativeTerm 110
Float 1062
Point3f 68
A função IntervalFindZeros(), a ser introduzida brevemente, encontra numericamente zeros de Equação (2.12). Até quatro são possíveis.
〈Find quaisquer zeros derivados do movimento para o componente c〉 ≡ 110
Zeros flutuantes;
int nZeros = 0;
IntervalFindZeros(c1.Eval(p), c2.Eval(p), c3.Eval(p), c4.Eval(p),
c5.Eval(p), theta,
Intervalo(0., 1.), zeros, &nZeros);
Os zeros são encontrados sobre t ∈ , então precisamos interpolar dentro do intervalo de tempo antes de chamar o método para transformar o ponto no tempo correspondente. Note também que o extremo está apenas em uma das dimensões x, y e z, e assim os limites só precisam ser atualizados nessa dimensão. Por conveniência, aqui usamos apenas a função União(), que considera todas as dimensões, mesmo que duas possam ser ignoradas.
〈Expand caixa de delimitação para qualquer zeros derivados de movimento found〉 ≡ 110
for (int i = 0; i <nZeros; ++i) {
Point3f pz = (*this)(Lerp(zeros, startTime, endTime), p);
bounds = Union(bounds, pz);
}
Finding zeros of the motion derivative function, Equation (2.12), não pode ser feita algebricamente; métodos numéricos são necessários. Felizmente, a função é bem comportada – é bastante suave e tem um número limitado de zeros. (Relembre o gráfico da Figura 2.18, que era um representante invulgarmente complexo.)
Embora pudéssemos usar uma busca baseada em bissecções ou o método de Newton, correríamos o risco de perder os zeros quando a função apenas atravessa brevemente o eixo. Portanto, usaremos a aritmética de intervalos, uma extensão da aritmética que dá uma visão sobre o comportamento de funções em intervalos de valores, o que torna possível encontrar robustamente zeros de funções.
Para entender a idéia básica da aritmética de intervalos, considere, por exemplo, a função f (x) = 2x. Se tivermos um intervalo de valores ∈ ℝ, então podemos ver que ao longo do intervalo, o intervalo de f é o intervalo . Em outras palavras f () ⊂ .
Mais geralmente, todas as operações básicas da aritmética têm extensões de intervalos que descrevem como elas operam em intervalos. Por exemplo, dados dois intervalos e ,
Em outras palavras, se adicionarmos juntos dois valores onde um está no intervalo e o segundo está em , então o resultado deve estar no intervalo .
A aritmética de intervalos tem a propriedade importante de que os intervalos que ela dá são conservadores. Em particular, se f () ⊂ e se c > 0, então sabemos com certeza que nenhum valor em f faz com que f seja negativo. A seguir, mostraremos como calcular a Equação (2.12) em intervalos e tiraremos vantagem dos limites conservadores dos intervalos computados para encontrar eficientemente pequenos intervalos com cruzamentos de zero onde métodos regulares de encontrar raízes podem ser usados com confiabilidade.
Primeiro vamos definir uma classe Intervalo que representa intervalos de números reais.
Bounds3::União() 78
Float 1062
Interval 112
IntervalFindZeros() 113
Lerp() 1079
Ponto3f 68
〈Interval Definitions〉 ≡
intervalo de classe {
público:
〈Interval Métodos públicos 112〉
Float low, high;
};
Um intervalo pode ser inicializado com um único valor, representando um único ponto na linha do número real, ou com dois valores que especificam um intervalo com largura diferente de zero.
〈Interval Public Methods〉 ≡ 112
Intervalo(Float v) : low(v), high(v) { }
Intervalo(Float v0, Float v1)
: low(std::min(v0, v1)), high(std::max(v0, v1)) { }
>A classe também fornece sobrecargas para as operações aritméticas básicas. Note que para subtração, o valor alto do segundo intervalo é subtraído do valor baixo do primeiro.3
〈Interval Public Methods〉 + ≡ 112
Intervalo operador + (const Intervalo &i) const {
return Intervalo(baixo + i.low, high + i.high);
}
Intervalo operador-(const Intervalo &i) const {
return Intervalo(baixo – i.high, high – i.low);
}
Para multiplicação, quais lados de cada intervalo determinam os valores mínimos e máximos do intervalo de resultado dependem dos sinais dos respectivos valores. Multiplicar as várias possibilidades e tomar o mínimo e o máximo geral é mais fácil do que trabalhar através de quais usar e multiplicar estes.
〈Interval Public Methods〉 + ≡ 112
Intervalo operador*(const Intervalo &i) const {
return Intervalo(std::min(std::min(low * i.low, high * i.low),
std::min(low * i.high, high * i.high),
std::max(std::max(max(low * i.low, high * i.low),
std::max(low * i.high, high * i.high));
}
Também implementamos as funções Sin() e Cos() para Intervalos. As implementações assumem que o intervalo dado está em , que é o caso para o nosso uso destas funções. Aqui incluímos apenas a implementação de Sin(); Cos() é bastante similar na estrutura básica.
Float 1062
Intervalo 112
Intervalo::high 112
Intervalo::baixo 112
〈Interval Definitions〉 + ≡
Intervalo em linha Sin(const Intervalo constante &i) {
Float sinLow = std::sin(i.low), sinHigh = std::sin(i.high);
if (sinLow> sinHigh)
std::swap(sinLow, sinHigh);
if (i.low <Pi / 2 && i.high> Pi / 2)
sinHigh = 1.;
if (i.low <(3.f / 2.f) * Pi && i.high> (3.f / 2.f) * Pi)
sinLow = -1.;
intervalo de retorno(sinLow, sinHigh);
}
Dada a maquinaria do intervalo, podemos agora implementar a função IntervalFindZeros(), que encontra os valores t de qualquer cruzamento zero da Equação (2.12) sobre o intervalo dado tInterval.
〈Interval Definitions〉 + ≡
void IntervalFindZeros(Float c1, Float c2, Float c3, Float c4,
Float c5, Float theta, Interval t Intervalo, Float *zeros,
int *zeroCount, int depth = 8) {
〈Evaluate derivada do movimento em forma de intervalo, retornar se não houver zeros 113〉
if (profundidade> 0) {
〈Split tIntervalo e verifique ambos os intervalos resultantes 114〉
} else {
〈Use Método de Newton para refinar zero 114〉
}
}
A função começa por calcular o intervalo de intervalo sobre o Intervalo t. Se o intervalo não for igual a zero, então não há zeros da função sobre o Intervalo t e a função pode retornar.
〈Evaluate derivada de movimento em forma de intervalo, return if no zeros〉 ≡ 113
Intervalo = Intervalo(c1) +
(Intervalo(c2) + Intervalo(c3) * tIntervalo) *
Cos(Intervalo(2 * theta) * tIntervalo) +
(Intervalo(c4) + Intervalo(c5) * tIntervalo) *
Sin(Intervalo(2 * theta) * tIntervalo);
if (Intervalo.low> 0. ∥ range.high <0. ∥ range.low == range.high)
return;
Se o intervalo do intervalo for zero, então pode haver um ou mais zeros no intervalo tInterval, mas também é possível que não haja nenhum, uma vez que os limites do intervalo são conservadores, mas não tão apertados quanto possível. A função divide o Intervalo t em duas partes e verifica recursivamente os dois sub-intervalos. A redução do tamanho do domínio do intervalo geralmente reduz a extensão do intervalo, o que pode nos permitir determinar que não há zeros em um ou ambos os novos intervalos.
Float 1062
Interval 112
Interval::high 112
Interval::baixo 112
Pi 1063
〈Split tInterval e verifique ambos os resultados intervals〉 ≡ 113
Float mid = (tInterval.low + tInterval.high) * 0.5f;
IntervalFindZeros(c1, c2, c3, c4, c5, theta,
Intervalo(tInterval.baixo, médio), zeros, zeroCount, profundidade – 1);
IntervalFindZeros(c1, c2, c3, c4, c5, theta,
Intervalo(médio, tInterval.high), zeros, zeroCount, depth – 1);
Após termos um intervalo estreito onde o valor do intervalo da função derivada do movimento se estende a zero, a implementação muda para algumas iterações do método de Newton para encontrar o zero, começando no ponto médio do intervalo. O método de Newton requer a derivada da função; como estamos encontrando zeros da função derivada do movimento, esta é a segunda derivada da Equação (2.11):
〈Use Método de Newton para refinar zero〉 ≡ 113
Float tNewton = (tInterval.low + tInterval.high) * 0.5f;
for (int i = 0; i <4; ++i) {
Flutuador fNewton = c1 +
(c2 + c3 * tNewton) * std::cos(2.f * theta * tNewton) +
(c4 + c5 * tNewton) * std::sin(2.f * theta * tNewton);
Float fPrimeNewton =
(c3 + 2 * (c4 + c5 * tNewton) * theta) *
std::cos(2.f * tNewton * theta) +
(c5 – 2 * (c2 + c3 * tNewton) * theta) *
std::sin(2.f * tNewton * theta);
if (fNewton == 0 ∥ fPrimeNewton == 0)
break;
tNewton = tNewton – fNewton / fPrimeNewton;