Cppcheck report - Godot - branch: 3.x, commit: cd92ad0f69a842d94dc2d56f83cbd8f724ed2959 (2024-12-15): scene/2d/line_builder.cpp

/**************************************************************************/
/*  line_builder.cpp                                                      */
/**************************************************************************/
/*                         This file is part of:                          */
/*                             GODOT ENGINE                               */
/*                        https://godotengine.org                         */
/**************************************************************************/
/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur.                  */
/*                                                                        */
/* Permission is hereby granted, free of charge, to any person obtaining  */
/* a copy of this software and associated documentation files (the        */
/* "Software"), to deal in the Software without restriction, including    */
/* without limitation the rights to use, copy, modify, merge, publish,    */
/* distribute, sublicense, and/or sell copies of the Software, and to     */
/* permit persons to whom the Software is furnished to do so, subject to  */
/* the following conditions:                                              */
/*                                                                        */
/* The above copyright notice and this permission notice shall be         */
/* included in all copies or substantial portions of the Software.        */
/*                                                                        */
/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,        */
/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF     */
/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY   */
/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,   */
/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE      */
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                 */
/**************************************************************************/

#include "line_builder.h"

//----------------------------------------------------------------------------
// Util
//----------------------------------------------------------------------------

enum SegmentIntersectionResult {
	SEGMENT_PARALLEL = 0,
	SEGMENT_NO_INTERSECT = 1,
	SEGMENT_INTERSECT = 2
};

static SegmentIntersectionResult segment_intersection(
		Vector2 a, Vector2 b, Vector2 c, Vector2 d,
		Vector2 *out_intersection) {
	// http://paulbourke.net/geometry/pointlineplane/ <-- Good stuff
	Vector2 cd = d - c;
	Vector2 ab = b - a;
	float div = cd.y * ab.x - cd.x * ab.y;

	if (Math::abs(div) > 0.001f) {
		float ua = (cd.x * (a.y - c.y) - cd.y * (a.x - c.x)) / div;
		float ub = (ab.x * (a.y - c.y) - ab.y * (a.x - c.x)) / div;
		*out_intersection = a + ua * ab;
		if (ua >= 0.f && ua <= 1.f &&
				ub >= 0.f && ub <= 1.f) {
			return SEGMENT_INTERSECT;
		}
		return SEGMENT_NO_INTERSECT;
	}

	return SEGMENT_PARALLEL;
}

static float calculate_total_distance(const Vector<Vector2> &points) {
	float d = 0.f;
	for (int i = 1; i < points.size(); ++i) {
		d += points[i].distance_to(points[i - 1]);
	}
	return d;
}

static inline Vector2 rotate90(const Vector2 &v) {
	// Note: the 2D referential is X-right, Y-down
	return Vector2(v.y, -v.x);
}

static inline Vector2 interpolate(const Rect2 &r, const Vector2 &v) {
	return Vector2(
			Math::lerp(r.position.x, r.position.x + r.get_size().x, v.x),
			Math::lerp(r.position.y, r.position.y + r.get_size().y, v.y));
}

//----------------------------------------------------------------------------
// LineBuilder
//----------------------------------------------------------------------------

LineBuilder::LineBuilder() {<--- Member variable 'LineBuilder::texture_mode' is not initialized in the constructor.
	joint_mode = Line2D::LINE_JOINT_SHARP;
	width = 10;
	curve = nullptr;
	default_color = Color(0.4, 0.5, 1);
<--- Variable 'default_color' is assigned in constructor body. Consider performing initialization in initialization list. [+]
When an object of a class is created, the constructors of all member variables are called consecutively in the order the variables are declared, even if you don't explicitly write them to the initialization list. You could avoid assigning 'default_color' a value by passing the value to the constructor in the initialization list.
	gradient = nullptr;
	sharp_limit = 2.f;
	round_precision = 8;
	begin_cap_mode = Line2D::LINE_CAP_NONE;
	end_cap_mode = Line2D::LINE_CAP_NONE;
	tile_aspect = 1.f;

	_interpolate_color = false;
	_last_index[0] = 0;
	_last_index[1] = 0;
}

void LineBuilder::clear_output() {
	vertices.clear();
	colors.clear();
	indices.clear();
	uvs.clear();
}

void LineBuilder::build() {
	// Need at least 2 points to draw a line
	if (points.size() < 2) {
		clear_output();
		return;
	}

	ERR_FAIL_COND(tile_aspect <= 0.f);

	const float hw = width / 2.f;
	const float hw_sq = hw * hw;
	const float sharp_limit_sq = sharp_limit * sharp_limit;
	const int len = points.size();

	// Initial values

	Vector2 pos0 = points[0];
	Vector2 pos1 = points[1];
	Vector2 f0 = (pos1 - pos0).normalized();
	Vector2 u0 = rotate90(f0);
	Vector2 pos_up0 = pos0;
	Vector2 pos_down0 = pos0;

	Color color0;
	Color color1;

	float current_distance0 = 0.f;
	float current_distance1 = 0.f;
	float total_distance = 0.f;
	float width_factor = 1.f;
	_interpolate_color = gradient != nullptr;
	bool retrieve_curve = curve != nullptr;
	bool distance_required = _interpolate_color ||
			retrieve_curve ||
			texture_mode == Line2D::LINE_TEXTURE_TILE ||
			texture_mode == Line2D::LINE_TEXTURE_STRETCH;
	if (distance_required) {
		total_distance = calculate_total_distance(points);
		//Adjust totalDistance.
		// The line's outer length will be a little higher due to begin and end caps
		if (begin_cap_mode == Line2D::LINE_CAP_BOX || begin_cap_mode == Line2D::LINE_CAP_ROUND) {
			if (retrieve_curve) {
				total_distance += width * curve->interpolate_baked(0.f) * 0.5f;
			} else {
				total_distance += width * 0.5f;
			}
		}
		if (end_cap_mode == Line2D::LINE_CAP_BOX || end_cap_mode == Line2D::LINE_CAP_ROUND) {
			if (retrieve_curve) {
				total_distance += width * curve->interpolate_baked(1.f) * 0.5f;
			} else {
				total_distance += width * 0.5f;
			}
		}
	}
	if (_interpolate_color) {
		color0 = gradient->get_color(0);
	} else {
		colors.push_back(default_color);
	}

	float uvx0 = 0.f;
	float uvx1 = 0.f;

	if (retrieve_curve) {
		width_factor = curve->interpolate_baked(0.f);
	}

	pos_up0 += u0 * hw * width_factor;
	pos_down0 -= u0 * hw * width_factor;

	// Begin cap
	if (begin_cap_mode == Line2D::LINE_CAP_BOX) {
		// Push back first vertices a little bit
		pos_up0 -= f0 * hw * width_factor;
		pos_down0 -= f0 * hw * width_factor;

		current_distance0 += hw * width_factor;
		current_distance1 = current_distance0;
	} else if (begin_cap_mode == Line2D::LINE_CAP_ROUND) {
		if (texture_mode == Line2D::LINE_TEXTURE_TILE) {
			uvx0 = width_factor * 0.5f / tile_aspect;
		} else if (texture_mode == Line2D::LINE_TEXTURE_STRETCH) {
			uvx0 = width * width_factor / total_distance;
		}
		new_arc(pos0, pos_up0 - pos0, -Math_PI, color0, Rect2(0.f, 0.f, uvx0 * 2, 1.f));
		current_distance0 += hw * width_factor;
		current_distance1 = current_distance0;
	}

	strip_begin(pos_up0, pos_down0, color0, uvx0);

	/*
	 *  pos_up0 ------------- pos_up1 --------------------
	 *     |                     |
	 *   pos0 - - - - - - - - - pos1 - - - - - - - - - pos2
	 *     |                     |
	 * pos_down0 ------------ pos_down1 ------------------
	 *
	 *   i-1                     i                      i+1
	 */

	// http://labs.hyperandroid.com/tag/opengl-lines
	// (not the same implementation but visuals help a lot)

	// For each additional segment
	for (int i = 1; i < len - 1; ++i) {
		pos1 = points[i];
		Vector2 pos2 = points[i + 1];

		Vector2 f1 = (pos2 - pos1).normalized();
		Vector2 u1 = rotate90(f1);

		// Determine joint orientation
		const float dp = u0.dot(f1);
		const Orientation orientation = (dp > 0.f ? UP : DOWN);

		if (distance_required) {
			current_distance1 += pos0.distance_to(pos1);
		}
		if (_interpolate_color) {
			color1 = gradient->get_color_at_offset(current_distance1 / total_distance);
		}
		if (retrieve_curve) {
			width_factor = curve->interpolate_baked(current_distance1 / total_distance);
		}

		Vector2 inner_normal0, inner_normal1;
		if (orientation == UP) {
			inner_normal0 = u0 * hw * width_factor;
			inner_normal1 = u1 * hw * width_factor;
		} else {
			inner_normal0 = -u0 * hw * width_factor;
			inner_normal1 = -u1 * hw * width_factor;
		}

		/*
		 * ---------------------------
		 *                        /
		 * 0                     /    1
		 *                      /          /
		 * --------------------x------    /
		 *                    /          /    (here shown with orientation == DOWN)
		 *                   /          /
		 *                  /          /
		 *                 /          /
		 *                     2     /
		 *                          /
		 */

		// Find inner intersection at the joint
		Vector2 corner_pos_in, corner_pos_out;
		SegmentIntersectionResult intersection_result = segment_intersection(
				pos0 + inner_normal0, pos1 + inner_normal0,
				pos1 + inner_normal1, pos2 + inner_normal1,
				&corner_pos_in);

		if (intersection_result == SEGMENT_INTERSECT) {
			// Inner parts of the segments intersect
			corner_pos_out = 2.f * pos1 - corner_pos_in;
		} else {
			// No intersection, segments are either parallel or too sharp
			corner_pos_in = pos1 + inner_normal0;
			corner_pos_out = pos1 - inner_normal0;
		}

		Vector2 corner_pos_up, corner_pos_down;
		if (orientation == UP) {
			corner_pos_up = corner_pos_in;
			corner_pos_down = corner_pos_out;
		} else {
			corner_pos_up = corner_pos_out;
			corner_pos_down = corner_pos_in;
		}

		Line2D::LineJointMode current_joint_mode = joint_mode;

		Vector2 pos_up1, pos_down1;
		if (intersection_result == SEGMENT_INTERSECT) {
			// Fallback on bevel if sharp angle is too high (because it would produce very long miters)
			float width_factor_sq = width_factor * width_factor;
			if (current_joint_mode == Line2D::LINE_JOINT_SHARP && corner_pos_out.distance_squared_to(pos1) / (hw_sq * width_factor_sq) > sharp_limit_sq) {
				current_joint_mode = Line2D::LINE_JOINT_BEVEL;
			}
			if (current_joint_mode == Line2D::LINE_JOINT_SHARP) {
				// In this case, we won't create joint geometry,
				// The previous and next line quads will directly share an edge.
				pos_up1 = corner_pos_up;
				pos_down1 = corner_pos_down;
			} else {
				// Bevel or round
				if (orientation == UP) {
					pos_up1 = corner_pos_up;
					pos_down1 = pos1 - u0 * hw * width_factor;
				} else {
					pos_up1 = pos1 + u0 * hw * width_factor;
					pos_down1 = corner_pos_down;
				}
			}
		} else {
			// No intersection: fallback
			if (current_joint_mode == Line2D::LINE_JOINT_SHARP) {
				// There is no fallback implementation for LINE_JOINT_SHARP so switch to the LINE_JOINT_BEVEL
				current_joint_mode = Line2D::LINE_JOINT_BEVEL;
			}
			pos_up1 = corner_pos_up;
			pos_down1 = corner_pos_down;
		}

		// Add current line body quad
		// Triangles are clockwise
		if (texture_mode == Line2D::LINE_TEXTURE_TILE) {
			uvx1 = current_distance1 / (width * tile_aspect);
		} else if (texture_mode == Line2D::LINE_TEXTURE_STRETCH) {
			uvx1 = current_distance1 / total_distance;
		}

		strip_add_quad(pos_up1, pos_down1, color1, uvx1);

		// Swap vars for use in the next line
		color0 = color1;
		u0 = u1;
		f0 = f1;
		pos0 = pos1;
		if (intersection_result == SEGMENT_INTERSECT) {
			if (current_joint_mode == Line2D::LINE_JOINT_SHARP) {
				pos_up0 = pos_up1;
				pos_down0 = pos_down1;
			} else {
				if (orientation == UP) {
					pos_up0 = corner_pos_up;
					pos_down0 = pos1 - u1 * hw * width_factor;
				} else {
					pos_up0 = pos1 + u1 * hw * width_factor;
					pos_down0 = corner_pos_down;
				}
			}
		} else {
			pos_up0 = pos1 + u1 * hw * width_factor;
			pos_down0 = pos1 - u1 * hw * width_factor;
		}
		// From this point, bu0 and bd0 concern the next segment

		// Add joint geometry
		if (current_joint_mode != Line2D::LINE_JOINT_SHARP) {
			/* ________________ cbegin
			 *               / \
			 *              /   \
			 * ____________/_ _ _\ cend
			 *             |     |
			 *             |     |
			 *             |     |
			 */

			Vector2 cbegin, cend;
			if (orientation == UP) {
				cbegin = pos_down1;
				cend = pos_down0;
			} else {
				cbegin = pos_up1;
				cend = pos_up0;
			}

			if (current_joint_mode == Line2D::LINE_JOINT_BEVEL) {
				strip_add_tri(cend, orientation);
			} else if (current_joint_mode == Line2D::LINE_JOINT_ROUND) {
				Vector2 vbegin = cbegin - pos1;
				Vector2 vend = cend - pos1;
				strip_add_arc(pos1, vbegin.angle_to(vend), orientation);
			}

			if (intersection_result != SEGMENT_INTERSECT) {
				// In this case the joint is too corrputed to be re-used,
				// start again the strip with fallback points
				strip_begin(pos_up0, pos_down0, color1, uvx1);
			}
		}
	}
	// Last (or only) segment
	pos1 = points[points.size() - 1];

	if (distance_required) {
		current_distance1 += pos0.distance_to(pos1);
	}
	if (_interpolate_color) {
		color1 = gradient->get_color(gradient->get_points_count() - 1);
	}
	if (retrieve_curve) {
		width_factor = curve->interpolate_baked(1.f);
	}

	Vector2 pos_up1 = pos1 + u0 * hw * width_factor;
	Vector2 pos_down1 = pos1 - u0 * hw * width_factor;

	// End cap (box)
	if (end_cap_mode == Line2D::LINE_CAP_BOX) {
		pos_up1 += f0 * hw * width_factor;
		pos_down1 += f0 * hw * width_factor;

		current_distance1 += hw * width_factor;
	}

	if (texture_mode == Line2D::LINE_TEXTURE_TILE) {
		uvx1 = current_distance1 / (width * tile_aspect);
	} else if (texture_mode == Line2D::LINE_TEXTURE_STRETCH) {
		uvx1 = current_distance1 / total_distance;
	}

	strip_add_quad(pos_up1, pos_down1, color1, uvx1);

	// End cap (round)
	if (end_cap_mode == Line2D::LINE_CAP_ROUND) {
		// Note: color is not used in case we don't interpolate...
		Color color = _interpolate_color ? gradient->get_color(gradient->get_points_count() - 1) : Color(0, 0, 0);
		float dist = 0;
		if (texture_mode == Line2D::LINE_TEXTURE_TILE) {
			dist = width_factor / tile_aspect;
		} else if (texture_mode == Line2D::LINE_TEXTURE_STRETCH) {
			dist = width * width_factor / total_distance;
		}
		new_arc(pos1, pos_up1 - pos1, Math_PI, color, Rect2(uvx1 - 0.5f * dist, 0.f, dist, 1.f));
	}
}

void LineBuilder::strip_begin(Vector2 up, Vector2 down, Color color, float uvx) {
	int vi = vertices.size();

	vertices.push_back(up);
	vertices.push_back(down);

	if (_interpolate_color) {
		colors.push_back(color);
		colors.push_back(color);
	}

	if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
		uvs.push_back(Vector2(uvx, 0.f));
		uvs.push_back(Vector2(uvx, 1.f));
	}

	_last_index[UP] = vi;
	_last_index[DOWN] = vi + 1;
}

void LineBuilder::strip_new_quad(Vector2 up, Vector2 down, Color color, float uvx) {
	int vi = vertices.size();

	vertices.push_back(vertices[_last_index[UP]]);
	vertices.push_back(vertices[_last_index[DOWN]]);
	vertices.push_back(up);
	vertices.push_back(down);

	if (_interpolate_color) {
		colors.push_back(color);
		colors.push_back(color);
		colors.push_back(color);
		colors.push_back(color);
	}

	if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
		uvs.push_back(uvs[_last_index[UP]]);
		uvs.push_back(uvs[_last_index[DOWN]]);
		uvs.push_back(Vector2(uvx, UP));
		uvs.push_back(Vector2(uvx, DOWN));
	}

	indices.push_back(vi);
	indices.push_back(vi + 3);
	indices.push_back(vi + 1);
	indices.push_back(vi);
	indices.push_back(vi + 2);
	indices.push_back(vi + 3);

	_last_index[UP] = vi + 2;
	_last_index[DOWN] = vi + 3;
}

void LineBuilder::strip_add_quad(Vector2 up, Vector2 down, Color color, float uvx) {
	int vi = vertices.size();

	vertices.push_back(up);
	vertices.push_back(down);

	if (_interpolate_color) {
		colors.push_back(color);
		colors.push_back(color);
	}

	if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
		uvs.push_back(Vector2(uvx, 0.f));
		uvs.push_back(Vector2(uvx, 1.f));
	}

	indices.push_back(_last_index[UP]);
	indices.push_back(vi + 1);
	indices.push_back(_last_index[DOWN]);
	indices.push_back(_last_index[UP]);
	indices.push_back(vi);
	indices.push_back(vi + 1);

	_last_index[UP] = vi;
	_last_index[DOWN] = vi + 1;
}

void LineBuilder::strip_add_tri(Vector2 up, Orientation orientation) {
	int vi = vertices.size();

	vertices.push_back(up);

	if (_interpolate_color) {
		colors.push_back(colors[colors.size() - 1]);
	}

	Orientation opposite_orientation = orientation == UP ? DOWN : UP;

	if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
		// UVs are just one slice of the texture all along
		// (otherwise we can't share the bottom vertice)
		uvs.push_back(uvs[_last_index[opposite_orientation]]);
	}

	indices.push_back(_last_index[opposite_orientation]);
	indices.push_back(vi);
	indices.push_back(_last_index[orientation]);

	_last_index[opposite_orientation] = vi;
}

void LineBuilder::strip_add_arc(Vector2 center, float angle_delta, Orientation orientation) {
	// Take the two last vertices and extrude an arc made of triangles
	// that all share one of the initial vertices

	Orientation opposite_orientation = orientation == UP ? DOWN : UP;
	Vector2 vbegin = vertices[_last_index[opposite_orientation]] - center;
	float radius = vbegin.length();
	float angle_step = Math_PI / static_cast<float>(round_precision);
	float steps = Math::abs(angle_delta) / angle_step;

	if (angle_delta < 0.f) {
		angle_step = -angle_step;
	}

	float t = Vector2(1, 0).angle_to(vbegin);
	float end_angle = t + angle_delta;
	Vector2 rpos(0, 0);

	// Arc vertices
	for (int ti = 0; ti < steps; ++ti, t += angle_step) {
		rpos = center + Vector2(Math::cos(t), Math::sin(t)) * radius;
		strip_add_tri(rpos, orientation);
	}

	// Last arc vertice
	rpos = center + Vector2(Math::cos(end_angle), Math::sin(end_angle)) * radius;
	strip_add_tri(rpos, orientation);
}

void LineBuilder::new_arc(Vector2 center, Vector2 vbegin, float angle_delta, Color color, Rect2 uv_rect) {
	// Make a standalone arc that doesn't use existing vertices,
	// with undistorted UVs from within a square section

	float radius = vbegin.length();
	float angle_step = Math_PI / static_cast<float>(round_precision);
	float steps = Math::abs(angle_delta) / angle_step;

	if (angle_delta < 0.f) {
		angle_step = -angle_step;
	}

	float t = Vector2(1, 0).angle_to(vbegin);
	float end_angle = t + angle_delta;
	Vector2 rpos(0, 0);
	float tt_begin = -Math_PI / 2.f;
	float tt = tt_begin;

	// Center vertice
	int vi = vertices.size();
	vertices.push_back(center);
	if (_interpolate_color) {
		colors.push_back(color);
	}
	if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
		uvs.push_back(interpolate(uv_rect, Vector2(0.5f, 0.5f)));
	}

	// Arc vertices
	for (int ti = 0; ti < steps; ++ti, t += angle_step) {
		Vector2 sc = Vector2(Math::cos(t), Math::sin(t));
		rpos = center + sc * radius;

		vertices.push_back(rpos);
		if (_interpolate_color) {
			colors.push_back(color);
		}
		if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
			Vector2 tsc = Vector2(Math::cos(tt), Math::sin(tt));
			uvs.push_back(interpolate(uv_rect, 0.5f * (tsc + Vector2(1.f, 1.f))));
			tt += angle_step;
		}
	}

	// Last arc vertice
	Vector2 sc = Vector2(Math::cos(end_angle), Math::sin(end_angle));
	rpos = center + sc * radius;
	vertices.push_back(rpos);
	if (_interpolate_color) {
		colors.push_back(color);
	}
	if (texture_mode != Line2D::LINE_TEXTURE_NONE) {
		tt = tt_begin + angle_delta;
		Vector2 tsc = Vector2(Math::cos(tt), Math::sin(tt));
		uvs.push_back(interpolate(uv_rect, 0.5f * (tsc + Vector2(1.f, 1.f))));
	}

	// Make up triangles
	int vi0 = vi;
	for (int ti = 0; ti < steps; ++ti) {
		indices.push_back(vi0);
		indices.push_back(++vi);
		indices.push_back(vi + 1);
	}
}