Archives de catégorie : Timidouveg’s Museum

[Timidouveg’s Museum] Système de décision de l’ordre des points et surbrillance des secteurs

J’ai mis en ligne les dernières nouveautés dans l’éditeur de mon futur musée virtuel. Comme je l’avais indiqué dans les premiers tutoriels d’algorithmie/mathématiques sur ce blog, j’ai conçu un système de décision de l’ordre approprié pour les points d’un polygone qui assure que peu importe dans quel sens vous dessinez vos secteurs, l’intérieur sera bien à l’intérieur et l’extérieur à sa bonne place 😀 Comme d’habitude, cliquez sur l’image pour accéder à l’éditeur de musée virtuel 🙂

TimidouvegMuseum_2017-07-31Autre chose que j’ai ajouté à l’aide des fonctions affines dont j’ai parlé dans le troisième tutoriel en utilisant le terme d’équation cartésienne d’ailleurs. Ce n’est pas tout à fait faux puisqu’une fonction affine est une équation cartésienne simplifiée pour une droite en 2 dimensions 😉 Bref, il est maintenant possible de mettre en surbrillance jaune les secteurs sous le curseur de la souris. Pour l’instant ça n’apporte rien au dessin, mais ça entrera par exemple dans une fonctionnalité permettant d’afficher des informations sur le secteur ou encore ajouter des polygones internes pour dessiner pourquoi pas des colonnes ou des murs au milieu d’une salle.

Une dernière chose, on peut toujours activer/désactiver le mode « Création de secteur » avec la touche C du clavier, mais en haut à gauche de l’écran est disponible un bouton pour le faire avec la souris. Comme la touche, il faut cliquer à nouveau sur le bouton pour désactiver le mode et pouvoir déplacer des points. J’ai mis un bouton simple, mais j’envisage de mettre un bouton qui reste enfoncé quand activé, lorsque j’aurais compris les classes qui permettent de faire ça ;p

Détecter si un point est avant, sur ou après une droite

Parfois, il est intéressant de savoir si un point est sur une droite, avant ou après. Dans mon moteur Build-like pour mon musée virtuel, par exemple, détecter cela entre dans le système de décision du sens du dessin. Si un polygone est dessiné dans un sens, il sera considéré à l’endroit (normales dirigées vers l’intérieur) ou dessiné dans l’autre sens, il sera considéré comme à l’envers (normales dirigées vers l’extérieur). J’expliquerais ce système de décision dans un autre article qui marie la technique pour trouver le sens d’un segment et celle présenté ici 🙂

Detecter point droite 1Dans le dessin ici présent, on peut voir une droite et trois points. Le point A et avant la droite, soit négatif. Le point B est sur la droite, soit à zéro. Le point C est après la droite, soit positif. Pour calculer le signe du rapport entre le point et la droite, il faut d’abord calculer l’équation cartésienne de la droite à partir d’un vecteur de cette droite. Prenons un segment et calculons son vecteur directeur. J’explique cela dans l’article Calculer la norme, la normale et le milieu d’un segment. Voici comment déterminer l’équation cartésienne de ce vecteur directeur non horizontale, ni verticale. Ces deux cas particuliers seront déterminés ensuite.

Équation à déterminer :
Vecteur.y = a * Vecteur.x + b
Détermination de a et b :
a = Vecteur.y / Vecteur.x
b = Vecteur.y - a * Vecteur.x

Voilà, une fois cette équation obtenue il s’utilise simplement en plaçant des coordonnées du point à détecter sur ou autour de la droite à la place y et x et déplacer y dans l’équation de sorte à obtenir un nombre inférieur, égal ou supérieur à zéro.

Détection = a * Point.x + b - Point.y

Avant d’expliquer avec un schéma où se situe la positif et le négatif pour les différentes droites possibles, voici comment traiter les droites horizontale et verticale.

Équation horizontale :
Vecteur.y = b
Donc :
a = 0
b = Vecteur.y
Équation verticale :
Vecteur.x = a
Donc :
a = Vecteur.x
b = 0

Pour l’utilisation de ces équations, il n’y a pas de difficulté pour la droite verticale, par contre pour la droite horizontale, il y a un sens à respecter pour obtenir un résultat signé correctement comme vous le verrez sur le schéma qui suivra.

Avec la droite verticale :
Détection = Point.x - a
Avec la droite horizontale :
Détection = b - Point.y

Detecter point droite 2La logique de ces équations ressort dans le schéma suivant. Dans un repère avec X allant de gauche à droite, et Y allant de haut en bas, cela se passe comme suit. Pour la droite horizontale, le signe positif se trouve à droite et le négatif à gauche. Pour la droite horizontale, le signe positif se trouve en haut et le négatif en bas. Le sens est inversé par rapport au repère pour cette droite. Enfin, les autres droites, en les imaginant tourner de la droite verticale en partant d’en haut (au-dessus de zéro), et tournant vers la gauche, le positif est donc à droite de la droite, parties bleue et rouge confondus. Une fois que le haut (bleu) de la droite dépasse la droite horizontale, toujours en tournant vers la gauche, donc se trouve en dessous, le positif est au-dessus de la droite et le négatif en dessous, et tend vers la droite du repère. La rotation s’arrête peu avant de revenir à une droite verticale, autrement le positif à gauche pour la partie bleue de la droite en bas change de côté. C’est visible pour la partie rouge de la droite verticale qui suit le sens de sa partie bleue.

Ce principe rappelle mon schéma pour le Calcul du sens d’un segment, à la différence que l’axe des changements de sens n’est pas l’axe des X, mais celui des Y. En adaptant ce schéma du sens d’un segment à celui-ci, j’ai pu marier les deux techniques et concevoir mon système de prise de décision du sens du dessin et de où se trouve l’intérieur et l’extérieur d’un secteur dessinés sans  que nous utilisateurices n’ayons à nous soucier du sens du dessin. Ce sera expliqué au prochaine article 🙂

[Timidouveg’s Museum] Déplacer les points créés et normale

Il y a quelques jours j’ai ajouté la possibilité de déplacer les points créés dans un secteur, au cas où l’utilisateurice se trompe ou simplement pour modeler son secteur à sa convenance. Je n’ai pas encore ajouté de boutons pour changer de mode, ni pour témoigner du mode dans lequel vous êtes. Il y a maintenant deux modes dans l’éditeur. Le mode création de secteurs que vous pouvez activer en appuyant sur la touche C du clavier, et le mode déplacement de points, en appuyant à nouveau sur C. Lors que vous arrivez sur l’éditeur, le mode actif est le déplacement de points. Vous ne pouvez donc pas créer de secteurs avant d’avoir appuyé une fois sur C. Attention à ne pas oublier d’appuyer sur C pour déplacer les points mal placés, autrement vous risquez de créer de nouveaux points en cliquant que un d’entre eux. Ce n’est pas pratique, et ce sera changé à l’avenir. Aussi un message indiquant le numéro du point apparaît en bas à gauche lorsqu’il est en cours de déplacement.

TimidouvegMuseum_2017-07-26Petit détail qui va évoluer aussi pour des raisons pratiques, en mode déplacement de points, chaque point survolé par le curseur de la souris est orange. Dés que vous cliquez sur le point, il devient jaune et si vous bougez avec le bouton de la souris enfoncée, le point et les lignes du dessin suivent la souris. La sélection orange utilise une simple condition d’égalité entre la position du point et la souris. Ce n’est pas pratique parce qu’il faut se mettre vraiment dessus et non un peu à coté pour attraper le point. C’était pour la première étape des tests à ce sujet, mais je changerais de méthode pour un cercle de détection autour du point et un système de choix du point le plus proche de la souris 🙂

Dans cette nouvelle version de l’éditeur, j’ai fais apparaître un fond blanc transparent qui permet de distinguer l’intérieur d’un secteur de l’extérieur (le vide). J’ai aussi ajouté des petits traits oranges au milieu des segments. Ces traits sont les normales des segments qui permettent de visualiser le sens des segments dont j’ai parlé dans l’article Calculer le sens d’un segment. J’explique dans l’article Calculer la norme, la normale et le milieu d’un segment, comment j’ai conçu ce petit système.

Rappel du lien vers l’application : Timidouveg’s Museum. Vous pouvez aussi cliquer sur l’image que pour y accéder 🙂

Calculer la norme, la normale et le milieu d’un segment

Dans cet article on va parler de comment calculer simplement la norme, la normale et le milieu d’un segment en 2 dimensions. L’intérêt est multiple, mais en ce moment, ces trois calculs me servent à afficher les normales des murs des secteurs dans l’éditeur de mon moteur de musée virtuel. Je m’en suis servit en partie dans Demiurge, en 3D, sauf pour la normale qui nécessite l’utilisation d’un produit en croix pour les surfaces (cross product en anglais).

Le milieu d’un segment

Commençons par le milieu d’un segment qui ne nécessite pas les deux autres pour être calculé. En 2D, pour calculer simplement le milieu d’un segment, il suffit tout d’abord de ramener le segment à son vecteur directeur, ici non normalisé, comme on la vue dans l’article sur le calcul du sens d’un segment. L’équation est simple, je le rappelle ici :

Vecteur = (xB - xA, yB - yA)

Ce vecteur, contrairement, au segment (sauf cas particulier) a sa position aux coordonnées (0, 0) et donc les coordonnées de la pointe du vecteur correspondent logiquement à la soustraction du deuxième point du segment par le premier point. Il s’agit d’une simplification du segment qui permet de lui faire toutes sortes de choses et notamment trouver le milieu, mais aussi sa normale. Mais, on verra après pour la normale 🙂

Pour trouver le milieu du segment, il reste deux étapes toutes simple. La première consiste à diviser par 2 les coordonnées du vecteur non normalisé. Ainsi, on obtient la moitié du vecteur. Puis, la deuxième et dernière étape consiste à ramener le vecteur à sa place en l’additionnant avec le premier point du segment.

DemiVecteur = (Vecteur.x / 2, Vecteur.y / 2)
Milieu = (xA + DemiVecteur.x, xB + DemiVecteur.y)

La norme du segment

La norme d’un segment est la distance entre le premier et le deuxième point qui le constitue. C’est à dire, pour faire simple, sa longueur. Peu importe que votre segment se trouve sur une grille de pixels, et donc soumis à un repère, il s’agit là de la longueur que vous obtiendriez si vous aviez une règle est mesureriez le segment 🙂

La formule de la norme est un peu plus compliqué et gourmand en ressources pour un ordinateur que ce qu’on a fait précédemment. Heureusement pour nous, elle a au moins le mérite de tenir sur une seule ligne :p

Norme = √(Vecteur.x²+Vecteur.y²)

Je le réécris différemment pour plus de lisibilité et de compréhension.

Norme = RacineCarrée( Carré(Vecteur.x) + Carré(Vecteur.y) )

J’ai utilisé ici le vecteur de tout à l’heure. En effet, on ne calcule pas directement la norme d’un segment, mais celui de son vecteur non normalisé. Et si depuis tout à l’heure je n’ai pas normalisé mon vecteur, c’est précisément parce que normaliser signifie qu’on le ramène à une norme de 1, hors nous voulons mesurer notre segment, ce serait donc absurde 🙂

Avec une norme on peut faire le calcul du milieu du segment d’une façon différente que la méthode précédente, mais aussi faire d’autres choses comme calculer la trajectoire d’un projectile par exemple. Cependant, pour y arriver, il va normaliser le vecteur. Je vais vous expliquer comment en même temps que le calcul de la normale d’un segment ou d’une droite 🙂

Normaliser un segment et calculer sa normale

Comme je l’ai dit tout à l’heure, normaliser un vecteur, c’est mettre sa norme à 1. Et pour faire cela, rien de plus simple 🙂

Normalisé = (Vecteur.x / norme, Vecteur.y / norme)

Voilà, c’est fait 😀 Il suffisait tout simplement de diviser les coordonnées du vecteur précédemment obtenu. C’est assez logique, puisque la norme est la longueur du vecteur de départ. Et c’est pour cette raison qu’un vecteur normalisé est très utile pour une trajectoire de projectile par exemple, puisque entre le moment où un personnage fait feu et un instant T, le projectile aura parcouru une certaine distance. Ainsi, connaître son vecteur directeur permet de simplement le multiplier par la distance parcouru pour trouver les coordonnées du projectile :p Si vous voulez par exemple, afficher un objet se déplaçant suivant un vecteur, vous pouvez associer une distance pour chaque quantum de temps (fraction du temps) et additionner ces distances à chaque instant pour ensuite le multiplier par le vecteur. A chaque quantum de temps, votre ordinateur affichera votre objet aux bonnes coordonnées et vous le verrez se déplacer sur votre trajectoire. Ajoutez à ceci, un vecteur de gravité, qui irait toujours vers le bas, soit ceci (0, y), et vous aurez la base d’un jeu de missile, sniper ou d’archer, et une part non négligeable d’un Worms x)

Bon, je vous raconte tout ça, mais il me reste un truc à vous expliquer. C’est le calcul de la normale au segment, ou plus tôt au vecteur. La normale d’un vecteur est un vecteur perpendiculaire au premier. Là encore, en 2 dimensions, trouver la normale d’un vecteur est simplicime. Voici la formule :

Normale =(-Normalisé.y, Normalisé.x)

Et voilà, hihihihi 😀 Tout simplement, la coordonnées X de la normale est égale à la coordonnées Y en négatif du vecteur directeur, et la coordonnées Y de la normale est égale à la coordonnées X du vecteur directeur. Ni plus, ni moins 🙂 Il n’y a donc pas réellement de calcules à faire, mais juste des assignations de valeurs.

C’est lorsqu’on fait des tests sur un papier ou à l’écran, qu’on comprend l’utilité de calculer le sens d’un segment comme je l’ai proposé en premier article de la série sur l’algorithmie. En effet, si vous placez les points de votre segment dans un ordre ou dans un autre, vous changerez nécessairement l’ordre de ces derniers dans les opérations précédemment expliqué ici. Ainsi, votre normale ne sera pas dans le même sens non plus. Pour un ligne horizontale par exemple, la normale sera soit vers le haut, soit vers le bas, selon l’ordre dans lequel vous avez entré vos deux points du segment. Cette propriété peut provoquer des erreurs d’affichages, de physique dans un moteur physique, mais aussi, bien exploitée, permettre de déterminer l’intérieur et l’extérieur d’un monde comme dans mon moteur de musée 🙂

Bonus : Dessiner une normale au milieu d’un segment

TimidouvegMuseum_2017-07-26Je vous mets un petit algorithme qui utilise tout ce qui est au-dessus pour dessiner la normale d’un segment.

DessinerSegment(xA, yA, xB, yB);
Vecteur(xB-xA, yB-yA);
Norme = RacineCarré(Carré(Vecteur.x) + Carré(Vecteur.y));
Normalisé = (Vecteur.x/Norme, Vecteur.y/Norme);
Normale = (-Normalisé.y, Normalisé.x);
Milieu = (xA+Vecteur.x/2, yA+Vecteur.y/2);
DessinerNormale(Milieu.x, Milieu.y, Milieu.x+Normale.x, Milieu.y+Normale.y);

Si les unités de votre dessin sont les pixels, la normale ne fera qu’un seule pixel et dans certains cas, il ne pourra pas s’afficher. Vous pouvez donc multiplier ses coordonnées par un nombre raisonnable pour bien voir la ligne s’afficher et apprécier la perpendiculaire a votre segment 🙂

Calculer le sens d’un segment

Sens segments 1Dans ma reproduction du moteur Build de Ken Silverman pour mon musée virtuel, j’ai eu besoin de déterminer le sens d’un segment. Je définis le sens du segment par est-ce que le segment va du point A au point B, ou du point B au point A. L’intérêt de savoir cela permet, dans mon moteur, de décider où se trouve l’intérieur et l’extérieur d’un polygone qui définit un secteur du musée. Lorsqu’on dessine un secteur, on ne fait pas toujours attention à l’ordre dans lequel on place les points qui le compose. Pour donner un exemple de l’intérêt de respecter l’ordre des points, dans OpenGL, placer les points dans un sens détermine la recto ou le verso d’un polygone, ce qui permet entre autres d’afficher l’un ou l’autre ou les deux. Dans mon moteur, en dessinant un secteur, si on se trompe dans l’ordre des points, l’intérieur ou l’extérieur seront inversés.

Comment faire simplement une détermination automatique du sens d’un segment pour ne pas avoir à le faire nous-même lors du dessin ? J’ai choisis d’utiliser les signes des coordonnées. D’abord, le moteur calcul un vecteur à partir des deux points du segment dans l’ordre dans lesquelles elles ont été dessinés. Ce dernier se calcule par l’équation suivante.

Vecteur = (xB - xA , yB - yA)

Une fois le vecteur correspondant au sens du segment, il suffit donc de regarder le signe des coordonnées. J’ai choisis d’indiquer le sens par négatif ou positif. Et je mets un dessin pour comprendre ce que ça donne pour toutes sortes de vecteurs sur 360°. Les sens sont déterminés de sorte à correspondre au cercle trigonométrique inversé dans l’axe Y en raison du fait que la plus part des repères graphiques sur ordinateur part du haut vers le bas et de gauche à droite. Ainsi le négatif est en haut pour les Y et le positif en bas.

Si Vecteur.x > 0 et Vecteur.y == 0 Alors
Sens positif horizontal;
Si Vecteur.y > 0 Alors
Sens positif;
Si Vecteur.x < 0 et Vecteur.y == 0 Alors
Sens négatif horizontal;
Si Vecteur.y < 0 Alors
Sens négatif;

Dans un autre article j’utiliserais ce petit système et vous expliquerais comment le moteur décide de l’ordre pour lire les points du dessin fraîchement réalisés par vous ou moi dans l’éditeur 🙂 Grâce à ça, et à l’aide d’une autre donnée, les secteurs et les ajouts aux secteurs sont créés de manière cohérentes.

[Timidouveg’s Museum] Création des secteurs

J’ai mis en ligne la suite du développement de l’éditeur pour mon musée virtuel 🙂 J’ai ajouté la structure de données pour stocker les secteurs et lorsque vous fermez votre dessin, le secteur est créé et le fond de votre dessins devient blanc transparent. Lors du dessin de votre section, une ligne grise simule la fermeture pour aider à voir comment il serait fermé au stade de votre dessin. Aussi les lignes ne sont plus continuent et lorsque vous avez fini un secteur, vous pouvez en créer un nouveau séparé du premier. Enfin, un petit message a été ajouté en bas à gauche pour indiquer le secteur créé.

Je mettrais une image plus tard pour la prochaine évolution, donc voici juste le lien rappel de l’application : Timidouveg’s Museum.

[Timidouveg’s Museum] Dessin de points et de lignes

J’ai avancé sur l’éditeur du musée virtuel 🙂 J’ai dimensionné la grille à 128 par 128 unités de points, et il est possible de se déplacer sur la grille à l’aide des flèches du clavier. J’ai aussi ajouté une ligne rouge pour l’axe des X et une verte pour l’axe des Y. Le zéro absolu est au centre de la grille, ce qui permet d’avoir des coordonnées de points allant de (-64, -64) à (64, 64). Il est possible de placer les points et ainsi de tracer des lignes blanches qui sont les prémices des murs du musée 🙂 Les points sont stockés dans un tableau qui grandit au fur et à mesure dynamiquement, mais je n’ai pas encore implémenté de sauvegarde.

Enfin, deux dernières choses à dire. Pour l’instant, les lignes sont dessinés en continue, ce qui veut dire que vous ne pouvez pas faire des dessins séparés, parce qu’à chaque point posé, une ligne relie la précédente à celle-ci. Je changerais ça évidemment, c’est juste une étape dans le développement en cours 🙂 La dernière chose à dire est que l’application est lente lorsqu’il y a des points dessinés. Plus il y a de points, plus vous aurez du mal à dessiner ou à déplacer la grille. La raison est que le dessin manipule les pixels mais de façon encore naïve. J’ai cherché sur Internet les outils proposés dans HaxeFlixel et j’ai trouvé une page qui explique une façon de manipuler directement les pixels, en faisant toutes sortes de manipulations de la mémoire, etc… Bref c’est très technique, mais j’ai absolument besoin de procéder ainsi. En effet, non seulement c’est plus pratique pour faire l’éditeur, mais c’est indispensable pour la future partie en 2.5D. L’idée est de reproduire un moteur 2.5D (vieille 3D entre le début et le milieu des années 90) en m’inspirant fortement du moteur Build de Ken Silverman 🙂

Je ferais une série d’articles tutoriels qui expliquera étape par étape comment est codé le moteur de mon musée et son éditeur avec HaxeFlixel. C’est l’occasion d’explorer plein de classes, fonctions, dépendances, etc… de ce framework, mais aussi d’étudier les différentes techniques utilisées pour faire un moteur comme Build et un éditeur de map pour ce type de moteur 🙂

[Timidouveg’s Museum] Mon futur musée virtuel

Je vous annonce la mise en ligne de ce que j’ai codé ce dimanche 16 juillet 2017 sur mon futur musée virtuel 🙂 Pour l’instant il n’y a qu’un écran de titre très sobre et simple et un écran pour l’éditeur de musée. L’éditeur ne permet rien pour le moment. Vous pouvez juste voir que j’ai codé un canevas avec une gris et dedans un point est affiché et suit la souris. Le point ne peut pas sortir du canevas et accroche à la grille et donc ne suit la souris que de sorte à rester sur les intersections des lignes de la grille.

TimidouvegMuseum_2017-07-16C’est un bon début, puisqu’à ce stade je vais pouvoir le week-end prochain, ajouter des boutons et touches de clavier pour activer le placement et la suppression de points et développer les fonctions qui vont bien. Par la suite, j’ajouterais des lignes entre les points, et une sauvegarde avec un système retrouver son plan 🙂

L’éditeur ne devrait en réalité servir qu’à moi pour faire mon musée, mais je le mettrais à disposition pour vous amuser à faire votre propre plan de musée. Je mettrais aussi à disposition le programme en HTML5 ou neko ou autres, selon vos besoins pour que vous puissiez installer votre propre musée sur votre site ou blog 🙂