Git Product home page Git Product logo

knn's Introduction

Demo Image

KNN

Simple K-Nearest Neighbour library for Unity, using the 'Dots' technology stack (the Burst compiler and Unity's job system). It uses K-D trees to speed up queries.

It is totally free from managed allocations and can run multi-threaded. The Burst compiler heavily vectorizes the searching code.

The implementation is a heavily modified version of a KD-Tree by viliwonka: https://github.com/viliwonka/KDTree . It only includes a sub-set of functionality however.

As a rough benchmark, here are perf numbers on a i7-770hq, querying the k=10 nearest neighbours, 100.000 times, in 100.000 points

Performance comparison

This shows an approximately ~130x speedup over the original implementation! Note that this is very much apples to oranges though (eg. this is multi-threaded, the original implementation was not); I don't mean to pick on the original at all, but does hopefully it shows this implementation is really fast!

API Overview

// First let's create a random point cloud
var points = new NativeArray<float3>(100000, Allocator.Persistent);
var rand = new Random(123456);
for (int i = 0; i < points.Length; ++i) {
    points[i] = rand.NextFloat3();
}

// Number of neighbours we want to query
const int kNeighbours = 10;
float3 queryPosition = float3.zero;

// Create a container that accelerates querying for neighbours.
// The 2nd argument indicates whether we want to build the tree straight away or not
// Let's hold off on building it a little bit
var knnContainer = new KnnContainer(points, false, Allocator.TempJob);

// Whenever your point cloud changes, you can make a job to rebuild the container:
var rebuildJob = new KnnRebuildJob(knnContainer);
rebuildJob.Schedule().Complete();

// Most basic usage:
// Get 10 nearest neighbours as indices into our points array!
// This is NOT burst accelerated yet! Unity need to implement compiling delegates with Burst
var result = new NativeArray<int>(kNeighbours, Allocator.TempJob);
knnContainer.QueryKNearest(queryPosition, result);

// The result array at this point contains indices into the points array with the nearest neighbours!
Profiler.BeginSample("Simple Query");
// Get a job to do the query.
var queryJob = new QueryKNearestJob(knnContainer, queryPosition, result);

// And just run immediately on the main thread for now. This uses Burst!
queryJob.Schedule().Complete();
Profiler.EndSample();

// Or maybe we want to query neighbours for multiple points.
const int queryPoints = 100000;

// Keep an array of neighbour indices of all points
var results = new NativeArray<int>(queryPoints * kNeighbours, Allocator.TempJob);

// Query at a few random points
var queryPositions = new NativeArray<float3>(queryPoints, Allocator.TempJob);
for (int i = 0; i < queryPoints; ++i) {
    queryPositions[i] = rand.NextFloat3() * 0.1f;
}	

// Fire up job to get results for all points
var batchQueryJob = new QueryKNearestBatchJob(knnContainer, queryPositions, results);

// And just run immediately now. This will run on multiple threads!
batchQueryJob.ScheduleBatch(queryPositions.Length, queryPositions.Length / 32).Complete();

// Or maybe we're interested in a range around eacht query point
var queryRangeResult = new NativeList<int>(Allocator.TempJob);
var rangeQueryJob = new QueryRangeJob(knnContainer, queryPosition, 2.0f, queryRangeResult);

// Store a list of particles in range
var rangeResults = new NativeArray<RangeQueryResult>(queryPoints, Allocator.TempJob);

// And just run immediately on the main thread for now. This uses Burst!
rangeQueryJob.Schedule().Complete();

// Unfortunately, for batch range queries we do need to decide upfront the maximum nr. of neighbours we allow
// This is due to limitation on allocations within a job.
for (int i = 0; i < rangeResults.Length; ++i) {
    rangeResults[i] = new RangeQueryResult(128, Allocator.TempJob);
}

// Fire up job to get results for all points
var batchRange = new QueryRangeBatchJob(knnContainer, queryPositions, 2.0f, rangeResults);

// And just run immediately now. This will run on multiple threads!
batchRange.ScheduleBatch(queryPositions.Length, queryPositions.Length / 32).Complete();

// Now the results array contains all the neighbours!
queryRangeResult.Dispose();
foreach (var r in rangeResults) {
    r.Dispose();
}
rangeResults.Dispose();
knnContainer.Dispose();
queryPositions.Dispose();
results.Dispose();
points.Dispose();
result.Dispose();

Demo

The demo folder contains 2 demos:

  • KnnApiDemo.cs, Illustrates various API usages from a basic to advanced level
  • KnnVisualizationDemo.cs: Illustrates a real scene where particles are colored based on their neighbourhood information. Shows how to dynamically rebuild your container and other advanced API usages

Installation

The project was made as a Unity Package. Just add the git URL to your package manifest and Unity should install it.

knn's People

Contributors

arthurbrussee avatar nezix avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.