Breshenem Concentric Circles Leave Blank Pixels

Question

I use the circle circumference algorithm, also known as Bresenham's, to draw concentric circles. The difference between each radius of the circle and the number of the next is always 1, so the final result should be a complete circular region.

However, some pixels remain blank, as shown in the attached image.

I use Javascript to draw on HTML5 canvas by manipulating canvas.getContext ("2d"). array of the getImageData (...) data array.

The circles are alternatively white and red, and the empty pixels are black. You may need to zoom in to see what I mean.

I am trying to add some code to the algorithm so that these pixels are filled when drawing the corresponding arc. There seems to be no reason that any of these pixels belong to one arc and not the next, so I don’t care if they are filled together with arcs with an even radius or with arcs with an odd radius (I hope I let myself know )

The pixels seem to follow the pattern, but I don't know what it could be. Can someone help me find it?

function drawCircles(radius, x, y){ var f = 1 - radius; var ddF_x = 1; var ddF_y = -2 * radius; var x = 0; var y = radius; //Colors var red = 255; var green = radius%2==0?255:0; var blue = radius%2==0?255:0; paintPixel(x, y + radius, red, green, blue); paintPixel(x, y - radius, red, green, blue); paintPixel(x + radius, y, red, green, blue); paintPixel(x - radius, y, red, green, blue); while(x < y){ // ddF_x == 2 * x + 1; // ddF_y == -2 * y; // f == x*x + y*y - radius*radius + 2*x - y + 1; if(f >= 0) { y--; ddF_y += 2; f += ddF_y; } x++; ddF_x += 2; f += ddF_x; paintPixel(x + x, y + y, red, green, blue); paintPixel(x - x, y + y, red, green, blue); paintPixel(x + x, y - y, red, green, blue); paintPixel(x - x, y - y, red, green, blue); paintPixel(x + y, y + x, red, green, blue); paintPixel(x - y, y + x, red, green, blue); paintPixel(x + y, y - x, red, green, blue); paintPixel(x - y, y - x, red, green, blue); } } function paintPixel(x, y, red, green, blue){ imageData.data[grid[y][x]] = red; imageData.data[grid[y][x]+1] = green; imageData.data[grid[y][x]+2] = blue; imageData.data[grid[y][x]+3] = 255; //Alpha } 

Answer 1

Bresenham is designed to draw a line using a single pixel in n-pixel areas. At 45 degrees, he will build one pixel, then another (+ 1, + 1). This gives an average thickness between the centers of two pixels 1 / & radic; 2. An accurate graph of a line with a thickness of one pixel has a thickness of 1. Black dots are due to this difference between the line thickness of the Breshenem algorithm and the true thickness.

If you enlarge the pixels built to include all the pixels intersecting the center of the true line, it should not have spaces, as its thickness will never be less than one. One way to do this is to use Bresenham twice with internal and external radii and plot the pixels based on the difference between them.

Answer 2

If you create your own Breshenem style circle box to calculate border outlines instead of pixels, you can create circles that nest perfectly. Conceptually, a border contour is a list of pixel edges, not pixel centers. This works well for operations in the Bresenham style: register a horizontal edge with increasing x-coordinate and a vertical edge with increasing y-coordinate.

For each circle, calculate two outer_radius : one for outer_radius and again for (outer_radius - pen_diameter) . Draw pixels between two paths: with a small amount of skill, you should be able to run both path generators in a single cycle, and do the drawing in pixels online.

Of course, circles drawn using this boundary technique will look different than created circles. However, IIRC, the boundary technique can be more reliable than the direct technique, anyway ...

Answer 3

This seems like a problem with an alias. Since the missing pixels seem denser at a 45 ° angle, I suspect that the root problem is related to distance calculations. Diagonally, the distance on the pixel is about 41% greater than when measured along the axes. This can cause the center of the pixels to be farther from the circle. Without seeing your code, it's hard to say more.

One fix can only be to simply fill the circle with one color and then simply draw a different color for the circle.

Answer 4

 <canvas width="500" height="500" style="background:#000;"> </canvas>​ var canvas = $("canvas")[0]; var cen = $("canvas").width()/2; var len = cen, i = len; var ctx = canvas.getContext("2d"); var red = "#f00"; var white = "#fff"; for (; i > 0; i--){ ctx.beginPath(); ctx.arc(cen, cen, i, 0, 2 * Math.PI, false); ctx.fillStyle = i % 2 ? red : white; ctx.fill(); }​ 

http://jsfiddle.net/RmHC3/

There are no black dots. :)

Answer 5

Ok, I teach Assembly language at the University of Technology of Honduras (UTH), and for some reason I tried to draw lines and circles, but I tried to find an algorithm other than Bresenham, and I found these (for lines and circle) that solve these holes in the original Breshenem when you fill circles with concentric circles or when you fill rectangles with sloping lines.

Note1: This algorithm does not match SuperCoron's algorithm, but you can use it for the same purpura.

Note2: I use an integer arithmetic and logic function to complete the tasks.

This is a screenshot (using Emu8086 in Windows XP VirtualBox and compiling the program into a .exe file).

This code needs to be optimized, but because it is designed for training, I just program it so that students can easily understand.

  data segment ; Las variables que comienzan con _ son variables usadas en los procedimientos _migaja dw ? _x dw ? _y dw ? _x2 dw ? _y2 dw ? _color dw ? _deltaX dw ? _deltaY dw ? _deltaX_abs dw ? _deltaY_abs dw ? _error dw ? _error_x dw ? _error_y dw ? _error_xy dw ? _error_x_abs dw ? _error_y_abs dw ? _error_xy_abs dw ? _cambio_y dw ? _color_inicial db ? _color_relleno db ? _xc dw ? _yc dw ? _radio dw ? ; Variables usadas en la parte principal i dw ? xcentro dw 160 ycentro dw 100 radio dw 1 color dw 0 ends stack segment dw 32767 dup(0) ends code segment start: mov ax, data mov ds, ax mov es, ax call videoMode mov color, 10 pre_ciclo: mov radio, 0 ciclo: cmp radio, 100 jge salir_ciclo push xcentro push ycentro push radio push color call circulo inc radio jmp ciclo salir_ciclo: mov ah, 1 int 21h mov ax, 4c00h int 21h ends videoMode PROC mov ah, 0 mov al, 13h int 10h ret ENDP setPixel PROC pop _migaja pop ax pop dx pop cx push _migaja mov ah, 0Ch int 10h ret ENDP circulo PROC ; Este procedimiento dibuja un circulo en (x,y) de radio r ; Hecho por Ing. Yury Euceda© para los alumnos de UTH Agosto 2014 pop _migaja pop _color pop _radio pop _yc pop _xc push _migaja ; Defino el error inicial pre_ciclo_circle: mov _error, 0 mov _x, 0 mov ax, _radio mov _y, ax ciclo_circulo: push cx mov cx, _x add cx, _xc mov dx, _yc add dx, _y mov ax, _color mov ah, 0Ch int 10h push dx mov dx, _yc sub dx, _y int 10h push cx mov cx, _xc sub cx, _x int 10h pop cx pop dx mov cx, _xc sub cx, _x int 10h pop cx cmp _y, 0 je salir_ciclo_circulo ; Calculo error si suben ambos mov ax, _x shl ax, 1 inc ax add ax, _error mov _error_x, ax mov _error_x_abs, ax mov _error_xy, ax mov _error_xy_abs, ax mov ax, _y shl ax, 1 neg ax inc ax add _error_xy, ax add _error_xy_abs, ax add ax, _error mov _error_y, ax mov _error_y_abs, ax ; Calculo los valores absolutos de los errores cmp _error_x_abs, 0 jge continuar1_circulo neg _error_x_abs continuar1_circulo: cmp _error_y_abs, 0 jge continuar2_circulo neg _error_y_abs continuar2_circulo: cmp _error_xy_abs, 0 jge continuar3_circulo neg _error_xy_abs continuar3_circulo: ; Ahora voy a decidir que error absoluto es el menor inc _x dec _y mov ax, _error_xy mov _error, ax mov ax, _error_xy_abs compare_a_b_circulo: cmp ax, _error_y_abs ; compare a con b jg compare_b_c_circulo ; si a > b compare b con c cmp ax, _error_xy_abs ; sino compare a con c jg continuar_loop_circulo ; si es mayor continue loop inc _y mov ax, _error_x mov _error, ax jmp continuar_loop_circulo compare_b_c_circulo: mov ax, _error_y_abs cmp ax, _error_xy_abs jg continuar_loop_circulo dec _x mov ax, _error_y mov _error, ax continuar_loop_circulo: jmp ciclo_circulo salir_ciclo_circulo: ret ENDP linea PROC ; Este procedimiento dibuja una linea desde (x1,y1) hasta (x2,y2) ; Hecho por Ing. Yury Euceda© para los alumnos de UTH Agosto 2014 pop _migaja pop _color pop _y2 pop _x2 pop _y pop _x push _migaja mov ax, _x cmp ax, _x2 jle calcular_deltaX xchg ax, _x2 mov _x, ax mov ax, _y xchg ax, _y2 mov _y, ax calcular_deltaX: ; Calculo deltaX = X2 - X mov ax, _x2 sub ax, _x mov _deltaX, ax mov _deltaX_abs, ax cmp ax, 0 jge calcular_deltaY neg _deltaX_abs calcular_deltaY: ; Calculo deltaY = Y2 - Y mov ax, _y2 sub ax, _y mov _deltaY, ax mov _deltaY_abs, ax cmp ax, 0 jge calcular_cambio neg _deltaY_abs calcular_cambio: mov _cambio_y, 1 cmp _deltaY, 0 jge pre_ciclo_linea neg _cambio_y ; Defino el error inicial pre_ciclo_linea: mov _error, 0 mov ax, _deltaY_abs cmp _deltaX_abs, ax jge asignar_deltaX mov cx, _deltaY_abs inc cx jmp ciclo_linea asignar_deltaX: mov cx, _deltaX_abs inc cx ciclo_linea: push cx push _x push _y push _color call setPixel pop cx ; Calculo error si suben ambos mov ax, _error add ax, _deltaY_abs ; ax = error + deltaY mov _error_x, ax mov _error_x_abs, ax sub ax, _deltaX_abs ; ax = error + deltaY - deltaX mov _error_xy, ax mov _error_xy_abs, ax sub ax, _deltaY_abs ; ax = error - deltaX mov _error_y, ax mov _error_y_abs, ax ; Calculo los valores absolutos de los errores cmp _error_x_abs, 0 jge continuar1 neg _error_x_abs continuar1: cmp _error_y_abs, 0 jge continuar2 neg _error_y_abs continuar2: cmp _error_xy_abs, 0 jge continuar3 neg _error_xy_abs continuar3: comparar_x_con_y: mov ax , _error_y_abs cmp _error_x_abs, ax jge comparar_y_con_xy mov ax , _error_xy_abs cmp _error_x_abs, ax jg cambiar_xy inc _x mov ax, _error_x mov _error, ax jmp continuar_loop comparar_y_con_xy: mov ax , _error_xy_abs cmp _error_y_abs, ax jge cambiar_xy mov ax, _cambio_y add _y, ax mov ax, _error_y mov _error, ax jmp continuar_loop cambiar_xy: inc _x mov ax, _cambio_y add _y, ax mov ax, _error_xy mov _error, ax continuar_loop: loop ciclo_linea ret ENDP rellenar PROC pop _migaja pop ax pop dx pop cx push _migaja mov _color_relleno, aL mov ah, 0Dh int 10h mov _color_inicial, aL ; Llamo la recursiva push cx push dx call rellenar_recursiva pop dx pop cx ret ENDP rellenar_recursiva PROC pop _migaja ; Saco los parametros de la pila pop dx pop cx ; Vuelvo a meterlos a la pila :) push cx push dx push _migaja ; valido que el punto este en rango cmp cx, 0 jl salir_rellenar cmp cx, 319 jg salir_rellenar cmp dx, 0 jl salir_rellenar cmp dx, 199 jg salir_rellenar ; Extraigo el color del pixel en CX,DX mov ah, 0Dh int 10h ; Lo comparo con el color inicial cmp _color_inicial, aL ; Si no es igual salgase jne salir_rellenar ; Si es igual entonces lo pinto mov aL, _color_relleno mov ah, 0Ch int 10h ; Pinto el norte dec dx push cx push dx call rellenar_recursiva pop dx pop cx inc dx ; Pinto el este inc cx push cx push dx call rellenar_recursiva pop dx pop cx dec cx ; Pinto el sur inc dx push cx push dx call rellenar_recursiva pop dx pop cx dec dx ; Pinto el oeste dec cx push cx push dx call rellenar_recursiva pop dx pop cx inc cx salir_rellenar: ret ENDP end start