src/rt/oocnn.h

/* 
   =========================================================================
   k-nearest neighbour lookup routines for out-of-core octree data structure
   
   Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
   (c) Lucerne University of Applied Sciences and Arts,
   supported by the Swiss National Science Foundation (SNSF, #147053)
   =========================================================================
   
   $Id: oocnn.h,v 1.14 2015/11/13 18:05:15 taschreg Exp taschreg $
*/


#ifndef OOC_SEARCH_H
   #define OOC_SEARCH_H
   
   #include "oococt.h"
   
   /* Priority queue node for octree lookups */
   typedef struct {
      float       dist2;   /* Record's *SQUARED* distance to query point */
      unsigned    idx;     /* Record's index in queue buffer */
   } OOC_SearchQueueNode;


   /* Priority queue for octree lookups. Note that we explicitly store the
    * NN candidates in a local in-core buffer nnRec for later retrieval
    * without incurring additional disk I/O. */
   typedef struct {
      OOC_SearchQueueNode  *node;
      unsigned             len, tail, recSize;
      void                 *nnRec;
   } OOC_SearchQueue;
   
   
   /* Filter for k-NN search; records are accepted for which func(rec, data)
    * returns nonzero */
   typedef struct {
      int   (*func)(void *rec, void *data);
      void  *data;
   } OOC_SearchFilter;
   

   float OOC_FindNearest (OOC_Octree *oct, OOC_Node *node, 
                          OOC_DataIdx dataIdx, const FVECT org, float size, 
                          const FVECT key, const OOC_SearchFilter *filter, 
                          OOC_SearchQueue *queue, float maxDist2);
   /* Find k nearest neighbours (where k = queue -> len) within a maximum
    * SQUARED distance of maxDist2 around key. Returns the corresponding
    * data records with their SQUARED distances in the search queue 
    * (queue -> node [0] .. queue -> node [queue -> tail - 1]), with the
    * furthest neighbour at the queue head and queue->tail <= queue->len.  
    *
    * This is a recursive function requiring params for the current node:
    * DataIdx is the data offset for records in the current node, which is
    * necessary for implied addressing into the leaf file. Org and size are
    * the origin and size of the current node's bounding box.
    *
    * An optional filter may be specified; if filter != NULL, filter->func()
    * is called for each potential nearest neighbour along with additional
    * data provided by the caller; see OOC_SearchFilter typedef above.  
    *
    * Return value is the SQUARED distance to furthest neighbour on success,
    * else -1 on failure. */          


   float OOC_Find1Nearest (OOC_Octree *oct, OOC_Node *node, 
                           OOC_DataIdx dataIdx, const FVECT org, float size, 
                           const FVECT key, const OOC_SearchFilter *filter, 
                           void *nnRec, float maxDist2);
    /* Find single nearest neighbour within max SQUARED distance maxDist2
     * around key and copy corresponding record in nnRec. This is an
     * optimised version of OOC_FindNearest() without a search queue */
    
    
    int OOC_InitNearest (OOC_SearchQueue *squeue, 
                         unsigned len, unsigned recSize);
    /* Initialise NN search queue of length len and local buffa for records
     * of size recSize; precondition to calling OOC_FindNearest() */
    
    
    void *OOC_GetNearest (const OOC_SearchQueue *queue, unsigned idx);
    /* Return pointer to record at pos idx in search queue after calling
     * OOC_FindNearest() */
#endif
Revision:	2.1
Committed:	Tue May 17 17:39:47 2016 UTC (9 years, 5 months ago) by rschregle
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, rad5R2, rad5R3, rad5R1
Log Message:	Initial import of ooC photon map
#	User	Rev	Content
1	rschregle	2.1	/*
2			=========================================================================
3			k-nearest neighbour lookup routines for out-of-core octree data structure
4
5			Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
6			(c) Lucerne University of Applied Sciences and Arts,
7			supported by the Swiss National Science Foundation (SNSF, #147053)
8			=========================================================================
9
10			$Id: oocnn.h,v 1.14 2015/11/13 18:05:15 taschreg Exp taschreg $
11			*/
12
13
14
15			#ifndef OOC_SEARCH_H
16			#define OOC_SEARCH_H
17
18			#include "oococt.h"
19
20			/* Priority queue node for octree lookups */
21			typedef struct {
22			float dist2; /* Record's SQUARED distance to query point */
23			unsigned idx; /* Record's index in queue buffer */
24			} OOC_SearchQueueNode;
25
26
27			/* Priority queue for octree lookups. Note that we explicitly store the
28			* NN candidates in a local in-core buffer nnRec for later retrieval
29			* without incurring additional disk I/O. */
30			typedef struct {
31			OOC_SearchQueueNode *node;
32			unsigned len, tail, recSize;
33			void *nnRec;
34			} OOC_SearchQueue;
35
36
37			/* Filter for k-NN search; records are accepted for which func(rec, data)
38			* returns nonzero */
39			typedef struct {
40			int (func)(void rec, void *data);
41			void *data;
42			} OOC_SearchFilter;
43
44
45
46			float OOC_FindNearest (OOC_Octree oct, OOC_Node node,
47			OOC_DataIdx dataIdx, const FVECT org, float size,
48			const FVECT key, const OOC_SearchFilter *filter,
49			OOC_SearchQueue *queue, float maxDist2);
50			/* Find k nearest neighbours (where k = queue -> len) within a maximum
51			* SQUARED distance of maxDist2 around key. Returns the corresponding
52			* data records with their SQUARED distances in the search queue
53			* (queue -> node [0] .. queue -> node [queue -> tail - 1]), with the
54			* furthest neighbour at the queue head and queue->tail <= queue->len.
55			*
56			* This is a recursive function requiring params for the current node:
57			* DataIdx is the data offset for records in the current node, which is
58			* necessary for implied addressing into the leaf file. Org and size are
59			* the origin and size of the current node's bounding box.
60			*
61			* An optional filter may be specified; if filter != NULL, filter->func()
62			* is called for each potential nearest neighbour along with additional
63			* data provided by the caller; see OOC_SearchFilter typedef above.
64			*
65			* Return value is the SQUARED distance to furthest neighbour on success,
66			* else -1 on failure. */
67
68
69			float OOC_Find1Nearest (OOC_Octree oct, OOC_Node node,
70			OOC_DataIdx dataIdx, const FVECT org, float size,
71			const FVECT key, const OOC_SearchFilter *filter,
72			void *nnRec, float maxDist2);
73			/* Find single nearest neighbour within max SQUARED distance maxDist2
74			* around key and copy corresponding record in nnRec. This is an
75			* optimised version of OOC_FindNearest() without a search queue */
76
77
78			int OOC_InitNearest (OOC_SearchQueue *squeue,
79			unsigned len, unsigned recSize);
80			/* Initialise NN search queue of length len and local buffa for records
81			* of size recSize; precondition to calling OOC_FindNearest() */
82
83
84			void OOC_GetNearest (const OOC_SearchQueue queue, unsigned idx);
85			/* Return pointer to record at pos idx in search queue after calling
86			* OOC_FindNearest() */
87			#endif