search

cerjones / dg2d

Boost Software License 1.0
19 stars 4 forks source link

Horizontal lines with some shapes #2

Closed p0nce closed 4 years ago

p0nce commented 4 years ago

Yesterday I've had a bug with some triangle exhibiting an horizontal line across the clip region. Trying to reproduce today but not much luck. It is known?

cerjones commented 4 years ago

It's a bug ive had in the past, there's quite a few situations where it can arise but it's probably to do with clipping as that's the least tested part. I'll have a look tonight see if I can locate the issue.

cerjones commented 4 years ago

Iv'e tried drawing a ton of random triangles with random clip windows and not managed to reproduce the bug. If it happens again could you get a screen shot? Do you remember or know where it was in respect to the clip window? started at left, or on the top or bottom egde?

The line is caused by the fact the delta buffer has to be integrated to get coverage, so one bad cell affects all cells following it.

p0nce commented 4 years ago

I think the shape was with a single triangle or quadrangle looking like this, and the horizontal was on the top scanline:

_________________________________________   <= bug
|\
|  \
|    \  <= intended triangle
|      \
--------

perhaps it was just an unclosed path? I'm unable to reproduce too, I haven't seen it for a good while.

cerjones commented 4 years ago

Hmmm I started out writing that unclosed paths cant happen and then I just realised they can. Although the intMoveTo method will close the previous sub path if there is one, the rasterize method doesn't, so I should add the auto close to rasterize too. That said I suspect it might actually be something to do with the left clip buffer just because of where it occurred.

p0nce commented 4 years ago

Hello,

I can reproduce a failed assertion in the rasterizer with the following triangle:

    float x1 = -4.48518;
    float y1 = 1.69193;
    float x2 = 9.89451;
    float y2 = 0.150122;
    float x3 = -1.97198;
    float y3 = 1.42315;
    gfx_triangle.moveTo(x1,y1).lineTo(x2,y2).lineTo(x3,y3).close();

Then if you fill this path, whatever the fill style it will assert in https://github.com/cerjones/dg2d/blob/master/source/rasterizer.d#L379

I'm continuing investigation, however it seems to become complicated territory. (I can provide a payment for this issue since we are using the rasterizer for a future product, what would you say?)

p0nce commented 4 years ago

image After clipping the two edges that get added are the same. But that shouldn't be a problem?

cerjones commented 4 years ago

Hi, it will be a problem, the edges have to cancel out on the right side of the shape, so in even odd it'll do, on, off, on, and leave the fill on, in non zero it'll do +1, -1, +1, which will be +1 where it should be zero. I will look into it tonight, its likely a clipping problem as there's so many cases to handle most likely I missed something there.

p0nce commented 4 years ago

Great news! At the end of the first offending line (where assert(e == 0) yield false), e == 2. I can try and generate more random triangle, to see the clip cases that get problematic.

p0nce commented 4 years ago

Hello, I've generated more triangles that fail.

For a canvas surface of 48x48

triangle 1
x1 = 49.276596 y1 = 11.177839 
x2 = 12.747784 y2 = 8.287876 
x3 = 50.662491 y3 = 11.286461

triangle 2
x1 = -4.820584 y1 = 34.291153 
x2 = -2.890672 y2 = 34.366234 
x3 = 50.161381 y3 = 36.457401

triangle 3
x1 = 50.861496 y1 = 20.968971 
x2 = -6.823852 y2 = 26.630871 
x3 = 46.685181 y3 = 21.377645

triangle 4
x1 = 46.575394 y1 = 54.352577 
x2 = 18.876856 y2 = 48.298264 
x3 = -5.532673 y3 = 42.964012

triangle 5
x1 = 53.697834 y1 = 37.919582 
x2 = 16.089132 y2 = 46.436161 
x3 = 55.921280 y3 = 37.421677

Let's plot those to see the recurring patterns:

image

cerjones commented 4 years ago

I misunderstood what you meant originally but have reproduced it here and understand now. After clipping the original triangle the clip buffers are empty and the edge table just has two identical edges. seems a bit odd but need to check if clipped coordinates are OK before conversion to edges, then also why rasterize is leaving some leftovers in the delta buffer.

cerjones commented 4 years ago

Checked the math, two identical edges 0,309 --> 2532,38 is correct for that (the triangle in the first post), the two almost coincident edges both intersect the left clip at y=309. The left clip buffer adds the clipped parts each time but it all cancels on the closing line, which is correct. So it's basically a NOP draw. So looks like initial clipping is OK, will have to look further to find what is causing the leftover values in the delta buffer. Will investigate again tomorrow evening.

cerjones commented 4 years ago

Found the problem. With two coincident lines they can cancel out and leave a span of zeros in the delta buffer. As the blitters stop integrating if they hit a span of zeros they can drop out into skipping or solid fill when they shouldn't. This in turn leaves some non-zero stuff in the delta buffer which can cause banding and / or crash in debug mode. Need to think on the best way to fix it, shouldn't be too long.

cerjones commented 4 years ago

Should be fixed now.

p0nce commented 4 years ago

I can confirm one of the repro program to work with the changes here.

p0nce commented 4 years ago

Any way to donate to dg2d ?

cerjones commented 4 years ago

You mean code or financial? To be honest the later wont affect how much time I have to work on it and I'm pretty open to requests / ideas anyway. My main interest is actually audio dsp so I've been following dplug a bit and am willing to prioritise if you have things you need / want for that.

p0nce commented 4 years ago

Oh great!

All in all I'm happy with dg2d and maintaining a fork of it. Dplug APIs are always awkward to use with the mallocNew! and lack of runtime, so I think continuing dg2d is a better idea. I think it's more fruitful to develop dg2d as Dplug will never be as usable as an API with the runtime. I'm not sure I will work on this too much, it already work well! (dplug:canvas is a fork with many small differences to fit Dplug)

One fix I haven't reported yet is the following:

Should gradient repeat or clip? In HTML they clip to 0..255 I can produce a patch that make gradients clipping, and it also allows larger look-ups tables. In dg2d they repeat, it can create oddities I've found. In dplug:canvas, gradients clip , maybe a backport of this fits the library?

Something that would be helpful are:

To be honest the later wont affect how much time I have to work on it and I'm pretty open to requests / ideas anyway. My main interest is actually audio dsp so I've been following dplug a bit and am willing to prioritise if you have things you need / want for that.

Nice! Same for Dplug then ^^ I'm open to suggestions to make it more useful for you!

p0nce commented 4 years ago

example: I currently use the following private helpers to simulate lineWidth in the next product:

void fillLine(ref Canvas canvas, vec2f A, vec2f B, float lineWidth)
{
    float lw = lineWidth * 0.5f;
    vec2f BA = (B - A);
    if (BA.magnitude() < 1e-4f) return;
    BA.normalize();
    vec2f C = A + vec2f(BA.y, -BA.x) * lw;
    vec2f D = A + vec2f(-BA.y, BA.x) * lw;
    vec2f E = B + vec2f(BA.y, -BA.x) * lw;
    vec2f F = B + vec2f(-BA.y, BA.x) * lw;
    canvas.beginPath();
    canvas.moveTo(C.x, C.y);
    canvas.lineTo(D.x, D.y);
    canvas.lineTo(F.x, F.y);
    canvas.lineTo(E.x, E.y);
    canvas.fill();
}

void fillBezier(ref Canvas canvas, vec2f A, vec2f control, vec2f B, float lineWidth)
{
    float lw = 0.5f * lineWidth;
    canvas.beginPath();
    canvas.moveTo(A.x, A.y - lw);
    canvas.quadraticCurveTo(control.x, control.y - lw, B.x, B.y - lw);
    canvas.lineTo(B.x, B.y + lw);
    canvas.quadraticCurveTo(control.x, control.y + lw, A.x, A.y + lw);
    canvas.fill();
}

but it doesn't really work, bezier curve have varying side vector so it should be computed into a different path. What is needed is stroke() and how it work in HTML is much more complicated than expected: https://html.spec.whatwg.org/multipage/canvas.html#trace-a-path

p0nce commented 4 years ago

I ported the fix and all triangles work!

cerjones commented 4 years ago

The plan is for 3 gradient modes, repeat, clip, and mirror, they are pretty simple to implement tbh. larger lookup tables is on the todo, was thinking 1024, not sure if it should just be a global setting, or let the user set as needed? The circular gradient should also be pretty easy, and if it just needs to do circles should be able to optimise a bit better than with ellipses. Stroking is really complicated, and hard to do well. You can easily end up with the stroked edges folding back on themselves and self intersecting. And there's no simple formula for generating offset curves. I have some ideas on it, but not done any actual work yet. I'm currently working on adding some stuff to the path module, rangey type adaptors. Its mostly done so will upload that soon. After that i'll look at the gradients, LUTs, two circle gradient, and then stroking. First 3 should be easy.

p0nce commented 4 years ago

With variable-sized LUT, i've found that reduce size are quite interesting for a retro look :) like 16 elements.

A tip with intel-intrinsics that wasn't clear enough:

You can get the n-th item of a __vector element with: v.array[n]

You can set the n-th item of a __vector element with: v.ptr[n] = x;

Both should be optimized by the compiler, and will lead to less intrinsics being used. This is the way that work across DMD, LDC and even old GDC.