src/rt/pmapkdt.h

/* 
   ==================================================================
   In-core kd-tree for photon map

   Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
   (c) Fraunhofer Institute for Solar Energy Systems,
   (c) Lucerne University of Applied Sciences and Arts,
   supported by the Swiss National Science Foundation (SNSF, #147053)
   ==================================================================
   
   $Id: pmapkdt.h,v 1.1 2016/05/18 08:22:45 rschregle Exp $
*/


#ifndef PMAPKDT_H
   #define PMAPKDT_H

/*   #include <stdio.h>
   #include "fvect.h" */
   #include "pmapdata.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() */
   
   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 PhotonSearchQueue *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
Revision:	1.2
Committed:	Wed Apr 8 15:14:21 2020 UTC (4 years, 1 month ago) by rschregle
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, rad5R3, HEAD
Changes since 1.1:	+11 -9 lines
Log Message:	Fixed est00pid bug in single photon lookups that returned junk when none found, added code to detect and handle (ignore).
#	User	Rev	Content
1	rschregle	1.1	/*
2			==================================================================
3			In-core kd-tree for photon map
4
5			Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
6			(c) Fraunhofer Institute for Solar Energy Systems,
7			(c) Lucerne University of Applied Sciences and Arts,
8			supported by the Swiss National Science Foundation (SNSF, #147053)
9			==================================================================
10
11	rschregle	1.2	$Id: pmapkdt.h,v 1.1 2016/05/18 08:22:45 rschregle Exp $
12	rschregle	1.1	*/
13
14
15			#ifndef PMAPKDT_H
16			#define PMAPKDT_H
17
18			/* #include <stdio.h>
19			#include "fvect.h" */
20			#include "pmapdata.h"
21
22
23			/* Forward declarations to break dependency loop with pmapdata.h */
24			struct PhotonMap;
25
26
27			/* k-d tree as linear array of photons */
28			typedef struct {
29			Photon nodes; / k-d tree as linear array */
30			} PhotonKdTree;
31
32			typedef PhotonKdTree PhotonStorage;
33			typedef Photon* PhotonIdx;
34
35			/* Priority queue node for kd-tree lookups */
36			typedef struct {
37			PhotonIdx idx; /* Pointer to photon */
38			float dist2; /* Photon's SQUARED distance to query point */
39			} kdT_SearchQueueNode;
40
41			typedef struct {
42			kdT_SearchQueueNode *node;
43			unsigned len, tail;
44			} kdT_SearchQueue;
45
46			typedef kdT_SearchQueueNode PhotonSearchQueueNode;
47			typedef kdT_SearchQueue PhotonSearchQueue;
48
49
50
51			void kdT_Null (PhotonKdTree *kdt);
52			/* Initialise kd-tree prior to storing photons */
53
54			void kdT_BuildPhotonMap (struct PhotonMap *pmap);
55			/* Build a balanced kd-tree pmap -> store from photons in unsorted
56			* heapfile pmap -> heap to guarantee logarithmic search times. The heap
57			* is destroyed on return. */
58
59			int kdT_SavePhotons (const struct PhotonMap pmap, FILE out);
60			/* Save photons in kd-tree to file. Return -1 on error, else 0 */
61
62			int kdT_LoadPhotons (struct PhotonMap pmap, FILE in);
63			/* Load photons in kd-tree from file. Return -1 on error, else 0 */
64
65			void kdT_InitFindPhotons (struct PhotonMap *pmap);
66			/* Initialise NN search queue prior to calling kdT_FindPhotons() */
67
68	rschregle	1.2	int kdT_FindPhotons (struct PhotonMap* pmap, const FVECT pos,
69			const FVECT norm);
70	rschregle	1.1	/* Locate pmap -> squeue.len nearest photons to pos with similar normal
71			* (NULL for volume photons) and return in search queue pmap -> squeue,
72	rschregle	1.2	* starting with the further photon at pmap -> squeue.node. Return -1
73			* if none found, else 0. */
74	rschregle	1.1
75	rschregle	1.2	int kdT_Find1Photon (struct PhotonMap* pmap, const FVECT pos,
76			const FVECT norm, Photon *photon);
77			/* Locate single nearest photon to pos with similar normal. Return -1
78			* if none found, else 0. */
79	rschregle	1.1
80			int kdT_GetPhoton (const struct PhotonMap *pmap, PhotonIdx idx,
81			Photon *photon);
82	rschregle	1.2	/* Retrieve photon referenced by idx from kd-tree and return -1 on
83			* error, else 0. */
84	rschregle	1.1
85			Photon kdT_GetNearestPhoton (const PhotonSearchQueue squeue,
86			PhotonIdx idx);
87			/* Retrieve photon from NN search queue after OOC_FindPhotons() */
88
89			PhotonIdx kdT_FirstPhoton (const struct PhotonMap* pmap);
90			/* Return pointer to first photon in kd-Tree */
91
92			void kdT_Delete (PhotonKdTree *kdt);
93			/* Self-destruct */
94
95			#endif