Discussion :

[TicTacToe]

Bonjour

Je ne faisais que passer, et je dois dire que je n'ai pas tout compris
(établir vraiment au hasard des vecteurs normés dans un cadre ?)

mais je passais juste pour ceci

Il faut faire attention avec les fonctions trigo c'est ce qui cosomme le plus de temps proc... Comme je l'ai déjà dis plus haut dans mon cas ça va servir très souvent. Si je commence à claquer 10000 sinus entre 2 frames juste pour générer mes vecteurs aléatoires, il n'y aura plus de temps pour faire le reste !!

Une manière classique de s'affranchir du temps de calculs des opérations trigo, et de précalculer dans un tableau (plus ou moins grand selon la précision souhaitée) toutes les valeurs de sin et cos... C'était classique à l'époque des démo 3D temps réels avec des machines très peu puissantes (286,386...). La méthode est efficace mais limitée en précision/range des valeurs selon la taille des tableaux...

voila, c'était juste pour ca

[j.p.mignot]

Pour essayer l'avoir une direction aléatoire j'avais procédé comme suit.
étape 1
répartir N points uniformément sur une sphère

étape 2
assimiler localement la sphère à son plan tangent autour de chacun de ce N points et utiliser la fonction ‘random’ pour une pondération aléatoire.

Pour l'étape 1 j'ai utilisé un modèle physique: si on suppose N charges identiques contraintes sur une surface, l'équilibre est atteint si F est normal à la surface pour chacune des charges. Ici on peut laisser de coté la constante 1/4/pi/eps0 . Le vecteur Fi peut donc s’écrire

Vecteur(Fi) = Somme(j <>i) Vecteur(Dij)/(dij^3) (a)
et
Fi vectoriel Ri = 0 pour équilibre de la charge ceci pour tout i ( minimum énergie potentielle du système )

Un moindre carrés [par exemple minimiser la somme des carrés des normes de Fi vectoriel Ri ] permet en quelques cycles de converger ( distances aux + proches voisins stable à # 10^-10) . La position initiale des N charge à été faite sur un nombre x de parallèles ( au sens géographique ) où j’ai mis y(x) points afin que les distances entres points ne soient pas initialement trop distribuée. Ici un calcul très simple permet d’estimer le nombre de parallèles et le nombre de points par parallèle pour initialiser N points.

L'étape 1 est "plutôt" longue mais peut être faite une seule fois. Autant que je me souvienne, j’avais pris 2048 points. Evidemment dans (a) il y a N-1 sommes. On peut aussi rendre le process + rapide en limitant aux x 1er voisins ( force en 1/d^2 décroît assez vite )

A partir de ces N points créer N éléments de surface

Un point aléatoire à alors été défini par
1- choisir aléatoirement 1 des N éléments de surface. ( la probabilité de choisir une surface peut être proportionelle à sa surface qui varie un peu de l'une à l'autre )
2- prendre ses m sommets
3- pondérer aléatoirement ces m points
4- projeter ce point sur la sphère ( ce qui crée une légère non uniformité, assimilation de la sphère à son plan tangent )
Cette erreur reste faible. L’élément de surface est vu du centre avec un angle solide
4Pi/N. le cône ‘moyen’ à donc une ouverture (angle au sommet * 2 ) vérifiant
2pi*(1-cos(a/2)) = 4pi / N
1-2/N = cos (a/2) # 1 – a^2/8 => a^2 = 16/N => a= 4/sqrt(N)

[TicTacToe]

Bonjour,

En 2D les coordonnées polaires résolvent le problème. En 3D aussi, je pense.

je ferais comme Graffito, j'ai testé, voila ce que ca donne en 2D


Vecteurs

Ca m'a bien l'air uniforme, et je vois pas pourquoi ca changerai en 3D... ?

Et question rapidité, l'algo est très simple, en 2D là

Point1 = Random
Angle = Random
Point2.X = Norme * cos( Angle )
Point2.Y = Norme * sin( Angle )

ou alors, j'ai rien compris à la question, c'est possible aussi
Etant donné que Cos et Sin peuvent être des tableaux et non des fonctions comme je l'ai cité, si on veut de la rapidité pure., donc très peu d'opérations élémentaires

[FrancisSourd]

Un moyen assez radical pour tirer les points rapidement est de précalculer un grand nombre de points sur la sphère (uniformément répartis), de les stocker et de tirer à chaque fois un point dans cette collection.

[2Eurocents]

Un moyen assez radical pour tirer les points rapidement est de précalculer un grand nombre de points sur la sphère (uniformément répartis), de les stocker et de tirer à chaque fois un point dans cette collection.

C'est le principe de "la balle de golf".

Cette méthode est extrêmement performante sur un problème 'statique' (nombre de points sur la sphère qui ne variera pas).

Elle nécessite, en revanche, un bon calcul de la répartition initiale de tous ces points : un bon maillage isotrope.

L'avantage essentiel, en terme de performances, c'est que ce maillage peut même faire partie des données initiales du programme, il n'a pas besoin d'être calculé en direct.

[j.p.mignot]

Un moyen assez radical pour tirer les points rapidement est de précalculer un grand nombre de points sur la sphère (uniformément répartis), de les stocker et de tirer à chaque fois un point dans cette collection

C'est 1 peu ce que je préconisais en proposant un calcul par moindre carrés pour localiser ces N points.
Je pense qu’il est tout de même préférable de limiter un peu ce nombre de points et d’assimiler la sphère à son plan tangent autour de ces N points puis de faire une pondération à partir des sommets de chacun des éléments de surface. Il s’agit là de trouver le meilleur compromis dans un cadre donné.

[FrancisSourd]

C'est 1 peu ce que je préconisais en proposant un calcul par moindre carrés pour localiser ces N points.
Je pense qu’il est tout de même préférable de limiter un peu ce nombre de points et d’assimiler la sphère à son plan tangent autour de ces N points puis de faire une pondération à partir des sommets de chacun des éléments de surface. Il s’agit là de trouver le meilleur compromis dans un cadre conné.

Effectivement, j'avais pensé à cela pendant le week-end et j'ai tapé cette idée ce matin avant même de lire ce qui avait été écrit entre temps...

[Rafy]

Alors voila des petites images qui vont être plus parlantes que tout les discours :
http://rafy.developpez.com/Croix
A savoir qu'il y a toujours une concentration au centre, Car ce que vous voyez est disque que j'ai généré en partant d'une sphere (on prend une sphere et on l'écrabouille), mais j'ai une version ou je n'ai plus cette concentration au centre car je fais un choix aléatoire sur le rayon de manière non uniforme suivant de rayon, ainsi, j'ai un disque parfaitement uniforme...
J'ai préfèré montrer le disque car la sphere on ne voyait pas très bien sur le screen shot... mais c'était le même problème.
J'ai utilisé boost::uniform_on_sphere et triangle_distribution comme algorithme de génération (respectivement choix d'un vecteur et choix non uniforme) et comme générateur, après quelques test j'ai choisi le fibonacci607.
Pourquoi celui la ?
Ben car c'est parmi un des plus rapide, et son cycle est très grand (le 607 est le plus petit mais largement suffisant pour moi)
Donc voila, Merci à tous pour vos réponses.

[Matthieu Brucher]

Super, je suis content pour toi

[Rafy]

Et encore une affaire de résolue