[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