update 2008 - 09 - 09 : une triangulation qui marche en actionscript 3

le problème de ce sujet c'est qu'il n'existe aucun script AS ce qui ne facilite pas tellement l'avancée des travaux :/ ça va prendre du temps. J'avais tenté une attaque frontale en passant par un script Processing disponible ici : http://yaxu.org/processing/voronoi/applet/. sexy hein ?! ben en fait non. ce script est tout sauf une tésselation: la couleur de chaque pixel est recalculée en rapport à sa disatnce au point . de tête : un canevas mesure 400 * 400 soit 160.000 pixels. pour CHAQUE point, ils va falloir recalculer la couleur de tous les pixels...
3 points > 480.000 setPixel
6 points > 960.000setPixel
25 points ? ( 4 millions )
1000 points ? non rien ,là tu peux directement rebooter l'ordinateur...
je veux bien que l'AS3 soit plus performant mais faut pas pousser ... faire comme ça, c'est se tirer une balle dans le pied.
ce script est donc un gadget même pas bon pour illustrer le propos.

donc j'ai commencé mes recherches.
Ce dont je parle c'est ça : http://www.cs.biu.ac.il/ ( lien trouvé ce matin et qui m'a encore mis une claque )
Avant ça, voila le lien dont je me servais pour essayer de comprendre : http://www.cs.cornell.edu

un article de Paul Bourke : http://local.wasp.uwa.edu.au/
un grand homme, je vous invite à visiter ses expériences, algos, trouvailles c'est très stimulant pour la tête et assez déprimant quand on voit le chemin qu'il reste à faire.

pseudo code pour la triangulation : http://fearyourself.developpez.com/

littérature théorique mais illustrée : http://www.cs.cmu.edu/
article très simple ( pesudo code ) +code en C + illustration claire de la marche à suivre ( celui qui m'a permis de comprendre ) : http://www.codeguru.com/
essai sur Voronoï et les shaders ( pour rêver un peu meme si c'est hyper kitsch ): http://blog.debreuil.com/ assez d'exemples.

le problème de tous ces trucs c'est qu'ils sont codés en Java ou pire en C ( la malepeste soit du C ) Quant ils sont codés car la plupart du temps c'est du pseudo code, des articles théoriques, des thèses de doctorat et autres trucs pas trop abordables pour moi.
Il y en a une dont j'aime bien le titre : "Centroidal Voronoi Tessellations Are Not Good Jigsaw Puzzles" traduisez : "les tésselations centroïdales de Voronoï font de très mauvais puzzles"
dispo ici : http://people.scs.fsu.edu/

Au fait qui est tu : voronoï ?
et toi Delaunay ? ( et sa triangulation )

pendant la premiere semaine de galère plusieurs fois j'ai cru voir la lumiere et puis rien : elle était là et pouf ! elle était plus là.
Ajoutez à ça que mon patron a décrété l'état d'urgence absolue au bureau et que maintenant il faut bosser ( salauds de patrons ) et qu'il est à peu près hermétique à géométrie. ça n'aide pas à avancer.

trois jours après le début de mes essais calamiteux j'ai remarqué que c'était quand même bel et bien de la géométrie tout ça. ce constat trivial m'a amené à reprendre les bases. he ben ça fait beaucoup de bien de reprendre un truc à zéro :)
j'ai donc commencé un package de classe géométriques simplifié.

En partant du Point ( il existe dans le package flash.geom.* ) le mien est un point Hyper basique avec 2 propriétés x, y et une méthode de dessin.

Après j'ai fait une classe Line très simple aussi : 2 points et quelques méthodes pratiques come :

  • longueur
  • angels en degrés et radians
  • le centre (renvoi un Point)
  • width / height
  • longueur unitaire uX/ uY
  • les normales gauches et droites
  • une méthode de dessin avec un paramètre couleur

Ensuite j'ai fait une classe Triangle et là ça a été comme de voir la mer pour la première fois... je n'avais jamais regardé un triangle je crois. basée sur 3 points stockés dans un tableau points, elle s'adjoint 3 Lines stockées dans un tableau edges, une méthode contains pour savoir si un point est dans le triangle ou pas(renvoie une booléenne), une méthode de dessin.

'elle est minus ta mer !' tu me diras
et 'tu parles pas comme ça de ma mer ok ?!' je te répondrai.

Parce qu'en fait la magie vient d'ailleurs, c'est qu'un triangle a plein de propriétés sympathiques que je ne voulais pas stocker dans le triangle pour ne pas l'alourdir inutilement par exemple il y a les droites suivantes:

  • les hauteurs : perpendiculaires au côté et passant pas le sommet opposé
  • les médiatrices : perpendiculaires au côté, elles le coupent en son centre
  • les médianes : elles coupent le côté en son centre et passent par le point opposé.
  • les bissectrices : qui divisent chaque angle du triangle en deux angles égaux.

et les points suivants :

  • orthocentre : le point d'intersection des hauteurs
  • le centre du cercle circonscrit : le point d'intersection des médiatrices. Le cercle circonscrit est le seul cercle qui passent par les trois points du triangle ! cette propriété est cruciale pour calculer une triangulation de Delaunay ( on commence à moins faire le malin là ...)
  • le centre de gravité : le point d'intersection des médianes.
  • le centre du cercle circonscrit : le point d'intersection des bissectrices . Le cerle inscrit est le seul cercle contenu entièrement par le triangle.

donc j'ai fait un classe pour chacun de ces petits bijous :

Plus une classe Utils avec les méthodes Statiques suivantes :

  • Intersection ( L1:Line, L2:Line ):Point
  • dotProduct( l1:Line, l2:Line ):Number
  • Projection( p:Point, L:Line ):Point
  • distToPoint( p1:Point , p2:Point):Number
  • angleToPoint( p1:Point , p2:Point):Number

histoire de se simplifier la vie sans alourdir les différents objets :)

plus une Classe Polygon balbutiante avec une méthode de triangulation extra bourrine. Aujourd'hui j'ai trouvé une classe de convex Hulling fort pratique dont je me suis empressé de convertir une des méthodes en AS3 (Melkman, la plus rapide, quasiment rien à faire à part typer les variables trier le tableau en entrée) : http://www.lostinactionscript.com/blog/

bref : une application de ce long texte

la source de cette prodigieuse animation

le truc certain c'est qu'on ne s'en sert jamais comme ça :)

le code de Test.as est tout procédural tout moche c'est plus pour l'exmple. En plus c'est au Mouse move donc ça marche pas super ... pas grave.


Bon voila pour l'état d'avancée, ça ouvre tellemnt de perspectives qu'une liste exhaustive serait impossible. à suivre donc...