O Teorema de Capullo

Quando eu era criança, tinham duas coisas que eu fazia bem: programar e desenhar. Em um certo ponto da vida eu decidi conscientemente deixar de lado o desenho pra focar na programação, mas não antes de tentar um emprego como desenhista :)

Isso foi quando eu tinha onze anos. Eu morava ao lado do estúdio do Ely Barbosa, que na década de 80 tinha vários personagens bizarros, incluindo um coelho que viajava numa escova de dentes voadora gigante. Na cara de pau eu fui lá e me ofereci pra desenhar os gibis deles. Incrivelmente, eles não falaram "se manda guri", mas fizeram de fato um teste pra ver se eu desenhava o suficiente. (Que eu acabei bombando. Tinha só onze anos poxa.)

Mas mesmo tendo optado pela programação, eu nunca deixei de lado esse lado artístico. Não por acaso, meus primeiros empregos foram todos com computação gráfica. E, embora há muito eu não desenhe, adoro comprar livros e revistas com técnicas de desenho, para o caso de algum dia dar vontade de desenhar de novo.

Uma das revistas que tenho aqui é a primeira edição da Wizard brasileira, onde publicaram na íntegra todo o curso de desenho do Greg Capullo (desenhista do Spawn), uma série muito boa chamada Curso de Impacto (no original Krash Course, tem digitalizado na web se você souber onde procurar). No capítulo sobre perspectiva, eu aprendi um truque muito bom com ele, que na falta de nome melhor eu chamo de Teorema de Capullo:

Se você tiver vários personagens de mesma altura em uma cena, mesmo que eles não estejam na mesma profundidade, sempre haverá uma parte do corpo deles que estará alinhada.

Sabendo usar a regra acima, fica super fácil desenhar cenas complexas com perspectiva correta. Pra ver experimentalmente como isso é verdade, eu fiz um programinha em pyOpenGL que desenha vários Ricbits em posições aleatórias, usando as regras acima:


Script em python que desenha a cena acima

Note como o teorema de Capullo é verdadeiro: apesar de estarem em distâncias diferentes, todos os Ricbits estão alinhados na altura da cintura. Naturalmente, a primeira coisa em que pensei quando vi o teorema foi: dá pra demonstrar? A resposta é: sim, dá, e é surpreendentemente simples!

Vamos assumir que o observador está a uma altura h do solo, e que o plano de projeção está na coordenada z=1 (sem perda de generalidade). Vamos projetar um ponto P qualquer nesse plano de projeção, cujas coordenadas são Px, Py, Pz, e a intersecção com o plano vai ser em Sx, Sy. O que nós queremos provar é que existe um Sy tal que, para qualquer Pz dado, sempre é possível escolher um Py, independente de Pz, que projeta nesse Sy. Virando a figura de lado ela fica assim:

(Thanks to Bani/Inkscape pelo diagrama)

Por semelhança de triângulos, nós tiramos que (Py-h)/Pz = Sy/1, logo Sy=(Py-h)/Pz. Agora é imediato, basta escolher Py=h que Sy sempre será zero, independente de Pz, QED.

A parte bacana de entender matematicamente o que acontece é que você pode extrapolar suas conclusões. Como a escolha de Py depende do h, isso significa que o ponto exato onde as figuras se encontram depende da altura do observador. Subindo o observador no script ficamos com uma figura como a abaixo, note como agora os Ricbits estão alinhados na altura do pescoço:


Um dia eu ainda volto a desenhar, mas enquanto isso programação e matemática são divertidas demais :)

PS: Minha resolução de ano novo é atualizar o blog pelo menos duas vezes por mês, então, se eu atrasar, me cobre!

Dez anos de MUST

É díficil achar alguém na faixa dos 30 anos que trabalhe com computadores e não conheça o MSX, um computador pessoal de 8 bits que fez um sucesso enorme por aqui. No seu auge, entre 85 e 91, estima-se que mais de 400 mil máquinas tenham sido vendidas no Brasil.

Mas embora esse período tenha sido o auge em número de usuários, não foi o ápice na parte técnica. Os mais avançados softwares brasileiros de MSX foram feitos no período de 1996 a 2004, e há dois motivos pra isso. O primeiro é que esse foi o início da internet comercial, então muitos dos manuais e datasheets que antes eram raros, passaram a ser difundidos livremente pelas listas de discussão. O segundo é que essa também foi a época em que começaram a se formar os primeiros engenheiros que cresceram com o MSX na infância, e toda essa criançada estava sedenta pra usar os novos conhecimentos na sua velha maquininha.

Eu mesmo fiz um monte de brincadeiras nessa época, talvez a mais conhecida tenha sido o meu emulador BrMSX. Mas agora, em 2008, um outro software que fiz completa dez anos, e nada mais apropriado que comemorar com um detalhado making of. Apresento a vocês o Music Station, ou como também era carinhosamente conhecido, o MUST:

Vamos voltar uma década no tempo: em 1998, a internet crescia, nasciam os primeiros grandes portais nacionais, e começava a surgir uma prática que hoje em dia é extremamente comum: o compartilhamento de músicas em mp3. Primeiro por FTP e IRC, depois pelo Napster e Audiogalaxy, em pouco tempo os arquivos mp3 estavam por toda a parte.

Naturalmente, quem ainda brincava com o MSX também queria entrar na onda. Mais de uma vez me perguntaram "Ricardo, você não pode fazer um programinha pra tocar mp3 no MSX?". Qualquer criatura com um mínimo de bom senso iria perguntar "pra quê?". Mas bom senso nunca foi o meu forte :)

Eu já sabia de antemão que mp3 no MSX não era viável, o coitado do Z80 não iria dar conta. Mas a essa altura eu já sabia evitar um erro muito comum em desenvolvedores, o de prestar atenção no que o usuário pede, ao invés de focar no usuário quer. Sure, eles estavam pedindo mp3, mas o que eles queriam mesmo era só tocar música no MSX. Se fosse um outro formato qualquer não faria diferença. Como eu tinha acabado de cursar Processamento Digital de Sinais na Poli (com o saudoso prof. Max Gerken), achei que poderia encarar a construção de uma solução customizada pro MSX.

Hora de calibrar os objetivos: eu decidi fazer um player que tivesse a melhor qualidade possível pro MSX, que rodasse em qualquer modelo de MSX, incluindo os nacionais, e que conseguisse espremer pelo menos um minuto de música em uma MegaRAM de 256kb, o modelo mais comum. O primeiro passo, portanto, é ver se o MSX dá conta de tocar um sample com qualidade aceitável.

O MSX usa como gerador de som o chip AY-3-8910 (popularmente PSG), que é basicamente um gerador de ondas quadradas. Pra tocar um Lá central, você especifica a freqüência de 440Hz, acerta o volume apropriado, e se diverte com o barulhinho que ele produz. Se você for um mago do chiptune, dá pra fazer músicas bem legais com o PSG, mas definitivamente ele não foi feito pra reprodução de áudio digital. Para conseguir isso, nós temos entender como o chip funciona por dentro.

Internamente, o gerador de ondas quadradas é só um contador digital, que alterna o estado de um flip-flop depois do término de meio período. O chip tem três geradores que você pode ligar ou desligar de maneira independente através de um mixer. Quem tem experiência com chips TTL sabe que sinais desligados usualmente não são interpretados como nível lógico zero, mas sim como nível lógico um.

Pro nosso ouvido tanto faz, um sinal constante é silêncio sempre, independente dele estar em zero volts ou em cinco volts, mas o segredo da coisa é que o controle de volume é uma etapa analógica feita depois do mixer. Por isso, se você desligar o gerador através do mixer, e mudar bem rapidamente o controle de volume, você pode improvisar qualquer forma de onda que quiser! Como o PSG tem 16 volumes possíveis, isso significa que o MSX pode emular um PCM de 4 bits, mesmo sem ter sido projetado pra isso.

Quando o sinal está em nível lógico um, basta variar o volume!

Agora basta ligar esse PCM num timer de alta resolução e pronto. Quer dizer, exceto pelo fato do MSX não ter um timer de alta resolução. O melhor que ele tem é um timer que dispara no início do retraço vertical, a 60Hz, que é uma freqüência baixa demais pra gente. Nesse caso, o jeito é apelar pra gambiarra criatividade :)

Como o Z80 do MSX não tem cache, nem prefetching, nem nenhuma dessas firulas de processadores modernos, os opcodes sempre levam o mesmo tempo pra rodar. Assim, você pode criar um pseudo-timer simplesmente contando quantos ciclos de clock seu programa leva pra executar. Se nós precisássemos de uma rotina que lesse um byte da memória, mandasse pro PSG, e levasse exatamente 50 clocks pra rodar, uma possibilidade seria:

LD A,(HL) ; 8 clocks

LD A,(HL) ; 8 clocks

INC HL ; 7 clocks

OUT (0A1h),A ; 12 clocks

NOP ; 5 clocks

NOP ; 5 clocks

NOP ; 5 clocks

Pra fazer um timer assim, além de programar em assembly, você ainda precisa resolver um subset sum dos opcodes, o que é extremamente divertido (eu assumo que se você está lendo até aqui, deve achar essas coisas divertidas também :). Note como é importante fazer o padding correto, além de colocar 3 NOPs, eu também repliquei o carregemento da memória, só pra fazer a conta bater certinho nos 50 clocks.

Agora que temos um jeito de reproduzir o som, precisamos escolher a sampling rate. Pra conseguir o objetivo de 1 minuto em 256kb, o áudio certamente terá que ser comprimido. Então a sampling rate precisa ser baixa o suficiente pra poder suportar a descompressão em real time entre cada amostra, e alta o suficiente pra não perder muita qualidade de som. Eu escolhi 11kHz; como o clock do MSX é 3.57MHz, isso dá um total de 324 clocks por amostra. Não é muito, mas alguma compressão dá pra fazer.

Vamos calcular a compressão agora. Pra colocar 60 segundos a 11kHz em 256kb, nós precisamos de, no máximo, 256k*8/60/11k = 3.1 bits por amostra. Nosso sinal original tem 4 bits por amostra, então realmente a compressão é necessária. O Z80 não tem fôlego pra implementar transformadas, então não podemos usar nada de DCT, e nem mesmo Haar.

O jeito é modelar alguma coisa bem simples mesmo, tipo um código de tamanho variável como o código de Huffman. Esse tipo de código funciona tanto melhor quanto menos uniforme for o seu histograma. Pegando uma música típica como teste, chegamos em uma entropia de 2.6 bits; mas, por outro lado, a primeira diferença tem entropia ainda menor, apenas 2 bits!

Vamos codificar a diferença então. Com apenas 324 clocks não dá pra implementar todo o Huffman, mas tem uma maneira de simplificar, que é usando compressão com perdas. Como 99.3% das diferenças estão na faixa de -3 a 3, eu posso saturar nesses valores pra deixar o código mais simples. O código que utilizei foi o abaixo:

3 1111

2 1110

1 01

0 00

-1 10

-2 1101

-3 1100

No final a implementação desse código ficou menor do que eu esperava, apenas 169 clocks. Isso significava que eu tinha 198 clocks sobrando, com a cpu parada. Eu poderia ter aprimorado o codec com uma compressão mais eficiente, mas pensei que seria mais divertido, ao invés disso, usar esses clocks sobrando pra adicionar animações. Nesses clocks sobrando eu acabei colocando um osciloscópio com a forma de onda tocada, um banner animado na parte inferior, e no cantinho ainda sobrou cpu pra colocar um pingüim dançando!

Nesse ponto tudo que faltava era uma tela de abertura. Como no final o programa acabou ficando uma experiência multimídia, eu resolvi que ele seria uma homenagem à série Disc Station da Compile, que primava por seus excelentes demos. Eu chamei então o meu programinha de Music Station, e como os Disc Station originais sempre começavam com uma menina bonitinha, eu pedi ao meu irmão que desenhasse uma pingüinha no mesmo estilo. O desenho original que ele fez foi o abaixo:

Adaptar desenhos no MSX é tão complicado quanto adaptar código, a resolução é de apenas 256x192 e ainda tem o problema do color clash (cada bloco de 8x1 pixels pode ter no máximo duas cores). O pingüim tomando sol no canto da imagem teve que sumir, eu não tinha resolução pra isso. Já na pingüinha, eu tive que usar traços bem grossos no contorno, pra minimizar o clash, mas mesmo assim ainda sobraram algumas partes borradas. A solução foi usar sprites pra cobrir esse borramento.

Consegue achar as diferenças?

Por fim, bastou criar um logo, inspirado no logo original do Disc Station, e o MUST estava finalmente pronto! Pra quem quiser brincar com ele, abaixo tem uma versão em .dsk que pode ser carregada em emuladores, como o blueMSX ou o openMSX, e também o código fonte original.

Imagem de disco para rodar em emuladores
Código fonte original do Music Station, em assembly Z80

Na época, a comunidade MSX adorou o MUST. Como eu esperava, o pessoal começou a compartilhar músicas convertidas, do mesmo jeito que o povo do PC compartilhava mp3; e como eu publiquei a engine do MUST em GPL, um monte de gente reaproveitou o código, sendo que a engine foi usada até em joguinhos. Eu até animei a fazer uma versão com vídeo também, mas isso já é outra história, pra outra ocasião :)

Parabéns pelos dez anos, Music Station!

Agradecimentos à Ila, ao Acidx e ao Sturaro por ajudar na arqueologia digital :)

O Desentortador

Eu confesso que fiquei apreensivo quando soube que teria que passar vários meses na Califórnia. Afinal, Mountain View não é nenhuma San Francisco, eu tinha medo de morrer de tédio enquanto estivesse lá. Mas, felizmente, meu medo esvaiu-se quando eu descobri O Sebo!

O Sebo é um lugar lindo e maravilhoso onde você pode comprar The Diamond Age por apenas 50 cents, e inúmeros outros livros por preços tão baixos quanto esse. Na foto acima, você pode ver uma pequena porção do paraíso, mostrando apenas a parte de sci-fi, e apenas os autores das letras D até L. Sim, O Sebo é um lugar gigante e com diversão garantida pra várias semanas.

Depois de encher a mochila com livros, eu tive vontade de tirar uma foto deles pra mandar pros amigos. Foi então que eu tive um problema. Eu estava tentando tirar a foto à noite, e se eu colocasse a câmera exatamente sobre o livro, o flash estourava, e tudo que saía na foto era um grande borrão branco. Sem flash também não funcionava, ficava escuro demais pra câmera conseguir estabilizar a imagem.

Eu resolvi esse problema inclinando a câmera em relação ao plano do livro. Isso certamente resolve o problema do flash, mas em compensação o livro fica torto na foto. Uma solução simples seria simplesmente esperar amanhecer e tirar a foto do livro com a luz do dia. Mas é claro que optei por uma alternativa mais bizarra :) Resolvi escrever um software que desentortasse a foto do livro automaticamente!

Pra isso, vamos começar com a foto original do livro torto:


Pra começar o desentortamento, a primeira coisa que precisamos descobrir é onde estão as bordas do livro, que vão definir como vai ser a rotação que iremos fazer. Achar as bordas é fácil, basta identificar a fronteira entre livro e não-livro. Para isso, eu usei um algoritmo simples de crescimento de região:


Não ficou a coisa mais perfeita do mundo: está cheio de ruído em volta, e o algoritmo ainda vazou pra dentro do livro (a mesa era marrom, da mesma cor do urso na capa, e ele se perdeu com isso).

A boa notícia é que nenhuma dessas coisas importa! O que eu quero achar são as bordas, que tem uma direção preferencial bem determinada. Se eu utilizar a transformada de Hough, tanto o ruído quanto o vazamento devem sumir, e de fato é o que acontece. Essa é a transformada da imagem acima:


A transformada de Hough leva retas em pontos, então as quatro retas que formam a borda do livro viram quatro pontos bem brilhantes na transformada. É simples agora usar um threshold pra identificar esses pontos, e aplicar a transformada inversa pra achar as retas na imagem original:

Nessa imagem eu tracei linhas vermelhas nas retas identificadas pela transformada. Estamos quase lá, mas um problema da transformada de Hough é que ela acha retas, e não segmentos de retas. O que me interessa na verdade são os vértices do livro, então eu preciso achar as intersecções entre essas retas.

O detalhe é que quatro retas em posição geral determinam seis pontos, e não quatro. No caso da imagem acima, por exemplo, as retas verticais se encontram no ponto de fuga, bem acima do livro. A solução que eu usei foi adotar uma gambiarra heurística de considerar apenas os quatro pontos mais próximos do centro da imagem original. Além disso, também é legal converter os pontos pra coordenadas polares em relação ao centro da imagem, assim podemos ordená-los pelo ângulo.

Tendo os quatro vértices, agora é só aplicar uma transformação afim na imagem que a leve pra um retângulo e o trabalho está terminado né? Quem dera hehe. Se você fizer isso, a imagem fica com uma deformação não-linear: achatada na parte de cima, e esticada na parte de baixo.


Na década de 90, todo guri metido a programador fazia sua própria engine 3D pra imitar o Doom e o Quake; quem passou por essa época reconhece na hora a origem da deformação. O que está acontecendo é um problema de inverse perspective-correct texture mapping. A perspectiva introduz um fator do tipo 1/z na sua textura, e você precisa compensar isso quando for mapear na imagem. Vamos fazer a correção de perspectiva então:


Yatta! Finalmente temos a imagem final, desentortada como queríamos :) Na verdade, nós desentortamos a imagem em um único eixo, dá pra ver claramente que além do pitch essa imagem também precisava de correção no roll, mas isso fica como exercício pro leitor.

Eu implementei todos os passos descritos acima em python, usando a biblioteca PIL. Ele roda rapidinho, uns 3s por imagem apenas. O source é o abaixo:

Source do desentortador em python

Se alguém quiser reaproveitar o código pra fazer alguma coisa útil com ele (hehe), sinta-se à vontade. Salvo indicação em contrário, todos os programas desse blog são disponibilizados sob a Licença Crowley (Do what you want shall be the whole of the License).

PS: Ah sim, como vocês repararam, a partir de agora o blog vai ter desenhos também! Eu gostaria de dizer que se funcionou pro Chrome, deve funcionar pra mim também; mas a verdade é que a Aleph já fazia a mesma coisa lá na década de 80 :)

MapReduce is running

Quando eu era estagiário na década de 90, um dos meus primeiros projetos envolvia computação paralela. O projeto Visible Human tinha acabado de fatiar os primeiros espécimes, e nosso grupo estava doidinho pra fazer ray-tracing do volume de dados. Mas o volume de dados era grande demais pros padrões da época, e única saída foi importar uma Meiko com dez processadores, pra dar conta do trabalho.

(Meiko, aliás, que tem uma história curiosa. Apesar de ter dez processadores, só conseguíamos rodar processos em nove deles, tinha um que não funcionava de jeito nenhum. Depois de muitas ligações pro suporte, resolvemos desmontar a máquina pra ver se tinha alguma coisa errada no hardware, e, surpresa, entre o pente de memória e o conector na motherboard tinha um mosquito preso. Sim, aquela cpu tinha um bug :)

Mas programar diretamente a comunicação entre os processadores, com PVM ou MPI, é trabalho demais. A nossa solução foi escrever uma camada intermediária que abstraía a parte de comunicação e fazia o paralelismo de modo implícito. Nossa biblioteca era customizada pra visualização volumétrica paralela, mas hoje em dia a mesma abordagem é feita de maneira mais genérica, por pacotes como o Hadoop e o MapReduce, sendo que esse último eu uso bastante hoje em dia.

Mas, mesmo paralelizando o processamento, o melhor que uma abordagem dessas consegue é um ganho linear no número de processadores. Se o tamanho do seu volume de dados precisa daqueles prefixos que vêm depois do giga, então até o MapReduce pode demorar um pouco pra rodar. Nesse fim de semana eu encontrei o Randall Munroe, e pedi pra ele ilustrar como é um MapReduce na prática :)


Eu também aproveitei pra filmar o Randall enquanto ele desenhava esse sketch. Como o estilo dele é, hum, minimalista, isso o torna o único cartunista que eu conheço que consegue ser mais rápido que o Aragonés:

Eu podia estar roubando

É isso. Eu podia estar roubando, eu podia estar matando, mas estou aqui escrevendo no blog. Reclamações sobre a periodicidade do blog devem ser enviadas diretamente à Rockstar :)

Ao falar de GTA, sempre tem quem o associe ao terrorismo islâmico. Mas pra mim, o que incomoda mais é a associação imediata do islã com o terrorismo, em oposição à sociedade ocidental civilizada. Na verdade, já houve um período onde acontecia o oposto, enquanto a ciência florescia na cultura islâmica, os cristãos saqueavam e destruíam em nome da fé (mas na época chamavam isso de cruzadas, ao invés de terrorismo).

Foi nessa época em que viveu Al-Khwarizm (cujo nome deu origem às palavras algarismo e algoritmo), nessa época em que Bhaskara escreveu Lilavati e resolveu a equação de segundo grau, e também nesse período é que surgiram as primeiras demonstrações por indução finita. Mas a influência mais direta que a matemática islâmica teve em mim foi, sem dúvida, através das obras do Júlio César de Mello e Souza, que escrevia com o pseudônimo de Malba Tahan.

Malba Tahan se inspirava na cultura islâmica pra escrever seus livros de divulgação científica, sendo que o mais famoso deles é o Homem Que Calculava. Num post anterior eu tinha dito que o cálculo do Pi com método de monte carlo tinha sido o segundo puzzle que levei mais tempo pra resolver; pois o primeiro puzzle foi justamente tirado de um dos capítulos do livro: como escrever qualquer número usando apenas quatro quatros. No livro, Malba Tahan mostra as soluções até o 10, que são mais ou menos assim:

0 = 44 - 44
1 = 44 / 44
2 = 4/4 + 4/4
3 = (4 + 4 + 4) / 4
...

Eu tinha só dez anos quando li pela primeira vez, e consegui estender a seqüência até o 20. O posfácio do livro dizia que era possível escrever até o 100, mas eu levei mais de uma década até ver a solução completa!

Depois dos 20 primeiros, eu só consegui fazer algum progresso significativo quando estava no colégio técnico. Eu notei que o problema ficava mais simples se eu reduzisse o número de quatros, montando primeiro todas as soluções com um quatro, depois todas com dois quatros, e assim por diante. Eu não sabia na época, mas o que eu estava fazendo era um forward chaining manual. Mesmo assim, eu só consegui fazer os números pares até 100, minha solução tinha um monte de buracos nos ímpares.

Quando eu estava na faculdade, com os skillz mais afiados, eu larguei mão de fazer manualmente e escrevi um script pra fazer o serviço automaticamente. Eu coloquei no script não só as quatro operações básicas, mas também todas as outras que estão no Concrete Mathematics: raiz quadrada, função piso e função teto, binomiais, potências, fatorial, fatorial crescente e decrescente. A única regra é não usar nenhuma notação que envolva letras (como sin, cos e log; se você permitir log, o problema perde a graça).

Meu script conseguiu finalmente resolver todos os números até 100, e até encontrou múltiplas soluções pra eles! Atribuindo um peso a cada operação, eu mandei ele imprimir somente a soluçao mais simples (por exemplo, adição tem peso baixo, piso e teto tem peso alto). A tabela com as respostas está abaixo, junto com o programa que escrevi na época:

Solução gerada pelo script
Script original, escrito em C

O script pode resolver também os 5 cincos, os 6 seis, e qualquer outra combinação, desde que você esteja disposto a esperar o suficiente. O código original é bem ruinzinho, mas na verdade eu me orgulho de achar que meu código escrito há dez anos é ruim, significa que eu aprendi alguma coisa desde então :)