bézier pb maths

[Ter Rowan]

hello guys

je fais différents tests graphiques avec les courbes de bézier cubiques

L'idée est de construire des paysage à partir d'un sol qui suit les dites courbes

j'ai poc"é" cette idée cependant je me trouve confronté à une problématique particulière :

l'utilisation des courbes implique (jusqu'à ce que vous me disiez comment faire autrement) sur une fonction basé sur un "pas"

x= f(pas)
y= g(pas)

or la dispersion n'est pas du tout ce que j'attendais, elle n'est pas homogène

on voit dans l'image que les courbes du haut sont des segments de droite qui positionnent
les points tous les x px en abscisse (pas = 0,1)

les courbes du bas sont des courbes de bézier cubique (toujours le pas = 0,1), mais avec un agglomération sur la partie gauche des courbes (particulièrement vraie sur les graphes du milieu et de droite en bas) ce qui ne me permet pas de positionner comme je le souhaite

je cherche donc à trouver le moyen de suivre la courbe mais avec une fonction y= h(x)
qui me permette de positionner chaque objet là où je le veux, en choisissant les abscisses

ca sous entend de trouver la fonction inverse de f ( afin d'avoir pas = f-1 (x) )

et là, je sais plus faire (où bien j'ai plus envie de retrouver des méthodes que j'ai apprises y a pfiou... trop longtemps)

si l'un de vous pouvez me donner le coup de pouce nécessaire....

à ciao

[Xenos]

Donc si j'ai bien compris, tu chercherai à placer les points à abscisses curvilignes régulières, pour avoir ce genre de chose?

Comme tu le vois sur les sources de l'exemple, en SVG+Javascript, c'est assez facile
Dans quel langage se place-t-on ici?

[Ter Rowan]

humm pas mal côté javascript (je ne connaissais pas getPointAtLength)

Effectivement ca correspond au besoin de restitution


mais tu poses la bonne question, dans quel langage se place t on.

Je me pose la question d'architecture.


là j'étais parti sur une génération php de svg stocké en bdd

l'idée : à la création / modification d'une case, de ses voisines, le php calcule le paysage (type de case, choix d'une courbe aléatoire mais définitive, position aléatoire mais définitive des éléments de décor (arbre, rocher, etc...) via l abscisse (curviligne me va bien, même si je pensais au départ au repère orthogonal)

évidemment pour ne pas surcharger le svg, je génère des use (pour une forêt , je ne vais pas dessiner 50 fois le même arbre= et d'un point de vue base de données je ne stockerai qu'une fois un décor donné (+ la liste des defs nécessaires pour afficher les use)


côté client, lors d'un déplacement, requête ajax, script php qui lit la bdd, envoie les svg des defs qui manque, envoie le svg final, et javascript met a jour

maintenant je pourrais faire autrement :

au lieu de stocker le paysage en svg, je pourrais le stocker en json et charge au client d'interpréter le json pour en faire du svg, ca ferait moins de données à transférer mais plus de calcul côté client

du coup je ne sais pas trop :/ ce qui est sûr c est que je veux calculer et stocker le paysage une fois pour toute

[Xenos]

En PHP, je n'ai pas de fonction toute prête.
La seule méthode que je vois consiste à découper l'intervalle [0,1] de t en N points, de calculer le point de la courbe de Bézier correspondant à t_i, et de faire ensuite une interpolation; donc, cela revient à approximer la courbe de Bézier par une ligne brisée dont les sommets sont les points de la courbe, aux paramètres t=i*P avec P le pas du calcul (1/N où N est le nombre de points voulus) et i l'index/numéro du point.

Si tu mets du pseudo-aléatoire, tu n'auras pas besoin de stocker la carte complète en BDD: seuls les points de contrôles seront stockés.
Par exemple, si au lieu d'utiliser un random() tu utilises la fonction sinus (avec une amplitude, une phase et une fréquence fixées), alors tu auras des variations de valeur qui ne seront pas aléatoires, mais qui seront calculables par n'importe qui (client ou serveur). Tu allègeras énormément la BDD, à condition que le serveur n'ai pas besoin de calculer la position des objets de nombreuses fois.
Par exemple, si le serveur doit calculer la position de tous les objets environnants pour savoir si le joueur courant peut voir un autre joueur avant de l'attaquer, alors il vaut mieux stocker la position des objets en BDD (sinon, ce serait lourd à calculer car ce calcul implique de nombreux objets et doit être souvent fait).
Sinon, si le calcul de position des objets n'est pas courant, ou s'il est fait pour 1 objet de temps en temps (par exemple, il est fait pour l'objet que le joueur veut activer), alors cette méthode sera probablement intéressante.

Il est possible de complexifier la fonction pseudo-aléatoire, soit en prenant un mersenne twister avec un seed précis et fixe (mais il faut alors que javascript ET PHP, aka que les langages utilisés, aient le même MT implémenté). Sinon, une somme de sinus à base/amplitude/phase/fréquences différentes sera suffisante.


Patron de fonction pseudo-aléatoire simple:

⅀(Base[i] + Amplitude[i]*sin(Frequence[i] * x + Phase[i]))

---

Un exemple live (rafraichir/F5 pour obtenir une nouvelle fonction) de ce que donne une telle fonction pseudo-aléatoire.
La période d'une fonction de cette structure-là est très difficile à calculer, dès l'instant où les fréquences des sinus et leur phase ne sont pas multiple les uns des autres.
Avec de telles fonctions, il y a quelques avantages:

• La moyenne de la fonction est la somme des "bases"
  
• La période est quasi-infinie si les fréquences et les phases ne sont pas multiples les unes des autres
  
• Elle est très portable (beaucoup de langages peuvent l'implémenter... à part XSL >.>)
  
• Sa valeur absolue ne peut dépasser la somme des valeurs absolues des amplitudes
  

En revanche, son min/max réels sont très difficiles à trouver.

[seishin]

et en utilisant l'interpolation de Bernstein ?

Wikipedia (en anglais car la vf est trop concise)
Wikipedia FR quand même

Pour une version efficace, Algo de DE CASTELJAU

[Ter Rowan]

ça me parait lourd tous ces calculs
je vais voir pour la graine quand même mais je vais partir sur le scenario d'abscisse curviligne (donc javascript qui positionne avec la fonction getPointAtLength)

avec

en structure globale

{

	"curve" : svg de la courbe

	"reverse" : true / false (pour le paysage vu de l'autre côté (faut que je creuse ce point, pas si sûr)

	"objects" : collection des instances d'objets à afficher

	"defs" : collection des svg de chaque type d'objets

}

et le descriptif de l'instance d'objet

{

	"use" : l'objet graphique

	"t" : l'abscisse curviligne

	"x" : décalage horizontal par rapport à la courbe

	"y" : décalage vertical par rapport à la courbe

}

[Xenos]

Les algorithmes donnés approximent les courbes de Bézier, or, ici, seules des Bézier cubiques (ordre 3) sont utilisées, l'approximation est donc superflue, puisqu'on peut calculer aisément, à tout paramètre t, le point P(t)=[x,y] correspondant.

La difficulté est que pour trouver l'abscisse curviligne exacte, il faudrait intégrer la racine des carrées la fonction paramétrique dérivée de la courbe de Bézier... Et on aboutit à des fonctions elliptiques qui ont peu de chances d'être implémentées en PHP.

En d'autres mots, l'abscisse curviligne, seule méthode mathématique exacte pour répartir des points régulièrement le long de la courbe, n'est pas calculable sur une Bézier cubique, et donc, il faudra se contenter de l'approximation donnée par getPointAtLength() ou réaliser une interpolation (en approximant la Bézier par une ligne brisée).