pept.utilities.traverse2d

pept.utilities.traverse2d(double[:, :] pixels, const double[:, :] lines, const double[:] grid_x, const double[:] grid_y) → void

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

Function Signature:
    traverse2d(
        double[:, :] 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

pixelsnumpy.ndarray(dtype = numpy.float64, 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.

linesnumpy.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_xnumpy.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_ynumpy.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).

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