Add PangoMatrix type for affine transforms.

Fri May 28 11:39:39 2004  Owen Taylor  <otaylor@redhat.com>

        * pango/pango-types.h pango/pango-utils.c: Add PangoMatrix
        type for affine transforms.

        * configure.in pango.pc.in pango/Makefile.am: Add a -lm
        dependency for PangoMatrix operations.

        * pango/pango-context.[ch]: Add pango_context_set/get_matrix().

        * pango/pangoft2-render.c pango/pangoft2-private.h: Add
        code for drawing antialiased transformed rectangles and
        squiggly error underlines.

        * pango/pangoft2.[ch]: Add pango_ft2_render_transformed(),
        pango_ft2_render_layout_subpixel(),
        pango_ft2_render_layout_line_subpixel(), implement transformed
        rendering.

        * pango/pangofc-font.c: Pass any transformation matrix on to
        fontconfig when creating the pattern for a PangoFcFont.

1 files changed, 459 insertions, 0 deletions

diff --git a/pango/pangoft2-render.c b/pango/pangoft2-render.c
new file mode 100644
index 00000000..2b809fb7
--- /dev/null
+++ b/pango/pangoft2-render.c
@@ -0,0 +1,459 @@
+/* Pango
+ * pangoft2-render.c: Rendering routines to FT_Bitmap objects
+ *
+ * Copyright (C) 2004 Red Hat Software
+ * Copyright (C) 2000 Tor Lillqvist
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include <math.h>
+
+#include "pangoft2-private.h"
+
+typedef struct {
+  double y;
+  double x1;
+  double x2;
+} Position;
+
+static void
+draw_simple_trap (FT_Bitmap *bitmap,
+		  Position  *t,
+		  Position  *b)
+{
+  int iy = floor (t->y);
+  int x1, x2, x;
+  double dy = b->y - t->y;
+  guchar *dest;
+
+  if (iy < 0 || iy >= bitmap->rows)
+    return;
+  dest = bitmap->buffer + iy * bitmap->pitch;
+
+  if (t->x1 < b->x1)
+    x1 = floor (t->x1);
+  else
+    x1 = floor (b->x1);
+
+  if (t->x2 > b->x2)
+    x2 = ceil (t->x2);
+  else
+    x2 = ceil (b->x2);
+
+  x1 = CLAMP (x1, 0, bitmap->width);
+  x2 = CLAMP (x2, 0, bitmap->width);
+
+  for (x = x1; x < x2; x++)
+    {
+      double top_left = MAX (t->x1, x);
+      double top_right = MIN (t->x2, x + 1);
+      double bottom_left = MAX (b->x1, x);
+      double bottom_right = MIN (b->x2, x + 1);
+      double c = 0.5 * dy * ((top_right - top_left) + (bottom_right - bottom_left));
+
+      /* When converting to [0,255], we round up. This is intended
+       * to prevent the problem of pixels that get divided into
+       * multiple slices not being fully black.
+       */
+      int ic = c * 256;
+
+      dest[x] = MIN (dest[x] + ic, 255);
+    }
+}
+
+static void
+interpolate_position (Position *result,
+		      Position *top,
+		      Position *bottom,
+		      double    val,
+		      double    val1,
+		      double    val2)
+{
+  result->y  = (top->y *  (val2 - val) + bottom->y *  (val - val1)) / (val2 - val1);
+  result->x1 = (top->x1 * (val2 - val) + bottom->x1 * (val - val1)) / (val2 - val1);
+  result->x2 = (top->x2 * (val2 - val) + bottom->x2 * (val - val1)) / (val2 - val1);
+}
+
+/* This draws a trapezoid with the parallel sides aligned with
+ * the X axis. We do this by subdividing the trapezoid vertically
+ * into thin slices (themselves trapezoids) where two edge sides are each
+ * contained within a single pixel and then rasterizing each
+ * slice. There are frequently multiple slices within a single
+ * line so we have to accumulate to get the final result.
+ */
+static void
+draw_trap (FT_Bitmap *bitmap,
+	   double     y1,
+	   double     x11,
+	   double     x21,
+	   double     y2,
+	   double     x12,
+	   double     x22)
+{
+  Position pos;
+  Position t;
+  Position b;
+  gboolean done = FALSE;
+
+  if (y1 == y2)
+    return;
+
+  pos.y = t.y = y1;
+  pos.x1 = t.x1 = x11;
+  pos.x2 = t.x2 = x21;
+  b.y = y2;
+  b.x1 = x12;
+  b.x2 = x22;
+
+  while (!done)
+    {
+      Position pos_next;
+      double y_next, x1_next, x2_next;
+      double ix1, ix2;
+
+      /* The algorithm here is written to emphasize simplicity and
+       * numerical stability as opposed to speed.
+       *
+       * While the end result is slicing up the polygon vertically,
+       * conceptually we aren't walking in the X direction, rather we
+       * are walking along the edges. When we compute crossing of
+       * horizontal pixel boundaries, we use the X coordinate as the
+       * interpolating variable, when we compute crossing for vertical
+       * pixel boundaries, we use the Y coordinate.
+       *
+       * This allows us to handle almost exactly horizontal edges without
+       * running into difficulties. (Almost exactly horizontal edges
+       * come up frequently due to inexactness in computing, say,
+       * a 90 degree rotation transformation)
+       */
+
+      pos_next = b;
+      done = TRUE;
+
+      /* Check for crossing vertical pixel boundaries */
+      y_next = floor (pos.y) + 1;
+      if (y_next < pos_next.y)
+	{
+	  interpolate_position (&pos_next, &t, &b,
+				y_next, t.y, b.y);
+	  pos_next.y = y_next;
+	  done = FALSE;
+	}
+
+      /* Check left side for crossing horizontal pixel boundaries */
+      ix1 = floor (pos.x1);
+
+      if (b.x1 < t.x1)
+	{
+	  if (ix1 == pos.x1)
+	    x1_next = ix1 - 1;
+	  else
+	    x1_next = ix1;
+
+	  if (x1_next > pos_next.x1)
+	    {
+	      interpolate_position (&pos_next, &t, &b,
+				    x1_next, t.x1, b.x1);
+	      pos_next.x1 = x1_next;
+	      done = FALSE;
+	    }
+	}
+      else if (b.x1 > t.x1)
+	{
+	  x1_next = ix1 + 1;
+
+	  if (x1_next < pos_next.x1)
+	    {
+	      interpolate_position (&pos_next, &t, &b,
+				    x1_next, t.x1, b.x1);
+	      pos_next.x1 = x1_next;
+	      done = FALSE;
+	    }
+	}
+
+      /* Check right side for crossing horizontal pixel boundaries */
+      ix2 = floor (pos.x2);
+
+      if (b.x2 < t.x2)
+	{
+	  if (ix2 == pos.x2)
+	    x2_next = ix2 - 1;
+	  else
+	    x2_next = ix2;
+
+	  if (x2_next > pos_next.x2)
+	    {
+	      interpolate_position (&pos_next, &t, &b,
+				    x2_next, t.x2, b.x2);
+	      pos_next.x2 = x2_next;
+	      done = FALSE;
+	    }
+	}
+      else if (x22 > x21)
+	{
+	  x2_next = ix2 + 1;
+
+	  if (x2_next < pos_next.x2)
+	    {
+	      interpolate_position (&pos_next, &t, &b,
+				    x2_next, t.x2, b.x2);
+	      pos_next.x2 = x2_next;
+	      done = FALSE;
+	    }
+	}
+
+      draw_simple_trap (bitmap, &pos, &pos_next);
+      pos = pos_next;
+    }
+}
+
+typedef struct
+{
+  double x, y;
+} Point;
+
+static void
+to_device (PangoMatrix *matrix,
+	   double       x,
+	   double       y,
+	   Point       *result)
+{
+  result->x = (x * matrix->xx + y * matrix->xy) / PANGO_SCALE + matrix->x0;
+  result->y = (x * matrix->yx + y * matrix->yy) / PANGO_SCALE + matrix->y0;
+}
+
+int
+compare_points (const void *a,
+		const void *b)
+{
+  const Point *pa = a;
+  const Point *pb = b;
+
+  if (pa->y < pb->y)
+    return -1;
+  else if (pa->y > pb->y)
+    return 1;
+  else if (pa->x < pb->x)
+    return -1;
+  else if (pa->x > pb->x)
+    return 1;
+  else
+    return 0;
+}
+
+/**
+ * _pango_ft2_draw_rect:
+ * @bitmap: a #FT_Bitmap
+ * @matrix: a #PangoMatrix giving the user to device transformation
+ * @x_offset: X offset in device coordinates to add onto transformation result
+ * @y_offset: Y offset in device coordinates to add onto transformation result
+ * @x: X coordinate of rectangle, in Pango units in user coordinate system
+ * @y: Y coordinate of rectangle, in Pango units in user coordinate system
+ * @width: width of rectangle, in Pango units in user coordinate system
+ * @height: height of rectangle, in Pango units in user coordinate system
+ *
+ * Render an axis aligned rectangle in user coordinates onto
+ * a bitmap after transformation by the given matrix. Rendering
+ * is done anti-aliased.
+ **/
+void
+_pango_ft2_draw_rect (FT_Bitmap    *bitmap,
+		      PangoMatrix  *matrix,
+		      int           x,
+		      int           y,
+		      int           width,
+		      int           height)
+{
+  Point points[4];
+
+  /* Convert the points to device coordinates, and sort
+   * in ascending Y order. (Ordering by X for ties)
+   */
+  to_device (matrix, x, y, &points[0]);
+  to_device (matrix, x + width, y, &points[1]);
+  to_device (matrix, x, y + height, &points[2]);
+  to_device (matrix, x + width, y + height, &points[3]);
+
+  qsort (points, 4, sizeof (Point), compare_points);
+
+  /* There are essentially three cases. (There is a fourth
+   * case where trapezoid B is degenerate and we just have
+   * two triangles, but we don't need to handle it separately.)
+   *
+   *     1            2             3
+   *
+   *     ______       /\           /\
+   *    /     /      /A \         /A \
+   *   /  B  /      /____\       /____\
+   *  /_____/      /  B  /       \  B  \
+   *              /_____/         \_____\
+   *              \ C  /           \ C  /
+   *               \  /             \  /
+   *                \/               \/
+   */
+  if (points[0].y == points[1].y)
+    {
+     /* Case 1 (pure shear) */
+      draw_trap (bitmap,                                 /* B */
+		 points[0].y, points[0].x, points[1].x,
+		 points[2].y, points[2].x, points[3].x);
+    }
+  else if (points[1].x < points[2].x)
+    {
+      /* Case 2 */
+      double tmp_width = ((points[2].x - points[0].x) * (points[1].y - points[0].y)) / (points[2].y - points[0].y);
+      double base_width = tmp_width + points[0].x - points[1].x;
+
+      draw_trap (bitmap,                                              /* A */
+		 points[0].y, points[0].x, points[0].x,
+		 points[1].y, points[1].x, points[1].x + base_width);
+      draw_trap (bitmap,
+		 points[1].y, points[1].x, points[1].x + base_width,  /* B */
+		 points[2].y, points[2].x - base_width, points[2].x);
+      draw_trap (bitmap,
+		 points[2].y, points[2].x - base_width, points[2].x,  /* C */
+		 points[3].y, points[3].x, points[3].x);
+    }
+  else
+    {
+      /* case 3 */
+      double tmp_width = ((points[0].x - points[2].x) * (points[1].y - points[0].y)) / (points[2].y - points[0].y);
+      double base_width = tmp_width + points[1].x - points[0].x;
+
+      draw_trap (bitmap,                                             /* A */
+		 points[0].y, points[0].x, points[0].x,
+		 points[1].y,  points[1].x - base_width, points[1].x);
+      draw_trap (bitmap,
+		 points[1].y, points[1].x - base_width, points[1].x, /* B */
+		 points[2].y, points[2].x, points[2].x + base_width);
+      draw_trap (bitmap,
+		 points[2].y, points[2].x, points[2].x + base_width, /* C */
+		 points[3].y, points[3].x, points[3].x);
+    }
+}
+
+/* We are drawing an error underline that looks like one of:
+ *
+ *  /\      /\      /\        /\      /\               -
+ * /  \    /  \    /  \      /  \    /  \              |
+ * \   \  /\   \  /   /      \   \  /\   \             |
+ *  \   \/B \   \/ C /        \   \/B \   \            | height = HEIGHT_SQUARES * square
+ *   \ A \  /\ A \  /          \ A \  /\ A \           | 
+ *    \   \/  \   \/            \   \/  \   \          |
+ *     \  /    \  /              \  /    \  /          |
+ *      \/      \/                \/      \/           -
+ *
+ * |----|
+ *   unit_width = (HEIGHT_SQUARES - 1) * square
+ *
+ * To do this conveniently, we work in a coordinate system where A,B,C
+ * are axis aligned rectangles. (If fonts were square, the diagrams
+ * would be clearer)
+ *
+ *             (0,0)    
+ *              /\      /\        
+ *             /  \    /  \      
+ *            /\  /\  /\  /      
+ *           /  \/  \/  \/       
+ *          /    \  /\  /        
+ *      Y axis    \/  \/         
+ *                 \  /\          
+ *                  \/  \         
+ *                       \ X axis
+ *
+ * Note that the long side in this coordinate system is HEIGHT_SQUARES + 1
+ * units long
+ *
+ * The diagrams above are shown with HEIGHT_SQUARES an integer, but
+ * that is actually incidental; the value 2.5 below seems better than
+ * either HEIGHT_SQUARES=3 (a little long and skinny) or
+ * HEIGHT_SQUARES=2 (a bit short and stubby)
+ */
+ 
+#define HEIGHT_SQUARES 2.5
+
+static void
+get_total_matrix (PangoMatrix  *total,
+		  PangoMatrix  *global,
+		  int           x,
+		  int           y,
+		  int           square)
+{
+  PangoMatrix local;
+  gdouble scale = 0.5 * square;
+
+  /* The local matrix translates from the axis aligned coordinate system
+   * to the original user space coordinate system.
+   */
+  local.xx = scale;
+  local.xy = - scale;
+  local.yx = scale;
+  local.yy = scale;
+  local.x0 = 0;
+  local.y0 = 0;
+
+  *total = *global;
+  pango_matrix_concat (total, &local);
+
+  total->x0 = (global->xx * x + global->xy * y) / PANGO_SCALE + global->x0;
+  total->y0 = (global->yx * x + global->yy * y) / PANGO_SCALE + global->y0;
+}
+
+void
+_pango_ft2_draw_error_underline (FT_Bitmap    *bitmap,
+				 PangoMatrix  *matrix,
+				 int           x,
+				 int           y,
+				 int           width,
+				 int           height)
+{
+
+  int square = height / HEIGHT_SQUARES;
+  int unit_width = (HEIGHT_SQUARES - 1) * square;
+  int width_units = (width + unit_width / 2) / unit_width;
+
+  x += (width - width_units * unit_width) / 2;
+  width = width_units * unit_width;
+
+  while (TRUE)
+    {
+      PangoMatrix total;
+      get_total_matrix (&total, matrix, x, y, square);
+
+      _pango_ft2_draw_rect (bitmap, &total,              /* A */
+			    0,                      0,
+			    HEIGHT_SQUARES * 2 - 1, 1);
+
+      if (width_units > 2)
+	{
+	  _pango_ft2_draw_rect (bitmap, &total,
+				HEIGHT_SQUARES * 2 - 2, - (HEIGHT_SQUARES * 2 - 3),
+				1,                      HEIGHT_SQUARES * 2 - 3); /* B */
+	  width_units -= 2;
+	  x += unit_width * 2;
+	}
+      else if (width_units == 2)
+	{
+	  _pango_ft2_draw_rect (bitmap, &total,
+				HEIGHT_SQUARES * 2 - 2, - (HEIGHT_SQUARES * 2 - 2),
+				1,                      HEIGHT_SQUARES * 2 - 2); /* C */
+	  break;
+	}
+      else
+	break;
+    }
+}