See attached...
This patch adds supports for basic Bezier curve computations based on
the code from Graphics Gems V. It also provides a widget primitive to
draw 2D Bezier curves from 4 control points, as well as a simple test
case that demonstrates curve drawing.
Note that the test case may need some slight patching -- I feel like it
should test if AG_MATH is enabled, but I'm not sure how to do that.
This patch compiles clean against r10481 on Ubuntu 18.04 / AMD64.
~ Charles
>From fffbd9ead1f2eab87473fb8c6383fdab23188fcd Mon Sep 17 00:00:00 2001
From: Charles Daniels <[email protected]>
Date: Fri, 13 Sep 2019 16:49:55 -0400
Subject: [PATCH] Implemented support for Bezier curves
---
ChangeLogs/Release-1.6.0.txt | 1 +
math/Makefile | 3 +-
math/m_bezier.c | 167 +++++++++++++++++++++++++++++++++++
math/m_bezier.h | 11 +++
math/m_bezier_primitives.c | 82 +++++++++++++++++
math/m_bezier_primitives.h | 17 ++++
math/m_geometry.h | 1 +
math/m_gui.h | 1 +
tests/Makefile | 2 +
tests/agartest.c | 2 +
10 files changed, 286 insertions(+), 1 deletion(-)
create mode 100644 math/m_bezier.c
create mode 100644 math/m_bezier.h
create mode 100644 math/m_bezier_primitives.c
create mode 100644 math/m_bezier_primitives.h
diff --git a/ChangeLogs/Release-1.6.0.txt b/ChangeLogs/Release-1.6.0.txt
index 4ba337a5d..ccde3bbee 100644
--- a/ChangeLogs/Release-1.6.0.txt
+++ b/ChangeLogs/Release-1.6.0.txt
@@ -46,3 +46,4 @@ particular order.
AG_QuadraticPositive, AG_QuadraticNegative, AG_Distance
- GUI: add AG_DrawArrowLine for drawing lines with arrowheads
- GUI: AG_Graph now supports directed graphs
+- MATH: Implemented M_Bezier module for computing Bézier curves.
diff --git a/math/Makefile b/math/Makefile
index e49a7d40a..f6192f1a1 100644
--- a/math/Makefile
+++ b/math/Makefile
@@ -27,7 +27,8 @@ SRCS= m_math.c m_complex.c m_quaternion.c \
m_coordinates.c m_heapsort.c m_mergesort.c m_qsort.c m_radixsort.c \
m_point_set.c m_color.c m_sphere.c m_polyhedron.c \
m_matrix_sparse.c m_sparse_allocate.c m_sparse_build.c m_sparse_eda.c \
- m_sparse_factor.c m_sparse_output.c m_sparse_solve.c m_sparse_utils.c
+ m_sparse_factor.c m_sparse_output.c m_sparse_solve.c m_sparse_utils.c \
+ m_bezier.c m_bezier_primitives.c
CFLAGS+=${GUI_CFLAGS} \
${CORE_CFLAGS} \
diff --git a/math/m_bezier.c b/math/m_bezier.c
new file mode 100644
index 000000000..8576e7aed
--- /dev/null
+++ b/math/m_bezier.c
@@ -0,0 +1,167 @@
+/* Copyright (c) Charles A. Daniels <http://cdaniels.net>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
+ * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * This module is based on code published in Graphics Gems V by Alan W. Paeth
+ * (ch IV.8, pp206) and written by Rober D. Miller. Said code was Copyright (c)
+ * 1995 Academic Press Inc. and distributed under the license:
+ *
+ * EULA: The Graphics Gems code is copyright-protected. In other words, you
+ * cannot claim the text of the code as your own and resell it. Using the code
+ * is permitted in any program, product, or library, non-commercial or
+ * commercial. Giving credit is not required, though is a nice gesture. The
+ * code comes as-is, and if there are any flaws or problems with any Gems code,
+ * nobody involved with Gems - authors, editors, publishers, or webmasters -
+ * are to be held responsible. Basically, don't be a jerk, and remember that
+ * anything free comes with no guarantee.
+ */
+
+#include <agar/core/core.h>
+#include <agar/math/m.h>
+
+#include <agar/config/enable_gui.h>
+
+#ifdef ENABLE_GUI
+# include <agar/gui/gui.h>
+#include <agar/gui/widget.h>
+#include <agar/math/m_bezier_primitives.h>
+#endif
+
+
+/* Setup Bezier coefficient array once for each control polygon. */
+void M_BezierForm2(M_PointSet2* p, M_PointSet2* c)
+{
+ int k;
+ M_Real n, choose;
+ n = p->n - 1;
+
+ M_PointSetAlloc2(c, p->n);
+
+ /* XXX: should be an error condition of n < c->n */
+
+ for(k = 0; k <= n; k++) {
+ if (k == 0) choose = 1;
+ else if (k == 1) choose = n;
+ else choose = choose *(n-k+1)/k;
+ c->p[k].x = p->p[k].x *choose;
+ c->p[k].y = p->p[k].y *choose;
+ c->n++;
+ };
+
+}
+
+/* Setup Bezier coefficient array once for each control polygon. */
+void M_BezierForm3(M_PointSet3* p, M_PointSet3* c)
+{
+ int k;
+ M_Real n, choose;
+ n = p->n - 1;
+
+ M_PointSetAlloc3(c, p->n);
+
+ /* XXX: should be an error condition of n < c->n */
+
+ for(k = 0; k <= n; k++) {
+ if (k == 0) choose = 1;
+ else if (k == 1) choose = n;
+ else choose = choose *(n-k+1)/k;
+ c->p[k].x = p->p[k].x *choose;
+ c->p[k].y = p->p[k].y *choose;
+ c->p[k].z = p->p[k].z *choose;
+ };
+}
+
+/* Return Point pt(t), t <= 0 <= 1 from c, given the number of Points in
+ * control polygon. BezierForm must be called once for any given control
+ * polygon. */
+void M_BezierCurve2(M_PointSet2* c, M_Real t, M_Vector2* pt)
+{
+ int k, n;
+ M_Real t1, tt, u;
+ M_PointSet2 b;
+
+ M_PointSetInit2(&b);
+ M_PointSetAlloc2(&b, c->n);
+
+ /* XXX: need to do bounds checking on c */
+
+ n = c->n - 1;
+ u = t;
+ b.p[0].x = c->p[0].x;
+ b.p[0].y = c->p[0].y;
+ for(k =1; k <=n; k++) {
+ b.p[k].x = c->p[k].x *u;
+ b.p[k].y = c->p[k].y *u;
+ u =u*t;
+ };
+
+ pt->x = b.p[n].x;
+ pt->y = b.p[n].y;
+ t1 = 1-t; tt = t1;
+ for(k =n-1; k >=0; k--) {
+ pt->x += b.p[k].x *tt;
+ pt->y += b.p[k].y *tt;
+ tt =tt*t1;
+ }
+
+ M_PointSetFree2(&b);
+}
+
+/* Return Point pt(t), t <= 0 <= 1 from c, given the number of Points in
+ * control polygon. BezierForm must be called once for any given control
+ * polygon. */
+void M_BezierCurve3(M_PointSet3* c, M_Real t, M_Vector3* pt)
+{
+ int k, n;
+ M_Real t1, tt, u;
+ M_PointSet3 b;
+
+ M_PointSetInit3(&b);
+ M_PointSetAlloc3(&b, c->n);
+
+ /* XXX: need to do bounds checking on c */
+
+ n = c->n - 1;
+ u = t;
+ b.p[0].x = c->p[0].x;
+ b.p[0].y = c->p[0].y;
+ b.p[0].z = c->p[0].z;
+ for(k =1; k <=n; k++) {
+ b.p[k].x = c->p[k].x *u;
+ b.p[k].y = c->p[k].y *u;
+ b.p[k].z = c->p[k].z *u;
+ u =u*t;
+ };
+
+ pt->x = b.p[n].x;
+ pt->y = b.p[n].y;
+ pt->z = b.p[n].z;
+ t1 = 1-t; tt = t1;
+ for(k =n-1; k >=0; k--) {
+ pt->x += b.p[k].x *tt;
+ pt->y += b.p[k].y *tt;
+ pt->z += b.p[k].z *tt;
+ tt =tt*t1;
+ }
+
+ M_PointSetFree3(&b);
+}
+
diff --git a/math/m_bezier.h b/math/m_bezier.h
new file mode 100644
index 000000000..1b4941273
--- /dev/null
+++ b/math/m_bezier.h
@@ -0,0 +1,11 @@
+/* Public domain */
+
+__BEGIN_DECLS
+
+
+void M_BezierForm2(M_PointSet2*, M_PointSet2*);
+void M_BezierForm3(M_PointSet3* , M_PointSet3*);
+void M_BezierCurve2(M_PointSet2*, M_Real, M_Vector2*);
+void M_BezierCurve3(M_PointSet3*, M_Real, M_Vector3*);
+
+__END_DECLS
diff --git a/math/m_bezier_primitives.c b/math/m_bezier_primitives.c
new file mode 100644
index 000000000..7eb5fa73b
--- /dev/null
+++ b/math/m_bezier_primitives.c
@@ -0,0 +1,82 @@
+/* Copyright (c) Charles A. Daniels <http://cdaniels.net>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
+ * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <agar/core/core.h>
+
+#include <agar/math/m.h>
+#include <agar/math/m_bezier.h>
+
+#include <agar/gui/gui.h>
+#include <agar/gui/widget.h>
+#include <agar/gui/primitive.h>
+
+#include <agar/math/m_bezier_primitives.h>
+
+/* Draw a 2 endpoint 2 control point 2D bezier curve. This is a widget drawing
+ * primitive, so it should only be called during Draw().
+ *
+ * Detail specifies the number of line segments to use.
+ * */
+void M_DrawBezier2(AG_Widget* widget,
+ M_Real x1, M_Real y1, /* start point */
+ M_Real x2, M_Real y2, /* end point */
+ M_Real cx1, M_Real cy1, /* control point 1 */
+ M_Real cx2, M_Real cy2, /* control point 2 */
+ int detail, AG_Color* c
+ )
+{
+ M_PointSet2 points;
+ M_PointSet2 ctrl;
+ M_Vector2 pt;
+ M_Vector2 prev;
+
+ pt.x = 0;
+ pt.y = 0;
+ prev.x = 0;
+ prev.y = 0;
+
+ M_PointSetInit2(&points);
+ M_PointSetInit2(&ctrl);
+ M_PointSetAlloc2(&points, 4);
+ M_PointSetAlloc2(&ctrl, 4);
+
+ M_PointSetAdd2(&points, (M_Vector2) {.x = x1, .y = y1});
+ M_PointSetAdd2(&points, (M_Vector2) {.x = x2, .y = y2});
+ M_PointSetAdd2(&points, (M_Vector2) {.x = cx1, .y = cy1});
+ M_PointSetAdd2(&points, (M_Vector2) {.x = cx2, .y = cy2});
+
+ M_BezierForm2(&points, &ctrl);
+
+ for (int k = 0 ; k < detail ; k++) {
+ prev = pt;
+ M_BezierCurve2(&ctrl, ((float) k) / ((float) detail), &pt);
+ if (k != 0) {
+ AG_DrawLine(widget, prev.x, prev.y, pt.x, pt.y, c);
+ }
+ }
+
+ M_PointSetFree2(&points);
+ M_PointSetFree2(&ctrl);
+
+}
+
diff --git a/math/m_bezier_primitives.h b/math/m_bezier_primitives.h
new file mode 100644
index 000000000..933de8b35
--- /dev/null
+++ b/math/m_bezier_primitives.h
@@ -0,0 +1,17 @@
+/* Public domain */
+
+#ifndef M_BEZIER_PRIMITIVES_H
+#define M_BEZIER_PRIMITIVES_H
+
+#include <agar/math/begin.h>
+
+__BEGIN_DECLS
+
+void M_DrawBezier2(AG_Widget*, M_Real, M_Real, M_Real, M_Real, M_Real,
+ M_Real, M_Real, M_Real, int, AG_Color*);
+
+__END_DECLS
+
+#include <agar/math/close.h>
+
+#endif /* M_BEZIER_PRIMITIVES_H */
diff --git a/math/m_geometry.h b/math/m_geometry.h
index e76d9afe1..a82162e14 100644
--- a/math/m_geometry.h
+++ b/math/m_geometry.h
@@ -223,6 +223,7 @@ typedef struct m_point_set3i {
#include <agar/math/m_polygon.h>
#include <agar/math/m_polyhedron.h>
#include <agar/math/m_point_set.h>
+#include <agar/math/m_bezier.h>
__BEGIN_DECLS
diff --git a/math/m_gui.h b/math/m_gui.h
index 155b56fe1..836d3b647 100644
--- a/math/m_gui.h
+++ b/math/m_gui.h
@@ -50,5 +50,6 @@ __END_DECLS
#include <agar/math/m_plotter.h>
#include <agar/math/m_matview.h>
+#include <agar/math/m_bezier_primitives.h>
#endif /* _AGAR_MATH_M_GUI_H_ */
diff --git a/tests/Makefile b/tests/Makefile
index 8e196c6cd..436518896 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -24,6 +24,8 @@ SRCS= agartest.c ${SRCS_EXTRA} \
console.c \
customwidget.c \
customwidget_mywidget.c \
+ bezier.c \
+ bezier_widget.c \
fixedres.c \
focusing.c \
fonts.c \
diff --git a/tests/agartest.c b/tests/agartest.c
index b231efc4a..7502868d6 100644
--- a/tests/agartest.c
+++ b/tests/agartest.c
@@ -71,6 +71,7 @@ extern const AG_TestCase userTest;
#endif
extern const AG_TestCase widgetsTest;
extern const AG_TestCase windowsTest;
+extern const AG_TestCase bezierTest;
const AG_TestCase *testCases[] = {
#ifdef AG_UNICODE
@@ -128,6 +129,7 @@ const AG_TestCase *testCases[] = {
#endif
&widgetsTest,
&windowsTest,
+ &bezierTest,
NULL
};
--
2.17.1
_______________________________________________
Agar mailing list
[email protected]
http://libagar.org/lists.html
