Algorithm for even rendering

Question

I want to write a program that draws a surface (X * Y) evenly.I already have an approach for this at the moment, but it doesn't quite work yet and is also very slow. Since this approach is far too slow, I do not want to pursue it much further.

At the beginning there is always the first point and the last one - so with an area of 10 x 10 the pixel at position 0 and the pixel at position 99.

Then the next best pixel must be found, i.e. the one with the largest distance. This is relatively easy with only two points - (99 - 0 / 2) so 49 or 48.

Now you have to look for the next best one again. So (49 - 0) / 2 or if 48 was taken before (99 - 48) / 2 so 24/25 or 74/75.

This process must be repeated until the correct sequence is found.

0,99,49,74,24,36,61,86,12,42,67,92,6,18,30,55,80,45,70,95,3,9,15,21,27,33,39,52,58,64,77,83,89,47,72,97,1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,50,53,56,59,62,65,68,75,78,81,84,87,90,93,2,5,8,11,14,17,20,23,26,29,32,35,38,41,44,46,48,51,54,57,60,63,66,69,71,73,76,79,82,85,88,91,94,96,98

I also added a small example here, which shows how it should work. The function getElementOrder should be replaced by a mathematical expression to get the fastest possible solution.

// define variables
const width = 20; // this will be > 2100
const height = 20; // this will be > 1600
const size = 20;
let elements = {};

// create all cells
for (let x = 0; x < width; x++) {
    for (let y = 0; y < height; y++) {
        let id = x + y * height;
        let div = document.createElement("div");

        div.style.border = "solid 1px black";
        div.style.width = size + "px"; 
        div.style.height = size + "px";
        div.style.position = "absolute";
        div.style.left = x * size + "px";
        div.style.top = y * size + "px";
        div.style.backgroundColor = "#F0F0F0";

        let textDiv = document.createElement("div");
        textDiv.innerHTML = id;
        textDiv.style.position = "absolute";
        textDiv.style.fontSize = "6pt";
        textDiv.style.top = "1px";
        textDiv.style.right = "1px";

        div.appendChild(textDiv);

        document.body.appendChild(div);

        elements[id] = div;
    }
}


function getElementOrder(width, height) {
    /* BAD SLOW CODE START - This sould be better: */
    const length = width * height;
    const order = [0, length -1];
    const result = [0, length -1];
    while (order.length !== length) {
        let index = 0;
        let diff = 0;
        for (let i = 0, m = order.length - 1; i < m; i++) {
            let localDiff = order[i+1] - order[i];
            if (localDiff > diff) {
                index = i;
                diff = localDiff;
            }
        }

        let offset = Math.floor(diff/2);
        let value = order[index] + offset;
        order.splice(index + 1, 0, value);
        result.push(value);
    }

    return result;
    /* BAD SLOW CODE END */
}

// get the draw order
let order = getElementOrder(width, height);

// change color of each pixel in draw order
let interval = setInterval(() => {
    if (order.length === 0) {
        clearInterval(interval);
        return;
    }
    const value = order.shift();
    elements[value].style.backgroundColor = "#00abab"; 
}, 10);

Are there any mathematical approaches to solve this problem? You are welcome to post better solutions, approaches or links to mathematical formulas for this problem here.

has your pixel only one dimension? please add some more calculation of the first 5 pairs. — Nina Scholz, Mar 27 '18 at 19:30
Is this what is called "ordered dithering"? wikipedia has a page on it. — Arndt Jonasson, Mar 27 '18 at 19:51
The title and example does not make any sense together. What does ti mean evenly? May be I am still sleeping and not getting it right but do you want to render simple line in 2D stored as 1D array? Do you need that silly order of points? if not why not use simple [DDA](https://stackoverflow.com/a/24682318/2521214) (one for cycle no integers only `+,-` operations) ? Or just linear interpolation ? — Spektre, Mar 28 '18 at 07:56

score 0 · Answer 1 · answered Mar 27 '18 at 20:00

I think I get what you're trying to accomplish, and what the underlying routine is. The way I see it, you're probably overcomplicating the question of "finding the biggest distance", since from what I can see, what you're basically doing is halving increasingly fine intervals.

So, here's my version:

function getElementOrder(width, height) {
    const length = width * height;
    const order = [ 0 ];
    for (let denominator = 2; order.length < length; denominator *= 2) {
        for (let enumerator = 1; enumerator < denominator; enumerator += 2) {
            order.push(Math.round(length * enumerator / denominator));
        }
    }
    return order;
}

I'm using very long and clunky variable names to make the principle behind it clearer: if you project the entire interval of [0, width*height] to the interval of [0, 1] then what you're doing is adding 1/2, then 1/4 and 3/4, then 1/8 and 3/8 and 5/8 and 7/8, and so on; each time you multiply the denominator by 2, and take all the odd-numbered multiples.

(Addendum: you can probably squeeze even better performance out of it by using a fixed-length TypedArray for the results, and adding elements by index instead of using .push(). I just didn't want to obscure the gist of the solution with the additional loop variable and such.)

Algorithm for even rendering

1 Answers1