1/**************************************************************************/
2/* line_builder.cpp */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#include "line_builder.h"
32
33#include "core/math/geometry_2d.h"
34
35// Utility method.
36static inline Vector2 interpolate(const Rect2 &r, const Vector2 &v) {
37 return Vector2(
38 Math::lerp(r.position.x, r.position.x + r.get_size().x, v.x),
39 Math::lerp(r.position.y, r.position.y + r.get_size().y, v.y));
40}
41
42LineBuilder::LineBuilder() {
43}
44
45void LineBuilder::build() {
46 // Need at least 2 points to draw a line, so clear the output and return.
47 if (points.size() < 2) {
48 vertices.clear();
49 colors.clear();
50 indices.clear();
51 uvs.clear();
52 return;
53 }
54
55 ERR_FAIL_COND(tile_aspect <= 0.f);
56
57 const float hw = width / 2.f;
58 const float hw_sq = hw * hw;
59 const float sharp_limit_sq = sharp_limit * sharp_limit;
60 const int point_count = points.size();
61 const bool wrap_around = closed && point_count > 2;
62
63 _interpolate_color = gradient != nullptr;
64 const bool retrieve_curve = curve != nullptr;
65 const bool distance_required = _interpolate_color || retrieve_curve ||
66 texture_mode == Line2D::LINE_TEXTURE_TILE ||
67 texture_mode == Line2D::LINE_TEXTURE_STRETCH;
68
69 // Initial values
70
71 Vector2 pos0 = points[0];
72 Vector2 pos1 = points[1];
73 Vector2 f0 = (pos1 - pos0).normalized();
74 Vector2 u0 = f0.orthogonal();
75 Vector2 pos_up0 = pos0;
76 Vector2 pos_down0 = pos0;
77
78 Color color0;
79 Color color1;
80
81 float current_distance0 = 0.f;
82 float current_distance1 = 0.f;
83 float total_distance = 0.f;
84
85 float width_factor = 1.f;
86 float modified_hw = hw;
87 if (retrieve_curve) {
88 width_factor = curve->sample_baked(0.f);
89 modified_hw = hw * width_factor;
90 }
91
92 if (distance_required) {
93 // Calculate the total distance.
94 for (int i = 1; i < point_count; ++i) {
95 total_distance += points[i].distance_to(points[i - 1]);
96 }
97 if (wrap_around) {
98 total_distance += points[point_count - 1].distance_to(pos0);
99 } else {
100 // Adjust the total distance.
101 // The line's outer length may be a little higher due to the end caps.
102 if (begin_cap_mode == Line2D::LINE_CAP_BOX || begin_cap_mode == Line2D::LINE_CAP_ROUND) {
103 total_distance += modified_hw;
104 }
105 if (end_cap_mode == Line2D::LINE_CAP_BOX || end_cap_mode == Line2D::LINE_CAP_ROUND) {
106 if (retrieve_curve) {
107 total_distance += hw * curve->sample_baked(1.f);
108 } else {
109 total_distance += hw;
110 }
111 }
112 }
113 }
114
115 if (_interpolate_color) {
116 color0 = gradient->get_color(0);
117 } else {
118 colors.push_back(default_color);
119 }
120
121 float uvx0 = 0.f;
122 float uvx1 = 0.f;
123
124 pos_up0 += u0 * modified_hw;
125 pos_down0 -= u0 * modified_hw;
126
127 // Begin cap
128 if (!wrap_around) {
129 if (begin_cap_mode == Line2D::LINE_CAP_BOX) {
130 // Push back first vertices a little bit.
131 pos_up0 -= f0 * modified_hw;
132 pos_down0 -= f0 * modified_hw;
133
134 current_distance0 += modified_hw;
135 current_distance1 = current_distance0;
136 } else if (begin_cap_mode == Line2D::LINE_CAP_ROUND) {
137 if (texture_mode == Line2D::LINE_TEXTURE_TILE) {
138 uvx0 = width_factor * 0.5f / tile_aspect;
139 } else if (texture_mode == Line2D::LINE_TEXTURE_STRETCH) {
140 uvx0 = width * width_factor / total_distance;
141 }
142 new_arc(pos0, pos_up0 - pos0, -Math_PI, color0, Rect2(0.f, 0.f, uvx0 * 2, 1.f));
143 current_distance0 += modified_hw;
144 current_distance1 = current_distance0;
145 }
146 strip_begin(pos_up0, pos_down0, color0, uvx0);
147 }
148
149 /*
150 * pos_up0 ------------- pos_up1 --------------------
151 * | |
152 * pos0 - - - - - - - - - pos1 - - - - - - - - - pos2
153 * | |
154 * pos_down0 ------------ pos_down1 ------------------
155 *
156 * i-1 i i+1
157 */
158
159 // http://labs.hyperandroid.com/tag/opengl-lines
160 // (not the same implementation but visuals help a lot)
161
162 // If the polyline wraps around, then draw two more segments with joints:
163 // The last one, which should normally end with an end cap, and the one that matches the end and the beginning.
164 int segments_count = wrap_around ? point_count : (point_count - 2);
165 // The wraparound case starts with a "fake walk" from the end of the polyline
166 // to its beginning, so that its first joint is correct, without drawing anything.
167 int first_point = wrap_around ? -1 : 1;
168
169 // If the line wraps around, these variables will be used for the final segment.
170 Vector2 first_pos_up, first_pos_down;
171 bool is_first_joint_sharp = false;
172
173 // For each additional segment
174 for (int i = first_point; i <= segments_count; ++i) {
175 pos1 = points[(i == -1) ? point_count - 1 : i % point_count]; // First point.
176 Vector2 pos2 = points[(i + 1) % point_count]; // Second point.
177
178 Vector2 f1 = (pos2 - pos1).normalized();
179 Vector2 u1 = f1.orthogonal();
180
181 // Determine joint orientation.
182 float dp = u0.dot(f1);
183 const Orientation orientation = (dp > 0.f ? UP : DOWN);
184
185 if (distance_required && i >= 1) {
186 current_distance1 += pos0.distance_to(pos1);
187 }
188 if (_interpolate_color) {
189 color1 = gradient->get_color_at_offset(current_distance1 / total_distance);
190 }
191 if (retrieve_curve) {
192 width_factor = curve->sample_baked(current_distance1 / total_distance);
193 modified_hw = hw * width_factor;
194 }
195
196 Vector2 inner_normal0 = u0 * modified_hw;
197 Vector2 inner_normal1 = u1 * modified_hw;
198 if (orientation == DOWN) {
199 inner_normal0 = -inner_normal0;
200 inner_normal1 = -inner_normal1;
201 }
202
203 /*
204 * ---------------------------
205 * /
206 * 0 / 1
207 * / /
208 * --------------------x------ /
209 * / / (here shown with orientation == DOWN)
210 * / /
211 * / /
212 * / /
213 * 2 /
214 * /
215 */
216
217 // Find inner intersection at the joint.
218 Vector2 corner_pos_in, corner_pos_out;
219 bool is_intersecting = Geometry2D::segment_intersects_segment(
220 pos0 + inner_normal0, pos1 + inner_normal0,
221 pos1 + inner_normal1, pos2 + inner_normal1,
222 &corner_pos_in);
223
224 if (is_intersecting) {
225 // Inner parts of the segments intersect.
226 corner_pos_out = 2.f * pos1 - corner_pos_in;
227 } else {
228 // No intersection, segments are too sharp or they overlap.
229 corner_pos_in = pos1 + inner_normal0;
230 corner_pos_out = pos1 - inner_normal0;
231 }
232
233 Vector2 corner_pos_up, corner_pos_down;
234 if (orientation == UP) {
235 corner_pos_up = corner_pos_in;
236 corner_pos_down = corner_pos_out;
237 } else {
238 corner_pos_up = corner_pos_out;
239 corner_pos_down = corner_pos_in;
240 }
241
242 Line2D::LineJointMode current_joint_mode = joint_mode;
243
244 Vector2 pos_up1, pos_down1;
245 if (is_intersecting) {
246 // Fallback on bevel if sharp angle is too high (because it would produce very long miters).
247 float width_factor_sq = width_factor * width_factor;
248 if (current_joint_mode == Line2D::LINE_JOINT_SHARP && corner_pos_out.distance_squared_to(pos1) / (hw_sq * width_factor_sq) > sharp_limit_sq) {
249 current_joint_mode = Line2D::LINE_JOINT_BEVEL;
250 }
251 if (current_joint_mode == Line2D::LINE_JOINT_SHARP) {
252 // In this case, we won't create joint geometry,
253 // The previous and next line quads will directly share an edge.
254 pos_up1 = corner_pos_up;
255 pos_down1 = corner_pos_down;
256 } else {
257 // Bevel or round
258 if (orientation == UP) {
259 pos_up1 = corner_pos_up;
260 pos_down1 = pos1 - u0 * modified_hw;
261 } else {
262 pos_up1 = pos1 + u0 * modified_hw;
263 pos_down1 = corner_pos_down;
264 }
265 }
266 } else {
267 // No intersection: fallback
268 if (current_joint_mode == Line2D::LINE_JOINT_SHARP) {
269 // There is no fallback implementation for LINE_JOINT_SHARP so switch to the LINE_JOINT_BEVEL.
270 current_joint_mode = Line2D::LINE_JOINT_BEVEL;
271 }
272 pos_up1 = corner_pos_up;
273 pos_down1 = corner_pos_down;
274 }
275
276 // Triangles are clockwise.
277 if (texture_mode == Line2D::LINE_TEXTURE_TILE) {
278 uvx1 = current_distance1 / (width * tile_aspect);
279 } else if (texture_mode == Line2D::LINE_TEXTURE_STRETCH) {
280 uvx1 = current_distance1 / total_distance;
281 }
282
283 // Swap vars for use in the next line.
284 color0 = color1;
285 u0 = u1;
286 f0 = f1;
287 pos0 = pos1;
288 if (is_intersecting) {
289 if (current_joint_mode == Line2D::LINE_JOINT_SHARP) {
290 pos_up0 = pos_up1;
291 pos_down0 = pos_down1;
292 } else {
293 if (orientation == UP) {
294 pos_up0 = corner_pos_up;
295 pos_down0 = pos1 - u1 * modified_hw;
296 } else {
297 pos_up0 = pos1 + u1 * modified_hw;
298 pos_down0 = corner_pos_down;
299 }
300 }
301 } else {
302 pos_up0 = pos1 + u1 * modified_hw;
303 pos_down0 = pos1 - u1 * modified_hw;
304 }
305
306 // End the "fake pass" in the closed line case before the drawing subroutine.
307 if (i == -1) {
308 continue;
309 }
310
311 // For wrap-around polylines, store some kind of start positions of the first joint for the final connection.
312 if (wrap_around && i == 0) {
313 Vector2 first_pos_center = (pos_up1 + pos_down1) / 2;
314 float lerp_factor = 1.0 / width_factor;
315 first_pos_up = first_pos_center.lerp(pos_up1, lerp_factor);
316 first_pos_down = first_pos_center.lerp(pos_down1, lerp_factor);
317 is_first_joint_sharp = current_joint_mode == Line2D::LINE_JOINT_SHARP;
318 }
319
320 // Add current line body quad.
321 if (wrap_around && retrieve_curve && !is_first_joint_sharp && i == segments_count) {
322 // If the width curve is not seamless, we might need to fetch the line's start points to use them for the final connection.
323 Vector2 first_pos_center = (first_pos_up + first_pos_down) / 2;
324 strip_add_quad(first_pos_center.lerp(first_pos_up, width_factor), first_pos_center.lerp(first_pos_down, width_factor), color1, uvx1);
325 return;
326 } else {
327 strip_add_quad(pos_up1, pos_down1, color1, uvx1);
328 }
329
330 // From this point, bu0 and bd0 concern the next segment.
331 // Add joint geometry.
332 if (current_joint_mode != Line2D::LINE_JOINT_SHARP) {
333 /* ________________ cbegin
334 * / \
335 * / \
336 * ____________/_ _ _\ cend
337 * | |
338 * | |
339 * | |
340 */
341
342 Vector2 cbegin, cend;
343 if (orientation == UP) {
344 cbegin = pos_down1;
345 cend = pos_down0;
346 } else {
347 cbegin = pos_up1;
348 cend = pos_up0;
349 }
350
351 if (current_joint_mode == Line2D::LINE_JOINT_BEVEL && !(wrap_around && i == segments_count)) {
352 strip_add_tri(cend, orientation);
353 } else if (current_joint_mode == Line2D::LINE_JOINT_ROUND && !(wrap_around && i == segments_count)) {
354 Vector2 vbegin = cbegin - pos1;
355 Vector2 vend = cend - pos1;
356 strip_add_arc(pos1, vbegin.angle_to(vend), orientation);
357 }
358
359 if (!is_intersecting) {
360 // In this case the joint is too corrupted to be re-used,
361 // start again the strip with fallback points
362 strip_begin(pos_up0, pos_down0, color1, uvx1);
363 }
364 }
365 }
366
367 // Draw the last (or only) segment, with its end cap logic.
368 if (!wrap_around) {
369 pos1 = points[point_count - 1];
370
371 if (distance_required) {
372 current_distance1 += pos0.distance_to(pos1);
373 }
374 if (_interpolate_color) {
375 color1 = gradient->get_color(gradient->get_point_count() - 1);
376 }
377 if (retrieve_curve) {
378 width_factor = curve->sample_baked(1.f);
379 modified_hw = hw * width_factor;
380 }
381
382 Vector2 pos_up1 = pos1 + u0 * modified_hw;
383 Vector2 pos_down1 = pos1 - u0 * modified_hw;
384
385 // Add extra distance for a box end cap.
386 if (end_cap_mode == Line2D::LINE_CAP_BOX) {
387 pos_up1 += f0 * modified_hw;
388 pos_down1 += f0 * modified_hw;
389
390 current_distance1 += modified_hw;
391 }
392
393 if (texture_mode == Line2D::LINE_TEXTURE_TILE) {
394 uvx1 = current_distance1 / (width * tile_aspect);
395 } else if (texture_mode == Line2D::LINE_TEXTURE_STRETCH) {
396 uvx1 = current_distance1 / total_distance;
397 }
398
399 strip_add_quad(pos_up1, pos_down1, color1, uvx1);
400
401 // Custom drawing for a round end cap.
402 if (end_cap_mode == Line2D::LINE_CAP_ROUND) {
403 // Note: color is not used in case we don't interpolate.
404 Color color = _interpolate_color ? gradient->get_color(gradient->get_point_count() - 1) : Color(0, 0, 0);
405 float dist = 0;
406 if (texture_mode == Line2D::LINE_TEXTURE_TILE) {
407 dist = width_factor / tile_aspect;
408 } else if (texture_mode == Line2D::LINE_TEXTURE_STRETCH) {
409 dist = width * width_factor / total_distance;
410 }
411 new_arc(pos1, pos_up1 - pos1, Math_PI, color, Rect2(uvx1 - 0.5f * dist, 0.f, dist, 1.f));
412 }
413 }
414}
415
416void LineBuilder::strip_begin(Vector2 up, Vector2 down, Color color, float uvx) {
417 int vi = vertices.size();
418
419 vertices.push_back(up);
420 vertices.push_back(down);
421
422 if (_interpolate_color) {
423 colors.push_back(color);
424 colors.push_back(color);
425 }
426
427 if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
428 uvs.push_back(Vector2(uvx, 0.f));
429 uvs.push_back(Vector2(uvx, 1.f));
430 }
431
432 _last_index[UP] = vi;
433 _last_index[DOWN] = vi + 1;
434}
435
436void LineBuilder::strip_add_quad(Vector2 up, Vector2 down, Color color, float uvx) {
437 int vi = vertices.size();
438
439 vertices.push_back(up);
440 vertices.push_back(down);
441
442 if (_interpolate_color) {
443 colors.push_back(color);
444 colors.push_back(color);
445 }
446
447 if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
448 uvs.push_back(Vector2(uvx, 0.f));
449 uvs.push_back(Vector2(uvx, 1.f));
450 }
451
452 indices.push_back(_last_index[UP]);
453 indices.push_back(vi + 1);
454 indices.push_back(_last_index[DOWN]);
455 indices.push_back(_last_index[UP]);
456 indices.push_back(vi);
457 indices.push_back(vi + 1);
458
459 _last_index[UP] = vi;
460 _last_index[DOWN] = vi + 1;
461}
462
463void LineBuilder::strip_add_tri(Vector2 up, Orientation orientation) {
464 int vi = vertices.size();
465
466 vertices.push_back(up);
467
468 if (_interpolate_color) {
469 colors.push_back(colors[colors.size() - 1]);
470 }
471
472 Orientation opposite_orientation = orientation == UP ? DOWN : UP;
473
474 if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
475 // UVs are just one slice of the texture all along
476 // (otherwise we can't share the bottom vertex)
477 uvs.push_back(uvs[_last_index[opposite_orientation]]);
478 }
479
480 indices.push_back(_last_index[opposite_orientation]);
481 indices.push_back(vi);
482 indices.push_back(_last_index[orientation]);
483
484 _last_index[opposite_orientation] = vi;
485}
486
487void LineBuilder::strip_add_arc(Vector2 center, float angle_delta, Orientation orientation) {
488 // Take the two last vertices and extrude an arc made of triangles
489 // that all share one of the initial vertices
490
491 Orientation opposite_orientation = orientation == UP ? DOWN : UP;
492 Vector2 vbegin = vertices[_last_index[opposite_orientation]] - center;
493 float radius = vbegin.length();
494 float angle_step = Math_PI / static_cast<float>(round_precision);
495 float steps = Math::abs(angle_delta) / angle_step;
496
497 if (angle_delta < 0.f) {
498 angle_step = -angle_step;
499 }
500
501 float t = Vector2(1, 0).angle_to(vbegin);
502 float end_angle = t + angle_delta;
503 Vector2 rpos(0, 0);
504
505 // Arc vertices
506 for (int ti = 0; ti < steps; ++ti, t += angle_step) {
507 rpos = center + Vector2(Math::cos(t), Math::sin(t)) * radius;
508 strip_add_tri(rpos, orientation);
509 }
510
511 // Last arc vertex
512 rpos = center + Vector2(Math::cos(end_angle), Math::sin(end_angle)) * radius;
513 strip_add_tri(rpos, orientation);
514}
515
516void LineBuilder::new_arc(Vector2 center, Vector2 vbegin, float angle_delta, Color color, Rect2 uv_rect) {
517 // Make a standalone arc that doesn't use existing vertices,
518 // with undistorted UVs from within a square section
519
520 float radius = vbegin.length();
521 float angle_step = Math_PI / static_cast<float>(round_precision);
522 float steps = Math::abs(angle_delta) / angle_step;
523
524 if (angle_delta < 0.f) {
525 angle_step = -angle_step;
526 }
527
528 float t = Vector2(1, 0).angle_to(vbegin);
529 float end_angle = t + angle_delta;
530 Vector2 rpos(0, 0);
531 float tt_begin = -Math_PI / 2.0f;
532 float tt = tt_begin;
533
534 // Center vertice
535 int vi = vertices.size();
536 vertices.push_back(center);
537 if (_interpolate_color) {
538 colors.push_back(color);
539 }
540 if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
541 uvs.push_back(interpolate(uv_rect, Vector2(0.5f, 0.5f)));
542 }
543
544 // Arc vertices
545 for (int ti = 0; ti < steps; ++ti, t += angle_step) {
546 Vector2 sc = Vector2(Math::cos(t), Math::sin(t));
547 rpos = center + sc * radius;
548
549 vertices.push_back(rpos);
550 if (_interpolate_color) {
551 colors.push_back(color);
552 }
553 if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
554 Vector2 tsc = Vector2(Math::cos(tt), Math::sin(tt));
555 uvs.push_back(interpolate(uv_rect, 0.5f * (tsc + Vector2(1.f, 1.f))));
556 tt += angle_step;
557 }
558 }
559
560 // Last arc vertex
561 Vector2 sc = Vector2(Math::cos(end_angle), Math::sin(end_angle));
562 rpos = center + sc * radius;
563 vertices.push_back(rpos);
564 if (_interpolate_color) {
565 colors.push_back(color);
566 }
567 if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
568 tt = tt_begin + angle_delta;
569 Vector2 tsc = Vector2(Math::cos(tt), Math::sin(tt));
570 uvs.push_back(interpolate(uv_rect, 0.5f * (tsc + Vector2(1.f, 1.f))));
571 }
572
573 // Make up triangles
574 int vi0 = vi;
575 for (int ti = 0; ti < steps; ++ti) {
576 indices.push_back(vi0);
577 indices.push_back(++vi);
578 indices.push_back(vi + 1);
579 }
580}
581