Saudações aos altivos.

Após algum tempo sem textos mais técnicos, trago-lhes o primeiro de dois posts baseado em uma reportagem da revista Game Developer publicada em setembro de 2000. O texto original é de autoria de Todd Meynink, que trabalhou na Angel Studios – a responsável pela produção da versão Nintendo 64 de Resident Evil 2. A parada foi bem tensa quando se considera que um jogo que que tinha 1,2GB no Playstation foi atochado (é esse mesmo o termo) em um cartucho de 64MB. Mais do que isso, o desafio maior foi como fazer as animações pré-renderizadas (full motion videos, se preferirem) rodarem no Nintendo 64, cuja arquitetura não foi feita para isso. Aviso de antemão entretanto, que como aquela série de textos que traduzi da EDGE, trata-se de um texto um tanto mais difícil de ler. Acompanhem.

Resident Evil 2 para Nintendo 64 foi o primeiro game de um console baseado em cartucho a ter full motion video. O time da Angel Studios converteu esse jogo de dois CDs, comprimindo 1,2GB em apenas um cartucho de 64MB. Uma porção significativa dos dados era 15 minutos de videos de sequências animadas. Conseguir esse nível de compressão, suportando o rigoroso requerimento de 30hz, entregando a melhor qualidade de video possível, era um desafio considerável. Olhando para esse desafio por outra perspectiva, coloquemos em números. Os quadros originalmente gerados das sequências de video eram de 320×160 pixels à 24 bits de cor, ou 153,600 bits por quadro. No Nintendo 64, os quinze minutos de videos à 30hz geravam um total de 15x60x30x153,600 = 4,147,200,000 bytes de dados não comprimidos. Mas o nosso espaço total no cartucho era de 25,165, 824 bytes, então eu tinha que conseguir uma compressão de 165:1. Pior ainda, eu tinha que dividir esse espaço módico do cartucho com o audio do video.

A versão Playstation rodava os videos rodava os videos com a ajuda de um chip proprietário MDEC, mas como o Nintendo 64 não dispunha de equipamento para descompressão, isso tornava o desafio ainda mais complexo. Para entender melhor a magnitude dos problemas, considere isso análogo a realizar descompressão em tela cheia de MPEG à 30 hz por software, em uma CPU mais ou menos equivalente a um Intel 486. Felizmente, o Nintendo 64 contava com um processador de sinal programável chamado RCP que rodava em paralelo com a CPU.

Uma rápida cartilha do JPEG

Para simplificar os problemas de tempo e sincronização, eu escolhi o estilo de compressão MPEG 1 (também conhecido por MPEG) apenas para o vídeo. Como uma introdução aos relativamente complexos problemas de aplicação da compressão MPEG, deixe-me apresentar um resumo rápido da compressão JPEG. Primeiro, a imagem é convertida de RGB para YCbCr. Esse processo converte a informação RGB em informação luminosa (Y) e cromaticidade (Cb e Cr).

Invertendo o quociente da matriz e aplicando ao YCbCr ocorre a transformação inversa. Esse sistema de cores explora as propriedades de nosso sistema visual. Já que o olho humano é mais sensível a mudanças de iluminação do que de cor, eu posso dedicar mais da banda para representar Y do que Cb e Cr. De fato eu posso dividir a imagem sem perda perceptível na qualidade na imagem apenas guardando a média não pesada de cada bloco de 2×2 pixels de informação cromática. Dessa forma a informação Cb e Cr é resuzida em 25% de seu tamanho original. Se cada um dos três componentes (Y, Cb e Cr) representou 1/3 da informação original de imagem, a versão sub-sampleada agora adiciona 1/3+1/12+1/12+ = metade do tamanho original.

Segundo, cada componente é quebrado em blocos de 8×8 pixels. Cada bloco de 8×8 pode ser representado por valores de 64 pontos denotados por esse conjunto:

Onde há x e y, há duas dimensões espaciais. Esse cosseno discreto de transformação (DTC) transforma esses valores em frequência dominantes como c=g(Fu,Fv), em que c é o coeficiente e Fu e Fv são as respectivas freuquências espaciais de cada direção:

O resultado dessa equação dá outro conjunto de 64 valores conhecidos como coeficientes DCT, que é o valor de uma frequência particular – não mais na amplitude do sinal na posição sampleada (x,y). O correspondente responsável pelo vetor (0,0) é o coeficiente DC(o coeficiente DCT pela qual a frequência das dimensões é zero) e o resto dos coeficientes AC (DCT coeficientes em que as frequências não são zero em uma ou duas dimensões). Como os valores de sample variam de ponto a ponto através de toda a imagem, o processamento DCT comprime os dados concentrando a maior parte do sinal nos menores valores do espaço (u,v). Para o típico bloco de 8×8 pixels, muitos -se não todos – dos (u,v) têm coeficientes zero ou próximo de zero e entretanto não precisam ser codificados. Esse fato é explorado ao longo da programação.

Próximo passo, os 64 valores de saída do DCT são quantificados em uma base por elementos com matriz de quantização de 8×8. A quantificação comprime ainda mais os dados representando os coeficientes DCT com precisão maior não maior do que a necessária para conseguir a qualidade de imagem necessária. Esse nível de precisão variável é o que você modifica quando você move o botão de compressão de JPEG do Photoshop ao salvar uma imagem. No terceiro passo (ignorando o detalhe que os componentes DC são codificados de maneiras diferentes) todos os coeficientes codificados são ordenados como uma sequência “zig-zag”. Já que a maior parte da informação de um típico bloco de 8×8 é armazenada na parte superior do canto esquerdo da tela, dessa forma a eficiência da codificação é maximizada. Então os dados de todos os blocos são codificados em um esquema Huffman ou algoritmica. A figura abaixo resume todo o processo:

(O blog reduz automaticamente o tamanho das imagens. Se abrí-as em separado, dá para ver em um tamanho um pouco maior)

Tanto o JPEG quanto o MPEG são formatos de compressão com perda de dados, significando que a imagem original nunca poderá ser exibida da mesma forma após ser comprimida. A informação é perdida na compressão JPEG em vários pontos: subsample cromático, quantização e imprecisão do ponto de flutuação durante o DCT.

Compressão de imagens em movimento

A compressão JPEG tenta reduzir a redundância espacial em uma única imagem estática. Em contraste com um único quadro, um video consiste em uma sequência de imagens(quadros) vindo em um ritmo constante (geralmente 30hz). Se você examinar os quadros consecutivos de um filme, você não encontrará muitas diferenças entre um quadro e outro. o MPEG explora essa redundância temporal através dos quadros, assim como a redundância espacial dentro de um quadro. Para lidar com a redundância temporal, o MPEG divide os quadros em grupos, cada um referido como “grupos de imagens” ou GOP (group of images). O tamanho do GOP tem efeito direto na qualidade das imagens comprimidas e na profundidade da compressão. O tamanho do GOP representa um dos problemas inerentes a esse processo. Se o GOP for muito pequeno, nem todas as redundâncias temporais serão eliminadas. Por outro lado, se for muito grande, imagens do começo e do final do GOP parecerão substancialmente diferentes em direção ao final (imaginem uma cena mudando no meio), o que adversamente afetará a qualidade das imagens reconstruídas.

Para melhorar a compressão, os quadros são geralmente representados em pedaços de quadros similares por referência. Os quadros dentro de um GOP por um dos três métodos mostrados na figura abaixo.

A figura mostra quadros diferentes e seus papéis e relacionamentos. Esse exemplo mostra um quadro intracodificados (I-frames). A sequência de intraquadros (I), quadros previstos (P) e figuras bidimensionais (B), ou IBBBPBBBI. Quando o tamanho do GOP é variado, apenas o número de quadros-B no outro lado do quadro-P muda. Note que essa sequência representa do playback, não necessariamente a ordem em que os quadros são armazenados. Guardando os quadros 1,2,3,4,5,6,7,8 como 1,5,2,3,4,9,6,7,8 pode fazer sentido desde que os quadros-i e p sejam lidos primeiro, facilitando a construção dos quadros-b assim que possível e reduzindo o número de quadros que precisam ser mantidos de forma a decodificar a sequência com sucesso.

Previsão e interpolação são empregados em uma técnica chamada “compensação de movimento” (motion compensation). Previsão assume que a figura corrente pode ser modelada como uma transformação da figura em um tempo prévio. Figuras interpoladas trabalham de forma similar em relação a referências passadas e futuras, combinadas com um termo de correção.

Não faz sentido usar uma imagem inteira para modelar movimento dentro de um quadro, então modelar movimento pode ser feito em blocos menores. MPEG usa macro-blocos de 16x16pixels(pense em um macro-bloco como quatro dos nossos blocos DCT de 8×8). Essa forma ilustra outra concessão entre qualidade da imagem e a quantidade de informação necessária para representar uma imagem. Uma estimativa por pixel do movimento pode aparecer melhor, mas pode ficar muito grande, enquanto um bloco com um quarto de imagem pode parecer bastante ordinário, mas ocupa pouco espaço. Em uma imagem codificada de forma bidirecional, cada macro-bloco de 16×16 pode ser intra, previsto para frente, para trás ou a média. Note que os blocos de 16×16 usados para compensação não precisam ficar sobre os limites dos 16×16 pixels.

O custo da função tipicamente avalia que macro-bloco(s) de qual imagem representa o bloco atual da imagem atual. Essa função de custo mede a diferença o bloco e o candidato precedente. Claramente é uma busca exaustiva, em que todos os possíveis vetores de movimento são considerados, o que daria o melhor resultado, mas custaria muito caro em termo de custo computacional. A figura abaixo mostra os tamanhos relativos dos diferentes tipos de quadro.

A implementação

Meu primeiro passo para implementar o full motion video para a versão Nintendo 64 de Resident Evil 2 foi desenvolver uma plataforma de compressão/descompressão baseada na dos PCs que pudesse ser facilmente “debugada” e ajustada. Isso me permitiu experimentar com diferentes tamanhos de GOP, taxas de transmissão de bits e outras variáveis. Se tornou rapidamente aparente que esse desafio de optimização seria uma guerra entre tamanho e qualidade de imagem e complexidade de decodificação. Sem contar as severas restrições de memória. Como vocês provavelmente sabem, sem o cartucho de expansão o Nintendo 64 tinha apenas 4MB de RAM. Essa memória era dividida entre código de programa, regiões da memória, frame buffer, Z-buffer, texturas e etc. Para um game grande é provável que haja espaço para apenas dois frame buffers em qualquer resolução razoável e profundidade de cor. Tenha em mente também que você precisa de espaço para carregar os quadros de referência necessários (quadros-i e qudros-p) para computar os quadros previstos. Esse requerimento era necessário para três quadros (I,P,I) de dados YCbCr à 24 bits de cor. Obviamente a resolução do video ditava o quanto de RAM isso requeria.

Eu testei muitos parâmetros de ajustes diferentes, cuja taxa de transmissão de bits era o mais importante. Uma taxa maior naturalmente leva a uma qualidade maior. Entretanto, simplesmente aumentar a txa de transmissão de bits a uma qualidade aceitável para exibição atraves da tela requeria muito espaço de armazenamento. No nosso caso, um rápido cálculo dava nosso alvo para o tamanho de compressão dos quadros: 25,165,824 bytes/ 27,000 quadros = 932 bytes por quadro.

Melhorar a resolução da imagem aumentava a qualidade até certo ponto, mas rapidamente caia após isso. A razão disso era o limitado número de bits disponíveis para descrever os pixels em um quadro. Enquanto um filme em alta resolução pode parecer bom quando há poucas mudanças em uma cena, movimentos ou mudanças rápidas em uma cena podem não ser adequadamente descritas na mesma taxa de transferência de bits. Esse mesmo artefato se torna extremamente visível quando os limites dos blocos de movimento são descontínuos, o que dá ao filme uma aparência quadriculada. Adicionalmente, aumentar a resolução significava mais macro-blocos, mais DCTs inversos, mais compensação de movimento, mais conversão de espaço das cores e mais tempo de decodificação. Rapidamente se tornou aparente para nós que exibir um filme à 30hz não seria possível.

Já que os filmes seria exibidos em uma resolução menor que a da origem, nós necessitávamos de um mecanismo para reescalonar os quadros decodificados de volta à resolução em tela cheia. Tentamos pixel doubling, mas o resultado foi insatisfatório mesmo em telas NTSC (que escondem muito da definição dos pixels aumentados). Depois eu tentei usar a rotina retcopy do Nintendo 64 (faz parte da biblioteca de software do N64) com interpolação bilinear. Dessa forma alcançamos um resultado melhor que ficou em uso até usarmos uma rotina de microcódigo customizada – o que por outro lado deixou a resolução de tela menor, mas o RCP do Nintendo 64 reescalonava automaticamente sem custo adicional de processamento. Resolução menor também reduziu os requerimentos de memória para os frame buffers.

Eu tentei decodificar os filmes tanto frame buffers de 16-bit RGB quanto de 32-bit RGBA. O de 32 deu resultados superiores, especialmente através das graduações de cor, embora na época o impacto na performance não justificasse os requerimentos extras de memória e processamento. O resultado da profundidade de cor tinha severas implicações. O principal era o aumento nos requerimentos de memória. Na época eu estava avaliando essa forma de atuação, se rodando na resolução e profundidade de cor originais não seriam possíveis devido as limitações de memória. A segunda implicação era o aumento do tempo de processamento para os quadros maiores, posteriormente atrasados pela performance abaixo da média da memória do Nintendo 64. Até esse ponto eu tinha filmes rodando em baixa resolução à 30hz e quase dentro dos requerimento de tamanhos, mas a qualidade da imagem deixava muito a desejar, e esse era um problema que precisava ser direcionado. Eu começei a pensar mais em optimização.

Reescrevendo o algorítmo em microcódigo

Meu algorítimo de descompressão foi escrito em C, e seu tempo computacional estava espalhado por boa parte do código. Eu não colheria os benefícios do código optimizado com o Assembly MIPS sem grande esforço e maior quantidade de tempo do que eu dispunha. Se por um lado eu nunca tinha lidado com o processador de sinal do Nintendo 64 (o RSP), sabia que sua manipulação de vetores e capacidade de rodar em paralelo eram as chaves para o aumento de performance que buscava. Após conseguir que uma simples função “adicione 2 para esse número” funcionasse, eu comecei a portar para o microcódigo porções do código baseado em C. Essa tarefa não foi nada simples. A única maneira para “debugar” o microcódigo era quebrar o RSP em vários lugares e ler o cache de dados para ver se tudo estava funcionando corretamente. Esse processo foi bastante trabalhoso.

O resultado direto das dificuldades de desenvolvimento do microcódigo foi que eu teria tempo apenas para escrever um número finito de rotinas. Reescrever o ponto fixo de um cosseno separado de transformação parecia a escolha óbvia. Vários dias duros de codificação e verificação dessa rotina, ela estava pronta para o uso principal. Infelizmente reescrever a rotina tornava sua performance mais lenta. Minha investigação revelou que o problema do cache estava causando esse problema de lentidão. Como cada bloco com dados de pixels é lido e preparado para decodificação, esses dados se tornam residentes no cache de dados do CPU. Para o RSP processar isso, os dados precisam ter passado pelo DMA da memória principal para o DMEM do RSP. Após processados, os dados precisam ser devolvidos do DMA para a memória principal. O cache do CPU não sabe que esse processo potencialmente não sincronizado modificou os dados, então essas linhas de cache precisam ser “invalidadas” e relidas para assegurar que o CPU está operando com dados mais recentes. O problema é que todo o impacto sobre a memória extra estava cobrindo os benefícios ganhos pela eficiência das instruções MIPS do RSP.

Minha próxima parada foi o código de compensação de movimento. Infelizmente a quantidade de código requerida para manejar os diferentes tipos de compensação de movimento era proibitivo. A falta da instrução “shift” do RSP tornava improvável uma implementação limpa. Claramente o código que finalmente trouxe a imagem descomprimida para a tela (sem intervenção posterior do CPU) tinha uma chance de ganhar a maior parte do benefício das instruções MIPS do RSP.

Reescrever as rotinas de conversão de cor-espaço (CSC) para aproveitar as vantagens da arquitetura de de vetores do RSP foi algo que deu certo. O RSP foi unicamente feito para esse tipo de tarefa. Assim que o RSP fez a conversão, os dados do DMA podiam ir para o DMEM diretamente para o frame buffer, evitando os problemas de cache anteriores. Isso trouxe o aumento visível de performance e providenciou a melhora correspondente da qualidade de imagem, mas ainda estava muito longe da qualidade do FMV original.

Epifania

Até esse ponto, minha implementação se aproximava do meu objetivo, mas alguns problemas permaneciam. Primeiro, a qualidade de imagem ainda não era tão boa quanto eu almejava. Segundo, os arquivos com dados requeridos para suportar essa qualidade inadequada já eram maiores que nosso limite. E finalmente, a decodificação ainda demorava muito, e eu não podia ver um modo fácil de melhorar isso – principalmente porque eu também estava tentando reduzir a taxa de bits. Então me ocorreu uma idéia: e se eu cortasse todos os frames adicionais e os interpolasse quando os videos fossem rodar? Eu sabia que se conseguisse seguir essa forma de trabalho eu conseguiria tanto dividir a taxa de bits quanto dobraro tempo da decodificação. Eu apostava na noção de que seria difícil diferenciar dados decodificados à 30hz de dados decodificados à 15hz com interpolação.

Inicialmente consederei usar triple buffering para decodificar dois quadros, então interpolar entre os dois para gerar o quadro intermediário. Mas restrições de memória rapidamente impediram essa forma de trabalho, ou qualquer variante desse método. Eventualmente eu achei a solução.

————————————————————————————————————————-

Até o próximo post.

André V.C Franco/AvcF – Loading Time.