---

What is "reorder"?
Can I just do this automatically in "cubes"?
What does this order look like?
Mesh Partitioning with SFCs?
Running Reorder, usage

---

Reorder takes meshes (Mesh.c3d) output by cubes and reorders them using a space-filling-curve based ordering. You should look at it as a backend for cubes.  flowCart takes these re-ordered meshes and can partition them on-the-fly onto any number of processors.  Even if you're going to run on a single CPU (unpartitioned domain) its worth reordering, since reordered meshes have better locality and will execute faster on cache-based machines.  Reorder is the key for flowCart's domain-decomposition strategy
top

Starting with release of Cart3d_v1.3, you can reorder automatically from within cubes using the "-reorder" command line option to cubes. This option tells cubes to do the reordering upon output of the mesh, and  names the output mesh Mesh.R.c3d, just as if you ran reorder externally. Reordering from within cubes  streamlines the meshing-simulation cycle somewhat, but doesn't offer all the choices as the standalone reorder code does, it also increases cubes' memory requirements somewhat. Do either, your choice.
top

A "space-filling curve"  is a curve which provides a map from a 2-D plane or a 3-D space to a 1-D interval. They have many interesting mathematical characteristics and there are some excellent resources on the web for getting acquainted with space-filling-curves. We have a paper on the various uses of space-filling-curves in Cart3D here. Otherwise, a good place to start is:

http://www.cut-the-knot.com/do_you_know/hilbert.html  (with a live java demo)
http://www.dcs.napier.ac.uk/~andrew/hilbert.html (with a windows screen saver :o)
http://www.math.ohio-state.edu/~fiedorow/math655/Peano.html (with illustrations of the 3D version)

Reorder uses these curves to re-order the cell and face lists that are output from cubes.  There are options for using either Morton or Peano-Hilbert SFC's to reorder your mesh. In general Peano-Hilbert produces slightly better partitionings and therefore its set  up as the default.  Here is a 2-D view of these two orderings. 

• Morton or "N" ordering:


 
• Peano-Hilbert or "U" ordering:

From these illustrations, its pretty clear to see how these curves can be used as partitioners but lets make it even clearer. 
top

 

Since the SFCs map the problem domain to a one-dimensional hyperspace along the curve, we can partition the problem space by partitioning the 1-D curve (e.g. collecting cells as we traverse the curve).  In the example a the right, there is an adapted mesh with 3 levels of cells, and its been partitioned into 4 subdomains.  Since this example is so small, the partition quality doesn't look particularly good. However, one characteristic of the SFC's that we use is that of locality this property guarantees that meshes will have asymptotically good partitioning. In fact, with both Peano-Hilbert and Morton orderings, the surface-to-volume ratio of the partitions will approach that of a cube.  Here are 2 examples of the meshes partitioned with the U-order.  Small mesh around 3 teardrops (4 partitions) Large mesh around complete space shuttle launch vehicle (16 partitions)

top

Reorder takes both the Mesh.c3d and the meta information in Mesh.c3d.Info output by cubes, and returns the reordered mesh to Mesh.R.c3d. It usually runs pretty quick, since its runtime is dominated by an internal call to qsort.  The usual unix command line is simply:
% reorder
Command line options can be used to specify either a different Mesh.c3d.Info file (-m infoFileName)  or a different mesh file (-i MeshFileName). By default, the output file name is "Mesh.R.c3d" to remind us that the mesh has been reordered and is ready for flowCart to do the domain-decomposition. You can also choose between Morton and Peano-Hilbert orderings, with Peano-Hilbert being used by default. 
After reorder executes, you can delete the original Mesh.c3d, since you wont need it anymore. 

Here is the full usage statement:
% reorder -
 

Usage: reorder [ argument list ]  Options: -i %s      ...Input  mesh file name, default:<Mesh.c3d> -o %s      ...output mesh file name, default:<Mesh.R.c3d> -m %s      ...Mesh info file,        default:<Mesh.c3d.Info> -sfc %c    ...sfc choice, H=peano-hilbert (default), M=morton -s         ...Use perfect sort of face list (default is bin sort)