CoboCards App FAQ & Wünsche Feedback
Sprache: Deutsch Sprache
Kostenlos registrieren  Login

Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Alle Oberthemen / Informatik / Computergrafik / Schwerpunktkolloquium: Basic Techniques, Geometry Processing, Global Illumination
58
How is the Photon Map stored? How are k-nearest-neighbor queries performed?
kD-Tree
Store photons in a balanced kD-Tree (i.e., a binary tree) with entries . The two child nodes of an inner node are and .

A balanced kD-Tree is constructed by successive median splits.

kD-Tree k-NN Search
Input:
: query point
: root node of subtree to be searched

Global variables:
: priority queue containing k-best search results
: distance from to furthest result in , or if less than results

knn(, ):
    if( is a leaf)
        insert into
        update
    else
        if is left of split plane
            knn(, )
            if distance to split plane
                knn(, )
        else
            knn(, )
            if distance to split plane
                knn(, )

More efficient: Compare squared distances
Neuer Kommentar
Karteninfo:
Autor: janisborn
Oberthema: Informatik
Thema: Computergrafik
Schule / Uni: RWTH Aachen
Ort: Aachen
Veröffentlicht: 18.05.2022

Abbrechen
E-Mail

Passwort

Login    

Passwort vergessen?
Deutsch  English