Geometry Nodes: Sort Elements node #114194
No reviewers
Labels
No Label
Interest
Alembic
Interest
Animation & Rigging
Interest
Asset Browser
Interest
Asset Browser Project Overview
Interest
Audio
Interest
Automated Testing
Interest
Blender Asset Bundle
Interest
BlendFile
Interest
Collada
Interest
Compatibility
Interest
Compositing
Interest
Core
Interest
Cycles
Interest
Dependency Graph
Interest
Development Management
Interest
EEVEE
Interest
EEVEE & Viewport
Interest
Freestyle
Interest
Geometry Nodes
Interest
Grease Pencil
Interest
ID Management
Interest
Images & Movies
Interest
Import Export
Interest
Line Art
Interest
Masking
Interest
Metal
Interest
Modeling
Interest
Modifiers
Interest
Motion Tracking
Interest
Nodes & Physics
Interest
OpenGL
Interest
Overlay
Interest
Overrides
Interest
Performance
Interest
Physics
Interest
Pipeline, Assets & IO
Interest
Platforms, Builds & Tests
Interest
Python API
Interest
Render & Cycles
Interest
Render Pipeline
Interest
Sculpt, Paint & Texture
Interest
Text Editor
Interest
Translations
Interest
Triaging
Interest
Undo
Interest
USD
Interest
User Interface
Interest
UV Editing
Interest
VFX & Video
Interest
Video Sequencer
Interest
Virtual Reality
Interest
Vulkan
Interest
Wayland
Interest
Workbench
Interest: X11
Legacy
Blender 2.8 Project
Legacy
Milestone 1: Basic, Local Asset Browser
Legacy
OpenGL Error
Meta
Good First Issue
Meta
Papercut
Meta
Retrospective
Meta
Security
Module
Animation & Rigging
Module
Core
Module
Development Management
Module
EEVEE & Viewport
Module
Grease Pencil
Module
Modeling
Module
Nodes & Physics
Module
Pipeline, Assets & IO
Module
Platforms, Builds & Tests
Module
Python API
Module
Render & Cycles
Module
Sculpt, Paint & Texture
Module
Triaging
Module
User Interface
Module
VFX & Video
Platform
FreeBSD
Platform
Linux
Platform
macOS
Platform
Windows
Priority
High
Priority
Low
Priority
Normal
Priority
Unbreak Now!
Status
Archived
Status
Confirmed
Status
Duplicate
Status
Needs Info from Developers
Status
Needs Information from User
Status
Needs Triage
Status
Resolved
Type
Bug
Type
Design
Type
Known Issue
Type
Patch
Type
Report
Type
To Do
No Milestone
No project
No Assignees
2 Participants
Notifications
Due Date
No due date set.
Dependencies
No dependencies set.
Reference: blender/blender#114194
Loading…
Reference in New Issue
No description provided.
Delete Branch "mod_moder/blender:sort_elements"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
See: #109983
I think this should use the attribute API rather than
CustomData
. We're trying to move away from usingCustomData
in general, and working on a single attribute array at a time should give much better cache usage. It would be okay not to reuse the code from the debug randomization. Generating new geometries rather than modifying them in place would also be okay IMO.indices_are_rangeDidn't read through all of this yet, mostly just
reorder.cc
@ -0,0 +85,4 @@
MutableSpan<int> new_offsets)
{
Array<int> old_counts(old_offsets.size());
array_utils::copy(old_offsets, old_counts.as_mutable_span());
How about adding an overload of
gather_group_sizes
that takes aSpan<int>
instead of anIndexMask
? Then this would just look like:@ -0,0 +91,4 @@
offset_indices::accumulate_counts_to_offsets(new_offsets);
}
static void reorder_attributes(const bke::AttributeAccessor src_attributes,
I think there's an overload of the existing
gather_attributes
function that does the same thing@ -0,0 +129,4 @@
return data;
}
static void reorder_customdata_groups(CustomData &data,
This function seems to be unused
@ -0,0 +158,4 @@
const Array<int> new_by_old_map = invert_permutation(old_by_new_map);
const auto old_index_to_new = [&](const int old_i) { return new_by_old_map[old_i]; };
parallel_transform(dst_mesh.edges_for_write().cast<int>(), 4098, old_index_to_new);
I'm pretty sure these can be written with
array_utils::gather
rather thantransform
Ooh, just after writing full comment why this is not correct, i realized what did you mean/
array_utils::gather(dst: edges, indices: edges, src: old_indices_to_new)
.Overall structure looks good. Thanks for keeping this up to date.
@ -156,2 +156,4 @@
void gather_group_sizes(OffsetIndices<int> offsets, const IndexMask &mask, MutableSpan<int> sizes);
void gather_group_sizes(OffsetIndices<int> offsets,
const Span<int> indices,
const Span
->Span
@ -0,0 +4,4 @@
#include "DNA_curves_types.h"
#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
DNA_meshdata_types
is unnecessaryWhat about
Mesh
declaration and access to its fields?That's in
DNA_mesh_types.h
Ah, i mixup headers!
@ -0,0 +26,4 @@
&components_supported_reordering()
{
using namespace bke;
const static MultiValueMap<GeometryComponent::Type, AttrDomain> supported_types_and_domains =
I'd probably skip the static variable unless it's helpful to the runtime of the calling code. AFAIK it has to be initialized on program startup otherwise.
I just not sure how to define supported types. I mean, to validate input geometry and node settings, and to do not declare such internal things in definitely wrong place (in node witch is use this functions).
This might be something like
bool is_supported(GeometryComponent::Type component, AttrDomain domain);
..Not sure about
has to be initialized on program startup otherwise
. It isn't is right now? Or you mean issues with guardedalloc?That could work too. What I had in mind was just returning a newly constructed
MultiValueMap
every time. But either way is fine with me.My thought wasn't about correctness, just about adding fewer static variables for performance reasons. But I forgot that if the static value is declared inside a function, it's just initialized the first time the function is called. So never mind about the whole comment! :)
@ -0,0 +226,4 @@
array_utils::gather(old_transforms, old_by_new_map, new_transforms);
}
bke::GeometryComponent &reordered_component_copy(const bke::GeometryComponent &src_component,
Think this should return a
GeometryComponentPtr
. That could be released by the caller.@ -462,6 +462,8 @@ DefNode(GeometryNode, GEO_NODE_INTERPOLATE_CURVES, 0, "INTERPOLATE_CURVES", Inte
DefNode(GeometryNode, GEO_NODE_POINTS_TO_CURVES, 0, "POINTS_TO_CURVES", PointsToCurves, "Points to Curves", "Split all points to curve by its group ID and reorder by weight")
DefNode(GeometryNode, GEO_NODE_INPUT_EDGE_SMOOTH, 0, "INPUT_EDGE_SMOOTH", InputEdgeSmooth, "Is Edge Smooth", "Retrieve whether each edge is marked for smooth or split normals")
DefNode(GeometryNode, GEO_NODE_SORT_ELEMENTS, 0, "SORT_ELEMENTS", SortElements, "Sort Elements", "")
Suggestion:
Rearrange geometry elements, changing their indices
@ -0,0 +43,4 @@
node->custom1 = int(bke::AttrDomain::Point);
}
static bool indices_are_range(const Span<int> indices, const IndexRange range)
The existing implementation of
indices_are_range
could move toBLI_array_utils.hh
for this.@ -0,0 +83,4 @@
});
}
static void find_points_by_group_index(const Span<int> indices_of_curves,
Guess this shouldn't mention curves anymore
@ -0,0 +178,4 @@
const int total_groups = identifiers_to_indices(gathered_group_id);
Array<int> offsets_to_sort(total_groups + 1, 0);
find_points_by_group_index(gathered_group_id, offsets_to_sort, gathered_indices);
parallel_transform<int>(gathered_indices, 2048, [&](const int pos) { return mask[pos]; });
Think this should be changed to avoid random access to the
IndexMask
.Here is the same issue as in #115142, we have to have this log(n) complexity, or create tempolar array to realize indices from mask. I'd prefer to do not do this without additional benchmarks, at least.
I measured impact on performance by mask sampling (in #114194 (comment)). Temporary array would be some faster, but in just general impact on whole node is really small, and i not sure it is necessary to allocate so big tempolar array.
@ -0,0 +201,4 @@
unselected.foreach_index_optimized<int>(GrainSize(2048),
[&](const int index) { indices[index] = index; });
mask.foreach_index_optimized<int>(GrainSize(2048), [&](const int index, const int pos) {
Looks like this is
array_utils::scatter
@ -0,0 +256,4 @@
}
}
items.append({0, nullptr, 0, nullptr, nullptr});
return items.as_span();
I'd just return the
Vector
, no real need to convert it to an arrayI added example .blend file with combination of all supported geometry components/domains. Switching is happened manually, so be careful that attribute domain is the same in capturing and in sorting.
I'll have to make a benchmarks to deduce if direct sample of index mask should be replaced by creating tempolar array of mask indices though.
Here is a result of benchmark.
I did this measurements for this scope of code
b9a539a76e/source/blender/nodes/geometry/nodes/node_geo_scale_elements.cc (L382)
(rewrited version of Scale Element node), but this still applicable for current PR, and maybe all next.Here is direct comparison of
mask[i]
andmask_indices[in]
approach:Here is 3x speed improvements for mapping on really segmented mask. Usually there is better result though.
Here is more detailed exploration of
mapping(to_indices)
and it's part (to_indices
):Real remapping is still slovest part of this scope, due to random memory-read i thought.
Array filling by
to_indices
is fast though.For
0.5
random factor, this array is nearly to3.000.000
-+1.000.000
size. I think is a lot for this part of code:This chart is about impact of both approach for one certain function (benchmarked node have other stages which simply didn't measured). Both target sub-parts is simply added under function timings:
@ -0,0 +254,4 @@
clean_unused_attributes(propagation_info, *component);
if (const bke::MeshComponent *src_mesh_component = dynamic_cast<const bke::MeshComponent *>(
Moving this component type switching to the geometry node (instead of this file) might allow exposing more reusable functionality:
reorder_mesh
,reorder_curves
, etc.It is component interface is not enough reusable already?
I think it's a bit messy to force users of the function to go to a different abstraction level just to use this code. If I just want to reorder vertices in a mesh, it would be better to call a function like
reorder_mesh_verts
than to have to create a geometry component. I'm thinking of the grease pencil operator as another user of this code currently.I had attempt to fix this, what do you think?
@ -0,0 +74,4 @@
offset_indices::build_reverse_offsets(indices, r_offsets);
Array<int> counts(r_offsets.size(), 0);
for (const int64_t index : indices.index_range()) {
Is this not the same as
reverse_indices_in_groups
? Seems it's missing the multithreading from that implementationRight now here performance is not important. So i made this as simple as possible. Size of groups might be different, so general group deduce code have to be used. I might copy functions from #111081, as i did in #115142 though.
@ -0,0 +183,4 @@
Array<int> indices(domain_size);
array_utils::scatter<int>(gathered_indices, mask, indices);
unselected.foreach_index_optimized<int>(GrainSize(2048),
index_mask::masked_fill
This filling by indices, not by constants. This is required to check if result indices are range, and pass this non-gathered next, to copy data (And additional optimization could be to create a mask in copying stage to split copying data from random indices and the copying of memory segments).
@ -85,1 +85,4 @@
template<typename T>
inline void scatter(const Span<T> src,
const IndexMask mask,
const IndexMask mask
->const IndexMask &indices
for consistency with other places in this file@ -86,0 +92,4 @@
BLI_assert(mask.size() == src.size());
BLI_assert(mask.min_array_size() <= dst.size());
mask.foreach_index_optimized<int>(
GrainSize(grain_size), [&](const int index, const int pos) { dst[index] = src[pos]; });
I don't think we can assume the size is less than 2 billion here. Using
int64_t
should be fine@ -0,0 +19,4 @@
#include "DNA_mesh_types.h"
#include "DNA_pointcloud_types.h"
namespace blender::geometry {
Missing the
GEO_reorder.hh
include here@ -0,0 +136,4 @@
dst_mesh.attributes_for_write());
}
static void reorder_mesh_exec(const Mesh &src_mesh,
I'd remove all of the
_exec
suffixes, I don't think they're necessaryJust to separate the two levels of functionality
prepare
/reorder
.Hmm, I didn't expect to see a warning in this case:
@ -85,1 +85,4 @@
template<typename T>
inline void scatter(const Span<T> src,
const IndexMask indices,
const IndexMask indices
->const IndexMask &indices
It is possible to mark copy constructor as an explicit?)
Hmm, if possible that seems like a nice idea