8.3
general 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-2024 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
52typedef enum {
53
57
59
60typedef unsigned int fvm_morton_int_t;
61
62typedef 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
86void
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
95void
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
116void
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
125void
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
147fvm_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
166void
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
185void
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
204fvm_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
217void
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
230void
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
245bool
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
260bool
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
278int
281 fvm_morton_code_t *codes);
282
283#if defined(HAVE_MPI)
284
285/*----------------------------------------------------------------------------
286 * Build a global Morton encoding rank index.
287 *
288 * The rank_index[i] contains the first Morton code assigned to rank [i].
289 *
290 * parameters:
291 * dim <-- 1D, 2D or 3D
292 * gmax_level <-- level in octree used to build the Morton encoding
293 * n_codes <-- number of Morton codes to be indexed
294 * morton_code <-- array of Morton codes to be indexed
295 * weight <-- weighting related to each code
296 * order <-- ordering array
297 * rank_index <-> pointer to the global Morton encoding rank index
298 * comm <-- MPI communicator on which we build the global index
299 *
300 * returns:
301 * the fit related to the Morton encoding distribution (lower is better).
302 *----------------------------------------------------------------------------*/
303
304double
305fvm_morton_build_rank_index(int dim,
306 int gmax_level,
307 cs_gnum_t n_codes,
308 const fvm_morton_code_t code[],
309 const cs_lnum_t weight[],
310 const cs_lnum_t order[],
311 fvm_morton_code_t rank_index[],
312 MPI_Comm comm);
313
314#endif /* if HAVE_MPI */
315
316/*----------------------------------------------------------------------------*/
327/*----------------------------------------------------------------------------*/
328
329void
330fvm_morton_s_to_code(double s,
331 void *elt,
332 const void *input);
333
334/*----------------------------------------------------------------------------*/
346/*----------------------------------------------------------------------------*/
347
348int
349fvm_morton_compare_o(const void *elt1,
350 const void *elt2,
351 const void *input);
352
353/*----------------------------------------------------------------------------
354 * Dump a Morton to standard output or to a file.
355 *
356 * parameters:
357 * dim <-- 2D or 3D
358 * code <-- Morton code to dump
359 *----------------------------------------------------------------------------*/
360
361void
362fvm_morton_dump(int dim,
363 fvm_morton_code_t code);
364
365/*----------------------------------------------------------------------------*/
366
368
369#endif /* __FVM_MORTON_H__ */
#define BEGIN_C_DECLS
Definition: cs_defs.h:542
double cs_coord_t
Definition: cs_defs.h:340
uint64_t cs_gnum_t
global mesh entity number
Definition: cs_defs.h:325
#define END_C_DECLS
Definition: cs_defs.h:543
int cs_lnum_t
local mesh entity id
Definition: cs_defs.h:335
void fvm_morton_local_sort(cs_lnum_t n_codes, fvm_morton_code_t morton_codes[])
Definition: fvm_morton.cpp:1170
fvm_morton_code_t fvm_morton_encode(int dim, fvm_morton_int_t level, const cs_coord_t coords[])
Definition: fvm_morton.cpp:950
bool fvm_morton_a_ge_b(fvm_morton_code_t a, fvm_morton_code_t b)
Definition: fvm_morton.cpp:1290
void fvm_morton_local_order(cs_lnum_t n_codes, const fvm_morton_code_t morton_codes[], cs_lnum_t order[])
Definition: fvm_morton.cpp:1121
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.cpp:904
int fvm_morton_compare_o(const void *elt1, const void *elt2, const void *input)
Function pointer for comparison of 2 Morton codes.
Definition: fvm_morton.cpp:1463
fvm_morton_compare_t fvm_morton_compare(int dim, fvm_morton_code_t code_a, fvm_morton_code_t code_b)
Definition: fvm_morton.cpp:1218
int fvm_morton_binary_search(cs_lnum_t size, fvm_morton_code_t code, fvm_morton_code_t *codes)
Definition: fvm_morton.cpp:1311
void fvm_morton_s_to_code(double s, void *elt, const void *input)
Function pointer for conversion of a double precision value in range [0, 1] to a given Morton code.
Definition: fvm_morton.cpp:1436
fvm_morton_compare_t
Definition: fvm_morton.h:52
@ FVM_MORTON_SAME_ANCHOR
Definition: fvm_morton.h:55
@ FVM_MORTON_EQUAL_ID
Definition: fvm_morton.h:54
@ FVM_MORTON_DIFFERENT_ID
Definition: fvm_morton.h:56
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.cpp:852
void fvm_morton_dump(int dim, fvm_morton_code_t code)
Definition: fvm_morton.cpp:1489
unsigned int fvm_morton_int_t
Definition: fvm_morton.h:60
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.cpp:988
bool fvm_morton_a_gt_b(fvm_morton_code_t a, fvm_morton_code_t b)
Definition: fvm_morton.cpp:1272
void fvm_morton_get_children(int dim, fvm_morton_code_t parent, fvm_morton_code_t children[])
Definition: fvm_morton.cpp:1063
Definition: fvm_morton.h:62
fvm_morton_int_t L
Definition: fvm_morton.h:64