blender
/
blender
129
397
Fork 571
Code Issues 6.2k Pull Requests 750 Projects 19 Wiki Activity

Curves: Port delete geometry node to the new curves type 

Add a method to remove points from the new curves type, just like
the existing curve removal function. No functional changes are expected.
The code is simpler because all data is just stored as attributes, but
also different because the point data for all curves is stored in the same
arrays.

Similar performance improvements as other commits in T95443 are
expected, expecially for cases where there are many small curves.

Differential Revision: https://developer.blender.org/D15130
This commit is contained in:
Hans Goudey 2022-06-09 13:09:04 +02:00
parent 0fddff027e
commit 8a6cbcf386
Notes: blender-bot 2023-02-13 16:20:51 +01:00 
Referenced by issue #95443, Refactor curve nodes to use new data structure
3 changed files with 202 additions and 167 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

1
source/blender/blenkernel/BKE_curves.hh
View File

@ -387,6 +387,7 @@ class CurvesGeometry : public ::CurvesGeometry {
void update_customdata_pointers();
void remove_points(IndexMask points_to_delete);
void remove_curves(IndexMask curves_to_delete);
/**

191
source/blender/blenkernel/intern/curves_geometry.cc
View File

@ -1100,6 +1100,165 @@ static void *ensure_customdata_layer(CustomData &custom_data,
&custom_data, data_type, CD_DEFAULT, nullptr, tot_elements, name.c_str());
}
static void copy_between_buffers(const CPPType &type,
const void *src_buffer,
void *dst_buffer,
const IndexRange src_range,
const IndexRange dst_range)
{
BLI_assert(src_range.size() == dst_range.size());
type.copy_construct_n(POINTER_OFFSET(src_buffer, type.size() * src_range.start()),
POINTER_OFFSET(dst_buffer, type.size() * dst_range.start()),
src_range.size());
}
template<typename T>
static void copy_with_map(const Span<T> src, const Span<int> map, MutableSpan<T> dst)
{
threading::parallel_for(map.index_range(), 1024, [&](const IndexRange range) {
for (const int i : range) {
dst[i] = src[map[i]];
}
});
}
static void copy_with_map(const GSpan src, const Span<int> map, GMutableSpan dst)
{
attribute_math::convert_to_static_type(src.type(), [&](auto dummy) {
using T = decltype(dummy);
copy_with_map(src.typed<T>(), map, dst.typed<T>());
});
}
/**
* Builds an array that for every point, contains the corresponding curve index.
*/
static Array<int> build_point_to_curve_map(const CurvesGeometry &curves)
{
Array<int> point_to_curve_map(curves.points_num());
threading::parallel_for(curves.curves_range(), 1024, [&](const IndexRange curves_range) {
for (const int i_curve : curves_range) {
point_to_curve_map.as_mutable_span().slice(curves.points_for_curve(i_curve)).fill(i_curve);
}
});
return point_to_curve_map;
}
static CurvesGeometry copy_with_removed_points(const CurvesGeometry &curves,
const IndexMask points_to_delete)
{
/* Use a map from points to curves to facilitate using an #IndexMask input. */
const Array<int> point_to_curve_map = build_point_to_curve_map(curves);
const Vector<IndexRange> copy_point_ranges = points_to_delete.extract_ranges_invert(
curves.points_range());
/* For every range of points to copy, find the offset in the result curves point layers. */
int new_point_count = 0;
Array<int> copy_point_range_dst_offsets(copy_point_ranges.size());
for (const int i : copy_point_ranges.index_range()) {
copy_point_range_dst_offsets[i] = new_point_count;
new_point_count += copy_point_ranges[i].size();
}
BLI_assert(new_point_count == (curves.points_num() - points_to_delete.size()));
/* Find out how many non-deleted points there are in every curve. */
Array<int> curve_point_counts(curves.curves_num(), 0);
for (const IndexRange range : copy_point_ranges) {
for (const int point_i : range) {
curve_point_counts[point_to_curve_map[point_i]]++;
}
}
/* Build the offsets for the new curve points, skipping curves that had all points deleted.
* Also store the original indices of the corresponding input curves, to facilitate parallel
* copying of curve domain data. */
int new_curve_count = 0;
int curve_point_offset = 0;
Vector<int> new_curve_offsets;
Vector<int> new_curve_orig_indices;
new_curve_offsets.append(0);
for (const int i : curve_point_counts.index_range()) {
if (curve_point_counts[i] > 0) {
curve_point_offset += curve_point_counts[i];
new_curve_offsets.append(curve_point_offset);
new_curve_count++;
new_curve_orig_indices.append(i);
}
}
CurvesGeometry new_curves{new_point_count, new_curve_count};
threading::parallel_invoke(
/* Initialize curve offsets. */
[&]() { new_curves.offsets_for_write().copy_from(new_curve_offsets); },
/* Copy over point attributes. */
[&]() {
const CustomData &old_point_data = curves.point_data;
CustomData &new_point_data = new_curves.point_data;
for (const int layer_i : IndexRange(old_point_data.totlayer)) {
const CustomDataLayer &old_layer = old_point_data.layers[layer_i];
const eCustomDataType data_type = static_cast<eCustomDataType>(old_layer.type);
const CPPType &type = *bke::custom_data_type_to_cpp_type(data_type);
void *dst_buffer = ensure_customdata_layer(
new_point_data, old_layer.name, data_type, new_point_count);
threading::parallel_for(
copy_point_ranges.index_range(), 128, [&](const IndexRange ranges_range) {
for (const int range_i : ranges_range) {
const IndexRange src_range = copy_point_ranges[range_i];
copy_between_buffers(type,
old_layer.data,
dst_buffer,
src_range,
{copy_point_range_dst_offsets[range_i], src_range.size()});
}
});
}
},
/* Copy over curve attributes.
* In some cases points are just dissolved, so the the number of
* curves will be the same. That could be optimized in the future. */
[&]() {
const CustomData &old_curve_data = curves.curve_data;
CustomData &new_curve_data = new_curves.curve_data;
for (const int layer_i : IndexRange(old_curve_data.totlayer)) {
const CustomDataLayer &old_layer = old_curve_data.layers[layer_i];
const eCustomDataType data_type = static_cast<eCustomDataType>(old_layer.type);
const CPPType &type = *bke::custom_data_type_to_cpp_type(data_type);
void *dst_buffer = ensure_customdata_layer(
new_curve_data, old_layer.name, data_type, new_curve_count);
if (new_curves.curves_num() == curves.curves_num()) {
type.copy_construct_n(old_layer.data, dst_buffer, new_curves.curves_num());
}
else {
copy_with_map({type, old_layer.data, curves.curves_num()},
new_curve_orig_indices,
{type, dst_buffer, new_curves.curves_num()});
}
}
});
new_curves.update_curve_types();
return new_curves;
}
void CurvesGeometry::remove_points(const IndexMask points_to_delete)
{
if (points_to_delete.is_empty()) {
return;
}
if (points_to_delete.size() == this->points_num()) {
*this = {};
}
*this = copy_with_removed_points(*this, points_to_delete);
}
static CurvesGeometry copy_with_removed_curves(const CurvesGeometry &curves,
const IndexMask curves_to_delete)
{
@ -1159,20 +1318,17 @@ static CurvesGeometry copy_with_removed_curves(const CurvesGeometry &curves,
const eCustomDataType data_type = static_cast<eCustomDataType>(old_layer.type);
const CPPType &type = *bke::custom_data_type_to_cpp_type(data_type);
const void *src_buffer = old_layer.data;
void *dst_buffer = ensure_customdata_layer(
new_point_data, old_layer.name, data_type, new_tot_points);
threading::parallel_for(
old_curve_ranges.index_range(), 128, [&](const IndexRange ranges_range) {
for (const int range_i : ranges_range) {
const IndexRange old_point_range = old_point_ranges[range_i];
const IndexRange new_point_range = new_point_ranges[range_i];
type.copy_construct_n(
POINTER_OFFSET(src_buffer, type.size() * old_point_range.start()),
POINTER_OFFSET(dst_buffer, type.size() * new_point_range.start()),
old_point_range.size());
copy_between_buffers(type,
old_layer.data,
dst_buffer,
old_point_ranges[range_i],
new_point_ranges[range_i]);
}
});
}
@ -1186,20 +1342,17 @@ static CurvesGeometry copy_with_removed_curves(const CurvesGeometry &curves,
const eCustomDataType data_type = static_cast<eCustomDataType>(old_layer.type);
const CPPType &type = *bke::custom_data_type_to_cpp_type(data_type);
const void *src_buffer = old_layer.data;
void *dst_buffer = ensure_customdata_layer(
new_curve_data, old_layer.name, data_type, new_tot_curves);
threading::parallel_for(
old_curve_ranges.index_range(), 128, [&](const IndexRange ranges_range) {
for (const int range_i : ranges_range) {
const IndexRange old_curve_range = old_curve_ranges[range_i];
const IndexRange new_curve_range = new_curve_ranges[range_i];
type.copy_construct_n(
POINTER_OFFSET(src_buffer, type.size() * old_curve_range.start()),
POINTER_OFFSET(dst_buffer, type.size() * new_curve_range.start()),
old_curve_range.size());
copy_between_buffers(type,
old_layer.data,
dst_buffer,
old_curve_ranges[range_i],
new_curve_ranges[range_i]);
}
});
}
@ -1212,6 +1365,12 @@ static CurvesGeometry copy_with_removed_curves(const CurvesGeometry &curves,
void CurvesGeometry::remove_curves(const IndexMask curves_to_delete)
{
if (curves_to_delete.is_empty()) {
return;
}
if (curves_to_delete.size() == this->curves_num()) {
*this = {};
}
*this = copy_with_removed_curves(*this, curves_to_delete);
}

177
source/blender/nodes/geometry/nodes/node_geo_delete_geometry.cc
View File

@ -8,10 +8,10 @@
#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
#include "BKE_curves.hh"
#include "BKE_customdata.h"
#include "BKE_mesh.h"
#include "BKE_pointcloud.h"
#include "BKE_spline.hh"
#include "node_geometry_util.hh"
@ -311,161 +311,35 @@ static void copy_masked_polys_to_new_mesh(const Mesh &src_mesh,
}
}
static void spline_copy_builtin_attributes(const Spline &spline,
Spline &r_spline,
const IndexMask mask)
{
copy_data_based_on_mask(spline.positions(), r_spline.positions(), mask);
copy_data_based_on_mask(spline.radii(), r_spline.radii(), mask);
copy_data_based_on_mask(spline.tilts(), r_spline.tilts(), mask);
switch (spline.type()) {
case CURVE_TYPE_POLY:
break;
case CURVE_TYPE_BEZIER: {
const BezierSpline &src = static_cast<const BezierSpline &>(spline);
BezierSpline &dst = static_cast<BezierSpline &>(r_spline);
copy_data_based_on_mask(src.handle_positions_left(), dst.handle_positions_left(), mask);
copy_data_based_on_mask(src.handle_positions_right(), dst.handle_positions_right(), mask);
copy_data_based_on_mask(src.handle_types_left(), dst.handle_types_left(), mask);
copy_data_based_on_mask(src.handle_types_right(), dst.handle_types_right(), mask);
break;
}
case CURVE_TYPE_NURBS: {
const NURBSpline &src = static_cast<const NURBSpline &>(spline);
NURBSpline &dst = static_cast<NURBSpline &>(r_spline);
copy_data_based_on_mask(src.weights(), dst.weights(), mask);
break;
}
case CURVE_TYPE_CATMULL_ROM: {
BLI_assert_unreachable();
break;
}
}
}
static void copy_dynamic_attributes(const CustomDataAttributes &src,
CustomDataAttributes &dst,
const IndexMask mask)
{
src.foreach_attribute(
[&](const AttributeIDRef &attribute_id, const AttributeMetaData &meta_data) {
std::optional<GSpan> src_attribute = src.get_for_read(attribute_id);
BLI_assert(src_attribute);
if (!dst.create(attribute_id, meta_data.data_type)) {
/* Since the source spline of the same type had the attribute, adding it should work.
*/
BLI_assert_unreachable();
}
std::optional<GMutableSpan> new_attribute = dst.get_for_write(attribute_id);
BLI_assert(new_attribute);
attribute_math::convert_to_static_type(new_attribute->type(), [&](auto dummy) {
using T = decltype(dummy);
copy_data_based_on_mask(src_attribute->typed<T>(), new_attribute->typed<T>(), mask);
});
return true;
},
ATTR_DOMAIN_POINT);
}
/**
* Deletes points in the spline. Those not in the mask are deleted. The spline is not split into
* multiple newer splines.
*/
static SplinePtr spline_delete(const Spline &spline, const IndexMask mask)
{
SplinePtr new_spline = spline.copy_only_settings();
new_spline->resize(mask.size());
spline_copy_builtin_attributes(spline, *new_spline, mask);
copy_dynamic_attributes(spline.attributes, new_spline->attributes, mask);
return new_spline;
}
static std::unique_ptr<CurveEval> curve_separate(const CurveEval &input_curve,
const Span<bool> selection,
const eAttrDomain selection_domain)
{
Span<SplinePtr> input_splines = input_curve.splines();
std::unique_ptr<CurveEval> output_curve = std::make_unique<CurveEval>();
/* Keep track of which splines were copied to the result to copy spline domain attributes. */
Vector<int64_t> copied_splines;
if (selection_domain == ATTR_DOMAIN_CURVE) {
/* Operates on each of the splines as a whole, i.e. not on the points in the splines
* themselves. */
for (const int i : selection.index_range()) {
if (selection[i]) {
output_curve->add_spline(input_splines[i]->copy());
copied_splines.append(i);
}
}
}
else {
/* Operates on the points in the splines themselves. */
/* Reuse index vector for each spline. */
Vector<int64_t> indices_to_copy;
int selection_index = 0;
for (const int i : input_splines.index_range()) {
const Spline &spline = *input_splines[i];
indices_to_copy.clear();
for (const int i_point : IndexRange(spline.size())) {
if (selection[selection_index]) {
/* Append i_point instead of selection_index because we need indices local to the spline
* for copying. */
indices_to_copy.append(i_point);
}
selection_index++;
}
/* Avoid creating an empty spline. */
if (indices_to_copy.is_empty()) {
continue;
}
SplinePtr new_spline = spline_delete(spline, IndexMask(indices_to_copy));
output_curve->add_spline(std::move(new_spline));
copied_splines.append(i);
}
}
if (copied_splines.is_empty()) {
return {};
}
output_curve->attributes.reallocate(output_curve->splines().size());
copy_dynamic_attributes(
input_curve.attributes, output_curve->attributes, IndexMask(copied_splines));
return output_curve;
}
static void separate_curve_selection(GeometrySet &geometry_set,
const Field<bool> &selection_field,
const eAttrDomain selection_domain)
static void delete_curves_selection(GeometrySet &geometry_set,
const Field<bool> &selection_field,
const eAttrDomain selection_domain)
{
const CurveComponent &src_component = *geometry_set.get_component_for_read<CurveComponent>();
GeometryComponentFieldContext field_context{src_component, selection_domain};
fn::FieldEvaluator evaluator{field_context,
src_component.attribute_domain_num(selection_domain)};
evaluator.add(selection_field);
const int domain_num = src_component.attribute_domain_num(selection_domain);
fn::FieldEvaluator evaluator{field_context, domain_num};
evaluator.set_selection(selection_field);
evaluator.evaluate();
const VArray_Span<bool> &selection = evaluator.get_evaluated<bool>(0);
std::unique_ptr<CurveEval> r_curve = curve_separate(
*curves_to_curve_eval(*src_component.get_for_read()), selection, selection_domain);
if (r_curve) {
geometry_set.replace_curves(curve_eval_to_curves(*r_curve));
const IndexMask selection = evaluator.get_evaluated_selection_as_mask();
if (selection.is_empty()) {
return;
}
else {
geometry_set.replace_curves(nullptr);
if (selection.size() == domain_num) {
geometry_set.remove<CurveComponent>();
return;
}
CurveComponent &component = geometry_set.get_component_for_write<CurveComponent>();
Curves &curves_id = *component.get_for_write();
bke::CurvesGeometry &curves = bke::CurvesGeometry::wrap(curves_id.geometry);
if (selection_domain == ATTR_DOMAIN_POINT) {
curves.remove_points(selection);
}
else if (selection_domain == ATTR_DOMAIN_CURVE) {
curves.remove_curves(selection);
}
}
@ -1224,7 +1098,8 @@ void separate_geometry(GeometrySet &geometry_set,
}
if (geometry_set.has_curves()) {
if (ELEM(domain, ATTR_DOMAIN_POINT, ATTR_DOMAIN_CURVE)) {
file_ns::separate_curve_selection(geometry_set, selection_field, domain);
file_ns::delete_curves_selection(
geometry_set, fn::invert_boolean_field(selection_field), domain);
some_valid_domain = true;
}
}