Logicielsmoto.com
http://www.logicielsmoto.com/phpBB/

Tracé de cercles
http://www.logicielsmoto.com/phpBB/viewtopic.php?f=3&t=595
Page 2 sur 3

Auteur:  Samuel Devulder [ 25 Mar 2019, 17:01 ]
Sujet du message:  Re: Tracé de cercles

Ammélioration du passage des aurguments à la routine plot. Les 8 points sont tracés en 808 cycles au lieu de 846, ce qui nous fait (45 + 808)*85/2 = ~36253 cycles au lieu 37888 (~1600 cycles plus rapide) :
Code:
* Trace 8 points (272+8*67=808)
* X = offset en abcisse, U = offset en ordonée, (PLOTX,PLOTY)=centre cercle (xc,yc)
plot8  pshs    d,x,u
* xc+x,yc+y
       ldd     <PLOTX
       addd    2,s
       pshs    d
       ldd     <PLOTY
       addd    6,s
       pshs    d
       bsr     plot
* xc+x,yc-y
       ldd     <PLOTY
       subd    8,s
       std     ,s
       bsr     plot
* xc-x,yc-y   
       ldd     <PLOTX
       subd    6,s
       std     2,s
       ldd     ,s
       bsr     plot
* xc-x,yc+y
       ldd     <PLOTY
       addd    8,s
       std     ,s
       bsr     plot
* xc+y,yc+x
       ldd     <PLOTX
       addd    8,s
       std     2,s
       ldd     <PLOTY
       addd    6,s
       std     ,s
       bsr     plot
* xc+y,yc-x
       ldd     <PLOTY
       subd    6,s
       std     ,s
       bsr     plot
* xc-y,yc-x
       ldd     <PLOTX
       subd    8,s
       std     2,s
       ldd     ,s
       bsr     plot
* xc+y,yc+x
       ldd     <PLOTY
       addd    6,s
       std     ,s
       bsr     plot
       leas    4,s
       puls    d,x,u,pc
(info)

* Trace un point (67cycles).
* D contient l'ordonnée (qui est aussi en "2,S").
* L'abscisse est en "4,S"
plot   subd    #200   ! hors écran en Y ?
       bhs     plot0  ! oui ==> terminé
       ldx     #scrptr+400 ! pointeur ecran + compensation du test
       lslb           !
       rola           !
       ldu     d,x    ! récupération pointeur écran
       ldd     4,s    ! abscisse
       subd    #320   ! hors écran en X ?
       bhs     plot0  ! oui ==> terminé
       ldx     #scrmsk+640 ! pointeur masque/décalage + compensation du test
       lslb           !
       rola           !
       ldd     d,x    ! recupération mask et décalage horizontal
       ora     b,u    !
       sta     b,u    ! mise à jour écran
plot0  rts
(info)


Chose amusante, si dans la boucle principale
Code:
IF Z<0 THEN Z=Z+X:X=X-1
on omet X=X-1, alors l'algo trace .... un beau carré!

Auteur:  Prehisto [ 25 Mar 2019, 17:39 ]
Sujet du message:  Re: Tracé de cercles

Samuel Devulder a écrit:
@Prehisto: comment comptes tu les cycles pour la boucle principale ? Tu estimes que le correctif n'est fait qu'une fois tous les deux pixels environ ?

Non, je le compte pour les 61 fois de la boucle. Ce qui fait que le programme est passé sous les 3 vbl depuis plus longtemps que je le crois, mais bon, peu importe. C'est juste pour un ordre d'idée.

Auteur:  Samuel Devulder [ 25 Mar 2019, 17:47 ]
Sujet du message:  Re: Tracé de cercles

ok, dans le cas la formule devient (45 + 808)*61 = 52033 cycles. On est effectivement bien en dessous de 3VBL dans le pire cas.

Auteur:  Prehisto [ 25 Mar 2019, 19:23 ]
Sujet du message:  Re: Tracé de cercles

Pour ta routine 'plot', tu peux calculer l'offset pour la table des pointeurs négativement et l'offset pour la table des masques/décalages positivement. Ainsi tu n'auras plus besoin que d'un seul pointeur de table pour satisfaire toutes tes pioches.

Auteur:  Samuel Devulder [ 25 Mar 2019, 19:28 ]
Sujet du message:  Re: Tracé de cercles

Oui, c'est une idée. Je vois pour le subd #200 qui du coup est <=0 et nous amène pile en offset negatif par rapport à la table. Mais après il faut remplacer le subd #320 par un cmpd soit +1 cycle, mais on économise un ldx: 3 cycle, bilan -2 cycles .. hmmm ca se tente en effet.

Auteur:  Prehisto [ 25 Mar 2019, 19:29 ]
Sujet du message:  Re: Tracé de cercles

En faisant:

Code:
       ldd     #320   ! abscisse
       subd    4,s    ! hors écran en X ?
       ble     plot0  ! oui ==> terminé


Ou, pour plus de clarté (et moins de risque d'erreur):

Code:
       ldd     #319   ! abscisse
       subd    4,s    ! hors écran en X ?
       bcs     plot0  ! oui ==> terminé

Auteur:  Samuel Devulder [ 25 Mar 2019, 19:49 ]
Sujet du message:  Re: Tracé de cercles

oh oui c'est encore mieux ca 319-machin... pas de CMPD (que j'aime pas: trop lent)

Bien vu! :bien: Ca donne ca:
Code:
(main)CIRCLE

       setdp  $60
      
PLOTX  equ    $603D
PLOTY  equ    $603F
TEMP   equ    $606C

       org    $9000

debut  equ    *
* Initialise l'écran
       ldx    #mess
       bsr    puts
       
* Initialise la table des pointeurs
       ldx    #scrptr
       ldd    #$4000
init0  std    ,x++
       addd   #40
       cmpx   #scrmsk
       bne    init0
       
* initialise la table des maques
       ldd    #$0128
init1  std    ,x++
       lsla
       bcc     init1
       rola
       decb
       bge     init1
       
* Trace le cercle
       ldd    #85     ;Rayon
       ldx    #128    ;Centre X
       ldy    #87     ;Centre Y
       
* loop
       bsr    circle
*      subd   #1
*      bne    loop
       
* Attend l'appui d'une touche
key0   jsr    >$e806
       tstb
       bne    key0
key1   jsr    >$e806
       tstb
       beq    key1
       swi
       rts

* Affiche un message
puts0  jsr    >$e803
puts   ldb    ,x+
       bne    puts0
       rts
(info)
* Initialisation de l'écran
mess   fcb    $1f,$20,$20
       fcb    $1f,$12,$14
       fcb    $1b,$47
       fcb    $1b,$50
       fcb    $1b,$60
       fcb    $0c
       fcb    $14
       fcb    0

circle pshs    a,b,dp,x,u
       lda     #$60
       tfr     a,dp
       stx     <PLOTX
       sty     <PLOTY
     
* X=rayon
       ldx     ,s
* Y=0
       ldu     #0
* Z=rayon/2
       lda     ,s
       lsra
       rorb
(info)
circl0 bsr     plot8
* Y = Y+1
       leau    1,u
* Z = Z - Y
       stu     <TEMP
       subd    <TEMP
* IF Z<0 THEN Z=Z+X:X=X-1
       bcc     circl1
       stx     <TEMP
       addd    <TEMP
       leax    -1,x
       stu     <TEMP
* IF X>=Y THEN GOTO 30
circl1 cmpx    <TEMP
       bcc     circl0
(info)
       puls    a,b,dp,x,u,pc
(info)

* Trace 8 points (272+8*64-5=779 cycles)
* X = offset en abcisse, U = offset en ordonée,
* (PLOTX,PLOTY) = centre cercle (xc,yc)
plot8  pshs    d,x,u
* xc+x,yc+y
       ldd     <PLOTX
       addd    2,s
       pshs    d
       ldd     <PLOTY
       addd    6,s
       pshs    d
       bsr     plot
* xc+x,yc-y
       ldd     <PLOTY
       subd    8,s
       std     ,s
       bsr     plot
* xc-x,yc-y   
       ldd     <PLOTX
       subd    6,s
       std     2,s
       ldd     ,s
       bsr     plot
* xc-x,yc+y
       ldd     <PLOTY
       addd    8,s
       std     ,s
       bsr     plot
* xc+y,yc+x
       ldd     <PLOTX
       addd    8,s
       std     2,s
       ldd     <PLOTY
       addd    6,s
       std     ,s
       bsr     plot
* xc+y,yc-x
       ldd     <PLOTY
       subd    6,s
       std     ,s
       bsr     plot
* xc-y,yc-x
       ldd     <PLOTX
       subd    8,s
       std     2,s
       ldd     ,s
       bsr     plot
* xc-y,yc+x
       ldd     <PLOTY
       addd    6,s
*       std     ,s        ! inutile pour le dernier point, 5 cycles de gagnés
       bsr     plot
       leas    4,s
       puls    d,x,u,pc
(info)

* Trace un point (64 cycles).
* D contient l'ordonnée (qui est aussi en "2,S").
* L'abscisse est en "4,S"
plot   subd    #200   ! hors écran en Y ?
       bhs     plot0  ! oui ==> terminé
       ldx     #scrmsk ! pointeur ecran
       lslb           !
       rola           !
       ldu     d,x    ! récupération pointeur écran
       ldd     #319   ! largeur ecran - 1
       subd    4,s    ! abscisse hors écran ?
       bcs     plot0  ! oui ==> terminé
       lslb           !
       rola           !
       ldd     d,x    ! recupération mask et décalage horizontal
       ora     b,u    !
       sta     b,u    ! mise à jour écran
plot0  rts
(info)
       echo    code=&*-debut

* Table des pointeurs d'écran
scrptr rmb     200*2

* Table avec le mask et l'offset
scrmsk rmb     320*2

       echo    data=&*-scrptr

       end     debut

Un point ne prends plus que 64 cycles. Les 8 points sont affichés en 779 cycles, ce qui nous fait, d'après la formule, le cercle en (45 + 779)*61 = 50264 cycles, soit encore 1769 cycles de gagnés.

Auteur:  Fool-DupleX [ 25 Mar 2019, 23:19 ]
Sujet du message:  Re: Tracé de cercles

Citation:
Ca ne correspond pas au Bresenham du wiki qui travaille avec 8x et 8y

multiplier par 8, c'est faire un decalage de 3 bit, or c'est c'est ce que je vois dans le code présenté un peu plus haut. :???:

Auteur:  Samuel Devulder [ 25 Mar 2019, 23:25 ]
Sujet du message:  Re: Tracé de cercles

8x, c'est des décalages à gauche, or ce que tu as vu plus haut c'est des décalages à droite, des divisions, pas des multiplications :p

Il y a d'autres particularités dans le Bresenham du wiki qu'on ne retrouve pas dans le code ci-dessus comme le fait d'avoir une addition par 5 dans l'init. Bref: c'est pas le même calcul.

Auteur:  Prehisto [ 26 Mar 2019, 09:17 ]
Sujet du message:  Re: Tracé de cercles

Samuel Devulder a écrit:
Un point ne prends plus que 64 cycles. Les 8 points sont affichés en 779 cycles, ce qui nous fait, d'après la formule, le cercle en (45 + 779)*61 = 50264 cycles, soit encore 1769 cycles de gagnés.

Tu devrais créer tes propres registres accessibles par ton propre DP, ainsi tu accéderais aux registres en adressage direct plutôt qu'en indexé. Ça te fera gagner quelques cycles.

EDIT: et si tu tiens vraiment à conserver l'avantage de la pile, déclare un pointeur de pile dans ta zone de page directe, ainsi tu pourras toujours accéder en direct à tes registres empilés.

EDIT2: En fait, l'élimination des empilements va te permettre d'éliminer :
Code:
       pshs    d,x,u
       ...
       bsr     plot
       leas    4,s
       puls    d,x,u,pc
soit quelques 36 cycles, ce qui sera avantageux même si tu dois préserver quelques registres en contre-coup par des STORE en adressage direct.

Auteur:  Prehisto [ 26 Mar 2019, 09:33 ]
Sujet du message:  Re: Tracé de cercles

Du coup, pas un gain de cycles, mais un gain de place. Tu as plusieurs fois un :
Code:
       std     <$xxxx
       bsr     plot

Fais donc deux entrées pour la routine 'plot':
Code:
plot0  std     <$xxxx
plot   subd    #200   ! hors écran en Y ?
       bhs     plot0  ! oui ==> terminé

Auteur:  Samuel Devulder [ 26 Mar 2019, 15:04 ]
Sujet du message:  Re: Tracé de cercles

Bah je voulais savoir si je pouvais n'utiliser que la page0 du moniteur. L'optim ultime serait d'avoir la direct-page sur le programme lui-même et utiliser du code auto-modifiable: faire des "addd #nnnn" au lieu de "addd <TEMP" c'est bien plus rapide.

Un autre optim que j'ai en tête, mais je ne suis pas certain qu'elle vaille le coup sur 6809 serait celle-ci: au lieu d’appeler PLOT 8 fois, on pourrait avoir 8 couples (masque,pointeur) correspondant aux bits à allumer en mémoire vidéo. L'affichage d'un point est un truc genre "*pointeur |= masque" en C. Ensuite dans la boucle "cercle" on modifie X/Y à chaque fois ce qui revient à décaler masque à droite ou à gauche si on touche à X (et corriger pointeur quand la carry disparaît), et à incrémenter/décrémenter pointeur de 40 quand on touche à Y. On perd le clipping des points, et je ne suis pas certain que ce soit rapide sur 6809 car comme on a pas beaucoup de registres il faudra passer par de la mémoire et à ce moment c'est vraiment beaucoup plus lent. Par contre sur une machine RISC avec pleins de pointeurs, ca peut être super rapide de remplacer les 8 appels à PLOT par une gestion intelligente de pointeurs et masques qui ne sont déplacés que d'une unité au plus à chaque tour de boucle.

Auteur:  Prehisto [ 26 Mar 2019, 15:30 ]
Sujet du message:  Re: Tracé de cercles

L'optimisation ultime serait de fabriquer une table en douce en mémoire de couples pointeur/bit et de l'afficher ensuite. Il y aurait alors une chance d'afficher un cercle en moins d'une moitié de VBL.

EDIT: Ah. Tu m'as pris de vitesse :L

Auteur:  Samuel Devulder [ 26 Mar 2019, 17:36 ]
Sujet du message:  Re: Tracé de cercles

Oui ca me semble tout à fait joueable: dans le pire des cas la table des couples occupe 3.8ko maxi (cercle de diamètre 200pixels * 2pi * 3 octets/pixel = 3770 octets). C'est pas beaucoup tout compte fait.

Auteur:  Prehisto [ 26 Mar 2019, 20:09 ]
Sujet du message:  Re: Tracé de cercles

C'est que l'affichage ne suffit pas, il faut aussi avoir le temps pour effacer ;)

Page 2 sur 3 Heures au format UTC + 1 heure
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/