src/common/hilbert.h

/* C header file for Hilbert curve functions */
#if !defined(_hilbert_h_)
#define _hilbert_h_

#ifdef __cplusplus
extern "C" {
#endif

/* define the bitmask_t type as an integer of sufficient size */
typedef unsigned long long bitmask_t;
/* define the halfmask_t type as an integer of 1/2 the size of bitmask_t */
typedef unsigned long halfmask_t;

/*****************************************************************
 * hilbert_i2c
 * 
 * Convert an index into a Hilbert curve to a set of coordinates.
 * Inputs:
 *  nDims:      Number of coordinate axes.
 *  nBits:      Number of bits per axis.
 *  index:      The index, contains nDims*nBits bits (so nDims*nBits must be <= 8*sizeof(bitmask_t)).
 * Outputs:
 *  coord:      The list of nDims coordinates, each with nBits bits.
 * Assumptions:
 *      nDims*nBits <= (sizeof index) * (bits_per_byte)
 */

void hilbert_i2c(unsigned nDims, unsigned nBits, bitmask_t index, bitmask_t coord[]);

/*****************************************************************
 * hilbert_c2i
 * 
 * Convert coordinates of a point on a Hilbert curve to its index.
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBits:      Number of bits/coordinate.
 *  coord:      Array of n nBits-bit coordinates.
 * Outputs:
 *  index:      Output index value.  nDims*nBits bits.
 * Assumptions:
 *      nDims*nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */

bitmask_t hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[]);

/*****************************************************************
 * hilbert_cmp, hilbert_ieee_cmp
 * 
 * Determine which of two points lies further along the Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBytes:     Number of bytes of storage/coordinate (hilbert_cmp only)
 *  nBits:      Number of bits/coordinate. (hilbert_cmp only)
 *  coord1:     Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
 *  coord2:     Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
 * Return value:
 *      -1, 0, or 1 according to whether
           coord1<coord2, coord1==coord2, coord1>coord2
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */

int hilbert_cmp(unsigned nDims, unsigned nBytes, unsigned nBits, void const* coord1, void const* coord2);
int hilbert_ieee_cmp(unsigned nDims, double const* coord1, double const* coord2);

/*****************************************************************
 * hilbert_box_vtx
 * 
 * Determine the first or last vertex of a box to lie on a Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBytes:     Number of bytes/coordinate.
 *  nBits:      Number of bits/coordinate. (hilbert_box_vtx only)
 *  findMin:    Is it the least vertex sought?
 *  coord1:     Array of nDims nBytes-byte coordinates - one corner of box
 *  coord2:     Array of nDims nBytes-byte coordinates - opposite corner
 * Output:
 *      c1 and c2 modified to refer to selected corner
 *      value returned is log2 of size of largest power-of-two-aligned box that
 *      contains the selected corner and no other corners
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */
unsigned
hilbert_box_vtx(unsigned nDims, unsigned nBytes, unsigned nBits,
                int findMin, void* c1, void* c2);
unsigned
hilbert_ieee_box_vtx(unsigned nDims,
                     int findMin, double* c1, double* c2);

/*****************************************************************
 * hilbert_box_pt
 * 
 * Determine the first or last point of a box to lie on a Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBytes:     Number of bytes/coordinate.
 *  nBits:      Number of bits/coordinate.
 *  findMin:    Is it the least vertex sought?
 *  coord1:     Array of nDims nBytes-byte coordinates - one corner of box
 *  coord2:     Array of nDims nBytes-byte coordinates - opposite corner
 * Output:
 *      c1 and c2 modified to refer to least point
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */
unsigned
hilbert_box_pt(unsigned nDims, unsigned nBytes, unsigned nBits,
               int findMin, void* coord1, void* coord2);
unsigned
hilbert_ieee_box_pt(unsigned nDims,
                    int findMin, double* c1, double* c2);

/*****************************************************************
 * hilbert_nextinbox
 * 
 * Determine the first point of a box after a given point to lie on a Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBytes:     Number of bytes/coordinate.
 *  nBits:      Number of bits/coordinate.
 *  findPrev:   Is the previous point sought?
 *  coord1:     Array of nDims nBytes-byte coordinates - one corner of box
 *  coord2:     Array of nDims nBytes-byte coordinates - opposite corner
 *  point:      Array of nDims nBytes-byte coordinates - lower bound on point returned
 *  
 * Output:
      if returns 1:
 *      c1 and c2 modified to refer to least point after "point" in box
      else returns 0:
        arguments unchanged; "point" is beyond the last point of the box
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */
int
hilbert_nextinbox(unsigned nDims, unsigned nBytes, unsigned nBits,
                  int findPrev, void* coord1, void* coord2,
                  void const* point);

/*****************************************************************
 * hilbert_incr
 * 
 * Advance from one point to its successor on a Hilbert curve
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBits:      Number of bits/coordinate.
 *  coord:      Array of nDims nBits-bit coordinates.
 * Output:
 *  coord:      Next point on Hilbert curve
 * Assumptions:
 *      nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */

void
hilbert_incr(unsigned nDims, unsigned nBits, bitmask_t coord[]);

#ifdef __cplusplus
}
#endif

#endif /* _hilbert_h_ */
Revision:	3.1
Committed:	Fri Feb 18 00:40:25 2011 UTC (13 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Log Message:	Major code reorg, moving mgflib to common and introducing BSDF material
#	Content
1	/* C header file for Hilbert curve functions */
2	#if !defined(_hilbert_h_)
3	#define _hilbert_h_
4
5	#ifdef __cplusplus
6	extern "C" {
7	#endif
8
9	/* define the bitmask_t type as an integer of sufficient size */
10	typedef unsigned long long bitmask_t;
11	/* define the halfmask_t type as an integer of 1/2 the size of bitmask_t */
12	typedef unsigned long halfmask_t;
13
14	/*****************************************************************
15	* hilbert_i2c
16	*
17	* Convert an index into a Hilbert curve to a set of coordinates.
18	* Inputs:
19	* nDims: Number of coordinate axes.
20	* nBits: Number of bits per axis.
21	* index: The index, contains nDimsnBits bits (so nDimsnBits must be <= 8*sizeof(bitmask_t)).
22	* Outputs:
23	* coord: The list of nDims coordinates, each with nBits bits.
24	* Assumptions:
25	* nDimsnBits <= (sizeof index) (bits_per_byte)
26	*/
27
28	void hilbert_i2c(unsigned nDims, unsigned nBits, bitmask_t index, bitmask_t coord[]);
29
30	/*****************************************************************
31	* hilbert_c2i
32	*
33	* Convert coordinates of a point on a Hilbert curve to its index.
34	* Inputs:
35	* nDims: Number of coordinates.
36	* nBits: Number of bits/coordinate.
37	* coord: Array of n nBits-bit coordinates.
38	* Outputs:
39	* index: Output index value. nDims*nBits bits.
40	* Assumptions:
41	* nDimsnBits <= (sizeof bitmask_t) (bits_per_byte)
42	*/
43
44	bitmask_t hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[]);
45
46	/*****************************************************************
47	* hilbert_cmp, hilbert_ieee_cmp
48	*
49	* Determine which of two points lies further along the Hilbert curve
50	* Inputs:
51	* nDims: Number of coordinates.
52	* nBytes: Number of bytes of storage/coordinate (hilbert_cmp only)
53	* nBits: Number of bits/coordinate. (hilbert_cmp only)
54	* coord1: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
55	* coord2: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
56	* Return value:
57	* -1, 0, or 1 according to whether
58	coord1<coord2, coord1==coord2, coord1>coord2
59	* Assumptions:
60	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
61	*/
62
63	int hilbert_cmp(unsigned nDims, unsigned nBytes, unsigned nBits, void const* coord1, void const* coord2);
64	int hilbert_ieee_cmp(unsigned nDims, double const* coord1, double const* coord2);
65
66	/*****************************************************************
67	* hilbert_box_vtx
68	*
69	* Determine the first or last vertex of a box to lie on a Hilbert curve
70	* Inputs:
71	* nDims: Number of coordinates.
72	* nBytes: Number of bytes/coordinate.
73	* nBits: Number of bits/coordinate. (hilbert_box_vtx only)
74	* findMin: Is it the least vertex sought?
75	* coord1: Array of nDims nBytes-byte coordinates - one corner of box
76	* coord2: Array of nDims nBytes-byte coordinates - opposite corner
77	* Output:
78	* c1 and c2 modified to refer to selected corner
79	* value returned is log2 of size of largest power-of-two-aligned box that
80	* contains the selected corner and no other corners
81	* Assumptions:
82	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
83	*/
84	unsigned
85	hilbert_box_vtx(unsigned nDims, unsigned nBytes, unsigned nBits,
86	int findMin, void* c1, void* c2);
87	unsigned
88	hilbert_ieee_box_vtx(unsigned nDims,
89	int findMin, double* c1, double* c2);
90
91	/*****************************************************************
92	* hilbert_box_pt
93	*
94	* Determine the first or last point of a box to lie on a Hilbert curve
95	* Inputs:
96	* nDims: Number of coordinates.
97	* nBytes: Number of bytes/coordinate.
98	* nBits: Number of bits/coordinate.
99	* findMin: Is it the least vertex sought?
100	* coord1: Array of nDims nBytes-byte coordinates - one corner of box
101	* coord2: Array of nDims nBytes-byte coordinates - opposite corner
102	* Output:
103	* c1 and c2 modified to refer to least point
104	* Assumptions:
105	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
106	*/
107	unsigned
108	hilbert_box_pt(unsigned nDims, unsigned nBytes, unsigned nBits,
109	int findMin, void* coord1, void* coord2);
110	unsigned
111	hilbert_ieee_box_pt(unsigned nDims,
112	int findMin, double* c1, double* c2);
113
114	/*****************************************************************
115	* hilbert_nextinbox
116	*
117	* Determine the first point of a box after a given point to lie on a Hilbert curve
118	* Inputs:
119	* nDims: Number of coordinates.
120	* nBytes: Number of bytes/coordinate.
121	* nBits: Number of bits/coordinate.
122	* findPrev: Is the previous point sought?
123	* coord1: Array of nDims nBytes-byte coordinates - one corner of box
124	* coord2: Array of nDims nBytes-byte coordinates - opposite corner
125	* point: Array of nDims nBytes-byte coordinates - lower bound on point returned
126	*
127	* Output:
128	if returns 1:
129	* c1 and c2 modified to refer to least point after "point" in box
130	else returns 0:
131	arguments unchanged; "point" is beyond the last point of the box
132	* Assumptions:
133	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
134	*/
135	int
136	hilbert_nextinbox(unsigned nDims, unsigned nBytes, unsigned nBits,
137	int findPrev, void* coord1, void* coord2,
138	void const* point);
139
140	/*****************************************************************
141	* hilbert_incr
142	*
143	* Advance from one point to its successor on a Hilbert curve
144	* Inputs:
145	* nDims: Number of coordinates.
146	* nBits: Number of bits/coordinate.
147	* coord: Array of nDims nBits-bit coordinates.
148	* Output:
149	* coord: Next point on Hilbert curve
150	* Assumptions:
151	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
152	*/
153
154	void
155	hilbert_incr(unsigned nDims, unsigned nBits, bitmask_t coord[]);
156
157	#ifdef __cplusplus
158	}
159	#endif
160
161	#endif /* _hilbert_h_ */