Page MenuHomec4science
Files F60015400

oocnn.h
No OneTemporary
Actions

File Metadata

Created
Fri, Apr 26, 20:11

oocnn.h
View Options

/*
=========================================================================
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, "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: oocnn.h,v 1.2 2020/11/10 01:15:09 u-no-hoo Exp u-no-hoo $
*/
#ifndef OOC_SEARCH_H
#define OOC_SEARCH_H
#include "oococt.h"
/* Priority queue node for octree lookups */
typedef struct {
float dist2; /* Record's distance^2 to query point */
unsigned idx; /* Record's index in queue buffer */
#ifdef OOC_NN_RECIDX
OOC_DataIdx recIdx; /* Record's absolute index */
#endif
} 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;
/* Requires above typedefs */
#include "pmapfilt.h"
float OOC_FindNearest (
OOC_Octree *oct, OOC_Node *node, OOC_DataIdx dataIdx,
const FVECT org, float size, const FVECT key,
const OOC_SearchFilterCallback *filter,
const OOC_SearchAttribCallback *attrib,
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.
*
* This function accepts two optional callbacks for selective search:
* /SHALL MODE ON
*
* -- If filter != NULL, filter->filtFunc() is called for each candidate
* nearest neighbour along with the encapsulated state data provided
* by the caller; records SHALL be accepted if filter->filtFunc()
* returns nonzero.
*
* -- If attrib != NULL, attrib->findFunc() is called for each candidate
* nearest neighbour that has been accepted by filter->filtFunc() and
* will therefore be added to the search queue.
* This function SHALL map a record attribute to its search queue node
* via a lookup table ("attribute map") accessible via attrib->state,
* and SHALL return a modifiable pointer to the corresponding search
* queue node, or NULL if the attribute is absent.
* This callback SHALL support replacing a previously enqueued record
* with the candidate if they share the same attribute and the latter
* is closer to the key; this avoids accumulating records with
* duplicate attributes in the queue, which may be desirable in some
* applications. Or not. Maybe not.
* This callback SHALL also support updating the attribute map entry
* for each resorted record when restoring the priority queue property
* during insertions; the search queue nodes referenced in the
* attribute map are directly modified by dereferencing the returned
* pointers.
* In addition, the callbacks attrib->addFunc() and attrib->delFunc()
* SHALL insert new entries into the attribute map, or delete evicted
* ones once the search queue is full.
*
* /SHALL MODE OFF
* We use the word "SHALL" a lot here 'cos Lars likes it and it sounds
* very imposing and professional and stuff.
*
* This function returns -1 on failure, else a positive value on success.
* The maximum (squared) distance to the found neighours can be obtained
* from the head of the search queue, queue -> node [0].dist2.
* (Note this will only coincide with the return value if the queue is
* full, so this value should not be relied on!). */
float OOC_Find1Nearest (
OOC_Octree *oct, OOC_Node *node, OOC_DataIdx dataIdx,
const FVECT org, float size, const FVECT key,
const OOC_SearchFilterCallback *filter, void *nnRec,
OOC_DataIdx *nnIdx, float maxDist2
);
/* Find single nearest neighbour within max SQUARED distance maxDist2
* around key and copy corresponding record in nnRec, and return its
* index in nnIdx (if nnIdx != NULL). 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

Event Timeline

c4science · Help