Homec4science
Diffusion RADIANCE Photon Map (pmapmerge) Browse

RadiancePmap/pmapkdt.h
72aafdb47124pmapmerge

Last Change
Raw File

pmapkdt.h
View Options

/*
==================================================================
In-core kd-tree for photon map
Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
(c) Fraunhofer Institute for Solar Energy Systems,
supported by the German Research Foundation
(DFG LU-204/10-2, "Fassadenintegrierte Regelsysteme" (FARESYS))
(c) Lucerne University of Applied Sciences and Arts,
supported by the Swiss National Science Foundation
(SNSF #147053, "Daylight Redirecting Components")
(c) Tokyo University of Science,
supported by the JSPS Grants-in-Aid for Scientific Research
(KAKENHI JP19KK0115, "Three-Dimensional Light Flow")
==================================================================
$Id: pmapkdt.h,v 1.2 2020/04/08 15:14:21 rschregle Exp $
*/
#ifndef PMAPKDT_H
#define PMAPKDT_H
#include "pmapdata.h"
#include "pmapfilt.h"
/* Forward declarations to break dependency loop with pmapdata.h */
struct PhotonMap;
/* k-d tree as linear array of photons */
typedef struct {
Photon *nodes; /* k-d tree as linear array */
} PhotonKdTree;
typedef PhotonKdTree PhotonStorage;
typedef Photon* PhotonIdx;
/* Priority queue node for kd-tree lookups */
typedef struct {
PhotonIdx idx; /* Pointer to photon */
float dist2; /* Photon's SQUARED distance to query point */
} kdT_SearchQueueNode;
typedef struct {
kdT_SearchQueueNode *node;
unsigned len, tail;
} kdT_SearchQueue;
typedef kdT_SearchQueueNode PhotonSearchQueueNode;
typedef kdT_SearchQueue PhotonSearchQueue;
void kdT_Null (PhotonKdTree *kdt);
/* Initialise kd-tree prior to storing photons */
void kdT_BuildPhotonMap (struct PhotonMap *pmap);
/* Build a balanced kd-tree pmap -> store from photons in unsorted
* heapfile pmap -> heap to guarantee logarithmic search times. The heap
* is destroyed on return. */
int kdT_SavePhotons (const struct PhotonMap *pmap, FILE *out);
/* Save photons in kd-tree to file. Return -1 on error, else 0 */
int kdT_LoadPhotons (struct PhotonMap *pmap, FILE *in);
/* Load photons in kd-tree from file. Return -1 on error, else 0 */
void kdT_InitFindPhotons (struct PhotonMap *pmap);
/* Initialise NN search queue prior to calling kdT_FindPhotons() */
float kdT_PutNearest (kdT_SearchQueue *squeue, float d2,
const Photon *photon, const kdT_SearchAttribCallback *attrib
);
/* Insert new photon with SQUARED distance to query point into the search
* priority queue, maintaining the most distant photon at the queue head.
* If the queue is full, the new photon is only inserted if it is closer
* than the queue head.
*
* The search priority queue is represented as a linearised binary tree with
* the root corresponding to the queue head, and the tail corresponding to
* the last leaf.
*
* The optional attrib callback maps photon attributes to their queue nodes
* by calling attrib->findFunc() if attrib != NULL. It enables finding a
* previously enqueued photon and replacing it if the new photon's SQUARED
* distance d2 is lower.
*
* This function returns the new maximum SQUARED distance at the head if the
* search queue is full. Otherwise it returns -1, indicating a maximum for
* the entire queue is as yet undefined.
*/
int kdT_FindPhotons (
struct PhotonMap* pmap, const FVECT pos, const FVECT norm
);
/* Locate pmap -> squeue.len nearest photons to pos with similar normal
* (NULL for volume photons) and return in search queue pmap -> squeue,
* starting with the further photon at pmap -> squeue.node. Return -1
* if none found, else 0. */
int kdT_Find1Photon (
struct PhotonMap* pmap, const FVECT pos, const FVECT norm,
Photon *photon
);
/* Locate single nearest photon to pos with similar normal. Return -1
* if none found, else 0. */
int kdT_GetPhoton (
const struct PhotonMap *pmap, PhotonIdx idx,Photon *photon
);
/* Retrieve photon referenced by idx from kd-tree and return -1 on
* error, else 0. */
Photon *kdT_GetNearestPhoton (
const kdT_SearchQueue *squeue, PhotonIdx idx
);
/* Retrieve photon from NN search queue after OOC_FindPhotons() */
PhotonIdx kdT_FirstPhoton (const struct PhotonMap* pmap);
/* Return pointer to first photon in kd-Tree */
void kdT_Delete (PhotonKdTree *kdt);
/* Self-destruct */
#endif
c4science · Help