Comment introduire la table des marching cubes dans une 4kb.


[INTRO]

  Si vous aimez cette forme de challenge un peu particulière qu'est l'intro
4kb, vous avez peut-être déjà eu envie d'y intégrer des métaballs...
Et là, vous aves vu que les deux tables utilisées à cet effet prennent
512+4096 octets ! Même en utilisant un compresseur sur le .COM final, ca
reste désagréablement gros, et ca ne laisse que peu de place pour le reste.

Voici une solution que j'ai trouvée alors que j'essayais désespérément de
m'endormir. Cela vous dirait de réduire cette grosse table de 4096 octets
à environ 16.5% de sa taille actuelle ? Je ne tiens pas compte, dans ce calcul,
du code nécessaire à recomposer la table d'origine.

Allons-y ! Si ces 15% sont en plus compressés par le com-packer, c'est tout
bon.



[Réduction n°1]

  Regardez un peu cette table. Attentivement. Une chose saute aux yeux.
Tous ces "-1", là... N'y aurait-il pas un moyen de les virer de là ? Ils 
prennent une place folle. Tiens, combien, exactement ? Allez-y, comptez. :-)
(1, 2, 3, 4, 5, 6, 7, ...) 
Arrêtez, c'est bon, je l'ai fait pour vous. Enfin, mon éditeur, plus 
exactement. Il y en a 1636. Oui, mille six cents trente-six ! C'est énorme !
Comment les virer... hum... pourquoi ne pas donner comme première valeur de
chaque ligne de cette table le nombre de cases réellement utiles ?
C'est parti !
On retire 1636 valeurs, mais on en ajoute 256, ce qui nous donne : 2716.

Et voilà la table réduite à 66% de sa taille.
Continuons.


[Réduction n°2]

  Prêts pour la suite ? Alors dites-moi quelle est la plus grande valeur
que l'on trouve dans cette table. Héhé... oui, c'est 11. Mais attention, 
n'oubliez pas ce nombre qu'on a calculé à l'étape 1 et qui doit bien être
stocké quelque part aussi. Quelle est sa valeur maximum, à celui-là ?
Ah ! c'est 15. Et 15, ca vous dit quelque chose ? Oui, c'est 14+1, mais 
encore ? 16-1 ? On se rapproche. Oui, toi, là, vas-y... Oui, c'est ça !
C'est la plus grande valeur que l'on puisse coder sur 4 bits. 
Mais c'est merveilleux, ca, dites-moi. Pourquoi ? Parce que toutes ces
valeurs tiennent sur 4 bits, et qu'on peut donc en stocker DEUX par octet.
On reprend la calculette et on remarque que 2716 divisé par deux nous donne
1358. 

On en est donc à 33% de la taille. Mais ce n'est pas tout !


[Réduction n°3]

Réfléchissons un peu ensemble. 
Si seul le point 1 de notre cube est en dehors de l'iso-surface et les sept
autres à l'intérieur, ne doit-on pas dessiner le même triangle que s'il était
seul à l'intérieur ?
BINGO !
Je ne m'amuse pas à le démontrer, c'est assez intuitif. En tout cas, ça marche
et c'est le principal. Mais comment faire comprendre ça à notre table ?
Pour ça, revenons un poil en arrière. On calcul l'indice dans la table en 
fonction des valeurs des 8 sommets de notre cube. Prenons l'exemple où seul le
point 3 est à l'intérieur de l'iso-surface. On regarde dans la table et on y
trouve la ligne :

{3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

Ouais, et alors ?
Et alors ? Eh bien, regardons la ligne où le point 3 est le seul à l'extérieur.

{3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

Vous ne voyez pas une similitude ?
Eh oui. C'est _presque_ pareil. La différence vient du fait que l'ordre des
sommets est utilisé pour calculer la normale. Et pour inverser l'ordre des
sommets d'un triangle, il suffit d'en inverser deux, ici, les deux derniers.
Mais comment savoir quelle ligne correspond ?
Si le 3 est à l'intérieur, notre indice vaut 8 (2^3).
Et s'il est à l'extérieur ? Il vaut 1+2+4+16+32+64+128. 
Ce qui est simplement 8 xor 255. 

Alors, on calcule ?
On avait 1358 octets, qu'on divise par 2, ce qui nous donne 679 octets.

Et ca nous fait bien les 16.5% annoncés.



Si vous avez d'autres réductions, n'hésitez pas à m'en faire part !

Happy 4kb !


Allergy/Idle 
mail: allergy@alrj.org
url:  http://www.alrj.org