impeller/renderer/path_polyline.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 = 256, 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;

layout(binding = 2) buffer Lines {
  uint count;
  LineData data[];
}
lines;

layout(binding = 3) buffer Components {
  uint count;
  PathComponent data[];
}
components;

layout(binding = 4) buffer Polyline {
  uint count;
  vec2 data[];
}
polyline;

uniform Config {
  float cubic_accuracy;
  float quad_tolerance;
}
config;

shared uvec2 cubic_ranges[512];
shared uvec2 quad_ranges[512];
shared uint scratch_count[512];
shared uint scratch_sum[512];

uint ComputePosition(uint index) {
  uint sum = scratch_sum[index];
  for (uint position = gl_SubgroupSize - 1; position < index;
       position += gl_SubgroupSize) {
    sum += scratch_sum[position] + scratch_count[position];
  }
  return sum;
}

void ProcessCubic(uint ident) {
  CubicData cubic;
  uint quad_count = 0;
  if (ident < cubics.count) {
    cubic = cubics.data[ident];
    quad_count = EstimateQuadraticCount(cubic, config.cubic_accuracy);
    scratch_count[ident] = quad_count;
  }

  barrier();

  uint offset = 0;
  if (quad_count > 0) {
    scratch_sum[ident] = subgroupExclusiveAdd(scratch_count[ident]);

    offset = ComputePosition(ident) + quads.count;
  }
  barrier();
  if (quad_count > 0) {
    atomicAdd(quads.count, quad_count);

    cubic_ranges[ident] = uvec2(offset, quad_count);
    for (uint i = 0; i < quad_count; i++) {
      quads.data[offset + i] = GenerateQuadraticFromCubic(cubic, i, quad_count);
    }
  }
}

void ProcessQuad(uint ident) {
  QuadData quad;
  QuadDecomposition decomposition;
  if (ident < quads.count) {
    quad = quads.data[ident];
    decomposition = DecomposeQuad(quad, config.quad_tolerance);
    scratch_count[ident] = decomposition.line_count;
  }

  barrier();

  uint offset = 0;
  if (decomposition.line_count > 0) {
    scratch_sum[ident] = subgroupExclusiveAdd(scratch_count[ident]);
    offset = ComputePosition(ident) + lines.count;
  }
  barrier();

  if (decomposition.line_count > 0) {
    atomicAdd(lines.count, decomposition.line_count);
    quad_ranges[ident] = uvec2(offset, decomposition.line_count);

    vec2 last_point = quad.p1;
    for (uint i = 1; i < decomposition.line_count; i++) {
      LineData line =
          LineData(last_point, GenerateLineFromQuad(quad, i, decomposition));
      last_point = line.p2;
      lines.data[offset + i - 1] = line;
    }
    lines.data[offset + decomposition.line_count - 1] =
        LineData(last_point, quad.p2);
  }
}

void ProcessLine(uint ident) {
  if (ident == 0) {
    polyline.count = lines.count + 1;
  }

  PathComponent component;
  uvec2 range = uvec2(0, 0);
  if (ident < components.count) {
    component = components.data[ident];
    if (component.count == 4) {
      // Determine location in quads
      uvec2 quad_range = cubic_ranges[component.index];
      uvec2 end_range = quad_ranges[quad_range.x + quad_range.y - 1];
      range.x = quad_ranges[quad_range.x].x;
      range.y = end_range.x + end_range.y - range.x;
    } else if (component.count == 3) {
      range = quad_ranges[component.index];
    } else if (component.count == 2) {
      range = uvec2(component.index, 1);
    }

    scratch_count[ident] = range.y;
  }
  barrier();

  if (ident < components.count) {
    scratch_sum[ident] = subgroupExclusiveAdd(scratch_count[ident]);
    uint offset = ComputePosition(ident);
    polyline.data[offset] = lines.data[range.x].p1;
    for (uint i = 0; i < range.y; i++) {
      polyline.data[offset + i + 1] = lines.data[range.x + i].p2;
    }
  }
}

void main() {
  uint ident = gl_GlobalInvocationID.x;
  // Turn each cubic into quads.
  ProcessCubic(ident);
  barrier();

  // Turn each quad into lines.
  ProcessQuad(ident);
  barrier();

  // Copy lines to the output buffer.
  ProcessLine(ident);
}