1/**
2 * Copyright (c) 2006-2023 LOVE Development Team
3 *
4 * This software is provided 'as-is', without any express or implied
5 * warranty. In no event will the authors be held liable for any damages
6 * arising from the use of this software.
7 *
8 * Permission is granted to anyone to use this software for any purpose,
9 * including commercial applications, and to alter it and redistribute it
10 * freely, subject to the following restrictions:
11 *
12 * 1. The origin of this software must not be misrepresented; you must not
13 * claim that you wrote the original software. If you use this software
14 * in a product, an acknowledgment in the product documentation would be
15 * appreciated but is not required.
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 * misrepresented as being the original software.
18 * 3. This notice may not be removed or altered from any source distribution.
19 **/
20
21// LOVE
22#include "MathModule.h"
23#include "common/Vector.h"
24#include "common/int.h"
25#include "common/StringMap.h"
26#include "BezierCurve.h"
27#include "Transform.h"
28
29// STL
30#include <cmath>
31#include <list>
32#include <iostream>
33
34// C
35#include <time.h>
36
37using std::list;
38using love::Vector2;
39
40namespace
41{
42
43// check if an angle is oriented counter clockwise
44inline bool is_oriented_ccw(const Vector2 &a, const Vector2 &b, const Vector2 &c)
45{
46 // return det(b-a, c-a) >= 0
47 return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) >= 0;
48}
49
50// check if a and b are on the same side of the line c->d
51bool on_same_side(const Vector2 &a, const Vector2 &b, const Vector2 &c, const Vector2 &d)
52{
53 float px = d.x - c.x, py = d.y - c.y;
54 // return det(p, a-c) * det(p, b-c) >= 0
55 float l = px * (a.y - c.y) - py * (a.x - c.x);
56 float m = px * (b.y - c.y) - py * (b.x - c.x);
57 return l * m >= 0;
58}
59
60// checks is p is contained in the triangle abc
61inline bool point_in_triangle(const Vector2 &p, const Vector2 &a, const Vector2 &b, const Vector2 &c)
62{
63 return on_same_side(p,a, b,c) && on_same_side(p,b, a,c) && on_same_side(p,c, a,b);
64}
65
66// checks if any vertex in `vertices' is in the triangle abc.
67bool any_point_in_triangle(const std::list<const Vector2 *> &vertices, const Vector2 &a, const Vector2 &b, const Vector2 &c)
68{
69 for (const Vector2 *p : vertices)
70 {
71 if ((p != &a) && (p != &b) && (p != &c) && point_in_triangle(*p, a,b,c)) // oh god...
72 return true;
73 }
74
75 return false;
76}
77
78inline bool is_ear(const Vector2 &a, const Vector2 &b, const Vector2 &c, const std::list<const Vector2 *> &vertices)
79{
80 return is_oriented_ccw(a,b,c) && !any_point_in_triangle(vertices, a,b,c);
81}
82
83} // anonymous namespace
84
85namespace love
86{
87namespace math
88{
89
90std::vector<Triangle> triangulate(const std::vector<love::Vector2> &polygon)
91{
92 if (polygon.size() < 3)
93 throw love::Exception("Not a polygon");
94 else if (polygon.size() == 3)
95 return std::vector<Triangle>(1, Triangle(polygon[0], polygon[1], polygon[2]));
96
97 // collect list of connections and record leftmost item to check if the polygon
98 // has the expected winding
99 std::vector<size_t> next_idx(polygon.size()), prev_idx(polygon.size());
100 size_t idx_lm = 0;
101 for (size_t i = 0; i < polygon.size(); ++i)
102 {
103 const love::Vector2 &lm = polygon[idx_lm], &p = polygon[i];
104 if (p.x < lm.x || (p.x == lm.x && p.y < lm.y))
105 idx_lm = i;
106 next_idx[i] = i+1;
107 prev_idx[i] = i-1;
108 }
109 next_idx[next_idx.size()-1] = 0;
110 prev_idx[0] = prev_idx.size()-1;
111
112 // check if the polygon has the expected winding and reverse polygon if needed
113 if (!is_oriented_ccw(polygon[prev_idx[idx_lm]], polygon[idx_lm], polygon[next_idx[idx_lm]]))
114 next_idx.swap(prev_idx);
115
116 // collect list of concave polygons
117 std::list<const love::Vector2 *> concave_vertices;
118 for (size_t i = 0; i < polygon.size(); ++i)
119 {
120 if (!is_oriented_ccw(polygon[prev_idx[i]], polygon[i], polygon[next_idx[i]]))
121 concave_vertices.push_back(&polygon[i]);
122 }
123
124 // triangulation according to kong
125 std::vector<Triangle> triangles;
126 size_t n_vertices = polygon.size();
127 size_t current = 1, skipped = 0, next, prev;
128 while (n_vertices > 3)
129 {
130 next = next_idx[current];
131 prev = prev_idx[current];
132 const Vector2 &a = polygon[prev], &b = polygon[current], &c = polygon[next];
133 if (is_ear(a,b,c, concave_vertices))
134 {
135 triangles.push_back(Triangle(a,b,c));
136 next_idx[prev] = next;
137 prev_idx[next] = prev;
138 concave_vertices.remove(&b);
139 --n_vertices;
140 skipped = 0;
141 }
142 else if (++skipped > n_vertices)
143 {
144 throw love::Exception("Cannot triangulate polygon.");
145 }
146 current = next;
147 }
148 next = next_idx[current];
149 prev = prev_idx[current];
150 triangles.push_back(Triangle(polygon[prev], polygon[current], polygon[next]));
151
152 return triangles;
153}
154
155bool isConvex(const std::vector<love::Vector2> &polygon)
156{
157 if (polygon.size() < 3)
158 return false;
159
160 // a polygon is convex if all corners turn in the same direction
161 // turning direction can be determined using the cross-product of
162 // the forward difference vectors
163 size_t i = polygon.size() - 2, j = polygon.size() - 1, k = 0;
164 Vector2 p(polygon[j] - polygon[i]);
165 Vector2 q(polygon[k] - polygon[j]);
166 float winding = Vector2::cross(p, q);
167
168 while (k+1 < polygon.size())
169 {
170 i = j; j = k; k++;
171 p = polygon[j] - polygon[i];
172 q = polygon[k] - polygon[j];
173
174 if (Vector2::cross(p, q) * winding < 0)
175 return false;
176 }
177 return true;
178}
179
180/**
181 * http://en.wikipedia.org/wiki/SRGB#The_reverse_transformation
182 **/
183float gammaToLinear(float c)
184{
185 if (c <= 0.04045f)
186 return c / 12.92f;
187 else
188 return powf((c + 0.055f) / 1.055f, 2.4f);
189}
190
191/**
192 * http://en.wikipedia.org/wiki/SRGB#The_forward_transformation_.28CIE_xyY_or_CIE_XYZ_to_sRGB.29
193 **/
194float linearToGamma(float c)
195{
196 if (c <= 0.0031308f)
197 return c * 12.92f;
198 else
199 return 1.055f * powf(c, 1.0f / 2.4f) - 0.055f;
200}
201
202Math::Math()
203 : rng()
204{
205 RandomGenerator::Seed seed;
206 seed.b64 = (uint64) time(nullptr);
207 rng.setSeed(seed);
208}
209
210Math::~Math()
211{
212}
213
214RandomGenerator *Math::newRandomGenerator()
215{
216 return new RandomGenerator();
217}
218
219BezierCurve *Math::newBezierCurve(const std::vector<Vector2> &points)
220{
221 return new BezierCurve(points);
222}
223
224Transform *Math::newTransform()
225{
226 return new Transform();
227}
228
229Transform *Math::newTransform(float x, float y, float a, float sx, float sy, float ox, float oy, float kx, float ky)
230{
231 return new Transform(x, y, a, sx, sy, ox, oy, kx, ky);
232}
233
234} // math
235} // love
236