Morphing : kesako ?
Par Supernova
Mes bien chers frères, mes bien chères soeurs... Nous allons
parler dans cet article du MORPHING ! (hm... on va essayer... du
moins du pseudo-morphing).
___
/\/\ ¦
/ \ORPHEZ ¦RANQUILLES...
****************************
Bon, alors comme chacun le sait, le terme "morphing" veut dire
transformation, ou plutôt mutation... Dans la nature, par exemple,
le morphing s'applique aux papillons qui passent du misérable ver
au somptueux papillon.
Bon, alors ici, il n'est nullement question de rivaliser avec
la nature, car notre but va être de "morpher" de simples figures
géométrique en fil de fer. Mais ne soyez pas déçu... Si vous vous
attendiez à ce qu'on étudie les routines de MORPH ou de APEX et
bin on serait pas sorti de l'auberge !
Cet article est à la portée de tous car nous allons appliquer
nos explications sur du GFA basic... Bon, alors je vais essayer
d'organiser à peu prés l'article et de pas trop faire de fautes
d'orthographes car je suis très habitué au minitel (Rtel)... C'est
parti.
OBJECTIF :
---------
Comme je l'ai dit plus haut, il sera question de "morphe" de
simples figures géométriques. Qui dit figures géométriques dit
droites reliées entres elles. Cela réduit déjà considérablement
les difficultés. Imaginons cette figure :
___________
/1 /2
5/ /
\ /
4\_______/3
Elle est constituée de 5 points. On remarque également que les
liens sont : 1+2,2+3,3+4,4+5,5+1, c'est à dire que la figure est
fermée.
Nous allons aussi nous intéresser aux figures non-fermées et
brisée du genre :
2_______1 5
/ /\
3/_______4 7/__\6
Quoi de neuf ? Cette fois, on a deux figures : un triangle et
un polygone ouvert... Nous obtenons donc la suite :
1+2,2+3,3+4,5+6,6+7,7+5 pour décrire nos 2 objets. Cette suite
sera stockée dans un tableau que nous appellerons "LIENS". LIENS
aura donc une structure sur une dimension et décrira les couples
de points relies entres eux.
Reste à déterminer les coordonnées des points eux-mêmes à
présent. Pour cela, nous utiliserons deux autres tableaux nommés
XDEPART et YDEPART à une dimension chacun.
On a donc un tableau contenant les coordonnées X des points,
un autre contenant les coordonnées Y et un autre indiquant quels
points sont reliés entres eux. On peut ainsi, à partir de 4 points
faire une figure très compliquée. Le seul impératif est de savoir
quand on désire s'arrêter de faire des liens. Il nous faut donc
une variable qui l'indique (nbliens).
On peut déjà dire que XDEPART et YDEPART posséderont un nombre
d'éléments égal aux nombres de points totaux. Nbpts désigne ce
nombre. Ici nbpts = 7
Pour clarifier ces choses, illustrons le contenu des tableaux
grâce à l'exemple du triangle et du polygone ouvert du dessus.
tableau : LIENS
élément : 1 2 3 4 5 6 7 8 9 10 11 12
_________________________________________________
contenu ¦ 1 ¦ 2 ¦ 2 ¦ 3 ¦ 3 ¦ 4 ¦ 5 ¦ 6 ¦ 6 ¦ 7 ¦ 7 ¦ 5 ¦
-------------------------------------------------
tableau : XDEPART
élément : 1 2 3 4 5 6 7
_____________________________
contenu ¦120¦100¦90 ¦110¦150¦170¦130¦
-----------------------------
tableau : YDEPART
élément : 1 2 3 4 5 6 7
_____________________________
contenu ¦ 60¦ 60¦ 90¦ 90¦ 60¦ 90¦ 90¦
-----------------------------
On a vu comment décrire nos objets précisément. Jusque là, on
a pas parlé de morphing... c'est la qu'intervient le...
MORPHISATEUR
------------
Bon, revenons à nos deux figures, on veut les transformer en
une ou deux autres figures... je dis UNE ou DEUX autres, mais pas
plus. Si c'est UNE alors des points seront forcement superposés.
On ne peut pas plus de deux car si au départ, on en avait deux, et
bien, on ne peut pas rajouter des points en cours pour arriver à
former une troisième ou quatrième figure finale. Vous me suivez ??
On décide d'obtenir deux autres figures à l'arrivée. Celles-ci
seront donc constituées d'un nombre de points égal à ceux des
figures de départ. Normal...
DEPART
2_______1 5
/ /\
3/_______4 7/__\6
ARRIVEE
4 2 7____5
\ /\ ¦ /
\ / \1 ¦ /
\/ ¦/
3 6
Quelques constatations s'imposent...
* Les liaisons n'ont pas changée.
* Le nombre de points n'a pas change (explication plus
haut...)
* on peut tracer une droite pour passer d'un point
source à un point arrivée.
Cette dernière constatation est la clé de notre algorithme. En
effet, il suffit de déterminer toutes les droites reliant les
points sources aux points arrivée un à un, puis de stocker les
coordonnées transitoires constituant ces droites dans un buffer.
Ce qui nous amènent à créer de nouveau tableaux. A l'image des
tableaux DEPART*, il nous faut forcement deux tableaux que nous
appellerons ARRIVEX et ARRIVEY, lesquels contiendront bien sûr les
coordonnées des points d'arrivée correspondant systématiquement
aux points départ.
Je ne vais pas refaire le schéma des tableaux... vous avez
compris. Il va falloir désormais tracer virtuellement ces fameuses
droites et stocker les transitions dans deux tableaux que nous
appellerons BUFFERX et BUFFERY. A noter que ces BUFFER auront deux
dimensions : une pour savoir de quel point il s'agit, et l'autre
pour stocker les coordonnées.
Comment trace t-on des droites ? Facile...il suffit d'utiliser
les formules du coeff. directeur et calculer ainsi A et B...
y=Ax+B, y décrira donc la droite entre deux points.
On fera évoluer x de XDEPART à XARRIVEE sans oublier de le
stocker à chaque itération dans BUFFERX, et on stockera chaque y
correspondant dans BUFFERY. (ouf !) Nous répèterons ceci autant de
fois qu'il y a de points. Le nombre de transitions composant les
droites dépendra du pas avec lequel on fera avancer x. Plus ce pas
sera grand, plus le déplacement aura lieu rapidement, moins précis
il sera et moins de place on prendra (reprendre cette phrase à
l'envers marche tout aussi bien...)
Remarque : Il faudra bien entendu faire attention au sens du
parcours de la droite. J'explique :
A x A
x
x B
x
B A désigne le point départ
B désigne le point arrivée
On remarque ici que A peut être placé avant ou après B dans le
repère. Il faudra donc prévoir les deux tracés de droite, de façon
à ce que le morphing se fasse dans le bon sens et que certains des
points ne morphent pas de leur point d'arrivée vers leur point de
départ... Bon, on arrive maintenant à...
L'ALGORITHME
------------
On suppose que les points de départ et d'arrivée sont déjà
stocke dans les tableaux par des routines que je vous laisse le
soin de mettre au point. Rassurez vous, le listing GFA est complet
et intègre ceci mais je ne vais pas me faire chier à expliquer ces
parties... ça ne rentre pas dans le cadre de l'article.
PROCEDURE DROITE(XA,YA,XB,YB)
SI XB>XA ALORS
CALCULER A
CALCULER B
X=XA
T=1
TANT QUE XB>=X
Y=AX+B
BUFFERX(PT,T)=X
BUFFERY(PT,T)=Y
X=X+PRECISION
INCREMENTER T
FINTANTQUE
SINON
PERMUTER XA,XB
PERMUTER YA,YB
CALCULER A
CACLULER B
X=XB
T=1
TANT QUE X>XA
Y=AX+B
BUFFERX(PT,T)=X
BUFFERY(PT,T)=Y
FINTANTQUE
FINSI
NBTRANSITION=T
FINPROCEDURE
PROCEDURE MORPH
POUR PT DE 1 A NBPTS
XA=DEPARTX(PT)
YA=DEPARTY(PT)
XB=ARRIVEEX(PT)
YB=ARRIVEEY(PT)
DROITE(XA,YA,XB,YB)
FINPOUR
FINPRCEDURE
PROCEDURE PLAY
POUR T DE 1 A NBTRANSITION
POUR PT DE 1 A NBPTS
LIGNE BUFFERX(LIENS(PT),T)
BUFFERY(LIENS(PT),T)
BUFFERX(LIENS(PT+1),T)
BUFFERY(LIENS(PT+1),T)
FINPOUR
EFFACER ECRAN
FINPOUR
NBPTS=7
PRECISION=1
MORPH
PLAY
AMELIORATIONS
-------------
Je vous rappelle que vous pouvez vous reporter au listing GFA
complet pour voir vraiment la gueule du programme. L'algo n'est
carrément pas optimisé et les routines annexes non plus. Je vous
laisse le soin de le faire.
Sinon avec l'algo ci dessus on remarque que durant le morphing
certains points ont la fâcheuse tendance d'arriver à destination
avant d'autres, si bien que la déformation est mal synchronisée.
Schéma :
tableau: XDEPART YDEPART XARRIVEE YARRIVEE
élément 1: 10 15 16 18
2: 22 56 36 63
Le morphing avec un pas de 2 donnerait :
tableau: BUFFERX(1,n) BUFFERY(1,n) BUFFERX(2,n) BUFFERY(2,n)
n= 1: 10 15 22 56
2: 12 15 24 58
3: 14 16 26 58
4: 16 17 28 59
5: 16 18 30 59
6: 16 18 32 60
7: 16 18 34 61
8: 16 18 36 63
Ceci est dû au fait que l'écart entre ces points (donc la
droite) est très court... Pour palier à cela, il faudrait imposer
à tous les points un nombre de transitions égal au nombre le plus
grand. De telles sorte que notre situation précédente donnerait :
tableau: BUFFERX(1,n) BUFFERY(1,n) BUFFERX(2,n) BUFFERY(2,n)
n= 1: 10 15 22 56
2: 10 15 24 58
3: 12 15 26 58
4: 12 15 28 59
5: 14 16 30 59
6: 14 16 32 60
7: 16 18 34 61
8: 16 18 36 63
Par conséquent, dans les tableaux BUFFER certaines coordonnées
apparaîtront plusieurs fois successivement. (cf buffer(1,n)). Le
tout est de trouver le coefficient de duplication... C'est ce que
va faire notre routine OPTIMISE. Regardez le listing. Je ne vous
explique pas en détail l'algo comme précédemment. Le schéma du
dessus et l'explication précédente du problème devrait suffire
pour comprendre la routine du listing ou de faire votre propre
solution.
EXPLOITATION :
-------------
En principe, vous trouverez dans le dossier morphing la source
complète GFA v3.5E en .LST et .GFA et les sources de replay ASM.
Je vous laisse le soin de le décortiquer, il n'y a rien de dur,
juste le fait d'arriver à comprendre le code des sous routines,
faites sur le tas... (j'ai pas fait d'algo...beurk !).
Voici un rapide résume du fonctionnement :
- Vous disposez de procédures à mettre ou 'REMiser' dans le
source.
- Certaines se chargent de sauver les objets, de les charger,
de sauver les calculs.
- L'une d'elle, OPTIMISE, est celle décrite plus haut. Essayer
d'effectuer un morphing avec puis sans pour voir la différence.
- Les routines pour tracer les objets fonctionnent comme suit :
Placer un point de départ avec le bouton gauche.
Sans lâcher le bouton, étirez la droite puis lâcher.
A partir de la, vous êtes en K-LINE, les droites se tracent du
dernier point au point actuel. Appuyez sur le bouton gauche pour
fixer les segments.
Pour obtenir une nouvelle origine, appuyez sur le bouton droit.
Un beep sonore retentit. Et c'est repartit.
Une fois l'objet trace, appuyer sur Esc. Vous arrivez alors dans
la phase durant laquelle vous déformez les points en les
étirant à la souris pour tracer la figure d'arrivée. Appuyer
sur Esc une fois fini. Les calculs se lancent.
- La procédure STORE permet de sauver les calculs pour une
utilisation en ASM ou autre langage. Son format est décrit
plus loin.
- Vous pouvez changer le nombre de points maximum, le nombre de
transitions maximum en modifiant les variables de la procédure
INIT. Les valeurs actuelles sont prévues pour 1 méga.
- Le carre qui apparaît à l'écran est utile au cas ou vous
rejoueriez le morphing avec le prog. ASM. En effet, la routine
ASM n'efface que la partie contenue dans le carré lors de
l'animation, si bien que si des points sont en dehors, ils
resteront apparent.
LA ROUTINE ASM.
---------------
Celle-ci vous permet de rejouer une animation "morphée"
qui est précalculée. Tout est commenté dans la source. Il est
indispensable d'avoir utilisé la procédure STORE pour disposer au
moins d'un fichier .XY et .DAT.
Vous pouvez ainsi créer une animation rapide de figure morphée
si vous avez calculé plusieurs objets. Le tout est de reprendre
à chaque fois le dernier objet grâce à CHARGER_OBJET, puis de le
déformer, de resauver l'objet ainsi obtenu etc...
Structure des fichiers :
*.XY: octets impaires: X
octets paires: Y
*.DAT:
octet 1: nombre de liens/2
octet 2: (distance maximum entre deux points
(nombre de points constituant la droite
les reliant)
+1)*4 ----> ceci pour l'ASM
cet octet va nous permettre de déterminer
l'offset entre les coordonnées des points
dans la table.
octet 3: liens(1)
octet 4: liens(2)
octet 5: liens(3)
etc...
Bon, je vous conseille vivement d'aller jeter un petit coup
d'oeil à la routine ASM. Elle est commentée.
BYE BYE...
----------
Bon, j'espère que vous aurez de quoi vous amuser avec tout ça.
Normalement, j'ai mis quelques exemples de fichier... Vous voyez
qu'il n'a rien de bien difficile et qu'on peut quand même arriver
à un résultat assez spectaculaire. Comme améliorations j'entrevois
de faire une interface utilisateur potable et de travailler avec
des courbes de bezier... (très intéressant ça...). Si quelqu'un
connaît les formules, je suis très intéresse. Vouala, si quelqu'un
s'est penche sur des algo de morphing bitmap, ça me botte aussi.
C'est carrément différent et dix fois plus intéressant.
Bon allez salut et laissez moi vos ptits mots sur le 3615 RTEL
bal SUPERNOVA (ou le 3614 pour ceux qui ont accès).
[ Retour au sommaire ]