Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : Assembleur - Les courbes
(Article écrit par Jérôme Étienne et extrait d'Amiga News Tech - avril 1992)
|
|
En regardant les dernières démos, on peut apercevoir dans certaines d'entre elles ce que l'on appelle des courbes
une série de "points chauds" reliés par une belle courbe lisse, calculée en temps réel.
Cela a l'avantage d'être, bien sûr, beaucoup plus beau qu'une ligne brisée classique, mais le désavantage
d'être bien plus long à calculer. Je me suis donc intéressé à la manière de calculer ces courbes et
j'ai été très surpris d'apprendre que de nombreuses personnes, bien plus qualifiées que moi, m'avaient
devancé. En effet, ces courbes ont de multiples applications dans le domaine professionnel et surtout
dans la modélisation d'objets 3D (par exemple, pour le dessin de la carrosserie d'une voiture).
Mais comme à leur habitude, les algorithmes sont compliqués et demandent une grande puissance de calcul.
Ils n'étaient donc pas adaptés à ce que nous voulons faire, d'autant plus que, dans le cas qui nous
intéresse, il nous faut arriver au temps réel.
Or donc, mon ego et moi-même avons décidé de trouver un autre algorithme qui convienne mieux à nos exigences
et sommes finalement parvenus à mettre au point ce que nous voulions.
Toute la ruse réside dans le fait de connaître le dessin de la fonction f(x)=1/x sur un repère orthonormé :
en effet, on s'aperçoit que la fonction fait exactement le dessin que l'on désire obtenir, à savoir une
belle courbe avec les axes x et y. Maintenant que l'on connaît l'essence de la technique, il faut
résoudre les petits problèmes de programmation. Dans un premier temps, faire en sorte que les axes
contrôlant la courbe puissent être quelconques, aussi bien en angles qu'en longueur. Les explications
qui vont suivre sont relativement complexes, donc je vous conseille de prendre de quoi écrire et de
faire des dessins.
Pour ce qui est des angles, vous aurez remarqué que les axes x et y sont perpendiculaires. Mais dans
notre cas, il est impératif que leur angle soit quelconque, d'où problème. Il peut être résolu
en faisant une sorte de changement de repère : on calcule d'abord les coordonnées de chaque point
dans le repère classique, puis on multiplie la composante y de la coordonnée par le vecteur unitaire
des y de notre propre repère, puis même chose avec celui des x. Si l'on n'a pas oublié de déplacer
l'origine, on obtient alors les coordonnées dans le repère de l'écran.
Parlons maintenant de la longueur : elle présente un problème à cause d'une propriété que possède la
fonction f(x)=1/x, à savoir qu'elle ne coupe jamais les axes x et y et nous (moi et mon ego)
désirons qu'elle le fasse. Donc, au lieu de recalculer complètement une géométrie, j'ai trouvé une
solution plus simple qui va encore compliquer les explications... Elle consiste à faire un changement
de repère au moment du calcul de la courbe, donc avant le changement de repère permettant de faire
n'importe quel angle. Ce nouveau repère doit couper la courbe sans la déformer et de sorte que la
nouvelle origine soit sur la droite d'angle 45° et qui passe par l'origine, et les nouveaux axes
soient parallèles aux précédents. La coordonnée de la nouvelle origine est, dans le listing,
déterminée en fonction de PARA_COURBE, c'est-à-dire que la coordonnée x est égale à la coordonnée y,
elle-même égale à 1/PARA_COURBE. Il apparaît aussi que PARA_COURBE est le x du premier repère où
la courbe coupe l'axe des x du nouveau repère (même chose pour les y).
Dans un premier temps, on récolte les paramètres nécessaires, à savoir les coordonnées des is points chauds
(A, B et C), la précision de calcul (2^PRECI_BIT est le nombre de points qui seront calculés),
le PARA_COURBE (il a aussi la faculté de déterminer la forme de la courbe ; plus ce chiffre
est grand, plus la courbe sera proche des axes directeurs et inversement). On initialise X_BA=(X_A-X_B)
et Y_BA=(Y_A-Y_B) ce sont les composantes du vecteur BA. Puis l'on calcule les coefficients x et y
du pas du curseur qui va se déplacer sur le vecteur BC(C_X=(X_C-X_B)>>PRECI_BIT et C_Y=(Y_C-Y_B)>>PRECI_BIT).
L'intervention du paramètre PRECI_BIT permet au curseur d'arriver au bout du vecteur après 2^PRECI_BIT
itérations, comme cela est nécessaire pour obtenir les 2^PRECI_BIT points que nous désirons.
Ensuite, on initialise les paramètres X1, Y1, X2 et Y2 : (X1,Y1) sont les coordonnées du
curseur qui se déplace sur le vecteur BC (X1=XB et Y1=YB), et (X2,Y2) servent uniquement de tampon
pour mémoriser les coordonnées et pour pouvoir relier tout les points ensemble.
Ensuite, on initialise FIRST_Y_PARA_COURBE avec 1/PARA_COURBE. Ce paramètre correspond au y
le plus faible que la courbe peut atteindre, étant donné que x varie entre ]0,PARA_COURBE].
Il sert à descendre la courbe pour qu'elle coupe l'axe des x. On initialise aussi EMPATEMEN_PARA_COURBE
avec (PARA_COURBE-FIRST_Y_PARA_COURBE). Il correspond à la distance entre l'origine du nouveau
repère et le point où la courbe coupe son axe des x. Il sert surtout pour rétrécir la courbe
en y, de façon qu'elle soit en permanence en dessous de 1 tout en commencent précisément à 1.
Cela permet de simplifier la gestion avec le vecteur unitaire.
On initialise le paramètre a1 qui est le x de f(x)=1/x. a1=FIRST_Y_PARA_COURBE=1/PARA_COURBE,
car le premier x doit être celui de l'origine du nouveau repère. Ensuite, on calcule C_A
qui est le pas avec lequel on incrémente A1. Sachant que a1 doit aller de FIRST_Y_PARA_COURBE
à PARA_COURBE en faisant 2^PRECI_BIT itérations, C_A=(PARA_COURBE-FIRST_PARA_COURBE)>>PRECI_BIT=(EMPATEMENT_COURBE)>>PRECI_BIT.
Maintenant que l'on a initialisé tous les paramètres, il ne reste plus qu'à faire la boucle. A chaque
fois, on commence par incrémenter A1, X1 et Y1 avec respectivement C_A1, C_X et C_Y. On calcule ensuite
le plus important, à savoir qui est égal à (accrochez-vous) : ((1/a1)-FIRST_Y_PARA_COURBE)/EMPATEMENT_PARA_COURBE,
avec 1/a1 vecteur normal pour obtenir la fonction f(x)=1/x, -FIRST_Y_PARA_COURBE pour descendre la
courbe pour qu'elle coupe l'axe des x et /EMPATEMENT_COURBE pour que la courbe soit toujours en dessous
de 1. On calcule ensuite X=X1+X_BA*Y_CO et Y=Y1+Y_BA*Y_CO, et on a enfin les coordonnées du point à afficher. Ouf !
Dans le listing qui suit, j'ai préféré ne pas mêler le tracé avec le calcul pour simplifier quelque
chose qui me paraît déjà bien complexe. J'établis donc un tableau qui est ensuite utilisé par une
autre routine pour tracer. Toujours dans un but de simplifier, je vous ai fait un petit programme en
AMOS
qui fait la même chose que le programme en assembleur, mais vu que c'est du BASIC, il est
beaucoup plus facile à comprendre.
Ce programme est surtout bien pour la technique de base mais pas forcément pour la programmation, qui
n'a pas été optimisée. En effet, on pourrait, si on avait besoin de vitesse, précalculer tous les
y_co, ce qui réduirait la boucle à deux multiplications.
* AUTEUR: j.etienne
* SUJET: dessin d'une courbe pseudo bspline
* ASSEMBLEUR: devpack 2.14
OPT C- * opt case off
incdir 'include:'
include 'exec/exec_lib.i'
include 'hardware/custom.i'
include 'hardware/blit.i'
custom = $dff000
execbase = 4
BPL_X = 320
BPL_Y = 256
BPL_DEPTH = 4
BPL_WIDTH = BPL_X/8
BPL_SIZE = BPL_WIDTH*BPL_Y
SCR_SIZE = BPL_SIZE*BPL_DEPTH
vsync: macro
.wait_vsync\@:
move.l vposr(a5),d0
and.l #$1ff00,d0
cmp.l #\1*$100,d0
bne.s .wait_vsync\@
endm
****************************
WAIT_BLT: macro
btst #14,dmaconr(a5)
.LOOP_WAIT_BLT\@:
btst #14,dmaconr(a5)
bne.s .LOOP_WAIT_BLT\@
endm
******************************************************
************** programme principal *****************
******************************************************
move.l (execbase).w,a6
lea custom,a5
CALLEXEC Forbid
move.w #$03e0,dmacon(a5) * all dma off except disk
move.w #(BPL_DEPTH<<12)+$200,bplcon0(a5)
clr.w bplcon1(a5)
clr.w bplcon2(a5)
move.w #BPL_WIDTH*(BPL_DEPTH-1),bpl1mod(a5)
move.w #BPL_WIDTH*(BPL_DEPTH-1),bpl2mod(a5)
move.w #$2981,diwstrt(a5) *\
move.w #$29c0,diwstop(a5) * > init un ecran 320*192
move.w #$0038,ddfstrt(a5) * > avec un mot en plus pour
move.w #$00d0,ddfstop(a5) */ le shift
bsr BUILD_COPLIST
move.l coplist_adr,cop1lc(a5) * > run my coplist
clr.w copjmp1(a5) */
move.w #$87c0,dmacon(a5) * dma blitter,copper & bitplane on
move.l #310*$10000,XA
move.l #10*$10000,YA
move.l #010*$10000,XB
move.l #50*$10000,YB
move.l #250*$10000,XC
move.l #150*$10000,YC
move.w #5,PRECI_BIT
move.w #8,PARA_COURBE
move.w XA,d0
move.w YA,d1
move.w XB,d2
move.w YB,d3
move.w #2,d4
bsr DISPLAY_NO_CLIP_LINE
move.w XB,d0
move.w YB,d1
move.w XC,d2
move.w YC,d3
move.w #2,d4
bsr DISPLAY_NO_CLIP_LINE
bsr COMPUTE_CURVE
bsr DISPLAY_CURVE
MAIN_LOOP:
vsync $f
move.w #$f00,color(a5) *\
move.w #$2f,d0 * > cree une barre de couleur pour
dbf d0,* * > montrer le temps d'execution
clr.w color(a5) */
move.b $bfec01,d0 *\
not d0 * >capture the key wich is pressed
ror.b #1,d0 */ and put is code RAW in d0
cmp.b #$1,d0 *\
bgt INIT_END */ sort si on presse une touche
btst #6,$bfe001 * ou si on appuie sur le bouton souris
bne MAIN_LOOP
bra INIT_END
DISPLAY_CURVE: *********************************************************
lea TAB_EACH_POINT(pc),a0
cmp.l #-1,(a0) *\ if the list is empty
beq.s .END_LOOP_DISPLAY_CURVE */
move.w (a0)+,.X1 *\ init first point
move.w (a0)+,.Y1 */
.LOOP_DISPLAY_CURVE:
cmp.l #-1,(a0)
beq.s .END_LOOP_DISPLAY_CURVE
move.w (a0)+,.X2
move.w (a0)+,.Y2
move.l a0,-(sp)
move.w .X1(pc),d0
move.w .Y1(pc),d1
move.w .X2(pc),d2
move.w .Y2(pc),d3
move.w #1,d4
bsr DISPLAY_NO_CLIP_LINE
* bsr PLOT
move.l (sp)+,a0
move.w .X2,.X1
move.w .Y2,.Y1
bra .LOOP_DISPLAY_CURVE
.END_LOOP_DISPLAY_CURVE
rts
.X1: ds.w 1
.Y1: ds.w 1
.X2: ds.w 1
.Y2: ds.w 1
****************************************************** END_DISPLAY_CURVE
COMPUTE_CURVE: ***********************************************************
move.w PRECI_BIT(pc),d0
moveq #1,d1
lsl.w d1,d0
move.w d0,PRECI
*
move.l XA(pc),d0
sub.l XB(pc),d0
move.l d0,X_BA
move.l YA(pc),d0
sub.l YB(pc),d0
move.l d0,Y_BA
*
move.l XC(pc),d0
sub.l XB(pc),d0
move.w PRECI_BIT(pc),d1
asr.l d1,d0
move.l d0,C_X
*
move.l YC(pc),d0
sub.l YB(pc),d0
move.w PRECI_BIT(pc),d1
asr.l d1,d0
move.l d0,C_Y
*
move.l XB(pc),X1
move.l YB(pc),Y1
move.l XA(pc),X2
move.l YA(pc),Y2
*
move.l #$10000,d1
move.w PARA_COURBE(pc),d0
bsr DIV_32_BITS
move.l d0,FIRST_Y_PARA_COURBE
*
moveq #0,d0
move.w PARA_COURBE(pc),d0
swap d0
sub.l FIRST_Y_PARA_COURBE(pc),d0
move.l d0,EMPATEMENT_PARA_COURBE
*
move.l EMPATEMENT_PARA_COURBE(pc),d0
move.w PRECI_BIT(pc),d1
asr.l d1,d0
move.l d0,C_A
*
move.l FIRST_Y_PARA_COURBE(pc),A_1
lea TAB_EACH_POINT(pc),a1
move.w XA,(a1)+
move.w YA,(a1)+
.LOOP
move.l C_A(pc),d0
add.l d0,A_1
move.l C_X(pc),d0
add.l d0,X1
move.l C_Y(pc),d0
add.l d0,Y1
move.l #$10000,d1
move.l A_1(pc),d0
moveq #6,d2
lsr.l d2,d0
bsr DIV_32_BITS
moveq #10,d2
lsl.l d2,d0
sub.l FIRST_Y_PARA_COURBE,d0
move.l d0,d1
move.l EMPATEMENT_PARA_COURBE(pc),d0
moveq #11,d3
lsr.l d3,d0
bsr DIV_32_BITS
move.w d0,d2
move.w X_BA,d0
muls d2,d0
lsl.l #5,d0
swap d0
add.w X1,d0
move.w d0,(a1)+
move.w Y_BA,d1
muls d2,d1
lsl.l #5,d1
swap d1
add.w Y1,d1
move.w d1,(a1)+
move.w A_1(pc),d0
cmp.w PARA_COURBE(pc),d0
blt.s .LOOP
move.w XC,(a1)+
move.w YC,(a1)+
move.l #-1,(a1) * pour marque la fin de cette liste
rts
XA: ds.l 1
YA: ds.l 1
XB: ds.l 1
YB: ds.l 1
XC: ds.l 1
YC: ds.l 1
*
X_BA: ds.l 1
Y_BA: ds.l 1
*
C_X: ds.l 1
C_Y: ds.l 1
*
X1: ds.l 1
Y1: ds.l 1
X2: ds.l 1
Y2: ds.l 1
*
PRECI_BIT: ds.w 1
PRECI: ds.w 1
PARA_COURBE: ds.w 1
FIRST_Y_PARA_COURBE: ds.l 1
EMPATEMENT_PARA_COURBE: ds.l 1
*
C_A: ds.l 1
A_1: ds.l 1
*
X: ds.w 1
Y: ds.w 1
*
TAB_EACH_POINT: ds.w (1<<12)*2
*************************************************** END_COMPUTE_CURVE
DIV_32_BITS: ***********************************************
* routine de division d'un chiffre 32 bits part un chiffre 16 bit avec un
* resultat 32 bits. Elle est directement tire de mise en oeuvre du 68000
* de sybex (tres bon livre soit dit en passant).
* in: d0 = X chiffre 16 bits
* d1 = YZ chiffre 32 bits
* out: d0 = resultat 32 bits
* d0-d3 sont detruit
moveq #0,d3
divu d0,d1
bvc.s .RESULT
move.l d1,d2
clr.w d1
swap d1
divu d0,d1
move.w d1,d3
move.w d2,d1
divu d0,d1
.RESULT move.l d1,d0
swap d1
move.w d3,d1
swap d1
move.l d1,d0
rts
******************************************** END_DIV_32_BITS
DISPLAY_NO_CLIP_LINE: *****************************************************
* this routine displays a no clip line.
* IN: d0.w = x1
* d1.w = y1
* d2.w = x2
* d3.w = y2
* d4.w = COLOR
* Cf: 'Amiga Hardware Reference Manuel' p 197 ed:addison wesley
sub.w d0,d2
bmi.s .xneg
sub.w d1,d3
bmi.s .yneg
cmp.w d3,d2
bmi.s .ygtx
moveq #OCTANT1+LINEMODE,d5
bra.s .OCTANT_FOUND
.ygtx: exg d2,d3
moveq #OCTANT2+LINEMODE,d5
bra.s .OCTANT_FOUND
.yneg: neg.w d3
cmp.w d3,d2
bmi.s .ynygtx
moveq #OCTANT8+LINEMODE,d5
bra.s .OCTANT_FOUND
.ynygtx:
exg d2,d3
moveq #OCTANT7+LINEMODE,d5
bra.s .OCTANT_FOUND
.xneg: neg.w d2
sub.w d1,d3
bmi.s .xyneg
cmp.w d3,d2
bmi.s .xnygtx
moveq #OCTANT4+LINEMODE,d5
bra.s .OCTANT_FOUND
.xnygtx:
exg d2,d3
moveq #OCTANT3+LINEMODE,d5
bra.s .OCTANT_FOUND
.xyneg: neg.w d3
cmp.w d3,d2
bmi.s .xynygtx
moveq #OCTANT5+LINEMODE,d5
bra.s .OCTANT_FOUND
.xynygtx:
exg d2,d3
moveq #OCTANT6+LINEMODE,d5
.OCTANT_FOUND:
lea ADR_SCR_ACORDING_TO_Y(pc),a0
lsl.w #2,d1
move.l (a0,d1.w),a0
add.l PHY_SCR_ADR(pc),a0
ror.w #4,d0
move.w d0,d1
and.w #$0fff,d1
add.w d1,d1
lea (a0,d1.w),a0
and.w #$f000,d0
or.w #$0bfa,d0
lsl.w #2,d3
add.w d2,d2
move.w d2,d1
lsl.w #5,d1
add.w #$42,d1
WAIT_BLT
move.w d3,BLTBMOD(a5)
sub.w d2,d3
move.w d3,BLTAPT+2(a5)
move.w d3,d6
bpl.s .lineover
or.w #$40,d5
.lineover:
sub.w d2,d3
move.w d3,BLTAMOD(a5)
move.w #BPL_WIDTH*BPL_DEPTH,BLTCMOD(a5)
move.w #BPL_WIDTH*BPL_DEPTH,BLTDMOD(a5)
move.w #-1,BLTAFWM(a5)
move.w #$8000,BLTADAT(a5)
moveq #BPL_DEPTH-1,d2
.LOOP_EACH_BPL
and.w #$ff0f,d0 * d0= minterns to CLR this bpl
lsr.w #1,d4
bcc.s .CLR_IN_THIS_BPL
or.w #$00f0,d0 * d0= minterns to SET this bpl
.CLR_IN_THIS_BPL
WAIT_BLT
move.w d6,BLTAPT+2(a5)
move.w d0,BLTCON0(a5)
move.w d5,BLTCON1(a5)
move.l a0,BLTCPT(a5)
move.l a0,BLTDPT(a5)
move.w d1,BLTSIZE(a5)
lea BPL_WIDTH(a0),a0
dbf d2,.LOOP_EACH_BPL
rts
ADR_SCR_ACORDING_TO_Y:
DUMMY SET 0
REPT BPL_Y
dc.l DUMMY
DUMMY SET DUMMY+BPL_WIDTH*BPL_DEPTH
ENDR
************************************************ END_DISPLAY_NO_CLIP_LINE
PLOT: *******************************************************
* in: d0 = x
* d1 = y
move.l PHY_SCR_ADR,a0
mulu #BPL_WIDTH*BPL_DEPTH,d1
add.l d1,a0
moveq #$7,d1
and.w d0,d1
neg.w d1
addq.w #7,d1
lsr.w #3,d0
lea (a0,d0.w),a0
bset d1,(a0)
rts
**************************************************** END_PLOT
INIT_END: *********************************************************
* reactivation de l'ancienne coplist
lea GfxName(pc),a1 * nom de la library ds a1
moveq #0,d0 * version 0 (the last)
CALLEXEC OpenLibrary * lib graphique ouverte
move.l d0,a4 * adr de graphicbase ds a4
move.l 38(a4),cop1lc(a5) * chargement de l'adr de
clr.w copjmp1(a5) * l'old coplist et lancement
move.w #$83e0,dmacon(a5) * activation des canaux dma necessaires
CALLEXEC Permit * multi switching autorise
* et on retourne d'ou l'on vient.
moveq #0,d0 * flag d'erreur desactive
rts
GfxName: dc.b "graphics.library",0
EVEN
******************************************************* end_INIT_END
BUILD_COPLIST: ********************************************************
move.l COPLIST_ADR,a0
move.l PHY_SCR_ADR,d2
moveq #BPL_DEPTH-1,d0
move.w #bplpt,d1
.LOOP_INIT_BPL_IN_CLIST
move.w d1,(a0)+
addq.l #2,d1
swap d2
move.w d2,(a0)+
swap d2
move.w d1,(a0)+
addq.l #2,d1
move.w d2,(a0)+
add.l #BPL_WIDTH,d2
dbf d0,.LOOP_INIT_BPL_IN_CLIST
move.l #$fffffffe,(a0)+ * montre la fin de la clist
rts
********************************************************* END_BUILD_COPLIST
******** datas
* variables
PHY_SCR_ADR: dc.l ecran1
COPLIST_ADR: dc.l coplist
section ZONE_CHIP,BSS_C
ecran1: ds.l (scr_size*2)/4
coplist: ds.l 1000*4 * taille inconnue donc on prevoit gros
end
* ceci est le programme amos permettant de faire la meme chose.
* mais vur que cela est en basic il devient beaucoup plus facile a
* comprendre
XA=250 : YA=120
XB=50 : YB=150
XC=300 : YC=10
Ink 4
Draw XA,YA To XB,YB
Draw XB,YB To XC,YC
Ink 2
PRECI#=32
PARA_COURBE#=4
X_BA#=(XA-XB) : Y_BA#=(YA-YB)
C_X#=(XC-XB)/PRECI# : C_Y#=(YC-YB)/PRECI#
X1#=XB : Y1#=YB
X2#=XA : Y2#=YA
FIRST_Y_PARA_COURBE#=1/PARA_COURBE#
EMPATEMENT_PARA_COURBE#=PARA_COURBE#-FIRST_Y_PARA_COURBE#
C_A#=EMPATEMENT_PARA_COURBE#/PRECI#
A1#=FIRST_Y_PARA_COURBE#
While A1#<=PARA_COURBE#
A1#=A1#+C_A#
X1#=X1#+C_X# : Y1#=Y1#+C_Y#
Y_CO#=((1/A1#)-FIRST_Y_PARA_COURBE#)/EMPATEMENT_PARA_COURBE#
X#=X1#+X_BA#*Y_CO#
Y#=Y1#+Y_BA#*Y_CO#
Draw X2#,Y2# To X#,Y#
X2#=X# : Y2#=Y#
Wend
|
|