Recherche d'un algorithme de rendu de ligne contourné rapidement

Question

Je cherche un algorithme rapide pour dessiner une ligne soulignée. Pour cette application, le contour doit seulement avoir une largeur de 1 pixel. Il devrait être possible, que ce soit par défaut ou par le biais d'une option, de connecter deux lignes de façon transparente, si elles partagent un point commun.

Excusez l'art ASCII mais c'est probablement le meilleur moyen de le démontrer.

ligne normale:

## 
    ## 
    ## 
     ## 
     ## 
      ## 

ligne "embarquées":

** 
*##** 
**##** 
    **##** 
    **##** 
     **##** 
     **##* 
      ** 

Je travaille sur un dsPIC33FJ128GP802. C'est un petit microcontrôleur/processeur de signal numérique, capable de 40 MIPS (millions d'instructions par seconde). Il est seulement capable de maths entières (addition, soustraction et multiplication: il peut faire la division, mais il prend ~ 19 cycles.) Pour traiter une couche OSD en même temps et seulement 3-4 MIPS du temps de traitement est disponible pour les calculs, la vitesse est critique. Les pixels occupent trois états: noir, blanc et transparent; et le champ vidéo est de 192x128 pixels. C'est pour Super OSD, un projet Open Source:

La première solution que j'ai pensée était de dessiner des rectangles 3x3 avec des pixels soulignés sur le premier passage et des pixels normaux sur la deuxième passe, mais cela pourrait être lent, comme pour chaque pixel d'au moins 3 pixels est écrasé et le temps passé à les dessiner est gaspillé. Donc je cherche un moyen plus rapide. Chaque pixel coûte environ 30 cycles. La cible est < 50 000 cycles pour dessiner une ligne de 100 pixels de longueur.

Answer 1

Je propose ce (mélange C/pseudocode):

void draw_outline(int x1, int y1, int x2, int y2) 
{ 
    int x, y; 
    double slope; 

    if (abs(x2-x1) >= abs(y2-y1)) { 
     // line closer to horizontal than vertical 
     if (x2 < x1) swap_points(1, 2); 
     // now x1 <= x2 
     slope = 1.0*(y2-y1)/(x2-x1); 
     draw_pixel(x1-1, y1, '*'); 
     for (x = x1; x <= x2; x++) { 
      y = y1 + round(slope*(x-x1)); 
      draw_pixel(x, y-1, '*'); 
      draw_pixel(x, y+1, '*'); 
      // here draw_line() does draw_pixel(x, y, '#'); 
     } 
     draw_pixel(x2+1, y2, '*'); 
    } 
    else { 
     // same as above, but swap x and y 
    } 
} 

Modifier: Si vous voulez avoir des lignes successives se connecter de façon transparente, je pense que vous avez vraiment tirer toutes les lignes dans le premier passage , et puis les lignes. J'ai édité le code ci-dessus pour dessiner seulement les contours. La fonction draw_line() serait exactement la même mais avec un seul draw_pixel(x, y, '#'); au lieu de quatre draw_pixel(..., ..., '*');. Et vous venez:

void draw_polyline(point p[], int n) 
{ 
    int i; 

    for (i = 0; i < n-1; i++) 
     draw_outline(p[i].x, p[i].y, p[i+1].x, p[i+1].y); 
    for (i = 0; i < n-1; i++) 
     draw_line(p[i].x, p[i].y, p[i+1].x, p[i+1].y); 
} 

Answer 2

Mon approche serait d'utiliser le Bresenham pour dessiner plusieurs lignes. En regardant votre art ASCII, vous remarquerez que les lignes de contour sont exactement les mêmes que la ligne de Bresenham, juste décalé de 1 pixel de haut en bas - plus un seul pixel à gauche du premier point et à droite du dernier . Pour une version générique, vous devez déterminer si votre ligne est plate ou raide, c'est-à-dire abs(y1 - y0) <= abs(x1 - x0). Pour les lignes raides, les contours sont décalés de 1 pixel vers la gauche et vers la droite, et les pixels de fermeture sont au-dessus du point de départ et en dessous du point de fin.

Il pourrait être intéressant d'optimiser ceci en traçant la ligne et deux pixels de contour en une fois pour chaque pixel de ligne. Cependant, si vous avez besoin de contours sans soudure, la solution la plus simple serait de dessiner d'abord tous les contours, puis les lignes elles-mêmes - ce qui ne fonctionnerait pas avec l'optimisation "trois-pixels-Bresenham".