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);
}
}
È ancora più lento? http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Subsection_39.5.5 –
@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
Puoi mostrare come stai usando esattamente il kd-tree? Il pacchetto Spatial Sorting descrive molte opzioni ... –