# PRT2 and SPRT Specification¶

## General Notes¶

### Breaking Compatibility with PRT 1.0 and 1.1¶

The PRT1 format includes a version number, but was written to support forward + backwards compatibility without permitting the kinds of breaking changes found in PRT2. We choose to signal that compatibility is broken by slightly changing the magic number.

A list of major differences between PRT1 and PRT2 include:

• Particles are always stored in sequential particle chunks within a file chunk instead of as a single compressed stream. Multiple versions of the particles (e.g. a preview subset) are supported by giving each stream of chunks a name.
• There is a selectable compression scheme which determines the data layout and compression of one particle chunk.
• Strings and many integers are stored in a variable-sized format instead of fixed-sized as before. An exception is some fields, like particle count, that are typically rewritten to a correct value after the file output is complete.
• Each named stream of particles may have a particle chunk index, generally written after the particles are completed to allow random seeking of the particles when reading them.
• SPRT files are valid PRT2, with an extra chunk that a conforming PRT2 reader would skip over.
• The bounding box global metadata has been removed, and a new generic channel metadata “Extents” was added. This new channel metadata can be used to provide the measured extents values for any particle channel. The bounding box is now “Extents” metadata for the channel “Position”.
• Bounding boxes, voxel coordinate systems, and other hard-coded floating point data are float64 instead of float32, to keep it simple while allowing for a higher precision Position channel.
• The particle channels are now specified as the first FileChunk.

### Position Channel Support for Both Double and Float¶

In order to support this, bounding boxes need to also always be double, or support either. For simplicity, we choose to require that bounding boxes are always double, as converting float -> double -> float is a lossless operation and this is at worst a 24-byte overhead per bounding box stored.

### Integer/String Representation¶

PRT1 stored channel names in fixed-size 32 byte buffers. We remove this restriction by taking a page from protobuf, which specifies some simple variable-sized encodings for integers and strings. We are not adopting anything else from protobuf.

For most integers we use the base 128 varint as used in protobuf. This is called “varint” throughout this document.

For strings we use a varint followed by the specified number of bytes of UTF-8 encoded data. This is called “varstring” throughout this document.

Some integers, such as the particle count or offsets into the file for the particle chunk and octree indexes, may not be known until the particle file has been written to the end. These should be uint64, not varint, and should be populated with 0xFFFFFFFFFFFFFFFF on initial writing.

### Type IDs¶

In PRT1, there are integer type IDs. To be more general in PRT2, we change these to strings. For most of the types, this does not make the storage significantly larger, because of the varstring representation.

Type ID Description
“uint8” 8-bit unsigned integer
“uint16” 16-bit unsigned integer
“uint32” 32-bit unsigned integer
“uint64” 64-bit unsigned integer
“int8” 8-bit two’s complement integer
“int16” 16-bit two’s complement integer
“int32” 32-bit two’s complement integer
“int64” 64-bit two’s complement integer
“float16” 16-bit IEEE floating point (binary16)
“float32” 32-bit IEEE floating point (binary32)
“float64” 64-bit IEEE flaoting point (binary64)
“string” UTF-8 string, encoded as varstring described above

By specifying the Type IDs as strings, future expansion of the types, for example adding a “bool” type, can be done fairly naturally. One difficulty, though, is that if a reader of the file doesn’t know how big an unfamiliar type is, it cannot itself determine the packed particle layout. For this reason, the specification of particle layout in the ‘Chan’ chunk includes the number of bytes each channel takes up so a reader can skip a channel if desired.

In PRT1, a channel data type was specified by the Type ID and an arity. In PRT2, these are combined together into one Type ID string, which is a strict subset of the types supported by [libdynd](https://github.com/libdynd/libdynd). The arity is specified as a “fixed” dimension, by prepending _”N * “_ to one of the above Type IDs.

For example, a channel with 3 float64s has Type ID “3 * float64”. Note that a channel with one element was equated with a scalar in PRT1. In PRT2, there is a difference between “float64” and “1 * float64”, however readers/writers may choose to treat them as equivalent.

### Binary Layout Syntax¶

This file uses a syntax for specifying binary layouts inspired by (but different from) the type system used in libdynd. The following specifies a structure, with no padding/alignment bytes between the fields:

{
firstField: int16
secondField: float64
}


An array is specified by pre-multiplying by a number. “3 * float32” is an array of 3 floats, “3 * 3 * float32” is a 3x3 matrix of floats.

The type “varstring” means a variable-szied string as specified above.

For arrays whose size is first specified as an integer, we use the syntax “^varName” to reference the previous value. For an array dimension like this, we use “fixed[^varName]”. So a typical variable-szied array of structures will look like:

{
arrSize: varint,
arrValues: fixed[^arrSize] * {
Position: 3 * float32,
Name: varstring
}
}


SIDE NOTE: If you want to see an intense application of dependent types using this kind of system to define actual parsers, check out the [PADS project](http://www.cs.princeton.edu/~dpw/papers/pads-overview.pdf).

## File Format Specification¶

A PRT file consists of a PRT Header followed by a sequence of adjacent FileChunks finishing at the end of file. A valid PRT file must begin with a ‘Chan’ chunk, and contain a ‘Part’ chunk. The metadata chunks ‘Meta’ are permitted anywhere after the ‘Chan’ chunk, including before or after the ‘Part’ chunk, so as to make it possible to trivially add additional metadata to an existing PRT file.

All multi-byte values, for example uint64, are stored in little-endian byte order.

The PRT header is very simple containing just the magic number and file format versioning information. The formatVersion value is 3 for the PRT2 format as specified in this document. Extensions that are compatible with older readers are done by adding new FileChunks, and a different formatVersion means a fully incompatible file format update.

{
# {192, 'P', 'R', 'T', '2', '\r', '\n', 26}
# {0xC0, 0x50, 0x52, 0x54, 0x32, 0x0D, 0x0A, 0x1A}
magic: uint64,
# 3 (For PRT2 version 2.0 format)
formatVersion: uint32,
}


### File Chunks¶

The rest of the file is a series of FileChunks. These are similar to the chunks in PRT1.1, but particle data is incorporated into a chunk instead of being a special section. Each chunk consists of a 4-byte ASCII chunk ID (starts with capital for all official PRT chunks, must be full lowercase for third-party custom chunks), a uint64 representing the size of the chunk data, followed by the chunk data.

If a PRT reader does not understand a chunk, it should skip over it.

The chunkSize may not be known when the chunk is being written. In such case, the value 0xFFFFFFFFFFFFFFFF (maximum uint64 value) should be written initially, then updated later.

{
chunkType: string[4],
chunkSize: uint64,
chunkData: fixed[^chunkSize] * byte
}


### FileChunk ‘Chan’¶

The first chunk in a PRT file must be the ‘Chan’ chunk. This chunk contains a serialized representation of all the channels, as follows. The data type is now represented as a string, as specified above. Channels may only contain numeric types, not the “string” type.

See the appendix for standard channel names. A particle file should at minimum have a ‘Position’ channel of 3 float16s, 3 float32s, or 3 float64s.

Additionally, no channel offsets are stored here. The packing of these fields into the file is determined by the compression/layout scheme.

{
channelCount: varint,
channels: fixed[^channelCount] * {
# The name of the channel.
# Must match the regex "[a-zA-Z_][0-9a-zA-Z_]\*".
name: varstring,
# Type ID, as specified above (numeric, not "string")
dataType: varstring
# Number of bytes the channel takes in packed storage
# (It's redundant, but allows for adding new types
# a reader may not know the size of, so that reader
# can skip them.)
sizeBytes: varint
}
}


### FileChunk ‘Meta’¶

This chunk provides both global and channel metadata. The value contains one instance of the specified type.

See the appendix for standard global and channel metadata. It is valuable to calculate and store the available global metadata, for example with the bounding box available file readers can display the particle box without actually reading the particle data.

Channel metadata is different from global metadata in that the name begins with the channel name, followed by a dot, followed by the metadata name. For example the ‘Extents’ metadata for the ‘Position’ channel is called ‘Position.Extents’. Another example channel metadata is how to interpret the channel with respect to transformations, i.e. should the value be scaled/rotated/translated when transforing the particle data.

{
# The name of the metadata
name: varstring,
# The type of the metadata, see the Type ID spec above.
type: varstring,
value: bytes[to the end of the chunk]
}


### FileChunk ‘Part’ and ‘PrtO’¶

The particle data, written as a brief header followed by series of particle chunks. There must be one default ‘Part’/’PrtO’ filechunk, whose particleStreamName must contain the empty string. Every ‘Part’/’PrtO’ chunk must have a corresponding ‘PIdx’ chunk somewhere in the file.

The only difference between a ‘Part’ chunk and a ‘PrtO’ is that the ‘PrtO’ has a 3*float32 offset value to the position for each particle chunk. This “position offset” mode provides a way to increase the precision of a float32 Position channel without moving to float64 precision, when used in combination with a spatial sorting of points like in the SPRT format.

When the “position offset” mode is used to target a specific absolute precision, the exponent of the precision is stored in a metadata chunk “Position.PrecisionExponent” as an int32. For example, if this metadata value is -10, and the file’s unit is meters, the storage precision will be 2^-10, which is about a millimeter.

The header at the beginning of this FileChunk is as follows. Since the particleCount and particleChunkCount are not typically known when beginning to write the file, they should initially have the value 0xFFFFFFFFFFFFFFFF, and be updated once the values are known.

{
# Name of the stream of particles, should be empty
# for the default stream.
particleStreamName: varstring,
# How each particle chunk is compressed.
compressionScheme: varstring,
# The number of particles.
particleCount: uint64
# The number of particle chunks.
particleChunkCount: uint64
fixed[^particleChunkCount] * {
# The number of bytes in the chunk data
chunkSize: uint32,
# The number of particles in the chunk
chunkParticleCount: uint32,
# For 'PrtO' only, an offset which is added to
# the Position channel of every particle in the
# particle chunk.
PrtO_positionOffset: float32 * 3, # In 'PrtO' only
# The particle chunk data
chunkData: fixed[^chunkSize] * byte
}
}


### Particle Chunk Compression¶

In the header for the ‘Part’ chunk, there is a compressionScheme string. The values of each chunk are reordered and compressed according to this value. The values are:

• “uncompressed”: The channels of each particle are apcked one after the other, and the particles are packed one after the other.
• “zlib”: The particles are packed as in the uncompressed case, then compressed with zlib.
• “transpose-zlib”: The particles are transposed byte-wise, then compressed with zlib. The transposition takes byte 0 of all the particles, then byte 1 of all the particles, etc.
• “transpose”: Just the transposition of transpose-zlib, temporarily implemented for test purposes

### Chunk Compression Strategy¶

The recommended default compression strategy is “transpose-zlib”. The idea is to reorder the data in a deterministic fashion so that things that might repeat are presented to the compressor all at once, think of it like a preconditioner to a matrix solver.

Small Panel3 benchmark (U) = uncompressed input, (T) = transposed input, sizes in KB. This benchmark is using external compressors on the uncompressed PRT2 to try and get an idea for a lot of compressors without implementing them into the format:

Compressor Size (U) Size (T) Time (U) Time (T) Multithreaded
raw data 901463 901463 N/A N/A N/A
lz4 -1 663392 537104 2.5 0.8 Yes
lz4 -9 599690 477271 10.0 14.8 Yes
zpaq -m 1 569849 469992 30.6 14.7 Yes
zstd (unstable) 652129 430211 6.1 2.6 No
lzham -l1 458318 428955 92.9 68.8 Yes
gzip -6 519892 415897 65.7 60.5 No
bzip2 372046 403243 92.9 75.6 No
zpaq -m 3 344185 364771 144.2 91.8 Yes
zpaq -m 5 245353 341527 1034.5 741.4 Yes

Further Panel3 benchmark with per-chunk compression implemented in the code:

Compressor Size (KB) Time (write) Time (read)
uncompressed 901463 2.6 2.3
zlib 520255 62.0 6.2
transpose_zlib 411256 60.0 5.1
transpose_zstd 428865 5.1 3.4

Same Mini frame 9 benchmark:

Compressor Size (KB) Time (write) Time (read)
uncompressed 58595 0.2 0.1
zlib 36883 2.6 0.3
transpose_zlib 38888 3.0 0.3
transpose_zstd 36489 0.3 0.2

A curious result for this one is saving to SPRT with transpose_zstd produced a file size 24304, and took 0.8 seconds. It looks like the floating point Morton order can sometimes increase compressibility.

Same UTMCrimeHouse benchmark:

Compressor Size (MB) Time (write) Time (read)
uncompressed 4582 37.4 55.4
zlib 2220 223.0 30.8
transpose_zlib 2566
33.3
transpose_zstd 2648 24.0 31.1

### FileChunk ‘Pldx’¶

This chunk provides an index of the particle chunks in the ‘Part’ chunk. This index provides information for seeking into the particles and accessing any chunk of particles randomly. It will generally be after the ‘Part’ chunk, but may appear anywhere in the file. Every ‘Part’ chunk must have a corresponding ‘PIdx’ chunk with the same particleStreamName somewhere in the file.

The index is stored as sizes instead of absolute offsets so that the storage is more compact as stored by the varint. The general expectation is that the entire particle chunk index will be read into memory and transformed into a data structure with easy random access.

{
# Name of the stream of particles, should be empty
# for the default stream.
particleStreamName: varstring,
# The number of particle chunks (same as in 'Part' chunk)
particleChunkCount: uint64
fixed[^particleChunkCount] * {
# The size of the chunk, in bytes, including both the
# size stored in-line and all the chunk data.
chunkSize: varint,
# The number of particles in the chunk
chunkParticleCount: varint
}
}


### FileChunk ‘Sldx’¶

This chunk is required in SPRT files, which have the .sprt extension instead of just .prt. It specifies additional octree index that layers on top of the particle chunk structure. The octree used is based on floating-point Morton order (FPMO), and defined in terms of a floating-point voxels (FPVOX) object. The important property that makes this all work is that points sorted in FPMO correspond to a depth-first traversal of the FPVOX octree.

The FPVOX can be related to the binary representation of floating-point numbers, in particular 32-bit float. It specifies a single voxel by a 3-vector of 32-bit integers and an exponent. The exponent is a single unsigned byte, with the same meaning as the exponent in 32-bit float. The voxel size for the exponent is thus 2^(exponent - 127), and can be reconstructed from the exponent by a shift operation followed by reinterpretation as float. The minimum coordinate of the voxel is simply the voxel size times the integer coordinates, and the voxel is inclusive towards the minimum, and exclusive towards the maximum, thus for a given voxel size, every coordinate belongs to a unique voxel.

The octree index matches precisely with the particle chunk index, specifying the FPVOX of each chunk. In almost all cases, each FPVOX maps to a single chunk, but it is possible that the particles for an FPVOX will be split across multiple chunks, in which case the FPVOX will appear multiple times in a row.

IMPORTANT NOTE: In an SPRT file, every named ‘Part’/’PrtO’ filechunk must contain exactly the same number of chunks, corresponding to the ‘SIdx’ index. This may result in chunks with zero particles in them, but the PRT2 format can handle this just fine.

{
# The number of particle chunks (same as 'Part', 'PIdx' chunk)
particleChunkCount: uint64
# The octree index
fixed[^particleChunkCount] * {
# The FPVOX (voxel coordinate + raw exponent)
voxelCoord: 3 * int32,
rawExponent: uint8
}
}


## Appendix A: Standard Channel Names¶

Channel names are arbitrary, apart from the identifier-like naming restriction. For interoperability to work, readers and writers of PRT files must use the same channel names, and this section sets out standard naming conventions for PRT files.

In this table, “float##” means any of float16, float32, or float64 is acceptable. The interpretation column indicates what interpretation metadata should be applied to the channel so that programs know how to transform it properly. The time unit used for channels like Velocity, Spin, and Acceleration is always seconds. This can be related to a sequence of frames using the FrameRate global metadata.

Channel Name Data Type(s) Interpretation Description
Position 3 * float## “Point” The particle position
Velocity 3 * float## “Vector” The particle velocity (dPosition/dt)
Orientation 4 * float## “Orientation” Orientation stored as a quaternion, with the 3 imaginary components first and the real component last.
Spin 4 * float## “Rotation” Representation of dOrientation/dt as an axis vector, followed by angle in radians per second.
Acceleration 3 * float## “Vector” The particle acceleration (dVelcotiy/dt).
Normal 3 * float## “Normal” Normal of some surface.
Tangent 3 * float## “Normal” Tangent fo some surface.
Binormal 3 * float## “Normal” Cross product of Tangent and Normal.
Density float## NA The particle density.
Intensity float## NA Strength of return signal in lidar scan. Range is from 0 to 1.
Color 3 * float## NA RGB Color. White is [1.0, 1.0, 1.0].
TextureCoord 3 * float## NA Default texture coordinates.
ID int 32, int64 NA A particle ID used to match up particles across files, when particles may be created or destroyed over time.
BirthPosition 3 * float## “Point” The Position at which the particle was born.

## Appendix B: Global Metadata Chunks¶

There are standard name/value pairs defined for the global ‘Meta’ chunks. Implementations are encouraged to support them and always write them to PRT2 compliant files. If one of these values is not specified in the PRT file, implementations should act as if the default value (indicated below) was provided.

### LengthUnitInMicrometers¶

A float64 representing the length unit used by the file, in terms of micrometers. This value is used to scale channels that are length measures (ex. Position, Velocity, etc.) in order to convert them to meters. Here are some common units:

Value Name
0.0(default) Unknown/unspecified unit
25400.0 Inches
304800.0 Feet
914400.0 Yards
1609344000.0 Miles
1.0e+3 Millimeters
1.0e+4 Centimeters
1.0e+6 Meters
1.0e+9 Kilometers

### CoordSys¶

This is an int32 value representing the handedness and up vector of the coordinate system used by 3D data. Its value is drawn from this table:

Value Meaning
0(default) Unspecified
1 right handed Y-up
2 right handed Z-up
3 left handed Y-up
4 left handed Z-up

### FrameRate¶

This is a rational number as a “2 * uint32” (numerator, denominator), specified in frames per second.

## Appendix C: Channel Metadata Chunks¶

There are standard name/value pairs defined for per-channel ‘Meta’ chunks. Implementations are encouraged to support them and always write them to PRT2 compliant files. If one of these values is not specified in the PRT file, implementations should act as if the default value (indicated below) was provided.

### Extents¶

A generalization of the BoundBox global metadata from PRT1. For a channel with arity N, type T (<N> * <T>), this is metadata with 2*N values of type T (<2 * N> * <T>). The first N are the minimum values seen in the particles for the specified channel, and the last N are the maximum values seen.

The BoundBox global metadata from PRT1 is now an Extents channel metadata for the Position channel.

### Mean¶

For a channel with arity N, type T (<N> * <T>), this is metadata with N values of type T. The N values is the mean of the particles for the specified channel.

The Mean global metadata is a Mean channel metadata for the Position channel.

### Standard Deviation¶

For a channel with arity N, type T (<N> * <T>), this is metadata with N values of type T. The N values is the standard deviation of the particles for the specified channel.

The Standard Deviation global metadata is a stdDev channel metadata for the Position channel.

### Interpretation¶

A varstring indicating the interpretation of a channel’s data. Can be used to automatically transform data when converting units, coordinate systems, etc.

NOTE: In PRT1, this was specified as an int32. In PRT2, it is a string to allow for more self-documenting extensibility.

Value Description Compatible Data Type
“Point” A 3D position vector(ex. Position) 3 * float## (X,Y,Z)
“Vector” A 3D direction and magnitude(ex. Velocity) 3 * float## (X,Y,Z)
“Normal” A 3D direction orthogonal to a surface(ex. Normal) 3 * float## (X,Y,Z)
“Orientation” A 3D orientation encoded as a unit quaternion (ex. Orientation) 4 * float## (I,J,K,R) Imaginary parts first
“Rotation” A 3D rotation encoded as an angle & axis (ex. Spin) 4 * float## (X, Y, Z, Angle) Axis first
“Scalar” A scalar value affected by the scale portion of a transformation (ex. Radius) float##