The rays of a source¶

The samples of the rays out from a source, each one's ray, its step and its cell.

Requires

the lattice's extents (cells), the source's cell, the Reach r (cells), and which rays: rim, one to each cell of the reach's edge (what a source sends, split among them), or within, one to each cell within the reach (what a cell receives, each down its own line).

Provides

each sample's ray (an integer, the ray's number in the reach's fixed order), its step (1 at the source's neighbour, growing outward) and its cell (the lattice's index it reads), only the samples inside the lattice: a ray stops at its first step outside it.

Law

ray k runs from the source to the k-th offset o_k of the reach (its rim, or every offset within it, by row then column); its step j's cell is the source plus line(o_k)[j - 1], the digital line's j-th cell, each step one Chebyshev ring further out.

Source

Bresenham, Algorithm for computer control of a digital plotter, IBM Systems Journal 4(1), 1965; Amanatides & Woo, A fast voxel traversal algorithm for ray tracing, Eurographics 1987.

Proof

invariant, limit.

No Trait form: waits on the middle: a key kernel, its samples a relation of ray and step whose cell is a formula of them, materialised or computed on the fly as the middle decides; until then a reference.

rays.fan(shape, source, reach, rays)

The samples of the rays out from a source, each one's ray, its step and its cell: the keys a source's law folds over, ordered(it.ray, it.step) with @ before, its cells read and given back through the relation.

In [1]:

import os, sys
root = os.getcwd()
while not os.path.isfile(os.path.join(root, 'docsite.json')):
    root = os.path.dirname(root)
sys.path.insert(0, os.path.join(root, 'tools'))
import numpy as np
import matplotlib.pyplot as plt
from lusine import library
from lusine.kernels._rays import ordered, rim, within
from lusine.kernels.rays.fan import fan

import os, sys root = os.getcwd() while not os.path.isfile(os.path.join(root, 'docsite.json')): root = os.path.dirname(root) sys.path.insert(0, os.path.join(root, 'tools')) import numpy as np import matplotlib.pyplot as plt from lusine import library from lusine.kernels._rays import ordered, rim, within from lusine.kernels.rays.fan import fan

The reference¶

The kernel's reference, in numpy; its Trait form is not written yet.

In [2]:

library.reference(fan)

library.reference(fan)

Out[2]:

the reference, fan.py

def fan(shape, source, reach, rays="rim"):
    """THE RAYS OF A SOURCE: the samples of the rays out from a source, each
    one's ray, its step and its cell.

    Requires: the lattice's extents (cells), the source's cell, the `Reach` r
    (cells), and which rays: `rim`, one to each cell of the reach's edge
    (what a source sends, split among them), or `within`, one to each cell
    within the reach (what a cell receives, each down its own line).
    Provides: each sample's `ray` (an integer, the ray's number in the reach's
    fixed order), its `step` (1 at the source's neighbour, growing outward)
    and its `cell` (the lattice's index it reads), only the samples inside
    the lattice: a ray stops at its first step outside it.
    Law: ray k runs from the source to the k-th offset o_k of the reach (its
    rim, or every offset within it, by row then column); its step j's cell is
    the source plus line(o_k)[j - 1], the digital line's j-th cell, each step
    one Chebyshev ring further out.
    Source: Bresenham, Algorithm for computer control of a digital plotter,
    IBM Systems Journal 4(1), 1965; Amanatides & Woo, A fast voxel traversal
    algorithm for ray tracing, Eurographics 1987.
    Proof: invariant, limit."""
    shape = tuple(int(n) for n in shape)
    if rays not in ("rim", "within"):
        raise ValueError(f"a fan's rays are `rim` or `within`, not {rays!r}")
    ends = rim(reach) if rays == "rim" else within(reach, len(shape))
    if rays == "rim" and len(shape) != 2:
        raise ValueError("a fan to the rim is drawn on a plane; in space its rays are `within`")
    ray, step, cell = [], [], []
    for k, end in enumerate(ends):
        for j, off in enumerate(line(*end), start=1):
            at = tuple(int(c) + o for c, o in zip(source, off))
            if not inside(shape, *at):
                break
            ray.append(k)
            step.append(j)
            cell.append(at)
    return (np.asarray(ray, dtype=np.int64), np.asarray(step, dtype=np.int64),
            np.asarray(cell, dtype=np.int64).reshape(-1, len(shape)))

Invariant: the rays cross near the source¶

A fan's rays do not partition the lattice: beside the source a cell lies on many rays, which is why the keys are the samples' and not the cells'. Every step is one Chebyshev ring out.

In [3]:

ray, step, cell = fan((31, 31), (15, 15), 12)
assert np.array_equal(np.max(np.abs(cell - 15), axis=1), step)
hits = np.zeros((31, 31), int)
np.add.at(hits, tuple(cell.T), 1)
assert hits[15, 16] > 1 and hits[14, 15] > 1
fig, ax = plt.subplots(figsize=(4, 4))
ax.imshow(hits, cmap='magma'); ax.set_title('samples a cell (rays to the rim, reach 12)')
plt.show()
print(len(rim(12)), 'rays; the cell beside the source on', hits[15, 16], 'of them')

ray, step, cell = fan((31, 31), (15, 15), 12) assert np.array_equal(np.max(np.abs(cell - 15), axis=1), step) hits = np.zeros((31, 31), int) np.add.at(hits, tuple(cell.T), 1) assert hits[15, 16] > 1 and hits[14, 15] > 1 fig, ax = plt.subplots(figsize=(4, 4)) ax.imshow(hits, cmap='magma'); ax.set_title('samples a cell (rays to the rim, reach 12)') plt.show() print(len(rim(12)), 'rays; the cell beside the source on', hits[15, 16], 'of them')

68 rays; the cell beside the source on 11 of them

Invariant: a ray within the reach ends at its cell; the walk is the keys'¶

With within, the rays are one to each cell within the reach, each ending on it; the walk is the same whatever the samples' storage order.

In [4]:

ray, step, cell = fan((21, 21), (10, 10), 7, rays='within')
ends = {tuple(cell[ray == q][-1] - 10) for q in np.unique(ray)}
assert ends == set(within(7))
order = ordered(ray, step)
perm = np.random.default_rng(0).permutation(len(ray))
assert np.array_equal(perm[ordered(ray[perm], step[perm])], order)
print(len(ends), 'rays, each to its own cell')

ray, step, cell = fan((21, 21), (10, 10), 7, rays='within') ends = {tuple(cell[ray == q][-1] - 10) for q in np.unique(ray)} assert ends == set(within(7)) order = ordered(ray, step) perm = np.random.default_rng(0).permutation(len(ray)) assert np.array_equal(perm[ordered(ray[perm], step[perm])], order) print(len(ends), 'rays, each to its own cell')

148 rays, each to its own cell

Limit: the lattice's edge¶

A ray stops at its first step outside the lattice, its steps 1, 2, ... to the last cell inside.

In [5]:

ray, step, cell = fan((10, 40), (2, 3), 9)
assert np.all((cell >= 0) & (cell < [10, 40]))
assert all(np.array_equal(step[ray == q], np.arange(1, (ray == q).sum() + 1)) for q in np.unique(ray))
print('every ray cut cleanly at the edge')

ray, step, cell = fan((10, 40), (2, 3), 9) assert np.all((cell >= 0) & (cell < [10, 40])) assert all(np.array_equal(step[ray == q], np.arange(1, (ray == q).sum() + 1)) for q in np.unique(ray)) print('every ray cut cleanly at the edge')

every ray cut cleanly at the edge