[PATCH xf86-input-libinput 1/2] Add a bezier curve implementation
Peter Hutterer
peter.hutterer at who-t.net
Mon Oct 31 05:26:32 UTC 2016
Needed for the wacom stylus pressure curve
Signed-off-by: Peter Hutterer <peter.hutterer at who-t.net>
---
src/Makefile.am | 5 +-
src/bezier.c | 170 +++++++++++++++++++++++++++++++++++++++++++++
src/bezier.h | 67 ++++++++++++++++++
test/Makefile.am | 5 +-
test/test-bezier.c | 199 +++++++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 443 insertions(+), 3 deletions(-)
create mode 100644 src/bezier.c
create mode 100644 src/bezier.h
create mode 100644 test/test-bezier.c
diff --git a/src/Makefile.am b/src/Makefile.am
index 60703e6..8634b69 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -30,10 +30,11 @@ AM_CPPFLAGS =-I$(top_srcdir)/include $(LIBINPUT_CFLAGS)
@DRIVER_NAME at _drv_la_LTLIBRARIES = @DRIVER_NAME at _drv.la
@DRIVER_NAME at _drv_la_LDFLAGS = -module -avoid-version
- at DRIVER_NAME@_drv_la_LIBADD = $(LIBINPUT_LIBS) libdraglock.la
+ at DRIVER_NAME@_drv_la_LIBADD = $(LIBINPUT_LIBS) libdraglock.la -lm
@DRIVER_NAME at _drv_ladir = @inputdir@
@DRIVER_NAME at _drv_la_SOURCES = xf86libinput.c
-noinst_LTLIBRARIES = libdraglock.la
+noinst_LTLIBRARIES = libdraglock.la libbezier.la
libdraglock_la_SOURCES = draglock.c draglock.h
+libbezier_la_SOURCES = bezier.c bezier.h
diff --git a/src/bezier.c b/src/bezier.c
new file mode 100644
index 0000000..e571a3c
--- /dev/null
+++ b/src/bezier.c
@@ -0,0 +1,170 @@
+/*
+ * Copyright © 2016 Red Hat, Inc.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Red Hat
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission. Red
+ * Hat makes no representations about the suitability of this software
+ * for any purpose. It is provided "as is" without express or implied
+ * warranty.
+ *
+ * THE AUTHORS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <assert.h>
+#include <math.h>
+#include <stdio.h>
+
+#include "bezier.h"
+
+struct point {
+ int x, y;
+};
+
+/**
+ * de Casteljau's algorithm. See this page here
+ * https://pomax.github.io/bezierinfo/#extended
+ *
+ * To play with bezier curve shapes, I used
+ * http://cubic-bezier.com/
+ */
+static struct point
+decasteljau(const struct point *controls,
+ size_t ncontrols,
+ double t)
+{
+ struct point new_controls[ncontrols];
+
+ if (ncontrols == 1)
+ return controls[0];
+
+ for (int i = 0; i < ncontrols - 1; i++) {
+ new_controls[i].x = (1.0 - t) * controls[i].x + t * controls[i + 1].x;
+ new_controls[i].y = (1.0 - t) * controls[i].y + t * controls[i + 1].y;
+ }
+
+ return decasteljau(new_controls, ncontrols - 1, t);
+}
+
+/**
+ * Given a Bézier curve defined by the control points, reduce the curve to
+ * one with ncurve_points.
+ */
+static void
+flatten_curve(const struct point *controls,
+ size_t ncontrols,
+ struct point *curve,
+ size_t ncurve_points)
+{
+ ncurve_points--; /* make sure we end up with 100/100 as last point */
+
+ for (int i = 0; i <= ncurve_points; i++) {
+ double t = 1.0 * i/ncurve_points;
+ struct point p;
+
+ p = decasteljau(controls, ncontrols, t);
+ curve[i] = p;
+ }
+}
+
+/**
+ * Calculate line through a and b, set curve[x] for each x between
+ * [a.x, b.x].
+ *
+ * Note: pcurve must be at least b.x size.
+ */
+static void
+line_between(struct point a, struct point b,
+ struct point *curve, size_t curve_sz)
+{
+ double slope;
+ double offset;
+
+ assert(b.x < curve_sz);
+
+ if (a.x == b.x) {
+ curve[a.x].x = a.x;
+ curve[a.x].y = a.y;
+ return;
+ }
+
+ slope = (double)(b.y - a.y)/(b.x - a.x);
+ offset = a.y - slope * a.x;
+
+ for (int x = a.x; x <= b.x; x++) {
+ struct point p;
+ p.x = x;
+ p.y = slope * x + offset;
+ curve[x] = p;
+ }
+}
+
+bool
+cubic_bezier(const struct bezier_control_point controls[4],
+ int *bezier_out,
+ size_t bezier_sz)
+{
+ const int nsegments = 50;
+ const int range = bezier_sz - 1;
+ struct point curve[nsegments];
+ struct point bezier[bezier_sz];
+ struct point zero = { 0, 0 },
+ max = { range, range};
+
+ /* Scale control points into the [0, bezier_sz) range */
+ struct point ctrls[4];
+
+ for (int i = 0; i < 4; i++) {
+ if (controls[i].x < 0.0 || controls[i].x > 1.0 ||
+ controls[i].y < 0.0 || controls[i].y > 1.0)
+ return false;
+
+ ctrls[i].x = controls[i].x * range;
+ ctrls[i].y = controls[i].y * range;
+ }
+
+ for (int i = 0; i < 3; i++) {
+ if (ctrls[i].x > ctrls[i+1].x)
+ return false;
+ }
+
+ /* Reduce curve to nsegments, because this isn't a drawing program */
+ flatten_curve(ctrls, 4, curve, nsegments);
+
+ /* we now have nsegments points in curve that represent the bezier
+ curve (already in the [0, bezier_sz) range). Run through the
+ points and draw a straight line between each point and voila, we
+ have our curve.
+
+ If the first control points (x0/y0) is not at x == 0 or the last
+ control point (x3/y3) is not at the max value, draw a line
+ between from 0/0 to x0/y0 and from x3/y3 to xmax/y3.
+ */
+
+ line_between(zero, curve[0], bezier, bezier_sz);
+
+ for (int i = 0; i < nsegments - 1; i++)
+ line_between(curve[i], curve[i+1], bezier, bezier_sz);
+
+ if (curve[nsegments - 1].x < max.x)
+ line_between(curve[nsegments - 1], max, bezier, bezier_sz);
+
+ for (int i = 0; i < bezier_sz; i++)
+ bezier_out[i] = bezier[i].y;
+
+ return true;
+}
diff --git a/src/bezier.h b/src/bezier.h
new file mode 100644
index 0000000..c7f3b27
--- /dev/null
+++ b/src/bezier.h
@@ -0,0 +1,67 @@
+/*
+ * Copyright © 2016 Red Hat, Inc.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Red Hat
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission. Red
+ * Hat makes no representations about the suitability of this software
+ * for any purpose. It is provided "as is" without express or implied
+ * warranty.
+ *
+ * THE AUTHORS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#ifndef BEZIER_H
+#define BEZIER_H
+
+#include <stdlib.h>
+#include <stdbool.h>
+
+struct bezier_control_point {
+ double x, y;
+};
+
+/**
+ * Given four control points in the range [(0.0/0.0), (1.0/1.0)]
+ * construct a Bézier curve.
+ *
+ * ^
+ *1.0 | c2 ______ c3
+ * | _/
+ * | /
+ * |c1 /
+ * | /
+ * | /
+ * |/_________________>
+ * c0 1.0
+ *
+ * This function requires that c[i].x <= c[i+1].x
+ *
+ * The curve is mapped into a canvas size [0, bezier_sz)². For each x
+ * coordiante in [0, bezier_sz), the matching y coordinate is thus
+ * bezier[x].
+ *
+ * In other words, if you have a range [0,2048) input possible values,
+ * the output is a list of 2048 points in a [0, 2048) range.
+ *
+ * @return true on success, false otherwise
+ */
+bool
+cubic_bezier(const struct bezier_control_point controls[4],
+ int *bezier,
+ size_t bezier_sz);
+#endif
diff --git a/test/Makefile.am b/test/Makefile.am
index 6f94abe..4c9c5f6 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -3,11 +3,14 @@ AM_CPPFLAGS = $(XORG_CFLAGS) \
-I$(top_srcdir)/include \
-I$(top_srcdir)/src
-tests = test-draglock
+tests = test-draglock test-bezier
noinst_PROGRAMS = $(tests)
test_draglock_SOURCES = test-draglock.c
test_draglock_LDADD = ../src/libdraglock.la
+test_bezier_SOURCES = test-bezier.c
+test_bezier_LDADD = ../src/libbezier.la -lm
+
TESTS = $(tests)
diff --git a/test/test-bezier.c b/test/test-bezier.c
new file mode 100644
index 0000000..1b290a4
--- /dev/null
+++ b/test/test-bezier.c
@@ -0,0 +1,199 @@
+/*
+ * Copyright © 2016 Red Hat, Inc.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Red Hat
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission. Red
+ * Hat makes no representations about the suitability of this software
+ * for any purpose. It is provided "as is" without express or implied
+ * warranty.
+ *
+ * THE AUTHORS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "bezier.h"
+
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+
+static inline void
+print_curve(int *bezier, size_t size)
+{
+ /* look at it with gnuplot, "plot 'output-file.txt'" */
+ for (int i = 0; i < size; i++)
+ printf("%d %d\n", i, bezier[i]);
+}
+
+static void
+test_linear(void)
+{
+ const int size = 2048;
+ int bezier[size];
+
+ struct bezier_control_point controls[] = {
+ { 0.0, 0.0 },
+ { 0.0, 0.0 },
+ { 1.0, 1.0 },
+ { 1.0, 1.0 }
+ };
+
+ cubic_bezier(controls, bezier, size);
+
+ assert(bezier[0] == 0);
+ assert(bezier[size - 1] == size - 1);
+
+ for (int x = 1; x < size; x++)
+ assert(bezier[x] == x);
+}
+
+/* Center point pulled down towards X axis */
+static void
+test_flattened(void)
+{
+ const int size = 2048;
+ int bezier[size];
+
+ struct bezier_control_point controls[] = {
+ { 0.0, 0.0 },
+ { 0.1, 0.0 },
+ { 1.0, 0.9 },
+ { 1.0, 1.0 }
+ };
+
+ cubic_bezier(controls, bezier, size);
+
+ assert(bezier[0] == 0);
+ assert(bezier[size - 1] == size - 1);
+
+ for (int x = 1; x < size - 1; x++) {
+ assert(bezier[x] < x);
+ }
+}
+
+/* Center point pulled up from X axis */
+static void
+test_raised(void)
+{
+ const int size = 2048;
+ int bezier[size];
+
+ struct bezier_control_point controls[] = {
+ { 0.0, 0.0 },
+ { 0.1, 0.4 },
+ { 0.4, 1.0 },
+ { 1.0, 1.0 }
+ };
+
+ cubic_bezier(controls, bezier, size);
+
+ assert(bezier[0] == 0);
+ assert(bezier[size - 1] == size - 1);
+
+ for (int x = 1; x < size; x++)
+ assert(bezier[x] >= x);
+
+ for (int x = 10; x < size - 10; x++)
+ assert(bezier[x] > x);
+}
+
+static void
+test_windy(void)
+{
+ const int size = 2048;
+ int bezier[size];
+
+ struct bezier_control_point controls[] = {
+ { 0.0, 0.0 },
+ { 0.0, 0.3 },
+ { 1.0, 0.7 },
+ { 1.0, 1.0 }
+ };
+
+ cubic_bezier(controls, bezier, size);
+
+ assert(bezier[0] == 0);
+ assert(bezier[size - 1] == size - 1);
+
+ for (int x = 1; x < size/2 - 20; x++)
+ assert(bezier[x] > x);
+
+ for (int x = size/2 + 20; x < size - 1; x++)
+ assert(bezier[x] < x);
+}
+
+static void
+test_nonzero_x_linear(void)
+{
+ const int size = 2048;
+ int bezier[size];
+ int x;
+
+ struct bezier_control_point controls[] = {
+ { 0.2, 0.0 },
+ { 0.2, 0.0 },
+ { 0.8, 1.0 },
+ { 0.8, 1.0 }
+ };
+
+ cubic_bezier(controls, bezier, size);
+
+ x = 0;
+ do {
+ assert(bezier[x] == 0);
+ } while (++x < size * 0.2 - 1);
+
+ do {
+ assert(bezier[x] > bezier[x-1]);
+ } while (++x < size * 0.8 - 1);
+
+ do {
+ assert(bezier[x] == size - 1);
+ } while (++x < size);
+}
+
+static void
+test_nonzero_y_linear(void)
+{
+ const int size = 2048;
+ int bezier[size];
+
+ struct bezier_control_point controls[] = {
+ { 0.0, 0.2 },
+ { 0.0, 0.2 },
+ { 1.0, 0.8 },
+ { 1.0, 0.8 }
+ };
+
+ cubic_bezier(controls, bezier, size);
+
+ assert(bezier[0] == (int)(size * 0.2));
+
+ for (int x = 1; x < size; x++) {
+ assert(bezier[x - 1] <= bezier[x]);
+ assert(bezier[x] >= (int)(size * 0.2));
+ }
+}
+
+int
+main(int argc, char **argv)
+{
+ test_linear();
+ test_flattened();
+ test_raised();
+ test_windy();
+ test_nonzero_x_linear();
+ test_nonzero_y_linear();
+
+ return 0;
+}
--
2.9.3
More information about the xorg-devel
mailing list