smarter merging with octrees

[dankamongmen]

The new octree implementation (see #2503) has a tres shitty merger (we always merge to the most popular, a terrible merger). Improve it, ideally improving performance at the same time somehow, heh. This is not as big a deal as #2515, as this kind of image is fairly rare.

[dankamongmen]

we're likely going to need this in the 3.0.x timeframe, since #2515 is going to put a lot more pressure on our color allocation.

[dankamongmen]

ok, here's how we do this in O(N):

• start with two values, "hi" and "lo", initialized to -1.
• start iterating over the qnodes. we'll be hitting them all, but only through the static 1000. idx is z.
• A: if node is empty, proceed to next
• if node is chosen, node replaces "lo"
• if node is populated but unchosen, and hi is less than z, we need find the next lowest chosen one by walking up from z. if there is no next lowest, hi is reset to -1. otherwise, set hi.
• once we have the new hi > z, determine which of hi and lo are closer to z (discount -1 values), and link the closer one to z
• goto A

simple. the only wrinkle is that iterating over the qnodes means:

• is qnode an onode? if so, iterate over elements of onode
• otherwise, just look at qnode
• each toplevel qnode is worth 8. each second level qnode is worth 1.

[dankamongmen]

w000t!

old:
1214400px Δr 106936936 (88.1) Δg 94246853 (77.6) Δb 122570434 (101)
avg diff per pixel: 267
done with /media/chungus/images/allrgb/balloon.png in 1180.116ms.

new:
1214400px Δr 104101608 (85.7) Δg 95135210 (78.3) Δb 116463896 (95.9)
avg diff per pixel: 260
done with /media/chungus/images/allrgb/balloon.png in 1220.229ms.

that's MUCH better quality and only a little bit of slowdown, huzzah! this slowdown will only happen when we have more colors than we do color registers.

[dankamongmen]

this is ready to go bitches! what a nice win for a monday morning!

[dankamongmen]

closed via #2545