routine 3D ultra-performante pour 6502

Cette catégorie traite de développements récents pour nos vieilles machines, applications, jeux ou démos... Amis programmeurs, c'est ici que vous pourrez enfin devenir célèbres!

Modérateurs : Papy.G, fneck, Carl

JiBé
Messages : 6
Enregistré le : 30 déc. 2019 22:43

routine 3D ultra-performante pour 6502

Message par JiBé » 09 janv. 2020 09:58

Bonjour à tous,

J'ai récemment conçu et réalisé une routine de projection 3d en assembleur 6502 qui est capable d'effectuer la projection d'un point 3D sur un écran 2D en moins de 500 cycles processeur (ce qui en fait un outils idéal pour le rendu de scènes 3D en temps-réel).

Le principe consiste à effectuer la projection en utilisant la trigonométrie plutôt que l'algèbre linéaire.
Ainsi, pour un point 3D aux coordonnées [pX, pY, pZ] et une caméra à la position [cX, cY, cZ] tournée d'un angle caZ autour de son axe Z et caX autour de son axe X, les coordonnées écran sont calculées en utilisant les coordonnées angulaires du point relativement à la caméra par l'algorithme suivant:

Code : Tout sélectionner

AngleHorizontal =  atan2((pY-cY),(pX-cY)) - caZ
DistanceHorizontale = sqrt ((pY-cY)**2+(pX-cX)**2)
AngleVertical = atan2((pY-cY),DistanceHorizontale ) - caX
l'arctangente est calculée par une simple abaque indexée par le résultat d'une division logarithmique entre le numérateur et le dénominateur.
J'ai utilisé l'algorithme trouvé sur codebase64.
la distance horizontale est calculée par une approximation biplanaire le norme euclidienne dont j'explique le principe d'élaboration ici.

Le code source de la routine, des outils pour le calcul des abaques, des fragments de documentation, et des exemples d'utilisation sont disponibles sur le dépôt du projet glOric.

La routine est disponible en deux versions :
  • - une pour xa65 à destination de l'Oric
  • - une pour ca65 pouvant adresser plusieurs plateformes.
Alors n'hésitez pas à l'utiliser dans vos réalisations en suivant ce rapide guide d'utilisation.

La seule chose que je vous demande, si vous me faites l'honneur d'utiliser cette routine, c'est d'ajouter mon nom dans les crédits de vos programmes:
Jean-Baptiste PERIN

Avatar du membre
rendomizer
Messages : 289
Enregistré le : 17 juin 2016 21:00
Contact :

Re: routine 3D ultra-performante pour 6502

Message par rendomizer » 09 janv. 2020 12:32

je cherchais un algo pour un cercle en asm justement ! merci mon pote
le mot de passe c'est quoi ? quoi.

Avatar du membre
Papy.G
Modérateur
Messages : 2220
Enregistré le : 10 juin 2014 13:40
Localisation : Haute-Garonne/Gers

Re: routine 3D ultra-performante pour 6502

Message par Papy.G » 09 janv. 2020 14:14

Sur Triceraprog, je crois avoir vu un truc du genre, en gros, avec Pythagore, tu traces 1/8 du cercle, puis tu dupliques tout le reste.
Soyez exigeants, ne vous contentez pas de ce que l'on vous vend.
Demandez-en plus, ou faites-le vous-même.

JiBé
Messages : 6
Enregistré le : 30 déc. 2019 22:43

Re: routine 3D ultra-performante pour 6502

Message par JiBé » 09 janv. 2020 15:42

Le plus efficace pour tracer un cercle est certainement l'algo de Bresenham dont une implémentation en assembleur 6502 est disponible ici.

On y retrouve l'idée évoquée par Papy.G consistant à diviser le problème en 8.

Avatar du membre
Mokona
Messages : 510
Enregistré le : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: routine 3D ultra-performante pour 6502

Message par Mokona » 09 janv. 2020 16:09

C'est fun finalement de revenir à de la trigo "manuelle". Mais c'est vrai que l'algèbre linéaire est probablement plus adaptée au machines plus récentes.

Merci pour la routine.

------

Effectivement, il y a une série de 3 articles sur Triceraprog à propos du tracé d'un cercle, par contre l'implémentation finale est en BASIC.

https://www.triceraprog.fr/apres-la-lig ... ercle.html
https://www.triceraprog.fr/vg5000u-simp ... ercle.html
https://www.triceraprog.fr/trace-dun-ce ... 5000u.html

__sam__
Messages : 5084
Enregistré le : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: routine 3D ultra-performante pour 6502

Message par __sam__ » 09 janv. 2020 18:21

JiBé a écrit :
09 janv. 2020 15:42
Le plus efficace pour tracer un cercle est certainement l'algo de Bresenham dont une implémentation en assembleur 6502 est disponible ici.
On peut cependant faire un peu mieux comme cela a été montré durant la Forever-Party de l'an dernier: http://www.logicielsmoto.com/phpBB/view ... ?f=3&t=595
Samuel.
A500 Vampire V2+ ^8^, A1200(030@50mhz/fpu/64mb/cf 8go),
GVP530 (MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.

Avatar du membre
Mokona
Messages : 510
Enregistré le : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: routine 3D ultra-performante pour 6502

Message par Mokona » 09 janv. 2020 19:56

Compliqué de comprendre quoi que ce soit avec le bruit ambiant.

Je ne comprends pas ce qu'il fait du petit bout d'assembleur à la fin.

__sam__
Messages : 5084
Enregistré le : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: routine 3D ultra-performante pour 6502

Message par __sam__ » 09 janv. 2020 23:51

Peu importe le bruit, ce qui compte c'est l'algorithme en basic qui est présenté à la minute 10. Après le passage à l'asm c'est secondaire, ca ne change pas la nature de l'algo.
Sans titre.png
Sans titre.png (418.74 Kio) Vu 863 fois
Samuel.
A500 Vampire V2+ ^8^, A1200(030@50mhz/fpu/64mb/cf 8go),
GVP530 (MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.

Avatar du membre
Papy.G
Modérateur
Messages : 2220
Enregistré le : 10 juin 2014 13:40
Localisation : Haute-Garonne/Gers

Re: routine 3D ultra-performante pour 6502

Message par Papy.G » 10 janv. 2020 10:28

Ce que je ne comprends pas, c'est qu'il nous montre une technique de calcul avec pas angulaire, ensuite la formule avec Pythagore, puis cette formule optimisé (pour éviter de recourir à la racine carrée, rarement disponible en ASM sur les 8 bits), mais quand il passe à l'assembleur, le tracé ressemble à celui de la technique par pas angulaire, il n'est pas si fin qu'avec la dernière technique présentée en basic. :|

J'avais essayé de voir sur ma calculette les procédés décrits sur Triceraprog, et je vais réessayer pour ceux-là, j'ai beaucoup de mal à accéder à l'abstraction, il me faut pratiquer pour appréhender la démarche, et j'encourage tous ceux que ça intéressent à faire de même si vous avec sous la main une machine combinant Basic (ou autre langage) et graphismes. :wink:

Pour en revenir au sujet, je me souviens avoir fait quand j'étais au lycée, une sorte de moteur de rendu de perspectives, et cela utilisait les fonctions de calcul trigo de la calculette, Thalès et un facteur pour la profondeur. Vu mon niveau en maths, c'était pas hyper élaboré, mais on pouvait afficher un cube (à l'époque, le délire, c'était le logo N64) ajuster les angles, le zoom… J'ai retrouvé quelques listings à traîner, avant de déménager, mais à priori pas celui-ci.
Ce que je me demande, c'est comment obtenir des valeurs pas trop moisies dans une table pas trop volumineuse pour reproduire des fonctions trigo en assembleur. On sait que pour tracer un cercle, on n'a besoin que de 0 à 45°, et que sur cette portion, un cercle décrit une courbe quasiment identique à celle du carré (de 0 à 0,7) si je me souviens bien, une valeur de 4bits avec un facteur me semble être la base minimum, est-ce ce qui se fait habituellement?
Soyez exigeants, ne vous contentez pas de ce que l'on vous vend.
Demandez-en plus, ou faites-le vous-même.

Avatar du membre
Mokona
Messages : 510
Enregistré le : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: routine 3D ultra-performante pour 6502

Message par Mokona » 10 janv. 2020 11:05

__sam__ a écrit :
09 janv. 2020 23:51
Peu importe le bruit, ce qui compte c'est l'algorithme en basic qui est présenté à la minute 10.
Ok. Du coup c'est le même que sur Triceraprog à la différence ici que la position et le rayon sont "en dur".
Mais même principe.

__sam__
Messages : 5084
Enregistré le : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: routine 3D ultra-performante pour 6502

Message par __sam__ » 10 janv. 2020 11:25

Sur Triceraprog il me semble voir se balader des carrés dans la boucle principale des exemples (calculer m=(x+1)²+(y−0.5)²−r²). Or il n'y en a aucun dans la routine de la capture écran plus haut. Idem dans Tricera on trouve les 8*y à la fois coûteux et présents dans Bresenham. Non je crois bien que la routine présentée à la Forever-Party est différente et est même plus rapide que Bresenham à cause de ces multiplications par 8 qui ne sont pas présentes. En plus avec une légère modification, elle trace un carré. C'est vraiment surprenant.
Samuel.
A500 Vampire V2+ ^8^, A1200(030@50mhz/fpu/64mb/cf 8go),
GVP530 (MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.

Avatar du membre
Mokona
Messages : 510
Enregistré le : 17 déc. 2016 22:01
Localisation : Nord Est des Yvelines
Contact :

Re: routine 3D ultra-performante pour 6502

Message par Mokona » 10 janv. 2020 11:53

Le code final sur Triceraprog est :

Code : Tout sélectionner

800 REM AFFICHE UN CERCLE (BRESENHAM)
810 REM CX ET CY CONTIENNENT LES COORDONNEES DU CENTRE
820 REM R CONTIENT LE RAYON

830 XX=0:YY=R:MM=5-4*R

840 IF XX>YY THEN GOTO 970
850 X=CX+XX:Y=CY+YY:GOSUB 100
860 X=CX+YY:Y=CY+XX:GOSUB 100
870 X=CX-XX:Y=CY+YY:GOSUB 100
880 X=CX-YY:Y=CY+XX:GOSUB 100
890 X=CX+XX:Y=CY-YY:GOSUB 100
900 X=CX+YY:Y=CY-XX:GOSUB 100
910 X=CX-XX:Y=CY-YY:GOSUB 100
920 X=CX-YY:Y=CY-XX:GOSUB 100

930 IF MM > 0 THEN YY=YY-1:MM=MM-8*YY
940 XX=XX+1
950 MM=MM+8*XX+4

960 GOTO 840
970 RETURN
Le GOSUB 100 est l'affichage d'un pixel, qui malheureusement n'existe pas tel quel en BASIC VG5000µ (et qui du coup est très lent en BASIC).

__sam__
Messages : 5084
Enregistré le : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: routine 3D ultra-performante pour 6502

Message par __sam__ » 10 janv. 2020 12:39

Oui, et on retrouve les multiplications par 8, qui bien que plus rapides que la multiplication en général, restent plus lentes que pas de multiplication du tout! (cf photo plus haut). Avec les conventions du programmes VG on aurait:

Code : Tout sélectionner

830 XX=R:YY=R:ZZ=INT(XX/2)

850 X=CX+XX:Y=CY+YY:GOSUB 100
860 X=CX+YY:Y=CY+XX:GOSUB 100
870 X=CX-XX:Y=CY+YY:GOSUB 100
880 X=CX-YY:Y=CY+XX:GOSUB 100
890 X=CX+XX:Y=CY-YY:GOSUB 100
900 X=CX+YY:Y=CY-XX:GOSUB 100
910 X=CX-XX:Y=CY-YY:GOSUB 100
920 X=CX-YY:Y=CY-XX:GOSUB 100

930 YY=YY+1
940 ZZ=ZZ-YY
950 IF ZZ<0 THEN ZZ=ZZ+XX:XX=XX-1
960 IF XX>=YY THEN GOTO 850
Modifié en dernier par __sam__ le 10 janv. 2020 12:45, modifié 1 fois.
Samuel.
A500 Vampire V2+ ^8^, A1200(030@50mhz/fpu/64mb/cf 8go),
GVP530 (MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.

Avatar du membre
Papy.G
Modérateur
Messages : 2220
Enregistré le : 10 juin 2014 13:40
Localisation : Haute-Garonne/Gers

Re: routine 3D ultra-performante pour 6502

Message par Papy.G » 10 janv. 2020 12:45

Huit points verticaux par caractère, il n'y a pas de mode graphique direct sur le EF9345. ;)
Mais c'est vrai que sans faire de carrés, c'est forcément plus rapide.
Soyez exigeants, ne vous contentez pas de ce que l'on vous vend.
Demandez-en plus, ou faites-le vous-même.

Avatar du membre
6502man
Messages : 9997
Enregistré le : 12 avr. 2007 22:46
Localisation : VAR
Contact :

Re: routine 3D ultra-performante pour 6502

Message par 6502man » 15 janv. 2020 23:06

@JiBé: Merci pour le partage du source :D

Tu à codé un exemple sur oric pour voir ce que cela donne ?
Phil.

www.6502man.com

To bit or not to bit.
1 or 0.

Répondre