Differential D12753 Diff 43042 source/blender/nodes/geometry/nodes/node_geo_curve_bool.cc

Changeset View

Standalone View

source/blender/nodes/geometry/nodes/node_geo_curve_bool.cc

This file was added.

				/*
				* This program is free software; you can redistribute it and/or
				* modify it under the terms of the GNU General Public License
				* as published by the Free Software Foundation; either version 2
				* of the License, or (at your option) any later version.
				*
				* This program is distributed in the hope that it will be useful,
				* but WITHOUT ANY WARRANTY; without even the implied warranty of
				* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
				* GNU General Public License for more details.
				*
				* You should have received a copy of the GNU General Public License
				* along with this program; if not, write to the Free Software Foundation,
				* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
				*/

				#include "BKE_spline.hh"
				#include "BLI_timeit.hh"
				#include "UI_interface.h"
				#include "UI_resources.h"
				#include "node_geometry_util.hh"
				#include <iostream>
				#include <list>

				using blender::attribute_math::mix2;
				using HandleType = BezierSpline::HandleType;

				/**
				* This file implements the Curve 2D Boolean geometry node.
				*
				* BUGS:
				*
				* TODO:
				* Optimize multiple bool operations in a row via multiple operands?
				* Line Segment intersection library
				* Optional hard corners so attributes like radius stick. Or maybe an enum to define which curve
				* should provide attributes for intersection points. Conformity slider : If 1, map intersection
				* points to geometry, if 0, map to bezier curve. Interpolate between. If either of the curves self
				* intersect, show a warning.
				* Splines to bezier conversion. ( How does this work with weighted points? We need 1 for 1 bezier
				* control points, no?)
				*/

				/**
				* Same ids as "curve_bool_items" in NOD_static_types.h
				*/
				typedef enum BoolOperationType {
				OR = 0,
				AND = 1,
				SUB = 2,
				} BoolOperationType;

				/**
				* DEBUG CODE START
				*/

				static void print(std::string s)
				{
				std::cout << s << std::endl << std::flush;
				}

				template<typename T> static void print(T s)
				{
				std::cout << s << std::endl << std::flush;
				}

				template<typename T> static std::string str(T t)
				{
				return std::to_string(t);
				}

				/**
				* DEBUG CODE END
				*/

				namespace blender::nodes {
				/**
				* Does the curve contain the point?
				* If the curve is open, it will be interpreted as a closed shape with a straight line between
				* start and end.
				*/
				static bool curve_contains(Spline *spline, float3 point)
				{
				HooglyBooglyUnsubmitted Done Inline Actions Maybe `SCOPED_TIMER` provides a simpler alternative here? HooglyBoogly: Maybe `SCOPED_TIMER` provides a simpler alternative here?
				// Using bounds would not improve performance, because they aren't cached.
				blender::Span<float3> points = spline->evaluated_positions();
				int points_length = points.size();
				int i, j;
				bool result = 0;
				for (i = 0, j = points_length - 1; i < points_length; j = i++) {
				if (((points[i].y > point.y) != (points[j].y > point.y)) &&
				(point.x <
				(points[j].x - points[i].x) * (point.y - points[i].y) / (points[j].y - points[i].y) +
				points[i].x)) {
				result = !result;
				}
				}

				return result; // if even, point is outside ( return false )
				}

				/**
				* Count the number of splines that contain the given point.
				* Ignore up to one particular spline, usually the one the point is located on
				*/
				static int count_containing_curves(Span<Spline *> splines,
				float3 point,
				const Spline *except = nullptr)
				{
				int counter = 0;
				for (Spline *spline : splines) {
				if ((spline != except) && curve_contains(spline, point)) {
				counter++;
				}
				}
				return counter;
				}

				/**
				* Find intersection between 2 2d line segments, each defined by a start and end point. Z
				* Coordinates are ignored. If either of the 2 floats returned is negative, no collision occured.
				* If they are not negative, they are in [0,1]
				*/
				static float2 linesIntersect(float2 A, float2 B, float2 C, float2 D)
				HooglyBooglyUnsubmitted Not Done Inline Actions Do any of the `isect_seg_seg_v2` set of functions work for this? It's nice to avoid reinventing this intersection unless it's necessary. HooglyBoogly: Do any of the `isect_seg_seg_v2` set of functions work for this? It's nice to avoid reinventing…
				{
				float AC_x = C.x - A.x;
				float AC_y = C.y - A.y;
				float AB_x = B.x - A.x;
				float AB_y = B.y - A.y;
				float CD_x = D.x - C.x;
				float CD_y = D.y - C.y;

				float ACxAB = AC_x * AB_y - AC_y * AB_x;

				// Lines are collinear. They intersect infinitely if they have any overlap. We can't handle that.
				if (ACxAB == 0.f) {
				return float2(-1, -1);
				}

				float ACxCD = AC_x * CD_y - AC_y * CD_x;
				float ABxCD = AB_x * CD_y - AB_y * CD_x;
				// Multiplication is MUCH faster than division. Worth the extra operation.
				float one_over_ABxCD = 1.f / ABxCD;
				float t = ACxCD * one_over_ABxCD;
				float u = ACxAB * one_over_ABxCD;

				if ((t >= 0.f) && (t <= 1.f) && (u >= 0.f) && (u <= 1.f)) {
				return float2(t, u);
				}
				return float2(-1, -1);
				}

				struct CurveHull;

				struct Intersection {
				// distance between the current evaluated point and the next, in [0,1)
				float v;
				// Intersection on the opposite segment
				Intersection *target;
				// self
				CurveHull *hull;
				};

				/**
				* Stores a complete map of all connected points and intersections across all involved splines as a
				* double linked list.
				*/
				struct CurveHull {
				// Used to identify which curve we're on, which is useful if self-intersection is disabled.
				int curve_id;
				// original spline this point is on.
				Spline *spline;
				// Index of evaluated point on curve.
				int curve_i;
				// Distance along curve, in [0,1) .
				float v;
				// Real evaluated position on the original curve.
				float3 position;
				// Next point along the original curve.
				CurveHull *next = nullptr;
				// Previous point along the original curve.
				CurveHull *prev = nullptr;
				// If not nullptr, this is a virtual CurveHull point, that denotes an intersection.
				Intersection *intersection = nullptr;
				// Used to collect intersections without creating additional segments. Only control points have
				// anything in here.
				std::vector<Intersection *> intersections;
				// Used when tracing to determine if a point has been passed through.
				int pass = -1;
				// Used when tracing. If true, the next intersection is passed right through.
				// 0 = false, 1 = true, -1 = undefined. Only starting points have this defined.
				int is_inside = -1;

				/**
				* Find the next control point that HAS intersections.
				*/
				CurveHull next_intersection_control(bool include_self = false, CurveHull __start = nullptr)
				{
				if (include_self && ((intersections.size() > 0))) {
				return this;
				}

				if (next == nullptr \|\| __start == this) { // end condition
				return nullptr;
				}

				if (__start == nullptr) {
				__start = this;
				}

				return next->next_intersection_control(true, __start);
				}

				/**
				* Find the next point that IS an intersection.
				*/
				CurveHull next_intersection(bool include_self = false, CurveHull __start = nullptr)
				{
				if (include_self && intersection != nullptr) {
				return this;
				}

				if (next == nullptr \|\| __start == this) { // end condition
				return nullptr;
				}

				if (__start == nullptr) {
				__start = this;
				}

				return next->next_intersection(true, __start);
				}

				/**
				* Removes this and all following points as well as their intersection structs.
				*/
				void remove()
				{
				if (prev != nullptr) {
				prev->next = nullptr;
				}

				if (next != nullptr) {
				next->prev = nullptr;
				next->remove();
				}

				if (intersection != nullptr) {
				delete intersection;
				}

				delete this;
				}
				};

				/**
				* Convert a path into a CurveHull form, which is a double linked list with extra variables for
				* tracing along intersections lateron.
				*/
				static CurveHull points_to_hull(Spline spline, int curve_id)
				{
				blender::Span<float3> points = spline->evaluated_positions();
				bool cycle = spline->is_cyclic();

				CurveHull *start = new CurveHull{.curve_id = curve_id,
				.spline = spline,
				.curve_i = 0,
				.v = 0,
				.position = points[0],
				.next = nullptr,
				.prev = nullptr};
				CurveHull *prev = start;

				int size = points.size();
				int real_size = size + (cycle ? 0 : -1);
				for (int i = 1; i < size; i++) {
				CurveHull *current = new CurveHull{.curve_id = curve_id,
				.spline = spline,
				.curve_i = i,
				.v = i / (float)real_size,
				.position = points[i],
				.prev = prev};
				prev->next = current;
				prev = current;
				}

				if (cycle) {
				prev->next = start;
				start->prev = prev;
				}

				return start;
				}

				/**
				* Check if 2 Bounds intersect
				*/
				static bool bounds_intersect(float2 bounds_a_min,
				float2 bounds_a_max,
				float2 bounds_b_min,
				float2 bounds_b_max)
				{
				return (bounds_a_min.x < bounds_b_max.x) && (bounds_a_max.x > bounds_b_min.x) &&
				(bounds_a_min.y < bounds_b_max.y) && (bounds_a_max.y > bounds_b_min.y);
				}

				/**
				* Creates a representation of all curves as linked lists between evaluated points.
				* Finds all intersections between curves and adds them as new points to the curves. These new
				* points contain references to the matching new point on the other curve. We're essentially
				* turning the splines into linked lists of points into linked meshes of points connected by common
				* pairs of intersection points.
				*/
				static std::list<CurveHull > splineIntersectAll(std::vector<std::vector<Spline >> splines)
				{
				// TODO : Create Binary search tree from bounds (Needs some kind of clumping heuristics.)
				// TODO : Option to allow self intersection in exchange for brute force collision algorithm

				std::list<CurveHull *> results;
				std::list<CurveHull *> frontier;

				// Calculate bounding box for each individual curve.
				std::vector<float3> bounds;

				int c = splines.size();
				for (int i = 0; i < c; i++) {
				HooglyBooglyUnsubmitted Not Done Inline Actions Range based for loops are much easier to read, and `blender::Span` includes some helpers to make it easier. In particular, `for (const int i : splines.index_range()) {` HooglyBoogly: Range based for loops are much easier to read, and `blender::Span` includes some helpers to…
				for (Spline *_spline : splines[i]) {
				float3 min = float3(INFINITY, INFINITY, INFINITY);
				float3 max = float3(-INFINITY, -INFINITY, -INFINITY);
				_spline->bounds_min_max(min, max, true);
				bounds.push_back(min);
				bounds.push_back(max);

				frontier.push_back(points_to_hull(_spline, i));
				CurveHull *last = frontier.back();
				int counter = count_containing_curves(last->curve_id == 0 ? splines[1] : splines[0],
				last->position);
				last->is_inside = counter % 2 == 1;
				}
				}

				c = frontier.size();
				int pass = 0;
				int i = -1; // refers to bounds array
				// loop through all possible curve segments.
				while (frontier.size() > 0) {
				i++;
				CurveHull *primary_curve = frontier.front();
				frontier.pop_front();

				int j = i; // refers to bounds array
				for (CurveHull *curve_hull_b : frontier) {
				pass++;
				j++;

				if (primary_curve->curve_id == curve_hull_b->curve_id \|\|
				!bounds_intersect(bounds[i * 2], bounds[i * 2 + 1], bounds[j * 2], bounds[j * 2 + 1])) {
				continue;
				}

				CurveHull *current_curve_hull_a = primary_curve;
				CurveHull *next_curve_hull_a = primary_curve->next;
				// loop through a's curve segments
				while (current_curve_hull_a != nullptr && next_curve_hull_a != nullptr &&
				current_curve_hull_a->pass != pass) {
				current_curve_hull_a->pass = pass;

				CurveHull *current_curve_hull_b = curve_hull_b;
				CurveHull *next_curve_hull_b = curve_hull_b->next;
				// loop through b's curve segments
				do {
				float2 intersection = linesIntersect(current_curve_hull_a->position,
				next_curve_hull_a->position,
				current_curve_hull_b->position,
				next_curve_hull_b->position);

				if (intersection[0] > 0) { // Found intersection
				auto intersection_a = new
				Intersection{v : intersection[0], hull : current_curve_hull_a};
				auto intersection_b = new Intersection{
				v : intersection[1],
				target : intersection_a,
				hull : current_curve_hull_b
				};
				intersection_a->target = intersection_b;
				current_curve_hull_a->intersections.push_back(intersection_a);
				current_curve_hull_b->intersections.push_back(intersection_b);
				}

				current_curve_hull_b = current_curve_hull_b->next;
				next_curve_hull_b = current_curve_hull_b->next;
				} while (next_curve_hull_b != nullptr && current_curve_hull_b->curve_i != 0);

				current_curve_hull_a = next_curve_hull_a;
				next_curve_hull_a = current_curve_hull_a->next;
				}
				}

				results.push_back(primary_curve);
				}

				// Now that all intersections are stored in their relevant control points, sort them by v and
				// create new "virtual" CurveHull points for each intersection.
				for (CurveHull *current_point : results) {
				CurveHull *start = current_point;
				float curve_length = current_point->spline->evaluated_points_size() +
				HooglyBooglyUnsubmitted Done Inline Actions How about `Spline::reverse()`? HooglyBoogly: How about `Spline::reverse()`?
				(current_point->spline->is_cyclic() ? 0 : -1);
				// Then create all intersection points as actual points. We didn't do this earlier to avoid
				// extra intersection calculations with the new line segments.
				do {
				std::vector<Intersection *> &intersections = current_point->intersections;
				// Sort the intersections by progress along line (v).
				std::sort(intersections.begin(), intersections.end(), [](Intersection a, Intersection b) {
				return a->v < b->v;
				});

				CurveHull *original_current_point = current_point;
				CurveHull *original_next_point = current_point->next;
				for (Intersection *intersection : intersections) {
				CurveHull *new_point = new CurveHull{
				.curve_id = current_point->curve_id,
				.spline = current_point->spline,
				.curve_i = current_point->curve_i,
				.v = original_current_point->v + intersection->v / curve_length,
				.position = float3::interpolate(
				original_current_point->position, original_next_point->position, intersection->v),
				.next = current_point->next,
				.prev = current_point,
				.intersection = intersection};
				intersection->hull = new_point;
				current_point->next->prev = new_point;
				current_point->next = new_point;
				current_point = new_point;
				}

				current_point = current_point->next;
				} while (current_point != nullptr && current_point != start);
				}

				return results;
				}

				/**
				* Given a bezier curve segment described by 2 points and 2 handles, generate an extra point at v
				* along the curve and return both the new point's position and handles, as well as the modified
				* handles of the initial points.
				* This is the same as #BezierSpline::calculate_bezier_segment_insertion, but it doesn't need the
				* points to exist on the curve yet.
				*/
				static BezierSpline::InsertResult calculate_bezier_segment_insertion(
				HooglyBooglyUnsubmitted Not Done Inline Actions There could be a static version of this function in the class that just takes `float3` inputs. Another option is creating a temporary `BezierSpline`. HooglyBoogly: There could be a static version of this function in the class that just takes `float3` inputs.
				float3 pos_prev, float3 handle_prev, float3 pos_next, float3 handle_next, float v)
				{
				const float3 center_point = float3::interpolate(handle_prev, handle_next, v);

				BezierSpline::InsertResult result;
				result.handle_prev = float3::interpolate(pos_prev, handle_prev, v);
				result.handle_next = float3::interpolate(handle_next, pos_next, v);
				result.left_handle = float3::interpolate(result.handle_prev, center_point, v);
				result.right_handle = float3::interpolate(center_point, result.handle_next, v);
				result.position = float3::interpolate(result.left_handle, result.right_handle, v);
				HooglyBooglyUnsubmitted Done Inline Actions I haven't looked through this in depth yet, but I'm a bit skeptical of having this struct. Splines use a struct of arrays approach on purpose-- for speed, simplicity of handling custom attributes, and memory reuse (future CoW of attribute arrays). Code handling splines is usually simplest if it takes the same approach. For example, if this code adds data directly to `blender::Vector` for the builtin data, it could pass those directly to `BezierSpline` and avoid the allocation/copy. Also, it usually makes sense to handle tilt and radius the same way as custom attributes. HooglyBoogly: I haven't looked through this in depth yet, but I'm a bit skeptical of having this struct.
				return result;
				}

				/**
				* Assign bezier point data to a particular index in a #BezierSpline.
				*/
				static void set_bezier_point(Spline *spline,
				int index,
				float3 position,
				float3 handle_l,
				float3 handle_r,
				float radius,
				float tilt)
				{
				BezierSpline bezierSpline = (BezierSpline )spline;
				bezierSpline->positions()[index] = position;
				bezierSpline->handle_positions_left()[index] = handle_l;
				bezierSpline->handle_positions_right()[index] = handle_r;
				bezierSpline->radii()[index] = radius;
				bezierSpline->tilts()[index] = tilt;
				bezierSpline->handle_types_left()[index] = HandleType::Free;
				bezierSpline->handle_types_right()[index] = HandleType::Free;
				}

				/**
				* Assign spline point data to a particular index in a #Spline of any type.
				*/
				static void set_spline_point(Spline *spline, int index, float3 position, float radius, float tilt)
				{
				BezierSpline bezierSpline = (BezierSpline )spline;
				bezierSpline->positions()[index] = position;
				bezierSpline->radii()[index] = radius;
				bezierSpline->tilts()[index] = tilt;
				}

				/**
				* Checks if the current point is a control point.
				HooglyBooglyUnsubmitted Done Inline Actions Does `BezierSpline::calculate_segment_insertion` not work in your case? HooglyBoogly: Does `BezierSpline::calculate_segment_insertion` not work in your case?
				* If so, inserts control point data at the specified index.
				*/
				static float process_control_point(CurveHull *current_point,
				Spline *result,
				int result_index,
				Spline::Type type,
				float last_intersection_offset = 0)
				{
				int resolution = current_point->spline->evaluated_points_size() /
				current_point->spline->segments_size();

				// control point index + v along segment
				float current_absolute_v = current_point->curve_i / (float)(resolution);
				int current_control_point = (int)(current_absolute_v);

				if (type == Spline::Type::Bezier) {
				if ((current_point->curve_i % resolution) != 0) {
				return last_intersection_offset;
				}
				BezierSpline current_spline = (BezierSpline )current_point->spline;
				BezierSpline result_spline = (BezierSpline )result;

				set_bezier_point(
				result,
				result_index,
				current_spline->evaluated_positions()[current_point->curve_i],
				float3::interpolate(current_spline->handle_positions_left()[current_control_point],
				current_spline->positions()[current_control_point],
				last_intersection_offset),
				current_spline->handle_positions_right()[current_control_point],
				current_spline->radii()[current_control_point],
				current_spline->tilts()[current_control_point]);
				}
				else {
				Spline *current_spline = current_point->spline;

				int current_segment_end = (current_control_point + 1) % current_spline->size();
				float current_relative_v = fmod(current_absolute_v, 1);
				MutableSpan<float> radii = current_spline->radii();
				MutableSpan<float> tilts = current_spline->tilts();
				set_spline_point(
				result,
				result_index,
				current_spline->evaluated_positions()[current_point->curve_i],
				// We mix, because if this is a bezier curve, that's forcefully converted to poly, it won't
				// have evaluated radii
				mix2(current_relative_v, radii[current_control_point], radii[current_segment_end]),
				mix2(current_relative_v, tilts[current_control_point], tilts[current_segment_end]));
				}

				return 0;
				}

				/**
				* Process a #CurveHull point that is an intersection.
				* Inserts control point data at the specified index in the result spline.
				*/
				static void process_intersection(CurveHull *current_point,
				Spline *result,
				int result_index,
				float &last_intersection_offset,
				Spline::Type type)
				{
				bool first = result_index == 0; // is this the first point in the newly generated spline?
				Intersection *current_intersection = current_point->intersection;

				CurveHull *other_point = current_intersection->target->hull;

				if (type == Spline::Type::Bezier) {
				BezierSpline bezier_result = (BezierSpline )result;

				BezierSpline current_spline = (BezierSpline )current_point->spline;
				BezierSpline other_spline = (BezierSpline )other_point->spline;

				MutableSpan<float3> current_positions = current_spline->positions();
				int current_resolution = current_spline->resolution();
				float current_absolute_v = current_point->curve_i / (float)(current_resolution);
				int current_control_point = (int)(current_absolute_v);
				float current_relative_v = fmod(current_absolute_v, 1);
				int current_segment_end = (current_control_point + 1) % current_spline->size();
				float v_cur = (current_relative_v + current_intersection->v / current_resolution -
				last_intersection_offset) /
				(1 - last_intersection_offset);

				float3 last_pos = first ? current_positions[current_control_point] :
				result->positions()[result_index - 1];
				float3 last_handle = first ? current_spline->handle_positions_right()[current_control_point] :
				bezier_result->handle_positions_right()[result_index - 1];
				BezierSpline::InsertResult insert_current = calculate_bezier_segment_insertion(
				last_pos,
				last_handle,
				current_positions[current_segment_end],
				float3::interpolate(current_spline->handle_positions_left()[current_segment_end],
				current_positions[current_segment_end],
				last_intersection_offset),
				v_cur);

				if (!first) {
				bezier_result->handle_positions_right()[result_index - 1] = insert_current.handle_prev;
				}

				MutableSpan<float3> other_positions = other_spline->positions();
				int next_resolution = other_spline->resolution();
				float next_absolute_v = other_point->curve_i / (float)(next_resolution);
				int next_control_point = (int)(next_absolute_v);
				float next_relative_v = fmod(next_absolute_v, 1);
				int next_segment_end = (next_control_point + 1) % other_spline->size();
				last_intersection_offset = next_relative_v + current_intersection->target->v / next_resolution;

				BezierSpline::InsertResult insert_next = calculate_bezier_segment_insertion(
				other_positions[next_control_point],
				other_spline->handle_positions_right()[next_control_point],
				other_positions[next_segment_end],
				other_spline->handle_positions_left()[next_segment_end],
				last_intersection_offset);

				float3 real_pos =
				current_intersection->hull->position; // the intersection point on the EVALUATED geometry

				MutableSpan<float> radii = current_spline->radii();
				MutableSpan<float> tilts = current_spline->tilts();
				set_bezier_point(
				result,
				result_index,
				real_pos,
				insert_current.left_handle, //+ real_pos - bezier_pos_current
				insert_next.right_handle, // + real_pos - bezier_pos_next
				mix2(next_relative_v, radii[current_control_point], radii[current_segment_end]),
				mix2(next_relative_v, tilts[current_control_point], tilts[current_segment_end]));
				}
				else {
				Spline *current_spline = current_point->spline;

				int current_resolution = current_spline->evaluated_points_size() /
				current_point->spline->segments_size();
				float current_absolute_v = current_point->curve_i / (float)(current_resolution);
				int current_control_point = (int)(current_absolute_v);
				int current_segment_end = (current_control_point + 1) % current_spline->size();

				MutableSpan<float> radii = current_spline->radii();
				MutableSpan<float> tilts = current_spline->tilts();
				float3 real_pos = current_intersection->hull->position;
				set_spline_point(
				result,
				result_index,
				real_pos,
				mix2(current_intersection->v, radii[current_control_point], radii[current_segment_end]),
				mix2(current_intersection->v, tilts[current_control_point], tilts[current_segment_end]));
				}
				}

				/**
				* Given a certain starting point, move along the #CurveHull and store each point in the result
				* list. Turns at each intersection. Returns an empty list if the trace failed to find a valid
				* path.
				*/
				static std::list<CurveHull > do_trace(CurveHull start_point,
				std::list<CurveHull *> &frontier,
				Spline::Type return_type)
				{
				std::list<CurveHull *> result;

				CurveHull *current_point = start_point;
				CurveHull *next_point = current_point->next;

				int resolution = return_type == Spline::Type::Bezier ?
				((BezierSpline *)start_point->spline)->resolution() :
				1;

				if (next_point != nullptr) {
				while (current_point != nullptr && (current_point->pass != -2)) {
				if (current_point->intersection == nullptr && (current_point->curve_i % resolution) != 0) {
				current_point = current_point->next;
				continue; // only keep control and intersection points.
				}
				result.push_back(current_point);

				current_point->pass = -2;

				if (current_point->intersection != nullptr) // current point is a virtual intersection point
				{
				CurveHull *next_possible_frontier = current_point->next_intersection();
				if (next_possible_frontier != nullptr) {
				frontier.push_back(next_possible_frontier->intersection->target->hull);
				}

				current_point = current_point->intersection->target->hull;
				current_point->pass = -2;
				resolution = return_type == Spline::Type::Bezier ?
				((BezierSpline *)current_point->spline)->resolution() :
				1;
				}
				current_point = current_point->next;
				}

				if (current_point != nullptr) {
				if ((current_point != start_point) &&
				(current_point->intersection == nullptr \|\|
				current_point->intersection->target->hull != start_point)) {
				// skip, didn't reach a valid target. Such as the part between two processed intersections.
				return {};
				}
				}
				}

				return result;
				}

				/**
				* After knowing a trace is viable, create a #Spline of type `return_type` from it.
				*/
				static std::unique_ptr<Spline> trace_to_spline(std::list<CurveHull *> trace,
				Spline::Type return_type)
				{
				std::unique_ptr<Spline> result = return_type == Spline::Type::Bezier ?
				(std::unique_ptr<Spline>)std::make_unique<BezierSpline>() :
				(std::unique_ptr<Spline>)std::make_unique<PolySpline>();
				result->resize(trace.size());

				float last_intersection_offset = 0;
				int i = 0;
				for (CurveHull *current_point : trace) {
				if (current_point->intersection != nullptr) // current point is a virtual intersection point
				{
				process_intersection(current_point, result.get(), i, last_intersection_offset, return_type);
				}
				else {
				// This function skips non control points by itself.
				last_intersection_offset = process_control_point(
				current_point, result.get(), i, return_type, last_intersection_offset);
				}
				i++;
				}

				CurveHull *start_point = trace.front();

				if (return_type == Spline::Type::Bezier) // if cyclical result
				{
				BezierSpline bezier_result = (BezierSpline )result.get();
				// if cyclic, make sure the initial point's left handle scales with any previous intersection.
				// (If not cyclic, those handles aren't used)
				if (start_point->intersection != nullptr) {
				int segment_count = start_point->spline->segments_size();

				float current_relative_v = fmod((start_point->v * segment_count), 1.0f);

				// both handles are already resized to the following sizes
				float expected_distance_right = 1 - last_intersection_offset;
				float expected_distance_left = current_relative_v;

				// but because of this new intersection, they will need to be this size instead
				float proportional_distance_right = (1 - current_relative_v) / expected_distance_right;
				float proportional_distance_left = last_intersection_offset / expected_distance_left;

				int back_i = bezier_result->size() - 1;
				bezier_result->handle_positions_left()[0] = float3::interpolate(
				bezier_result->handle_positions_left()[0],
				bezier_result->positions()[0],
				proportional_distance_left);
				bezier_result->handle_positions_right()[back_i] = float3::interpolate(
				bezier_result->handle_positions_right()[back_i],
				bezier_result->positions()[back_i],
				proportional_distance_right);
				}
				else {
				bezier_result->handle_positions_left()[0] = float3::interpolate(
				bezier_result->handle_positions_left()[0],
				bezier_result->positions()[0],
				last_intersection_offset);
				}
				}

				return result;
				}

				/**
				* Walk along the #CurveHull and generate new #Splines from each valid path.
				*/
				static void trace_hull(std::vector<std::unique_ptr<Spline>> &results,
				CurveHull *path,
				BoolOperationType type,
				Spline::Type return_type)
				{
				std::list<CurveHull *> frontier;
				frontier.push_back(path);

				while (frontier.size() > 0) {
				CurveHull *start_point = frontier.front();
				frontier.pop_front();

				int is_inside = start_point->is_inside;

				if ((type == BoolOperationType::SUB \|\| type == BoolOperationType::OR) && is_inside == 1) {
				start_point = start_point->next_intersection();
				if (start_point == nullptr) {
				continue;
				}
				start_point = start_point->intersection->target->hull;
				}

				HooglyBooglyUnsubmitted Done Inline Actions The code should be formatted with clang format: https://wiki.blender.org/wiki/Tools/ClangFormat You can set it up to format when you save the file, then it saves a lot of time. HooglyBoogly: The code should be formatted with clang format: https://wiki.blender.org/wiki/Tools/ClangFormat…
				if (type == BoolOperationType::AND && is_inside == 0) {
				start_point = start_point->next_intersection();
				if (start_point == nullptr) {
				continue;
				}
				HooglyBooglyUnsubmitted Done Inline Actions The style guide mentions always using braces: https://wiki.blender.org/wiki/Style_Guide/C_Cpp HooglyBoogly: The style guide mentions always using braces: https://wiki.blender.org/wiki/Style_Guide/C_Cpp
				start_point = start_point->intersection->target->hull;
				}

				if (start_point->pass == -2) {
				continue;
				}
				HooglyBooglyUnsubmitted Done Inline Actions Is there something in particular you don't understand about them? Also, `SplinePtr` is not really a unique replacement, it's just a shorthand for `unique_ptr<Spline>` HooglyBoogly: Is there something in particular you don't understand about them? Also, `SplinePtr` is not…

				std::list<CurveHull *> trace = do_trace(start_point, frontier, return_type);

				if (trace.size() > 0) {
				results.push_back(trace_to_spline(trace, return_type));
				}
				}
				}

				/**
				* Do the evaluated points form a clockwise curve?
				* #Spline must have at least one point.
				*/
				static bool is_curve_clockwise(Spline *spline)
				{
				Span<float3> points = spline->evaluated_positions();

				float dotsum = 0; // calculates 2x enclosed area. If negative, curve is counter clockwise
				for (int i = 0; i < points.size() - 1; i++) {
				dotsum += (points[i + 1].x - points[i].x) * (points[i + 1].y + points[i].y);
				}

				const float3 start = points.first();
				const float3 end = points.last();
				dotsum += (start.x - end.x) * (start.y + end.y);

				return dotsum >= 0;
				}

				/**
				* Extract #Spline Pointers and put them into a resizable vector.
				* Toss all splines with length 0 for one less border case.
				*/
				static std::vector<Spline *> _unrwap_splines(blender::Span<SplinePtr> s)
				{
				std::vector<Spline *> result = {};
				for (const SplinePtr &spline : s) {
				if (spline.get()->size() > 0)
				result.push_back(spline.get());
				}
				return result;
				}
				HooglyBooglyUnsubmitted Not Done Inline Actions Retrieving non-const pointers from a span seems like it shouldn't be possible, yet somehow this compiles. If the inputs need to be changed (generally I'd aim for avoiding that), they will need to be copied. HooglyBoogly: Retrieving non-const pointers from a span seems like it shouldn't be possible, yet somehow this…

				/**
				* Generate one or more new curves from 2 existing sets of curves.
				* These curves must not self intersect.
				* The general idea is to follow one of the curves and copy the control points until an
				* intersection is found. At which point we know the other curve is bigger, so we switch to the
				* other one. We do this for each intersection until we reach our initial position.
				*/
				static std::unique_ptr<CurveEval> generate_boolean_shapes(const CurveEval *a,
				const CurveEval *b,
				BoolOperationType type,
				int resolution)
				{
				std::unique_ptr<CurveEval> result = std::make_unique<CurveEval>();

				// SplinePtr is a unique ptr. We're not modifying those, we just want their
				// data. So we cast to Spline* from the get-go.
				std::vector<Spline *> splines_a = _unrwap_splines(a->splines());
				std::vector<Spline *> splines_b = _unrwap_splines(b->splines());
				std::vector<std::vector<Spline *>> splines = {splines_a, splines_b};

				Spline::Type result_type = Spline::Type::Bezier;

				for (Span<Spline *> _splines : splines) {
				for (Spline *spline : _splines) {
				if (spline->type() != Spline::Type::Bezier) {
				result_type = Spline::Type::Poly;
				}
				}
				}

				/// First, we need to prepare the curves. Outside curves must go clockwise, inside
				/// counterclockwise. Operators may flip them yet again.

				for (Span<Spline *> _splines : splines) {
				for (Spline *spline : _splines) {
				// Auto Handles are weird. Make sure all handles are Free.
				if (spline->type() == Spline::Type::Bezier) {
				BezierSpline bezier_spline = ((BezierSpline )spline);
				MutableSpan<HandleType> handles_l_t = bezier_spline->handle_types_left();
				MutableSpan<HandleType> handles_r_t = bezier_spline->handle_types_right();
				// Bug : Don't remove ! This needs to be called or else the "auto -> free" handle change
				// loses the handle data. (It presumably flips some dirty flag that the handle_types alone
				// don't but should).
				HooglyBooglyUnsubmitted Not Done Inline Actions Right, one of the consequences of the lazy evaluation is the need for `spline->ensure_auto_handles();` when changing handle types to non-automatic types. Theoretically that could be done when retrieving a mutable span of handle types automatically, I'm not sure why I didn't do that. HooglyBoogly: Right, one of the consequences of the lazy evaluation is the need for `spline…
				kiririAuthorUnsubmitted Done Inline Actions Got it. That function name is confusing. It sounds like something you'd use while you're in auto mode, not after you switched out of it. kiriri: Got it. That function name is confusing. It sounds like something you'd use //while// you're in…
				bezier_spline->handle_positions_left();
				bezier_spline->handle_positions_right();

				int size = handles_l_t.size();
				for (int i = 0; i < size; i++) {
				handles_l_t[i] = HandleType::Free;
				handles_r_t[i] = HandleType::Free;
				}

				spline->mark_cache_invalid();
				}

				// All curves must be clockwise, unless the algorithm turns them explicitly.
				bool is_clockwise = is_curve_clockwise(spline);

				// Outside curves must go clockwise.
				// Inside curves must go counterclockwise.
				int counter = count_containing_curves(_splines, spline->positions()[0], spline);
				if (counter % 2 == (is_clockwise ? 1 : 0)) {
				// curve represents negative space, must go counterclockwise.
				spline->reverse();
				}
				}
				}

				// Some operations need one curve to go clockwise, and the other counter-clockwise.
				if (type == BoolOperationType::AND) {
				for (Spline *spline : splines_a) {
				spline->reverse();
				}
				for (Spline *spline : splines_b) {
				spline->reverse();
				}
				}
				else if (type == BoolOperationType::SUB) {
				for (Spline *spline : splines_b) {
				spline->reverse();
				}
				}

				/// Then, find all intersections
				std::list<CurveHull *> paths = splineIntersectAll(splines);

				int length = 0;

				for (CurveHull *path : paths) {
				std::vector<std::unique_ptr<Spline>> results;
				HooglyBooglyUnsubmitted Not Done Inline Actions 12 is the default value, so this shouldn't be necessary. HooglyBoogly: 12 is the default value, so this shouldn't be necessary.
				if (path->next_intersection() == nullptr) // Path does not intersect with anything.
				{
				// count the number of curves that contain this one. Depending on the mode, and if it's
				// contained in the other curve, toss it, or keep it as-is.
				int counter = count_containing_curves(path->curve_id == 0 ? splines_b : splines_a,
				path->position);
				if (type == BoolOperationType::SUB) {
				if (counter % 2 == (path->curve_id == 0 ? 0 : 1)) {
				results.push_back(path->spline->copy());
				}
				}
				else if (type == BoolOperationType::OR) {
				if (counter % 2 == 0) {
				results.push_back(path->spline->copy());
				}
				}
				else if (type == BoolOperationType::AND) {
				if (counter % 2 == 1) {
				results.push_back(path->spline->copy());
				}
				}
				}
				else {
				trace_hull(results, path, type, result_type);
				}

				/// Now turn our individual spline pointers into their final unique ptr form.

				for (std::unique_ptr<Spline> &trace : results) {
				if (trace->type() == Spline::Type::Bezier) {
				BezierSpline result_spline = (BezierSpline )trace.get();
				// BUG : Why does removing this cause SegFaults?
				result_spline->set_resolution(resolution);
				}
				trace.get()->set_cyclic(true);
				result->add_spline(std::move(trace));
				length += result->splines().size();
				}
				}

				// Remove all CurveHull and Intersection helper structs. These were created with new().
				for (CurveHull *path : paths) {
				path->remove();
				}
				HooglyBooglyUnsubmitted Not Done Inline Actions Then it should be simpler to just use `Vector<CurveHull>` :) HooglyBoogly: Then it should be simpler to just use `Vector<CurveHull>` :)
				kiririAuthorUnsubmitted Done Inline Actions CurveHull is already a double-linked-list by itself ( even quadruple-linked in parts) . And there's plenty of random insertions happening, eg whenever an intersection is found. Stuffing them all in a vector, in random order, might confuse people to what this struct actually represents. And then we'd have to turn all pointers into int offsets, which obfuscates things even further. I too am not a fan of manual allocation. But it might be the lesser evil here. Unless I'm misunderstanding you. kiriri: CurveHull is already a double-linked-list by itself ( even quadruple-linked in parts) . And…

				result->attributes.reallocate(length);

				return result;
				}

				/**
				* This is called whenever the node needs to update, such as when inputs change.
				*/
				static void geo_node_curve_bool_exec(GeoNodeExecParams params)
				{
				SCOPED_TIMER("Curve Boolean");

				int resolution = params.extract_input<int>("Int. Resolution");
				GeometrySet curve_set_a = params.extract_input<GeometrySet>("Base Curve");
				curve_set_a = bke::geometry_set_realize_instances(curve_set_a);
				std::vector<const CurveEval *> curves_b;

				Vector<GeometrySet> geometry_sets = params.extract_multi_input<GeometrySet>("Curves");

				if (!(curve_set_a.has_curve())) {
				print("Nope");
				params.set_output("Curve", curve_set_a);
				return;
				}

				const bNode &node = params.node();
				const BoolOperationType data_type = static_cast<BoolOperationType>(node.custom2);

				// Repeat the bool operation for each element in the operand `Curves` input.
				const CurveEval* primary_curve = curve_set_a.get_curve_for_read();
				std::unique_ptr<CurveEval> result_curve;
				int real_count = 0;
				for (const GeometrySet &set_group : geometry_sets) {
				const GeometrySet curve_in = bke::geometry_set_realize_instances(set_group);
				if (curve_in.has_curve()) { // TODO : What is this witchcraft? Why is geometry_sets size 1 when it's empty?
				result_curve = generate_boolean_shapes(
				primary_curve,
				curve_in.get_curve_for_read(),
				data_type,
				resolution);

				primary_curve = result_curve.get();

				real_count++;
				}
				}

				if(real_count == 0)
				{
				params.set_output("Curve", curve_set_a);
				}
				else
				{
				params.set_output("Curve", GeometrySet::create_with_curve(result_curve.release()));
				}
				}

				static void geo_node_curve_bool_declare(NodeDeclarationBuilder &b)
				{
				b.add_input<decl::Geometry>("Base Curve");
				b.add_input<decl::Geometry>("Curves").multi_input();
				b.add_input<decl::Int>("Int. Resolution").min(1).description("If multiple bezier curves are used, this node will process them one by one and generate an intermediate curve after each step. Lowering that curve's resolution will increase performance but decrease accuracy. This does not affect input curves. It does affect the output.").default_value(12);
				b.add_output<decl::Geometry>("Curve");
				}

				/**
				* This function is needed to draw the enum dropdown of operations.
				*/
				static void geo_node_curve_bool_layout(uiLayout layout, bContext UNUSED(C), PointerRNA *ptr)
				{
				uiLayoutSetPropSep(layout, true);
				uiLayoutSetPropDecorate(layout, false);
				uiItemR(layout, ptr, "operation", 0, "", ICON_NONE);
				}

				} // namespace blender::nodes

				void register_node_type_geo_curve_bool()
				{
				static bNodeType ntype;
				geo_node_type_base(&ntype, GEO_NODE_CURVE_BOOL, "Curve Bool", NODE_CLASS_GEOMETRY, 0);
				ntype.geometry_node_execute = blender::nodes::geo_node_curve_bool_exec;
				ntype.draw_buttons = blender::nodes::geo_node_curve_bool_layout;
				ntype.declare = blender::nodes::geo_node_curve_bool_declare;
				nodeRegisterType(&ntype);
				}