Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F80293476
oocnn.h
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Fri, Aug 30, 23:52
Size
5 KB
Mime Type
text/x-Algol68
Expires
Sun, Sep 1, 23:52 (2 d)
Engine
blob
Format
Raw Data
Handle
20336894
Attached To
R10977 RADIANCE Photon Map
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
Log In to Comment