Page MenuHome

Add arbitrary sized kdtree (fix for select co-planar faces T62595)
AbandonedPublic

Authored by Campbell Barton (campbellbarton) on Mar 17 2019, 1:31 PM.

Details

Summary

This is a simple conversion of BLI_kdtree to a version that supports any number of dimensions.

It currently only supports find_nearest (not range_search and other utility functions).

There are some open topics here, so this is a request-for-discussion on how best to resolve the issue.


  • We could solve this by having a template function similar to source/blender/blenlib/intern/list_sort_impl.h to avoid duplicate code. (then define a float[3] and float[4] version).
  • We could solve selecting co-planar faces differently (use a different data-structure for eg).
  • Using a single distance for angle and distance isn't correct, It could pass in a distance callback which could treat components differently.

    OTOH, in practice this patch work well as-is, making select co-planar usable again.

Diff Detail

Repository
rB Blender
Branch
TEMP-FIX-T62595 (branched from master)
Build Status
Buildable 3148
Build 3148: arc lint + arc unit

Event Timeline

Campbell Barton (campbellbarton) retitled this revision from Fix T62595 to Add arbitrary sized kdtree (fix T62595).Mar 17 2019, 1:35 PM
  • Correct plane comparison
Campbell Barton (campbellbarton) retitled this revision from Add arbitrary sized kdtree (fix T62595) to Add arbitrary sized kdtree (fix for select co-planar faces T62595).Mar 17 2019, 1:53 PM
Campbell Barton (campbellbarton) edited the summary of this revision. (Show Details)
  • declare v4 nearest type
Campbell Barton (campbellbarton) edited the summary of this revision. (Show Details)

Abandoning this for now and look into a sharing code for 3D and 4D versions.