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 "Polyline.h"
23#include "graphics/Graphics.h"
24
25// C++
26#include <algorithm>
27
28// treat adjacent segments with angles between their directions <5 degree as straight
29static const float LINES_PARALLEL_EPS = 0.05f;
30
31namespace love
32{
33namespace graphics
34{
35
36void Polyline::render(const Vector2 *coords, size_t count, size_t size_hint, float halfwidth, float pixel_size, bool draw_overdraw)
37{
38 static std::vector<Vector2> anchors;
39 anchors.clear();
40 anchors.reserve(size_hint);
41
42 static std::vector<Vector2> normals;
43 normals.clear();
44 normals.reserve(size_hint);
45
46 // prepare vertex arrays
47 if (draw_overdraw)
48 halfwidth -= pixel_size * 0.3f;
49
50 // compute sleeve
51 bool is_looping = (coords[0] == coords[count - 1]);
52 Vector2 segment;
53 if (!is_looping) // virtual starting point at second point mirrored on first point
54 segment = coords[1] - coords[0];
55 else // virtual starting point at last vertex
56 segment = coords[0] - coords[count - 2];
57
58 float segmentLength = segment.getLength();
59 Vector2 segmentNormal = segment.getNormal(halfwidth / segmentLength);
60
61 Vector2 pointA, pointB(coords[0]);
62 for (size_t i = 0; i + 1 < count; i++)
63 {
64 pointA = pointB;
65 pointB = coords[i + 1];
66 renderEdge(anchors, normals, segment, segmentLength, segmentNormal, pointA, pointB, halfwidth);
67 }
68
69 pointA = pointB;
70 pointB = is_looping ? coords[1] : pointB + segment;
71 renderEdge(anchors, normals, segment, segmentLength, segmentNormal, pointA, pointB, halfwidth);
72
73 vertex_count = normals.size();
74
75 size_t extra_vertices = 0;
76
77 if (draw_overdraw)
78 {
79 calc_overdraw_vertex_count(is_looping);
80
81 // When drawing overdraw lines using triangle strips, we want to add an
82 // extra degenerate triangle in between the core line and the overdraw
83 // line in order to break up the strip into two. This will let us draw
84 // everything in one draw call.
85 if (triangle_mode == vertex::TriangleIndexMode::STRIP)
86 extra_vertices = 2;
87 }
88
89 // Use a single linear array for both the regular and overdraw vertices.
90 vertices = new Vector2[vertex_count + extra_vertices + overdraw_vertex_count];
91
92 for (size_t i = 0; i < vertex_count; ++i)
93 vertices[i] = anchors[i] + normals[i];
94
95 if (draw_overdraw)
96 {
97 overdraw = vertices + vertex_count + extra_vertices;
98 overdraw_vertex_start = vertex_count + extra_vertices;
99 render_overdraw(normals, pixel_size, is_looping);
100 }
101
102 // Add the degenerate triangle strip.
103 if (extra_vertices)
104 {
105 vertices[vertex_count + 0] = vertices[vertex_count - 1];
106 vertices[vertex_count + 1] = vertices[overdraw_vertex_start];
107 }
108}
109
110void NoneJoinPolyline::renderEdge(std::vector<Vector2> &anchors, std::vector<Vector2> &normals,
111 Vector2 &segment, float &segmentLength, Vector2 &segmentNormal,
112 const Vector2 &pointA, const Vector2 &pointB, float halfWidth)
113{
114 // ns1------ns2
115 // | |
116 // q ------ r
117 // | |
118 // (-ns1)----(-ns2)
119
120 anchors.push_back(pointA);
121 anchors.push_back(pointA);
122 normals.push_back(segmentNormal);
123 normals.push_back(-segmentNormal);
124
125 segment = (pointB - pointA);
126 segmentLength = segment.getLength();
127 segmentNormal = segment.getNormal(halfWidth / segmentLength);
128
129 anchors.push_back(pointA);
130 anchors.push_back(pointA);
131 normals.push_back(segmentNormal);
132 normals.push_back(-segmentNormal);
133}
134
135
136/** Calculate line boundary points.
137 *
138 * Sketch:
139 *
140 * u1
141 * -------------+---...___
142 * | ```'''-- ---
143 * p- - - - - - q- - . _ _ | w/2
144 * | ` ' ' r +
145 * -------------+---...___ | w/2
146 * u2 ```'''-- ---
147 *
148 * u1 and u2 depend on four things:
149 * - the half line width w/2
150 * - the previous line vertex p
151 * - the current line vertex q
152 * - the next line vertex r
153 *
154 * u1/u2 are the intersection points of the parallel lines to p-q and q-r,
155 * i.e. the point where
156 *
157 * (q + w/2 * ns) + lambda * (q - p) = (q + w/2 * nt) + mu * (r - q) (u1)
158 * (q - w/2 * ns) + lambda * (q - p) = (q - w/2 * nt) + mu * (r - q) (u2)
159 *
160 * with ns,nt being the normals on the segments s = p-q and t = q-r,
161 *
162 * ns = perp(s) / |s|
163 * nt = perp(t) / |t|.
164 *
165 * Using the linear equation system (similar for u2)
166 *
167 * q + w/2 * ns + lambda * s - (q + w/2 * nt + mu * t) = 0 (u1)
168 * <=> q-q + lambda * s - mu * t = (nt - ns) * w/2
169 * <=> lambda * s - mu * t = (nt - ns) * w/2
170 *
171 * the intersection points can be efficiently calculated using Cramer's rule.
172 */
173void MiterJoinPolyline::renderEdge(std::vector<Vector2> &anchors, std::vector<Vector2> &normals,
174 Vector2 &segment, float &segmentLength, Vector2 &segmentNormal,
175 const Vector2 &pointA, const Vector2 &pointB, float halfwidth)
176{
177 Vector2 newSegment = (pointB - pointA);
178 float newSegmentLength = newSegment.getLength();
179 if (newSegmentLength == 0.0f)
180 {
181 // degenerate segment, skip it
182 return;
183 }
184
185 Vector2 newSegmentNormal = newSegment.getNormal(halfwidth / newSegmentLength);
186
187 anchors.push_back(pointA);
188 anchors.push_back(pointA);
189
190 float det = Vector2::cross(segment, newSegment);
191 if (fabs(det) / (segmentLength * newSegmentLength) < LINES_PARALLEL_EPS)
192 {
193 // lines parallel, compute as u1 = q + ns * w/2, u2 = q - ns * w/2
194 normals.push_back(segmentNormal);
195 normals.push_back(-segmentNormal);
196
197 if (Vector2::dot(segment, newSegment) < 0)
198 {
199 // line reverses direction; because the normal flips, the
200 // triangle strip would twist here, so insert a zero-size
201 // quad to contain the twist
202 // ____.___.____
203 // | |\ /| |
204 // p q X q r
205 // |____|/ \|____|
206 anchors.push_back(pointA);
207 anchors.push_back(pointA);
208 normals.push_back(-segmentNormal);
209 normals.push_back(segmentNormal);
210 }
211 }
212 else
213 {
214 // cramers rule
215 float lambda = Vector2::cross((newSegmentNormal - segmentNormal), newSegment) / det;
216 Vector2 d = segmentNormal + segment * lambda;
217 normals.push_back(d);
218 normals.push_back(-d);
219 }
220
221 segment = newSegment;
222 segmentNormal = newSegmentNormal;
223 segmentLength = newSegmentLength;
224}
225
226/** Calculate line boundary points.
227 *
228 * Sketch:
229 *
230 * uh1___uh2
231 * .' '.
232 * .' q '.
233 * .' ' ' '.
234 *.' ' .'. ' '.
235 * ' .' ul'. '
236 * p .' '. r
237 *
238 *
239 * ul can be found as above, uh1 and uh2 are much simpler:
240 *
241 * uh1 = q + ns * w/2, uh2 = q + nt * w/2
242 */
243void BevelJoinPolyline::renderEdge(std::vector<Vector2> &anchors, std::vector<Vector2> &normals,
244 Vector2 &segment, float &segmentLength, Vector2 &segmentNormal,
245 const Vector2 &pointA, const Vector2 &pointB, float halfWidth)
246{
247 Vector2 newSegment = (pointB - pointA);
248 float newSegmentLength = newSegment.getLength();
249
250 float det = Vector2::cross(segment, newSegment);
251 if (fabs(det) / (segmentLength * newSegmentLength) < LINES_PARALLEL_EPS)
252 {
253 // lines parallel, compute as u1 = q + ns * w/2, u2 = q - ns * w/2
254 Vector2 newSegmentNormal = newSegment.getNormal(halfWidth / newSegmentLength);
255 anchors.push_back(pointA);
256 anchors.push_back(pointA);
257 normals.push_back(segmentNormal);
258 normals.push_back(-segmentNormal);
259
260 if (Vector2::dot(segment, newSegment) < 0)
261 {
262 // line reverses direction; same as for miter
263 anchors.push_back(pointA);
264 anchors.push_back(pointA);
265 normals.push_back(-segmentNormal);
266 normals.push_back(segmentNormal);
267 }
268
269 segment = newSegment;
270 segmentLength = newSegmentLength;
271 segmentNormal = newSegmentNormal;
272 return; // early out
273 }
274
275 // cramers rule
276 Vector2 newSegmentNormal = newSegment.getNormal(halfWidth / newSegmentLength);
277 float lambda = Vector2::cross((newSegmentNormal - segmentNormal), newSegment) / det;
278 Vector2 d = segmentNormal + segment * lambda;
279
280 anchors.push_back(pointA);
281 anchors.push_back(pointA);
282 anchors.push_back(pointA);
283 anchors.push_back(pointA);
284 if (det > 0) // 'left' turn -> intersection on the top
285 {
286 normals.push_back(d);
287 normals.push_back(-segmentNormal);
288 normals.push_back(d);
289 normals.push_back(-newSegmentNormal);
290 }
291 else
292 {
293 normals.push_back(segmentNormal);
294 normals.push_back(-d);
295 normals.push_back(newSegmentNormal);
296 normals.push_back(-d);
297 }
298 segment = newSegment;
299 segmentLength = newSegmentLength;
300 segmentNormal = newSegmentNormal;
301}
302
303void Polyline::calc_overdraw_vertex_count(bool is_looping)
304{
305 overdraw_vertex_count = 2 * vertex_count + (is_looping ? 0 : 2);
306}
307
308void Polyline::render_overdraw(const std::vector<Vector2> &normals, float pixel_size, bool is_looping)
309{
310 // upper segment
311 for (size_t i = 0; i + 1 < vertex_count; i += 2)
312 {
313 overdraw[i] = vertices[i];
314 overdraw[i+1] = vertices[i] + normals[i] * (pixel_size / normals[i].getLength());
315 }
316 // lower segment
317 for (size_t i = 0; i + 1 < vertex_count; i += 2)
318 {
319 size_t k = vertex_count - i - 1;
320 overdraw[vertex_count + i] = vertices[k];
321 overdraw[vertex_count + i+1] = vertices[k] + normals[k] * (pixel_size / normals[k].getLength());
322 }
323
324 // if not looping, the outer overdraw vertices need to be displaced
325 // to cover the line endings, i.e.:
326 // +- - - - //- - + +- - - - - //- - - +
327 // +-------//-----+ : +-------//-----+ :
328 // | core // line | --> : | core // line | :
329 // +-----//-------+ : +-----//-------+ :
330 // +- - //- - - - + +- - - //- - - - - +
331 if (!is_looping)
332 {
333 // left edge
334 Vector2 spacer = (overdraw[1] - overdraw[3]);
335 spacer.normalize(pixel_size);
336 overdraw[1] += spacer;
337 overdraw[overdraw_vertex_count - 3] += spacer;
338
339 // right edge
340 spacer = (overdraw[vertex_count-1] - overdraw[vertex_count-3]);
341 spacer.normalize(pixel_size);
342 overdraw[vertex_count-1] += spacer;
343 overdraw[vertex_count+1] += spacer;
344
345 // we need to draw two more triangles to close the
346 // overdraw at the line start.
347 overdraw[overdraw_vertex_count-2] = overdraw[0];
348 overdraw[overdraw_vertex_count-1] = overdraw[1];
349 }
350}
351
352void NoneJoinPolyline::calc_overdraw_vertex_count(bool /*is_looping*/)
353{
354 overdraw_vertex_count = 4 * (vertex_count-2); // less than ideal
355}
356
357void NoneJoinPolyline::render_overdraw(const std::vector<Vector2> &/*normals*/, float pixel_size, bool /*is_looping*/)
358{
359 for (size_t i = 2; i + 3 < vertex_count; i += 4)
360 {
361 // v0-v2
362 // | / | <- main quad line
363 // v1-v3
364
365 Vector2 s = vertices[i+0] - vertices[i+2];
366 Vector2 t = vertices[i+0] - vertices[i+1];
367 s.normalize(pixel_size);
368 t.normalize(pixel_size);
369
370 const size_t k = 4 * (i - 2);
371
372 overdraw[k+0] = vertices[i+0];
373 overdraw[k+1] = vertices[i+1];
374 overdraw[k+2] = vertices[i+0] + s + t;
375 overdraw[k+3] = vertices[i+1] + s - t;
376
377 overdraw[k+4] = vertices[i+1];
378 overdraw[k+5] = vertices[i+3];
379 overdraw[k+6] = vertices[i+1] + s - t;
380 overdraw[k+7] = vertices[i+3] - s - t;
381
382 overdraw[k+ 8] = vertices[i+3];
383 overdraw[k+ 9] = vertices[i+2];
384 overdraw[k+10] = vertices[i+3] - s - t;
385 overdraw[k+11] = vertices[i+2] - s + t;
386
387 overdraw[k+12] = vertices[i+2];
388 overdraw[k+13] = vertices[i+0];
389 overdraw[k+14] = vertices[i+2] - s + t;
390 overdraw[k+15] = vertices[i+0] + s + t;
391 }
392}
393
394Polyline::~Polyline()
395{
396 if (vertices)
397 delete[] vertices;
398}
399
400void Polyline::draw(love::graphics::Graphics *gfx)
401{
402 const Matrix4 &t = gfx->getTransform();
403 bool is2D = t.isAffine2DTransform();
404 Color32 curcolor = toColor32(gfx->getColor());
405
406 int overdraw_start = (int) overdraw_vertex_start;
407 int overdraw_count = (int) overdraw_vertex_count;
408
409 int total_vertex_count = (int) vertex_count;
410 if (overdraw)
411 total_vertex_count = overdraw_start + overdraw_count;
412
413 // love's automatic batching can only deal with < 65k vertices per draw.
414 // uint16_max - 3 is evenly divisible by 6 (needed for quads mode).
415 int maxvertices = LOVE_UINT16_MAX - 3;
416
417 int advance = maxvertices;
418 if (triangle_mode == vertex::TriangleIndexMode::STRIP)
419 advance -= 2;
420
421 for (int vertex_start = 0; vertex_start < total_vertex_count; vertex_start += advance)
422 {
423 const Vector2 *verts = vertices + vertex_start;
424
425 Graphics::StreamDrawCommand cmd;
426 cmd.formats[0] = vertex::getSinglePositionFormat(is2D);
427 cmd.formats[1] = vertex::CommonFormat::RGBAub;
428 cmd.indexMode = triangle_mode;
429 cmd.vertexCount = std::min(maxvertices, total_vertex_count - vertex_start);
430
431 Graphics::StreamVertexData data = gfx->requestStreamDraw(cmd);
432
433 if (is2D)
434 t.transformXY((Vector2 *) data.stream[0], verts, cmd.vertexCount);
435 else
436 t.transformXY0((Vector3 *) data.stream[0], verts, cmd.vertexCount);
437
438 Color32 *colordata = (Color32 *) data.stream[1];
439
440 int draw_rough_count = std::min(cmd.vertexCount, (int) vertex_count - vertex_start);
441
442 // Constant vertex color up to the overdraw vertices.
443 for (int i = 0; i < draw_rough_count; i++)
444 colordata[i] = curcolor;
445
446 if (overdraw)
447 {
448 int draw_remaining_count = cmd.vertexCount - draw_rough_count;
449
450 int draw_overdraw_begin = overdraw_start - vertex_start;
451 int draw_overdraw_end = draw_overdraw_begin + overdraw_count;
452
453 draw_overdraw_begin = std::max(0, draw_overdraw_begin);
454
455 int draw_overdraw_count = std::min(draw_remaining_count, draw_overdraw_end - draw_overdraw_begin);
456
457 if (draw_overdraw_count > 0)
458 {
459 Color32 *colors = colordata + draw_overdraw_begin;
460 fill_color_array(curcolor, colors, draw_overdraw_count);
461 }
462 }
463 }
464}
465
466void Polyline::fill_color_array(Color32 constant_color, Color32 *colors, int count)
467{
468 for (int i = 0; i < count; ++i)
469 {
470 Color32 c = constant_color;
471 c.a *= (i+1) % 2; // avoids branching. equiv to if (i%2 == 1) c.a = 0;
472 colors[i] = c;
473 }
474}
475
476void NoneJoinPolyline::fill_color_array(Color32 constant_color, Color32 *colors, int count)
477{
478 for (int i = 0; i < count; ++i)
479 {
480 Color32 c = constant_color;
481 c.a *= (i & 3) < 2; // if (i % 4 == 2 || i % 4 == 3) c.a = 0
482 colors[i] = c;
483 }
484}
485
486} // graphics
487} // love
488