Algoritmo de dibujo lineal rápido

La tarea es encontrar una manera de dibujar una línea horizontal en una matriz de enteros de 16 bits.

Asumimos una matriz de 256x192 píxeles con 16 píxeles por palabra. Una línea es una serie contigua de bits set (1). Las líneas pueden comenzar en el medio de cualquier palabra, superponerse con otras palabras y terminar en cualquier palabra; También pueden comenzar y terminar en la misma palabra. Es posible que no se envuelvan a la siguiente línea. Sugerencia: las palabras intermedias son fáciles: solo escriba 0xffff, pero los bordes serán complicados, al igual que manejar el caso para el inicio y el final en la misma palabra. Una función / procedimiento / rutina debe tomar una coordenada x0 y x1 que indique los puntos de inicio y parada horizontales, así como una coordenada ay.

Me excluyo de esto porque diseñé un algoritmo casi idéntico para un procesador integrado, pero tengo curiosidad por saber cómo lo harían otros. Puntos de bonificación por usar operaciones relativamente rápidas (por ejemplo, una operación de multiplicación de 64 bits o de coma flotante no sería rápida en una máquina integrada, pero un simple cambio de bits sería).

Este código supone que tanto x0 como x1 son puntos finales inclusivos, y que las palabras son little endian (es decir, el (0,0) píxel se puede establecer con array[0][0]|=1).

int line(word *array, int x0, int x1, int y) {
  word *line = array + (y << 4);
  word *start = line + (x0 >> 4);
  word *end = line + (x1 >> 4);
  word start_mask = (word)-1 << (x0 & 15);
  word end_mask = (unsigned word)-1 >> (15 - (x1 & 15));
  if (start == end) {
    *start |= start_mask & end_mask;
  } else {
    *start |= start_mask;
    *end |= end_mask;
    for (word *p = start + 1; p < end; p++) *p = (word)-1;
  }
}

Pitón

El truco principal aquí es usar una tabla de búsqueda para almacenar máscaras de bits de los píxeles. Esto ahorra algunas operaciones. Una tabla de 1kB no es tan grande incluso para una plataforma integrada en estos días

Si el espacio es realmente limitado, por el precio de un par de & 0xf, la tabla de búsqueda se puede reducir a solo 64B

Este código está en Python, pero sería fácil de transferir a cualquier lenguaje que admita operaciones de bits.

Si usa C, podría considerar desenrollar el bucle usando el dispositivoswitch de Duff . Como la línea tiene un máximo de 16 palabras de ancho, extendería las switch14 líneas y prescindiría del whiletotal.

T=[65535, 32767, 16383, 8191, 4095, 2047, 1023, 511,
   255, 127, 63, 31, 15, 7, 3, 1]*16
U=[32768, 49152, 57344, 61440, 63488, 64512, 65024, 65280,
   65408, 65472, 65504, 65520, 65528, 65532, 65534, 65535]*16

def drawline(x1,x2,y):
    y_=y<<4
    x1_=y_+(x1>>4)
    x2_=y_+(x2>>4)
    if x1_==x2_:
        buf[x1_]|=T[x1]&U[x2]
        return    
    buf[x1_]|=T[x1]
    buf[x2_]|=U[x2]        
    x1_+=+1
    while x1_<x2_:
        buf[x1_] = 0xffff
        x1_+=1


#### testing code ####

def clear():
    global buf
    buf=[0]*192*16

def render():
    for y in range(192):
        print "".join(bin(buf[(y<<4)+x])[2:].zfill(16) for x in range(16))


clear()
for y in range(0,192):
    drawline(y/2,y,y)
for x in range(10,200,6):
    drawline(x,x+2,0)
    drawline(x+3,x+5,1)
for y in range(-49,50):
    drawline(200-int((2500-y*y)**.5), 200+int((2500-y*y)**.5), y+60)
render()

Aquí hay una versión C de mi respuesta de Python usando la instrucción switch en lugar del ciclo while y la indexación reducida al incrementar un puntero en lugar del índice de matriz

El tamaño de la tabla de búsqueda se puede reducir sustancialmente usando T [x1 y 0xf] y U [x2 y 0xf] para un par de instrucciones adicionales

#include <stdio.h>
#include <math.h>

unsigned short T[] = {0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001};

unsigned short U[] = {0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff};

unsigned short buf[192*16];

void clear(){
    int i;
    for (i=0; i<192*16; i++) buf[i]==0;
}

void render(){
    int x,y;
    for (y=0; y<192; y++){
        for (x=0; x<256; x++) printf("%d", (buf[(y<<4)+(x>>4)]>>(15-(x&15)))&1);
        printf("\n");
    }
}

void drawline(int x1, int x2, int y){
    int y_ = y<<4;
    int x1_ = y_+(x1>>4);
    int x2_ = y_+(x2>>4);
    unsigned short *p = buf+x1_;

    if (x1_==x2_){
        *p|=T[x1]&U[x2];
        return;
        }

    *p++|=T[x1];
    switch (x2_-x1_){
    case 14: *p++ = 0xffff;
    case 13: *p++ = 0xffff;
    case 12: *p++ = 0xffff;
    case 11: *p++ = 0xffff;
    case 10: *p++ = 0xffff;
    case 9: *p++ = 0xffff;
    case 8: *p++ = 0xffff;
    case 7: *p++ = 0xffff;
    case 6: *p++ = 0xffff;
    case 5: *p++ = 0xffff;
    case 4: *p++ = 0xffff;
    case 3: *p++ = 0xffff;
    case 2: *p++ = 0xffff;
    case 1: *p++ = U[x2];
    }     
}


int main(){
    int x,y;
    clear();

    for (y=0; y<192; y++){
        drawline(y/2,y,y); 
    }

    for (x=10; x<200; x+=6){
        drawline(x,x+2,0);
        drawline(x+3,x+5,1);
    }

    for (y=-49; y<50; y++){
        x = sqrt(2500-y*y);
        drawline(200-x, 200+x, y+60);
    }
    render();
    return 0;
    }

Scala, 7s / 1M líneas 4.1s / 1M líneas

// declaration and initialisation of an empty field: 
val field = Array.ofDim[Short] (192, 16) 

primera implementación:

// util-method: set a single Bit:
def setBit (x: Int, y: Int) = 
  field (y)(x/16) = (field (y)(x/16) | (1 << (15 - (x % 16)))).toShort 
def line (x0: Int, x1: Int, y: Int) = 
  (x0 to x1) foreach (setBit (_ , y))

Después de eliminar la llamada al método interno, y reemplazar el for- con un ciclo while, en mi 2Ghz Single Core con Scala 2.8, absuelve 1 Mio. Líneas en 4.1s sec. en lugar de los 7 iniciales.

  def line (x0: Int, x1: Int, y: Int) = {
    var x = x0
    while (x < x1) {  
      field (y)(x/16) = (field (y)(x/16) | (1 << (15 - (x % 16)))).toShort
      x += 1
    }
  }

Código de prueba e invocación:

// sample invocation:
line (12, 39, 3) 
// verification 
def shortprint (s: Short) = s.toBinaryString.length match {          
  case 16 => s.toBinaryString                                          
  case 32 => s.toBinaryString.substring (16)                           
  case x  => ("0000000000000000".substring (x) + s.toBinaryString)}

field (3).take (5).foreach (s=> println (shortprint (s)))            
// result:
0000000000001111
1111111111111111
1111111100000000
0000000000000000
0000000000000000

Pruebas de rendimiento:

  val r = util.Random 

  def testrow () {
    val a = r.nextInt (256)
    val b = r.nextInt (256)
    if (a < b)
      line (a, b, r.nextInt (192)) else
        line (b, a, r.nextInt (192)) 
  }

  def test (count: Int): Unit = {
    for (n <- (0 to count))
      testrow ()
  }

  // 1 mio tests
  test (1000*1000) 

Probado con el tiempo de la herramienta Unix, comparando el tiempo de usuario, incluido el tiempo de inicio, el código compilado, sin fase de inicio de JVM.

El aumento de la cantidad de líneas muestra que, por cada millón nuevo, necesita 3.3 s adicionales.