Dessin au trait anticrénelé rapide

11

L'algorithme de ligne de Bresenham est un moyen de tracer des lignes droites en utilisant uniquement des opérations entières rapides (addition, soustraction et multiplication par 2). Cependant, il génère des lignes aliasées. Existe-t-il un moyen tout aussi rapide de tracer des lignes anti-crénelées?

antialiasing pixel-graphics line-drawing marque
la source
1
Quelques questions ... faites-vous la logique de dessin sur le CPU ou le GPU? Aussi, cherchez-vous des algorithmes basés sur des nombres entiers ou des virgules flottantes?
Alan Wolfe
5
@AlanWolfe, algorithmes entiers sur le CPU - le même environnement pour lequel l'algorithme de Bresenham a été conçu.
Mark
3
en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm est le classique, bien que la page wikipedia soit assez à moitié cuite et que je n'ai pas accès au papier. Cela ressemble à une question paresseuse, car il est assez facile de trouver cela en faisant quelques recherches de base sur Google.
yuriks
2
En pensant à voix haute, je pense qu'il devrait être facile d'adapter Bresenham pour dessiner des lignes de plusieurs pixels. Ensuite, vous pouvez faire l'anti-crénelage en calculant la distance de chaque centre de pixel de la ligne idéale mathématique, et en appliquant une fonction d'atténuation.
Nathan Reed
2
Je ne peux cependant pas marquer un commentaire comme correct.
Mark

Réponses:

9

Existe-t-il un moyen tout aussi rapide de tracer des lignes anti-crénelées?

Non, car par définition, une ligne anti-aliasée touche plus de pixels. Ces algorithmes seront plus lents.

Dans un rasterizer logiciel, la méthode omniprésente pour dessiner des lignes anti-aliasées est l'algorithme de ligne de Xiaolin Wu . Ce n'est pas difficile à implémenter, et de toute façon il y a un pseudocode de qualité inhabituelle sur ce lien.

Dans un tube raster matériel, la primitive de ligne est étendue à un quadrilatère d'espace d'écran par le shader de géométrie par défaut (ou fourni par l'utilisateur), puis dessinée en deux triangles, qui peuvent ensuite être anticrénelés de la manière habituelle.

Dans un raytracer, il existe une variété d'options. Cela vaut la peine de réfléchir à la façon dont vous voulez réellement dessiner un objet 1D. Peut-être comme un cylindre (woo shadows!). Notez que cela introduit des problèmes de perspective / raccourcissement qui peuvent (ou non) être ce que vous voulez. Il n'y a pas de généralisation claire. Alors, évidemment, quoi que vous fassiez, vous le suréchantillonnez.

imallett
la source
"et de toute façon il y a un pseudocode d'une qualité inhabituelle sur ce lien", je ne suis pas d'accord. Ce pseudo-code n'est probablement pas une implémentation appropriée de l'algorithme de Wu même s'il semble être ce qui a été utilisé dans d'innombrables endroits sur le Web. L'algorithme original de Wu a tiré des deux extrémités vers le centre et était en fait plus rapide que celui de Bresenham car il effectue environ la moitié du nombre d'opérations même s'il écrit sur plus de pixels. Je parle de l'algorithme réel de Wu, pas celui publié dans l'article wikipedia lié.
Octopus
@Octopus [Exprime un vague scepticisme, en particulier sur le bit le plus rapide, mais manque de contexte pour réfuter ou confirmer - si tel est le cas, les sources, les corrections et les modifications sont bien sûr les bienvenues.]
imallett
Cela dépend de ce que vous comptez. Si vous dessinez des deux extrémités vers l'intérieur, l'algorithme de Wu effectue la moitié des calculs mais deux fois plus d'écritures de pixels. Voir le tableau 1 dans l'article de Wu, lié sur Wikipedia. Donc, si les écritures de pixels sont coûteuses, comme c'est le cas lors de l'écriture sur un TFT sur une connexion série, alors l'algorithme de Wu est plus cher que celui de Bresenham. (Je dois admettre que je ne vois pas pourquoi l'algorithme de Bresenham ne peut pas aussi utiliser la symétrie.)
Jan-Åke Larsson
1
Mais je suis d'accord avec @Octopus, acceptant même "dessiner d'un bout à l'autre", le pseudocode n'est l'algorithme de Wu que si l'arithmétique entière est utilisée partout. Le code que je vois en ligne utilise l'arithmétique à virgule flottante, ce qui est un changement important. Dans l'article de Wu, l'algorithme utilise uniquement l'arithmétique entière (ou en réalité l'arithmétique à virgule fixe).
Jan-Åke Larsson