trimesh.voxel.runlength¶

Numpy encode/decode/utility implementations for run length encodings.

# Run Length Encoded Features

Encoding/decoding functions for run length encoded data.

We include code for two variations:

run length encoding (RLE)
binary run length encdoing (BRLE)

RLE stores sequences of repeated values as the value followed by its count, e.g.

`python dense_to_rle([5, 5, 3, 2, 2, 2, 2, 6]) == [5, 2, 3, 1, 2, 4, 6, 1] `

i.e. the value 5 is repeated 2 times, then 3 is repeated 1 time, 2 is repeated 4 times and 6 is repeated 1 time.

BRLE is an optimized form for when the stored values can only be 0 or 1. This means we only need to save the counts, and assume the values alternate (starting at 0).

`python dense_to_brle([1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0]) == [0, 2, 4, 7, 2] `

i.e. the value zero occurs 0 times, followed by 2 ones, 4 zeros, 7 ones and 2 zeros.

Sequences with counts exceeding the data type’s maximum value have to be handled carefully. For example, the uint8 encoding of 300 zeros (uint8 has a max value of 255) is:

RLE: [0, 255, 0, 45] (0 repeated 255 times + 0 repeated 45 times)
BRLE: [255, 0, 45, 0] (255 zeros + 0 ones + 45 zeros + 0 ones)

This module contains implementations of various RLE/BRLE operations.

trimesh.voxel.runlength.brle_gather_1d(brle_data, indices)¶

Gather BRLE data values at the provided dense indices.

This is equivalent to rle_to_dense(rle_data)[indices] but the implementation does not require the construction of the dense array.

If indices is known to be in order, use sorted_brle_gather_1d.

Parameters:

rle_data (run length encoded data)
indices (dense indices)

Returns:

numpy array, dense data at indices, same length as indices and dtype as
rle_data

trimesh.voxel.runlength.brle_gatherer_1d(indices)¶

Get a gather function at the given indices.

Because gathering on BRLE data requires sorting, for instances where gathering at the same indices on different RLE data this can save the sorting process.

If only gathering on a single RLE iterable, use brle_gather_1d.

Parameters:

indices (iterable of integers)

Returns:

gather function, mapping (rle_data, dtype=None) -> values.
values will have the same length as indices and dtype provided,
or rle_data.dtype if no dtype is provided.

trimesh.voxel.runlength.brle_length(brle)¶: Optimized implementation of len(brle_to_dense(brle))

trimesh.voxel.runlength.brle_logical_not(brle)¶

Get the BRLE encoding of the logical_not`ed dense form of `brle.

Equivalent to dense_to_brle(np.logical_not(brle_to_dense(brle))) but highly optimized - just pads brle with a 0 on each end (or strips is existing endpoints are both zero).

Parameters:

brle (rank 1 int array of binary run length encoded data)

Returns:

rank 1 int array of binary run length encoded data corresponding to
element-wise not of the input.

trimesh.voxel.runlength.brle_mask(rle_data, mask)¶

Perform masking of the input binary run-length data.

Parameters:

brle_data (iterable of binary run length encoded data)
mask (iterable of bools corresponding to the dense mask.)

Return type:

iterable dense values of brle_data wherever mask is True.

trimesh.voxel.runlength.brle_reverse(brle_data)¶: Equivalent to dense_to_brle(brle_to_dense(brle_data)[-1::-1]).

trimesh.voxel.runlength.brle_strip(brle_data)¶

Remove leading and trailing zeros.

Parameters:

brle_data (binary run length encoded data.)

Returns:

(stripped_brle_data, padding)
stripped_brle_data (rle data without any leading or trailing zeros)
padding (2-element dense padding)

trimesh.voxel.runlength.brle_to_brle(brle, dtype=<class 'numpy.int64'>)¶

Almost the identity function.

Checks for possible merges and required splits.

trimesh.voxel.runlength.brle_to_dense(brle_data, vals=None)¶

Decode binary run length encoded data to dense.

Parameters:

brle_data (BRLE counts of False/True values)
vals (if not None, a length 2 array/list/tuple with False/True substitute) – values, e.g. brle_to_dense([2, 3, 1, 0], [7, 9]) == [7, 7, 9, 9, 9, 7]

Return type:

rank 1 dense data of dtype bool if vals is None else vals.dtype

Raises:

ValueError if vals it not None and shape is not (2,) –

trimesh.voxel.runlength.brle_to_rle(brle, dtype=<class 'numpy.int64'>)¶

trimesh.voxel.runlength.brle_to_sparse(brle_data, dtype=<class 'numpy.int64'>)¶

trimesh.voxel.runlength.dense_to_brle(dense_data, dtype=<class 'numpy.int64'>)¶

Get the binary run length encoding of dense_data.

Parameters:

dense_data (rank 1 bool array of data to encode.)
dtype (numpy int type.)

Return type:

Binary run length encoded rank 1 array of dtype dtype.

Raises:

ValuError if dense_data is not a rank 1 bool array. –

trimesh.voxel.runlength.dense_to_rle(dense_data, dtype=<class 'numpy.int64'>)¶: Get run length encoding of the provided dense data.

trimesh.voxel.runlength.merge_brle_lengths(lengths)¶: Inverse of split_long_brle_lengths.

trimesh.voxel.runlength.merge_rle_lengths(values, lengths)¶: Inverse of split_long_rle_lengths except returns normal python lists.

trimesh.voxel.runlength.rle_gather_1d(rle_data, indices, dtype=None)¶

Gather RLE data values at the provided dense indices.

This is equivalent to rle_to_dense(rle_data)[indices] but the implementation does not require the construction of the dense array.

If indices is known to be in order, use sorted_gather_1d.

Parameters:

rle_data (run length encoded data)
indices (dense indices)
dtype (numpy dtype. If not provided, uses rle_data.dtype)

Returns:

numpy array, dense data at indices, same length as indices and dtype as
rle_data

trimesh.voxel.runlength.rle_gatherer_1d(indices)¶

Get a gather function at the given indices.

Because gathering on RLE data requires sorting, for instances where gathering at the same indices on different RLE data this can save the sorting process.

If only gathering on a single RLE iterable, use rle_gather_1d.

Parameters:

indices (iterable of integers)

Returns:

gather function, mapping (rle_data, dtype=None) -> values.
values will have the same length as indices and dtype provided,
or rle_data.dtype if no dtype is provided.

trimesh.voxel.runlength.rle_length(rle)¶: Optimized implementation of len(rle_to_dense(rle_to_brle(rle)))

trimesh.voxel.runlength.rle_mask(rle_data, mask)¶

Perform masking of the input run-length data.

Parameters:

rle_data (iterable of run length encoded data)
mask (iterable of bools corresponding to the dense mask.)

Return type:

iterable of dense values of rle_data wherever mask is True.

trimesh.voxel.runlength.rle_reverse(rle_data)¶: Get the rle encoding of the reversed dense array.

trimesh.voxel.runlength.rle_strip(rle_data)¶

Remove leading and trailing zeros.

Parameters:: rle_data (run length encoded data)
Returns:: stripped_rle_data: rle data without any leading or trailing zeros padding: 2-element dense padding
Return type:: (stripped_rle_data, padding)

trimesh.voxel.runlength.rle_to_brle(rle, dtype=None)¶

Convert run length encoded (RLE) value/counts to BRLE.

RLE data is stored in a rank 1 array with each pair giving: (value, count)

e.g. the RLE encoding of [4, 4, 4, 1, 1, 6] is [4, 3, 1, 2, 6, 1].

Parameters:: rle ((n,) int) – Run length encoded data
Returns:: otherwise brle_to_brle is called on that list before returning.
Return type:: equivalent binary run length encoding. a list if dtype is None,
Raises:: ValueError – If any of the even counts of rle are not zero or 1.

trimesh.voxel.runlength.rle_to_dense(rle_data, dtype=<class 'numpy.int64'>)¶: Get the dense decoding of the associated run length encoded data.

trimesh.voxel.runlength.rle_to_rle(rle, dtype=<class 'numpy.int64'>)¶

Almost the identity function.

Checks for possible merges and required splits.

trimesh.voxel.runlength.rle_to_sparse(rle_data)¶: Get dense indices associated with non-zeros.

trimesh.voxel.runlength.sorted_brle_gather_1d(brle_data, ordered_indices)¶

Gather brle_data at ordered_indices.

This is equivalent to brle_to_dense(brle_data)[ordered_indices] but avoids the decoding.

Parameters:

raw_data (iterable of run-length-encoded data.)
ordered_indices (iterable of ints in ascending order.)

Returns:

raw_data iterable of values at the dense indices, same length as
ordered indices.

trimesh.voxel.runlength.sorted_rle_gather_1d(rle_data, ordered_indices)¶

Gather brle_data at ordered_indices.

This is equivalent to rle_to_dense(brle_data)[ordered_indices] but avoids the decoding.

Parameters:

brle_data (iterable of run-length-encoded data.)
ordered_indices (iterable of ints in ascending order.)

Returns:

brle_data iterable of values at the dense indices, same length as
ordered indices.

trimesh.voxel.runlength.split_long_brle_lengths(lengths, dtype=<class 'numpy.int64'>)¶

Split lengths that exceed max dtype value.

Lengths l are converted into [max_val, 0] * l // max_val + [l % max_val]

e.g. for dtype=np.uint8 (max_value == 255) ` split_long_brle_lengths([600, 300, 2, 6], np.uint8) == [255, 0, 255, 0, 90, 255, 0, 45, 2, 6] `

trimesh.voxel.runlength.split_long_rle_lengths(values, lengths, dtype=<class 'numpy.int64'>)¶

Split long lengths in the associated run length encoding.

e.g. `python split_long_rle_lengths([5, 300, 2, 12], np.uint8) == [5, 255, 5, 45, 2, 12] `

Parameters:

values (values column of run length encoding, or rle[::2])
lengths (counts in run length encoding, or rle[1::2])
dtype (numpy data type indicating the maximum value.)

Returns:

values, lengths associated with the appropriate splits. lengths will be
of type dtype, while values will be the same as the value passed in.