Algorithme de la ligne Bresenham: Rendu de ligne efficace au pixel près pour la vision par ordinateur

Par Fouad Sabry

Qu'est-ce que l'algorithme de ligne de Bresenham

L'algorithme de ligne de Bresenham est un algorithme de dessin de ligne qui détermine les points d'un raster à n dimensions qui doivent être sélectionnés afin de former un approximation d'une droite entre deux points. Il est couramment utilisé pour dessiner des primitives de ligne dans une image bitmap, car il utilise uniquement l'addition, la soustraction et le décalage de bits d'entiers, qui sont toutes des opérations très bon marché dans les architectures informatiques historiquement courantes. Il s'agit d'un algorithme d'erreur incrémental et l'un des premiers algorithmes développés dans le domaine de l'infographie. Une extension de l'algorithme d'origine appelée algorithme du cercle médian peut être utilisée pour dessiner des cercles.

Comment vous en bénéficierez

(I) Informations et validations sur les sujets suivants :

Chapitre 1 : Algorithme de ligne de Bresenham

Chapitre 2 : Algorithme de dessin de ligne

Chapitre 3 : Algorithme de ligne de Xiaolin Wu

Chapitre 4 : Analyseur différentiel numérique (algorithme graphique)

Chapitre 5 : Algorithme du cercle médian

Chapitre 6 : Règle de chaîne

Chapitre 7 : Dérivée

Chapitre 8 : Pente

Chapitre 9 : Calcul différentiel

Chapitre 10 : Algorithmes de traçage pour l'ensemble de Mandelbrot

(II) Répondre au public principales questions sur l'algorithme de ligne de Bresenham.

(III) Exemples concrets d'utilisation de l'algorithme de ligne de Bresenham dans de nombreux domaines.

À qui s'adresse ce livre

Professionnels, étudiants de premier cycle et des cycles supérieurs, passionnés, amateurs et ceux qui souhaitent aller au-delà des connaissances ou des informations de base pour tout type d'algorithme de ligne de Bresenham.

• Langue: Français
• Éditeur: Un Milliard De Personnes Informées [French]
• Date de sortie: 5 mai 2024

Aperçu du livre

Algorithme de la ligne de Bresenham

Rendu de ligne efficace au pixel près pour la vision par ordinateur

Fouad Sabry est l'ancien responsable régional du développement commercial pour les applications chez Hewlett Packard pour l'Europe du Sud, le Moyen-Orient et l'Afrique. Fouad est titulaire d'un baccalauréat ès sciences des systèmes informatiques et du contrôle automatique, d'une double maîtrise, d'une maîtrise en administration des affaires et d'une maîtrise en gestion des technologies de l'information, de l'Université de Melbourne en Australie. Fouad a plus de 25 ans d'expérience dans les technologies de l'information et de la communication, travaillant dans des entreprises locales, régionales et internationales, telles que Vodafone et des machines professionnelles internationales. Actuellement, Fouad est un entrepreneur, auteur, futuriste, axé sur les technologies émergentes et les solutions industrielles, et fondateur de l'initiative One Billion Knowledge.

Un milliard de connaissances

Algorithme de la ligne de Bresenham

Rendu de ligne efficace au pixel près pour la vision par ordinateur

Fouad Sabry

Copyright

Algorithme © de la ligne de Bresenham 2024 par Fouad Sabry. Tous droits réservés.

Aucune partie de ce livre ne peut être reproduite sous quelque forme que ce soit ou par quelque moyen électronique ou mécanique que ce soit, y compris les systèmes de stockage et de récupération d'informations, sans l'autorisation écrite de l'auteur. La seule exception est celle d'un critique, qui peut citer de courts extraits dans une critique.

Couverture dessinée par Fouad Sabry.

Bien que toutes les précautions aient été prises dans la préparation de ce livre, les auteurs et les éditeurs n'assument aucune responsabilité pour les erreurs ou omissions, ou pour les dommages résultant de l'utilisation des informations contenues dans le présent document.

Table des matières

Chapitre 1 : L'algorithme linéaire de Bresenham

Chapitre 2 : Algorithme de dessin au trait

Chapitre 3 : L'algorithme linéaire de Xiaolin Wu

Chapitre 4 : Analyseur différentiel numérique (algorithme graphique)

Chapitre 5 : Algorithme du cercle médian

Chapitre 6 : Règle en chaîne

Chapitre 7 : Dérivée

Chapitre 8 : Pente

Chapitre 9 : Calcul différentiel

Chapitre 10 : Algorithmes de traçage pour l'ensemble de Mandelbrot

Appendice

À propos de l'auteur

Chapitre 1 : L'algorithme linéaire de Bresenham

L'algorithme linéaire de Bresenham est une procédure de dessin au trait qui identifie les points raster à n dimensions qui doivent être sélectionnés pour approximer une ligne droite entre deux points. Il est fréquemment utilisé pour dessiner des primitives de lignes dans une image bitmap (par exemple, sur un écran d'ordinateur) car il ne nécessite que l'addition d'entiers, la soustraction et le décalage de bits, qui sont toutes des opérations assez peu coûteuses dans les architectures informatiques historiquement répandues. C'est l'un des premiers algorithmes créés dans le domaine de l'infographie et il s'agit d'un algorithme d'erreur incrémentielle. Une modification de l'algorithme d'origine peut être utilisée pour créer des cercles.

Alors que les techniques d'anticrénelage telles que l'algorithme de Wu sont également largement utilisées dans l'infographie moderne, l'algorithme linéaire de Bresenham reste important en raison de sa rapidité et de sa simplicité. L'algorithme est utilisé dans les traceurs et les puces graphiques des cartes graphiques contemporaines. Également présent dans de nombreuses bibliothèques graphiques logicielles. En raison de la simplicité de l'algorithme, il est fréquemment implémenté dans le matériel graphique ou le micrologiciel des cartes graphiques actuelles.

Aujourd'hui, le terme « Bresenham » fait référence à une famille d'algorithmes qui prolongent ou modifient l'approche originale de Bresenham.

L'algorithme linéaire de Bresenham porte le nom de Jack Elton Bresenham, l'employé d'IBM qui l'a créé en 1962. En 2001, Bresenham a publié :

Je travaillais dans le laboratoire de calcul du laboratoire de développement d'IBM à San Jose. Par l'intermédiaire du terminal de la machine à écrire 1407, un traceur Calcomp a été connecté à un IBM 1401. L'algorithme a été utilisé en production à l'été 1962, ou peut-être un mois plus tôt. Calcomp (Jim Newland et Calvin Heft) avaient des copies des programmes parce que les entreprises les partageaient ouvertement à l'époque. Quand je suis retourné à Stanford à l'automne 1962, j'en ai fait don d'un exemplaire à la bibliothèque du centre informatique de Stanford. Lors de la convention nationale de l'ACM de 1963 à Denver, Colorado, une description de la routine de dessin au trait a été acceptée pour présentation. Cette année-là, seul l'ordre du jour des conférenciers et des sujets a été publié dans un numéro de la communication de l'ACM. Après ma présentation, quelqu'un de l'IBM Systems Journal m'a demandé s'ils pouvaient publier le travail. J'ai accepté avec plaisir, et il a été publié en 1965.

L'approche de Bresenham a été élargie pour générer des cercles, des ellipses, des courbes de Bézier cubiques et quadratiques, ainsi que des versions natives anticrénelées de ces courbes.

Les conventions suivantes seront utilisées :

La coordonnée en haut à gauche est (0,0), de sorte que les coordonnées des pixels croissent dans les directions droite et vers le bas (par exemple, le pixel en (7,4) est directement au-dessus du pixel en (7,5)), tandis que la coordonnée en bas à droite est (1,1).

Les centres des pixels ont des coordonnées entières.

Les extrémités de la ligne sont les pixels en et (x_{0},y_{0}) (x_{1},y_{1}) , où la première coordonnée représente la colonne et la seconde la ligne.

L'algorithme ne sera initialement présenté que pour l'octant dans lequel le segment descend et se dirige vers la droite ( x_{0}\leq x_{1} et y_{0}\leq y_{1} ), et sa projection horizontale x_{1}-x_{0} est plus longue que la projection verticale y_{1}-y_{0} (la droite a une pente positive inférieure à 1).

Dans cette huitième, pour chaque colonne x entre x_{0} et x_{1} , La technique calcule exactement une ligne y qui contient un pixel de la ligne, tandis que chaque ligne entre y_{0} et y_{1} peut contenir plusieurs pixels pixellisés.

La technique de Bresenham sélectionne l'entier y qui correspond au centre du pixel le plus proche du y idéal (fractionnaire) pour le même x ; Sur les colonnes suivantes, y peut rester le même ou augmenter de 1. L'équation générale de la droite qui passe par les extrémités est la suivante :

{\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}} .

Puisque nous avons la colonne, x, nous pouvons obtenir la ligne du pixel, y, en arrondissant ce nombre à l'entier le plus proche :

y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}

.

La pente (y_{1}-y_{0})/(x_{1}-x_{0}) ne dépend que des coordonnées de l'extrémité et peut être précalculée, et le y  idéal pour les valeurs entières successives de x peut être calculé à partir de y_{0} la pente et en l'ajoutant de manière répétée.

En pratique, l'algorithme ne maintient pas l'information de coordonnée y, qui augmente de m = ∆y/∆x chaque fois que x augmente d'une unité ; Il maintient une borne d'erreur à chaque niveau, qui indique la distance entre (a) le point où la ligne sort du pixel et (b) le bord supérieur du pixel.

Cette valeur est d'abord définie sur {\displaystyle y_{0}-0.5} (en raison de l'utilisation des coordonnées centrales du pixel), chaque fois que la coordonnée x est incrémentée d'une unité, m est ajouté.

Chaque fois que l'imprécision est supérieure à 0,5, nous sommes conscients que la ligne s'est déplacée d'un pixel vers le haut, nous devons incrémenter la coordonnée y et en soustraire une de l'erreur pour refléter la distance du haut du nouveau pixel.

L'algorithme de Bresenham doit être dérivé en deux étapes. La première étape consiste à traduire la forme pente-ordonnée à l'origine de l'équation d'une droite sous une forme différente, puis à utiliser cette nouvelle équation pour tracer une ligne basée sur le concept d'accumulation d'erreurs.

La forme d'intersection de pente d'une ligne s'écrit sous la forme

y=f(x)=mx+b

où m est la pente et b est l'ordonnée à l'origine.

Comme il s'agit d'une fonction de , x il ne peut pas symboliser une ligne verticale.

Par conséquent, il serait utile de faire en sorte que cette équation s'écrive en fonction de et x y , capable de tracer des lignes à n'importe quel angle.

L'angle (ou la pente) d'une ligne peut être indiqué sous la forme « montée sur course » ou \Delta y/\Delta x .

Ensuite, à l'aide d'opérations algébriques,

{\begin{aligned}y&=mx+b\\y&={\frac {(\Delta y)}{(\Delta x)}}x+b\\(\Delta x)y&=(\Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{aligned}}

Si cette dernière équation est fonction de x et y , elle peut aussi s'écrire comme suit :

{\displaystyle f(x,y):=Ax+By+C=0}

où se trouvent les constantes

{\displaystyle A=\Delta y=y_{1}-y_{0}}{\displaystyle B=-\Delta x=-(x_{1}-x_{0})}{\displaystyle C=(\Delta x)b=(x_{1}-x_{0})b}

La droite est alors définie pour certaines constantes A , B , et C n'importe où f(x,y)=0 .