This patch contains the Performance improvement, that was originally contained in D8966.
It improves the performance of the Weld Modifier by a lot. It had a loop with execution time O(N^2) which is now O(N*log(N)) at a bare maximum.
Details
Details
- Reviewers
Germano Cavalcante (mano-wii) - Group Reviewers
Modifiers - Commits
- rB8eda3ddc4f04: Weld Modifier: Performance improvement
Diff Detail
Diff Detail
- Repository
- rB Blender
Event Timeline
Comment Actions
Thanks for the patch indeed it is a considerable improvement:
| patch | 0.000119 sec |
| master | 0.006195 sec |
But some changes here don't seem to be necessary (see inline comments)...
| source/blender/modifiers/intern/MOD_weld.c | ||
|---|---|---|
| 214 | The purpose of this function is to find out if vert_dest_map has been configured correctly without the need for this loop. | |
| 1617 | Why return earlier if the merge_dist value is 0.0f? | |
| 1674 | You can use range_vn_u here. | |
| 1723–1724 | When creating the code, I sought to create/configure the entire weld_mesh object inside the weld_mesh_context_create function (especially because this is the purpose of this function). Unless there are good reasons, I would prefer that all this logic be moved into weld_vert_ctx_alloc_and_setup. | |
Comment Actions
Some thoughts on the comments.
I will now try and make the described new function.
| source/blender/modifiers/intern/MOD_weld.c | ||
|---|---|---|
| 214 | If I would do the idea from the other inline comment with the function, then I could probably change it back. | |
| 1617 | I guess I can move this to the next patch, as there, it is actually kind of important. | |
| 1674 | I would rather use vert_dest_map to be consistent if vm is to short. | |
| 1723–1724 | I was expecting this comment. The problem is line 1721 with that if statement. It's nice to have that there and I want to keep it, but that means the proximity evaluation has to stay before that. Now again, I would move it all inside if overlap would be always necessary, but with the next patch, the variable would not even be initialized in simple mode. What I can do as a better solution is to make a new function before weld_vert_ctx_alloc_and_setup which would create the vertex merge map and would also be able to do different things depending on the settings. Then I could remove vert_groups_map from weld_mesh and pass it along with vert_kill_len as an argument to weld_mesh_context_create instead. | |
| source/blender/modifiers/intern/MOD_weld.c | ||
|---|---|---|
| 1674 | range_vn_u is a function. | |
Comment Actions
- use range_vn_u
- still use vert_dest_map instead of vm
- move proximity checks an vert_dest_map creation into its own function
Comment Actions
Creating a new function is not making the code more readable.
If your intention is to use another method to obtain a vert_dest_map, add a parameter of type bool to the function weld_mesh_context_create to use another method.
If you don't want to pass a BVHTreeOverlap *overlap as a parameter, pass an uint (*overlap)[2] which is the same thing.
I will make a commit based on the ideas in this patch.
Feel free to edit the patch to be a cleanup if necessary.
Comment Actions
Oh wow, I am so sorry, I was too busy thinking ahead... The solution in the commit is obviously what it should have been for this patch. Thanks.