elements.comp scene traversal may leave gaps in paths

[eliasnaur]

The fill algorithm implemented by path_coarse.comp assumes that closed paths contain no gaps. Unfortunately, the non-deterministic scene tracersal in elements.comp may introduce gaps in otherwise gap-less paths.

Consider two fill path segments through endpoints A, B, C in a scene fragment with three preceding transforms. The segments are initialized with the identity transform, I.

T₁·T₂·T₃·S(I, A, B)·S(I, B, C)

Since scene element operations are associative, elements.comp evaluates them in a GPU-friendly but non-deterministic order. In particular, it may use the ordering

S((T₁·T₂)·T₃, A, B)·S(T₁·(T₂·T₃), B, C)

Because of numerical imprecision, the path segments may end up with slightly different transformations,

S(M₁, A, B)·S(M₂, B, C)

Finally, M₁·B is not in general equal to M₂·B, leading to a gap in the path that includes the two segments.

To verify my claim, I made the following change,

diff --git gpu/shaders/elements.comp gpu/shaders/elements.comp
index a43c270..b5f2342 100644
--- gpu/shaders/elements.comp
+++ gpu/shaders/elements.comp
@@ -259,34 +259,8 @@ void main() {
                     State their_prefix = State_read(state_prefix_ref(look_back_ix));
                     exclusive = combine_state(their_prefix, exclusive);
                     break;
-                } else if (flag == FLAG_AGGREGATE_READY) {
-                    their_agg = State_read(state_aggregate_ref(look_back_ix));
-                    exclusive = combine_state(their_agg, exclusive);
-                    look_back_ix--;
-                    their_ix = 0;
-                    continue;
-                }
+                } 
                 // else spin
-
-                // Unfortunately there's no guarantee of forward progress of other
-                // workgroups, so compute a bit of the aggregate before trying again.
-                // In the worst case, spinning stops when the aggregate is complete.
-                ElementRef ref = ElementRef((look_back_ix * PARTITION_SIZE + their_ix) * Element_size);
-                State s = map_element(ref);
-                if (their_ix == 0) {
-                    their_agg = s;
-                } else {
-                    their_agg = combine_state(their_agg, s);
-                }
-                their_ix++;
-                if (their_ix == PARTITION_SIZE) {
-                    exclusive = combine_state(their_agg, exclusive);
-                    if (look_back_ix == 0) {
-                        break;
-                    }
-                    look_back_ix--;
-                    their_ix = 0;
-                }
             }
 
             // step 5 of paper: compute inclusive prefix

which removes the non-deterministic evaluation order. As expected, the path gaps disappeared.

I don't have a good fix yet. It's possible that the endpoints can be propagated in the scene traversal, at the cost of state memory. Perhaps a PathSeparator scene element should be added to delimit closed paths. It may also be a good idea to make path scene segment have implicit start points, saving a bit of memory.

[raphlinus]

This is a very interesting problem, thanks for bringing it to my attention. I will study your solution, but also consider some alternatives. Just to brainstorm, one is to represent the affine transformation using fixed point arithmetic, which should make the math deterministic, but with limitations.

[eliasnaur]

@raphlinus I'd like to take a stab at implementing your idea of combining transformations in their own monoid in elements.comp. Are you currently (or anyone else) working on this?

Related, is the comment about shared arrays of structs in elements.comp still relevant? If we're going to have two monoid passes, it would be a big readability to work on structs.

FWIW, the malloc functionality (example) uses shared arrays of structs, and I haven't heard you complain.

[raphlinus]

I'm open to you having a crack at it. If you would like to write a brief design doc before digging into the code, I'll try to prioritize it (I've had difficulty switching gears to focus on piet-gpu, but plan for it to be my main work over the next weeks).

I think we can do shared structs now, the bug in the NV shader compiler has been fixed a while ago and we're not at the point where we have to accumulate workarounds for driver bugs - yet.

[eliasnaur]

Please review #71 which contains an implementation of your separate transformation monoid. It works for me in Gio, and the piet-gpu tiger.

EDIT: I lied. It doesn't always work correctly. Stay tuned.

[eliasnaur]

Ok, I believe I found a correct (and simpler) fix, a hybrid between your resolved transforms and my tracking of path endpoints. I abandoned the second pass, because I ended up needing both the resolved transformations (for path segments) and the relative transformations (for the bounding box monoid). The new approach keeps a single pass, and doesn't need an end path flag.

Tested with Gio and the piet-gpu tiger.

Please review at #72.