impeller/fixtures/cubic_to_quads.comp

// Copyright 2013 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#extension GL_KHR_shader_subgroup_arithmetic : enable

layout(local_size_x = 512, local_size_y = 1) in;
layout(std430) buffer;

#include <impeller/path.glsl>

layout(binding = 0) readonly buffer Cubics {
  uint count;
  CubicData data[];
}
cubics;

layout(binding = 1) buffer Quads {
  uint count;
  QuadData data[];
}
quads;

uniform Config {
  float accuracy;
}
config;

shared uint quad_counts[512];
shared uint count_sums[512];

void main() {
  uint ident = gl_GlobalInvocationID.x;
  if (ident >= cubics.count) {
    return;
  }

  // The maximum error, as a vector from the cubic to the best approximating
  // quadratic, is proportional to the third derivative, which is constant
  // across the segment. Thus, the error scales down as the third power of
  // the number of subdivisions. Our strategy then is to subdivide `t` evenly.
  //
  // This is an overestimate of the error because only the component
  // perpendicular to the first derivative is important. But the simplicity is
  // appealing.

  // This magic number is the square of 36 / sqrt(3).
  // See: http://caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html
  float max_hypot2 = 432.0 * config.accuracy * config.accuracy;

  CubicData cubic = cubics.data[ident];

  vec2 err_v = (3.0 * cubic.cp2 - cubic.p2) - (3.0 * cubic.cp1 - cubic.p1);
  float err = dot(err_v, err_v);
  float quad_count = max(1., ceil(pow(err * (1.0 / max_hypot2), 1. / 6.0)));

  quad_counts[ident] = uint(quad_count);

  barrier();
  count_sums[ident] = subgroupInclusiveAdd(quad_counts[ident]);

  quads.count = count_sums[cubics.count - 1];
  for (uint i = 0; i < quad_count; i++) {
    float t0 = i / quad_count;
    float t1 = (i + 1) / quad_count;

    // calculate the subsegment
    vec2 sub_p1 = CubicSolve(cubic, t0);
    vec2 sub_p2 = CubicSolve(cubic, t1);
    QuadData quad = QuadData(3.0 * (cubic.cp1 - cubic.p1),   //
                             3.0 * (cubic.cp2 - cubic.cp1),  //
                             3.0 * (cubic.p2 - cubic.cp2));
    float sub_scale = (t1 - t0) * (1.0 / 3.0);
    vec2 sub_cp1 = sub_p1 + sub_scale * QuadraticSolve(quad, t0);
    vec2 sub_cp2 = sub_p2 - sub_scale * QuadraticSolve(quad, t1);

    vec2 quad_p1x2 = 3.0 * sub_cp1 - sub_p1;
    vec2 quad_p2x2 = 3.0 * sub_cp2 - sub_p2;
    uint offset = count_sums[ident] - uint(quad_count);
    quads.data[offset + i] = QuadData(sub_p1,                           //
                                      ((quad_p1x2 + quad_p2x2) / 4.0),  //
                                      sub_p2);
  }
}