Transparent blitting doesn't properly stack #1068
Comments
|
So to do this right, you absolutely have to do it in
The EGC is always solved for by this time, but one or both of the colors are not yet solved. So essentially as you're descending, you need to identify cases where the background vs. foreground were chosen arbitrarily, and both are in use, and your unsolved area is within their foreground area. This can only be the case for half blocks (upper, lower, left, or right), quarter blocks (all four), and three-quarter blocks (again all four) (and since Unicode 13 -- see #137 -- the sixth blocks) -- spaces vs full blocks only use one of bg or fg (and we always generate spaces, so we always get bg, which works by itself), and no other glyphs have symmetry across bg/fg regions. (I leave aside the case of, e.g. a space being written with both colors transparent. Imagine that there is a half block underneath it. Whatever we solve for the foreground will be ignored; only the background matters here. Which color do we take? Always the background? Perhaps. Now imagine we have a three-quarter underneath it. Ought we take the foreground, since that would dominate in the space's absence? Or the background, despite only being a quarter of the cell? I think always the background in both cases here, and for all other glyphs not closed under inversion within Unicode.) and there are cases we can't get exactly right. imagine we have a RIGHT HALF BLOCK atop a THREE-QUARTERS BLOCK ocupying the lower left and both right quarters. The RIGHT HALF BLOCK leaves the left hand side in its entirety transparent. What color ought the left hand side get? Here again I say we default to the background, since we must somehow break the symmetry. So in
yessssss, i think that works. @grendello , @dcantrell , hell @dcantrell , i'd like some additional eyes on this problem and plan. it's very subtle. |
|
...can't decide whether i want to block 2.1.0 on this... |
|
I just saw this now...oops. While I've been playing with notcurses on the side, I have not had a lot of time to dig in to the details and really haven't had time to look in to this one. So as of right now I have no opinion. I am taking a lot of time off this December, so I'll probably have time to catch up on !work, but I can't promise anything. |
no worries at all man, was just inviting your comments as a respected computer scientist =]. |
|
so i think the first thing to do is to make some solid unit tests around this, and make them |
|
I've added the |
|
I really want to get this done for 2.2.0, where it's the last major remaining feature. |
For properly stacking transparent blittings (#1068), we need tag those cells which both (1) originated in an ncvisual operation and (2) have some transparency. For the three affected blitters (halfblock, quadrant, and sexblitter), call cell_set_blitted().
We need track whether we've entered blitterstacking mode across the paint() of a given cell. This means stashing it in the crender rvec #1068.
|
I've started moving on this. I've added I've added |
Iff cell_blitted_p() when we select the glyph in paint(), we ought enter blitter stacking mode. Make this decision in paint() #1068.
|
So what remains is to amend If we do those maps in O(1), this is all O(1), and only ever touched where necessary. |
|
I'm now doing the inversion in |
|
OK, so for the last part, here's what I'm thinking. We can't do a conditionless O(1) map so far as I can tell. But we can get pretty close, with O(1) using four conditions. There's no point in doing this when we set so, when you hit all three parts of the blitter stacking conditional, you look up a map set based on the chosen glyph, and a secondary set based on the current glyph. i don't think this can be parallelized. the O(1)+4cond lookup involves getting an index from the glyph. you need the four conditionals to determine whether the glyph is in the half, quad, or sex range of Unicode. then you take a difference against the range base, add it to the skipped count, and get your index. this is done twice to find the correct map entry, which will be precomputed (this will require 5041 bytes assuming one byte per map entry, nothing doing). the map entry is, as mentioned above, {NORMAL, INVERT, TRANS}. if NORMAL, use the background color. if INVERT, use the foreground color. if TRANS....oh, i think we can do without TRANS, actually? that's just NORMAL + local trans. so that's a single bit. we could do 631 bytes if we used a bit per entry. ok, i think this is a good plan. this ought solve the deep problem of transparent blitter stacking, and do it all in O(N) time and O(1) space. the O(N) time refers to N planes deep, when 99.999% of the time we'll only touch one plane. we add a total of 1 conditional per plane that's not affected, and 9 conditionals per plane that is affected, and this will be a very rare effect. i like it. |
|
I think we can actually do this without the full map. We can just track the possible regions, associate them with each piece, and do the bitwise calculation. That drops us to a byte or less per glyph, so fewer than 100 total bytes. |
|
If we keep it down to 8 regions or fewer (done by definition), we can just encode this directly into the nccell, and we don't need any additional space. yes! |
|
So we currently have 6 free bits in the 64-bit channels. We could add a quadrant bitmask and have 2 left. Can we reclaim any existing ones?
so we have 6 free bits, and we're using 4, but we're reclaiming two, with a net result of four free bits. i think it's worth it to get a no-spacecost solution to this vexing bug. |
|
it's safe to change the meaning of those bits, as they were never exposed to the user. it's unsafe however, from an ABI perspective, to go shuffling bits around arbitrarily like i was starting to do in this branch, argh. reverting all that noise. |
|
i believe we have a good fix! |
This completes the work for #1068. This addressed a subtle issue. When we're using pixel->semigraphic art, we want slightly different rendering. Essentially, imagine that we have two images, each two pixels tall and one pixel wide. The top image is a transparent pixel above a white pixel. The bottom image is a white pixel above a black pixel. We'd expect the result to be two white pixels, but we can instead get a black pixel above a white pixel. This is because the *background* color is being merged from the bottom plane, but really we want the *top* color. Ncvisuals are now blitted along with information regarding which quadrants they draw over, and when appropriate, we invert the foreground and background. Closes #1068.
|
all unit tests pass, and there is no measurable performance impact on ...in fact... |
For properly stacking transparent blittings (#1068), we need tag those cells which both (1) originated in an ncvisual operation and (2) have some transparency. For the three affected blitters (halfblock, quadrant, and sexblitter), call cell_set_blitted().
We need track whether we've entered blitterstacking mode across the paint() of a given cell. This means stashing it in the crender rvec #1068.
Iff cell_blitted_p() when we select the glyph in paint(), we ought enter blitter stacking mode. Make this decision in paint() #1068.
Reclaim the "blitted" and "full foreground" bits in the channels. Instead, we now write four bits, encoding the four quadrants we might occupy as the result of a blit. These four imply the previous two, leaving us with four free bits remaining in the channels. This opens a clear path to O(1)-time, zero-space blitter stacking #1068. w00t!
This completes the work for #1068. This addressed a subtle issue. When we're using pixel->semigraphic art, we want slightly different rendering. Essentially, imagine that we have two images, each two pixels tall and one pixel wide. The top image is a transparent pixel above a white pixel. The bottom image is a white pixel above a black pixel. We'd expect the result to be two white pixels, but we can instead get a black pixel above a white pixel. This is because the *background* color is being merged from the bottom plane, but really we want the *top* color. Ncvisuals are now blitted along with information regarding which quadrants they draw over, and when appropriate, we invert the foreground and background. Closes #1068.
|
OK, i've found weird behavior in |
|
Figured out what was wrong -- we wanted to invert the bits, not invert the logical result -- ~, not !. Doh! Ready to merge. |
For properly stacking transparent blittings (#1068), we need tag those cells which both (1) originated in an ncvisual operation and (2) have some transparency. For the three affected blitters (halfblock, quadrant, and sexblitter), call cell_set_blitted().
We need track whether we've entered blitterstacking mode across the paint() of a given cell. This means stashing it in the crender rvec #1068.
Iff cell_blitted_p() when we select the glyph in paint(), we ought enter blitter stacking mode. Make this decision in paint() #1068.
Reclaim the "blitted" and "full foreground" bits in the channels. Instead, we now write four bits, encoding the four quadrants we might occupy as the result of a blit. These four imply the previous two, leaving us with four free bits remaining in the channels. This opens a clear path to O(1)-time, zero-space blitter stacking #1068. w00t!
This completes the work for #1068. This addressed a subtle issue. When we're using pixel->semigraphic art, we want slightly different rendering. Essentially, imagine that we have two images, each two pixels tall and one pixel wide. The top image is a transparent pixel above a white pixel. The bottom image is a white pixel above a black pixel. We'd expect the result to be two white pixels, but we can instead get a black pixel above a white pixel. This is because the *background* color is being merged from the bottom plane, but really we want the *top* color. Ncvisuals are now blitted along with information regarding which quadrants they draw over, and when appropriate, we invert the foreground and background. Closes #1068.
This was first discovered in #1065, and I've made it its own bug. This is independent of quadblitter (it can also happen with halfblitter). See the image below:
So each place where we have the invalid green is a cell from
CelesF.pngwhere we have a transparent pixel above a non-transparent pixel, and the corresponding map area has two black pixels above two green pixels. So in such a case, the quadblitter/halfblitter is going to solve for a bottom half with appropriate foreground and transparent background for the top plane. The bottom plane then cheerfully sets the background to its solved background, which is, of course, green (since it always emits lower halves). This problem exists even if we always emit upper as opposed to lower half blocks (which we can't do anyway, as it screws up transparency) -- quadblitter could emit say a bottom+right triblock. Well, shit. This is a deep problem, and solving it correctly will require some extensive plumbing. We'd basically need to recognize that we are serving as the background of any already-selected, independent glyph, figure out what color of ours dominates the uncovered area, and make that our background color. That's the fully general solution, of course; we can probably get by with just the simple geometry of quadblitting. Still kinda delicate and subtle, though.The text was updated successfully, but these errors were encountered: