Blender V5.3
blender::offset_indices Namespace Reference

Namespaces

namespace  tests

Classes

struct  NoSortCheck
class  OffsetIndices
struct  GroupedSpan

Functions

OffsetIndices< int > accumulate_counts_to_offsets (MutableSpan< int > counts_to_offsets, int start_offset=0)
std::optional< OffsetIndices< int > > accumulate_counts_to_offsets_with_overflow_check (MutableSpan< int > counts_to_offsets, int start_offset=0)
void fill_constant_group_size (int size, int start_offset, MutableSpan< int > offsets)
void copy_group_sizes (OffsetIndices< int > offsets, const IndexMask &mask, MutableSpan< int > sizes)
void gather_group_sizes (OffsetIndices< int > offsets, const IndexMask &mask, MutableSpan< int > sizes)
void gather_group_sizes (OffsetIndices< int > offsets, Span< int > indices, MutableSpan< int > sizes)
int sum_group_sizes (OffsetIndices< int > offsets, const IndexMask &mask)
int sum_group_sizes (OffsetIndices< int > offsets, Span< int > indices)
OffsetIndices< int > gather_selected_offsets (OffsetIndices< int > src_offsets, const IndexMask &selection, int start_offset, MutableSpan< int > dst_offsets)
OffsetIndices< int > gather_selected_offsets (OffsetIndices< int > src_offsets, const IndexMask &selection, MutableSpan< int > dst_offsets)
OffsetIndices< int > gather_selected_offsets (OffsetIndices< int > src_offsets, Span< int > selection, int start_offset, MutableSpan< int > dst_offsets)
OffsetIndices< int > gather_selected_offsets (OffsetIndices< int > src_offsets, const Span< int > selection, MutableSpan< int > dst_offsets)
void build_reverse_map (OffsetIndices< int > offsets, MutableSpan< int > r_map)
OffsetIndices< int > build_reverse_offsets (Span< int > indices, MutableSpan< int > offsets)
void sort_groups (OffsetIndices< int > groups, MutableSpan< int > indices)
void reverse_indices_in_groups (Span< int > group_indices, OffsetIndices< int > offsets, MutableSpan< int > results, bool sort=true)
void reverse_indices_in_groups (Span< int > group_indices, OffsetIndices< int > offsets, MutableSpan< int > results, OffsetIndices< int > value_groups)
void reverse_indices_in_groups (Span< int > group_indices, OffsetIndices< int > offsets, MutableSpan< int > results, int value_group_size)
GroupedSpan< int > build_groups_from_indices (Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
GroupedSpan< int > build_groups_from_indices (Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data, const IndexMask &values)
static int64_t counting_chunk_size (const int64_t indices_num)
template<typename ValueSourceForeach>
static void reverse_indices_in_groups_counting (const Span< int > group_indices, const OffsetIndices< int > offsets, const ValueSourceForeach &value_source_foreach, MutableSpan< int > results)
template<typename ValueSourceForeach>
static void reverse_indices_in_groups_atomic (const Span< int > group_indices, const OffsetIndices< int > offsets, const ValueSourceForeach &value_source_foreach, MutableSpan< int > results)
template<typename ValueSourceForeach>
static void fill_groups (const Span< int > group_indices, const OffsetIndices< int > offsets, const ValueSourceForeach &value_source_foreach, const bool sort, MutableSpan< int > results)
static void assert_group_indices_valid (const Span< int > group_indices, const OffsetIndices< int > offsets)

Function Documentation

◆ accumulate_counts_to_offsets()

OffsetIndices< int > blender::offset_indices::accumulate_counts_to_offsets ( MutableSpan< int > counts_to_offsets,
int start_offset = 0 )

Turn an array of sizes into the offset at each index including all previous sizes.

Definition at line 24 of file offset_indices.cc.

References accumulate_counts_to_offsets(), blender::BLI_assert(), BLI_assert_msg, blender::IndexRange::drop_back(), blender::MutableSpan< T >::index_range(), blender::MutableSpan< T >::last(), and UNUSED_VARS_NDEBUG.

Referenced by blender::nodes::node_geo_duplicate_elements_cc::accumulate_counts_to_offsets(), accumulate_counts_to_offsets(), blender::ed::curves::add_curves(), blender::bke::pbvh::pixels::build_border_triangles(), blender::build_concurrent(), blender::ed::greasepencil::build_curves_2d_bvh_from_visible(), build_reverse_offsets(), blender::build_sequential(), blender::io::usd::calc_curve_offsets(), blender::geometry::calc_new_edges(), blender::geometry::ngon::calc_tris_by_ngon(), blender::geometry::calculate_result_offsets(), blender::geometry::calculate_result_offsets(), blender::geometry::calculate_sphere_faces(), blender::geometry::construct::compute_new_corner_interp_weights(), blender::geometry::convert_curves_to_bezier(), blender::geometry::convert_curves_to_catmull_rom_or_poly(), blender::geometry::convert_curves_to_nurbs(), blender::geometry::copy_and_reorder_curves(), blender::geometry::copy_and_reorder_mesh_faces(), blender::geometry::create_cylinder_or_cone_mesh(), blender::create_envelope_strokes(), blender::ed::sculpt_paint::create_node_vert_offsets(), blender::ed::sculpt_paint::create_node_vert_offsets(), blender::ed::sculpt_paint::create_node_vert_offsets_bmesh(), blender::ed::transform::curves::curve_populate_trans_data_structs(), blender::bke::curves_copy_point_selection(), blender::displist_fill_cdt_process_group(), blender::bke::calc_edges::edge_map_offsets(), blender::geometry::execute_instances_tasks(), blender::ed::greasepencil::boolean::execute_single_boolean(), blender::geometry::extend_curves(), blender::io::grease_pencil::extend_curves_geometry(), blender::ed::curves::pen_tool::extrude_curves(), blender::ed::greasepencil::extrude_grease_pencil_curves(), blender::nodes::node_geo_extrude_mesh_cc::extrude_mesh_edges(), blender::bke::greasepencil::fill_cache_from_fill_ids(), blender::geometry::find_connected_ranges(), blender::ed::sculpt_paint::greasepencil::find_curve_pair_offsets(), blender::ed::greasepencil::find_curve_segments(), blender::geometry::fit_poly_to_bezier_curves(), blender::meshintersect::flood_fill_region_values(), blender::ed::sculpt_paint::grease_pencil_fill_extension_cut(), blender::ed::curves::pen_tool::insert_point_to_curve(), blender::ed::sculpt_paint::greasepencil::interpolate_between_curves(), blender::geometry::join_curves_ranges(), blender::geometry::join_instances(), blender::ed::mesh::join_objects_exec(), blender::geometry::make_new_offset_indices(), blender::geometry::merge_propagation_map(), blender::bke::mesh_apply_spatial_organization(), blender::bke::mesh_calc_edges(), blender::draw::mesh_render_data_faces_sorted_build(), blender::nodes::node_geo_rasterize_points::node_geo_exec(), blender::bke::CurvesGeometry::nurbs_custom_knots_by_curve(), blender::geometry::remove_points_and_split(), blender::geometry::reorder_and_flip_curves(), blender::geometry::resample_to_count(), blender::geometry::resample_to_evaluated(), blender::geometry::resample_to_length(), blender::ed::curves::resize_curves(), blender::bke::greasepencil::shapes_from_fill_ids(), blender::offset_indices::tests::TEST(), blender::offset_indices::tests::test_reverse_indices_in_uniform_value_groups(), blender::offset_indices::tests::test_reverse_indices_in_value_groups(), blender::ed::greasepencil::trim::trim_curve_segment_ends(), blender::ed::greasepencil::trim::trim_curve_segments(), blender::geometry::trim_curves(), blender::bke::greasepencil::update_triangle_and_offsets_changed(), and blender::geometry::weld_face_find_doubles().

◆ accumulate_counts_to_offsets_with_overflow_check()

std::optional< OffsetIndices< int > > blender::offset_indices::accumulate_counts_to_offsets_with_overflow_check ( MutableSpan< int > counts_to_offsets,
int start_offset = 0 )

◆ assert_group_indices_valid()

void blender::offset_indices::assert_group_indices_valid ( const Span< int > group_indices,
const OffsetIndices< int > offsets )
static

◆ build_groups_from_indices() [1/2]

GroupedSpan< int > blender::offset_indices::build_groups_from_indices ( Span< int > indices,
int groups_num,
Array< int > & offset_data,
Array< int > & index_data )

With indices divided in a certain number of unique groups, reverse the index mapping so that the indices in each group can be index by the group index. Similar to reverse_indices_in_groups, but also creates the offsets.

Example: [1, 0, 1, 1], groups_num 2 -> offsets [0, 1, 4], indices [1, 0, 2, 3].

Definition at line 418 of file offset_indices.cc.

References blender::Array< T, InlineBufferCapacity, Allocator >::as_mutable_span(), build_groups_from_indices(), build_reverse_offsets(), blender::Array< T, InlineBufferCapacity, Allocator >::reinitialize(), reverse_indices_in_groups(), and blender::offset_indices::OffsetIndices< T >::total_size().

Referenced by blender::bke::mesh::build_edge_to_corner_map(), build_groups_from_indices(), build_groups_from_indices(), blender::bke::mesh::build_vert_to_corner_map(), blender::geometry::find_duplicate_edges(), blender::bke::find_duplicate_faces(), blender::index_mask::IndexMask::from_group_ids(), blender::nodes::node_geo_scale_elements_cc::gather_edge_islands(), blender::nodes::node_geo_scale_elements_cc::gather_face_islands(), blender::nodes::node_geo_merge_layers_cc::get_layers_map_by_id(), blender::nodes::node_geo_cluster_by_distance_cc::ClusterByDistanceFieldInput::get_varray_for_context(), blender::nodes::node_geo_index_of_nearest_cc::IndexOfNearestFieldInput::get_varray_for_context(), blender::geometry::merge_layers_by_name(), blender::geometry::merge_points(), blender::geometry::merge_propagation_map(), blender::run_build_groups_table(), blender::offset_indices::tests::TEST(), blender::offset_indices::tests::test_build_groups_from_indices(), blender::offset_indices::tests::test_build_groups_from_indices_mask(), and blender::bke::pbvh::pixels::update_pixels().

◆ build_groups_from_indices() [2/2]

GroupedSpan< int > blender::offset_indices::build_groups_from_indices ( Span< int > indices,
int groups_num,
Array< int > & offset_data,
Array< int > & index_data,
const IndexMask & values )

◆ build_reverse_map()

void blender::offset_indices::build_reverse_map ( OffsetIndices< int > offsets,
MutableSpan< int > r_map )

Create a map from indexed elements to the source indices, in other words from the larger array to the smaller array.

Example: [0, 2, 2, 5] -> [0, 0, 2, 2, 2].

Definition at line 169 of file offset_indices.cc.

References build_reverse_map(), blender::offset_indices::OffsetIndices< T >::index_range(), and blender::threading::parallel_for().

Referenced by blender::bke::mesh::build_corner_to_face_map(), build_reverse_map(), and blender::bke::CurvesGeometry::point_to_curve_map().

◆ build_reverse_offsets()

◆ copy_group_sizes()

◆ counting_chunk_size()

int64_t blender::offset_indices::counting_chunk_size ( const int64_t indices_num)
static

Number of indices per chunk when counting. An offset is stored for every group in every chunk, so the number of chunks is limited to a small multiple of the number of threads. More chunks than threads still helps load balancing.

Definition at line 205 of file offset_indices.cc.

References blender::BLI_system_thread_count(), counting_chunk_size(), and blender::divide_ceil_ul().

Referenced by counting_chunk_size(), fill_groups(), and reverse_indices_in_groups_counting().

◆ fill_constant_group_size()

◆ fill_groups()

template<typename ValueSourceForeach>
void blender::offset_indices::fill_groups ( const Span< int > group_indices,
const OffsetIndices< int > offsets,
const ValueSourceForeach & value_source_foreach,
const bool sort,
MutableSpan< int > results )
static

Fill the groups with the value of every element that maps to them. The values must not decrease with the position in #group_indices, so that sorting them orders each group by position.

Definition at line 298 of file offset_indices.cc.

References blender::BLI_system_thread_count(), counting_chunk_size(), blender::divide_ceil_ul(), fill_groups(), reverse_indices_in_groups_atomic(), reverse_indices_in_groups_counting(), blender::offset_indices::OffsetIndices< T >::size(), blender::Span< T >::size(), sort(), and sort_groups().

Referenced by build_groups_from_indices(), fill_groups(), and reverse_indices_in_groups().

◆ gather_group_sizes() [1/2]

◆ gather_group_sizes() [2/2]

◆ gather_selected_offsets() [1/4]

◆ gather_selected_offsets() [2/4]

OffsetIndices< int > blender::offset_indices::gather_selected_offsets ( OffsetIndices< int > src_offsets,
const IndexMask & selection,
MutableSpan< int > dst_offsets )
inline

Definition at line 182 of file BLI_offset_indices.hh.

References gather_selected_offsets().

◆ gather_selected_offsets() [3/4]

OffsetIndices< int > blender::offset_indices::gather_selected_offsets ( OffsetIndices< int > src_offsets,
const Span< int > selection,
MutableSpan< int > dst_offsets )
inline

Definition at line 192 of file BLI_offset_indices.hh.

References gather_selected_offsets().

◆ gather_selected_offsets() [4/4]

OffsetIndices< int > blender::offset_indices::gather_selected_offsets ( OffsetIndices< int > src_offsets,
Span< int > selection,
int start_offset,
MutableSpan< int > dst_offsets )

◆ reverse_indices_in_groups() [1/3]

void blender::offset_indices::reverse_indices_in_groups ( Span< int > group_indices,
OffsetIndices< int > offsets,
MutableSpan< int > results,
bool sort = true )

◆ reverse_indices_in_groups() [2/3]

void blender::offset_indices::reverse_indices_in_groups ( Span< int > group_indices,
OffsetIndices< int > offsets,
MutableSpan< int > results,
int value_group_size )

◆ reverse_indices_in_groups() [3/3]

void blender::offset_indices::reverse_indices_in_groups ( Span< int > group_indices,
OffsetIndices< int > offsets,
MutableSpan< int > results,
OffsetIndices< int > value_groups )

Same as above, but every element belongs to one of the larger groups described by value_groups Results contain the index of each group, and are always sorted.

Example: [1, 0, 1, 1], offsets [0, 1, 4], value_groups [0, 2, 4] -> [0, 0, 1, 1].

Definition at line 353 of file offset_indices.cc.

References assert_group_indices_valid(), blender::Span< T >::begin(), blender::BLI_assert(), blender::offset_indices::OffsetIndices< T >::data(), blender::Span< T >::is_empty(), blender::IndexRange::one_after_last(), reverse_indices_in_groups(), reverse_indices_in_groups_atomic(), blender::MutableSpan< T >::size(), blender::Span< T >::size(), sort_groups(), blender::IndexRange::start(), and blender::offset_indices::OffsetIndices< T >::total_size().

◆ reverse_indices_in_groups_atomic()

template<typename ValueSourceForeach>
void blender::offset_indices::reverse_indices_in_groups_atomic ( const Span< int > group_indices,
const OffsetIndices< int > offsets,
const ValueSourceForeach & value_source_foreach,
MutableSpan< int > results )
static

Fill the groups in parallel, using atomics to find the position to write to in each group. The order within each group is non-deterministic.

Definition at line 278 of file offset_indices.cc.

References blender::Span< T >::index_range(), blender::threading::parallel_for(), reverse_indices_in_groups_atomic(), and blender::offset_indices::OffsetIndices< T >::size().

Referenced by fill_groups(), reverse_indices_in_groups(), reverse_indices_in_groups(), and reverse_indices_in_groups_atomic().

◆ reverse_indices_in_groups_counting()

template<typename ValueSourceForeach>
void blender::offset_indices::reverse_indices_in_groups_counting ( const Span< int > group_indices,
const OffsetIndices< int > offsets,
const ValueSourceForeach & value_source_foreach,
MutableSpan< int > results )
static

Fill the groups by first counting, for every chunk of indices, how many of its indices fall into each group. Every chunk then knows where it can write in each group, so no atomics are needed and the indices in each group end up sorted.

This needs an offset for each group in each chunk, so it is only suitable while the number of groups is small relative to the number of indices.

Definition at line 221 of file offset_indices.cc.

References blender::Array< T, InlineBufferCapacity, Allocator >::as_mutable_span(), blender::begin(), counting_chunk_size(), blender::divide_ceil_ul(), blender::MutableSpan< T >::fill(), blender::threading::parallel_for(), position, reverse_indices_in_groups_counting(), blender::offset_indices::OffsetIndices< T >::size(), blender::Span< T >::size(), and blender::Span< T >::slice_safe().

Referenced by fill_groups(), and reverse_indices_in_groups_counting().

◆ sort_groups()

void blender::offset_indices::sort_groups ( OffsetIndices< int > groups,
MutableSpan< int > indices )

Used as a final step for parallel creation of grouped indices, to make results deterministic as each group's indices are potentially filled from multiple threads.

Definition at line 185 of file offset_indices.cc.

References blender::offset_indices::OffsetIndices< T >::index_range(), blender::threading::parallel_for(), and sort_groups().

Referenced by fill_groups(), reverse_indices_in_groups(), reverse_indices_in_groups(), and sort_groups().

◆ sum_group_sizes() [1/2]

◆ sum_group_sizes() [2/2]

int blender::offset_indices::sum_group_sizes ( OffsetIndices< int > offsets,
Span< int > indices )