Windmill : moteur graphique 3D - PARTAGE DES SOURCES
Posté le 30/09/2016 00:44
Windmill
Bonjour, bonsoir !
Windmill est un moteur graphique 3D pour calculatrices CASIO monochromes.
Ce topic est le journal de bord du projet, il décrit l'avancée étape par étape, jour par jour, depuis la création du projet à aujourd'hui.
Début du projet : juillet 2016
Dernière mise à jour : mars 2019
Dernière démo : jour 22
Un petit brief d'abord :
Windmill est un moteur graphique 3D, il est capable d'afficher des objets définis en trois dimensions.
Le principe de base du moteur graphique est de décomposer en triangles un modèle 3D puis d'appliquer des textures sur ces triangles en gérant l'occlusion.
Sur calculatrice, il n'existe aucune libairie dédiée à le 3D, donc Windmill a été écrit à partir d'une feuille blanche, tout à été réalisé de A à Z.
Jour 1
Cliquez pour recouvrir
Dans la vidéo, j'ai optimisé le moteur graphique pour les murs verticaux. c'est à dire qu'il ne dessine plus des triangles mais des trapèzes, j'ai commencé l'optimisation pour les murs horizontaux récemment.
La bonne nouvelle c'est qu'il reste une grosse marge de progression pour optimiser ces cas particuliers : éviter les flottants, gérer un peu mieux le clipping, le back face culling et éviter un calcul redondant dans la boucle principale.
Jour 2
Cliquez pour recouvrir
Principalement un gros travail sur l'optimisation des murs : la plupart des calculs flottants sont désormais avec des entiers, le clipping est géré (on affiche pas les pixels en dehors de l'écran), des calculs sont simplifiés, et même pour gagner encore quelques fps les textures doivent être tournées de 90°.
Désormais les murs horizontaux peuvent être affichés, et même le plafond noir (avant c'était de la triche juste pour la vidéo...), des textures peuvent être appliquées sur le sol, et on peux construire des objets telle que la caisse ici présente.
Les textures peuvent être changées pendant le jeu, ainsi cela permettra d'afficher des textures animées comme de l'eau par exemple !
Il y a trois types d'objets affichable :
- les murs. De face ou de coté.
- les étages. Il s'agit d'objets plats, par exemple le sol, le paillasson, le haut de la caisse.
- le plafond. C'est un étage optimisé pour le noir.
Tous les objets sont paramètrables, de la taille, la hauteur, la texture que l'on veut.
Jour 3
Cliquez pour recouvrir
Simplement un aperçu de la vue de coté, en fil de fer cette fois parce que je n'ai pas terminé l'algo pour afficher les textures sur les murs.
J'ai déjà la structure de l'algo pour appliquer mes textures, il me reste plus qu'a l'implémenter. Il ressemble à celui que j'ai déjà mais avec une variante. Cependant je vais le reprendre de zéro pour être certain d'optimiser au mieux.
Parce que avec cette vue il y a beaucoup de chose qui changent :
- les textures appliquées sur le sol, au plafond ne sont plus des sprites classiques, elles sont maintenant déformées ce qui implique d'utiliser l'algo "lourd" et pas un simple affichage de sprite zoomé (cf la lib ML_zoom)
- les murs orientés vers le "sud" ne sont plus visible car toujours vu par "derrière" donc plus besoin d'être géré. Ça c'est une bonne nouvelle, mais je ne pense pas que ça puisse compenser le point du dessus.
Donc en conclusion, j'ai peur quand aux performances de l'ensemble fini. Il va arriver un moment où ça risque de coincer.
Jour 4
Cliquez pour recouvrir
GROSSE GROSSE nouveauté ! Comme promis le moteur gère la vue de coté !!
Pour cela j'ai totalement repris mon algo de base pour appliquer les textures sur des triangles avec un bon passage à la moulinette de l'optimisation, et j'ai ainsi multiplié par 11 les performances ! C'est énorme !
La prochaine étape est d'implémenter le Z-buffer pour ne pas voir à travers les murs, et encore un tas d'optimisations...
Et maintenant il n'y a pas de cas particuliers dans l'algo, c'est à dire que je peux tourner la caméra dans tous les sens, afficher des formes dans n'importe quelle position (mais ça ce sera pour une prochaine vidéo )
Jour 5
Cliquez pour recouvrir
Et voilà encore du nouveau ! (Oui ça avance vite )
Maintenant j'ai rajouté le z_buffer qui permet de ne pas afficher les murs sensé ne pas être visible.
Et j'ai rajouté un degré de liberté pour la caméra, ce qui permet de tourner sur soi-même.
Il reste encore un tas de choses à améliorer (meilleur rendu des textures, déplacement de la caméra selon différents repères) et d'optimisations (accès à la vram plus intelligent pour éviter de dessiner du banc si c'était déjà blanc, passage des calculs pour les rotations, les projections et les produits vectoriels en nombres entiers).
Je vais mixer un peu le rendu avec le mode fil de fer pour les murs vu par derrière (qui sont transparents actuellement). J'ai déjà fait quelques test et on se rend mieux compte des volumes !
Jour 6
Cliquez pour recouvrir
J'ai amélioré la qualité du rendu général en jouant sur les décalages de bits de façon plus astucieuse, en simplifiant des opérations et en arrondissant les nombres flottants. Résultat moins de perte à cause d'arrondi et de troncature, les textures sont moins déformées et plus précises. J'ai encore optimisé mon algorithme pour appliquer les textures, j'étais passé à côté de quelque chose d'énorme, résultat j'ai pu simplifier encore mes calculs pour gagner 35% de performances. Je suis passé de 10 décalages de bit, 17 mults, 9 additions à 7 décalages, 12 mults et 10 additions.
J'ai apporté quelques modifications au z-buffer (qui permet de ne pas afficher les objets caché par d'autres), l'initialisation est plus rapide et il est plus stable car il ne risque pas de d'overflow. Et je ne dessine plus de pixel blanc si c'est la première fois que je dessine sur un pixel puisqu'il était forcement blanc avant.
J'ai rajouté la gestion des viewport, c'est à dire que le rendu peu être dans une fenêtre définie par le programmeur et plus forcement sur l'écran entier. C'est utile si on utilise un ATH qui prend une partie de l'écran ou dans un menu pour afficher un objet 3D dans un coin facilement. Je n'ai pas testé, mais il est théoriquement possible d'afficher deux rendus différents en même temps, un écran splitté pour le multijoueur par exemple
Jour 7
Cliquez pour recouvrir
Il n'y a pas grand chose de nouveau visuellement donc je sors pas de vidéo, mais maintenant que j'ai fini d'opimisé le rendu des textures, j'ai optimisé la transformation des points dans l'espace 3D. J'ai gagné 71% de rapidité depuis le jour 6 ! Entre autres, j'ai précalculé les cos et sin, les coefficients de la matrice de rotation, le tout avec des nombre entiers.
Ce qui me prend du temps en ce moment c'est la structure de mes données, comment faire quelque chose d'efficace et qui permette d'écrire les modèle 3D rapidement à la main. Donc je gère des mini structures toutes faites, des triangles, des rectangles, et peut être d'autres plus tard comme des cylindres.
De plus, j'ai ajouté une fonctionalité qui permet d'appliquer une texture des deux cotés d'un triangles. Mais un problème est apparu, quand deux textures sont trop prochent l'une de l'autre, elle on tendance à se chevaucher, c'est à dire que la texture qui est derrière est affichée par dessus celle de devant...Ici on voit la texture blanche qui passe par dessus le mur de brique (frame 2 à 7)
Ça fait une journée que je cherche le problème. Il vient evidemment du z-buffer, mais la raison du problème est assez floue
Jour 8
Cliquez pour recouvrir
J'ai réussi à repérer l'origine de mon problème après plusieurs longues séances de documentation et de débeugage.
L'utilisation des matrices de projection perspective m'a permis de remapper la coordonnée z de mes points dans l'espace caméra, c'est à dire que maintenant leur coordonnée z à une valeur logique : elle est définie à 0 quand le point est sur le near clipping plane et à 1 sur le far clipping plane. Deux plans que je définie moi même.
Ceci m'a permis de mettre au jour une relation très vicieuse entre mes triangles que je n'avais pas remarqué jusqu'à présent. Je m'explique : dans ma phase de simplification, j'ai remarqué qu'une division était inutile puisque qu'elle se simplifiait dans une multiplication un peu plus loin. Dans le même genre que (A / B) x (C x B) = A x C
Cela n'a pas posé de problème de simplifier, j'ai obtenu exactement le même rendu.
Cependant, et c'est là que c'est vicieux, c'est que, plus tard, en rajoutant mon z-buffer (qui permet de connaître la distance entre mon point et la caméra afin d'afficher uniquement le plus proche), j'ai fabriqué une relation cachée entre mes triangles. En effet ils ne sont plus dessinés independamment puisqu'ils partagent le même z-buffer.
Et comme j'ai utilisé uniquement A et pas A / B et que B varie d'un triangle à l'autre, les données que je rentrais dans mon z-buffer étaient faussent.
Mais comme B varie peu, le problème ne s'est pas montré au premier abort, mais il était bien là !
Maintenant que je comprends l'origine du problème, je vais pouvoir le résoudre. En tout cas, c'était bien tordu et ça m'a bien pris la tête.
Désolé pour ce passage assez technique, mais expliquer l'origine du problème ne peut pas se faire sans
Jour 9
Cliquez pour recouvrir
Et voilà problème réglé ! Enfin, ça m'a pris une journée complète. (j'ai bien perdu 1h sur un copier coller raté et 3h parce que j'avais pas mon café...)
Maintenant le z-buffer est ultra propre ! je maitrise vraiment tout se qui passe. Un bon point pour la stabilité et éviter l'apparition d'artéfactes visuels
Jour 10
Cliquez pour recouvrir
J'ai commencé à modéliser des vrais objets pour voir ce que mon moteur a dans le ventre, et le résultat est renversant !
En définissant toutes les faces du moulin à vent, j'ai pu créer avec une relative simplicité un résultat plus que correct.
D'un point de vue technique, j'ai de nouveau optimisé depuis le jour précédent, en effet j'avais tout "désoptimisé" pour résoudre mon problème. Les fps en temps réel sont affichés dans le coin de l'écran, on voit que pour un modèle aussi riche (30 triangles) la vitesse du rendu est plus que convenable ce qui démontre que ce projet est viable. De plus il me reste quelques points à optimiser, sur le calcul des coordonnées de textures je peux grater pas mal, j'ai deux divisions que je peux transformer en une seule, et quelques autres idées. Donc j'ai encore de la marge, l'objectif étant qu'a terme le rendu soit le plus véloce possible
Sinon on peut remarquer que j'applique des textures sur des triangles dans des positions quelconques (le toit et les pales) et que j'ai ajouté l'option pour afficher une texture différentes de chaque côté d'un triangle (le toit vu par en dessous est noir) et j'ai rajouté un paramètre pour une bonne utilisation des textures sur les triangles (en effet le sprite est un carré à la base).
La prochaine étape est une réorganisation du code, j'ai deux fichiers que je vais réunir en un seul et je vais revoir comment le moteur recoit les objets à afficher. Dans la prochaine vidéo, les pales du moulin tourneront (enfin je l'espère bien )
Jour 11
Cliquer pour enrouler
Jour 11
Maintenant le moteur peut afficher plusieurs objets différents et les objets dynamiques ! J'ai revu totalement la façon de fournir les objets à afficher au moteur. Maintenant on peut afficher plusieurs objets simultanément, et on peut définir des mouvements pour les objets.
Jour 12
Cliquer pour enrouler
Jour 12
Après une grande pause, le projet reprend, en fonction de ma disponibilté, plus faible qu'avant, mais toujours présente
Comme je l'avais annoncé, la reprise de mes travaux portent sur l'optimisation, la résolution de bugs, et des changements internes pour les nouveautés à venir.
- nettoyage du fov, la valeur qui correspond à l'angle de vision, c'était un peu au pif avant.
- mise en const des variables de la map : les textures, les objets, les triangles et les rectangles.
- j'ai clarifié la précision des fixed (des nombres entiers utilisés comme des nombres à virgules) pour éviter les débordements, c'est surtout problématique pour les objets lointains, ou très proches car des variables s'approchent des limites d'un int.
Maintenant je suis certain qu'afficher un objet à la taille minimale (de taille 1) ne pose aucuns problèmes.
un cube de côté 1 :
un cube de coté 10, avec à sa droite le cube de coté 1.
(On voit le sol à partir de cette échelle, la distance entre les points est de 10)
L'histoire d'échelle est d'ailleurs très subjective, à combien correspond une taille de 10 si on veut la comparer au monde réel ? J'ai fait la proposition suivante : 1 = 10cm
- j'ai ajouté un repère 3D dans un coin de l'écran, c'est utile pour le debug.
- j'ai sorti la camera de la scène, c'est à dire que j'ai crée une classe juste pour la caméra.
- correction d'un problème dans le z-buffer (un tableau de la taille de l'écran enregistrant la distance des pixels par rapport à l'écran), j'avais un overflow, maintenant c'est tout propre !
- nettoyage divers dans le code
Jour 13
Cliquer pour enrouler
Jour 13
J'avance lentement, j'ai assez peu de disponibilité depuis 2 semaines...
MAIS ! Windmill avec encore et toujours
J'ai ajouté une fonctionnalité qui manquait depuis un long moment mais qui est pourtant essentielle : l'affichage des triangles devant le plan de clipping...
Explication :
Je parlais plus haut des plans de clipping, le proche et le lointain. Ces deux plans parralèles forment une pyramide avec à son sommet la caméra. Tout ce qui est entre ces plans est affiché. Le problème c'est si un point du triangle est avant le plan proche, jusqu'à présent si un des points avaient une coordonnée en z négative je n'affichais tout simplement pas le triangle.
Pour résoudre celà je tronque ou divise, en fonction des cas (1 ou 2 points devant le plan)
Desormais il n'y a presque plus de cas où des triangles disparaissent
Jour 14
Cliquer pour enrouler
Jour 14
Le problème de clipping que j'exposais en jour 13 est résolu !
Voici un petit rendu que comment c'était avant et comment c'est maintenant, le triangle (qui est la brique essentielle de tout le reste) est maintenant affichable avec beaucoup plus d'angle. Même quand on est presque dans le mur, il s'affiche correctement.
La texture se déforme légèrement quand on est vraiment proche, c'est dû aux erreurs d'arrondi.
Bonne vidéo
Jour 15
Cliquer pour enrouler
Jour 15
Une grosse surprise se prépare. Encore quelques soucis en train d'être corrigés et vous allez en prendre plein les yeux promis
En attendant cette semaine j'ai corrigé quelques bêtes erreurs comme un 1204 au lieu d'un 1024.
Changé un tas de chose en interne pour homogénéiser mon code
Les ajouts depuis le jour 13 :
Ajouté une ligne d'horizon (c'est tout bête mais ça rend bien mieux)
Changé les coordonnées des textures, maintenant on définit la taille en pixel en la texture, et la taille dans le monde.
Par exemple un texture de 32x32 peut correspondre à un carré de taille 20x20 (soit 2m carré), ou plus, ou moins c'est au choix.
- En affichant cette texture sur un rectangle de taille 40x40, la texture va automatiquement boucler.
- En renseignant 0x0 en taille réelle, la texture va s'étirer sur son support au lieu de boucler.
C'est très pratique pour répéter des motifs sans avoir à créer un autre rectangle, ou alors pour appliquer une texture sur n'importe quelle surface.
Actuellement j'ai un problème de serpent qui se mort la queue, clipping() doit être executé avant afficher() et afficher() doit être executé avant clipping() sinon j'ai des triangles qui s'effacent à certains moment. Je suis en train de corriger ça, mais c'est un peu casse tête
j'ai une grosse piste d'optimisation, si ça fonctionne j'estime à +30% de fps !
Jour 16
Cliquer pour enrouler
Jour 16
Désolé si tu es venu sur ce topic en pensant que j'ai enfin lancé LA démo ultime que j'ai vendu au jour 15.
Aujourd'hui c'est résolution de bugs.
J'ai résolu le problème du serpent qui se mort la queue en créant une fonction dédié plus rapide. Le problème était de savoir quelle face du triangle afficher, pour rentrer les dimensions de la textures dans les points.
Le problème que j'ai maintenant est une erreur d'overflow, lorsque la surface du triangle à afficher est trop importante, les nombres prennent des valeurs qui dépassent les limites d'un int (+- 2 milliards) et provoquent des bugs terribles sur l'affichage des textures.
J'ai bien ciblé le problème, je sais exactement quand, comment et pourquoi il se produit, je ne sais juste pas comment le résoudre simplement.
Après 3 soirées gachées à essayer de bricoler un truc, j'ai décidé de faire une autre fonction de clipping.
Cette fois l'objectif n'est pas découpe en plusieurs triangles ceux qui passent derrière la caméra (comme au jour14), mais découper pour n'avoir que les pixel qui sont à l'écran.
Le petit triangle s'affiche sans procblème, le grand à une aire qui overflow et bug visuellement
Jour 17
Cliquer pour enrouler
Jour 17
Le problème de clipping est résolu !
Pour récapituler, j'ai intégré du clipping sur l'axe devant-derrière pour couper les triangles passant derrière la caméra. Puis j'ai créé une nouvelle fonction pour découper les triangles sur l'axe haut-bas/droite-gauche, c'est à dire les bord de l'écran pour régler des problèmes d'overflow (cf jour 16). Le résultat est que le moteur est capable d'afficher des triangles dans n'importe quelle position, même la plus tordue sans bug, ou déformation du triangle.
A cette occasion j'ai revu toute la structure interne pour gérer l'affichage des objets. Je commence avec 1 triangle, et le clipping peux me renvoyer 1 à 10 triangles. Au lieu de gérer chaque point individuellement et avec des conditions à n'en plus finir, j'ai tout inséré dans un tableau que j'envoie à mes fonctions, et tout roule tout seul. c'est beaucoup plus léger et propre.
J'ai rajouté une synchronisation de la caméra avec le rendu. Le déplacement de la caméra (gestion du clavier) est appelé par un timer à interval régulier, ce qui peut tomber pendant le rendu d'une frame. Du coup je commence à dessiner un objet en regardant sous un angle X, la caméra se mets à jour et je termine de dessiner l'objet sous un angle Y. Ça provoquait des secousses et bugs visuels.
Résolution d'un bug sur le z-buffer.
Correction des quelques soucis avec le rendu du sol.
Un peu d'optimisation sur quelques variables.
Le moteur est super stable et il n'y a plus d'artéfactes visuels majeurs !!
C'est un vrai plaisir à regarder Pour ça rien de mieux qu'une vidéo !
Je teste ici sur émulateur et sur la machine, c'est quand même suffisament fluide, environ 10 fps, sachant que cette valeur est doublée avec de l'overcloacking
Jour 18
Cliquer pour enrouler
Jour 18
Windmill avance toujours, bien que la dernière vidéo soit impressionnante, il reste beaucoup de choses à faire.
Voici les nouveautés de la semaine :
- Réorganisation du code. J'ai ajouté une class Player et une class Engine avec un tas de petites modifications. Maintenant on peut créer son propre moteur physique et de gestion du jeu totalement indépendant du rendu 3D.
On peut même créer des moteurs physiques différents. Je suis en train d'en coder 2 :
>> Moteur de déplacement d'un personnage. En vue classique style FPS, on peut courrir, sauter, regarder dans toutes les direction (@Lephé : tout est fluide), interagir avec les objets (porte, trappe, ...)
>> Moteur de création de map. En vue de haut uniquement, on peut selectionner un objet, le déplacer, le tourner et observer ses coordonnées en temps réel. Une fois au bon endroit, il suffit d'écrire les coordonnées en dur dans le code. Très pratique pour créer une map.
- Ajout des billboard. Ce sont des sprites qui font toujours face au joueur. Il tournent sur l'axe vertical pour toujours faire face à la caméra. J'ai crée des arbres avec et des personnages avec.
- Ajout des masques alpha. Chaque texture doit avoir un sprite, et peut avoir un masque. La texture est dessinée que si le pixel du masque est noir.
- Ajout des sphere englobantes. Au chargement d'une nouvelle map, Windmill calcule automatiquement une sphere englobante pour chaque objet. Ceci permet de faire un test rapide. Si la sphere n'est pas à l'écran, aucune utilisté de vérifier si tous les triangles à l'intérieur sont à l'écran. Pour l'instant j'ai fais l'algo pour créer le spheres, il me reste l'algo pour savoir si elles sont à l'écran. J'ai mesuré les fps avant pour faire la comparaison.
- Ajout d'un tas de petites modifications.
- J'ai commencé à rédiger un manuel complet pour utiliser Windmill
Donc voilà, pas mal de nouveautés, c'est à chaque fois de plus en plus impressionnant
Jour 19
Le jour 19 arrive rapidement après le jour 18 car il y a une bonne nouveauté qui fera sans aucun doute plaisir à entendre !
J'ai terminé l'algo des sphères englobantes pour ne pas "chercher" à afficher les objets qui ne sont pas à l'écran.
Une petite explication plus détaillée
Lors du chargement de la map, un premier algorithme génère pour chaque objet une sphère qui englobe tous ses points. Lors du rendu, un second algorithme test pour chaque objet, si sa sphère est intersecte ou est incluse dans le champ de vision de la caméra. Si c'est le cas, on dessine l'objet, dans le cas contraire l'objet est ignoré.
Soit N le nombre de point d'un objet composant un objet, au lieu de calculer à chaque fois N points, on calcule au pire N+1 (N+centre de la sphère) ou au mieux 1 point. C'est très rentable !
Voici une animation représentant 2 sphères. La rouge est hors du champs de vision, la verte est dans le champs de vision.
Le gain en fps est d'autant plus important que le nombre d'objet hors du champs de vision est important. Donc impossible d'exprimer un gain fixe en fps.
Voici un comparatif :
Cas n°1, la map est peu chargée (celle en exterieur)
avant après
Tous les objets hors du champs de vision : 67 85
La moitié des objets dans le champs : 28 32
Cas n°1, la map est fort chargée (j'ai ajouté 15 moulins sur la map)
avant après
Tous les objets hors du champs de vision : 35 83
La moitié des objets dans le champs : 22 32
On remarque qu'avec cette méthode, les objets hors ne baisse pas (ou très peu) les performances.
En plus de cela, ça m'ouvre des opportunités pour de nouvelles foncionnalités
Jour 20
Une petite nouveauté dont je parlais précédemment : le trie des objets en fonction de la distance à la caméra.
Windmill trie en continue les objets pour afficher ceux qui sont les plus près en premier. En vérité Il trie les sphères englobantes.
Par exemple, j'ai placé 7 "murs" les uns derrière les autres.
Quand les objets sont dessinés du plus loin au plus proche : 10 fps
Quand les objets sont dessinés du plus proche au plus loin : 17 fps
Le trie permet garantir le second cas.
Cette fonctionnalité permet d'ajouter encore des objets sans perte majeure de performances
Jour 21
Bon... Ça fait un bon moment que je vous promets une démo pour le fameux et si attendu "jour 21".
Depuis le jour 20 il y a eu de gros changements, en interne comme en externe, visibles ou non visibles.
Je vais vous présenter l'ensemble de nouveautés en attendant la prochaine démo, qui sera pour le jour 22 du coup.
D'abord... Windmill gère les collisions avec le décors !!!
J'ai intégré un algorithme qui génèrement automatiquement au chargement de la carte des boites de collision à partir du modèle 3D. Donc le personnage bute sur les murs d'une maison, mais peut aussi monter sur une caisse. En effet le moteur de collision fonctionne dans les 3 dimensions.
Ensuite... Windmill intègre un algorithme de post traitement de l'image.
Cet algorithme détecte les contours des objets et les dessine en noir. Ceci permet de mieux apprecier les volumes.
Et surtout, il simplifie la création des modèle 3D (je développerai pourquoi plus tard)
Après... Windmill gère les "décorations".
Il s'agit d'objets que l'on peut poser en superposition sur les murs pour ajouter du détail. L'objectif est encore une fois de simplifier (énormément) la création des modèles 3D. Avant, pour ajouter une porte sur un mur, il fallait découper le mur en plusieurs parties pour éviter les bugs d'affichage. Maintenant, il suffit de placer la porte où on veut par dessus un unique mur. Il reste néanmoins quelques petits bugs d'affichage avec cette méthode, mais elle fonctionne 90% du temps.
Enfin... beaucoup de remaniement en interne
J'ai nettoyé l'ensemble du code. Il y a maintenant une gestion par scene facilitant la gestion des différentes parties du jeu : l'écran titre est une scene, la map est une autre scene, le menu de sauvegarde sera une scene...
Modification de l'étalement des textures sur les objets
Ajout d'un moteur de création rapide de map, il permet de sélectionner, déplacer et tourner un objet en affichant en direct ces coordonnées. C'est une scene de debug extremment utile pour agencer les objets sur la carte.
Réunion de toutes les variables à sauvegarder dans une même classe, en prévision de la sauvegarde/chargement de partie.
Diverses améliorations
Le jeu tourne forcement moins vite avec l'ajout de ces nouvelles fonctionnalités. Le moteur physique n'influe presque pas, par contre le post traitement diminue entre 5 et 15% les fps. Je dispose cependant toujours de pistes d'optimisation, mais elle ne seront pas fabuleuses non plus. Quoi qu'il en soit, Windmill est toujours parfaitement jouable !
Jour 22 : 22 mars 2019
Bon, je suis malheureux de plus trop bosser dessus, du coup je vous donne le dernier g1a que j'ai compilé !!!
Je souhaitais faire un effet encore plus Wahou en ajoutant encore quelques trucs mais je me rends compte qu'il ne sortira jamais sinon.
Et vu le nombre de fois que je vois passer le Windmill je ressens l'impatience des gens
Je vous laisse vous balader dans ce village virtuel
La grosse nouveauté est, je le rappelle, le moteur physique, essayez de monter sur les bottes de foin ou de sauter par dessus les barrières
Jour 23 : 01 mai 2019
Je commence à en voir de le bout de cette documentation !
J'y ai consacré de nombreuses heures. C'est pour moi un point essentiel pour comprendre comment créer un environnement en 3D à travers Windmill.
De plus, elle n'arrive que tardivement car il fallait s'assurer que les bases du moteurs soit stables et qu'il n'y ait pas de revirement majeur dans la façon de créer une carte. Sinon cela aurait été du travail pour presque rien.
Maintenant c'est assez modulaire pour que l'ajout de nouvelles fonctionnalités se fasse de façon transparente pour vous, au même titre qu'une mise à jour de logiciel.
Vous trouverez ci-joint la documentation dans sa version 3.0. A priori elle devrait suffire pour couvrir les bases de la création d'une carte sous Windmill.
Je posterai les sources par la suite, je vais prendre un peu de temps pour clarifier quelques point au niveau du code
Jour 24 : 02 septembre 2021
Après une longue période sans nouvelles officielles je vous annonce officiellement que Windmill tourne avec les derniers (et même un peu plus) standards de compilation : Gint & C++
Il m'aura fallu bien plus de temps que je ne l'imaginais pour installer Gint, comprendre son fonctionnement, comprendre le fonctionnement du terminal, adapter le code du jeu... J'avais un peu avancé sur l'adaptation en y allant cran par cran jusqu'à ce le C++ soit un obstacle pour continuer.
Lephénixnoir ce sera bien démené mais nous y sommes arrivé !
Que du texte, pas grand chose à montrer, hormis un rendu pas très joli.
Il faut que je refasse une passe sur le code pour voir ce qui cloche car les textures ne sont pas sur bien rendu, il doit y avoir quelques erreur de calculs de ci de là.
Et il faut aussi que je regarde pourquoi le jeu crach dès que je regarde trop à droite ou à gauche.
J'ai a nouveau la main pour avancer comme il se doit. Des nouvelles prochainement sans doute !
Jour 25 : 12 novembre 2021
Bonjour à tous !
La dernière vidéo de Sebastian Lague (I Tried Creating a Game Using Real-world Geographic Data) détaille à 24min moment comment générer des ombres pour un rendu 3D. Je pensais que c'était hyper complexe comme sujet mais en fait c'est assez simple. En fouillant un peu je suis tombé sur une méthode encore plus simple, qui parait trivial une fois dites mais il fallait penser Planar Shadow. J'ai bien l'intention d'implémenter ça
J'ai encore du mal avec le passage sous Gint, avec des bugs dont j'ai du mal à me dépatouiller.
Autre chose, je vais désormais avoir une 90E, donc un truc bien plus récent que ma calto SH3, et avec la couleur, je pourrai faire des tests sur le portage pour cette plateforme ! On verra ce que donnent les performances.
J'ai encore un autre projet, c'est de créer un importeur de fichier obj. L'obj est un format 3D simple à générer, et aussi simple à parser. Le but est de simplifier la création des modèles 3D en passant par un logiciel 3D plutôt que créer à la fin la liste des triangle, c'est fastidieux. Ici une maison crée sous Fusion 360 en 1 minute. On voit le maillage avec les 16 triangles.
Jour 26 : 5 janvier 2022
Bonne année à tous, me revoici avec des nouveautés concernant Windmill.
Les nouvelles fonctions que je vous décrivais dans le "jour 25" et surtout les ombres et le passage en obj nécessitent une refonte du système de clipping décrit dans le jour 14.
Ce qui change ? Je passe d'un clipping 2D à un clipping 3D.
En somme, je tronque les triangles du modèle en étant encore dans l'espace 3D et plus dans l'espace 2D, c'est à dire un cran avant.
C'était un peu de boulot mais ça me permet désormais d'avancer.
Je vous présente une petite vidéo qui illustre le clipping d'un triangle par rapport au frustrum (la pyramide de vision de la caméra). Le chiffre indique le nombre de trinagle résultant du découpage
Jour 27 : 26 octobre 2022
Bonjour à tous,
La programmation sur calculatrice est chronophage et je n'ai plus de temps perso à y accorder.
J'ai des envies pour ce projet, et pas des petites : passer à la couleur, mettre en place les ombres, terminer l'import au format stl. Ça me motive à fond. Dans le même temps côté boulot, j'utilise le C# et dès que je replonge dans le C ou C++ c'est un retour en arrière qui me frustre. Je passe plus de temps à débugger Windmill qu'à faire ce qui me plait. Je n'avance pas.
J'ai finalement vendu ma 90E avant qu'elle ne prenne la poussière, que les touches se mettent à gripper et que les araignées y fassent leur nid.
Pour être honnête, je ne pense pas remettre un pied dans le projet.
Windmill a souvent été pris en exemple pour l'exploit technique et son potentiel, et je n'en suis pas peu fière. Je ne pense pas qu'une autre personne de la communauté (fr ou non) soit allé aussi loin dans la création d'un vrai moteur 3D pour calculatrice.
C'est pourquoi ce projet doit continuer à vivre et ne doit pas tomber dans l'oubli.
Ainsi je partage à la communauté les sources du projet aujourd'hui.
C'est brut, tout n'est pas commenté, si vous souhaitez reprendre le projet, bon courage, mais merci si vous vous lancez !
Peut être que si le résultat de la multiplication rentre dans un short par exemple, il s'arrête et remplie le reste de 0. Peut être une gestion des signes aussi. Je ne sais pas.
Dark Storm, on parle uniquement de multiplication entière. La commande MUL.L en assembleur indique
" cycles : 2 (to 5)"
Merci d'avoir fait le point. Ce que tu as dit ne remet pas en cause ce que je racontais plus tôt, mais je crois qu'il faut que je détaille un peu plus, aussi. En particulier, je voudrais répondre à cette remarque :
Ninestars a écrit : J'insiste sur le fait que le SEUL ET UNIQUE moyen de savoir si un point est visible est de transformer les coordonnées du point en question dans le repère de la caméra !
Il n'y a pas de moyen plus rapide. Minecraft ou pas
Je suis en train de prétendre tout pile le contraire. Pas mal, hein ? Je pense que tu oublies des possibilités quand tu dis ça ; voilà pourquoi.
Imagine que tu te balades dans la map que Darks a représentée dans son message (merci Darks !). C'est en 2D disons, un monde plat comme on en verrait avec du mode 7 -- il n'y a pas de hauteur. Ton objectif à toi, c'est d'afficher toutes les cases vertes... et mon objectif à moi, c'est de le faire sans m'intéresser aux cases qui sont autour. Mon point de vue, c'est « le monde est infini », donc je ne veux surtout pas avoir à tester toutes les cases du monde. Je veux donc avoir les vertes à disposition immédiate, sans avoir à calculer quoi que ce soit au sujet des blocs... et c'est possible.
Pour cela, il me suffit de stockef le monde dans un tableau en 2D et de parcourir de bas en haut les lignes qui sont devant la caméra ; pour chacune de ces lignes, je sélectionne les cellules qui seront visibles -- en nombre proportionnel au nombre de lignes que j'ai déjà parcouru. Un calcul sur l'angle de vision me donnera combien de cellules je dois prendre à chaque ligne, et je sais que le résultat sera centré par rapport à la verticale. Deux boucles régleront aisément le problème dans ce cas très simple.
Comme tu peux le voir, l'approche que j'ai utilisée pour cet exemple est très différente de la tienne ; la différence fondamentale étant que la structure de données que j'ai utilisée, à savoir le tableau 2D, possède une méthode d'accès rapide qui a du sens du point de vue du monde virtuel. La première coordonnée est la position en x, la seconde en y. Je peux accéder à un point de l'espace en temps constant, et je peux même faire mieux : je peux accéder aux zones adjacentes via une simple modification des indices. En un mot : la structure de données utilisée décrit par essence la notion d'adjacence dans l'espace. Voilà ce que je cherche depuis le tout début (mon message est long mais c'est ça qu'il faut retenir !).
Pour enfoncer un peu le clou sur la clarté, je prends un exemple simple : un jeu en 2D en vue de dessus qui possède une map, stockée dans un tableau 2D, et un ensemble d'ennemis mobiles, se déplaçant sur la map en même temps que le joueur, stockés dans une liste. Les collisions entre le joueur et la map sont simples à réaliser puisqu'il suffit d'observer les cases adjacentes au joueur (ce qui est rendu possible par la notion d'adjacence portée par le tableau 2D), mais les collisions entre le joueur et les ennemis sont très désoptimisées, car il faut parcourir la liste de tous les ennemis pour trouver ceux qui sont proches ! Quand il y aura beaucoup d'ennemis, ce sera fatalement gênant au niveau de la performance (bon après faut quantifier le « beaucoup » hein !).
Je pense que tu vois où je veux en venir, en particulier quand j'ai posé cette question :
Ninestars a écrit : Sans vouloir spoiler un peu tout, t'as quel type de structure pour la représentation de ton espace par ailleurs ?
Je voulais au fond savoir si tu disposais de cet accès rapide à des zones de l'espace en particulier. Le problème est simple : soit tu y as accès, et tu peux itérer plus ou moins comme je l'ai fait sur des zones précises peu importe la taille totale de la map, soit tu ne peux pas, et tu es condamné à utiliser ta méthode et à observer en permanence des objets qui sont à l'autre bout de la map. Bien sûr, je comprends que ma « solution » d'itération est d'une sainte horreur à implémenter (les intersections entre des carrés et un cône orienté avec deux angles, berk !), et je suis persuadé que ce n'est pas une bonne idée de s'en servir dans un cas général -- mais quand on est dans Minecraft, un monde simpliste où il y a beaucoup de faces à afficher, ou quand on a des très grandes maps, on veut peut-être s'en servir.
Voilà, c'était l'essence de ma réflexion sur la question. Surtout quelque chose de théorique, pas forcément pour soumettre l'idée à implémentation. Quant aux quadtrees, la remarque est simple : les quadtrees possèdent la notion d'adjacence, tout comme les tableaux à plusieurs dimensions -- et contrairement aux listes.
---
Pour ce qui est de la multiplication des entiers, le problème est plus simple (euh, non, plus compliqué en fait é_é ) que ce que vous proposiez. Je dois d'abord me corriger : la multiplications des entiers se fait en 1 à 3 cycles, contrairement à ce que j'avais prétendu (2 à 5 cycles), qui est la durée de la multiplication 64 bits (celle que je prends en général pour référence).
Non Zezombye, cela n'a rien à voir avec la difficulté du calcul -- le processeur n'est pas humain, et de la même manière qu'il additionne toujours 32 bits même quand il fait 1 + 1, il multipliera toujours de la même manière peu importe quels sont ses opérandes. Ici bien sûr, on ne multiplie que des entiers donc le type de données ne peut pas expliquer ça (note pour Darks : le FPU multiplie les flottants dans le temps d'un cycle proco, ce qui justifie bien ce que je vais dire ensuite sur les considérations électroniques).
C'est essentiellement un problème d'électronique, en fait. Je me permets de déborder un peu sur le pipeline du proco au passage. L'exécution d'une instruction, quelle qu'elle soit, prend au moins 5 cycles : IF (Instruction Fetch), ID (Instruction Decode), EX (Execution), MA (Memory Access) et WB (Write Back). Ce qui permet d'exécuter une addition « en un cycle » c'est le fait que le processeur est capable d'effectuer toutes ces actions en même temps -- pour 5 instructions différentes.
--------1---2---3---4---5---6---7---8---9--> time
ins. 0 IF ID EX MA WB
ins. 1 IF ID EX MA WB
ins. 2 IF ID EX MA WB
ins. 3 IF ID EX MA WB
ins. 4 IF ID EX MA WB
Sur le schéma précédent, vous pouvoir constater qu'à l'instant 5, le processeur exécute 5 stages en même temps (mais pour des instructions différentes, hein !). Ce fonctionnement permet de boucler en moyenne une instruction par cycle dans le flot d'exécution (je masque les détails gores comme la contention ou les prédiction de branchements, mais sachez que la durée d'exécution de l'instruction est définie comme la différence entre les instants d'exécution des phases EX). C'est pour ça qu'on dit que l'instruction add rm, rn, comme la plupart des autres, s'exécute en un cycle.
Il faut savoir que l'exécution du stage EX est le moment où sont faits les calculs. C'est à ce moment que l'ALU est mise à la disposition de l'instruction pour ajouter deux nombres, pré-décrémenter un pointeur avant l'accès à la mémoire, ou effectuer des opérations logiques. Cette phase prend toujours un cycle, mais ce n'est pas l'ALU qui gère la multiplication : c'est le multiplieur. Et si on regarde le pipeline des instructions de multiplication sur 32 bits, ça ressemble à ça :
--------1---2---3---4---5---6---7---8---9--> time
multi. IF ID EX MA MA mm mm mm
ins. 1 IF -- ID EX MA WB
ins. 2 IF ID EX MA WB
(Pour ceux qui regarderaient le problème en détail, il y a ici une contention mais on l'oubliera). Vous voyez qu'il y a deux cycles d'accès mémoire (ils interfacent avec le multiplieur) et 3 phases « mm » à la fin de l'instruction ; ce sont les opérations du multiplieur. Le fondement du problème est là (c'est le moment d'être attentif !) : le mutiplieur peut tourner tout seul dans le fond, et l'exécution des instructions suivantes peut continuer pendant le calcul.
De base, c'est ce qu'il se passe ; et alors le temps d'exécution est de 1 cycle seulement. Mais les choses peuvent se compliquer. En particulier, l'instruction qui suit peut tenter d'accéder également au multiplieur, pour accéder aux résultats ou pour effectuer un autre calcul. À ce moment, elle doit attendre la fin du calcul, portant la durée d'exécution à 3 cycles. Si c'est la deuxième instruction après le premier accès au multiplier, on est à 2 cycles ; je pense que vous avez compris comment va la suite.
C'est pareil pour les autres instructions de multiplication. Pour plus d'informations, vous pouvez vous référer au manuel du SH3
D'accord je vois où tu voulais en venir, et ça prend tout son sens, ce que tu racontes est très clair.
A l'époque où je travaillais sur mon projet Age of Empire, j'avais réfléchi un long moment pour trouver comment enregistrer mes données aussi.
Il y a toujours ce dilemme entre une spacialisation des données ou un listage des données. Est-ce qu'il est plus interressant d'avoir un acces rapide à mes données par leurs coordonnées ?
J'avais choisi la deuxième méthode. J'avais une liste avec tous les objets présents sur la carte. Bien que ce modèle ne semble cohérent avec une map composées de tiles, il y avait plus d'avantages. Je n'ai pas envie de rentrer dans les détails puisque ça serait long et le sujet n'est pas là.
Reparlons plutôt du moteur 3D
Utiliser une spacialisation des données dans mon cas n'est pas la bonne solution.
Premièrement il me faut une matrice tridimensionnelle, c'est lourd, très lourd, d'autant plus en 3D, et ensuite l'espace que je défini entre les points de la grille doivent être assez prochent pour pouvoir afficher des formes complexes, donc encore plus de points, donc encore plus lourd !
Ensuite la majorité de l'espace est vide, c'est une perte de mémoire inutile.
Et pour finir je ne fais pas de recherche par coordonnées, je n'ai pas besoin de savoir si une face est à coté d'une autre.
Si on pourrait théoriser ça, je dirais qu'il y a un compromis entre la mémoire utilisée et la puissance de calcul.
Je suis persuadé que dans minecraft (j'ai cherché mais je n'ai rien trouvé) il utilise ton principe au niveau des chunks pour savoir lesquels afficher. Dans ce cas oui puisque que les chunks doivent être enregistrés dans une matrice 2D.
Merci pour l'explication de la multiplication, c'est très clair.
Si je peux me permettre, ton problème concernant le niveau de précision (points très proches) et les espaces vides est la raison d'être des quadtrees. Ces machins-là sont adaptés pour avoir une précision variable en différents points de l'espace
Bon après je pense bien que dans ton cas il est plus intéressant de garder des listes. Tu pourrais toujours tenter d'ordonner un peu ta liste pour reproduire cette adjacence mais ce serait un peu compliqué. Ce n'est peut-être pas pertinent.
En soit cela ne me servirait à rien. Ce qui pourrait être interresant par contre c'est que mes faces soient triées par rapport à la distance par rapport à la caméra.
Le pire cas, c'est que mes triangles soient du plus éloigné au plus proche puisque je modifie les mêmes pixels plusieurs fois.
Ajouté le 18/11/2016 à 00:53 :
Jour 10
J'ai commencé à modéliser des vrais objets pour voir ce que mon moteur a dans le ventre, et le résultat est renversant !
En définissant toutes les faces du moulin à vent, j'ai pu créer avec une relative simplicité un résultat plus que correct.
D'un point de vue technique, j'ai de nouveau optimisé depuis le jour précédent, en effet j'avais tout "désoptimisé" pour résoudre mon problème. Les fps en temps réel sont affichés dans le coin de l'écran, on voit que pour un modèle aussi riche (30 triangles) la vitesse du rendu est plus que convenable ce qui démontre que ce projet est viable. De plus il me reste quelques points à optimiser, sur le calcul des coordonnées de textures je peux grater pas mal, j'ai deux divisions que je peux transformer en une seule, et quelques autres idées. Donc j'ai encore de la marge, l'objectif étant qu'a terme le rendu soit le plus véloce possible
Sinon on peut remarquer que j'applique des textures sur des triangles dans des positions quelconques (le toit et les pales) et que j'ai ajouté l'option pour afficher une texture différentes de chaque côté d'un triangle (le toit vu par en dessous est noir) et j'ai rajouté un paramètre pour une bonne utilisation des textures sur les triangles (en effet le sprite est un carré à la base).
La prochaine étape est une réorganisation du code, j'ai deux fichiers que je vais réunir en un seul et je vais revoir comment le moteur recoit les objets à afficher. Dans la prochaine vidéo, les pales du moulin tourneront (enfin je l'espère bien )
D'ailleurs j'ai un problème plus propre au language C/C++
J'ai copié ce bout de code depuis MonochromeLib dans mon fichier cpp
static int SysCallCode[] = {0xD201422B,0x60F20000,0x80010070};
static int (*SysCall)( int R4, int R5, int R6, int R7, int FNo ) = (void*)&SysCallCode;
char* Scene::get_vram_adress()
{
return (char*)((*SysCall)(0, 0, 0, 0, 309));
}
Mais le compilateur n'aime pas et me dit
A value of type "void *" cannot be used to initialize an entity of type "int (*)(int, int, int, int, int)"
Qu'est-ce qui ne va pas ?
Je précise que j'ai importé (je suppose) la lib où sont définies R4, R5 ...
C'est le cast de pointeur qui n'est pas apprécié. Précisément ici :
static int (*SysCall)( int R4, int R5, int R6, int R7, int FNo ) = (void*)&SysCallCode;
Comme justement relevé par le compilateur, la variable « SysCall » est de type int (*)(int, int, int, int, int) mais tu l'initialises avec un pointeur de type void *, à savoir « (void*)&SysCallCode ».
Le compilateur C caste silencieusement, mais si tu as besoin d'être explicite tu peux toujours user de la syntaxe suivante :
static int (*SysCall)( int R4, int R5, int R6, int R7, int FNo ) = (int (*)(int, int, int, int, int))&SysCallCode;
Cependant, il me semble plus intelligent d'essayer avant de placer cette ligne et les définitions qui vont avec dans un bloc extern "C", au moins pour d'autres raisons.
Par ailleurs R4, R5, etc. ne sont définies nulle part et encore moins dans une lib (et surtout pas dans la lib standard !), c'est juste une indication de nom facultative. Toutes les déclarations suivantes sont équivalentes :
int (*syscall)(int r4, int r5, int r6, int r7, int function);
int (*syscall)(int pomme, int banane, int orange, int citron, int bouton);
int (*syscall)(int, int, int, int, int);
C'est vraiment le nombre et le type des arguments qui compte.
Excellent ! J'adore ! Quel est le fps au plus bas que tu as pu constater ? Y a t-il encore des axes d'amélioration possible ?
As-tu l'intention d'écrire un jeu utilisant ton moteur à l'avenir ?
Bon courage.
Non pas de quaternions, j'utilise les matrices de rotations. Les quaternions sont utiles pour éviter le phénomène "gimbal lock", ici comme je veux une simple "vue fps", si je peux appeller ça comme ça, je n'ai pas ce problème.
En plus les quaternions necessitent un poil plus de calcul qu'avec les matrices
Je n'ajouterai pas les ombres, ça prend beaucoup de ressources et même avec les nuances de gris, je ne pense pas que l'effet rende bien. Par contre j'ai quelques autres idées pour utiliser les nuances de gris.
Au plus bas, c'est à dire quand je suis au plus proche de ma texture je suis à 7 fps.
Oui il y a quelques pistes, elles portent principalement sur l'affichage des textures. Comme c'est le plus gourmand, c'est là dessus que je joue principalement. Il y a plusieurs pistes d'améliorations, particulièrement une très prométeuse qui consiste à afficher d'une traite mes rectangles sans les diviser en deux triangles. Aussi une simplification qui m'évite plusieurs multiplications dans ma boucle principale pour afficher les textures. J'ai déjà fait quelques essais là dessus mais je n'ai pas réussi, j'ai des erreurs que je n'arrive pas à identifier mais je sens que je suis pas loin
Hey, si tu es désespéré en termes d'optimisation je peux te crafter un produit matriciel optimisé.
N'hésite pas si tu repères des schémas récurrents (a * b + c), des trucs comme ça, c'est optimisable au niveau du proco. Btw si tu veux utiliser le gris faudra passer à gcc, ce qui permettra de faire ce genre d'optimisations plus facilement.
Une des choses que le processeur sait bien faire est sommer des produits de deux termes. Le produit matriciel en est un exemple majestueux, mais ce que tu fais là est pas mal aussi. On peut déjà probablement gagner sur les trois parties sommes/produits (l'idéal ce serait que les triplets (tx0, tx1, tx2) soient alignés comme des tableaux de trois éléments).
Pour la division, si tu manques de précision, il faut définitivement passer le produit par z_div (après calcul de l'inverse) en 64 bits. Faut que j'y réfléchisse mais à vue de nez c'est un gain conséquent.
Si tu normalises des vecteurs tu as sans doute envie d'utiliser la méthode magique de calcul de l'inverse de la racine carrée en flottant.
lephenixnoir a écrit : sommer des produits de deux termes
Genre A * B + C * D ?
Parce que dans 90% des cas v0tx = v0ty = 0 donc je peux trouver le moyen de retirer les produits w0 * t0x et w0 * t0y.
En l'état actuel je les laisse puisque je gagne pas grand chose à les enlever et ça marche pour les 10% restant.
Je les définis les uns après les autres au début de la fonction, ça ne garanti pas un alignement mémoire mais on peut les mettre dans un tableau.
Effectivement, c'est sur le passage des deux divisions en 1 seule + deux multiplications qu'on a le plus de marge !
L'opération précise c'est Σ a_n * b_n. Ce truc-là est tellement courant que le proco a des instructions pour le faire facilement. Donc pas besoin de virer des termes, en fait plus il y en a et plus on gagne. Ça reste léger sur trois termes comme ça mais sur un produit matriciel c'est peut-être important (j'essaierai de te quantifier ça).
Finalement, je suis surpris de ne pas y avoir pensé plus tôt, mais le SDK n'est pas ton ami en termes d'optimisation.
Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd
)
)
J'ai encore optimisé mon algorithme pour appliquer les textures, j'étais passé à côté de quelque chose d'énorme, résultat j'ai pu simplifier encore mes calculs pour gagner 35% de performances. Je suis passé de 10 décalages de bit, 17 mults, 9 additions à 7 décalages, 12 mults et 10 additions.
Ici on voit la texture blanche qui passe par dessus le mur de brique (frame 2 à 7)
Ajouté une ligne d'horizon (c'est tout bête mais ça rend bien mieux)
Il reste néanmoins quelques petits bugs d'affichage avec cette méthode, mais elle fonctionne 90% du temps.
Citer : Posté le 10/11/2016 21:13 | #
Peut être que si le résultat de la multiplication rentre dans un short par exemple, il s'arrête et remplie le reste de 0. Peut être une gestion des signes aussi. Je ne sais pas.
Dark Storm, on parle uniquement de multiplication entière. La commande MUL.L en assembleur indique
" cycles : 2 (to 5)"
Citer : Posté le 10/11/2016 21:19 | #
Merci d'avoir fait le point. Ce que tu as dit ne remet pas en cause ce que je racontais plus tôt, mais je crois qu'il faut que je détaille un peu plus, aussi.
J'insiste sur le fait que le SEUL ET UNIQUE moyen de savoir si un point est visible est de transformer les coordonnées du point en question dans le repère de la caméra !
Il n'y a pas de moyen plus rapide. Minecraft ou pas
Je suis en train de prétendre tout pile le contraire. Pas mal, hein ?
Imagine que tu te balades dans la map que Darks a représentée dans son message (merci Darks !). C'est en 2D disons, un monde plat comme on en verrait avec du mode 7 -- il n'y a pas de hauteur. Ton objectif à toi, c'est d'afficher toutes les cases vertes... et mon objectif à moi, c'est de le faire sans m'intéresser aux cases qui sont autour. Mon point de vue, c'est « le monde est infini », donc je ne veux surtout pas avoir à tester toutes les cases du monde. Je veux donc avoir les vertes à disposition immédiate, sans avoir à calculer quoi que ce soit au sujet des blocs... et c'est possible.
Pour cela, il me suffit de stockef le monde dans un tableau en 2D et de parcourir de bas en haut les lignes qui sont devant la caméra ; pour chacune de ces lignes, je sélectionne les cellules qui seront visibles -- en nombre proportionnel au nombre de lignes que j'ai déjà parcouru. Un calcul sur l'angle de vision me donnera combien de cellules je dois prendre à chaque ligne, et je sais que le résultat sera centré par rapport à la verticale. Deux boucles régleront aisément le problème dans ce cas très simple.
Comme tu peux le voir, l'approche que j'ai utilisée pour cet exemple est très différente de la tienne ; la différence fondamentale étant que la structure de données que j'ai utilisée, à savoir le tableau 2D, possède une méthode d'accès rapide qui a du sens du point de vue du monde virtuel. La première coordonnée est la position en x, la seconde en y. Je peux accéder à un point de l'espace en temps constant, et je peux même faire mieux : je peux accéder aux zones adjacentes via une simple modification des indices. En un mot : la structure de données utilisée décrit par essence la notion d'adjacence dans l'espace. Voilà ce que je cherche depuis le tout début (mon message est long mais c'est ça qu'il faut retenir !).
Pour enfoncer un peu le clou sur la clarté, je prends un exemple simple : un jeu en 2D en vue de dessus qui possède une map, stockée dans un tableau 2D, et un ensemble d'ennemis mobiles, se déplaçant sur la map en même temps que le joueur, stockés dans une liste. Les collisions entre le joueur et la map sont simples à réaliser puisqu'il suffit d'observer les cases adjacentes au joueur (ce qui est rendu possible par la notion d'adjacence portée par le tableau 2D), mais les collisions entre le joueur et les ennemis sont très désoptimisées, car il faut parcourir la liste de tous les ennemis pour trouver ceux qui sont proches ! Quand il y aura beaucoup d'ennemis, ce sera fatalement gênant au niveau de la performance (bon après faut quantifier le « beaucoup » hein !).
Je pense que tu vois où je veux en venir, en particulier quand j'ai posé cette question :
Sans vouloir spoiler un peu tout, t'as quel type de structure pour la représentation de ton espace par ailleurs ?
Je voulais au fond savoir si tu disposais de cet accès rapide à des zones de l'espace en particulier. Le problème est simple : soit tu y as accès, et tu peux itérer plus ou moins comme je l'ai fait sur des zones précises peu importe la taille totale de la map, soit tu ne peux pas, et tu es condamné à utiliser ta méthode et à observer en permanence des objets qui sont à l'autre bout de la map. Bien sûr, je comprends que ma « solution » d'itération est d'une sainte horreur à implémenter (les intersections entre des carrés et un cône orienté avec deux angles, berk !), et je suis persuadé que ce n'est pas une bonne idée de s'en servir dans un cas général -- mais quand on est dans Minecraft, un monde simpliste où il y a beaucoup de faces à afficher, ou quand on a des très grandes maps, on veut peut-être s'en servir.
Voilà, c'était l'essence de ma réflexion sur la question. Surtout quelque chose de théorique, pas forcément pour soumettre l'idée à implémentation. Quant aux quadtrees, la remarque est simple : les quadtrees possèdent la notion d'adjacence, tout comme les tableaux à plusieurs dimensions -- et contrairement aux listes.
---
Pour ce qui est de la multiplication des entiers, le problème est plus simple (euh, non, plus compliqué en fait é_é ) que ce que vous proposiez. Je dois d'abord me corriger : la multiplications des entiers se fait en 1 à 3 cycles, contrairement à ce que j'avais prétendu (2 à 5 cycles), qui est la durée de la multiplication 64 bits (celle que je prends en général pour référence).
Non Zezombye, cela n'a rien à voir avec la difficulté du calcul -- le processeur n'est pas humain, et de la même manière qu'il additionne toujours 32 bits même quand il fait 1 + 1, il multipliera toujours de la même manière peu importe quels sont ses opérandes. Ici bien sûr, on ne multiplie que des entiers donc le type de données ne peut pas expliquer ça (note pour Darks : le FPU multiplie les flottants dans le temps d'un cycle proco, ce qui justifie bien ce que je vais dire ensuite sur les considérations électroniques).
C'est essentiellement un problème d'électronique, en fait. Je me permets de déborder un peu sur le pipeline du proco au passage. L'exécution d'une instruction, quelle qu'elle soit, prend au moins 5 cycles : IF (Instruction Fetch), ID (Instruction Decode), EX (Execution), MA (Memory Access) et WB (Write Back). Ce qui permet d'exécuter une addition « en un cycle » c'est le fait que le processeur est capable d'effectuer toutes ces actions en même temps -- pour 5 instructions différentes.
ins. 0 IF ID EX MA WB
ins. 1 IF ID EX MA WB
ins. 2 IF ID EX MA WB
ins. 3 IF ID EX MA WB
ins. 4 IF ID EX MA WB
Sur le schéma précédent, vous pouvoir constater qu'à l'instant 5, le processeur exécute 5 stages en même temps (mais pour des instructions différentes, hein !). Ce fonctionnement permet de boucler en moyenne une instruction par cycle dans le flot d'exécution (je masque les détails gores comme la contention ou les prédiction de branchements, mais sachez que la durée d'exécution de l'instruction est définie comme la différence entre les instants d'exécution des phases EX). C'est pour ça qu'on dit que l'instruction add rm, rn, comme la plupart des autres, s'exécute en un cycle.
Il faut savoir que l'exécution du stage EX est le moment où sont faits les calculs. C'est à ce moment que l'ALU est mise à la disposition de l'instruction pour ajouter deux nombres, pré-décrémenter un pointeur avant l'accès à la mémoire, ou effectuer des opérations logiques. Cette phase prend toujours un cycle, mais ce n'est pas l'ALU qui gère la multiplication : c'est le multiplieur. Et si on regarde le pipeline des instructions de multiplication sur 32 bits, ça ressemble à ça :
multi. IF ID EX MA MA mm mm mm
ins. 1 IF -- ID EX MA WB
ins. 2 IF ID EX MA WB
(Pour ceux qui regarderaient le problème en détail, il y a ici une contention mais on l'oubliera). Vous voyez qu'il y a deux cycles d'accès mémoire (ils interfacent avec le multiplieur) et 3 phases « mm » à la fin de l'instruction ; ce sont les opérations du multiplieur. Le fondement du problème est là (c'est le moment d'être attentif !) : le mutiplieur peut tourner tout seul dans le fond, et l'exécution des instructions suivantes peut continuer pendant le calcul.
De base, c'est ce qu'il se passe ; et alors le temps d'exécution est de 1 cycle seulement. Mais les choses peuvent se compliquer. En particulier, l'instruction qui suit peut tenter d'accéder également au multiplieur, pour accéder aux résultats ou pour effectuer un autre calcul. À ce moment, elle doit attendre la fin du calcul, portant la durée d'exécution à 3 cycles. Si c'est la deuxième instruction après le premier accès au multiplier, on est à 2 cycles ; je pense que vous avez compris comment va la suite.
C'est pareil pour les autres instructions de multiplication. Pour plus d'informations, vous pouvez vous référer au manuel du SH3
Citer : Posté le 10/11/2016 22:23 | #
D'accord je vois où tu voulais en venir, et ça prend tout son sens, ce que tu racontes est très clair.
A l'époque où je travaillais sur mon projet Age of Empire, j'avais réfléchi un long moment pour trouver comment enregistrer mes données aussi.
Il y a toujours ce dilemme entre une spacialisation des données ou un listage des données. Est-ce qu'il est plus interressant d'avoir un acces rapide à mes données par leurs coordonnées ?
J'avais choisi la deuxième méthode. J'avais une liste avec tous les objets présents sur la carte. Bien que ce modèle ne semble cohérent avec une map composées de tiles, il y avait plus d'avantages. Je n'ai pas envie de rentrer dans les détails puisque ça serait long et le sujet n'est pas là.
Reparlons plutôt du moteur 3D
Utiliser une spacialisation des données dans mon cas n'est pas la bonne solution.
Premièrement il me faut une matrice tridimensionnelle, c'est lourd, très lourd, d'autant plus en 3D, et ensuite l'espace que je défini entre les points de la grille doivent être assez prochent pour pouvoir afficher des formes complexes, donc encore plus de points, donc encore plus lourd !
Ensuite la majorité de l'espace est vide, c'est une perte de mémoire inutile.
Et pour finir je ne fais pas de recherche par coordonnées, je n'ai pas besoin de savoir si une face est à coté d'une autre.
Si on pourrait théoriser ça, je dirais qu'il y a un compromis entre la mémoire utilisée et la puissance de calcul.
Je suis persuadé que dans minecraft (j'ai cherché mais je n'ai rien trouvé) il utilise ton principe au niveau des chunks pour savoir lesquels afficher. Dans ce cas oui puisque que les chunks doivent être enregistrés dans une matrice 2D.
Merci pour l'explication de la multiplication, c'est très clair.
Citer : Posté le 10/11/2016 22:29 | #
Si je peux me permettre, ton problème concernant le niveau de précision (points très proches) et les espaces vides est la raison d'être des quadtrees. Ces machins-là sont adaptés pour avoir une précision variable en différents points de l'espace
Bon après je pense bien que dans ton cas il est plus intéressant de garder des listes. Tu pourrais toujours tenter d'ordonner un peu ta liste pour reproduire cette adjacence mais ce serait un peu compliqué. Ce n'est peut-être pas pertinent.
Citer : Posté le 10/11/2016 22:33 | #
En soit cela ne me servirait à rien. Ce qui pourrait être interresant par contre c'est que mes faces soient triées par rapport à la distance par rapport à la caméra.
Le pire cas, c'est que mes triangles soient du plus éloigné au plus proche puisque je modifie les mêmes pixels plusieurs fois.
Ajouté le 18/11/2016 à 00:53 :
J'ai commencé à modéliser des vrais objets pour voir ce que mon moteur a dans le ventre, et le résultat est renversant !
En définissant toutes les faces du moulin à vent, j'ai pu créer avec une relative simplicité un résultat plus que correct.
D'un point de vue technique, j'ai de nouveau optimisé depuis le jour précédent, en effet j'avais tout "désoptimisé" pour résoudre mon problème. Les fps en temps réel sont affichés dans le coin de l'écran, on voit que pour un modèle aussi riche (30 triangles) la vitesse du rendu est plus que convenable ce qui démontre que ce projet est viable. De plus il me reste quelques points à optimiser, sur le calcul des coordonnées de textures je peux grater pas mal, j'ai deux divisions que je peux transformer en une seule, et quelques autres idées. Donc j'ai encore de la marge, l'objectif étant qu'a terme le rendu soit le plus véloce possible
Sinon on peut remarquer que j'applique des textures sur des triangles dans des positions quelconques (le toit et les pales) et que j'ai ajouté l'option pour afficher une texture différentes de chaque côté d'un triangle (le toit vu par en dessous est noir) et j'ai rajouté un paramètre pour une bonne utilisation des textures sur les triangles (en effet le sprite est un carré à la base).
La prochaine étape est une réorganisation du code, j'ai deux fichiers que je vais réunir en un seul et je vais revoir comment le moteur recoit les objets à afficher. Dans la prochaine vidéo, les pales du moulin tourneront (enfin je l'espère bien
Citer : Posté le 18/11/2016 06:20 | #
Ah, c'est magnifique !
Il n'y a plus rien à dire, tu as définitivement atteint un tout autre niveau que les projets existants sur le sujet.
Bon coup de turbo aussi ! Ça laisse rêver :3
Citer : Posté le 18/11/2016 11:12 | #
Merci
D'ailleurs j'ai un problème plus propre au language C/C++
J'ai copié ce bout de code depuis MonochromeLib dans mon fichier cpp
static int (*SysCall)( int R4, int R5, int R6, int R7, int FNo ) = (void*)&SysCallCode;
char* Scene::get_vram_adress()
{
return (char*)((*SysCall)(0, 0, 0, 0, 309));
}
Je précise que j'ai importé (je suppose) la lib où sont définies R4, R5 ...
{
#include "fxlib.h"
#include "string.h"
#include <stdlib.h>
}
Citer : Posté le 18/11/2016 12:41 | #
Ah oui, quand même !!
Super boulot, y'a pas à dire.
Je vais peut-être pouvoir me remettre à Arcuz du coup
Nan je rigole, Trouve Le Titre est prioritaire et plus avancé, c'est dire x)
Citer : Posté le 18/11/2016 13:39 | #
C'est le cast de pointeur qui n'est pas apprécié. Précisément ici :
Comme justement relevé par le compilateur, la variable « SysCall » est de type int (*)(int, int, int, int, int) mais tu l'initialises avec un pointeur de type void *, à savoir « (void*)&SysCallCode ».
Le compilateur C caste silencieusement, mais si tu as besoin d'être explicite tu peux toujours user de la syntaxe suivante :
Cependant, il me semble plus intelligent d'essayer avant de placer cette ligne et les définitions qui vont avec dans un bloc extern "C", au moins pour d'autres raisons.
Par ailleurs R4, R5, etc. ne sont définies nulle part et encore moins dans une lib (et surtout pas dans la lib standard !), c'est juste une indication de nom facultative. Toutes les déclarations suivantes sont équivalentes :
int (*syscall)(int pomme, int banane, int orange, int citron, int bouton);
int (*syscall)(int, int, int, int, int);
C'est vraiment le nombre et le type des arguments qui compte.
Citer : Posté le 18/11/2016 13:51 | #
Merci Dark Storm, ça fait plaisir
Parfait Lephé, ça marche
Citer : Posté le 18/11/2016 16:13 | #
Wow 9*, ce que tu fais est incroyable.
- Kirby's DreamLand : Gobe , Gobe , Gobe !!!
- L'invasion Seanchans : Détruit la flotte ennemis a bord du "Danseur des vagues".
Citer : Posté le 18/11/2016 18:11 | #
Merci bien Fife
Citer : Posté le 18/11/2016 18:20 | #
Tu utilises la méthode des quaternions pour afficher tes points ?
Il n'y aura pas d'ombres au objets ? (dans ce cas-là, gint ne serait pas mal)
Bonne continuation !
Citer : Posté le 18/11/2016 18:21 | #
Excellent ! J'adore !
As-tu l'intention d'écrire un jeu utilisant ton moteur à l'avenir ?
Bon courage.
Citer : Posté le 18/11/2016 19:18 | #
Non pas de quaternions, j'utilise les matrices de rotations. Les quaternions sont utiles pour éviter le phénomène "gimbal lock", ici comme je veux une simple "vue fps", si je peux appeller ça comme ça, je n'ai pas ce problème.
En plus les quaternions necessitent un poil plus de calcul qu'avec les matrices
Je n'ajouterai pas les ombres, ça prend beaucoup de ressources et même avec les nuances de gris, je ne pense pas que l'effet rende bien. Par contre j'ai quelques autres idées pour utiliser les nuances de gris.
Au plus bas, c'est à dire quand je suis au plus proche de ma texture je suis à 7 fps.
Oui il y a quelques pistes, elles portent principalement sur l'affichage des textures. Comme c'est le plus gourmand, c'est là dessus que je joue principalement. Il y a plusieurs pistes d'améliorations, particulièrement une très prométeuse qui consiste à afficher d'une traite mes rectangles sans les diviser en deux triangles. Aussi une simplification qui m'évite plusieurs multiplications dans ma boucle principale pour afficher les textures. J'ai déjà fait quelques essais là dessus mais je n'ai pas réussi, j'ai des erreurs que je n'arrive pas à identifier mais je sens que je suis pas loin
Je n'ai pas vraiment d'idée de jeu
Citer : Posté le 18/11/2016 19:53 | #
Hey, si tu es désespéré en termes d'optimisation je peux te crafter un produit matriciel optimisé.
N'hésite pas si tu repères des schémas récurrents (a * b + c), des trucs comme ça, c'est optimisable au niveau du proco. Btw si tu veux utiliser le gris faudra passer à gcc, ce qui permettra de faire ce genre d'optimisations plus facilement.
Citer : Posté le 18/11/2016 21:18 | #
Merci, ton aide peut m'être bien utile dans ce cas. Je vais partager une partie de mon code pour voir ce qui est optimisable.
Par exemple j'ai dans mon algorithme d'application des textures, dans la partie en O(n²)
int f_tx = (w0 * tx0 + w1 * tx1 + w2 * tx2) / z_div;
int f_ty = (w0 * ty0 + w1 * ty1 + w2 * ty2) / z_div;
Toutes les variables sont des int et constantes, seules w0, w1 et w2 varient
Avec les txi et tyi précalculés.
tx0 = v0tx * v0z;
ty0 = v0ty * v0z;
...
L'objectif serait surtout de supprimer les deux divisions ou de simplifier. Tu penses qu'on peut faire quelque chose de plus ?
J'ai déjà tenté ça
int f_tx = (w0 * tx0 + w1 * tx1 + w2 * tx2) * z_div;
int f_ty = (w0 * ty0 + w1 * ty1 + w2 * ty2) * z_div;
Du coup j'ai fais ça
int f_tx = ((w0 * tx0 + w1 * tx1 + w2 * tx2) * z_div) >> 20;
int f_ty = ((w0 * ty0 + w1 * ty1 + w2 * ty2) * z_div) >> 20;
Citer : Posté le 18/11/2016 21:26 | #
Une des choses que le processeur sait bien faire est sommer des produits de deux termes. Le produit matriciel en est un exemple majestueux, mais ce que tu fais là est pas mal aussi. On peut déjà probablement gagner sur les trois parties sommes/produits (l'idéal ce serait que les triplets (tx0, tx1, tx2) soient alignés comme des tableaux de trois éléments).
Pour la division, si tu manques de précision, il faut définitivement passer le produit par z_div (après calcul de l'inverse) en 64 bits. Faut que j'y réfléchisse mais à vue de nez c'est un gain conséquent.
Si tu normalises des vecteurs tu as sans doute envie d'utiliser la méthode magique de calcul de l'inverse de la racine carrée en flottant.
Citer : Posté le 18/11/2016 21:39 | #
sommer des produits de deux termes
Parce que dans 90% des cas v0tx = v0ty = 0 donc je peux trouver le moyen de retirer les produits w0 * t0x et w0 * t0y.
En l'état actuel je les laisse puisque je gagne pas grand chose à les enlever et ça marche pour les 10% restant.
Je les définis les uns après les autres au début de la fonction, ça ne garanti pas un alignement mémoire mais on peut les mettre dans un tableau.
Effectivement, c'est sur le passage des deux divisions en 1 seule + deux multiplications qu'on a le plus de marge !
Non je n'ai rien à normaliser par contre
Citer : Posté le 19/11/2016 06:28 | #
L'opération précise c'est Σ a_n * b_n. Ce truc-là est tellement courant que le proco a des instructions pour le faire facilement. Donc pas besoin de virer des termes, en fait plus il y en a et plus on gagne. Ça reste léger sur trois termes comme ça mais sur un produit matriciel c'est peut-être important (j'essaierai de te quantifier ça).
Finalement, je suis surpris de ne pas y avoir pensé plus tôt, mais le SDK n'est pas ton ami en termes d'optimisation.
Citer : Posté le 19/11/2016 10:47 | #
Peut-être qu'il fait déjà l'optimisation aussi. ça donne ça en assembleur cette partie
Scene.cpp 897 int f_tx = ((w0 * tx0 + w1 * tx1 + w2 * tx2) / z_div);
00004CF8 E064 MOV #100,R0
00004CFA 01FE MOV.L @(R0,R15),R1
00004CFC 01D7 MUL.L R13,R1
00004CFE E060 MOV #96,R0
00004D00 03FE MOV.L @(R0,R15),R3
00004D02 011A STS MACL,R1
00004D04 0377 MUL.L R7,R3
00004D06 E04C MOV #76,R0
00004D08 031A STS MACL,R3
00004D0A 313C ADD R3,R1
00004D0C 03FE MOV.L @(R0,R15),R3
00004D0E 0357 MUL.L R5,R3
00004D10 031A STS MACL,R3
00004D12 313C ADD R3,R1
00004D14 D322 MOV.L L805+6,R3 ; __divls
00004D16 430B JSR @R3
00004D18 60B3 MOV R11,R0
00004D1A 2F02 MOV.L R0,@R15
Scene.cpp 898 int f_ty = ((w0 * ty0 + w1 * ty1 + w2 * ty2) / z_div);
00004D1C E058 MOV #88,R0
00004D1E 01FE MOV.L @(R0,R15),R1
00004D20 01D7 MUL.L R13,R1
00004D22 E044 MOV #68,R0
00004D24 03FE MOV.L @(R0,R15),R3
00004D26 011A STS MACL,R1
00004D28 0377 MUL.L R7,R3
00004D2A E040 MOV #64,R0
00004D2C 031A STS MACL,R3
00004D2E 313C ADD R3,R1
00004D30 03FE MOV.L @(R0,R15),R3
00004D32 0357 MUL.L R5,R3
00004D34 031A STS MACL,R3
00004D36 313C ADD R3,R1
00004D38 D319 MOV.L L805+6,R3 ; __divls
00004D3A 430B JSR @R3
00004D3C 60B3 MOV R11,R0
00004D3E 61F3 MOV R15,R1
00004D40 7170 ADD #112,R1