Brainfart: 0x86 CPU; line rasterization algorithm performance

[K.I.L.E.R]

Replaced raster writing with a 2D int array, new times:

Avg time bres: 11003.051580000001
Avg time dda: 11338.594620000002
Avg time NEW DDA: 24416.42683

 

[Simon F]

It's slower than the last 2 algorithms. :/
I thought itneger division was faster than that.

Division is slow regardless of whether it is floating point or integer.... unless you are using a particular divisor. That is why I said to use fixed point maths.

Your divisor then becomes a power of two and, hence, is just a shift operator. In fact, you need to use a shift operator so that you get a round towards -INF rather than a round towards zero.

 

[Simon F]

i'd also say,,
is that how the dda is coded?? i dont remember having a "/" in the loop!?

Hey we're dealing with Kiler here... it will take a while....

 

[K.I.L.E.R]

I'm reading about fixed point arithmetic right now:
http://en.wikipedia.org/wiki/Fixed-point_arithmetic

 

[d-f-b]

I'm reading about fixed point arithmetic right now:
http://en.wikipedia.org/wiki/Fixed-point_arithmetic

blimey

now i dont understand it

 

[ERP]

No. Just wanting to see the performance between the 2 and I ended up getting free tips on performance. Here is my revised algorithm.

* 1/1e3 due to numerical issues. (Overflow)

Math proof:
y = dy/dx * x + c; c = 0
*dx => dx.y = dy.x
solve for dy and dx:
dy = dx.dy / x
dx = dy.dx/y

m = dy/dx

Sub:
m = y^2.dx / x^2.dy

Numerically to avoid floating point computations, break apart the fraction.

[B]int yi = y1;
        int dx = x2 - x1;
        int dy = y2 - y1;
        int ySqr = dy * dy;
        int xSqr = dx * dx;
        int topFract = (ySqr*dx) / 1000;
        int fraction = (xSqr*dy) / 1000;
        
        yi /= 1000;
        
        for (int x = x1; x < x2; x++) {
            image.getRaster().setPixel(x, yi/fraction, data);
            yi += topFract;
        }[/B]

It's slower than the last 2 algorithms. :/
I thought itneger division was faster than that.

Your algorythm doesn't work for lines over 45 degrees, you need to establish the primary axis, and compute on the other one.

 

[K.I.L.E.R]

The idea is to get it fast, then I'm satisfied. I don't actually need the algorithm for anything.