Merge by Distance node re-indexes points non-determinstically. #107306

New Issue

Closed

opened 2023-04-24 17:52:57 +02:00 by Mike · 14 comments

Mike commented

2023-04-24 17:52:57 +02:00

Blender Version
Broken: 5.0, 2023-03-29

The indexes of points are seemingly randomly changed, when using merge by distance. This completely breaks using indexes for selection after a merge by distance.

In the blend file attached, Change the index of the "sample index" to any number 4-8 and all the index numbers are as expected. Set to 0-3 and it shuffles the indexes around. You can see in the 2nd Set Position node, I have "Index = 7" as selection, and when changing number in "sample index" node, it changes which node is at index 7.

In my working project (not included), even something where changing the position of some arbitrary point not being merged (before the merge node) changes the index numbering after the merge node.

It'll be the same number of points, in the same position, just in a different order... breaking any use of selection "index = X".

**Blender Version** Broken: 5.0, 2023-03-29 The indexes of points are seemingly randomly changed, when using merge by distance. This completely breaks using indexes for selection after a merge by distance. In the blend file attached, Change the index of the "sample index" to any number 4-8 and all the index numbers are as expected. Set to 0-3 and it shuffles the indexes around. You can see in the 2nd Set Position node, I have "Index = 7" as selection, and when changing number in "sample index" node, it changes which node is at index 7. In my working project (not included), even something where changing the position of some arbitrary point *not being merged* (before the merge node) changes the index numbering after the merge node. It'll be the same number of points, in the same position, just in a different order... breaking any use of selection "index = X".

bug 9.blend

894 KiB

Mike added the

labels 2023-04-24 17:52:58 +02:00

Iliya Katushenock added the

Nodes & Physics

labels 2023-04-24 18:10:42 +02:00

Iliya Katushenock commented

2023-04-24 18:42:02 +02:00

Member

Hello, thanks for the report. While I can confirm this behavior, it's not a bug.

This node must resize the point domain randomly and in random order.
Because of this, some deterministic reindexing options can be added, but this is not a real feature that is expected or should be. Basically, expected to use attributes as a way to carry data in a deterministic way.

NOTE: That you can sample associatively (by and index captured as an attribute) using nodes. To unify this, there is this project #103457.

Of course, if this is possible without losing speed, it would be nice to have it. But for now, this report can be considered a feature/improvement request. For this kind of thing, please use: https://wiki.blender.org/wiki/Communication/Contact#User_Feedback_and_Requests

For more information on why this isn't considered a bug, visit: https://wiki.blender.org/wiki/Reference/Not_a_bug

Hello, thanks for the report. While I can confirm this behavior, it's not a bug. This node must resize the point domain randomly and in random order. Because of this, some deterministic reindexing options can be added, but this is not a real feature that is expected or should be. Basically, expected to use attributes as a way to carry data in a deterministic way. _NOTE:_ That you can sample associatively (by and index captured as an attribute) using nodes. To unify this, there is this project https://projects.blender.org/blender/blender/issues/103457. Of course, if this is possible without losing speed, it would be nice to have it. But for now, this report can be considered a feature/improvement request. For this kind of thing, please use: https://wiki.blender.org/wiki/Communication/Contact#User_Feedback_and_Requests For more information on why this isn't considered a bug, visit: https://wiki.blender.org/wiki/Reference/Not_a_bug

Iliya Katushenock closed this issue

2023-04-24 18:42:04 +02:00

Blender Bot added

and removed

labels 2023-04-24 18:42:05 +02:00

Mike commented

2023-04-24 20:00:57 +02:00

Author

Its a bug because the behavior of a node is inconsistent and unexpected.
To be clear, I can't continue on any of my projects until this bug gets fixed. They all rely upon merge by distance and index selection. :(

Why can't the node just keep the earlier indexes during the merge, then keep them all in the same order?

If I merge index 4 with Index 8, it should always keep 4 and get rid of 8. This is exactly what it does in the example file when sample index is set at 4-8.
However, when I merge index 3 with 8... it deletes 3.

Just changing this one thing would fix the issue. If it has the same points in the same order, it should deterministically delete the same index. It shouldn't be based on position or any other attribute.

There's no reason why it should sometimes delete the lower index and sometimes delete the higher index.

Its a bug because the behavior of a node is inconsistent and unexpected. To be clear, I can't continue on any of my projects until this bug gets fixed. They all rely upon merge by distance and index selection. :( Why can't the node just keep the earlier indexes during the merge, then keep them all in the same order? If I merge index 4 with Index 8, it should always keep 4 and get rid of 8. This is exactly what it does in the example file when sample index is set at 4-8. However, when I merge index 3 with 8... it deletes 3. Just changing this one thing would fix the issue. If it has the same points in the same order, it should deterministically delete the same index. It shouldn't be based on position or any other attribute. There's no reason why it should sometimes delete the lower index and sometimes delete the higher index.

Mike reopened this issue

2023-04-24 20:00:59 +02:00

Blender Bot added

and removed

labels 2023-04-24 20:01:00 +02:00

Mike commented

2023-04-24 20:03:23 +02:00

Author

"This node must resize the point domain randomly and in random order."
This does not happen. It's not in a random order.
It's in the same order, but some times it deletes the lower index, some times the higher index. Just making this consistent would fix the bug.

"This node must resize the point domain randomly and in random order." This does not happen. It's not in a random order. It's in the same order, but some times it deletes the lower index, some times the higher index. Just making this consistent would fix the bug.

Iliya Katushenock commented

2023-04-24 20:08:57 +02:00

Member

With this you can get around your problem I hope.

The problem is that you relied on non-deterministic behavior.
Indexing is not what it should be. If someone wants to do it, that's fine. But that's not what is a bug.

With this you can get around your problem I hope. ![image](/attachments/29dfd3bf-7e8a-4cde-97d1-04a12a3cd021) The problem is that you relied on non-deterministic behavior. Indexing is not what it should be. If someone wants to do it, that's fine. But that's not what is a bug.

85 KiB

Iliya Katushenock closed this issue

2023-04-24 20:08:59 +02:00

Blender Bot added

and removed

labels 2023-04-24 20:09:01 +02:00

Mike commented

2023-04-24 20:16:21 +02:00

Author

With this you can get around your problem I hope.

The problem is that you relied on non-deterministic behavior.
Indexing is not what it should be. If someone wants to do it, that's fine. But that's not what is a bug.

Though that is wrong, I get the jist, however this would be impossibly slow as I'd have to do it thousands of times.

"The problem is that you relied on non-deterministic behavior." But it shouldn't be non-deterministic.... that's the bug.

If you have point 0 and point 2 being merged, it shouldn't randomly pick 0 sometimes and 2 other times. This is something that can and should be consistent. I'll dig around in the code and see if I can find a solution.

> With this you can get around your problem I hope. > ![image](/attachments/29dfd3bf-7e8a-4cde-97d1-04a12a3cd021) > > The problem is that you relied on non-deterministic behavior. > Indexing is not what it should be. If someone wants to do it, that's fine. But that's not what is a bug. Though that is wrong, I get the jist, however this would be impossibly slow as I'd have to do it thousands of times. "The problem is that you relied on non-deterministic behavior." But it shouldn't be non-deterministic.... that's the bug. If you have point 0 and point 2 being merged, it shouldn't randomly pick 0 sometimes and 2 other times. This is something that can and should be consistent. I'll dig around in the code and see if I can find a solution.

Iliya Katushenock commented

2023-04-24 20:19:28 +02:00

Member

@MMMM This is not stated in the documentation. And I can't read minds, but for some reason it seems that this was not planned.
You MUST do this with attributes, since copying always be determinate.

@MMMM This is not stated in the documentation. And I can't read minds, but for some reason it seems that this was not planned. You MUST do this with attributes, since copying always be determinate.

Mike commented

2023-04-24 21:01:06 +02:00

Author

a649ff7b98/source/blender/geometry/intern/mesh_merge_by_distance.cc (L1740)

Change "False" to "True". That fixes this bug.

https://github.com/blender/blender/blob/a649ff7b983f181360bf86c81e8f85e7979a4db6/source/blender/geometry/intern/mesh_merge_by_distance.cc#L1740 Change "False" to "True". That fixes this bug.

Mike reopened this issue

2023-04-24 21:01:08 +02:00

Blender Bot added

and removed

labels 2023-04-24 21:01:09 +02:00

Mike commented

2023-04-24 21:02:40 +02:00

Author

BLI_kdtree_calc_duplicates_fast is already written to send in the results in the correct order. It just has to be enabled for the Merge by distance node.

int BLI_kdtree_calc_duplicates_fast(
        const KDTree *tree, const float range, bool use_index_order,
        int *doubles);

`BLI_kdtree_calc_duplicates_fast` is already written to send in the results in the correct order. It just has to be enabled for the Merge by distance node. ```Cpp int BLI_kdtree_calc_duplicates_fast( const KDTree *tree, const float range, bool use_index_order, int *doubles); ````

Iliya Katushenock commented

2023-04-24 21:14:50 +02:00

Member

Loop over the coordinates ordered by #KDTreeNode.index. At the expense of some performance, this ensures the layout of the tree doesn't influence the iteration order.

Not sure if only for your case, this node have to be slower.

```Cpp Loop over the coordinates ordered by #KDTreeNode.index. At the expense of some performance, this ensures the layout of the tree doesn't influence the iteration order. ``` Not sure if only for your case, this node have to be slower.

Iliya Katushenock commented

2023-04-24 21:16:16 +02:00

Member

Just use the attributes, they already give you that, and no one will suffer performance but you.

Just use the attributes, they already give you that, and no one will suffer performance but you.

Iliya Katushenock closed this issue

2023-04-24 21:16:18 +02:00

Blender Bot added

and removed

labels 2023-04-24 21:16:19 +02:00

Mike commented

2023-04-24 21:16:34 +02:00

Author

Loop over the coordinates ordered by #KDTreeNode.index. At the expense of some performance, this ensures the layout of the tree doesn't influence the iteration order.

Not sure if only for your case, this node have to be slower.

Add bool option so the node user gets to choose would be the best of both worlds. ^_^

> ```Cpp > Loop over the coordinates ordered by #KDTreeNode.index. At the expense of some performance, this ensures the layout of the tree doesn't influence the iteration order. > ``` > Not sure if only for your case, this node have to be slower. Add bool option so the node user gets to choose would be the best of both worlds. ^_^

Iliya Katushenock commented

2023-04-24 21:19:20 +02:00

Member

This is a feature request.

This is a feature request.

Iliya Katushenock commented

2023-04-24 21:45:47 +02:00

Member

Hans said that nodes should have deterministic behavior, so this can be considered a bug.
After a light build: the performance drop is hard to find, seems to be quite low indeed.
So this is being confirmed and will be fixed, thanks for the report and perseverance.

Hans said that nodes should have deterministic behavior, so this can be considered a bug. After a light build: the performance drop is hard to find, seems to be quite low indeed. So this is being confirmed and will be fixed, thanks for the report and perseverance.

👍 1 ❤️ 1

Iliya Katushenock reopened this issue

2023-04-24 21:45:49 +02:00

Blender Bot added

and removed

labels 2023-04-24 21:45:50 +02:00

Iliya Katushenock added

Nodes & Physics

and removed

Nodes & Physics

labels 2023-04-24 21:46:12 +02:00

Mike commented

2023-04-24 21:55:00 +02:00

Author

Hans said that nodes should have deterministic behavior, so this can be considered a bug.
After a light build: the performance drop is hard to find, seems to be quite low indeed.
So this is being confirmed and will be fixed, thanks for the report and perseverance.

There was a "bug fix" about 6 years ago that changed the "Meld Modifier" to be "false" because it cause crashes.
I believe I have a solution to that as well, if ti reoccurs:
If there this causes a crash caused by accessing a index that's already been deleted, this can be fixed by setting Some Variable to "tree->nodes_len" then I to in the loop, the inside the loop, subtracting the number of removed indexes from .

ae7c71ef09/source/blender/blenlib/intern/kdtree_impl.h (L889)

I'd typed up a nice long Feature request... and got a notification that you'd reopened it before I could submit. ^_^

And thanks for Checking with Hans.

> Hans said that nodes should have deterministic behavior, so this can be considered a bug. > After a light build: the performance drop is hard to find, seems to be quite low indeed. > So this is being confirmed and will be fixed, thanks for the report and perseverance. There was a "bug fix" about 6 years ago that changed the "Meld Modifier" to be "false" because it cause crashes. I believe I have a solution to that as well, if ti reoccurs: If there this causes a crash caused by accessing a index that's already been deleted, this can be fixed by setting Some Variable to "tree->nodes_len" then I to <Some Variable> in the loop, the inside the loop, subtracting the number of removed indexes from <Some Variable>. https://github.com/blender/blender/blob/ae7c71ef09029a1fbadc0f4813ee233cdf2ee6b7/source/blender/blenlib/intern/kdtree_impl.h#L889 I'd typed up a nice long Feature request... and got a notification that you'd reopened it before I could submit. ^_^ And thanks for Checking with Hans.

Iliya Katushenock referenced a pull request that will close this issue

2023-04-24 21:57:56 +02:00

Fix #107306: Merge by distance node is not deterministic #107312

Hans Goudey referenced this issue from a commit

2023-05-01 22:15:25 +02:00

Fix #107306: Merge by distance node is not deterministic

Hans Goudey closed this issue

2023-05-01 22:15:27 +02:00

Blender Bot added

and removed

labels 2023-05-01 22:15:28 +02:00

Sign in to join this conversation.

No Label

Animation & Rigging

Asset Browser Project Overview

Automated Testing

Blender Asset Bundle

Dependency Graph

Development Management

EEVEE & Viewport

Images & Movies

Motion Tracking

Nodes & Physics

Pipeline, Assets & IO

Platforms, Builds & Tests

Render & Cycles

Render Pipeline

Sculpt, Paint & Texture

Video Sequencer

Virtual Reality

Blender 2.8 Project

Milestone 1: Basic, Local Asset Browser

Good First Issue

Animation & Rigging

Development Management

EEVEE & Viewport

Nodes & Physics

Pipeline, Assets & IO

Platforms, Builds & Tests

Render & Cycles

Sculpt, Paint & Texture

Needs Info from Developers

Needs Information from User

No Milestone

No project

No Assignees

2 Participants

Notifications

Due Date

The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: blender/blender#107306

No description provided.