Commentaires

1 Le 8 octobre 2003, 09:16 par Timothee Groleau

Cool! Vraiment sympa ta demo. Je n'avais pas realise que Casteljau avait cree son algorithme pour une proportion quelconque. Moi je m'etais concentre sur les milieus (ratio 1/2). Je vais voir si j'ai le temps d'etendre ma, erm soit-disante "preuve"

Merci pour le lien sur mon article. Petite correction cependant, mon papier ne traite pas de transformer une quadratique en cubique mais plutot de transformer une cubique en une serie de courbes quadratiques (c'est l'inverse) pour pouvoir utiliser les API de dessin. Au passage, le papier est un peu vieux alors le code est pas forcement le plus beau du monde :p.

Je ne suis pas sur qu'il soit interessant d'essayer de deriver le raisonnement pour un nombre de point arbitraire. C'est certainement faisable mais j'ai peur que les calculs engendres soit super lourds pour une utilisation tres limites. Le probleme des courbes de beziers c'est que modifier un seul point de control modifie toute la courbe et ca devient donc instable pour avoir la courbe desiree a un haut degree. C'est pour ca d'ailleurs que la plupart des logiciels n'utilisent que des series de courbes beziers cubique plutot qu'une bezier de degree 10, 15 ou plus haut (et en plus comme c'est polynomial, plus le degree est haut et plus ca rame pour faire les calculs). Mon easing function generator utilise une bezier de degree 5 et deja c'est chiant pour avoir une courbe precise.

En tout si tu t'y lances, jette aussi un coup d'oeil au code de Robert Penner: recursion d'approximation cubique vers quadratique. Au vu de ta demo je suis persuade que tu peux faire une approximation degree N sur quadratique. La recursion risque "juste" d'etre un peu lourde.

Bon courage.

2 Le 8 octobre 2003, 09:49 par LAlex

Oups, je vais rectifier cette inversion des termes tout de suite

En fait, je me lance la dedans surtout pour le sport plutôt que dans le but de l'appliquer dans un développement ... Les courbes cubiques (euh ... 4 points c'est bien cubique hein ?) paraissent largement suffisantes pour du code "de tous les jours" ...

Je viens justement de voir que les courbes de Bezier peuvent être utilisées pour les easing, et évidemment j'ai tout de suite pensé à ton easing function generator ... Pour l'instant, je me suis plus penché sur l'aspect géométrique que sur le coté mathématique, mais je vais m'y mettre !

L'aspect mathématique justement permet-il de calculer les coordonnées d'un point de la courbe sans utiliser casteljau ? Parce que si je veux utiliser l'approximation de PENNER, et que je dois utiliser en plus la recursivité de casteljau, je suis pas arrivé ... :?

Je me demande si la meilleure approximation n'est pas celle des tangentes, car elle ne dépend pas du nombre de points de contrôles, mais bien du nombre de point arbitratire que l'on choisit ... je vais essayer de mettre ca en pratique ... :roll:

Merci en tout cas de tes précisions !

3 Le 8 octobre 2003, 11:50 par Timothee Groleau

> euh ... 4 points c'est bien cubique hein ?

:). Oui, cubique ca veut dire que le polynome est de degree 3 et qu'il y a donc 3+1 points de control.

> L'aspect mathématique justement permet-il de
> calculer les coordonnées d'un point de la courbe
> sans utiliser casteljau ?

Oui, une courbe de bezier est une fonction basee sur formule polynomiale de math toute bete. La fonction B(u) est definie pour u appartenant a [0, 1]. A u=0, tu est sur P0, a u=1, tu est sur PN (PN etant le dernier point de control), a u=1/2, tu es a la moitie de la courbe. Donc en utilisat la formule tu peux avoir n'importe quel point de la courbe en changeant u dans l'appel a la fonction.

> Parce que si je veux utiliser l'approximation de
> PENNER, et que je dois utiliser en plus la recursivité
> de casteljau, je suis pas arrivé ...

Pourtant c'est probablement la meilleure approche. Penner utilise deja CastelJau et ce serait sans doute facile de modifier son algo pour une courbe de degree N (ou au moins d'un degree donne). Ce qu'il est important de voir c'est que le but de l'algo de Casteljau n'est pas de determiner un point de la courbe (pour ca on a deja la formule de base). Il sert surtout a determiner de nouveaux points de controls pour couper la courbe en deux sous-courbes de bezier de meme degree que la premiere avec chaque sous-courbes, plus "simple" (en terme de forme) que la premiere. En faisant ca, du coup tu peux utiliser exactement la meme approche que Penner, meme si tu as une courbe de degree N: cherche la distance entre le milieu de la courbe de degree N et le milieu de la courbe quadratique dont les points de controls sont: P0, PN et l'intersection des droites (P0, P1) et (PN, PN-1). Si les milieus sont suffisement proches, arrete toi la et dessine avec la method curveTo, sinon, utilise l'algo Casteljau pour couper la courbe en deux et recommence tout pour chaque sous-courbe recursivement.

De cubique a quadratique, ca converge relativement rapidement, si le degre est haut, je ne sais pas du tout si ca irait vite ou pas mais ca m'interesse de savoir si tu essaies

>Je me demande si la meilleure approximation n'est
>pas celle des tangentes

Je ne crois pas. Je devrais changer ma conclusion dans mon papier pour rajouter un ou deux mots a ce propos. La methode des tangentes n'est pas stable du tout et TRES gourmandes en ressources (surtout si tu joue avec une courbe a haut degre). Ma recommendation pour un systeme de degree N fixe, c'est de trouver une methode approximative "suffisemment bonne" qui sert tout le temps. Deuxieme option, utiliser la methode recursive de Penner. Je ne toucherai pas aux tangentes. Je l'ai laisse dans mon article parce que je voulais montrer les chemins que j'avais explores mais clairement, je n'utilise pas la methode des tangentes quand j'ai besoin de courbes de beziers.

4 Le 10 octobre 2003, 16:39 par Kib

Je viens de lire (très rapidement) ton article Timothee, c'est dommage que tu ne l'aies pas écrit en français

Je n'ai pas bien compris pourquoi vous cherchez à approximer des courbes de Bézier cubiques avec des courbes quadratiques ? Pourquoi ne pas directement écrire une fonction qui tracerait des courbes de Bézier cubiques ? Est ce vraiment gourmand en ressource ? Pourquoi ne pas écrire des tables de coefficients binomiaux, ceci éviterait les calculs des factorielles à la rigueur ? non ?

5 Le 10 octobre 2003, 16:44 par LAlex

Tracer une courbe de bézier point par point serait trop consommateur de ressources ... et pas vectoriel en plus. :?

Sachant que l'on peut zoomer sur une anim flash, comment définir quel pas utiliser pour le tracage ? Il faudrait qu'il soit minuscule, et donc avec un nombre de calculs astonomique ... :roll:

De plus, les API de dessins de Flash sont natives, donc forcément plus performantes ...

Sinon, pour les "coefficients binomiaux", je sais pas ce que c'est (pas plus que je sais où se situe l'utilisations des vectorielles dans une courbe de Bézier) ... comme je le disais, je n'ai eu pour l'instant qu'une aproche géométrique !

6 Le 10 octobre 2003, 17:08 par Kib

Dans l'article de Timothée, il y a une formule mathématique de la courbe de Bézier,

ce que j'apelle un coefficient binomial, c'est :
(n!) / ((k!)(n-k)!)
Rapelle toi ! Le binôme de Newton, le triangle de Pascal
Selon Timothée, c'était cette partie du calcul qui consommait plein de ressources, mais à mon avis les u^k et (1-u)^k aussi, arf !

Euh ... les "vectorielles", je ne sais pas trop ce que c'est non plus ... je n'en ai pas vu la trace dans l'article de Timothée ...

Est ce que le temps d'approximer la courbe + la tracer prend moins de temps que de tracer la courbe cubique, si on considère que l'utilisateur n'ira pas zoomer ?

Sinon je trouve que tu fais des trucs très chouettes et intéressants en Flash (pathfinder, moteur 3d ect ...) !

7 Le 12 octobre 2003, 00:58 par Alcys

Pour ceux qui sont intéressé par les courbes de Bézier et les B-splines ,un livre super bien fait en français,(avec de multiples schémas), est paru il y a quelques années:
Modèles de BEZIER,des B-splines et des Nurbs
Demangel et Pouget (éditeur:Ellipses)

8 Le 12 octobre 2003, 15:17 par Timothee Groleau

@Lalex, je pense que Kyb, ne pense pas a du point par point mais plutot a du segment par segment ;). Ca reste "vectoriel" au sens de Flash (tu peux zoomer et ca reste continue) mais zoomer a fond peut montrer des angles.

@kib, comme l'a dit Lalex, le but d'approximer
une cubique avec des quadratiques c'est pour pouvoir utiliser les API de dessins, etant natives en MX, on ne peut sans doute pas les battre en vitesse avec ActionScript. Plus, Le flash player va effectivement faire en sorte que la courbe reste continue et sans angle si tu zoomes.

> [coefficient binomial]... Selon Timothée, c'était cette partie du
> calcul qui consommait plein de ressources

Je ne me rappelle pas avoir dit dans mon papier que les coefficients binomiaux etaient la partie lourde, est-ce que tu peux preciser a quoi tu fais reference? Si on reste sur une courbe cubique, les coefficients sont precalcules; et meme pour un systeme dynamique on peut calculer les coefficient pour un degre donne et les reutiliser pour chaque point. Pour moi la partie lourde c'est effectivement les puissances du temps, comme tu le dis.

> Est ce que le temps d'approximer la courbe + la tracer prend moins
> de temps que de tracer la courbe cubique, si on considère que
> l'utilisateur n'ira pas zoomer ?

Sans avoir teste, je pense que oui. Sans meme parler de zoomer, le pas a utiliser pour tracer une courbe depend de la courbe elle-meme donc il faut deja avoit un petit systeme de detection. Normallement le Flash player a deja ca integre. En plus, supposons qu'on utilise 100 pas, calculer 100 points sur la courbe de bezier cubique revient a 2x100 calculs polynomiaux de degre 3 (_x et _y) pour chaque cubique. C'est le type de calculs bien lourd qui est le plus efficace si implemente nativement.

Aussi en terme de memoire, une fois que tu as fait tes calculs et tracer les quadratiques, le player Flash ne va garder en memoire que les donnees necessaires pour decrire les 4 courbes quadratiques (si tu utilises midpoint). Je crois que Flash est capable de sauver des courbes en enchaine, ca voudrait dire 7 points en memoire) mais meme s'il ne peut pas et doit garder 3 points par quadratique, on est a 12 points au total. Si tu utilises une routine a 100 pas, alors le player doit garder en memoire les coordonnees des 100 points (10 fois plus). Si tu utilises ca pour generer des gros graphiques, genre plusieurs dizaines ou centaines de courbes cubiques, la consommation de memoire peut grimper vite (enfin bon, c'est pas la mort non plus).

Je dis tout ca en tres theorique et en pure speculation parce que je n'ai pas etudie la consommation de memoire avec les APIs de dessins. J'essaye d'etre logique sur le fonctionnement du Flash player mais c'est possible que ca ne se passe pas du tout comme je le decris. Ca me semble juste tres logique de vouloir utiliser les courbes qudratiques puisqu'elles sont supportees nativement. Si quelqu'un fait des tests precis et a des resultats qui montrent que ca va plus vite sans approximation par quadratique, je suis ouvert et carrement preneur :).

9 Le 12 octobre 2003, 23:03 par Kib

Alcys : merci pour la référence.

Timothée : J'ai peut être parlé et lu trop vite pour les coeff binomiaux, après tout, ce sont des entiers, et puis nCr(4,i) c'est pas si compliqué

Je n'ai pas etudie la consommation de memoire avec les APIs de dessins
Moi non plus, mais je pense que ton intuition est raisonnable. Je vais essayer d'implémenter des courbes de bézier à plus haut degrè, à titre d'exercice, j'essaierai de faire des mesures de temps ! Arf !

10 Le 13 octobre 2003, 10:12 par LAlex

Kib >> n'hésites pas à nous tenir au courant !!!

11 Le 6 novembre 2004, 02:12 par mnia_siham

est ce que les courbes de bezier peuvent aider a trecer l arcade detaire?

12 Le 6 novembre 2004, 02:14 par mnia siham

est ce que les courbes de beziers peuvent m aider a tracer l'arcade dentaire?

13 Le 6 novembre 2004, 08:45 par ekameleon

euh ? dépend de ce que tu entends par tracer une arcade dentaire
Tu veux faire quoi exactement ? un traçage dynamique de la machoire de quelqu'un en vecto ?

14 Le 11 juin 2005, 19:27 par naruto

juste comme ca ! pour l'application de thimothee je l'ai généraliser a n point mais au bout d'un certain nombre de calcul , le logiciel commence a ramé un peu ! voila

15 Le 11 juin 2005, 20:32 par ekameleon

on peut voir un exemple de code & co ?

16 Le 17 janvier 2006, 19:28 par exam

Bonjour tt le monde,

Je suis un etudiant en inge et je travaille sur un projet de fin d'etude. Alors si vous pouvez m'aider je vous serais tres reconnaissant.

Voila, ce que je voudrais savoir c'est comment trouver la deformation realiser sur une premiere courbe pour avoir une deuxieme courbe. En d'autres termes, j'ai 2 courbes avec toutes les coordonnees et je voudrais savoir comment passer de la premiere courbe a la seconde ...

Et sinon, a partir des coordonnees que j'ai, pourrais je determiner la fonction de cette courbe ???

Merci de me repondre le plus rapidement possible

17 Le 18 janvier 2006, 10:58 par LAlex

Merci de me repondre le plus rapidement possibleMauvaise pioche! Tu es ici sur un blog, pas dans un espace de support... Essaie sur des forums tels que MediaBox!

++ ^^

18 Le 17 avril 2006, 18:20 par Guillaume

Je voulais savoir si tu avais un dossier sur les courbes de béziers ou si tu avais un programme en pascal qui permet de calculer les polynome de bernstein etc merci de ta réponse

19 Le 24 novembre 2007, 21:33 par sandra444454

ecrére un algorithme qui calcule le p d c d des deux nombres (pdcd: plus grand commun division

Fil des commentaires de ce billet