DisPerSE - persistent structures identification

References

3100-05-10T08:30:00+01:00

A few references:

DisPerSE: (see therein for references on discrete Morse theory and persistence)

-Sousbie, T., "The persistent cosmic web and its filamentary structure - I. Theory and implementation", 2011, Monthly Notices of the Royal Astronomical Society, 414, 350

-Sousbie, T., Pichon, C., Kawahara, H., "The persistent cosmic web and its filamentary structure - II. Illustrations", 2011, Monthly Notices of the Royal Astronomical Society, 414, 384

Books on persistence and discrete Morse-theory:

-Zomorodian A. J., "Topology for computing", 2009, Vol. 16 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, Cambridge 2, 19, 32

-Edelsbrunner, H. & Harer, J.L., "Computational Topology", 2010

-Gyulassy A., 2009, PhD thesis, Univ. California Berkeley 2, 8, 13

-Forman, R., "A user’s guide to discrete morse theory", 2002

There is also a swarm of scientific articles dealing with these topics that you can find on the net, just google it :)

Contact

3000-05-10T07:52:00+01:00

For any question regarding DisPerSE or this website, please contact sousbie(AT)iap.fr.

vtk field format

2430-01-06T06:56:00+01:00

VTK formats are developed for the Visualization Tool Kit library (VTK) and can be used for 3D visualization with software such as VisIt or ParaView. Only regular grids field types can be converted to VTK (for particle type fields, convert to NDnet unstructured network format first and then use netconv -to vtk). Regular grids are stored as VTK image data and can be output in fours different VTK formats:

-vtk: the legacy format
-vtk_ascii: ASCII version of the vtk format
-vti: a more recently developed XML version of the vtk format,
-vti_ascii: ASCII version of the vtu format

The specifications for these formats can be found in this PDF file. See also here and there for additional information.

SDL-image format

2430-01-05T06:56:00+01:00

This input format is used to read 2D regular grids encoded in a popular picture format readable by SDL-image library (jpg, png, gif, ...). When using this format as input to mse, the field whose topology is computed is the luminosity L of the image, a weighted average of the RED, GREEN and BLUE components of the image:

L = 0.2989*RED + 0.5870*GREEN + 0.1140*BLUE

survey_ascii format

2430-01-04T06:56:00+01:00

This is a simple ASCII format whose main purpose is to easily read coordinates of discretely sampled astrophysical surveys (e.g. such as an SDSS galaxy catalog). It should be considered when using spherical coordinates systems or if distance is measured by redshift for instance.

In this format, particles properties are encoded in an ASCII array where each row corresponds to one particle and each column to one property. Each column must have a name defined in the header (the first line of the file, starting with character #). An survey_ascii file may look like this:

# ra dec z my_field
+2.115401e+02	+6.313433e-01	+2.666800e-01  1	
+2.115633e+02	+7.550188e-01	+1.259900e-01  0	
+2.115687e+02	+8.108763e-01	+3.646600e-01  0	
+2.117158e+02	+6.393598e-01	+1.143600e-01  1	
+2.116826e+02	+6.528485e-01	+2.455700e-01  1	
+2.116993e+02	+6.509297e-01	+1.199000e-01  0	
+2.115738e+02	+7.772653e-01	+3.240600e-01  0	
+2.116198e+02	+6.950604e-01	+1.987300e-01  0	
+2.116773e+02	+7.085776e-01	+2.561900e-01  1

The name of a column defines its role if it matches one of the following keywords:

header keywords
Keyword	Meaning
px	X coordinate of the particle
py	Y coordinate of the particle
pz	Z coordinate of the particle
vx	X component of the velocity
vy	Y component of the velocity
vz	Z component of the velocity
id	an index associated to the particle
ra	The right ascension of the particle
dec	The declination of the particle
z	The redshift of the particle.

When particles coordinates are defined with ra, dec or z (redshift), DisPerSE automatically transform them into cartesian coordinates using the standard LCDM model to compute distances (Omega_m=0.27, Omega_L=0.73 ). This transformation can be inverted on the output skeletons and networks using options -toRaDecZ and -toRaDecDist of skelconv and netconv.

FITS format

2430-01-03T06:56:00+01:00

This field format is used to read 2D or 3D regular grids of arbitrary dimensions in the popular Flexible Image Transport System (FITS) image format. A popular library for reading and writing FITS image in C or FORTRAN is CFITSIO, which must be installed for DisPerSE to be able to use this kind of files.

This file format is also used for storing HEALPIX tesselations of the sphere. DisPerSE will automatically detect if the FITS file contains a HEALPIX tesselation.

NDfield format

2430-01-02T06:56:00+01:00

This is the native binary format of DisPerSE. Functions for reading and writing NDfield format in C can be found within the file ${DISPERSE_SRC}/src/C/NDfield.c (see functions Load_NDfield and Save_NDfield).

When using the C functions from Disperse, data is loaded into the following C structure which is close to the actual structure of the file (see file ${DISPERSE_SRC}/src/C/NDfield.h):

#define ND_CHAR   (1<<0)
#define ND_UCHAR  (1<<1)
#define ND_SHORT  (1<<2)
#define ND_USHORT (1<<3)
#define ND_INT    (1<<4)
#define ND_UINT   (1<<5)
#define ND_LONG   (1<<6)
#define ND_ULONG  (1<<7)
#define ND_FLOAT  (1<<8)
#define ND_DOUBLE (1<<9)

typedef struct NDfield_str
{
 char comment[80];  // a comment on the data
 int dims[NDFIELD_MAX_DIMS];  // dimensions of the grid, must be [ndims,nparticles] when data represents sample particles coordinates (i.e. when fdims_index!=0)
 int ndims;  // number of dimensions of the space
 int n_dims;  // number of meaningfull values in dims array
 int fdims_index; // if 0, the field is a regular grid of dimensions dims, else the file contains the dims[0] coordinates of dims[1] particles.
 int datatype;  // type of the data (one of the ND_... defined above)
 double x0[NDFIELD_MAX_DIMS];  // origin of the bounding box
 double delta[NDFIELD_MAX_DIMS];  // extent of the bounding box
 char dummy[160];  // dummy data, for future extensions or for storing anything you want.

 void *val;  // pointer to data

 long nval;  // total number of particles (fdims_index==1) or pixels (fdims_index==0)
 int datasize;  // size in bytes of datatype type.
} NDfield;

The NDfield binary format is organized as follows (blocks are delimited by dummy variables indicating the size of the blocks for FORTRAN compatibility, but they are ignored in C):

NDnet binary format
field	type	size	comment
dummy	int(4B)	1	for FORTRAN compatibility
tag	char(1B)	16	identifies the file type. Value : "NDFIELD"
dummy	int(4B)	1
dummy	int(4B)	1
ndims	int(4B)	1	number of dimensions of the embedding space
dims	int(4B)	20	size of the grid in pixels along each dimension, or [ndims,nparticles] if data represents particle coordinates (i.e. fdims_index=1)
fdims_index	int(4B)	1	0 if data represents a regular grid, 1 if it represents coordinates of tracer particles
datatype	int(4B)	1	type of data stored (see below)
x0	double(8B)	20	origin of bounding box (first ndims val. are meaningfull)
delta	double(8B)	20	size of bounding box (first ndims val. are meaningfull)
dummy_ext	char(1B)	160	dummy data reserved for future extensions
dummy	int(4B)	1
dummy	int(4B)	1
data	size of datatype	N	data itself (N may be the number of pixels or ndism times the number of particles)
dummy	int(4B)	1

Possible data types
name	size (Bytes)	type	value
ND_CHAR	1	integer	1 (=1<<0)
ND_UCHAR	1	integer	2 (=1<<1)
ND_SHORT	2	integer	4 (=1<<2)
ND_USHORT	2	integer	8 (=1<<3)
ND_INT	4	integer	16 (=1<<4)
ND_UINT	4	integer	32 (=1<<5)
ND_LONG	8	integer	64 (=1<<6)
ND_ULONG	8	integer	128 (=1<<7)
ND_FLOAT	4	float	256 (=1<<8)
ND_DOUBLE	8	float	512 (=1<<9)

NDfield_ascii format

2430-01-02T06:56:00+01:00

A simple ASCII version of the NDfield format used to represent either uniform grids or particles coordinates. Data type is always interpreted as double precision floating point.

NDfield_ascii format

ANDFIELD COORDS	header (COORDS keyword is optional, if present, values are interpreted as coordinates, or else, as pixel values)
[N_1 ... N_ndims]	size of the grid along each of the ndims dimensions (in pixels) or number of dimensions and number of particles if COORDS keyword is in the header (= [ndims,nparticles])
BBOX [X0_1 ... X0_ndims] [delta_1 ... delta_ndims]	OPTIONAL: bounding box definition (origin and extent)
V_1 V_2	values (any number of values can be on the same line)
V_3	no particular formating is required
...	Repeat enough time to define a number of values equal to the number of pixels or the number of particles (if COORDS keyword is in the header)

Field files

2430-01-01T06:56:00+01:00

This file type is designed to store scalar fields sampled over regular grids (i.e. regular images in 2D, 3D and more) or, by extension, coordinates of tracer particles sampling an underlying density field. The main field format is NDfield, which allows to store any type of data (integer, simple or double precision floating point, ...) over arbitrary sized regular grids or as coordinates of tracer particles.

Available formats:

-NDfield (Read / Write):
This is the format used internally in DisPerSE, it is efficient and generic as it can store regular grids or sample particles coordinates indifferently.

-NDfield_ascii (Read / Write):
A simple ASCII version of the NDfield format, it is as versatile but data is always considered to be double precision floating point.

-FITS (Read only):
Used to read 2D or 3D regular grids of arbitrary dimensions in the popular Flexible Image Transport System (FITS) image format. Also used for HEALPIX tessellations of the sphere.

-survey_ascii(Read only):
A simple ASCII format whose main purpose is to easily read coordinates of discretely sampled astrophysical surveys (e.g. such as an SDSS galaxy catalog). Try this if you use spherical coordinates or if distance is measured by redshift for instance.

-SDL-image (Read only):
This input format is used to read 2D regular grids encoded in a popular picture format readable by SDL-image library (jpg, png, gif, ...).

-vtk, vtk_ascii, vti and vti_ascii (Write only):
These formats are binary and ASCII legacy and XML VTK formats that are readable by several 3D visualization tools, such as VisIt or ParaView for instance.

-NDnet (Write only):
Using this format, field files representing tracer particles coordinates can be converted to unstructured networks (use netconv to convert NDnet files to other network formats). Regular grids conversion is not implemented yet due to the huge size of the output network.

vtk network format

2426-01-04T13:14:00+01:00

VTK formats are developed for the Visualization Tool Kit library (VTK) and can be used for 3D visualization with software such as VisIt or ParaView. Networks are stored as VTK unstructured network data and can be output in fours different VTK formats:

-vtk: the legacy format
-vtk_ascii: ASCII version of the vtk format
-vtu: a more recently developed XML version of the vtk format,
-vtu_ascii: ASCII version of the vtu format

The specifications for these formats can be found in this PDF file. See also here and there for additional information.

ply format

2426-01-03T13:14:00+01:00

The PLY format is a relatively generic file format designed to store three dimensional data from 3D scanners with the possibility of associating properties to the polygons. Information on this format can be found on wikipedia (see also the External links section). A very efficient C library for reading and writing PLY files in ASCII or binary format is RPly (DisPerSE uses it for PLY files I/O, see files NDnet_PLY_IO.c and NDnet_PLY_IO.h).

A typical header for a PLY file readable by netconv or mse is as follows:

ply
format ascii 1.0
element bbox 1
property list uchar double x0 
property list uchar double delta
element vertex 77595
property float x
property float y
property float z
property double field_value
element face 482867
property list uchar uint vertex_indices
end_header

-format may be ASCII or little / big endian binary

-bbox element is used to define a bounding box if available (x0 is its origin and delta its extent)

-coordinates of the vertices are given as vertex properties labeled x, y, and z or x0, x1, ... (the number of this properties gives the dimension of the embedding space)

-faces are defined by the property vertex_indices, each element corresponding to a list of vertices. A cell is always supposed to be a simplex, so the number of vertices determine the dimension spanned by the complex (a 2D complex may be embedded in a 3D space).

-additional properties may be defined for cells and vertices. In particular, a vertex property labeled field_value would be used as input function in mse.

NDnet_ascii format

2426-01-02T13:14:00+01:00

This ASCII format is a simpler version of the NDnet format, designed to be fully compatible but restricted to simplicial networks. It is easy to read and write and should probably be used for reasonably sized data sets.

Note: The scalar function whose MS-complex is computed by mse can be stored as an additional data field named 'field_value' (case sensitive).

NDnet_ascii format

ANDNET	header
ndims	the number of dimensions
#comments go here	OPTIONAL: should start with '#' if present (the 80 first characters are read and stored).
BBOX [x0_1 .. x0_d] [delta_1 .. delta_d]	OPTIONAL: the bounding box, defined by the 'ndims' coordinates of the origin 'x0' and extent 'delta'.
nv	number of vertices
vx[0] vy[0] ...	the ndims coordinates of the first vertex
...	One line for each vertex
Simplices definition (0-cells up to ndims-cells). One blue block should be added for each type of explicitly defined simplex. Note that only the highest dimension cells are sufficient to define a complex.
T N	network has N T-simplices (each T-simplex has (T+1) vertices).
i[0] j[0] ...	the T+1 indices (start at 0) of the vertices of the first T-simplex.
...	one line for each of the N T-simplices
[ADDITIONAL_DATA]	OPTIONAL: indicate the beginning of the additional data section
additional_data_name_1	name of the additional data (e.g. field_value for mse input files)
T	type of simplex it is associated to (T-simplex, 0 means vertices)
val[0]	value for the first T-simplex
...	One line for each T-simplex

NDnet format

2426-01-01T13:14:00+01:00

This is the native binary format of DisPerSE. Functions for reading and writing NDnet format in C can be found within the file ${DISPERSE_SRC}/src/C/NDnetwork.c (see functions Load_NDnetwork and Save_NDnetwork). The format may seem relatively complex, but most of it is actually optional and not used in disperse (only simplicial complexes are used in DisPerSE). To create DisPerSE input files, it is only necessary to define the highest dimensional n-simplices as a list of (n+1) vertices (see also function CreateNetwork).

Note: The scalar function whose MS-complex is computed by mse can be stored as an additional data field named 'field_value' (case sensitive).
Warning: in the following, for legacy reasons, the terms n-face and n-cell are used indifferently to designate polygons of dimension n (which are always simplexes in DisPerSE).

When using the C functions from Disperse, data is loaded into the following C structure which is close to the actual structure of the file (see file ${DISPERSE_SRC}/src/C/NDnetwork.h):

typedef struct
 {
   int type; // the cell-type
   char name[255];  // name of the field
   double *data;  // value for each of the nfaces[n] n-cells
} NDnetwork_Data;

// NDnetwork_SupData is not used in disperse ...
typedef struct
{
   int type; 
   char name[255];
   int datasize;
   char datatype[255];// a string to identity how data should be casted
   void *data;
} NDnetwork_SupData;

typedef struct 
{
   char comment[80];
   int periodicity;
   int ndims; // the number of spatial dimensions
   int ndims_net; // number of dimension of the network itself (e.g. 2 for a sphere embedded in 3D)
   int isSimpComplex;  // 1 if network is a simplicial complex (always true in disperse)
   double *x0;  // origin of the bounding box
   double *delta;  // size of the bounding box
   int indexSize; // size of NDNET_UINT type in Bytes
   int cumIndexSize; // size of NDNET_IDCUMT type in Bytes
   char dummy[160-4*2]; // dummy data reserved for future extensions
 
   NDNET_UINT nvertex;  // total number of vertices
   float *v_coord; //vertices coodinates (X_0,Y_0,Z_0,X_1,Y_1,...,Z_nvertex-1)
   
   NDNET_UINT *nfaces; // number of cells of a given type t is given by nfaces[t]
 
   int *haveVertexFromFace; // haveVertexFromFace[n] is 1 if we have an explicit definition of the n-cells (at least one type of cell must be defined).
   NDNET_IDCUMT **f_numVertexIndexCum;// cumulative number of vertice in the t-cells, NULL when cells are simplexes (isSimpComplex=1)
   NDNET_UINT **f_vertexIndex; // list of vertices defining the n-cells is stored in f_vertexIndex[n], all vertices being enumerated for each cell (the indices of the vertices in the kth n-cell start at f_vertexIndex[n][(n+1)*k] )
   // see also macro  NUM_VERTEX_IN_FACE(net,type,face) and VERTEX_IN_FACE(net,type,face)
 
   //This may be computed internally within DisPerSE but does not need to be defined explicitely
   int *haveFaceFromVertex; // haveFaceFromVertex[n] is 1 if we have an explicit list of all the n-cells that contain each vertex (used to navigate within the network)
   NDNET_IDCUMT **v_numFaceIndexCum; // cumulative number of t-cells a vertex v belongs to
   NDNET_UINT **v_faceIndex; // indices of the t-cells in the co-boundary of v ( the list of n-cells of vertex k starts at v_faceIndex[n][net->v_numFaceIndexCum[n][k]] and ends at v_faceIndex[n][net->v_numFaceIndexCum[n][k+1]] )
   // see also macro  NUM_FACE_IN_VERTEX(net,type,vertex) and  FACE_IN_VERTEX(net,type,vertex)
   
   // This can become extremely memory heavy ... NOT used in DisPerSE
   int **haveFaceFromFace; // haveFaceFromFace[k][n] is 1 if we have an explicit list of all the n-cells that have a boundary/co-boundary relation with each k-cell (used to navigate within the network)
   NDNET_IDCUMT ***f_numFaceIndexCum; //  cumulative number of n-cells having a boundary / co-boundary relation with each k-cell: f_numFaceIndexCum[k][n]
   NDNET_UINT ***f_faceIndex; // indices of the cells (similar to v_faceIndex)
   // see also macro NUM_FACE_IN_FACE(net,ref_type,ref_face,type) and FACE_IN_FACE(net,ref_type,ref_face,type)
   
   int haveVFlags;  // do we have flags associated to each vertex ?
   int *haveFFlags;  // do we have flags associated to each n-cell ?
   unsigned char *v_flag; // nvertex flag values (1 for each vertex) or NULL 
   unsigned char **f_flag; // nfaces[n] flag values (1 of each n-cell) or NULL

   int ndata; // number of additional data fields.
   NDnetwork_Data *data; // array of all additionnal data (data in total)
   
   int nsupData;
   NDnetwork_SupData *supData;

} NDnetwork;

The NDnet binary format is organized as follows (blocks are delimited by dummy variables indicating the size of the blocks for FORTRAN compatibility, but they are ignored in C):

NDnet binary format
field	type	size	comment
dummy	int(4B)	1	for FORTRAN compatibility
tag	char(1B)	16	identifies the file type. Value : "NDNETWORK"
dummy	int(4B)	1
dummy	int(4B)	1
ndims	int(4B)	1	number of dimensions of the embedding space
ndims_net	int(4B)	1	ndims spanned by the network (=ndims by default)
dummy	int(4B)	1
dummy	int(4B)	1
comment	char(1B)	80	a comment on the file (string)
periodicity	int(4B)	1	0=non periodic, if p^th bit is set, boundary are periodic along dimension p
isSimpComplex	int(4B)	1	1 if network is made of simplices (must be 1 for DisPerSE)
x0	double(8B)	ndims	origin of bounding box
delta	double(8B)	ndims	size of bounding box
index_size	int(4B)	1	size of NDNET_UINT integer format in Bytes
cumindex_size	int(4B)	1	size of NDNET_IDCUMT integer format in Bytes
dummy_ext	char(1B)	152	dummy data reserved for future extensions
nvertex	NDNET_UINT	1	number of vertices
dummy	int(4B)	1
dummy	int(4B)	1
v_coords	float(4B)	ndims×nvertex	coordinates of the vertices [X0,Y0, ...]
dummy	int(4B)	1
dummy	int(4B)	1
nfaces	NDNET_UINT	ndims+1	number of cells of each type (N0,N1,...)
dummy	int(4B)	1
dummy	int(4B)	1
haveVertexFromFace	int(4B)	ndims+1	are n-cells explicitly defined ? (0=no, 1=yes)
dummy	int(4B)	1
*	*	*	next 3 lines are repeated for each (ndims+1) possible cells type , only if haveVertexFromFace[n] is true.
dummy	int(4B)	1
f_vertexIndex[n]	NDNET_UINT	(n+1)×nfaces[n]	list of (n+1) vertex indices for each n-cell
dummy	int(4B)	1
dummy	int(4B)	1
haveFaceFromVertex	int(4B)	ndims+1	are n-cells in the co-boundary of each vertex explicitly defined ? (0=no, 1=yes)
dummy	int(4B)	1
*	*	*	next 6 lines are repeated for each (ndims+1) possible cells type, only if haveFaceFromVertex[n] is true.
dummy	int(4B)	1
numFaceIndexCum[n]	NDNET_IDCUMT	nvertex+1	cumulative count of n-cells on vertices co-boundary
dummy	int(4B)	1
dummy	int(4B)	1
v_faceIndex[n]	NDNET_UINT	numFaceIndexCum[n]	list of n-cells on the co-boundary of each vertex (vertex i have numFaceIndexCum[n][i+1]-numFaceIndexCum[n][i] of them)
dummy	int(4B)	1
dummy	int(4B)	1
haveFaceFromFace	int(4B)	(ndims+1)^2	are n-cells in the co-boundary of each k-cell explicitly defined ? (0=no, 1=yes)
dummy	int(4B)	1
*	*	*	This section describes boundary relation between n-cells and k-cells. It is usually empty in DisPerSE (see NDnetwork.c for details) so SKIP IT :)
dummy	int(4B)	1
haveVFlags	int(4B)	1	1 if vertex flags are defined
dummy	int(4B)	1
*	*	*	next 3 lines are skipped if haveVFlags=0
dummy	int(4B)	1
v_flag	uchar(1B)	nvertex	value of the flags for vertices
dummy	int(4B)	1
dummy	int(4B)	1
haveFFlags	int(4B)	ndims+1	1 if flags are defined for n-cells
dummy	int(4B)	1
*	*	*	next 3 lines are repeated for each n-cell such that haveFFlags[n]=1
dummy	int(4B)	1
f_flag[n]	uchar(1B)	nfaces[n]	value of the flags for n-cells
dummy	int(4B)	1
dummy	int(4B)	1
ndata	int(4B)	1	total number of additional fields
dummy	int(4B)	1
*	*	*	next 7 lines are repeated for each additional field (×ndata)
dummy	int(4B)	1
type	int(4B)	1	the type of cells (0=vertex, n = n-simplex)
name	char(1B)	255	name of the supplementary data
dummy	int(4B)	1
dummy	int(4B)	1
data	double(8B)	N	data associated to cells or vertices. N is nfaces[n] or nvertex depending on the type value.
dummy	int(4B)	1

Network files

2425-05-09T06:54:00+01:00

This file type is designed to store any kind of unstructured network (such as delaunay tesselations or more generally cell complexes). In DisPerSE, its usage is restricted to networks of simplices though, and it is mainly used to store ascending and descending manifolds (voids and walls for instance) and persistence pairs as output by mse or Delaunay tessellations as output by delaunay_nD (skeleton files can also be converted to networks using skelconv -to NDnet). Within network files, networks are represented by setz of vertices and cells of any dimension. A n-cell is a cell of dimension n, which is therefore described, in the case of a simplicial network, as a set of n+1 vertices index. In the case of a simplicial complex, only the highest dimensional cell have to be explicitly given, but other type of cells may also be specified. Indeed, extended manifolds for instance are not described as complexes: an ascending 0-manifold in 3D is a set of tetrahedrons (3-cells), triangles (representing ascending 1-manifolds on its boundary), segments (ascending 2-manifolds on its boundary) and vertices (ascending 3-manifolds / critical points). Note that additional information can also be associated to each type of cell (see below).
The base network format is NDnet which is used internally, but this format may be converted to several other more or less complex formats of network files adapted to different applications (see option -to in program netconv, a list of available formats is displayed when running the program without argument).

Available formats:

-NDnet (Read / Write):
This is the format of the network files created or red by mse. It is a relatively complex binary format (it is actually more complex than needed as it is designed to store generic non-simplicial networks) that contains all the information on the geometry and topology of unstructured networks as well as additional data associated to each type of cells.

-NDnet_ascii (Read / Write):
This ASCII format contains the same amount of information as NDnet files, but restricted to simplicial networks. It is easy to read and write so it may be used to write reasonably sized networks used as input for mse.

-PLY and PLY_ascii (Read binary only / Write):
This is a rather popular and simple binary or ASCII format that can be used as an interface with other software.

-vtk, vtk_ascii, vtu and vtu_ascii (Write only):
These formats are binary and ASCII legacy and XML VTK formats that are readable by several 3D visualization tools, such as VisIt or ParaView for instance.

Additional data: In addition to the topology and geometry of the network, arbitrary additional information may be associated to each type of cell. Run netconv filename -info for a list of additional data available in the network file filename. By default, the name of additional data added by mse is relatively explicit, it includes (see also the additional data section of the skeleton file format description):

-field_value / log_field_value :
The value of the field and its logarithm. The tag field_value corresponds to the input function for mse, whose Morse-Smale complex is to be computed.

-cell:
The type and index of a cell in the original network (prefix may be added). The value is a double precision floating number whose integer part is the index of the cell and decimal part its type. For instance, the 156th vertex (i.e. 0-cell) in the cell complex is represented as 156.0, while the 123th tetrahedron is 123.3. Note that the index of the 0-cell correpond to the index of the pixel / vertices in the original network from which the skeleton was computed.

-type:
This usually corresponds to the critical index of a critical point (for instance, vertices of persistence pairs networks), or the type of a persistence pair (i.e. the minimum critical index of the CP in the pair, for segments of persistence pairs networks).

-index
Usually the index of a vertex (e.g. for persistence pairs, additional segment data tagged up_index and down_index correspond to the indices of the vertices with lowest and highest critical index in the persistence pair respectively).

-persistence / persistence_ratio / persistence_nsigmas :
The persistence (expressed as a difference, ratio or in number of sigmas) of the persistence pair containing the corresponding critical point. A negative or null value indicates that persistence is not relevant to this particular cell.

-parent_index / parent_log_index (vertices only):
For persistence pairs type networks, for each vertex representing an extremum (i.e. minima and maxima), the index of the vertex that corresponds to the other extremum into which it would be merged if its persistence pair was canceled (indices start at 0). This can be used to reconstruct the tree of the hierarchy of maxima and minima. The value is -1 for non extrema critical points. The difference between the two versions is that the second (parent_log_index) is the hierarchy computed from the logarithm of the field. The second version is useful only for discrete point samples whose MS-complex is obtained from the delaunay tessellation computed with delaunay_nD. Practically, parent_log_index can be used whenever persistence pairs are cancelled in order of increasing ratio (option -nsig in mse), and parent_index whenever persistence pairs are cancelled in order of increasing difference (option -cut in mse).

-source_cell / source_index:
For networks representing manifolds (voids, walls, ... obtained with option -dumpManifolds of mse), this represents for each simplex the critical point from which the manifold it belongs to originates (for instance, the minimum corresponding to a void, or the saddle point corresponding to a filament). In source_cell, the critical points is represented by its cell in the initial cell complex (see cell above), while source_index gives the index of the critical point in the skeleton file or persistence pair network obtained with mse (options -dumpArcs and -ppairs). See also here and there in the tutorial section.

vtk skeleton formats

2420-05-07T15:06:00+01:00

VTK formats are developed for the Visualization Tool Kit library (VTK) and can be used for 3D visualization with software such as VisIt or ParaView. Skeletons are stored as VTK polygon data and can be output in fours different VTK formats:

-vtk: the legacy format
-vtk_ascii: ASCII version of the vtk format
-vtp: a more recently developed XML version of the vtk format,
-vtp_ascii: ASCII version of the vtp format

The specifications for these formats can be found in this PDF file. See also here and there for additional information.

crits_ascii format

2420-05-06T15:03:00+01:00

This ASCII format is a very simple one. It consists in a list of all the critical points with some useful information for each of them.

crits_ascii format

#critical points	Header
#X0 X1 X2 value type pair_id boundary	Header identifying each column
#NDIMS NPOINTS	Number of dimensions and number of points
X0 X1 X2 value type pair_id boundary	The value of the fields for the first point
....	One such line for each NPOINTS points

Notations:

-X_0,..., X_ndims : the coordinates of the pooint
-value : Value of the field.
-type : the critical index of the point. A value of NDIMS+1 indicates a bifurcation point or a trimmed extremity.
-pair_id : index of the other critical point in the persistence pair. C style convention is used, indices starting at 0, and points without perisstence pairs have their own index for pair_id.
-boundary : value can be 0, 1 or 2 when the point is inside the domain, on the boundary, or outside (e.g. at infinity)

segs_ascii format

2420-05-04T15:03:00+01:00

This ASCII format is a very simple one. It consists in a list of individual segments describing the local orientation of the arcs as well as some limited information on the filament they belong. This may be used for doing statistical analysis of local properties of filaments such as the local orientation of a magnetic field for instance. Note that all the segments are oriented from the lower critical index extremity of the filament they belong toward the other extremity (which does NOT mean that the value is strictly increasing, as local fluctuations of amplitude the persistence threshold are still allowed ... ).
nb: you probably want to use option -breakdown of skelconv before using this format.

segs_ascii format

#arc segments	Header
#U0 U1 U2 V0 V1 V2 value_U value_V type boundary	Header identifying each column
#NDIMS NSEGS	Number of dimensions and number of segments
U0 U1 U2 V0 V1 V2 value_U value_V type boundary	The value of the fields for the first segment
....	One such line for each NSEGS segment

Notations:

-U_0,..., U_ndims : The coordinates of the first extremity of the segment. It is the one closest to the lowest critical index CP along the filament it belongs to.
-V_0,..., V_ndims : The coordinates of the second extremity of the segment. It is the one closest to the highest critical index CP along the filament it belongs to.
-value_U, value_V : Value of the field in U and V.
-type : the type of arc the segment belongs to. The type of an arc is the minimum critical index of the CP at the extremity of the filament the segment belong to.
-boundary : value can be 0, 1 or 2 when the segment is inside the domain, on the boundary, or outside (e.g. at infinity)

NDskl_ascii format

2420-05-03T15:02:00+01:00

An ASCII format that contains the same amount of information as NDskl files, but organized in a different way. In particular, filaments are not described as lists of segments but rather each filament is described by an origin node, a destination node, and a set of sampling points.

NDskl_ascii format

ANDSKEL	header
ndims	the number of dimensions
#comments go here	OPTIONAL: should start with '#' if present (the 80 first characters are read and stored).
BBOX [x0_1 .. x0_d] [delta_1 .. delta_d]	OPTIONAL: the bounding box, defined by the 'ndims' coordinates of the origin 'x0' and extent 'delta'.
[CRITICAL POINTS]	Marks the beginning of the critical points section
ncrit	The number of critical points (CP)
type pos[0] ... pos[ndims-1] value pairID boundary	Info on the first CP: critical index, position, value, index of CP in the persistence pair, 0 if not on the boundary
nfil	The number of filaments connected to this CP
destId[0] filId[0]	Info on the first filament: index of the CP at the other extremity of the filament, and index of the filament (see filaments table below)
...	One line for each filament connecting on the CP
destId[nfil-1] filId[nfil-1]	Information on the last filament
.....
.....	one blue block for each CP.
.....
[FILAMENTS]	Marks the beginning of the filaments section
nfil	Total number of filaments
CP1 CP2 nSamp	index of the CP at the extremity of the first filament and number of sampling points
P[0][0] ... P[0][ndims-1]	position of the first sampling point of first filament.
...	One line for each sampling point of first filament.
P[nSamp-1][0] ... P[nSamp-1][ndims-1]	Position of the last sampling point
.....
.....	one blue block for each filament.
.....
[CRITICAL POINTS DATA]	Marks the beginning of the CP data section
NF	Number of fields associated to each CP.
CP_DATA_FIELD_NAME_1	Name of the first field
...
CP_DATA_FIELD_NAME_NF	Name of the last field
val_1[0] ... val_NF[0]	Value of each field for first CP
...
val_1[N_CP-1] ... val_NF[N_CP-1]	Value of each field for last CP
[FILAMENTS DATA]	Marks the beginning of the filaments data section
NF	Number of fields associated to each sampling point of each filament.
FIL_DATA_FIELD_NAME_1	Name of the first field
...
FIL_DATA_FIELD_NAME_NF	Name of the last field
val_1[0][0] ... val_NF[0][0]	field values for first sampling point, first filament
...
val_1[0][nSamp[0]] ... val_NF[0][nSamp[0]]	field values for last sampling point, first filament
.....
.....	one blue block for each filament.
.....

NDskl format

2420-05-02T15:01:00+01:00

This is the native binary format of DisPerSE. Functions for reading and writing NDskl format in C can be found within the file ${DISPERSE_SRC}/src/C/NDskeleton.c (see functions Load_NDskel, Save_NDskel and also Create_NDskel). In this format, the arcs of the Morse-Smale complex are described as arrays of nodes and segments with data associated to each of them. Each node contains information on critical points (which may also be bifurcations points or trimmed extremities of filaments). Each segment contains information on the local geometry of the arcs and global properties of the skeleton.

When using the C functions from Disperse, data is loaded into the following C structure which is close to the actual structure of the file (see file ${DISPERSE_SRC}/src/C/NDskeleton.h):

struct NDskl_seg_str {
   int nodes[2];  // index of the nodes at the extremity of the arc. Segment is oriented from nodes[0] toward nodes[1]
   float *pos;  // points to appropriate location in segpos
   int flags;  // non null if on boundary 
   int index;  // index of the segment in the Seg array
   double *data;  // points to the nsegdata supplementary data for this segment
   struct NDskl_seg_str *Next; // points to next segment in the arc, NULL if extremity (->connects to nodes[1])
   struct NDskl_seg_str *Prev; // points to previous segment in the arc, NULL if extremity (->connects to nodes[0])
 }; 
 typedef struct NDskl_seg_str NDskl_seg;

 struct NDskl_node_str {
   float *pos;  // points to appropriate location in nodepos
   int flags;  // non null if on boundary 
   int nnext;  // number of arcs connected
   int type;  // critical index
   int index;  // index of the node in the Node array
   int *nsegs; // number pf segments in each of the the nnext arcs
   double *data;   // points to the nnodedata supplementary data for this segment
   struct NDskl_node_str **Next;  // points to the node at the other extremity of each of the nnext arcs
   struct NDskl_seg_str **Seg;   // points to the first segment in the arcs, starting from current node.
 }; 
 typedef struct NDskl_node_str NDskl_node;

 typedef struct NDskel_str {
   char comment[80];
   
   int ndims;  // number of dimensions
   int *dims;  // dimension of the underlying grid, only meaningfull when computed from a regular grid
   double *x0;  // origin of the bounding box
   double *delta;  // dimension of the bounding box
    
   int nsegs;  // number of segments
   int nnodes;  // number of nodes
   
   int nsegdata;  // number of additional data for segments
   int nnodedata;  // number of additional data for nodes
   char **segdata_info;  // name of additional fields for segments
   char **nodedata_info;  // name of additional fields for nodes
   
   float *segpos;  // positions of the extremities of segments (2xndims coords for each segment)
   float *nodepos; // positions of the nodes (ndims coords for each segment)
   double *segdata; // additional data for segments (nsegs times nsegdata consecutive values)
   double *nodedata; // additional data for nodes (nnodes times nnodedata consecutive values)
   
   NDskl_seg *Seg;  // segment array (contains all segs)
   NDskl_node *Node;  // nodes array (contains all nodes)
 } NDskel;

The NDskl binary format is organized as follows (blocks are delimited by dummy variables indicating the size of the blocks for FORTRAN compatibility, but they are ignored in C):

NDskl binary format
field	type	size	comment
dummy	int(4B)	1	for FORTRAN compatibility
tag	char(1B)	16	identifies the file type. Value : "NDSKEL"
dummy	int(4B)	1
dummy	int(4B)	1
comment	char(1B)	80	a comment on the file (string)
ndims	int(4B)	1	number of dimensions
dims	int(4B)	20	dimension of underlying grid (0=none, ndims values are read)
x0	double(8B)	20	origin of bounding box (ndims first values are meaningful)
delta	double(8B)	20	size of bounding box (ndims first values are meaningful)
nsegs	int(4B)	1	number of segments
nnodes	int(4B)	1	number of nodes
nsegdata	int(4B)	1	number of additional data associated to segments.
nnodedata	int(4B)	1	number of additional data associated to nodes.
dummy	int(4B)	1
dummy	int(4B)	1	this block is ommited if nsegdata=0
seg_data_info	char(1B)	20×nsegdata	name of the segment data field
dummy	int(4B)	1	this block is ommited if nsegdata=0
dummy	int(4B)	1	this block is ommited if nnodedata=0
node_data_info	char(1B)	20×nnodedata	name of the node data field
dummy	int(4B)	1	this block is ommited if nnodedata=0
dummy	int(4B)	1
segpos	float(4B)	2×nsegs×ndims	coordinates of segment extremities
dummy	int(4B)	1
dummy	int(4B)	1
nodepos	float(4B)	nnodes×ndims	coordinates of nodes
dummy	int(4B)	1
dummy	int(4B)	1
segdata	double(8B)	nsegdata×nsegs	value of the segments data fields
dummy	int(4B)	1
dummy	int(4B)	1
nodedata	double(8B)	nnodedata×nnodes	value of the nodes data fields
dummy	int(4B)	1
dummy	int(4B)	1	following block is repeated for each node (×nnodes).
pos_index	int(4B)	1	index in the nodepos/nodedata arrays
flags	int(4B)	1	flags (identify boundary nodes)
nnext	int(4B)	1	number of connected arcs
type	int(4B)	1	critical index (ndims+1 for bifurcations / trimmed arc axtremity)
index	int(4B)	1	index of this node
nsegs	int(4B)	nnext	number of segments in each connected arc
*	*	*	blue section repeated for each connected arc (×nnext)
nextNode	int(4B)	1	index of the other node of the arc
nextSeg	int(4B)	1	index of the first segment on the arc
dummy	int(4B)	1
dummy	int(4B)	1	following block is repeated for each segment (×nsegs).
pos_index	int(4B)	1	index in the segpos/segdata arrays
nodes	int(4B)	2	index of the 2 nodes at the endpoints of the current arc.
flags	int(4B)	1	flags (identify boundary nodes)
index	int(4B)	1	index of this segment
next_seg	int(4B)	1	index of the next segment in the node (-1 if none)
prev_seg	int(4B)	1	index of the previous segment in the node (-1 if none)
dummy	int(4B)	1

Skeleton files

2420-05-01T06:56:00+01:00

This file type is designed to store the critical points and arcs of the Morse-Smale complex (i.e. one dimensionnal filamentary structures). In skeleton files, the filamentary network is described as lists of nodes representing critical points or bifurcation points if available (see option -breakdown of skelconv), lists of segments tracing the local geometry of arcs and filaments originating from and leading to nodes and described as lists of segments. The base skeleton format is NDskl which is used internally, but this format may be converted to several other more or less complex formats of skeleton files adapted to different applications (see option -to in program skelconv, a list of available formats is displayed when running the program without argument).
nb: Within skeleton files, the segments are always oriented in the ascending direction of the arcs, which does *NOT* necessarily mean that the value of the field is necessarily increasing locally ! Indeed, the value is locally allowed to fluctuate within the persistence threshold, so the field value does not have to be strictly increasing locally along an arc.

Available formats:

-NDskl (Read / Write):
This is the format of the skeleton files created with mse. It is a relatively complex binary format that contains all the information on the geometry and connectivity of the arcs of the Morse-Smale complex (i.e. filaments).

-NDskl_ascii (Write only):
This ASCII format contains the same amount of information as NDskl files, but organized in a different way. In particular, filaments are not described as lists of segments but rather each filament is described by an origin node, a destination node, and a set of sampling points.

-segs_ascii and crits_ascii (Write only):
This is a simplified ASCII file format designed to be easily readable but that only contains a subset of the information available in NDskl files. In particular, segs_ascii files contain a list of individual segments describing the local orientation of the arcs as well as some limited information on the filament they belong to, while crits_ascii contain information on the critical points and bifurcation points only.

-vtk, vtk_ascii, vtp and vtp_ascii (Write only):
These formats are binary and ASCII legacy and XML VTK formats that are readable by several 3D visualization tools, such as VisIt or ParaView for instance.

-NDnet (Write only):
Using this format, skeleton files can be converted to unstructured networks (use netconv to convert NDnet files to other network formats).

Additional data: In addition to the topology and geometry of filamentary structures, more complete formats (i.e. NDskl, NDskl_ascii and all vtk formats) may store arbitrary additional information associated to filaments and nodes that can be used by skelconv (run skelconv filename.NDskl -info for a list of additional data available in skeleton file filename.NDskl). By default, mse stores the following additional data in skeleton type files:

-persistence / persistence_ratio / persistence_nsigmas (Nodes only) :
The persistence (expressed as a difference, ratio or in number of sigmas) of the persistence pair containing the corresponding critical point. A negative or null value indicates that the node is not a critical point or that it does not belong to a persistence pair.

-persistence_pair (Nodes only):
The index of the node that corresponds to the other critical point in the persistence pair (indices start at 0). The value is the index of the current node itself when it is not a critical point or it does not belong to a persistence pair.

-parent_index / parent_log_index (Nodes only):
For each extrema only (i.e. minima and maxima), the index of the node that corresponds to the other extremum into which it would be merged if its persistence pair was canceled (indices start at 0). This can be used to reconstruct the tree of the hierarchy of maxima and minima. The value is -1 for non extrema critical points. The difference between the two versions is that the second (parent_log_index) is the hierarchy computed from the logarithm of the field. This second version is useful only for discrete point samples whose MS-complex is obtained from the delaunay tessellation computed with delaunay_nD. Practically, parent_log_index can be used whenever persistence pairs are cancelled in order of increasing ratio (option -nsig in mse), and parent_index whenever persistence pairs are cancelled in order of increasing difference (option -cut in mse).

-field_value / log_field_value (Nodes and Segments) :
The value of the field and it logarithm. For segments, the suffix _p1 and _p2 is added to indicate which extremity of the segment it corresponds to.

-cell (Nodes and Segments) :
The type and index of the cell corresponding to the node / segment in the initial network (i.e. from which the skeleton was computed). For segments, the suffix _p1 and _p2 is added to indicate which extremity of the segment it corresponds to. The value is a double precision floating number whose integer part is the index of the cell and decimal part its type. For instance, the 156th vertex (i.e. 0-cell) in the cell complex is represented as 156.0, while the 123th tetrahedron is 123.3. Note that the index of the 0-cell correpond to the index of the pixel / vertices in the original network from which the skeleton was computed.

-robustness / robustness_ratio (Nodes and Segments) :
The robustness of the node / segment. Robustness is a local measure of how contrasted the critical point / filament is with respect to its local background, and it is therefore a good way to select only highly contrasted subsets of the filamentary structures (see option -trimBelow in skelconv). Note that robustness, like persistence, is defined as a difference or ratio between the value of the field in two points, so the robustness threshold has the same order of magnitude as the persistence threshold.

- type (Segments only) :
The type of arc the segment belongs to. The value corresponds to the lowest critical index of the two critical points at the extremities of the arc the segments belongs to. For instance, in dimension D, the ridges (filaments) have type D-1.