pept.utilities.traverse3d#

pept.utilities.traverse3d(double[:, :, :] voxels, const double[:, :] lines, const double[:] grid_x, const double[:] grid_y, const double[:] grid_z) → void#

Fast voxel traversal for 3D lines (or LoRs).

Function Signature:
    traverse3d(
        long[:, :, :] voxels,       # Initialised!
        double[:, :] lines,         # Has exactly 7 columns!
        double[:] grid_x,           # Has voxels.shape[0] + 1 elements!
        double[:] grid_y,           # Has voxels.shape[1] + 1 elements!
        double[:] grid_z            # Has voxels.shape[2] + 1 elements!
    )

This function computes the number of lines that passes through each voxel, saving the result in voxels. It does so in an efficient manner, in which for every line, only the voxels that is passes through are traversed.

As it is highly optimised, this function does not perform any checks on the validity of the input data. Please check the parameters before calling traverse3d, as it WILL segfault on wrong input data. Details are given below, along with an example call.

Parameters

voxelsnumpy.ndarray(dtype = numpy.float64, ndim = 3): The voxels parameter is a numpy.ndarray of shape (X, Y, Z) that has been initialised to zeros before the function call. The values will be modified in-place in the function to reflect the number of lines that pass through each voxel.
linesnumpy.ndarray(dtype = numpy.float64, ndim = 2): The lines parameter is a numpy.ndarray of shape(N, 7), where each row is formatted as [time, x1, y1, z1, x2, y2, z2]. Only indices 1:7 will be used as the two points P1 = [x1, y1, z2] and P2 = [x2, y2, z2] defining the line (or LoR).
grid_xnumpy.ndarray(dtype = numpy.float64, ndim = 1): The grid_x parameter is a one-dimensional grid that delimits the voxels in the x-dimension. It must be sorted in ascending order with equally-spaced numbers and length X + 1 (voxels.shape[0] + 1).
grid_ynumpy.ndarray(dtype = numpy.float64, ndim = 1): The grid_y parameter is a one-dimensional grid that delimits the voxels in the y-dimension. It must be sorted in ascending order with equally-spaced numbers and length Y + 1 (voxels.shape[1] + 1).
grid_znumpy.ndarray(dtype = numpy.float64, ndim = 1): The grid_z parameter is a one-dimensional grid that delimits the voxels in the z-dimension. It must be sorted in ascending order with equally-spaced numbers and length Z + 1 (voxels.shape[2] + 1).

Notes

This function is an adaptation of a widely-used algorithm [1], optimised for PEPT LoRs traversal.

1: Amanatides J, Woo A. A fast voxel traversal algorithm for ray tracing. InEurographics 1987 Aug 24 (Vol. 87, No. 3, pp. 3-10)..

Examples

The input parameters can be easily generated using numpy before calling the function. For example, if a volume of 300 x 400 x 500 is split into 30 x 40 x 50 voxels, a possible code would be:

>>> import numpy as np
>>> from pept.utilities.traverse import traverse3d
>>>
>>> volume = [300, 400, 500]
>>> number_of_voxels = [30, 40, 50]
>>> voxels = np.zeros(number_of_voxels)

The grid has one extra element than the number of voxels. For example, 5 voxels between 0 and 5 would be delimited by the grid [0, 1, 2, 3, 4, 5] which has 6 elements (see off-by-one errors - story of my life).

>>> grid_x = np.linspace(0, volume[0], number_of_voxels[0] + 1)
>>> grid_y = np.linspace(0, volume[1], number_of_voxels[1] + 1)
>>> grid_z = np.linspace(0, volume[2], number_of_voxels[2] + 1)
>>>
>>> random_lines = np.random.random((100, 7)) * 300

Calling traverse3d will modify voxels in-place.

>>> traverse3d(voxels, random_lines, grid_x, grid_y, grid_z)