programmer's documentation
fvm_morton.h
Go to the documentation of this file.
1 #ifndef __FVM_MORTON_H__
2 #define __FVM_MORTON_H__
3 
4 /*============================================================================
5  * Morton encoding for 2D or 3D coordinates.
6  *============================================================================*/
7 
8 /*
9  This file is part of Code_Saturne, a general-purpose CFD tool.
10 
11  Copyright (C) 1998-2015 EDF S.A.
12 
13  This program is free software; you can redistribute it and/or modify it under
14  the terms of the GNU General Public License as published by the Free Software
15  Foundation; either version 2 of the License, or (at your option) any later
16  version.
17 
18  This program is distributed in the hope that it will be useful, but WITHOUT
19  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
20  FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
21  details.
22 
23  You should have received a copy of the GNU General Public License along with
24  this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
25  Street, Fifth Floor, Boston, MA 02110-1301, USA.
26 */
27 
28 /*----------------------------------------------------------------------------*/
29 
30 #include "cs_defs.h"
31 
32 /*----------------------------------------------------------------------------
33  * Standard C library headers
34  *----------------------------------------------------------------------------*/
35 
36 #include <stdio.h>
37 
38 /*----------------------------------------------------------------------------
39  * Local headers
40  *----------------------------------------------------------------------------*/
41 
42 #include "fvm_defs.h"
43 
44 /*----------------------------------------------------------------------------*/
45 
47 
48 /*============================================================================
49  * Macro and type definitions
50  *============================================================================*/
51 
52 typedef enum {
53 
57 
59 
60 typedef unsigned int fvm_morton_int_t;
61 
62 typedef struct {
63 
64  fvm_morton_int_t L; /* Level in the tree structure */
65  fvm_morton_int_t X[3]; /* X, Y, Z coordinates in Cartesian grid */
66 
68 
69 /*============================================================================
70  * Public function definitions
71  *============================================================================*/
72 
73 /*----------------------------------------------------------------------------
74  * Determine the global extents associated with a set of coordinates
75  *
76  * parameters:
77  * dim <-- spatial dimension
78  * n_coords <-- local number of coordinates
79  * coords <-- entity coordinates; size: n_entities*dim (interlaced)
80  * g_extents --> global extents (size: dim*2)
81  * comm <-- associated MPI communicator
82  *---------------------------------------------------------------------------*/
83 
84 #if defined(HAVE_MPI)
85 
86 void
88  size_t n_coords,
89  const cs_coord_t coords[],
90  cs_coord_t g_extents[],
91  MPI_Comm comm);
92 
93 #else
94 
95 void
97  size_t n_coords,
98  const cs_coord_t coords[],
99  cs_coord_t g_extents[]);
100 
101 #endif
102 
103 /*----------------------------------------------------------------------------
104  * Determine the global extents associated with a set of local extents
105  *
106  * parameters:
107  * dim <-- spatial dimension
108  * n_extents <-- local number of coordinates
109  * extents <-- entity coordinates; size: n_entities*dim*2 (interlaced)
110  * g_extents --> global extents (size: dim*2)
111  * comm <-- associated MPI communicator
112  *---------------------------------------------------------------------------*/
113 
114 #if defined(HAVE_MPI)
115 
116 void
118  size_t n_extents,
119  const cs_coord_t extents[],
120  cs_coord_t g_extents[],
121  MPI_Comm comm);
122 
123 #else
124 
125 void
127  size_t n_extents,
128  const cs_coord_t extents[],
129  cs_coord_t g_extents[]);
130 
131 #endif
132 
133 /*----------------------------------------------------------------------------
134  * Build a Morton code according to the level in an octree grid and its
135  * coordinates in the grid.
136  *
137  * parameters:
138  * dim <-- 1D, 2D or 3D
139  * level <-- level in the grid
140  * coords <-- coordinates in the grid (normalized)
141  *
142  * returns:
143  * a Morton code
144  *----------------------------------------------------------------------------*/
145 
147 fvm_morton_encode(int dim,
148  fvm_morton_int_t level,
149  const cs_coord_t coords[]);
150 
151 /*----------------------------------------------------------------------------
152  * Encode an array of coordinates.
153  *
154  * The caller is responsible for freeing the returned array once it is
155  * no longer useful.
156  *
157  * parameters:
158  * dim <-- 1D, 2D or 3D
159  * level <-- level in the grid
160  * extents <-- coordinate extents for normalization (size: dim*2)
161  * n_coords <-- nomber of coordinates in array
162  * coords <-- coordinates in the grid (interlaced, not normalized)
163  * m_code --> array of corresponding Morton codes
164  *----------------------------------------------------------------------------*/
165 
166 void
168  fvm_morton_int_t level,
169  const cs_coord_t extents[],
170  size_t n_coords,
171  const cs_coord_t coords[],
172  fvm_morton_code_t m_code[]);
173 
174 /*----------------------------------------------------------------------------
175  * Given a Morton code in the grid, compute the Morton codes of its
176  * children when refining the grid by one level.
177  *
178  * parameters:
179  * dim <-- 1D, 2D or 3D
180  * parent <-- Morton code associated with parent
181  * children --> array of children Morton codes
182  * (size: 8 in 3D, 4 in 2D, 2 in 1D)
183  *----------------------------------------------------------------------------*/
184 
185 void
187  fvm_morton_code_t parent,
188  fvm_morton_code_t children[]);
189 
190 /*----------------------------------------------------------------------------
191  * Compare two Morton encoding and check if these two codes are equal,
192  * different or shared the same anchor.
193  *
194  * parameters:
195  * dim <-- 2D or 3D
196  * code_a <-- first Morton code to compare
197  * code_b <-- second Morton code to compare
198  *
199  * returns:
200  * a type on the kind of relation between the two Morton encodings.
201  *----------------------------------------------------------------------------*/
202 
204 fvm_morton_compare(int dim,
205  fvm_morton_code_t code_a,
206  fvm_morton_code_t code_b);
207 
208 /*----------------------------------------------------------------------------
209  * Locally order a list of Morton ids.
210  *
211  * parameters:
212  * n_codes <-- number of Morton ids to order
213  * morton_codes <-- array of Morton ids to order
214  * order --> pointer to pre-allocated ordering table
215  *----------------------------------------------------------------------------*/
216 
217 void
219  const fvm_morton_code_t morton_codes[],
220  cs_lnum_t order[]);
221 
222 /*----------------------------------------------------------------------------
223  * Locally sort a list of Morton ids.
224  *
225  * parameters:
226  * n_codes <-- number of Morton ids to order
227  * morton_codes <-> array of Morton ids to sort
228  *----------------------------------------------------------------------------*/
229 
230 void
232  fvm_morton_code_t morton_codes[]);
233 
234 /*----------------------------------------------------------------------------
235  * Test if Morton code "a" is greater than Morton code "b"
236  *
237  * parameters:
238  * code_a <-- first Morton code to compare
239  * code_b <-- second Morton code to compare
240  *
241  * returns:
242  * true or false
243  *----------------------------------------------------------------------------*/
244 
245 bool
248 
249 /*----------------------------------------------------------------------------
250  * Test if Morton code "a" is greater or equal to Morton code "b"
251  *
252  * parameters:
253  * code_a <-- first Morton code to compare
254  * code_b <-- second Morton code to compare
255  *
256  * returns:
257  * true or false
258  *----------------------------------------------------------------------------*/
259 
260 bool
263 
264 /*----------------------------------------------------------------------------
265  * Get the index associated to a Morton code using a binary search.
266  *
267  * No check is done to ensure that the code is present in the array.
268  *
269  * parameters:
270  * size <-- size of the array
271  * code <-- code we are searching for
272  * codes <-- array of Morton codes
273  *
274  * returns:
275  * id associated to the given code in the codes array.
276  *----------------------------------------------------------------------------*/
277 
278 int
280  fvm_morton_code_t code,
281  fvm_morton_code_t *codes);
282 
283 /*----------------------------------------------------------------------------
284  * Get the quantile associated to a Morton code using a binary search.
285  *
286  * No check is done to ensure that the code is present in the quantiles.
287  *
288  * parameters:
289  * n_quantiles <-- number of quantiles
290  * code <-- code we are searching for
291  * quantile_start <-- first Morton code in each quantile (size: n_quantiles)
292  *
293  * returns:
294  * id associated to the given code in the codes array.
295  *----------------------------------------------------------------------------*/
296 
297 size_t
298 fvm_morton_quantile_search(size_t n_quantiles,
299  fvm_morton_code_t code,
300  fvm_morton_code_t *quantile_start);
301 
302 #if defined(HAVE_MPI)
303 
304 /*----------------------------------------------------------------------------
305  * Build a global Morton encoding rank index.
306  *
307  * The rank_index[i] contains the first Morton code assigned to rank [i].
308  *
309  * parameters:
310  * dim <-- 1D, 2D or 3D
311  * gmax_level <-- level in octree used to build the Morton encoding
312  * n_codes <-- number of Morton codes to be indexed
313  * morton_code <-- array of Morton codes to be indexed
314  * weight <-- weighting related to each code
315  * order <-- ordering array
316  * rank_index <-> pointer to the global Morton encoding rank index
317  * comm <-- MPI communicator on which we build the global index
318  *
319  * returns:
320  * the fit related to the Morton encoding distribution (lower is better).
321  *----------------------------------------------------------------------------*/
322 
323 double
324 fvm_morton_build_rank_index(int dim,
325  int gmax_level,
326  cs_gnum_t n_codes,
327  const fvm_morton_code_t code[],
328  const cs_lnum_t weight[],
329  const cs_lnum_t order[],
330  fvm_morton_code_t rank_index[],
331  MPI_Comm comm);
332 
333 #endif /* if HAVE_MPI */
334 
335 /*----------------------------------------------------------------------------
336  * Dump a Morton to standard output or to a file.
337  *
338  * parameters:
339  * dim <-- 2D or 3D
340  * code <-- Morton code to dump
341  *----------------------------------------------------------------------------*/
342 
343 void
344 fvm_morton_dump(int dim,
345  fvm_morton_code_t code);
346 
347 /*----------------------------------------------------------------------------*/
348 
350 
351 #endif /* __FVM_MORTON_H__ */
unsigned long cs_gnum_t
global mesh entity number
Definition: cs_defs.h:280
void fvm_morton_local_sort(cs_lnum_t n_codes, fvm_morton_code_t morton_codes[])
Definition: fvm_morton.c:1170
fvm_morton_compare_t fvm_morton_compare(int dim, fvm_morton_code_t code_a, fvm_morton_code_t code_b)
Definition: fvm_morton.c:1218
void fvm_morton_local_order(cs_lnum_t n_codes, const fvm_morton_code_t morton_codes[], cs_lnum_t order[])
Definition: fvm_morton.c:1121
#define BEGIN_C_DECLS
Definition: cs_defs.h:429
void fvm_morton_get_coord_extents(int dim, size_t n_coords, const cs_coord_t coords[], cs_coord_t g_extents[])
Definition: fvm_morton.c:852
int fvm_morton_binary_search(cs_lnum_t size, fvm_morton_code_t code, fvm_morton_code_t *codes)
Definition: fvm_morton.c:1311
void fvm_morton_get_children(int dim, fvm_morton_code_t parent, fvm_morton_code_t children[])
Definition: fvm_morton.c:1063
double cs_coord_t
Definition: cs_defs.h:293
void fvm_morton_get_global_extents(int dim, size_t n_extents, const cs_coord_t extents[], cs_coord_t g_extents[])
Definition: fvm_morton.c:904
Definition: fvm_morton.h:55
fvm_morton_compare_t
Definition: fvm_morton.h:52
Definition: fvm_morton.h:62
unsigned int fvm_morton_int_t
Definition: fvm_morton.h:60
Definition: fvm_morton.h:54
double precision, save a
Definition: cs_fuel_incl.f90:146
fvm_morton_code_t fvm_morton_encode(int dim, fvm_morton_int_t level, const cs_coord_t coords[])
Definition: fvm_morton.c:950
int cs_lnum_t
local mesh entity id
Definition: cs_defs.h:292
#define END_C_DECLS
Definition: cs_defs.h:430
void fvm_morton_encode_coords(int dim, fvm_morton_int_t level, const cs_coord_t extents[], size_t n_coords, const cs_coord_t coords[], fvm_morton_code_t m_code[])
Definition: fvm_morton.c:988
bool fvm_morton_a_gt_b(fvm_morton_code_t a, fvm_morton_code_t b)
Definition: fvm_morton.c:1272
size_t fvm_morton_quantile_search(size_t n_quantiles, fvm_morton_code_t code, fvm_morton_code_t *quantile_start)
Definition: fvm_morton.c:1346
Definition: fvm_morton.h:56
void fvm_morton_dump(int dim, fvm_morton_code_t code)
Definition: fvm_morton.c:1476
fvm_morton_int_t L
Definition: fvm_morton.h:64
bool fvm_morton_a_ge_b(fvm_morton_code_t a, fvm_morton_code_t b)
Definition: fvm_morton.c:1290
double precision, save b
Definition: cs_fuel_incl.f90:146