2013-02-27 23 views
12

Sto usando l'implementazione KD dell'albero di CGAL (l'ultima) per la ricerca dei vicini più prossimi in serie di punti. E anche Wikipedia e altre risorse sembrano suggerire che gli alberi KD sono la strada da percorrere. Ma in qualche modo sono troppo lenti e Wiki suggerisce anche il loro tempo peggiore di O (n), che è tutt'altro che ideale.Perché gli alberi KD sono così dannatamente lenti per la ricerca del vicino più vicino nei set di punti?

[BEGIN-EDIT] ora sto usando "nanoflann", che è di circa 100-1000 volte più veloce rispetto all'equivalente in CGAL per la ricerca K-vicino di casa. E sto usando "Intel Embree" per raycasting, che è circa 100-200 volte più veloce degli alberi AABB di CGAL. [END-EDIT]

Il mio compito si presenta in questo modo:

Ho un set point enorme, dicono come fino a qualche 100 milioni. punti!! e la loro distribuzione è su superfici di geometria triangolata (sì, un tracciante di fotoni). Quindi si potrebbe dire che la loro distribuzione è 2D nello spazio 3D, perché è sparsa in 3D ma densa quando si guardano le superfici ... Questo potrebbe essere il problema giusto? Perché a mio avviso questo sembra innescare la peggiore performance di un albero KD che probabilmente potrebbe fare molto meglio con i set di punti densi 3D ...

CGAl è abbastanza bravo in quello che fa, quindi ho un po 'di dubbio che la loro implementazione fa schifo. Il loro albero AABB che sto usando per raytracing brucia un miliardo di raytraces in pochi minuti nel terreno ... Questo è notevole credo. Ma il loro albero KD d'altra parte non può nemmeno occuparsi di un mio. punti e 250K campioni (query punto) in qualsiasi momento ragionevole ...

mi si avvicinò con due soluzioni che calci la merda di KD-alberi:

1) utilizzare le mappe di texture per memorizzare i fotoni in un elenco collegato sulla geometria. Questa è sempre un'operazione O (1), poiché è comunque necessario eseguire il raycast ...

2) Utilizzare hashset affettati dipendenti dalla vista. Più è lontano, più gli hash si ottengono. Quindi, in pratica, puoi pensare a un raster 1024x1024x1024 in coordinate NDC, ma con hashset, per risparmiare memoria in aree sparse. Questo ha fondamentalmente una complessità O (1) e può essere parallelizzato in modo efficiente, sia per gli inserti (micro-sharding) che per le query (lock-free).

La soluzione precedente ha lo svantaggio che è quasi impossibile fare una media su elenchi di fotoni vicini, che è importante nelle regioni più scure per evitare il rumore. Quest'ultima soluzione non ha questo problema e dovrebbe essere alla pari con gli alberi KD, solo che ha O (1) performance peggiore, lol.

Quindi cosa ne pensi? Implementazione Bad KD-tree? In caso contrario, c'è qualcosa di "migliore" di un albero KD per le query delimitate più vicine? Voglio dire, non ho nulla contro la mia seconda soluzione di cui sopra, ma una struttura dati "comprovata" che offre prestazioni simili sarebbe più bella!

Grazie!

Ecco il codice (non compilabile però) che ho usato:

#include "stdafx.h" 
#include "PhotonMap.h" 

#pragma warning (push) 
    #pragma warning (disable: 4512 4244 4061) 
    #pragma warning (disable: 4706 4702 4512 4310 4267 4244 4917 4820 4710 4514 4365 4350 4640 4571 4127 4242 4350 4668 4626) 
    #pragma warning (disable: 4625 4265 4371) 

    #include <CGAL/Simple_cartesian.h> 
    #include <CGAL/Orthogonal_incremental_neighbor_search.h> 
    #include <CGAL/basic.h> 
    #include <CGAL/Search_traits.h> 
    #include <CGAL/point_generators_3.h> 

#pragma warning (pop) 

struct PhotonicPoint 
{ 
    float vec[3]; 
    const Photon* photon; 

    PhotonicPoint(const Photon& photon) : photon(&photon) 
    { 
     vec[0] = photon.hitPoint.getX(); 
     vec[1] = photon.hitPoint.getY(); 
     vec[2] = photon.hitPoint.getZ(); 
    } 

    PhotonicPoint(Vector3 pos) : photon(nullptr) 
    { 
     vec[0] = pos.getX(); 
     vec[1] = pos.getY(); 
     vec[2] = pos.getZ(); 
    } 

    PhotonicPoint() : photon(nullptr) { vec[0] = vec[1] = vec[2] = 0; } 

    float x() const { return vec[0]; } 
    float y() const { return vec[1]; } 
    float z() const { return vec[2]; } 
    float& x() { return vec[0]; } 
    float& y() { return vec[1]; } 
    float& z() { return vec[2]; } 

    bool operator==(const PhotonicPoint& p) const 
    { 
     return (x() == p.x()) && (y() == p.y()) && (z() == p.z()) ; 
    } 

    bool operator!=(const PhotonicPoint& p) const 
    { 
     return ! (*this == p); 
    } 
}; 

namespace CGAL 
{ 
    template <> 
    struct Kernel_traits<PhotonicPoint> 
    { 
     struct Kernel 
     { 
      typedef float FT; 
      typedef float RT; 
     }; 
    }; 
} 

struct Construct_coord_iterator 
{ 
    typedef const float* result_type; 

    const float* operator()(const PhotonicPoint& p) const 
    { 
     return static_cast<const float*>(p.vec); 
    } 

    const float* operator()(const PhotonicPoint& p, int) const 
    { 
     return static_cast<const float*>(p.vec+3); 
    } 
}; 

typedef CGAL::Search_traits<float, PhotonicPoint, const float*, Construct_coord_iterator> Traits; 
typedef CGAL::Orthogonal_incremental_neighbor_search<Traits> NN_incremental_search; 
typedef NN_incremental_search::iterator NN_iterator; 
typedef NN_incremental_search::Tree Tree; 


struct PhotonMap_Impl 
{ 
    Tree tree; 

    PhotonMap_Impl(const PhotonAllocator& allocator) : tree() 
    { 
     int counter = 0, maxCount = allocator.GetAllocationCounter(); 
     for(auto& list : allocator.GetPhotonLists()) 
     { 
      int listLength = std::min((int)list.size(), maxCount - counter); 
      counter += listLength; 
      tree.insert(std::begin(list), std::begin(list) + listLength); 
     } 

     tree.build(); 
    } 
}; 

PhotonMap::PhotonMap(const PhotonAllocator& allocator) 
{ 
    impl = std::make_shared<PhotonMap_Impl>(allocator); 
} 

void PhotonMap::Sample(Vector3 where, float radius, int minCount, std::vector<const Photon*>& outPhotons) 
{ 
    NN_incremental_search search(impl->tree, PhotonicPoint(where)); 
    int count = 0; 

    for(auto& p : search) 
    { 
     if((p.second > radius) && (count > minCount) || (count > 50)) 
      break; 

     count++; 
     outPhotons.push_back(p.first.photon); 
    } 

} 
+0

È ancora più lento? http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Subsection_39.5.5 –

+0

@MarcGlisse: Potresti approfondire cosa significhi. Eseguo una triangolazione delauny per ottenere query puntuali veloci? Non sono sicuro che una triangolazione di un miliardo di punti sia fattibile. – thesaint

+1

Puoi mostrare come stai usando esattamente il kd-tree? Il pacchetto Spatial Sorting descrive molte opzioni ... –

risposta

3

Dalla mia esperienza, qualità attuazione varia ampiamente, purtroppo. Tuttavia, non ho mai esaminato l'implementazione della CGAL.

Il caso peggiore per il k-d-tree di solito è quando a causa di modifiche incrementali diventa troppo sbilanciato e deve essere ricaricato.

Tuttavia, in genere tali alberi sono più efficienti quando non si conosce la distribuzione dei dati.

Nel tuo caso sembra che un semplice approccio basato sulla griglia possa essere la scelta migliore. Se vuoi, puoi considerare una texture come una griglia 2d densa. Quindi forse puoi trovare una proiezione 2d in cui una griglia funziona bene e poi intersecare con questa proiezione.

+0

Sapete bene, non avrei mai considerato gli alberi KD se non fossero stati consigliati in un libro sul tracciamento dei fotoni per questo compito. Quindi pensavo che sarebbero stati adatti e mi chiedevo se forse stavo facendo qualcosa di sbagliato! – thesaint

+0

Era un libro pratico o un libro teorico? Inoltre, l'implementazione conta davvero. Ho visto gli alberi di kd esibirsi molto bene, e li ho visti aggiungere poco alla performance, sfortunatamente. –

+0

Il libro ha sicuramente un obiettivo pratico, perché viene fornito con un tracciante di fotoni e utilizza il codice sorgente per illustrare tutte le cose. Ecco perché l'ho comprato;). Ma ovviamente copre anche la teoria in grande dettaglio. Allora, sai una buona implementazione di KD-tree (o implementazione di ricerca di set di punti, dato che non mi interessa il datastructure) ?? – thesaint

9

Le risposte non sono il posto dove porre domande, ma la tua domanda non è una domanda, ma una dichiarazione che fa schifo il kd-tree di CGAL.

lettura 1.8mio punti di un modello di dati geologici, e calcolando i 50 punti clostest per ciascuno di questi punti ha le seguenti prestazioni sul mio Dell Precision, Windows7, 64bit, VC10:

  • lettura dei punti da un file: 10 sec
  • costruzione dell'albero 1,3 sec
  • 1,8 milioni di query che riportano i 50 punti più vicini: 17 sec

avete prestazioni simili. Ti aspetteresti che un albero di kd sia più veloce?

Inoltre, mi sto chiedendo dove sono i tuoi punti di ricerca, cioè vicino alla superficie o vicino allo scheletro.

+0

Sì, questi risultati delle prestazioni (anche se non corrispondono ma sono nella stessa "lega") sono ciò che ottengo . Ed è almeno 1000 volte a rallentare per essere fattibile per me (supponendo che sia scala linearmente fino a 100 milioni di punti, che non sarà LOL) ... – thesaint

+0

Quindi quello che mi serve è 100 milioni. punti (cioè le mie intersezioni raggio già calcolate), 2 milioni. query per FullHD (forse anche multipli di quella per Supersampling/Antialiasing), con vicini illimitati, ma un raggio che è apx. 1/1000 di larghezza della scena, in circa 20 secondi. Tutto il resto è una perdita di tempo, letteralmente. – thesaint

+12

OK. Qualcuno mi spiega cosa diavolo è un mio. È questo un modo bizzarro di rappresentare la metrica 'M', cioè' 1e6', '1,000,000'? Si prega di usare quello. La gente poi ti prenderà sul serio. Ma cosa so. Potrebbe essere una convention locale o qualcosa del genere. –

4

Ho fatto qualche ricerca sulle implementazioni veloci di KD-tree alcuni mesi fa, e sono d'accordo con Anony-Mousse che la qualità (e il "peso" delle librerie) varia fortemente. Ecco alcuni dei miei risultati:

kdtree2 è un'implementazione di KD-tree poco conosciuta e abbastanza semplice che ho trovato essere abbastanza veloce per i problemi 3D, specialmente se gli permetti di copiare e riordinare i tuoi dati. Inoltre, è piccolo e molto facile da incorporare e adattare. Here è un documento sull'attuazione da parte dell'autore (non lasciatevi scoraggiare dalla menzione di Fortran nel titolo). Questa è la libreria che ho finito usando. I miei colleghi hanno confrontato la sua velocità per i punti 3D contro gli alberi KD-VLFeat's e un'altra libreria che non ricordo (molti FLANN, vedi sotto) e ha vinto.

FLANN ha una reputazione di essere veloce, e viene utilizzato e consigliato abbastanza spesso di recente. Mira al caso di dimensione superiore, dove offre algoritmi approssimativi, ma è anche usato nel Point Cloud Library che si occupa di problemi 3D.

Non ho sperimentato con CGAL da quando ho trovato la libreria troppo pesante. Sono d'accordo sul fatto che CGAL abbia una buona reputazione, ma ritengo che a volte soffra di eccessiva somiglianza.

+0

Grazie per questa panoramica! Ma penso che il problema risieda nella struttura dei dati, non nella sua implementazione. Quindi lo stesso albero KD sembra essere troppo lento, indipendentemente da quanto bene lo si implementa (in genere si guadagna comunque un fattore costante). – thesaint

0

Date un'occhiata a biblioteca ApproxMVBB nei termini della licenza MPL:

https://github.com/gabyx/ApproxMVBB:

L'implementazione kdTree dovrebbe essere paragonabile a PCL (FLANN) e potrebbe essere ancora più veloce. (i test con PCL sembravano essere più veloci con la mia implementazione!)

Diclaimer: io sono il proprietario di questa libreria e in nessun modo questa libreria afferma di essere più veloce e non sono state ancora eseguite prove di prestazioni serie, ma sono usando questa libreria con successo in dinamiche di corpo rigido granulare dove la velocità è il re! Tuttavia, questa libreria è molto piccola, e l'implementazione di kdTree è molto generica (vedi gli esempi) e ti consente di suddividere in modo personalizzato heurstics e altre cose fantastiche :-).

Miglioramenti e considerazioni simili a quelli del nanoflann (accesso diretto ai dati ecc., Dati generici, n-dimensionali) sono implementati ... (vedere l'intestazione KdTree.hpp).

Alcune Aggiornamenti sul Timing:
L'esempio kdTreeFiltering contiene alcuni piccoli punti di riferimento: Il coniglio Standord con 35947 punti viene caricata (esempio completamente funzionante nel repository dalla scatola):

I risultati :

Bunny.txt

Loaded: 35947 points 
KDTree:: Exotic point traits , Vector3* + id, start: ===== 
KdTree build took: 3.1685ms. 
Tree Stats: 
    nodes  : 1199 
    leafs  : 600 
    tree level : 11 
    avg. leaf data size : 29.9808 
    min. leaf data size : 0 
    max. leaf data size : 261 
    min. leaf extent : 0.00964587 
    max. leaf extent : 0.060337 
SplitHeuristics Stats: 
    splits   : 599 
    avg. split ratio (0,0.5] : 0.5 
    avg. point ratio [0,0.5] : 0.22947 
    avg. extent ratio (0,1] : 0.616848 
    tries/calls  : 599/716 = 0.836592 
Neighbour Stats (if computed): 

    min. leaf neighbours : 6 
    max. leaf neighbours : 69 
    avg. leaf neighbours : 18.7867 
(Built with methods: midpoint, no split heuristic optimization loop) 


Saving KdTree XML to: KdTreeResults.xml 
KDTree:: Simple point traits , Vector3 only , start: ===== 
KdTree build took: 18.3371ms. 
Tree Stats: 
    nodes  : 1199 
    leafs  : 600 
    tree level : 10 
    avg. leaf data size : 29.9808 
    min. leaf data size : 0 
    max. leaf data size : 306 
    min. leaf extent : 0.01 
    max. leaf extent : 0.076794 
SplitHeuristics Stats: 
    splits   : 599 
    avg. split ratio (0,0.5] : 0.448302 
    avg. point ratio [0,0.5] : 0.268614 
    avg. extent ratio (0,1] : 0.502048 
    tries/calls  : 3312/816 = 4.05882 
Neighbour Stats (if computed): 

    min. leaf neighbours : 6 
    max. leaf neighbours : 43 
    avg. leaf neighbours : 21.11 
(Built with methods: midpoint, median,geometric mean, full split heuristic optimization) 

Lucy.txt modello con 14 milioni di punti:

Loaded: 14027872 points 
KDTree:: Exotic point traits , Vector3* + id, start: ===== 
KdTree build took: 3123.85ms. 
Tree Stats: 
     nodes  : 999999 
     leafs  : 500000 
     tree level : 25 
     avg. leaf data size : 14.0279 
     min. leaf data size : 0 
     max. leaf data size : 159 
     min. leaf extent : 2.08504 
     max. leaf extent : 399.26 
SplitHeuristics Stats: 
     splits   : 499999 
     avg. split ratio (0,0.5] : 0.5 
     avg. point ratio [0,0.5] : 0.194764 
     avg. extent ratio (0,1] : 0.649163 
     tries/calls  : 499999/636416 = 0.785648 
(Built with methods: midpoint, no split heuristic optimization loop) 

KDTree:: Simple point traits , Vector3 only , start: ===== 
KdTree build took: 7766.79ms. 
Tree Stats: 
    nodes  : 1199 
    leafs  : 600 
    tree level : 10 
    avg. leaf data size : 11699.6 
    min. leaf data size : 0 
    max. leaf data size : 35534 
    min. leaf extent : 9.87306 
    max. leaf extent : 413.195 
SplitHeuristics Stats: 
    splits   : 599 
    avg. split ratio (0,0.5] : 0.297657 
    avg. point ratio [0,0.5] : 0.492414 
    avg. extent ratio (0,1] : 0.312965 
    tries/calls  : 5391/600 = 8.985 
Neighbour Stats (if computed): 

    min. leaf neighbours : 4 
    max. leaf neighbours : 37 
    avg. leaf neighbours : 12.9233 
(Built with methods: midpoint, median,geometric mean, full split heuristic optimization) 

prendere a cuore l'interpretazione! e guarda le impostazioni utilizzate nell'esempio File. Tuttavia a confronto con i risultati di altre persone: ~ 3100ms per 14 * 10⁶ punti è abbastanza liscia :-)

processore utilizzato: Intel® Core ™ i7 CPU 970 @ 3.20GHz × 12, 12GB di Ram

+0

puoi dare un test, quanto tempo ci vuole in ms, con numero di punti, la tua cpu, sistema ecc. –

+0

questo dipende molto dal caso d'uso per la tua applicazione, se vuoi una semplice suddivisione del punto medio, senza pazzesca suddivisione heurisitc Ottimizzazione, quindi è molto fastern quindi valutando la migliore tecnica di split per ogni potenziale split, è possibile compilare l'esempio nel progetto (ho aggiunto qualche funzione di timeing, il modello di Lucy è incluso nel sottomodulo e per testare 14 milioni di punti) Ho aggiornato la risposta un po ' – Gabriel

0

Se il kdtree è veloce per piccoli set, ma "lento" per set di grandi dimensioni (> 100000?), potresti soffrire di svuotamento delle cache del processore. Se i nodi principali sono interlacciati con nodi foglia usati raramente, si installeranno meno nodi molto utilizzati nelle cache del processore. Questo può essere migliorato riducendo al minimo la dimensione dei nodi e il layout accurato dei nodi nella memoria .. ma alla fine arriverete comunque a un buon numero di nodi. Si può finire con l'accesso alla memoria principale essendo il collo a bottiglia.

Valgrind mi dice che una versione del mio codice è del 5% in meno di istruzioni, ma credo che il cronometro indichi che è circa il 10% più lento per lo stesso input. Sospetto che valgrind fare una simulazione di cache completa mi dica la risposta giusta.

Se si dispone di multi-thread, si consiglia di incoraggiare i thread a eseguire ricerche in aree simili per riutilizzare la cache ... che presuppone un singolo processore multi-core: più processori potrebbero desiderare l'approccio opposto.

Suggerimento: si impacchettano più indici a 32 bit in memoria rispetto ai puntatori a 64 bit.