Module pept.utilities.traverse

Functions

def traverse2d(...)

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

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

This function computes the number of lines that passes through each pixel, saving the result in pixels. It does so in an efficient manner, in which for every line, only the pixels that it 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 traverse2d(), as it WILL segfault on wrong input data. Details are given below, along with an example call.

Parameters

pixels : numpy.ndarray(dtype = numpy.int64, ndim = 2)
    The `pixels` parameter is a numpy.ndarray of shape (X, Y) 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 pixel.
lines : numpy.ndarray(dtype = numpy.float64, ndim = 2)
    The `lines` parameter is a numpy.ndarray of shape(N, 5), where each
    row is formatted as [time, x1, y1, x2, y2]. Only indices 1:5
    will be used as the two points P1 = [x1, y1] and P2 = [x2, y2]
    defining the line (or LoR).
grid_x : numpy.ndarray(dtype = numpy.float64, ndim = 1)
    The grid_x parameter is a one-dimensional grid that delimits the
    pixels in the x-dimension. It must be *sorted* in ascending order
    with *equally-spaced* numbers and length X + 1 (pixels.shape[0] + 1).
grid_y : numpy.ndarray(dtype = numpy.float64, ndim = 1)
    The grid_y parameter is a one-dimensional grid that delimits the
    pixels in the y-dimension. It must be *sorted* in ascending order
    with *equally-spaced* numbers and length Y + 1 (pixels.shape[1] + 1).

Example usage

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

>>> import numpy as np
>>> from pept.utilities.traverse import traverse2d
>>>
>>> plane = [300, 400]
>>> number_of_pixels = [30, 40]
>>> pixels = np.zeros(number_of_pixels)

The grid has one extra element than the number of pixels. For example, 5 pixels 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, plane[0], number_of_pixels[0] + 1)
>>> grid_y = np.linspace(0, plane[1], number_of_pixels[1] + 1)
>>>
>>> random_lines = np.random.random((100, 5)) * 100

Calling traverse2d() will modify pixels in-place.

>>> traverse2d(pixels, random_lines, grid_x, grid_y)

Note

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)..

def traverse3d(...)

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

Function Signature: traverse3d( long[:, :, :] voxels, # Initialised to zero! 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

voxels : numpy.ndarray(dtype = numpy.int64, 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.
lines : numpy.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_x : numpy.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_y : numpy.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_z : numpy.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).

Example usage

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)

Note

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)..