|
Bienvenue ! - Articles : Article -
|
News | Archives | FAQ | Communauté | Projets |
News Non Officielles | Le site | TiWiki | Liens |
Bienvenue sur Ti-Fr v3!
News
Officieuses
BTS en bâtiment...
Message personnel... Romain Liévin quitte la communauté TI - la suite TIGCC v0.95 moins pratique que GTC v0.90 ? sortie de ppglib Et 100000, ça fait un joli nombre, non ? Problème d'accès MERCI !
Anciennes news
InfinitEye, un projet de casque de réalité virtuelle
De retour... Questions posées en messages privés. Bonne année ! Messages... Du nouveau sur Punix TI déverrouille la nSpire Reflashages et corrections en série pour les Nspire...
Plus...
Articles
Programmation Tutorial : Programmation C [OLD] (200423) Tutorial : Programmation C [NEW] (117940) Tutorial sur Vertel3 (60908) Hardware
Dernières archives
Assembleur & C
Basic
nSpire & nSpire CAS
Production Clickpad Nspire infor (15/09/2012)
imgmanip pour Nspire (3/04/2012) imgdump Clickpad - Touchpad - CX (4/03/2012)
Meilleurs DL
La plus consultée
Plus...
Infos
|
Article TI [Programmation] Articles sur la programmation des TI68k Algorithme de BresenhamExplication de l'instruction lineVous avez, dans le cadre de l'un de vos développements, ou tout simplement par soif de connaissance envie de savoir comment tracer une ligne en codant vous même l'allumage des points à l'écran ? Sasume vous propose un article pour comprendre comment ce faire dans un programme en C. Explications de l'algorithme de tracé de lignes de BresenhamPour représenter une ligne sur un écran composé de pixels, il faut allumer les pixels passant le plus près possible de la ligne idéale : Sur ce schéma, on suppose que chaque case représente un pixel, s'il est grisé c'est qu'il est allumé. La droite (AB) est la droite idéale. Le problème est celui-ci : comment savoir quels pixels allumer pour s'approcher le plus possible de la droite idéale ? La première solution qui vient à l'esprit est de calculer la distance verticale entre le pixel et la droite idéale et d'allumer le pixel pour lequel l'erreur est inférieure à 0.5. Par exemple, considérons la droite d'équation y=ax+b avec a=1/3 : Pour le premier pixel, bien entendu, il n'y a aucune erreur,
mais pour le deuxième, l'erreur est égale à 0.33 (
UR chaque pixel, l'erreur augmente de void ligne(short x1,short y1,short x2,short y2) { float erreur,a; short dx,dy,x,y; dx = x2 - x1 ; dy = y2 - y1 ; a = dy / dx ; err = 0 ; for(x = x1 , y = y1 ; x < x2 ; x++) { AffichePixel(x,y); err += a ; if(err > 0.5) { err -= 1 ; y++ ; } x++ ; } } Bien sûr, cette fonction ne permet que de tracer une ligne dont la distance
sur x est plus grande que celle sur y et il faut aussi que les coordonnées
passées en argument respectent ces deux conditions : Le gros problème de cet algorithme, si on recherche la vitesse, c'est qu'il
utilise deux nombres à virgule flottante pour stocker - err += dy/dx - err > 1/2 - err -= 1 Et si on est obligé d'utiliser des nombres à virgule flottante, c'est
simplement à cause de la division par - err += dx*dy/dx <=> err += dy - err > dx*1/2 <=> err > dx/2 - err -= dx*1 <=> err -= dx Voilà, avec ça on peut utiliser des entiers. Une deuxième optimisation qui permettrait de gagner un petit peu de
rapidité (mais c'est vraiment infime par rapport à ce qu'on vient de gagner en
supprimant l'utilisation des Une autre optimisation, puisqu'on connaît à l'avance la longueur de la
ligne sur x, consisterait à ne pas comparer à chaque cycle la valeur courante
de La dernière optimisation, est de remplacer la division par deux par un décalage de bits vers la droite. Voici ce qu'est devenu l'algorithme du début : void ligne(short x1,short y1,short x2,short y2) { short err, a, dx, dy; dx = x2 - x1 ; dy = y2 - y1 ; err = -dx>>1 ; x2 -= x1 ; do { AffichePixel(x1,y1); err += dy ; if(err > 0) { err -= dx ; y1++ ; } x1++ ; }while(x2--); } Cet algorithme est maintenant devenu très rapide puisqu'il n'utilise que des entiers et ne requiert que des additions et soustractions (aucune multiplication ni division). Les dernières optimisations consisteraient à afficher le pixel directement dans la fonction, cela permettrait de ne pas avoir à recalculer l'adresse du pixel à allumer à chaque cycle puisqu'on se déplace d'un pixel à chaque fois, mais ces optimisations ne font plus vraiment partie de l'algorithme de tracé, donc je ne les implémente pas ici. L'algorithme juste au-dessus permet toujours de ne tracer qu'un seul type de
lignes, ces lignes doivent remplir ces conditions : Dernières optimisations : Voilà, c'est la fin de cet article sur le traçage de ligne selon
l'algorithme de Bresenham. Julien RF (aka Sasume). Sasume(2005-01-06 21:17:42) En cas de problème avec un article veuillez contacter DIRECTEMENT l'auteur. Merci. |
- Ti FR v3 - Ce site n'est pas le site officiel de texas instruments. En cas de problèmes techniques sur le site veuillez contacter l'administrateur. Merci de vos visites ! |