diff options
Diffstat (limited to 'source/blender/geometry/intern')
-rw-r--r-- | source/blender/geometry/intern/add_curves_on_mesh.cc | 43 | ||||
-rw-r--r-- | source/blender/geometry/intern/mesh_merge_by_distance.cc | 82 | ||||
-rw-r--r-- | source/blender/geometry/intern/mesh_primitive_cuboid.cc | 11 | ||||
-rw-r--r-- | source/blender/geometry/intern/mesh_to_curve_convert.cc | 26 | ||||
-rw-r--r-- | source/blender/geometry/intern/mesh_to_volume.cc | 9 | ||||
-rw-r--r-- | source/blender/geometry/intern/point_merge_by_distance.cc | 5 | ||||
-rw-r--r-- | source/blender/geometry/intern/realize_instances.cc | 188 | ||||
-rw-r--r-- | source/blender/geometry/intern/resample_curves.cc | 239 | ||||
-rw-r--r-- | source/blender/geometry/intern/reverse_uv_sampler.cc | 18 | ||||
-rw-r--r-- | source/blender/geometry/intern/trim_curves.cc | 1299 | ||||
-rw-r--r-- | source/blender/geometry/intern/uv_parametrizer.cc | 95 |
11 files changed, 1738 insertions, 277 deletions
diff --git a/source/blender/geometry/intern/add_curves_on_mesh.cc b/source/blender/geometry/intern/add_curves_on_mesh.cc index 299040d4d32..bb5e2a0a28a 100644 --- a/source/blender/geometry/intern/add_curves_on_mesh.cc +++ b/source/blender/geometry/intern/add_curves_on_mesh.cc @@ -4,6 +4,7 @@ #include "BLI_task.hh" #include "BKE_attribute_math.hh" +#include "BKE_mesh.h" #include "BKE_mesh_sample.hh" #include "GEO_add_curves_on_mesh.hh" @@ -244,6 +245,8 @@ AddCurvesOnMeshOutputs add_curves_on_mesh(CurvesGeometry &curves, Vector<float2> used_uvs; /* Find faces that the passed in uvs belong to. */ + const Span<MVert> surface_verts = inputs.surface->verts(); + const Span<MLoop> surface_loops = inputs.surface->loops(); for (const int i : inputs.uvs.index_range()) { const float2 &uv = inputs.uvs[i]; const ReverseUVSampler::Result result = inputs.reverse_uv_sampler->sample(uv); @@ -256,9 +259,9 @@ AddCurvesOnMeshOutputs add_curves_on_mesh(CurvesGeometry &curves, looptris.append(&looptri); const float3 root_position_su = attribute_math::mix3<float3>( result.bary_weights, - inputs.surface->mvert[inputs.surface->mloop[looptri.tri[0]].v].co, - inputs.surface->mvert[inputs.surface->mloop[looptri.tri[1]].v].co, - inputs.surface->mvert[inputs.surface->mloop[looptri.tri[2]].v].co); + surface_verts[surface_loops[looptri.tri[0]].v].co, + surface_verts[surface_loops[looptri.tri[1]].v].co, + surface_verts[surface_loops[looptri.tri[2]].v].co); root_positions_cu.append(inputs.transforms->surface_to_curves * root_position_su); used_uvs.append(uv); } @@ -276,6 +279,7 @@ AddCurvesOnMeshOutputs add_curves_on_mesh(CurvesGeometry &curves, /* Grow number of curves first, so that the offsets array can be filled. */ curves.resize(old_points_num, new_curves_num); + const IndexRange new_curves_range = curves.curves_range().drop_front(old_curves_num); /* Compute new curve offsets. */ MutableSpan<int> curve_offsets = curves.offsets_for_write(); @@ -290,8 +294,8 @@ AddCurvesOnMeshOutputs add_curves_on_mesh(CurvesGeometry &curves, else { new_point_counts_per_curve.fill(inputs.fallback_point_count); } - for (const int i : IndexRange(added_curves_num)) { - curve_offsets[old_curves_num + i + 1] += curve_offsets[old_curves_num + i]; + for (const int i : new_curves_range) { + curve_offsets[i + 1] += curve_offsets[i]; } const int new_points_num = curves.offsets().last(); @@ -342,7 +346,7 @@ AddCurvesOnMeshOutputs add_curves_on_mesh(CurvesGeometry &curves, const VArray<float> curves_selection = curves.selection_curve_float(); if (curves_selection.is_span()) { MutableSpan<float> curves_selection_span = curves.selection_curve_float_for_write(); - curves_selection_span.drop_front(old_curves_num).fill(1.0f); + curves_selection_span.slice(new_curves_range).fill(1.0f); } /* Initialize position attribute. */ @@ -366,10 +370,29 @@ AddCurvesOnMeshOutputs add_curves_on_mesh(CurvesGeometry &curves, inputs.transforms->surface_to_curves_normal); } - /* Set curve types. */ - MutableSpan<int8_t> types_span = curves.curve_types_for_write(); - types_span.drop_front(old_curves_num).fill(CURVE_TYPE_CATMULL_ROM); - curves.update_curve_types(); + curves.fill_curve_types(new_curves_range, CURVE_TYPE_CATMULL_ROM); + + /* Explicitly set all other attributes besides those processed above to default values. */ + bke::MutableAttributeAccessor attributes = curves.attributes_for_write(); + Set<std::string> attributes_to_skip{{"position", + "curve_type", + "surface_uv_coordinate", + ".selection_point_float", + ".selection_curve_float"}}; + attributes.for_all( + [&](const bke::AttributeIDRef &id, const bke::AttributeMetaData /*meta_data*/) { + if (id.is_named() && attributes_to_skip.contains(id.name())) { + return true; + } + bke::GSpanAttributeWriter attribute = attributes.lookup_for_write_span(id); + const int new_elements_num = attribute.domain == ATTR_DOMAIN_POINT ? new_points_num : + new_curves_num; + const CPPType &type = attribute.span.type(); + GMutableSpan new_data = attribute.span.take_back(new_elements_num); + type.fill_assign_n(type.default_value(), new_data.data(), new_data.size()); + attribute.finish(); + return true; + }); return outputs; } diff --git a/source/blender/geometry/intern/mesh_merge_by_distance.cc b/source/blender/geometry/intern/mesh_merge_by_distance.cc index d3a5a194555..d7c35a4fcc1 100644 --- a/source/blender/geometry/intern/mesh_merge_by_distance.cc +++ b/source/blender/geometry/intern/mesh_merge_by_distance.cc @@ -1164,26 +1164,26 @@ static void weld_mesh_context_create(const Mesh &mesh, const int vert_kill_len, WeldMesh *r_weld_mesh) { - Span<MEdge> medge{mesh.medge, mesh.totedge}; - Span<MPoly> mpoly{mesh.mpoly, mesh.totpoly}; - Span<MLoop> mloop{mesh.mloop, mesh.totloop}; const int mvert_len = mesh.totvert; + const Span<MEdge> edges = mesh.edges(); + const Span<MPoly> polys = mesh.polys(); + const Span<MLoop> loops = mesh.loops(); Vector<WeldVert> wvert = weld_vert_ctx_alloc_and_setup(vert_dest_map, vert_kill_len); r_weld_mesh->vert_kill_len = vert_kill_len; - Array<int> edge_dest_map(medge.size()); - Array<int> edge_ctx_map(medge.size()); - Vector<WeldEdge> wedge = weld_edge_ctx_alloc(medge, vert_dest_map, edge_dest_map, edge_ctx_map); + Array<int> edge_dest_map(edges.size()); + Array<int> edge_ctx_map(edges.size()); + Vector<WeldEdge> wedge = weld_edge_ctx_alloc(edges, vert_dest_map, edge_dest_map, edge_ctx_map); Array<WeldGroup> v_links(mvert_len, {0, 0}); weld_edge_ctx_setup(v_links, edge_dest_map, wedge, &r_weld_mesh->edge_kill_len); - weld_poly_loop_ctx_alloc(mpoly, mloop, vert_dest_map, edge_dest_map, r_weld_mesh); + weld_poly_loop_ctx_alloc(polys, loops, vert_dest_map, edge_dest_map, r_weld_mesh); - weld_poly_loop_ctx_setup(mloop, + weld_poly_loop_ctx_setup(loops, #ifdef USE_WELD_DEBUG - mpoly, + polys, #endif mvert_len, @@ -1198,7 +1198,7 @@ static void weld_mesh_context_create(const Mesh &mesh, r_weld_mesh->vert_groups_buffer, r_weld_mesh->vert_groups); - weld_edge_groups_setup(medge.size(), + weld_edge_groups_setup(edges.size(), r_weld_mesh->edge_kill_len, wedge, edge_ctx_map, @@ -1232,8 +1232,6 @@ static void customdata_weld( #ifdef USE_WELD_NORMALS float no[3] = {0.0f, 0.0f, 0.0f}; #endif - int crease = 0; - int bweight = 0; short flag = 0; /* interpolates a layer at a time */ @@ -1267,15 +1265,11 @@ static void customdata_weld( no[1] += mv_src_no[1]; no[2] += mv_src_no[2]; #endif - bweight += mv_src->bweight; - flag |= mv_src->flag; } } else if (type == CD_MEDGE) { for (j = 0; j < count; j++) { MEdge *me_src = &((MEdge *)src_data)[src_indices[j]]; - crease += me_src->crease; - bweight += me_src->bweight; flag |= me_src->flag; } } @@ -1312,8 +1306,6 @@ static void customdata_weld( if (type == CD_MVERT) { MVert *mv = &((MVert *)layer_dst->data)[dest_index]; mul_v3_fl(co, fac); - bweight *= fac; - CLAMP_MAX(bweight, 255); copy_v3_v3(mv->co, co); #ifdef USE_WELD_NORMALS @@ -1323,19 +1315,9 @@ static void customdata_weld( mv_no[1] = (short)no[1]; mv_no[2] = (short)no[2]; #endif - - mv->flag = (char)flag; - mv->bweight = (char)bweight; } else if (type == CD_MEDGE) { MEdge *me = &((MEdge *)layer_dst->data)[dest_index]; - crease *= fac; - bweight *= fac; - CLAMP_MAX(crease, 255); - CLAMP_MAX(bweight, 255); - - me->crease = (char)crease; - me->bweight = (char)bweight; me->flag = flag; } else if (CustomData_layer_has_interp(dest, dest_i)) { @@ -1360,23 +1342,24 @@ static Mesh *create_merged_mesh(const Mesh &mesh, MutableSpan<int> vert_dest_map, const int removed_vertex_count) { - Span<MPoly> mpoly{mesh.mpoly, mesh.totpoly}; - Span<MLoop> mloop{mesh.mloop, mesh.totloop}; + const Span<MPoly> src_polys = mesh.polys(); + const Span<MLoop> src_loops = mesh.loops(); const int totvert = mesh.totvert; const int totedge = mesh.totedge; - const int totloop = mesh.totloop; - const int totpoly = mesh.totpoly; WeldMesh weld_mesh; weld_mesh_context_create(mesh, vert_dest_map, removed_vertex_count, &weld_mesh); const int result_nverts = totvert - weld_mesh.vert_kill_len; const int result_nedges = totedge - weld_mesh.edge_kill_len; - const int result_nloops = totloop - weld_mesh.loop_kill_len; - const int result_npolys = totpoly - weld_mesh.poly_kill_len + weld_mesh.wpoly_new_len; + const int result_nloops = src_loops.size() - weld_mesh.loop_kill_len; + const int result_npolys = src_polys.size() - weld_mesh.poly_kill_len + weld_mesh.wpoly_new_len; Mesh *result = BKE_mesh_new_nomain_from_template( &mesh, result_nverts, result_nedges, 0, result_nloops, result_npolys); + MutableSpan<MEdge> dst_edges = result->edges_for_write(); + MutableSpan<MPoly> dst_polys = result->polys_for_write(); + MutableSpan<MLoop> dst_loops = result->loops_for_write(); /* Vertices. */ @@ -1431,7 +1414,7 @@ static Mesh *create_merged_mesh(const Mesh &mesh, } if (count) { CustomData_copy_data(&mesh.edata, &result->edata, source_index, dest_index, count); - MEdge *me = &result->medge[dest_index]; + MEdge *me = &dst_edges[dest_index]; dest_index += count; for (; count--; me++) { me->v1 = vert_final[me->v1]; @@ -1448,7 +1431,7 @@ static Mesh *create_merged_mesh(const Mesh &mesh, &weld_mesh.edge_groups_buffer[wegrp->group.ofs], wegrp->group.len, dest_index); - MEdge *me = &result->medge[dest_index]; + MEdge *me = &dst_edges[dest_index]; me->v1 = vert_final[wegrp->v1]; me->v2 = vert_final[wegrp->v2]; /* "For now, assume that all merged edges are loose. This flag will be cleared in the @@ -1464,13 +1447,13 @@ static Mesh *create_merged_mesh(const Mesh &mesh, /* Polys/Loops. */ - MPoly *r_mp = &result->mpoly[0]; - MLoop *r_ml = &result->mloop[0]; + MPoly *r_mp = dst_polys.data(); + MLoop *r_ml = dst_loops.data(); int r_i = 0; int loop_cur = 0; Array<int, 64> group_buffer(weld_mesh.max_poly_len); - for (const int i : mpoly.index_range()) { - const MPoly &mp = mpoly[i]; + for (const int i : src_polys.index_range()) { + const MPoly &mp = src_polys[i]; const int loop_start = loop_cur; const int poly_ctx = weld_mesh.poly_map[i]; if (poly_ctx == OUT_OF_CONTEXT) { @@ -1486,7 +1469,7 @@ static Mesh *create_merged_mesh(const Mesh &mesh, const WeldPoly &wp = weld_mesh.wpoly[poly_ctx]; WeldLoopOfPolyIter iter; if (!weld_iter_loop_of_poly_begin( - iter, wp, weld_mesh.wloop, mloop, weld_mesh.loop_map, group_buffer.data())) { + iter, wp, weld_mesh.wloop, src_loops, weld_mesh.loop_map, group_buffer.data())) { continue; } @@ -1503,9 +1486,9 @@ static Mesh *create_merged_mesh(const Mesh &mesh, r_ml++; loop_cur++; if (iter.type) { - result->medge[e].flag &= ~ME_LOOSEEDGE; + dst_edges[e].flag &= ~ME_LOOSEEDGE; } - BLI_assert((result->medge[e].flag & ME_LOOSEEDGE) == 0); + BLI_assert((dst_edges[e].flag & ME_LOOSEEDGE) == 0); } } @@ -1522,7 +1505,7 @@ static Mesh *create_merged_mesh(const Mesh &mesh, const int loop_start = loop_cur; WeldLoopOfPolyIter iter; if (!weld_iter_loop_of_poly_begin( - iter, wp, weld_mesh.wloop, mloop, weld_mesh.loop_map, group_buffer.data())) { + iter, wp, weld_mesh.wloop, src_loops, weld_mesh.loop_map, group_buffer.data())) { continue; } @@ -1538,9 +1521,9 @@ static Mesh *create_merged_mesh(const Mesh &mesh, r_ml++; loop_cur++; if (iter.type) { - result->medge[e].flag &= ~ME_LOOSEEDGE; + dst_edges[e].flag &= ~ME_LOOSEEDGE; } - BLI_assert((result->medge[e].flag & ME_LOOSEEDGE) == 0); + BLI_assert((dst_edges[e].flag & ME_LOOSEEDGE) == 0); } r_mp->loopstart = loop_start; @@ -1569,8 +1552,9 @@ std::optional<Mesh *> mesh_merge_by_distance_all(const Mesh &mesh, KDTree_3d *tree = BLI_kdtree_3d_new(selection.size()); + const Span<MVert> verts = mesh.verts(); for (const int i : selection) { - BLI_kdtree_3d_insert(tree, i, mesh.mvert[i].co); + BLI_kdtree_3d_insert(tree, i, verts[i].co); } BLI_kdtree_3d_balance(tree); @@ -1595,8 +1579,8 @@ std::optional<Mesh *> mesh_merge_by_distance_connected(const Mesh &mesh, const float merge_distance, const bool only_loose_edges) { - Span<MVert> verts{mesh.mvert, mesh.totvert}; - Span<MEdge> edges{mesh.medge, mesh.totedge}; + const Span<MVert> verts = mesh.verts(); + const Span<MEdge> edges = mesh.edges(); int vert_kill_len = 0; diff --git a/source/blender/geometry/intern/mesh_primitive_cuboid.cc b/source/blender/geometry/intern/mesh_primitive_cuboid.cc index 486d8adbf39..39571f2931e 100644 --- a/source/blender/geometry/intern/mesh_primitive_cuboid.cc +++ b/source/blender/geometry/intern/mesh_primitive_cuboid.cc @@ -54,7 +54,7 @@ struct CuboidConfig { } }; -static void calculate_vertices(const CuboidConfig &config, MutableSpan<MVert> verts) +static void calculate_verts(const CuboidConfig &config, MutableSpan<MVert> verts) { const float z_bottom = -config.size.z / 2.0f; const float z_delta = config.size.z / config.edges_z; @@ -321,7 +321,7 @@ static void calculate_polys(const CuboidConfig &config, static void calculate_uvs(const CuboidConfig &config, Mesh *mesh, const bke::AttributeIDRef &uv_id) { - bke::MutableAttributeAccessor attributes = bke::mesh_attributes_for_write(*mesh); + bke::MutableAttributeAccessor attributes = mesh->attributes_for_write(); bke::SpanAttributeWriter<float2> uv_attribute = attributes.lookup_or_add_for_write_only_span<float2>(uv_id, ATTR_DOMAIN_CORNER); MutableSpan<float2> uvs = uv_attribute.span; @@ -405,10 +405,13 @@ Mesh *create_cuboid_mesh(const float3 &size, Mesh *mesh = BKE_mesh_new_nomain( config.vertex_count, 0, 0, config.loop_count, config.poly_count); + MutableSpan<MVert> verts = mesh->verts_for_write(); + MutableSpan<MPoly> polys = mesh->polys_for_write(); + MutableSpan<MLoop> loops = mesh->loops_for_write(); - calculate_vertices(config, {mesh->mvert, mesh->totvert}); + calculate_verts(config, verts); - calculate_polys(config, {mesh->mpoly, mesh->totpoly}, {mesh->mloop, mesh->totloop}); + calculate_polys(config, polys, loops); BKE_mesh_calc_edges(mesh, false, false); if (uv_id) { diff --git a/source/blender/geometry/intern/mesh_to_curve_convert.cc b/source/blender/geometry/intern/mesh_to_curve_convert.cc index 350dfe73d57..c2a9b16c8b6 100644 --- a/source/blender/geometry/intern/mesh_to_curve_convert.cc +++ b/source/blender/geometry/intern/mesh_to_curve_convert.cc @@ -1,6 +1,7 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ #include "BLI_array.hh" +#include "BLI_array_utils.hh" #include "BLI_devirtualize_parameters.hh" #include "BLI_set.hh" #include "BLI_task.hh" @@ -12,24 +13,12 @@ #include "BKE_attribute_math.hh" #include "BKE_curves.hh" #include "BKE_geometry_set.hh" +#include "BKE_mesh.h" #include "GEO_mesh_to_curve.hh" namespace blender::geometry { -template<typename T> -static void copy_with_map(const VArray<T> &src, Span<int> map, MutableSpan<T> dst) -{ - devirtualize_varray(src, [&](const auto &src) { - threading::parallel_for(map.index_range(), 1024, [&](const IndexRange range) { - for (const int i : range) { - const int vert_index = map[i]; - dst[i] = src[vert_index]; - } - }); - }); -} - bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh, const Span<int> vert_indices, const Span<int> curve_offsets, @@ -43,7 +32,7 @@ bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh, curves.cyclic_for_write().fill(false); curves.cyclic_for_write().slice(cyclic_curves).fill(true); - const bke::AttributeAccessor mesh_attributes = bke::mesh_attributes(mesh); + const bke::AttributeAccessor mesh_attributes = mesh.attributes(); bke::MutableAttributeAccessor curves_attributes = curves.attributes_for_write(); Set<bke::AttributeIDRef> source_attribute_ids = mesh_attributes.all_ids(); @@ -70,7 +59,7 @@ bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh, using T = decltype(dummy); bke::SpanAttributeWriter<T> attribute = curves_attributes.lookup_or_add_for_write_only_span<T>(attribute_id, ATTR_DOMAIN_POINT); - copy_with_map<T>(mesh_attribute.typed<T>(), vert_indices, attribute.span); + array_utils::gather<T>(mesh_attribute.typed<T>(), vert_indices, attribute.span); attribute.finish(); }); } @@ -213,8 +202,9 @@ static CurveFromEdgesOutput edges_to_curve_point_indices(Span<MVert> verts, static Vector<std::pair<int, int>> get_selected_edges(const Mesh &mesh, const IndexMask selection) { Vector<std::pair<int, int>> selected_edges; + const Span<MEdge> edges = mesh.edges(); for (const int i : selection) { - selected_edges.append({mesh.medge[i].v1, mesh.medge[i].v2}); + selected_edges.append({edges[i].v1, edges[i].v2}); } return selected_edges; } @@ -222,8 +212,8 @@ static Vector<std::pair<int, int>> get_selected_edges(const Mesh &mesh, const In bke::CurvesGeometry mesh_to_curve_convert(const Mesh &mesh, const IndexMask selection) { Vector<std::pair<int, int>> selected_edges = get_selected_edges(mesh, selection); - CurveFromEdgesOutput output = edges_to_curve_point_indices({mesh.mvert, mesh.totvert}, - selected_edges); + const Span<MVert> verts = mesh.verts(); + CurveFromEdgesOutput output = edges_to_curve_point_indices(verts, selected_edges); return create_curve_from_vert_indices( mesh, output.vert_indices, output.curve_offsets, output.cyclic_curves); diff --git a/source/blender/geometry/intern/mesh_to_volume.cc b/source/blender/geometry/intern/mesh_to_volume.cc index ae98b048a6c..b1c7be38609 100644 --- a/source/blender/geometry/intern/mesh_to_volume.cc +++ b/source/blender/geometry/intern/mesh_to_volume.cc @@ -1,5 +1,6 @@ /* SPDX-License-Identifier: GPL-2.0-or-later */ +#include "BKE_mesh.h" #include "BKE_mesh_runtime.h" #include "BKE_volume.h" @@ -15,7 +16,7 @@ namespace blender::geometry { /* This class follows the MeshDataAdapter interface from openvdb. */ class OpenVDBMeshAdapter { private: - Span<MVert> vertices_; + Span<MVert> verts_; Span<MLoop> loops_; Span<MLoopTri> looptris_; float4x4 transform_; @@ -29,7 +30,7 @@ class OpenVDBMeshAdapter { }; OpenVDBMeshAdapter::OpenVDBMeshAdapter(const Mesh &mesh, float4x4 transform) - : vertices_(mesh.mvert, mesh.totvert), loops_(mesh.mloop, mesh.totloop), transform_(transform) + : verts_(mesh.verts()), loops_(mesh.loops()), transform_(transform) { /* This only updates a cache and can be considered to be logically const. */ const MLoopTri *looptris = BKE_mesh_runtime_looptri_ensure(&mesh); @@ -44,7 +45,7 @@ size_t OpenVDBMeshAdapter::polygonCount() const size_t OpenVDBMeshAdapter::pointCount() const { - return static_cast<size_t>(vertices_.size()); + return static_cast<size_t>(verts_.size()); } size_t OpenVDBMeshAdapter::vertexCount(size_t UNUSED(polygon_index)) const @@ -58,7 +59,7 @@ void OpenVDBMeshAdapter::getIndexSpacePoint(size_t polygon_index, openvdb::Vec3d &pos) const { const MLoopTri &looptri = looptris_[polygon_index]; - const MVert &vertex = vertices_[loops_[looptri.tri[vertex_index]].v]; + const MVert &vertex = verts_[loops_[looptri.tri[vertex_index]].v]; const float3 transformed_co = transform_ * float3(vertex.co); pos = &transformed_co.x; } diff --git a/source/blender/geometry/intern/point_merge_by_distance.cc b/source/blender/geometry/intern/point_merge_by_distance.cc index 42fac849667..81f57f785a3 100644 --- a/source/blender/geometry/intern/point_merge_by_distance.cc +++ b/source/blender/geometry/intern/point_merge_by_distance.cc @@ -17,7 +17,7 @@ PointCloud *point_merge_by_distance(const PointCloud &src_points, const float merge_distance, const IndexMask selection) { - const bke::AttributeAccessor src_attributes = bke::pointcloud_attributes(src_points); + const bke::AttributeAccessor src_attributes = src_points.attributes(); VArraySpan<float3> positions = src_attributes.lookup_or_default<float3>( "position", ATTR_DOMAIN_POINT, float3(0)); const int src_size = positions.size(); @@ -41,8 +41,7 @@ PointCloud *point_merge_by_distance(const PointCloud &src_points, /* Create the new point cloud and add it to a temporary component for the attribute API. */ const int dst_size = src_size - duplicate_count; PointCloud *dst_pointcloud = BKE_pointcloud_new_nomain(dst_size); - bke::MutableAttributeAccessor dst_attributes = bke::pointcloud_attributes_for_write( - *dst_pointcloud); + bke::MutableAttributeAccessor dst_attributes = dst_pointcloud->attributes_for_write(); /* By default, every point is just "merged" with itself. Then fill in the results of the merge * finding, converting from indices into the selection to indices into the full input point diff --git a/source/blender/geometry/intern/realize_instances.cc b/source/blender/geometry/intern/realize_instances.cc index 4b3b184536b..99b6bb29051 100644 --- a/source/blender/geometry/intern/realize_instances.cc +++ b/source/blender/geometry/intern/realize_instances.cc @@ -9,11 +9,13 @@ #include "DNA_object_types.h" #include "DNA_pointcloud_types.h" +#include "BLI_devirtualize_parameters.hh" #include "BLI_noise.hh" #include "BLI_task.hh" #include "BKE_collection.h" #include "BKE_curves.hh" +#include "BKE_deform.h" #include "BKE_geometry_set_instances.hh" #include "BKE_material.h" #include "BKE_mesh.h" @@ -95,12 +97,18 @@ struct MeshElementStartIndices { struct MeshRealizeInfo { const Mesh *mesh = nullptr; + Span<MVert> verts; + Span<MEdge> edges; + Span<MPoly> polys; + Span<MLoop> loops; + /** Maps old material indices to new material indices. */ Array<int> material_index_map; /** Matches the order in #AllMeshesInfo.attributes. */ Array<std::optional<GVArraySpan>> attributes; /** Vertex ids stored on the mesh. If there are no ids, this #Span is empty. */ Span<int> stored_vertex_ids; + VArray<int> material_indices; }; struct RealizeMeshTask { @@ -181,6 +189,7 @@ struct AllMeshesInfo { /** Ordered materials on the output mesh. */ VectorSet<Material *> materials; bool create_id_attribute = false; + bool create_material_index_attribute = false; }; struct AllCurvesInfo { @@ -659,7 +668,7 @@ static AllPointCloudsInfo preprocess_pointclouds(const GeometrySet &geometry_set pointcloud_info.pointcloud = pointcloud; /* Access attributes. */ - bke::AttributeAccessor attributes = bke::pointcloud_attributes(*pointcloud); + bke::AttributeAccessor attributes = pointcloud->attributes(); pointcloud_info.attributes.reinitialize(info.attributes.size()); for (const int attribute_index : info.attributes.index_range()) { const AttributeIDRef &attribute_id = info.attributes.ids[attribute_index]; @@ -735,8 +744,7 @@ static void execute_realize_pointcloud_tasks(const RealizeInstancesOptions &opti PointCloudComponent &dst_component = r_realized_geometry.get_component_for_write<PointCloudComponent>(); dst_component.replace(dst_pointcloud); - bke::MutableAttributeAccessor dst_attributes = bke::pointcloud_attributes_for_write( - *dst_pointcloud); + bke::MutableAttributeAccessor dst_attributes = dst_pointcloud->attributes_for_write(); SpanAttributeWriter<float3> positions = dst_attributes.lookup_or_add_for_write_only_span<float3>( "position", ATTR_DOMAIN_POINT); @@ -774,9 +782,7 @@ static void execute_realize_pointcloud_tasks(const RealizeInstancesOptions &opti dst_attribute.finish(); } positions.finish(); - if (point_ids) { - point_ids.finish(); - } + point_ids.finish(); } /** \} */ @@ -786,7 +792,10 @@ static void execute_realize_pointcloud_tasks(const RealizeInstancesOptions &opti * \{ */ static OrderedAttributes gather_generic_mesh_attributes_to_propagate( - const GeometrySet &in_geometry_set, const RealizeInstancesOptions &options, bool &r_create_id) + const GeometrySet &in_geometry_set, + const RealizeInstancesOptions &options, + bool &r_create_id, + bool &r_create_material_index) { Vector<GeometryComponentType> src_component_types; src_component_types.append(GEO_COMPONENT_TYPE_MESH); @@ -799,10 +808,9 @@ static OrderedAttributes gather_generic_mesh_attributes_to_propagate( src_component_types, GEO_COMPONENT_TYPE_MESH, true, attributes_to_propagate); attributes_to_propagate.remove("position"); attributes_to_propagate.remove("normal"); - attributes_to_propagate.remove("material_index"); attributes_to_propagate.remove("shade_smooth"); - attributes_to_propagate.remove("crease"); r_create_id = attributes_to_propagate.pop_try("id").has_value(); + r_create_material_index = attributes_to_propagate.pop_try("material_index").has_value(); OrderedAttributes ordered_attributes; for (const auto item : attributes_to_propagate.items()) { ordered_attributes.ids.add_new(item.key); @@ -832,13 +840,19 @@ static AllMeshesInfo preprocess_meshes(const GeometrySet &geometry_set, { AllMeshesInfo info; info.attributes = gather_generic_mesh_attributes_to_propagate( - geometry_set, options, info.create_id_attribute); + geometry_set, options, info.create_id_attribute, info.create_material_index_attribute); gather_meshes_to_realize(geometry_set, info.order); for (const Mesh *mesh : info.order) { - for (const int slot_index : IndexRange(mesh->totcol)) { - Material *material = mesh->mat[slot_index]; - info.materials.add(material); + if (mesh->totcol == 0) { + /* Add an empty material slot for the default material. */ + info.materials.add(nullptr); + } + else { + for (const int slot_index : IndexRange(mesh->totcol)) { + Material *material = mesh->mat[slot_index]; + info.materials.add(material); + } } } info.realize_info.reinitialize(info.order.size()); @@ -846,17 +860,26 @@ static AllMeshesInfo preprocess_meshes(const GeometrySet &geometry_set, MeshRealizeInfo &mesh_info = info.realize_info[mesh_index]; const Mesh *mesh = info.order[mesh_index]; mesh_info.mesh = mesh; + mesh_info.verts = mesh->verts(); + mesh_info.edges = mesh->edges(); + mesh_info.polys = mesh->polys(); + mesh_info.loops = mesh->loops(); /* Create material index mapping. */ - mesh_info.material_index_map.reinitialize(mesh->totcol); - for (const int old_slot_index : IndexRange(mesh->totcol)) { - Material *material = mesh->mat[old_slot_index]; - const int new_slot_index = info.materials.index_of(material); - mesh_info.material_index_map[old_slot_index] = new_slot_index; + mesh_info.material_index_map.reinitialize(std::max<int>(mesh->totcol, 1)); + if (mesh->totcol == 0) { + mesh_info.material_index_map.first() = info.materials.index_of(nullptr); + } + else { + for (const int old_slot_index : IndexRange(mesh->totcol)) { + Material *material = mesh->mat[old_slot_index]; + const int new_slot_index = info.materials.index_of(material); + mesh_info.material_index_map[old_slot_index] = new_slot_index; + } } /* Access attributes. */ - bke::AttributeAccessor attributes = bke::mesh_attributes(*mesh); + bke::AttributeAccessor attributes = mesh->attributes(); mesh_info.attributes.reinitialize(info.attributes.size()); for (const int attribute_index : info.attributes.index_range()) { const AttributeIDRef &attribute_id = info.attributes.ids[attribute_index]; @@ -873,6 +896,8 @@ static AllMeshesInfo preprocess_meshes(const GeometrySet &geometry_set, mesh_info.stored_vertex_ids = ids_attribute.varray.get_internal_span().typed<int>(); } } + mesh_info.material_indices = attributes.lookup_or_default<int>( + "material_index", ATTR_DOMAIN_FACE, 0); } return info; } @@ -880,26 +905,33 @@ static AllMeshesInfo preprocess_meshes(const GeometrySet &geometry_set, static void execute_realize_mesh_task(const RealizeInstancesOptions &options, const RealizeMeshTask &task, const OrderedAttributes &ordered_attributes, - Mesh &dst_mesh, MutableSpan<GSpanAttributeWriter> dst_attribute_writers, - MutableSpan<int> all_dst_vertex_ids) + MutableSpan<MVert> all_dst_verts, + MutableSpan<MEdge> all_dst_edges, + MutableSpan<MPoly> all_dst_polys, + MutableSpan<MLoop> all_dst_loops, + MutableSpan<int> all_dst_vertex_ids, + MutableSpan<int> all_dst_material_indices) { const MeshRealizeInfo &mesh_info = *task.mesh_info; const Mesh &mesh = *mesh_info.mesh; - const Span<MVert> src_verts{mesh.mvert, mesh.totvert}; - const Span<MEdge> src_edges{mesh.medge, mesh.totedge}; - const Span<MLoop> src_loops{mesh.mloop, mesh.totloop}; - const Span<MPoly> src_polys{mesh.mpoly, mesh.totpoly}; + const Span<MVert> src_verts = mesh_info.verts; + const Span<MEdge> src_edges = mesh_info.edges; + const Span<MPoly> src_polys = mesh_info.polys; + const Span<MLoop> src_loops = mesh_info.loops; - MutableSpan<MVert> dst_verts{dst_mesh.mvert + task.start_indices.vertex, mesh.totvert}; - MutableSpan<MEdge> dst_edges{dst_mesh.medge + task.start_indices.edge, mesh.totedge}; - MutableSpan<MLoop> dst_loops{dst_mesh.mloop + task.start_indices.loop, mesh.totloop}; - MutableSpan<MPoly> dst_polys{dst_mesh.mpoly + task.start_indices.poly, mesh.totpoly}; + const IndexRange dst_vert_range(task.start_indices.vertex, src_verts.size()); + const IndexRange dst_edge_range(task.start_indices.edge, src_edges.size()); + const IndexRange dst_poly_range(task.start_indices.poly, src_polys.size()); + const IndexRange dst_loop_range(task.start_indices.loop, src_loops.size()); - const Span<int> material_index_map = mesh_info.material_index_map; + MutableSpan<MVert> dst_verts = all_dst_verts.slice(dst_vert_range); + MutableSpan<MEdge> dst_edges = all_dst_edges.slice(dst_edge_range); + MutableSpan<MPoly> dst_polys = all_dst_polys.slice(dst_poly_range); + MutableSpan<MLoop> dst_loops = all_dst_loops.slice(dst_loop_range); - threading::parallel_for(IndexRange(mesh.totvert), 1024, [&](const IndexRange vert_range) { + threading::parallel_for(src_verts.index_range(), 1024, [&](const IndexRange vert_range) { for (const int i : vert_range) { const MVert &src_vert = src_verts[i]; MVert &dst_vert = dst_verts[i]; @@ -907,7 +939,7 @@ static void execute_realize_mesh_task(const RealizeInstancesOptions &options, copy_v3_v3(dst_vert.co, task.transform * float3(src_vert.co)); } }); - threading::parallel_for(IndexRange(mesh.totedge), 1024, [&](const IndexRange edge_range) { + threading::parallel_for(src_edges.index_range(), 1024, [&](const IndexRange edge_range) { for (const int i : edge_range) { const MEdge &src_edge = src_edges[i]; MEdge &dst_edge = dst_edges[i]; @@ -916,7 +948,7 @@ static void execute_realize_mesh_task(const RealizeInstancesOptions &options, dst_edge.v2 += task.start_indices.vertex; } }); - threading::parallel_for(IndexRange(mesh.totloop), 1024, [&](const IndexRange loop_range) { + threading::parallel_for(src_loops.index_range(), 1024, [&](const IndexRange loop_range) { for (const int i : loop_range) { const MLoop &src_loop = src_loops[i]; MLoop &dst_loop = dst_loops[i]; @@ -925,21 +957,39 @@ static void execute_realize_mesh_task(const RealizeInstancesOptions &options, dst_loop.e += task.start_indices.edge; } }); - threading::parallel_for(IndexRange(mesh.totpoly), 1024, [&](const IndexRange poly_range) { + threading::parallel_for(src_polys.index_range(), 1024, [&](const IndexRange poly_range) { for (const int i : poly_range) { const MPoly &src_poly = src_polys[i]; MPoly &dst_poly = dst_polys[i]; dst_poly = src_poly; dst_poly.loopstart += task.start_indices.loop; - if (src_poly.mat_nr >= 0 && src_poly.mat_nr < mesh.totcol) { - dst_poly.mat_nr = material_index_map[src_poly.mat_nr]; + } + }); + if (!all_dst_material_indices.is_empty()) { + const Span<int> material_index_map = mesh_info.material_index_map; + MutableSpan<int> dst_material_indices = all_dst_material_indices.slice(dst_poly_range); + if (mesh.totcol == 0) { + /* The material index map contains the index of the null material in the result. */ + dst_material_indices.fill(material_index_map.first()); + } + else { + if (mesh_info.material_indices.is_single()) { + const int src_index = mesh_info.material_indices.get_internal_single(); + const bool valid = IndexRange(mesh.totcol).contains(src_index); + dst_material_indices.fill(valid ? material_index_map[src_index] : 0); } else { - /* The material index was invalid before. */ - dst_poly.mat_nr = 0; + VArraySpan<int> indices_span(mesh_info.material_indices); + threading::parallel_for(src_polys.index_range(), 1024, [&](const IndexRange poly_range) { + for (const int i : poly_range) { + const int src_index = indices_span[i]; + const bool valid = IndexRange(mesh.totcol).contains(src_index); + dst_material_indices[i] = valid ? material_index_map[src_index] : 0; + } + }); } } - }); + } if (!all_dst_vertex_ids.is_empty()) { create_result_ids(options, @@ -955,13 +1005,13 @@ static void execute_realize_mesh_task(const RealizeInstancesOptions &options, [&](const eAttrDomain domain) { switch (domain) { case ATTR_DOMAIN_POINT: - return IndexRange(task.start_indices.vertex, mesh.totvert); + return dst_vert_range; case ATTR_DOMAIN_EDGE: - return IndexRange(task.start_indices.edge, mesh.totedge); - case ATTR_DOMAIN_CORNER: - return IndexRange(task.start_indices.loop, mesh.totloop); + return dst_edge_range; case ATTR_DOMAIN_FACE: - return IndexRange(task.start_indices.poly, mesh.totpoly); + return dst_poly_range; + case ATTR_DOMAIN_CORNER: + return dst_loop_range; default: BLI_assert_unreachable(); return IndexRange(); @@ -991,12 +1041,19 @@ static void execute_realize_mesh_tasks(const RealizeInstancesOptions &options, Mesh *dst_mesh = BKE_mesh_new_nomain(tot_vertices, tot_edges, 0, tot_loops, tot_poly); MeshComponent &dst_component = r_realized_geometry.get_component_for_write<MeshComponent>(); dst_component.replace(dst_mesh); - bke::MutableAttributeAccessor dst_attributes = bke::mesh_attributes_for_write(*dst_mesh); + bke::MutableAttributeAccessor dst_attributes = dst_mesh->attributes_for_write(); + MutableSpan<MVert> dst_verts = dst_mesh->verts_for_write(); + MutableSpan<MEdge> dst_edges = dst_mesh->edges_for_write(); + MutableSpan<MPoly> dst_polys = dst_mesh->polys_for_write(); + MutableSpan<MLoop> dst_loops = dst_mesh->loops_for_write(); /* Copy settings from the first input geometry set with a mesh. */ const RealizeMeshTask &first_task = tasks.first(); const Mesh &first_mesh = *first_task.mesh_info->mesh; BKE_mesh_copy_parameters_for_eval(dst_mesh, &first_mesh); + /* The above line also copies vertex group names. We don't want that here because the new + * attributes are added explicitly below. */ + BLI_freelistN(&dst_mesh->vertex_group_names); /* Add materials. */ for (const int i : IndexRange(ordered_materials.size())) { @@ -1009,6 +1066,12 @@ static void execute_realize_mesh_tasks(const RealizeInstancesOptions &options, if (all_meshes_info.create_id_attribute) { vertex_ids = dst_attributes.lookup_or_add_for_write_only_span<int>("id", ATTR_DOMAIN_POINT); } + /* Prepare material indices. */ + SpanAttributeWriter<int> material_indices; + if (all_meshes_info.create_material_index_attribute) { + material_indices = dst_attributes.lookup_or_add_for_write_only_span<int>("material_index", + ATTR_DOMAIN_FACE); + } /* Prepare generic output attributes. */ Vector<GSpanAttributeWriter> dst_attribute_writers; @@ -1024,8 +1087,16 @@ static void execute_realize_mesh_tasks(const RealizeInstancesOptions &options, threading::parallel_for(tasks.index_range(), 100, [&](const IndexRange task_range) { for (const int task_index : task_range) { const RealizeMeshTask &task = tasks[task_index]; - execute_realize_mesh_task( - options, task, ordered_attributes, *dst_mesh, dst_attribute_writers, vertex_ids.span); + execute_realize_mesh_task(options, + task, + ordered_attributes, + dst_attribute_writers, + dst_verts, + dst_edges, + dst_polys, + dst_loops, + vertex_ids.span, + material_indices.span); } }); @@ -1033,9 +1104,8 @@ static void execute_realize_mesh_tasks(const RealizeInstancesOptions &options, for (GSpanAttributeWriter &dst_attribute : dst_attribute_writers) { dst_attribute.finish(); } - if (vertex_ids) { - vertex_ids.finish(); - } + vertex_ids.finish(); + material_indices.finish(); } /** \} */ @@ -1329,19 +1399,11 @@ static void execute_realize_curve_tasks(const RealizeInstancesOptions &options, for (GSpanAttributeWriter &dst_attribute : dst_attribute_writers) { dst_attribute.finish(); } - if (point_ids) { - point_ids.finish(); - } - if (radius) { - radius.finish(); - } - if (resolution) { - resolution.finish(); - } - if (all_curves_info.create_handle_postion_attributes) { - handle_left.finish(); - handle_right.finish(); - } + point_ids.finish(); + radius.finish(); + resolution.finish(); + handle_left.finish(); + handle_right.finish(); } /** \} */ diff --git a/source/blender/geometry/intern/resample_curves.cc b/source/blender/geometry/intern/resample_curves.cc index e252e28805e..a7f6ac16f8d 100644 --- a/source/blender/geometry/intern/resample_curves.cc +++ b/source/blender/geometry/intern/resample_curves.cc @@ -88,20 +88,20 @@ static bool interpolate_attribute_to_poly_curve(const bke::AttributeIDRef &attri * Retrieve spans from source and result attributes. */ static void retrieve_attribute_spans(const Span<bke::AttributeIDRef> ids, - const CurveComponent &src_component, - CurveComponent &dst_component, + const CurvesGeometry &src_curves, + CurvesGeometry &dst_curves, Vector<GSpan> &src, Vector<GMutableSpan> &dst, Vector<bke::GSpanAttributeWriter> &dst_attributes) { for (const int i : ids.index_range()) { - GVArray src_attribute = src_component.attributes()->lookup(ids[i], ATTR_DOMAIN_POINT); + GVArray src_attribute = src_curves.attributes().lookup(ids[i], ATTR_DOMAIN_POINT); BLI_assert(src_attribute); src.append(src_attribute.get_internal_span()); const eCustomDataType data_type = bke::cpp_type_to_custom_data_type(src_attribute.type()); bke::GSpanAttributeWriter dst_attribute = - dst_component.attributes_for_write()->lookup_or_add_for_write_only_span( + dst_curves.attributes_for_write().lookup_or_add_for_write_only_span( ids[i], ATTR_DOMAIN_POINT, data_type); dst.append(dst_attribute.span); dst_attributes.append(std::move(dst_attribute)); @@ -116,21 +116,25 @@ struct AttributesForInterpolation : NonCopyable, NonMovable { Vector<GSpan> src_no_interpolation; Vector<GMutableSpan> dst_no_interpolation; + + Span<float3> src_evaluated_tangents; + Span<float3> src_evaluated_normals; + MutableSpan<float3> dst_tangents; + MutableSpan<float3> dst_normals; }; /** * Gather a set of all generic attribute IDs to copy to the result curves. */ -static void gather_point_attributes_to_interpolate(const CurveComponent &src_component, - CurveComponent &dst_component, - AttributesForInterpolation &result) +static void gather_point_attributes_to_interpolate( + const CurvesGeometry &src_curves, + CurvesGeometry &dst_curves, + AttributesForInterpolation &result, + const ResampleCurvesOutputAttributeIDs &output_ids) { - bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap( - dst_component.get_for_write()->geometry); - VectorSet<bke::AttributeIDRef> ids; VectorSet<bke::AttributeIDRef> ids_no_interpolation; - src_component.attributes()->for_all( + src_curves.attributes().for_all( [&](const bke::AttributeIDRef &id, const bke::AttributeMetaData meta_data) { if (meta_data.domain != ATTR_DOMAIN_POINT) { return true; @@ -152,29 +156,89 @@ static void gather_point_attributes_to_interpolate(const CurveComponent &src_com ids.remove_contained("position"); retrieve_attribute_spans( - ids, src_component, dst_component, result.src, result.dst, result.dst_attributes); + ids, src_curves, dst_curves, result.src, result.dst, result.dst_attributes); /* Attributes that aren't interpolated like Bezier handles still have to be copied * to the result when there are any unselected curves of the corresponding type. */ retrieve_attribute_spans(ids_no_interpolation, - src_component, - dst_component, + src_curves, + dst_curves, result.src_no_interpolation, result.dst_no_interpolation, result.dst_attributes); + + bke::MutableAttributeAccessor dst_attributes = dst_curves.attributes_for_write(); + if (output_ids.tangent_id) { + result.src_evaluated_tangents = src_curves.evaluated_tangents(); + bke::GSpanAttributeWriter dst_attribute = dst_attributes.lookup_or_add_for_write_only_span( + output_ids.tangent_id, ATTR_DOMAIN_POINT, CD_PROP_FLOAT3); + result.dst_tangents = dst_attribute.span.typed<float3>(); + result.dst_attributes.append(std::move(dst_attribute)); + } + if (output_ids.normal_id) { + result.src_evaluated_normals = src_curves.evaluated_normals(); + bke::GSpanAttributeWriter dst_attribute = dst_attributes.lookup_or_add_for_write_only_span( + output_ids.normal_id, ATTR_DOMAIN_POINT, CD_PROP_FLOAT3); + result.dst_normals = dst_attribute.span.typed<float3>(); + result.dst_attributes.append(std::move(dst_attribute)); + } } -static Curves *resample_to_uniform(const CurveComponent &src_component, - const fn::Field<bool> &selection_field, - const fn::Field<int> &count_field) +static void copy_or_defaults_for_unselected_curves(const CurvesGeometry &src_curves, + const Span<IndexRange> unselected_ranges, + const AttributesForInterpolation &attributes, + CurvesGeometry &dst_curves) { - const bke::CurvesGeometry &src_curves = bke::CurvesGeometry::wrap( - src_component.get_for_read()->geometry); + bke::curves::copy_point_data(src_curves, + dst_curves, + unselected_ranges, + src_curves.positions(), + dst_curves.positions_for_write()); + for (const int i : attributes.src.index_range()) { + bke::curves::copy_point_data( + src_curves, dst_curves, unselected_ranges, attributes.src[i], attributes.dst[i]); + } + for (const int i : attributes.src_no_interpolation.index_range()) { + bke::curves::copy_point_data(src_curves, + dst_curves, + unselected_ranges, + attributes.src_no_interpolation[i], + attributes.dst_no_interpolation[i]); + } + + if (!attributes.dst_tangents.is_empty()) { + bke::curves::fill_points(dst_curves, unselected_ranges, float3(0), attributes.dst_tangents); + } + if (!attributes.dst_normals.is_empty()) { + bke::curves::fill_points(dst_curves, unselected_ranges, float3(0), attributes.dst_normals); + } +} + +static void normalize_span(MutableSpan<float3> data) +{ + for (const int i : data.index_range()) { + data[i] = math::normalize(data[i]); + } +} + +static void normalize_curve_point_data(const CurvesGeometry &curves, + const IndexMask curve_selection, + MutableSpan<float3> data) +{ + for (const int i_curve : curve_selection) { + normalize_span(data.slice(curves.points_for_curve(i_curve))); + } +} + +static CurvesGeometry resample_to_uniform(const CurvesGeometry &src_curves, + const fn::Field<bool> &selection_field, + const fn::Field<int> &count_field, + const ResampleCurvesOutputAttributeIDs &output_ids) +{ /* Create the new curves without any points and evaluate the final count directly * into the offsets array, in order to be accumulated into offsets later. */ - Curves *dst_curves_id = bke::curves_new_nomain(0, src_curves.curves_num()); - bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id->geometry); + CurvesGeometry dst_curves = CurvesGeometry(0, src_curves.curves_num()); /* Directly copy curve attributes, since they stay the same (except for curve types). */ CustomData_copy(&src_curves.curve_data, @@ -184,7 +248,7 @@ static Curves *resample_to_uniform(const CurveComponent &src_component, src_curves.curves_num()); MutableSpan<int> dst_offsets = dst_curves.offsets_for_write(); - bke::GeometryComponentFieldContext field_context{src_component, ATTR_DOMAIN_CURVE}; + bke::CurvesFieldContext field_context{src_curves, ATTR_DOMAIN_CURVE}; fn::FieldEvaluator evaluator{field_context, src_curves.curves_num()}; evaluator.set_selection(selection_field); evaluator.add_with_destination(count_field, dst_offsets); @@ -207,9 +271,7 @@ static Curves *resample_to_uniform(const CurveComponent &src_component, MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); AttributesForInterpolation attributes; - CurveComponent dst_component; - dst_component.replace(dst_curves_id, GeometryOwnershipType::Editable); - gather_point_attributes_to_interpolate(src_component, dst_component, attributes); + gather_point_attributes_to_interpolate(src_curves, dst_curves, attributes, output_ids); src_curves.ensure_evaluated_lengths(); @@ -281,14 +343,27 @@ static Curves *resample_to_uniform(const CurveComponent &src_component, }); } + auto interpolate_evaluated_data = [&](const Span<float3> src, MutableSpan<float3> dst) { + for (const int i_curve : sliced_selection) { + const IndexRange src_points = src_curves.evaluated_points_for_curve(i_curve); + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + length_parameterize::interpolate(src.slice(src_points), + sample_indices.as_span().slice(dst_points), + sample_factors.as_span().slice(dst_points), + dst.slice(dst_points)); + } + }; + /* Interpolate the evaluated positions to the resampled curves. */ - for (const int i_curve : sliced_selection) { - const IndexRange src_points = src_curves.evaluated_points_for_curve(i_curve); - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - length_parameterize::interpolate(evaluated_positions.slice(src_points), - sample_indices.as_span().slice(dst_points), - sample_factors.as_span().slice(dst_points), - dst_positions.slice(dst_points)); + interpolate_evaluated_data(evaluated_positions, dst_positions); + + if (!attributes.dst_tangents.is_empty()) { + interpolate_evaluated_data(attributes.src_evaluated_tangents, attributes.dst_tangents); + normalize_curve_point_data(dst_curves, sliced_selection, attributes.dst_tangents); + } + if (!attributes.dst_normals.is_empty()) { + interpolate_evaluated_data(attributes.src_evaluated_normals, attributes.dst_normals); + normalize_curve_point_data(dst_curves, sliced_selection, attributes.dst_normals); } /* Fill the default value for non-interpolating attributes that still must be copied. */ @@ -300,54 +375,40 @@ static Curves *resample_to_uniform(const CurveComponent &src_component, } }); - /* Any attribute data from unselected curve points can be directly copied. */ - for (const int i : attributes.src.index_range()) { - bke::curves::copy_point_data( - src_curves, dst_curves, unselected_ranges, attributes.src[i], attributes.dst[i]); - } - for (const int i : attributes.src_no_interpolation.index_range()) { - bke::curves::copy_point_data(src_curves, - dst_curves, - unselected_ranges, - attributes.src_no_interpolation[i], - attributes.dst_no_interpolation[i]); - } - - /* Copy positions for unselected curves. */ - Span<float3> src_positions = src_curves.positions(); - bke::curves::copy_point_data( - src_curves, dst_curves, unselected_ranges, src_positions, dst_positions); + copy_or_defaults_for_unselected_curves(src_curves, unselected_ranges, attributes, dst_curves); for (bke::GSpanAttributeWriter &attribute : attributes.dst_attributes) { attribute.finish(); } - return dst_curves_id; + return dst_curves; } -Curves *resample_to_count(const CurveComponent &src_component, - const fn::Field<bool> &selection_field, - const fn::Field<int> &count_field) +CurvesGeometry resample_to_count(const CurvesGeometry &src_curves, + const fn::Field<bool> &selection_field, + const fn::Field<int> &count_field, + const ResampleCurvesOutputAttributeIDs &output_ids) { - return resample_to_uniform(src_component, selection_field, get_count_input_max_one(count_field)); + return resample_to_uniform( + src_curves, selection_field, get_count_input_max_one(count_field), output_ids); } -Curves *resample_to_length(const CurveComponent &src_component, - const fn::Field<bool> &selection_field, - const fn::Field<float> &segment_length_field) +CurvesGeometry resample_to_length(const CurvesGeometry &src_curves, + const fn::Field<bool> &selection_field, + const fn::Field<float> &segment_length_field, + const ResampleCurvesOutputAttributeIDs &output_ids) { return resample_to_uniform( - src_component, selection_field, get_count_input_from_length(segment_length_field)); + src_curves, selection_field, get_count_input_from_length(segment_length_field), output_ids); } -Curves *resample_to_evaluated(const CurveComponent &src_component, - const fn::Field<bool> &selection_field) +CurvesGeometry resample_to_evaluated(const CurvesGeometry &src_curves, + const fn::Field<bool> &selection_field, + const ResampleCurvesOutputAttributeIDs &output_ids) { - const bke::CurvesGeometry &src_curves = bke::CurvesGeometry::wrap( - src_component.get_for_read()->geometry); src_curves.ensure_evaluated_offsets(); - bke::GeometryComponentFieldContext field_context{src_component, ATTR_DOMAIN_CURVE}; + bke::CurvesFieldContext field_context{src_curves, ATTR_DOMAIN_CURVE}; fn::FieldEvaluator evaluator{field_context, src_curves.curves_num()}; evaluator.set_selection(selection_field); evaluator.evaluate(); @@ -355,8 +416,7 @@ Curves *resample_to_evaluated(const CurveComponent &src_component, const Vector<IndexRange> unselected_ranges = selection.extract_ranges_invert( src_curves.curves_range(), nullptr); - Curves *dst_curves_id = bke::curves_new_nomain(0, src_curves.curves_num()); - bke::CurvesGeometry &dst_curves = bke::CurvesGeometry::wrap(dst_curves_id->geometry); + CurvesGeometry dst_curves(0, src_curves.curves_num()); /* Directly copy curve attributes, since they stay the same (except for curve types). */ CustomData_copy(&src_curves.curve_data, @@ -368,7 +428,7 @@ Curves *resample_to_evaluated(const CurveComponent &src_component, dst_curves.fill_curve_types(selection, CURVE_TYPE_POLY); MutableSpan<int> dst_offsets = dst_curves.offsets_for_write(); - src_curves.ensure_evaluated_offsets(); + src_curves.ensure_can_interpolate_to_evaluated(); threading::parallel_for(selection.index_range(), 4096, [&](IndexRange range) { for (const int i : selection.slice(range)) { dst_offsets[i] = src_curves.evaluated_points_for_curve(i).size(); @@ -380,13 +440,11 @@ Curves *resample_to_evaluated(const CurveComponent &src_component, dst_curves.resize(dst_offsets.last(), dst_curves.curves_num()); /* Create the correct number of uniform-length samples for every selected curve. */ - Span<float3> evaluated_positions = src_curves.evaluated_positions(); + const Span<float3> evaluated_positions = src_curves.evaluated_positions(); MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); AttributesForInterpolation attributes; - CurveComponent dst_component; - dst_component.replace(dst_curves_id, GeometryOwnershipType::Editable); - gather_point_attributes_to_interpolate(src_component, dst_component, attributes); + gather_point_attributes_to_interpolate(src_curves, dst_curves, attributes, output_ids); threading::parallel_for(selection.index_range(), 512, [&](IndexRange selection_range) { const IndexMask sliced_selection = selection.slice(selection_range); @@ -407,11 +465,24 @@ Curves *resample_to_evaluated(const CurveComponent &src_component, }); } + auto copy_evaluated_data = [&](const Span<float3> src, MutableSpan<float3> dst) { + for (const int i_curve : sliced_selection) { + const IndexRange src_points = src_curves.evaluated_points_for_curve(i_curve); + const IndexRange dst_points = dst_curves.points_for_curve(i_curve); + dst.slice(dst_points).copy_from(src.slice(src_points)); + } + }; + /* Copy the evaluated positions to the selected curves. */ - for (const int i_curve : sliced_selection) { - const IndexRange src_points = src_curves.evaluated_points_for_curve(i_curve); - const IndexRange dst_points = dst_curves.points_for_curve(i_curve); - dst_positions.slice(dst_points).copy_from(evaluated_positions.slice(src_points)); + copy_evaluated_data(evaluated_positions, dst_positions); + + if (!attributes.dst_tangents.is_empty()) { + copy_evaluated_data(attributes.src_evaluated_tangents, attributes.dst_tangents); + normalize_curve_point_data(dst_curves, sliced_selection, attributes.dst_tangents); + } + if (!attributes.dst_normals.is_empty()) { + copy_evaluated_data(attributes.src_evaluated_normals, attributes.dst_normals); + normalize_curve_point_data(dst_curves, sliced_selection, attributes.dst_normals); } /* Fill the default value for non-interpolating attributes that still must be copied. */ @@ -423,29 +494,13 @@ Curves *resample_to_evaluated(const CurveComponent &src_component, } }); - /* Any attribute data from unselected curve points can be directly copied. */ - for (const int i : attributes.src.index_range()) { - bke::curves::copy_point_data( - src_curves, dst_curves, unselected_ranges, attributes.src[i], attributes.dst[i]); - } - for (const int i : attributes.src_no_interpolation.index_range()) { - bke::curves::copy_point_data(src_curves, - dst_curves, - unselected_ranges, - attributes.src_no_interpolation[i], - attributes.dst_no_interpolation[i]); - } - - /* Copy positions for unselected curves. */ - Span<float3> src_positions = src_curves.positions(); - bke::curves::copy_point_data( - src_curves, dst_curves, unselected_ranges, src_positions, dst_positions); + copy_or_defaults_for_unselected_curves(src_curves, unselected_ranges, attributes, dst_curves); for (bke::GSpanAttributeWriter &attribute : attributes.dst_attributes) { attribute.finish(); } - return dst_curves_id; + return dst_curves; } } // namespace blender::geometry diff --git a/source/blender/geometry/intern/reverse_uv_sampler.cc b/source/blender/geometry/intern/reverse_uv_sampler.cc index 39fec40333c..f66e4a3ac2e 100644 --- a/source/blender/geometry/intern/reverse_uv_sampler.cc +++ b/source/blender/geometry/intern/reverse_uv_sampler.cc @@ -50,6 +50,11 @@ ReverseUVSampler::Result ReverseUVSampler::sample(const float2 &query_uv) const float3 best_bary_weights; const MLoopTri *best_looptri; + /* The distance to an edge that is allowed to be inside or outside the triangle. Without this, + * the lookup can fail for floating point accuracy reasons when the uv is almost exact on an + * edge. */ + const float edge_epsilon = 0.00001f; + for (const int looptri_index : looptri_indices) { const MLoopTri &looptri = looptris_[looptri_index]; const float2 &uv_0 = uv_map_[looptri.tri[0]]; @@ -68,8 +73,12 @@ ReverseUVSampler::Result ReverseUVSampler::sample(const float2 &query_uv) const const float dist = MAX3(x_dist, y_dist, z_dist); if (dist <= 0.0f && best_dist <= 0.0f) { - /* The uv sample is in multiple triangles. */ - return Result{ResultType::Multiple}; + const float worse_dist = std::max(dist, best_dist); + /* Allow ignoring multiple triangle intersections if the uv is almost exactly on an edge. */ + if (worse_dist < -edge_epsilon) { + /* The uv sample is in multiple triangles. */ + return Result{ResultType::Multiple}; + } } if (dist < best_dist) { @@ -79,8 +88,9 @@ ReverseUVSampler::Result ReverseUVSampler::sample(const float2 &query_uv) const } } - /* Allow for a small epsilon in case the uv is on th edge. */ - if (best_dist < 0.00001f) { + /* Allow using the closest (but not intersecting) triangle if the uv is almost exactly on an + * edge. */ + if (best_dist < edge_epsilon) { return Result{ResultType::Ok, best_looptri, math::clamp(best_bary_weights, 0.0f, 1.0f)}; } diff --git a/source/blender/geometry/intern/trim_curves.cc b/source/blender/geometry/intern/trim_curves.cc new file mode 100644 index 00000000000..cd93f295685 --- /dev/null +++ b/source/blender/geometry/intern/trim_curves.cc @@ -0,0 +1,1299 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +/** \file + * \ingroup bke + */ + +#include "BLI_array_utils.hh" +#include "BLI_length_parameterize.hh" + +#include "BKE_attribute.hh" +#include "BKE_attribute_math.hh" +#include "BKE_curves.hh" +#include "BKE_curves_utils.hh" +#include "BKE_geometry_set.hh" + +#include "GEO_trim_curves.hh" + +namespace blender::geometry { + +/* -------------------------------------------------------------------- */ +/** \name Curve Enums + * \{ */ + +#define CURVE_TYPE_AS_MASK(curve_type) ((CurveTypeMask)((1 << (int)(curve_type)))) + +typedef enum CurveTypeMask { + CURVE_TYPE_MASK_CATMULL_ROM = (1 << 0), + CURVE_TYPE_MASK_POLY = (1 << 1), + CURVE_TYPE_MASK_BEZIER = (1 << 2), + CURVE_TYPE_MASK_NURBS = (1 << 3), + CURVE_TYPE_MASK_ALL = (1 << 4) - 1 +} CurveTypeMask; + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name #IndexRangeCyclic Utilities + * \{ */ + +/** + * Create a cyclical iterator for all control points within the interval [start_point, end_point] + * including any control point at the start or end point. + * + * \param start_point: Point on the curve that define the starting point of the interval. + * \param end_point: Point on the curve that define the end point of the interval (included). + * \param points: #IndexRange for the curve points. + */ +static bke::curves::IndexRangeCyclic get_range_between_endpoints( + const bke::curves::CurvePoint start_point, + const bke::curves::CurvePoint end_point, + const IndexRange points) +{ + const int64_t start_index = start_point.parameter == 0.0 ? start_point.index : + start_point.next_index; + int64_t end_index = end_point.parameter == 0.0 ? end_point.index : end_point.next_index; + int64_t cycles; + + if (end_point.is_controlpoint()) { + ++end_index; + if (end_index > points.last()) { + end_index = points.one_after_last(); + } + /* end_point < start_point but parameter is irrelevant (end_point is controlpoint), and loop + * when equal due to increment. */ + cycles = end_index <= start_index; + } + else { + cycles = end_point < start_point || end_index < start_index; + } + return bke::curves::IndexRangeCyclic(start_index, end_index, points, cycles); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Lookup Curve Points + * \{ */ + +/** + * Find the point on the curve defined by the distance along the curve. Assumes curve resolution is + * constant for all curve segments and evaluated curve points are uniformly spaced between the + * segment endpoints in relation to the curve parameter. + * + * \param lengths: Accumulated length for the evaluated curve. + * \param sample_length: Distance along the curve to determine the #CurvePoint for. + * \param cyclic: If curve is cyclic. + * \param resolution: Curve resolution (number of evaluated points per segment). + * \param num_curve_points: Total number of control points in the curve. + * \return: Point on the piecewise segment matching the given distance. + */ +static bke::curves::CurvePoint lookup_curve_point(const Span<float> lengths, + const float sample_length, + const bool cyclic, + const int resolution, + const int num_curve_points) +{ + BLI_assert(!cyclic || lengths.size() / resolution >= 2); + const int last_index = num_curve_points - 1; + if (sample_length <= 0.0f) { + return {{0, 1}, 0.0f}; + } + if (sample_length >= lengths.last()) { + return cyclic ? bke::curves::CurvePoint{{last_index, 0}, 1.0} : + bke::curves::CurvePoint{{last_index - 1, last_index}, 1.0}; + } + int eval_index; + float eval_factor; + length_parameterize::sample_at_length(lengths, sample_length, eval_index, eval_factor); + + const int index = eval_index / resolution; + const int next_index = (index == last_index) ? 0 : index + 1; + const float parameter = (eval_factor + eval_index) / resolution - index; + + return bke::curves::CurvePoint{{index, next_index}, parameter}; +} + +/** + * Find the point on the 'evaluated' polygonal curve. + */ +static bke::curves::CurvePoint lookup_evaluated_point(const Span<float> lengths, + const float sample_length, + const bool cyclic, + const int evaluated_size) +{ + const int last_index = evaluated_size - 1; + if (sample_length <= 0.0f) { + return {{0, 1}, 0.0f}; + } + if (sample_length >= lengths.last()) { + return cyclic ? bke::curves::CurvePoint{{last_index, 0}, 1.0} : + bke::curves::CurvePoint{{last_index - 1, last_index}, 1.0}; + } + + int eval_index; + float eval_factor; + length_parameterize::sample_at_length(lengths, sample_length, eval_index, eval_factor); + + const int next_eval_index = (eval_index == last_index) ? 0 : eval_index + 1; + return bke::curves::CurvePoint{{eval_index, next_eval_index}, eval_factor}; +} + +/** + * Find the point on a Bezier curve using the 'bezier_offsets' cache. + */ +static bke::curves::CurvePoint lookup_bezier_point(const Span<int> bezier_offsets, + const Span<float> lengths, + const float sample_length, + const bool cyclic, + const int num_curve_points) +{ + const int last_index = num_curve_points - 1; + if (sample_length <= 0.0f) { + return {{0, 1}, 0.0f}; + } + if (sample_length >= lengths.last()) { + return cyclic ? bke::curves::CurvePoint{{last_index, 0}, 1.0} : + bke::curves::CurvePoint{{last_index - 1, last_index}, 1.0}; + } + int eval_index; + float eval_factor; + length_parameterize::sample_at_length(lengths, sample_length, eval_index, eval_factor); + + /* Find the segment index from the offset mapping. */ + const int *offset = std::upper_bound(bezier_offsets.begin(), bezier_offsets.end(), eval_index); + const int left = offset - bezier_offsets.begin(); + const int right = left == last_index ? 0 : left + 1; + + const int prev_offset = left == 0 ? 0 : bezier_offsets[(int64_t)left - 1]; + const float offset_in_segment = eval_factor + eval_index - prev_offset; + const int segment_resolution = bezier_offsets[left] - prev_offset; + const float parameter = std::clamp(offset_in_segment / segment_resolution, 0.0f, 1.0f); + + return {{left, right}, parameter}; +} + +Array<bke::curves::CurvePoint, 12> lookup_curve_points(const bke::CurvesGeometry &curves, + const Span<float> lengths, + const Span<int64_t> curve_indices, + const bool normalized_factors) +{ + BLI_assert(lengths.size() == curve_indices.size()); + BLI_assert(*std::max_element(curve_indices.begin(), curve_indices.end()) < curves.curves_num()); + + const VArray<bool> cyclic = curves.cyclic(); + const VArray<int> resolution = curves.resolution(); + const VArray<int8_t> curve_types = curves.curve_types(); + + /* Compute curve lengths! */ + curves.ensure_evaluated_lengths(); + curves.ensure_evaluated_offsets(); + + /* Find the curve points referenced by the input! */ + Array<bke::curves::CurvePoint, 12> lookups(curve_indices.size()); + threading::parallel_for(curve_indices.index_range(), 128, [&](const IndexRange range) { + for (const int64_t lookup_index : range) { + const int64_t curve_i = curve_indices[lookup_index]; + + const int point_count = curves.points_num_for_curve(curve_i); + if (curve_i < 0 || point_count == 1) { + lookups[lookup_index] = {{0, 0}, 0.0f}; + continue; + } + + const Span<float> accumulated_lengths = curves.evaluated_lengths_for_curve(curve_i, + cyclic[curve_i]); + BLI_assert(accumulated_lengths.size() > 0); + + const float sample_length = normalized_factors ? + lengths[lookup_index] * accumulated_lengths.last() : + lengths[lookup_index]; + + const CurveType curve_type = (CurveType)curve_types[curve_i]; + + switch (curve_type) { + case CURVE_TYPE_BEZIER: { + if (bke::curves::bezier::has_vector_handles( + point_count, + curves.evaluated_points_for_curve(curve_i).size(), + cyclic[curve_i], + resolution[curve_i])) { + const Span<int> bezier_offsets = curves.bezier_evaluated_offsets_for_curve(curve_i); + lookups[lookup_index] = lookup_bezier_point( + bezier_offsets, accumulated_lengths, sample_length, cyclic[curve_i], point_count); + } + else { + lookups[lookup_index] = lookup_curve_point(accumulated_lengths, + sample_length, + cyclic[curve_i], + resolution[curve_i], + point_count); + } + break; + } + case CURVE_TYPE_CATMULL_ROM: { + lookups[lookup_index] = lookup_curve_point(accumulated_lengths, + sample_length, + cyclic[curve_i], + resolution[curve_i], + point_count); + break; + } + case CURVE_TYPE_NURBS: + case CURVE_TYPE_POLY: + default: { + /* Handle general case as an "evaluated" or polygonal curve. */ + BLI_assert(resolution[curve_i] > 0); + lookups[lookup_index] = lookup_evaluated_point( + accumulated_lengths, + sample_length, + cyclic[curve_i], + curves.evaluated_points_for_curve(curve_i).size()); + break; + } + } + } + }); + return lookups; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Transfer Curve Domain + * \{ */ + +/** + * Determine curve type(s) for the copied curves given the supported set of types and knot modes. + * If a curve type is not supported the default type is set. + */ +static void determine_copyable_curve_types(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const IndexMask selection_inverse, + const CurveTypeMask supported_curve_type_mask, + const int8_t default_curve_type = (int8_t) + CURVE_TYPE_POLY) +{ + const VArray<int8_t> src_curve_types = src_curves.curve_types(); + const VArray<int8_t> src_knot_modes = src_curves.nurbs_knots_modes(); + MutableSpan<int8_t> dst_curve_types = dst_curves.curve_types_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange selection_range) { + for (const int64_t curve_i : selection.slice(selection_range)) { + if (supported_curve_type_mask & CURVE_TYPE_AS_MASK(src_curve_types[curve_i])) { + dst_curve_types[curve_i] = src_curve_types[curve_i]; + } + else { + dst_curve_types[curve_i] = default_curve_type; + } + } + }); + + array_utils::copy(src_curve_types, selection_inverse, dst_curve_types); +} + +/** + * Determine if a curve is treated as an evaluated curve. Curves which inherently do not support + * trimming are discretized (e.g. NURBS). + */ +static bool copy_as_evaluated_curve(const int8_t src_type, const int8_t dst_type) +{ + return src_type != CURVE_TYPE_POLY && dst_type == CURVE_TYPE_POLY; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Specialized Curve Constructors + * \{ */ + +static void compute_trim_result_offsets(const bke::CurvesGeometry &src_curves, + const IndexMask selection, + const IndexMask inverse_selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + const VArray<int8_t> dst_curve_types, + MutableSpan<int> dst_curve_offsets, + Vector<int64_t> &r_curve_indices, + Vector<int64_t> &r_point_curve_indices) +{ + BLI_assert(r_curve_indices.size() == 0); + BLI_assert(r_point_curve_indices.size() == 0); + const VArray<bool> cyclic = src_curves.cyclic(); + const VArray<int8_t> curve_types = src_curves.curve_types(); + r_curve_indices.reserve(selection.size()); + + for (const int64_t curve_i : selection) { + + int64_t src_point_count; + + if (copy_as_evaluated_curve(curve_types[curve_i], dst_curve_types[curve_i])) { + src_point_count = src_curves.evaluated_points_for_curve(curve_i).size(); + } + else { + src_point_count = (int64_t)src_curves.points_num_for_curve(curve_i); + } + BLI_assert(src_point_count > 0); + + if (start_points[curve_i] == end_points[curve_i]) { + dst_curve_offsets[curve_i] = 1; + r_point_curve_indices.append(curve_i); + } + else { + const bke::curves::IndexRangeCyclic point_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_point_count}); + const int count = point_range.size() + !start_points[curve_i].is_controlpoint() + + !end_points[curve_i].is_controlpoint(); + dst_curve_offsets[curve_i] = count; + r_curve_indices.append(curve_i); + } + BLI_assert(dst_curve_offsets[curve_i] > 0); + } + threading::parallel_for( + inverse_selection.index_range(), 4096, [&](const IndexRange selection_range) { + for (const int64_t curve_i : inverse_selection.slice(selection_range)) { + dst_curve_offsets[curve_i] = src_curves.points_num_for_curve(curve_i); + } + }); + bke::curves::accumulate_counts_to_offsets(dst_curve_offsets); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Utility Functions + * \{ */ + +static void fill_bezier_data(bke::CurvesGeometry &dst_curves, const IndexMask selection) +{ + if (dst_curves.has_curve_with_type(CURVE_TYPE_BEZIER)) { + MutableSpan<float3> handle_positions_left = dst_curves.handle_positions_left_for_write(); + MutableSpan<float3> handle_positions_right = dst_curves.handle_positions_right_for_write(); + MutableSpan<int8_t> handle_types_left = dst_curves.handle_types_left_for_write(); + MutableSpan<int8_t> handle_types_right = dst_curves.handle_types_right_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange points = dst_curves.points_for_curve(curve_i); + handle_types_right.slice(points).fill((int8_t)BEZIER_HANDLE_FREE); + handle_types_left.slice(points).fill((int8_t)BEZIER_HANDLE_FREE); + handle_positions_left.slice(points).fill({0.0f, 0.0f, 0.0f}); + handle_positions_right.slice(points).fill({0.0f, 0.0f, 0.0f}); + } + }); + } +} +static void fill_nurbs_data(bke::CurvesGeometry &dst_curves, const IndexMask selection) +{ + if (dst_curves.has_curve_with_type(CURVE_TYPE_NURBS)) { + bke::curves::fill_points(dst_curves, selection, 0.0f, dst_curves.nurbs_weights_for_write()); + } +} + +template<typename T> +static int64_t copy_point_data_between_endpoints(const Span<T> src_data, + MutableSpan<T> dst_data, + const bke::curves::IndexRangeCyclic src_range, + const int64_t src_index, + int64_t dst_index) +{ + int64_t increment; + if (src_range.cycles()) { + increment = src_range.size_before_loop(); + dst_data.slice(dst_index, increment).copy_from(src_data.slice(src_index, increment)); + dst_index += increment; + + increment = src_range.size_after_loop(); + dst_data.slice(dst_index, increment) + .copy_from(src_data.slice(src_range.curve_range().first(), increment)); + dst_index += increment; + } + else { + increment = src_range.one_after_last() - src_range.first(); + dst_data.slice(dst_index, increment).copy_from(src_data.slice(src_index, increment)); + dst_index += increment; + } + return dst_index; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Sampling Utilities + * \{ */ + +template<typename T> +static T interpolate_catmull_rom(const Span<T> src_data, + const bke::curves::CurvePoint insertion_point, + const bool src_cyclic) +{ + BLI_assert(insertion_point.index >= 0 && insertion_point.next_index < src_data.size()); + int i0; + if (insertion_point.index == 0) { + i0 = src_cyclic ? src_data.size() - 1 : insertion_point.index; + } + else { + i0 = insertion_point.index - 1; + } + int i3 = insertion_point.next_index + 1; + if (i3 == src_data.size()) { + i3 = src_cyclic ? 0 : insertion_point.next_index; + } + return bke::curves::catmull_rom::interpolate<T>(src_data[i0], + src_data[insertion_point.index], + src_data[insertion_point.next_index], + src_data[i3], + insertion_point.parameter); +} + +static bke::curves::bezier::Insertion knot_insert_bezier( + const Span<float3> positions, + const Span<float3> handles_left, + const Span<float3> handles_right, + const bke::curves::CurvePoint insertion_point) +{ + BLI_assert( + insertion_point.index + 1 == insertion_point.next_index || + (insertion_point.next_index >= 0 && insertion_point.next_index < insertion_point.index)); + return bke::curves::bezier::insert(positions[insertion_point.index], + handles_right[insertion_point.index], + handles_left[insertion_point.next_index], + positions[insertion_point.next_index], + insertion_point.parameter); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Sample Single Point + * \{ */ + +template<typename T> +static void sample_linear(const Span<T> src_data, + MutableSpan<T> dst_data, + const IndexRange dst_range, + const bke::curves::CurvePoint sample_point) +{ + BLI_assert(dst_range.size() == 1); + if (sample_point.is_controlpoint()) { + /* Resolves cases where the source curve consist of a single control point. */ + const int index = sample_point.parameter == 1.0 ? sample_point.next_index : sample_point.index; + dst_data[dst_range.first()] = src_data[index]; + } + else { + dst_data[dst_range.first()] = attribute_math::mix2( + sample_point.parameter, src_data[sample_point.index], src_data[sample_point.next_index]); + } +} + +template<typename T> +static void sample_catmull_rom(const Span<T> src_data, + MutableSpan<T> dst_data, + const IndexRange dst_range, + const bke::curves::CurvePoint sample_point, + const bool src_cyclic) +{ + BLI_assert(dst_range.size() == 1); + if (sample_point.is_controlpoint()) { + /* Resolves cases where the source curve consist of a single control point. */ + const int index = sample_point.parameter == 1.0 ? sample_point.next_index : sample_point.index; + dst_data[dst_range.first()] = src_data[index]; + } + else { + dst_data[dst_range.first()] = interpolate_catmull_rom(src_data, sample_point, src_cyclic); + } +} + +static void sample_bezier(const Span<float3> src_positions, + const Span<float3> src_handles_l, + const Span<float3> src_handles_r, + const Span<int8_t> src_types_l, + const Span<int8_t> src_types_r, + MutableSpan<float3> dst_positions, + MutableSpan<float3> dst_handles_l, + MutableSpan<float3> dst_handles_r, + MutableSpan<int8_t> dst_types_l, + MutableSpan<int8_t> dst_types_r, + const IndexRange dst_range, + const bke::curves::CurvePoint sample_point) +{ + BLI_assert(dst_range.size() == 1); + if (sample_point.is_controlpoint()) { + /* Resolves cases where the source curve consist of a single control point. */ + const int index = sample_point.parameter == 1.0 ? sample_point.next_index : sample_point.index; + dst_positions[dst_range.first()] = src_positions[index]; + dst_handles_l[dst_range.first()] = src_handles_l[index]; + dst_handles_r[dst_range.first()] = src_handles_r[index]; + dst_types_l[dst_range.first()] = src_types_l[index]; + dst_types_r[dst_range.first()] = src_types_r[index]; + } + else { + bke::curves::bezier::Insertion insertion_point = knot_insert_bezier( + src_positions, src_handles_l, src_handles_r, sample_point); + dst_positions[dst_range.first()] = insertion_point.position; + dst_handles_l[dst_range.first()] = insertion_point.left_handle; + dst_handles_r[dst_range.first()] = insertion_point.right_handle; + dst_types_l[dst_range.first()] = BEZIER_HANDLE_FREE; + dst_types_r[dst_range.first()] = BEZIER_HANDLE_FREE; + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Sample Curve Interval (Trim) + * \{ */ + +/** + * Sample source curve data in the interval defined by the points [start_point, end_point]. + * Uses linear interpolation to compute the endpoints. + * + * \tparam include_start_point If False, the 'start_point' point sample will not be copied + * and not accounted for in the destination range. + * \param src_data: Source to sample from. + * \param dst_data: Destination to write samples to. + * \param src_range: Interval within [start_point, end_point] to copy from the source point domain. + * \param dst_range: Interval to copy point data to in the destination buffer. + * \param start_point: Point on the source curve to start sampling from. + * \param end_point: Last point to sample in the source curve. + */ +template<typename T, bool include_start_point = true> +static void sample_interval_linear(const Span<T> src_data, + MutableSpan<T> dst_data, + const bke::curves::IndexRangeCyclic src_range, + const IndexRange dst_range, + const bke::curves::CurvePoint start_point, + const bke::curves::CurvePoint end_point) +{ + int64_t src_index = src_range.first(); + int64_t dst_index = dst_range.first(); + + if (start_point.is_controlpoint()) { + /* 'start_point' is included in the copy iteration. */ + if constexpr (!include_start_point) { + /* Skip first. */ + ++src_index; + } + } + else if constexpr (!include_start_point) { + /* Do nothing (excluded). */ + } + else { + /* General case, sample 'start_point' */ + dst_data[dst_index] = attribute_math::mix2( + start_point.parameter, src_data[start_point.index], src_data[start_point.next_index]); + ++dst_index; + } + + dst_index = copy_point_data_between_endpoints( + src_data, dst_data, src_range, src_index, dst_index); + + /* Handle last case */ + if (end_point.is_controlpoint()) { + /* 'end_point' is included in the copy iteration. */ + } + else { + dst_data[dst_index] = attribute_math::mix2( + end_point.parameter, src_data[end_point.index], src_data[end_point.next_index]); +#ifdef DEBUG + ++dst_index; +#endif + } + BLI_assert(dst_index == dst_range.one_after_last()); +} + +template<typename T, bool include_start_point = true> +static void sample_interval_catmull_rom(const Span<T> src_data, + MutableSpan<T> dst_data, + const bke::curves::IndexRangeCyclic src_range, + const IndexRange dst_range, + const bke::curves::CurvePoint start_point, + const bke::curves::CurvePoint end_point, + const bool src_cyclic) +{ + int64_t src_index = src_range.first(); + int64_t dst_index = dst_range.first(); + + if (start_point.is_controlpoint()) { + /* 'start_point' is included in the copy iteration. */ + if constexpr (!include_start_point) { + /* Skip first. */ + ++src_index; + } + } + else if constexpr (!include_start_point) { + /* Do nothing (excluded). */ + } + else { + /* General case, sample 'start_point' */ + dst_data[dst_index] = interpolate_catmull_rom(src_data, start_point, src_cyclic); + ++dst_index; + } + + dst_index = copy_point_data_between_endpoints( + src_data, dst_data, src_range, src_index, dst_index); + + /* Handle last case */ + if (end_point.is_controlpoint()) { + /* 'end_point' is included in the copy iteration. */ + } + else { + dst_data[dst_index] = interpolate_catmull_rom(src_data, end_point, src_cyclic); +#ifdef DEBUG + ++dst_index; +#endif + } + BLI_assert(dst_index == dst_range.one_after_last()); +} + +template<bool include_start_point = true> +static void sample_interval_bezier(const Span<float3> src_positions, + const Span<float3> src_handles_l, + const Span<float3> src_handles_r, + const Span<int8_t> src_types_l, + const Span<int8_t> src_types_r, + MutableSpan<float3> dst_positions, + MutableSpan<float3> dst_handles_l, + MutableSpan<float3> dst_handles_r, + MutableSpan<int8_t> dst_types_l, + MutableSpan<int8_t> dst_types_r, + const bke::curves::IndexRangeCyclic src_range, + const IndexRange dst_range, + const bke::curves::CurvePoint start_point, + const bke::curves::CurvePoint end_point) +{ + bke::curves::bezier::Insertion start_point_insert; + int64_t src_index = src_range.first(); + int64_t dst_index = dst_range.first(); + + bool start_point_trimmed = false; + if (start_point.is_controlpoint()) { + /* The 'start_point' control point is included in the copy iteration. */ + if constexpr (!include_start_point) { + ++src_index; /* Skip first! */ + } + } + else if constexpr (!include_start_point) { + /* Do nothing, 'start_point' is excluded. */ + } + else { + /* General case, sample 'start_point'. */ + start_point_insert = knot_insert_bezier( + src_positions, src_handles_l, src_handles_r, start_point); + dst_positions[dst_range.first()] = start_point_insert.position; + dst_handles_l[dst_range.first()] = start_point_insert.left_handle; + dst_handles_r[dst_range.first()] = start_point_insert.right_handle; + dst_types_l[dst_range.first()] = src_types_l[start_point.index]; + dst_types_r[dst_range.first()] = src_types_r[start_point.index]; + + start_point_trimmed = true; + ++dst_index; + } + + /* Copy point data between the 'start_point' and 'end_point'. */ + int64_t increment = src_range.cycles() ? src_range.size_before_loop() : + src_range.one_after_last() - src_range.first(); + + const IndexRange dst_range_to_end(dst_index, increment); + const IndexRange src_range_to_end(src_index, increment); + dst_positions.slice(dst_range_to_end).copy_from(src_positions.slice(src_range_to_end)); + dst_handles_l.slice(dst_range_to_end).copy_from(src_handles_l.slice(src_range_to_end)); + dst_handles_r.slice(dst_range_to_end).copy_from(src_handles_r.slice(src_range_to_end)); + dst_types_l.slice(dst_range_to_end).copy_from(src_types_l.slice(src_range_to_end)); + dst_types_r.slice(dst_range_to_end).copy_from(src_types_r.slice(src_range_to_end)); + dst_index += increment; + + increment = src_range.size_after_loop(); + if (src_range.cycles() && increment > 0) { + const IndexRange dst_range_looped(dst_index, increment); + const IndexRange src_range_looped(src_range.curve_range().first(), increment); + dst_positions.slice(dst_range_looped).copy_from(src_positions.slice(src_range_looped)); + dst_handles_l.slice(dst_range_looped).copy_from(src_handles_l.slice(src_range_looped)); + dst_handles_r.slice(dst_range_looped).copy_from(src_handles_r.slice(src_range_looped)); + dst_types_l.slice(dst_range_looped).copy_from(src_types_l.slice(src_range_looped)); + dst_types_r.slice(dst_range_looped).copy_from(src_types_r.slice(src_range_looped)); + dst_index += increment; + } + + if (start_point_trimmed) { + dst_handles_l[dst_range.first() + 1] = start_point_insert.handle_next; + /* No need to set handle type (remains the same)! */ + } + + /* Handle 'end_point' */ + bke::curves::bezier::Insertion end_point_insert; + if (end_point.is_controlpoint()) { + /* Do nothing, the 'end_point' control point is included in the copy iteration. */ + } + else { + /* Trimmed in both ends within the same (and only) segment! Ensure both end points is not a + * loop. */ + if (start_point_trimmed && start_point.index == end_point.index && + start_point.parameter <= end_point.parameter) { + + /* Copy following segment control point. */ + dst_positions[dst_index] = src_positions[end_point.next_index]; + dst_handles_r[dst_index] = src_handles_r[end_point.next_index]; + + /* Compute interpolation in the result curve. */ + const float parameter = (end_point.parameter - start_point.parameter) / + (1.0f - start_point.parameter); + end_point_insert = knot_insert_bezier( + dst_positions, + dst_handles_l, + dst_handles_r, + {{(int)dst_range.first(), (int)(dst_range.first() + 1)}, parameter}); + } + else { + /* General case, compute the insertion point. */ + end_point_insert = knot_insert_bezier( + src_positions, src_handles_l, src_handles_r, end_point); + } + + dst_handles_r[dst_index - 1] = end_point_insert.handle_prev; + dst_types_r[dst_index - 1] = src_types_l[end_point.index]; + + dst_handles_l[dst_index] = end_point_insert.left_handle; + dst_handles_r[dst_index] = end_point_insert.right_handle; + dst_positions[dst_index] = end_point_insert.position; + dst_types_l[dst_index] = src_types_l[end_point.next_index]; + dst_types_r[dst_index] = src_types_r[end_point.next_index]; +#ifdef DEBUG + ++dst_index; +#endif // DEBUG + } + BLI_assert(dst_index == dst_range.one_after_last()); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Convert to Point Curves + * \{ */ + +static void convert_point_polygonal_curves( + const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> sample_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + sample_linear<float3>( + src_positions.slice(src_points), dst_positions, dst_points, sample_points[curve_i]); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + sample_linear<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + dst_curves.points_for_curve(curve_i), + sample_points[curve_i]); + }); + } + } + }); + + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); +} + +static void convert_point_catmull_curves( + const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> sample_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + const VArray<bool> src_cyclic = src_curves.cyclic(); + + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + sample_catmull_rom<float3>(src_positions.slice(src_points), + dst_positions, + dst_points, + sample_points[curve_i], + src_cyclic[curve_i]); + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + sample_catmull_rom<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + dst_points, + sample_points[curve_i], + src_cyclic[curve_i]); + }); + } + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); +} + +static void convert_point_bezier_curves( + const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> sample_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + const VArraySpan<int8_t> src_types_l{src_curves.handle_types_left()}; + const VArraySpan<int8_t> src_types_r{src_curves.handle_types_right()}; + const Span<float3> src_handles_l = src_curves.handle_positions_left(); + const Span<float3> src_handles_r = src_curves.handle_positions_right(); + + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + MutableSpan<int8_t> dst_types_l = dst_curves.handle_types_left_for_write(); + MutableSpan<int8_t> dst_types_r = dst_curves.handle_types_right_for_write(); + MutableSpan<float3> dst_handles_l = dst_curves.handle_positions_left_for_write(); + MutableSpan<float3> dst_handles_r = dst_curves.handle_positions_right_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + sample_bezier(src_positions.slice(src_points), + src_handles_l.slice(src_points), + src_handles_r.slice(src_points), + src_types_l.slice(src_points), + src_types_r.slice(src_points), + dst_positions, + dst_handles_l, + dst_handles_r, + dst_types_l, + dst_types_r, + dst_points, + sample_points[curve_i]); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + sample_linear<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + dst_points, + sample_points[curve_i]); + }); + } + } + }); + fill_nurbs_data(dst_curves, selection); +} + +static void convert_point_evaluated_curves( + const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> evaluated_sample_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_eval_positions = src_curves.evaluated_positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 4096, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + const IndexRange src_evaluated_points = src_curves.evaluated_points_for_curve(curve_i); + + sample_linear<float3>(src_eval_positions.slice(src_evaluated_points), + dst_positions, + dst_points, + evaluated_sample_points[curve_i]); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + GArray evaluated_data(CPPType::get<T>(), src_evaluated_points.size()); + GMutableSpan evaluated_span = evaluated_data.as_mutable_span(); + src_curves.interpolate_to_evaluated( + curve_i, attribute.src.slice(src_curves.points_for_curve(curve_i)), evaluated_span); + sample_linear<T>(evaluated_span.typed<T>(), + attribute.dst.span.typed<T>(), + dst_points, + evaluated_sample_points[curve_i]); + }); + } + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Trim Curves + * \{ */ + +static void trim_attribute_linear(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_linear<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + src_sample_range, + dst_curves.points_for_curve(curve_i), + start_points[curve_i], + end_points[curve_i]); + } + }); + }); + } +} + +static void trim_polygonal_curves(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_linear<float3>(src_positions.slice(src_points), + dst_positions, + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i]); + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); + trim_attribute_linear( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); +} + +static void trim_catmull_rom_curves(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + const VArray<bool> src_cyclic = src_curves.cyclic(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_catmull_rom<float3>(src_positions.slice(src_points), + dst_positions, + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i], + src_cyclic[curve_i]); + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_catmull_rom<T>(attribute.src.template typed<T>().slice(src_points), + attribute.dst.span.typed<T>(), + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i], + src_cyclic[curve_i]); + } + }); + }); + } +} + +static void trim_bezier_curves(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_positions = src_curves.positions(); + const VArraySpan<int8_t> src_types_l{src_curves.handle_types_left()}; + const VArraySpan<int8_t> src_types_r{src_curves.handle_types_right()}; + const Span<float3> src_handles_l = src_curves.handle_positions_left(); + const Span<float3> src_handles_r = src_curves.handle_positions_right(); + + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + MutableSpan<int8_t> dst_types_l = dst_curves.handle_types_left_for_write(); + MutableSpan<int8_t> dst_types_r = dst_curves.handle_types_right_for_write(); + MutableSpan<float3> dst_handles_l = dst_curves.handle_positions_left_for_write(); + MutableSpan<float3> dst_handles_r = dst_curves.handle_positions_right_for_write(); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange src_points = src_curves.points_for_curve(curve_i); + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_points.size()}); + sample_interval_bezier(src_positions.slice(src_points), + src_handles_l.slice(src_points), + src_handles_r.slice(src_points), + src_types_l.slice(src_points), + src_types_r.slice(src_points), + dst_positions, + dst_handles_l, + dst_handles_r, + dst_types_l, + dst_types_r, + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i]); + } + }); + fill_nurbs_data(dst_curves, selection); + trim_attribute_linear( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); +} + +static void trim_evaluated_curves(const bke::CurvesGeometry &src_curves, + bke::CurvesGeometry &dst_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points, + MutableSpan<bke::AttributeTransferData> transfer_attributes) +{ + const Span<float3> src_eval_positions = src_curves.evaluated_positions(); + MutableSpan<float3> dst_positions = dst_curves.positions_for_write(); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + const IndexRange dst_points = dst_curves.points_for_curve(curve_i); + const IndexRange src_evaluated_points = src_curves.evaluated_points_for_curve(curve_i); + + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_evaluated_points.size()}); + sample_interval_linear<float3>(src_eval_positions.slice(src_evaluated_points), + dst_positions, + src_sample_range, + dst_points, + start_points[curve_i], + end_points[curve_i]); + } + }); + fill_bezier_data(dst_curves, selection); + fill_nurbs_data(dst_curves, selection); + + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute_math::convert_to_static_type(attribute.meta_data.data_type, [&](auto dummy) { + using T = decltype(dummy); + + threading::parallel_for(selection.index_range(), 512, [&](const IndexRange range) { + for (const int64_t curve_i : selection.slice(range)) { + /* Interpolate onto the evaluated point domain and sample the evaluated domain. */ + const IndexRange src_evaluated_points = src_curves.evaluated_points_for_curve(curve_i); + GArray evaluated_data(CPPType::get<T>(), src_evaluated_points.size()); + GMutableSpan evaluated_span = evaluated_data.as_mutable_span(); + src_curves.interpolate_to_evaluated( + curve_i, attribute.src.slice(src_curves.points_for_curve(curve_i)), evaluated_span); + bke::curves::IndexRangeCyclic src_sample_range = get_range_between_endpoints( + start_points[curve_i], end_points[curve_i], {0, src_evaluated_points.size()}); + sample_interval_linear<T>(evaluated_span.typed<T>(), + attribute.dst.span.typed<T>(), + src_sample_range, + dst_curves.points_for_curve(curve_i), + start_points[curve_i], + end_points[curve_i]); + } + }); + }); + } +} + +bke::CurvesGeometry trim_curves(const bke::CurvesGeometry &src_curves, + const IndexMask selection, + const Span<bke::curves::CurvePoint> start_points, + const Span<bke::curves::CurvePoint> end_points) +{ + BLI_assert(selection.size() > 0); + BLI_assert(selection.last() <= start_points.size()); + BLI_assert(start_points.size() == end_points.size()); + + src_curves.ensure_evaluated_offsets(); + Vector<int64_t> inverse_selection_indices; + const IndexMask inverse_selection = selection.invert(src_curves.curves_range(), + inverse_selection_indices); + + /* Create trim curves. */ + bke::CurvesGeometry dst_curves(0, src_curves.curves_num()); + determine_copyable_curve_types(src_curves, + dst_curves, + selection, + inverse_selection, + (CurveTypeMask)(CURVE_TYPE_MASK_CATMULL_ROM | + CURVE_TYPE_MASK_POLY | CURVE_TYPE_MASK_BEZIER)); + + Vector<int64_t> curve_indices; + Vector<int64_t> point_curve_indices; + compute_trim_result_offsets(src_curves, + selection, + inverse_selection, + start_points, + end_points, + dst_curves.curve_types(), + dst_curves.offsets_for_write(), + curve_indices, + point_curve_indices); + /* Finalize by updating the geometry container. */ + dst_curves.resize(dst_curves.offsets().last(), dst_curves.curves_num()); + dst_curves.update_curve_types(); + + /* Populate curve domain. */ + const bke::AttributeAccessor src_attributes = src_curves.attributes(); + bke::MutableAttributeAccessor dst_attributes = dst_curves.attributes_for_write(); + bke::copy_attribute_domain(src_attributes, + dst_attributes, + selection, + ATTR_DOMAIN_CURVE, + {"cyclic", "curve_type", "nurbs_order", "knots_mode"}); + + /* Fetch custom point domain attributes for transfer (copy). */ + Vector<bke::AttributeTransferData> transfer_attributes = bke::retrieve_attributes_for_transfer( + src_attributes, + dst_attributes, + ATTR_DOMAIN_MASK_POINT, + {"position", + "handle_left", + "handle_right", + "handle_type_left", + "handle_type_right", + "nurbs_weight"}); + + auto trim_catmull = [&](IndexMask selection) { + trim_catmull_rom_curves( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); + }; + auto trim_poly = [&](IndexMask selection) { + trim_polygonal_curves( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); + }; + auto trim_bezier = [&](IndexMask selection) { + trim_bezier_curves( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); + }; + auto trim_evaluated = [&](IndexMask selection) { + /* Ensure evaluated positions are available. */ + src_curves.ensure_evaluated_offsets(); + src_curves.evaluated_positions(); + trim_evaluated_curves( + src_curves, dst_curves, selection, start_points, end_points, transfer_attributes); + }; + + auto single_point_catmull = [&](IndexMask selection) { + convert_point_catmull_curves( + src_curves, dst_curves, selection, start_points, transfer_attributes); + }; + auto single_point_poly = [&](IndexMask selection) { + convert_point_polygonal_curves( + src_curves, dst_curves, selection, start_points, transfer_attributes); + }; + auto single_point_bezier = [&](IndexMask selection) { + convert_point_bezier_curves( + src_curves, dst_curves, selection, start_points, transfer_attributes); + }; + auto single_point_evaluated = [&](IndexMask selection) { + convert_point_evaluated_curves( + src_curves, dst_curves, selection, start_points, transfer_attributes); + }; + + /* Populate point domain. */ + bke::curves::foreach_curve_by_type(src_curves.curve_types(), + src_curves.curve_type_counts(), + curve_indices.as_span(), + trim_catmull, + trim_poly, + trim_bezier, + trim_evaluated); + + if (point_curve_indices.size()) { + bke::curves::foreach_curve_by_type(src_curves.curve_types(), + src_curves.curve_type_counts(), + point_curve_indices.as_span(), + single_point_catmull, + single_point_poly, + single_point_bezier, + single_point_evaluated); + } + /* Cleanup/close context */ + for (bke::AttributeTransferData &attribute : transfer_attributes) { + attribute.dst.finish(); + } + + /* Copy unselected */ + if (!inverse_selection.is_empty()) { + bke::copy_attribute_domain( + src_attributes, dst_attributes, inverse_selection, ATTR_DOMAIN_CURVE); + /* Trim curves are no longer cyclic. If all curves are trimmed, this will be set implicitly. */ + dst_curves.cyclic_for_write().fill_indices(selection, false); + + /* Copy point domain. */ + for (auto &attribute : bke::retrieve_attributes_for_transfer( + src_attributes, dst_attributes, ATTR_DOMAIN_MASK_POINT)) { + bke::curves::copy_point_data( + src_curves, dst_curves, inverse_selection, attribute.src, attribute.dst.span); + attribute.dst.finish(); + } + } + + dst_curves.tag_topology_changed(); + return dst_curves; +} + +/** \} */ + +} // namespace blender::geometry diff --git a/source/blender/geometry/intern/uv_parametrizer.cc b/source/blender/geometry/intern/uv_parametrizer.cc index b7526d82ecc..b15c8b6e319 100644 --- a/source/blender/geometry/intern/uv_parametrizer.cc +++ b/source/blender/geometry/intern/uv_parametrizer.cc @@ -22,11 +22,11 @@ /* Utils */ #define param_assert(condition) \ - if (!(condition)) { /*printf("Assertion %s:%d\n", __FILE__, __LINE__); abort();*/ \ + if (!(condition)) { /* `printf("Assertion %s:%d\n", __FILE__, __LINE__); abort();` */ \ } \ (void)0 #define param_warning(message) \ - {/*printf("Warning %s:%d: %s\n", __FILE__, __LINE__, message);*/}(void)0 + {/* `printf("Warning %s:%d: %s\n", __FILE__, __LINE__, message);` */}(void)0 /* Special Purpose Hash */ @@ -307,12 +307,70 @@ static float p_vec2_angle(const float v1[2], const float v2[2], const float v3[2 { return angle_v2v2v2(v1, v2, v3); } + +/* Angles close to 0 or 180 degrees cause rows filled with zeros in the linear_solver. + * The matrix will then be rank deficient and / or have poor conditioning. + * => Reduce the maximum angle to 179 degrees, and spread the remainder to the other angles. + */ +static void fix_large_angle(const float v_fix[3], + const float v1[3], + const float v2[3], + float *r_fix, + float *r_a1, + float *r_a2) +{ + const float max_angle = (float)M_PI * (179.0f / 180.0f); + const float fix_amount = *r_fix - max_angle; + if (fix_amount < 0.0f) { + return; /* angle is reasonable, i.e. less than 179 degrees. */ + } + + /* The triangle is probably degenerate, or close to it. + * Without loss of generality, transform the triangle such that + * v_fix == { 0, s}, *r_fix = 180 degrees + * v1 == {-x1, 0}, *r_a1 = 0 + * v2 == { x2, 0}, *r_a2 = 0 + * + * With `s = 0`, `x1 > 0`, `x2 > 0` + * + * Now make `s` a small number and do some math: + * tan(*r_a1) = s / x1 + * tan(*r_a2) = s / x2 + * + * Remember that `tan = sin / cos`, `sin(s) ~= s` and `cos(s) = 1` + * + * Rearrange to obtain: + * *r_a1 = fix_amount * x2 / (x1 + x2) + * *r_a2 = fix_amount * x1 / (x1 + x2) + */ + + const float dist_v1 = len_v3v3(v_fix, v1); + const float dist_v2 = len_v3v3(v_fix, v2); + const float sum = dist_v1 + dist_v2; + const float weight = (sum > 1e-20f) ? dist_v2 / sum : 0.5f; + + /* Ensure sum of angles in triangle is unchanged. */ + *r_fix -= fix_amount; + *r_a1 += fix_amount * weight; + *r_a2 += fix_amount * (1.0f - weight); +} + static void p_triangle_angles( const float v1[3], const float v2[3], const float v3[3], float *r_a1, float *r_a2, float *r_a3) { *r_a1 = p_vec_angle(v3, v1, v2); *r_a2 = p_vec_angle(v1, v2, v3); - *r_a3 = (float)M_PI - *r_a2 - *r_a1; + *r_a3 = p_vec_angle(v2, v3, v1); + + /* Fix for degenerate geometry e.g. v1 = sum(v2 + v3). See T100874 */ + fix_large_angle(v1, v2, v3, r_a1, r_a2, r_a3); + fix_large_angle(v2, v3, v1, r_a2, r_a3, r_a1); + fix_large_angle(v3, v1, v2, r_a3, r_a1, r_a2); + + /* Workaround for degenerate geometry, e.g. v1 == v2 == v3. */ + *r_a1 = max_ff(*r_a1, 0.001f); + *r_a2 = max_ff(*r_a2, 0.001f); + *r_a3 = max_ff(*r_a3, 0.001f); } static void p_face_angles(PFace *f, float *r_a1, float *r_a2, float *r_a3) @@ -2266,7 +2324,6 @@ using PAbfSystem = struct PAbfSystem { float *bAlpha, *bTriangle, *bInterior; float *lambdaTriangle, *lambdaPlanar, *lambdaLength; float (*J2dt)[3], *bstar, *dstar; - float minangle, maxangle; }; static void p_abf_setup_system(PAbfSystem *sys) @@ -2294,9 +2351,6 @@ static void p_abf_setup_system(PAbfSystem *sys) for (i = 0; i < sys->ninterior; i++) { sys->lambdaLength[i] = 1.0; } - - sys->minangle = 1.0 * M_PI / 180.0; - sys->maxangle = (float)M_PI - sys->minangle; } static void p_abf_free_system(PAbfSystem *sys) @@ -2707,25 +2761,6 @@ static bool p_chart_abf_solve(PChart *chart) e3 = e2->next; p_face_angles(f, &a1, &a2, &a3); - if (a1 < sys.minangle) { - a1 = sys.minangle; - } - else if (a1 > sys.maxangle) { - a1 = sys.maxangle; - } - if (a2 < sys.minangle) { - a2 = sys.minangle; - } - else if (a2 > sys.maxangle) { - a2 = sys.maxangle; - } - if (a3 < sys.minangle) { - a3 = sys.minangle; - } - else if (a3 > sys.maxangle) { - a3 = sys.maxangle; - } - sys.alpha[e1->u.id] = sys.beta[e1->u.id] = a1; sys.alpha[e2->u.id] = sys.beta[e2->u.id] = a2; sys.alpha[e3->u.id] = sys.beta[e3->u.id] = a3; @@ -4260,7 +4295,7 @@ void GEO_uv_parametrizer_average(ParamHandle *phandle, for (int j = 0; j < max_iter; j++) { /* An island could contain millions of polygons. When summing many small values, we need to * use double precision in the accumulator to maintain accuracy. Note that the individual - * calculations only need to be at single precision.*/ + * calculations only need to be at single precision. */ double scale_cou = 0; double scale_cov = 0; double scale_cross = 0; @@ -4275,11 +4310,11 @@ void GEO_uv_parametrizer_average(ParamHandle *phandle, s[1][0] = vb->uv[0] - vc->uv[0]; s[1][1] = vb->uv[1] - vc->uv[1]; /* Find the "U" axis and "V" axis in triangle co-ordinates. Normally this would require - * SVD, but in 2D we can use a cheaper matrix inversion instead.*/ + * SVD, but in 2D we can use a cheaper matrix inversion instead. */ if (!invert_m2_m2(m, s)) { continue; } - float cou[3], cov[3]; /* i.e. Texture "U" and texture "V" in 3D co-ordinates.*/ + float cou[3], cov[3]; /* i.e. Texture "U" and texture "V" in 3D co-ordinates. */ for (int k = 0; k < 3; k++) { cou[k] = m[0][0] * (va->co[k] - vc->co[k]) + m[0][1] * (vb->co[k] - vc->co[k]); cov[k] = m[1][0] * (va->co[k] - vc->co[k]) + m[1][1] * (vb->co[k] - vc->co[k]); @@ -4320,7 +4355,7 @@ void GEO_uv_parametrizer_average(ParamHandle *phandle, const float tolerance = 1e-6f; /* Trade accuracy for performance. */ if (err < tolerance) { - /* Too slow? Use Richardson Extrapolation to accelerate the convergence.*/ + /* Too slow? Use Richardson Extrapolation to accelerate the convergence. */ break; } } |