Page MenuHome

Improve proportional editing calculation to use a kd-tree when calculating distances.
ClosedPublic

Authored by Alan Troth (Al) on Nov 26 2018, 12:44 AM.

Details

Summary

Improve proportional editing calculation to use a kd-tree when calculating distances.

Diff Detail

Repository
rB Blender
Branch
set_prop_dist_kdtree (branched from master)
Build Status
Buildable 3947
Build 3947: arc lint + arc unit

Event Timeline

Alan Troth (Al) planned changes to this revision.EditedNov 26 2018, 12:48 AM

Since updating to the newest blender2.8 code I'm having crashes transforming uv vertices.

I've also noticed that my code needs to transform vertices to world space in order to compare them across objects. At the moment the code only rotates to world space. (I've been testing mainly in the uv window.)

I'll do a full recompile and get back to this code when I can.

Could you do a performance comparison with a single fairly high poly mesh, with around half the vertices selected?

For changes to internal workings like this we should take care it doesn't introduce performance regressions.

Alan Troth (Al) updated this revision to Diff 16147.EditedJul 1 2019, 5:15 PM

New version of set_prop_dist. Distance calculations are now done in common space (world or proj_vec).

Alan Troth (Al) added a comment.EditedJul 1 2019, 6:00 PM

If this diff isn't suitable, an alternate version of set_prop_dist(...) (which is more of a straight 'N2' multi-object upgrade) can be found here D5163.

Note that at the date of this diff, any objects that are being edited that don't have a vertex selected won't have a TransDataContainer - in other words if an object doesn't have at least one selected vertex it will not be affected by proportional editing.

Timings are from a 2013 computer. Timings from the original code ('N2') and code from D5163 ('new N2') are fairly consistent - which vertices are selected doesn't have much affect on timings. Timings for this diff are affected by which vertices are selected ('kdTree' and 'kdTree Bad Case').

50% vertex selection timings (3D viewport):

Vertex countkdTreekdTree Bad CaseN2new N2
8K0.02s0 .11s0.05s
32K0.17s0.8s1.56s0.57s
128K1.52s11.6s46s9s
512K21s240s143s

A handful of KdTree times for different vertex selections:
128K: 1.37s, 1.52s, 2,3s, 3.4s, and 11.6s when all the selection is on an xz plane.
512K: 6.2s, 21s, 24s, 35s and 240s when all the selection is on an xz plane.

Alan Troth (Al) added a comment.EditedJul 2 2019, 12:01 AM

A few UV Editor results. As a reminder, 'kdTree' is this diff of set_prop_dist(...), 'N2' is the current single object set_prop_dist(...) and 'new N2' is diff at D5163 of set_prop_dist(...).

I didn't try selecting different vertices to see if it affects results.

I used a subdivided plane for my uv tests, the number of vertices in the UV Editor approaches four times that reported by the mesh. So the UV editor is handling nearly 128K vertices for the 32K mesh.

And a few 3D Viewport results.
kdTree timings dovary depending on which vertices are selected.

Campbell Barton (campbellbarton) retitled this revision from Fix transform_conversions.c::set_prop_dist(...) to check all selected vertices when finding nearest selected vertex. to Improve proportional editing calculation to use a kd-tree when calculating distances..Jul 2 2019, 1:48 AM
Campbell Barton (campbellbarton) edited the summary of this revision. (Show Details)

Thanks for the update, added to T63731, to review after 2.80 release.

Alan Troth (Al) planned changes to this revision.Aug 13 2019, 5:17 PM

I'm planning on adding the extra code to fully get multi object proportional editing working.

Alan Troth (Al) retitled this revision from Improve proportional editing calculation to use a kd-tree when calculating distances. to Fix proportional editing so that it works with multi object editing Improve proportional editing calculation to use a kd-tree when calculating distances..Aug 15 2019, 4:24 PM
Alan Troth (Al) retitled this revision from Fix proportional editing so that it works with multi object editing Improve proportional editing calculation to use a kd-tree when calculating distances. to Improve proportional editing calculation to use a kd-tree when calculating distances..Aug 15 2019, 4:27 PM
Alan Troth (Al) requested review of this revision.Aug 15 2019, 4:37 PM

I was planning on adding to this patch to make it a complete 'multi object editing with proportional editing' patch. After second thoughts this patch should probably left as a potential upgrade to set_prop_dist().

A full (clean, no added frills) upgrade to get proportional editing working across multiple objects can be found here D5163. If wanted, this patch can be after.

Alan Troth (Al) edited the summary of this revision. (Show Details)Aug 15 2019, 4:41 PM
This revision is now accepted and ready to land.Aug 16 2019, 10:38 AM