src/hb-gpu-cu2qu.hh

/*
 * Copyright (C) 2026  Behdad Esfahbod
 *
 *  This is part of HarfBuzz, a text shaping library.
 *
 * Cubic-to-quadratic Bézier conversion.
 * Ported from fonttools cu2qu:
 * https://github.com/fonttools/fonttools/blob/main/Lib/fontTools/cu2qu/cu2qu.py
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and its documentation for any purpose, provided that the
 * above copyright notice and the following two paragraphs appear in
 * all copies of this software.
 *
 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 *
 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * Author(s): Behdad Esfahbod
 */

#ifndef HB_GPU_CU2QU_HH
#define HB_GPU_CU2QU_HH

#include "hb-gpu-draw.hh"

#include <cmath>


/* Maximum approximation error in font units.
 * 0.5 is well below one unit in any reasonable coordinate system. */
#ifndef HB_GPU_CU2QU_TOLERANCE
#define HB_GPU_CU2QU_TOLERANCE 0.5
#endif

/* Maximum subdivision depth.  Each level halves the parameter interval;
 * at depth 10 the sub-curve spans 1/1024 of the original, so the
 * quadratic error (O(dt^4)) is reduced by a factor of ~10^12. */
#define HB_GPU_CU2QU_MAX_DEPTH 10


struct hb_gpu_cu2qu_point_t
{
  double x, y;
};

static inline hb_gpu_cu2qu_point_t
hb_gpu_cu2qu_lerp (hb_gpu_cu2qu_point_t a, hb_gpu_cu2qu_point_t b, double t)
{
  return {a.x + (b.x - a.x) * t,
	  a.y + (b.y - a.y) * t};
}


/*
 * Check whether a cubic error curve stays within `tolerance` of the origin.
 */
static bool
hb_gpu_cubic_farthest_fit_inside (hb_gpu_cu2qu_point_t p0,
				  hb_gpu_cu2qu_point_t p1,
				  hb_gpu_cu2qu_point_t p2,
				  hb_gpu_cu2qu_point_t p3,
				  double tolerance, unsigned depth)
{
  if (hypot (p1.x, p1.y) <= tolerance &&
      hypot (p2.x, p2.y) <= tolerance)
    return true;

  if (depth >= 8)
    return false;

  hb_gpu_cu2qu_point_t mid = {(p0.x + 3 * (p1.x + p2.x) + p3.x) * 0.125,
			      (p0.y + 3 * (p1.y + p2.y) + p3.y) * 0.125};
  if (hypot (mid.x, mid.y) > tolerance)
    return false;

  hb_gpu_cu2qu_point_t d3 = {(p3.x + p2.x - p1.x - p0.x) * 0.125,
			     (p3.y + p2.y - p1.y - p0.y) * 0.125};

  return hb_gpu_cubic_farthest_fit_inside (
    p0,
    hb_gpu_cu2qu_lerp (p0, p1, 0.5),
    {mid.x - d3.x, mid.y - d3.y},
    mid,
    tolerance, depth + 1
  ) && hb_gpu_cubic_farthest_fit_inside (
    mid,
    {mid.x + d3.x, mid.y + d3.y},
    hb_gpu_cu2qu_lerp (p2, p3, 0.5),
    p3,
    tolerance, depth + 1
  );
}


/*
 * Try to approximate a cubic Bézier with a single quadratic.
 */
static bool
hb_gpu_cubic_approx_quadratic (hb_gpu_cu2qu_point_t c0,
			       hb_gpu_cu2qu_point_t c1,
			       hb_gpu_cu2qu_point_t c2,
			       hb_gpu_cu2qu_point_t c3,
			       double tolerance,
			       hb_gpu_cu2qu_point_t *q1)
{
  double ax = c1.x - c0.x, ay = c1.y - c0.y;
  double dx = c3.x - c2.x, dy = c3.y - c2.y;

  double px = -ay, py = ax;

  double denom = px * dx + py * dy;
  if (fabs (denom) < 1e-12)
    return false;

  double h = (px * (c0.x - c2.x) + py * (c0.y - c2.y)) / denom;

  q1->x = c2.x + dx * h;
  q1->y = c2.y + dy * h;

  hb_gpu_cu2qu_point_t err1 = {c0.x + (q1->x - c0.x) * (2.0 / 3.0) - c1.x,
			       c0.y + (q1->y - c0.y) * (2.0 / 3.0) - c1.y};
  hb_gpu_cu2qu_point_t err2 = {c3.x + (q1->x - c3.x) * (2.0 / 3.0) - c2.x,
			       c3.y + (q1->y - c3.y) * (2.0 / 3.0) - c2.y};

  return hb_gpu_cubic_farthest_fit_inside ({0, 0}, err1, err2, {0, 0}, tolerance, 0);
}


/*
 * Split a cubic at t = 0.5 (de Casteljau).
 */
static void
hb_gpu_split_cubic_half (hb_gpu_cu2qu_point_t c0,
			 hb_gpu_cu2qu_point_t c1,
			 hb_gpu_cu2qu_point_t c2,
			 hb_gpu_cu2qu_point_t c3,
			 hb_gpu_cu2qu_point_t out[7])
{
  hb_gpu_cu2qu_point_t m01  = hb_gpu_cu2qu_lerp (c0,  c1,  0.5);
  hb_gpu_cu2qu_point_t m12  = hb_gpu_cu2qu_lerp (c1,  c2,  0.5);
  hb_gpu_cu2qu_point_t m23  = hb_gpu_cu2qu_lerp (c2,  c3,  0.5);
  hb_gpu_cu2qu_point_t m012 = hb_gpu_cu2qu_lerp (m01, m12, 0.5);
  hb_gpu_cu2qu_point_t m123 = hb_gpu_cu2qu_lerp (m12, m23, 0.5);
  hb_gpu_cu2qu_point_t mid  = hb_gpu_cu2qu_lerp (m012, m123, 0.5);

  out[0] = c0;   out[1] = m01;  out[2] = m012;
  out[3] = mid;
  out[4] = m123; out[5] = m23;  out[6] = c3;
}


/*
 * Recursively convert a cubic into quadratic segments.
 */
static void
hb_gpu_cubic_to_quadratics (hb_gpu_draw_t *g,
			    hb_gpu_cu2qu_point_t c0,
			    hb_gpu_cu2qu_point_t c1,
			    hb_gpu_cu2qu_point_t c2,
			    hb_gpu_cu2qu_point_t c3,
			    double tolerance, unsigned depth)
{
  hb_gpu_cu2qu_point_t q1;
  if (hb_gpu_cubic_approx_quadratic (c0, c1, c2, c3, tolerance, &q1))
  {
    g->acc_conic_to (q1.x, q1.y, c3.x, c3.y);
    return;
  }

  if (depth >= HB_GPU_CU2QU_MAX_DEPTH)
  {
    g->acc_line_to (c3.x, c3.y);
    return;
  }

  hb_gpu_cu2qu_point_t pts[7];
  hb_gpu_split_cubic_half (c0, c1, c2, c3, pts);
  hb_gpu_cubic_to_quadratics (g, pts[0], pts[1], pts[2], pts[3], tolerance, depth + 1);
  hb_gpu_cubic_to_quadratics (g, pts[3], pts[4], pts[5], pts[6], tolerance, depth + 1);
}


#endif /* HB_GPU_CU2QU_HH */