Struct PixelMap

pub struct PixelMap<T: Copy + PartialEq = bool, U: Unsigned + NumCast + Copy + Debug = u16> { /* private fields */ }

A two-dimensional map of pixels implemented by an MX quadtree. The coordinate origin is at the bottom left.

Type Parameters

• T: The type of pixel data. By default, a bool, to denote the pixel is on or off. A more useful type could be a Color.
• U: The unsigned integer type of the coordinates used to index the pixels, typically u16 (default), or u32.

Implementations

impl<T: Copy + PartialEq, U: Unsigned + NumCast + Copy + Debug> PixelMap<T, U>

pub fn visit_all_neighbors<F, V>( &self, rect: &URect, node_region: &URect, predicate: F, visitor: V, )

where F: FnMut(&PNode<T, U>, &URect) -> bool, V: FnMut(&PNode<T, U>, &URect),

pub fn visit_diagonal_neighbors<F, V>( &self, rect: &URect, node_region: &URect, predicate: F, visitor: V, )

where F: FnMut(&PNode<T, U>, &URect) -> bool, V: FnMut(&PNode<T, U>, &URect),

pub fn visit_cardinal_neighbors<F, V>( &self, rect: &URect, node_region: &URect, predicate: F, visitor: V, )

where F: FnMut(&PNode<T, U>, &URect) -> bool, V: FnMut(&PNode<T, U>, &URect),

pub fn visit_neighbors<F, V>( &self, rect: &URect, node_region: &URect, direction: Direction, predicate: F, visitor: V, )

where F: FnMut(&PNode<T, U>, &URect) -> bool, V: FnMut(&PNode<T, U>, &URect),

Visit neighboring nodes to the given node, on the specified edge or corner.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• node_region: The region represented by the node for which to visit neighbors.
• direction: The direction of the edge of the node for which to visit neighbors. When the given direction is one of the diagonal variants, the single respective corner node is visited.
• predicate: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method. It returns true if the node matches the predicate, or false otherwise.
• visitor: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. The node reference is a neighbor of the node passed to this method, on the edge of the given direction, that has been accepted by the given predicate callback. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method.

pub fn visit_neighbor_pairs<F>(&self, rect: &URect, visitor: &mut F)

where F: FnMut(NeighborOrientation, &PNode<T, U>, &URect, &PNode<T, U>, &URect),

Visit all leaf nodes that intersect with the given rect that are neighbors. The visitor closure is called once for each unique pair of neighbor nodes.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• visitor: A closure that takes:
  • A NeighborOrientation that indicates the orientation of the neighboring nodes.
  • The left or bottom node, depending on the orientation.
  • The rectangle that is the effective intersection of the left or bottom node’s region and the rect parameter supplied to this method.
  • The right or top node, depending on the orientation.
  • The rectangle that is the effective intersection of the right or top node’s region and the rect parameter supplied to this method.

impl<T: Copy + PartialEq, U: Unsigned + NumCast + Copy + Debug> PixelMap<T, U>

pub fn pathfind_a_star_grid<H, F>( &self, bounds: &URect, cell_size: u32, start: UVec2, goal: UVec2, heuristic: H, predicate: F, ) -> Option<PathfindAStarGridResult>

where H: Fn(&UVec2, &UVec2) -> u32, F: FnMut(&PNode<T, U>, &URect) -> bool,

Find the shortest path from the start point to the goal point, using the A* algorithm to traverse a grid of cells over this quadtree. The grid, for which square cell size is defined by cell_size, is aligned with the (0,0) point (bottom-left of the quadtree) regardless of the given bounds. A path is determined by examining cells, and a cell is considered navigable when all nodes that compose the cell pass the given predicate. Apart from the start and goal points, resulting path points are positioned at the center of navigable cells.

Parameters

• bounds: The rectangle in which contained or overlapping cells will be considered.
• cell_size: The size of an edge, in pixels, of a single square cell in the grid to navigate. A lower value will produce better path precision, but will take longer to compute being that there will be more potential paths to consider. This value also contributes to the effective spacing from walls that a resulting path will take. For example, a cell_size of 50 would produce a path that is roughly 25 pixels away from walls, minimum. Also consider that a gap between walls must be at least this size in order to path through it. And, being that the grid is fixed to the zero point a gap that is actually wider than the cell_size may still deny a path if the gap straddles a border between two cells, where the predicate rejects both of those cells due to overlap with either wall. So, generally, at least 2x the cell_size is what can safely be considered the minimum allowable gap between walls that a path can take.
• start: The origin point of the potential path.
• goal: The destination point of the potential path.
• heuristic: The A* algorithm heuristic function. A general-purpose euclidean_heuristic is provided. But, a heuristic tuned specifically for your use case can produce significant performance improvements.
• predicate: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the bounds parameter supplied to this method. It returns true if the node matches the predicate, or false otherwise. The predicate function is consulted for every node the composes a cell (with short-circuit), and cell is considered to be navigable only if all nodes produce a true result.

Returns

`None is returned under the following conditions:

• The bounds does not intersect with this quadtree’s PixelMap::map_rect.
• The start or goal points do not fall within the intersection of the bounds rectangle and this quadtree’s PixelMap::map_rect.
• The nodes representing the start or goal points do not pass the predicate.
• A navigable path is not possible.

Otherwise, Some of a PathfindAStarGridResult is returned.

impl<T: Copy + PartialEq, U: Unsigned + NumCast + Copy + Debug> PixelMap<T, U>

pub fn new(dimensions: &UVec2, value: T, pixel_size: u8) -> Self

Create a new PixelMap.

Parameters

• dimensions: The size of this PixelMap.
• value: The initial value of all pixels in this PixelMap.
• pixel_size: The pixel size of this PixelMap that is considered the smallest divisible unit. Must be a power of two.

Panics

If dimensions size is not a multiple of pixel size on each axis. If pixel_size is not a power of two.

pub fn map_size(&self) -> UVec2

Obtain the dimensions of this PixelMap.

pub fn map_rect(&self) -> URect

Obtain the dimensions of this PixelMap as a rectangle.

pub fn pixel_size(&self) -> u8

Obtain the pixel size of this PixelMap. When a node’s region is of this size, it cannot be subdivided further.

pub fn region(&self) -> &Region<U>

Obtain the region that this PixelMap’s quadtree root node covers. This value differs from map_size in that it the nearest power of two larger than the map size, and it is square.

pub fn clear(&mut self, value: T)

Discard any existing pixel data and set the root node’s value to that provided.

Parameters

• value: The value to assign to the root node.

pub fn empty(&self) -> bool

Determine if this PixelMap is empty, which means that it has no pixel data.

pub fn contains(&self, point: UVec2) -> bool

Determine if the given point is within the PixelMap::map_size bounds.

pub fn get_pixel<P>(&self, point: P) -> Option<&T>

where P: Into<UVec2>,

Get the value of the pixel at the given coordinates. If the coordinates are outside the region covered by this PixelMap, None is returned.

Parameters

• point: The coordinates of the pixel for which to retrieve the associated value.

pub fn find_node<P>(&self, point: P) -> Option<&PNode<T, U>>

where P: Into<UVec2>,

Get the node that represents the pixel at the given coordinates. If the coordinates are outside the region covered by this PixelMap, None is returned.

Parameters

• point: The coordinates of the pixel for which to retrieve the representing node.

pub fn get_path<P>(&self, point: P) -> Option<NodePath>

where P: Into<UVec2>,

Get the path to the node that stores the pixel at the given point.

Parameters

• point: The coordinates of the pixel for which to retrieve the node path.

Returns

If the coordinates are outside the region covered by this PixelMap, None is returned.

pub fn set_pixel<P>(&mut self, point: P, value: T) -> bool

where P: Into<UVec2>,

Set the value of the pixel at the given coordinates.

Parameters

• point: The coordinates of the pixel for which to set the associated value.

Returns

If the coordinates are outside the PixelMap::map_rect, false is returned. Otherwise, true is returned.

pub fn set_pixels<I>(&mut self, points: I, value: T) -> bool

where I: Iterator<Item = UVec2>,

Set the value of all pixel coordinates yielded by the given iterator.

Parameters

• points: An iterator that yields pixel coordinates.

Returns

If any of the coordinates are inside the PixelMap::map_rect, true is returned, false otherwise.

pub fn draw_rect(&mut self, rect: &URect, value: T) -> bool

Set the value of the pixels within the given rectangle.

Parameters

• rect: The rectangle in which pixels will be set to associated value.
• value: The value to assign to the pixels within the given rectangle.

Returns

If the rectangle overlaps the PixelMap::map_rect, true is returned. Otherwise, false is returned.

pub fn draw_rotated_rect(&mut self, rrect: &RotatedIRect, value: T) -> bool

Set the value of the pixels within the given rotated rectangle.

Parameters

• rrect: The rotated rectangle in which pixels will be set to associated value.
• value: The value to assign to the pixels within the given rectangle.

Returns

If the rectangle overlaps the PixelMap::map_rect, true is returned. Otherwise, false is returned.

pub fn draw_circle(&mut self, circle: &ICircle, value: T) -> bool

Set the value of the pixels within the given circle.

Parameters

• circle: The circle in which pixels will be set to associated value.
• value: The value to assign to the pixels within the given circle.

Returns

If the circle’s aabb does not overlap the region covered by this PixelMap, false is returned. Otherwise, true is returned.

pub fn visit<F>(&self, visitor: F) -> u32

where F: FnMut(&PNode<T, U>, &URect),

Visit all leaf nodes in this PixelMap in pre-order.

Parameters

• visitor: A closure that takes a reference to a leaf node as its only parameter.

Returns

The number of nodes traversed.

pub fn visit_in_rect<F>(&self, rect: &URect, visitor: F) -> u32

where F: FnMut(&PNode<T, U>, &URect),

Visit all leaf nodes in this PixelMap that overlap with the given rectangle.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• visitor: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method.

Returns

The number of nodes traversed.

pub fn visit_nodes_in_rect<F>(&self, rect: &URect, visitor: F) -> u32

where F: FnMut(&PNode<T, U>, &URect) -> CellFill,

Visit all nodes in this PixelMap that overlap with the given rectangle, controlling navigation with the visitor return value.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• visitor: A closure that takes a reference to a node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method. It returns a CellFill that denotes which child nodes should be visited.

Returns

The number of nodes traversed.

pub fn any_in_rect<F>(&self, rect: &URect, f: F) -> Option<bool>

where F: FnMut(&PNode<T, U>, &URect) -> bool,

Determine if any of the leaf nodes within the bounds of the given rectangle match the predicate. Node visitation short-circuits upon the first match.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• f: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method. It returns true if the node matches the predicate, or false otherwise.

Returns

Some(true) if any of the leaf nodes within the bounds of rect match the predicate. Or Some(false) if no nodes within rect match the predicate. None if rect does not overlap the region covered by this PixelMap.

pub fn all_in_rect<F>(&self, rect: &URect, f: F) -> Option<bool>

where F: FnMut(&PNode<T, U>, &URect) -> bool,

Determine if all the leaf nodes within the bounds of the given rectangle match the predicate. Node visitation short-circuits upon the first match.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• f: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method. It returns true if the node matches the predicate, or false otherwise.

Returns

Some(true) if all of the leaf nodes within the bounds of rect match the predicate. Or Some(false) if none or some of the nodes within rect match the predicate. None if rect does not overlap the region covered by this PixelMap.

pub fn visit_dirty<F>(&self, visitor: F) -> u32

where F: FnMut(&PNode<T, U>, &URect),

Visit all leaf nodes in this PixelMap that are marked as dirty. This is useful for examining only leaf nodes that have changed (became dirty), and to limit time spent traversing the quadtree. Dirty status is not changed.

Parameters

• visitor: A closure that takes a reference to a leaf node as its only parameter.

Returns

The number of nodes traversed.

pub fn visit_dirty_in_rect<F>(&self, rect: &URect, visitor: F) -> u32

where F: FnMut(&PNode<T, U>, &URect),

Visit dirty leaf nodes in this PixelMap that overlap with the given rectangle. This is useful for examining only leaf nodes that have changed (became dirty), and to limit time spent traversing the quadtree. Dirty status is not changed.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• visitor: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method.

Returns

The number of nodes traversed.

pub fn dirty(&self) -> bool

Determine if the root node is marked as dirty, which indicates that at least one leaf node has changed (became dirty).

pub fn drain_dirty<F>(&mut self, visitor: F) -> usize

where F: FnMut(&PNode<T, U>),

Visit all leaf nodes in this PixelMap that are marked as dirty, and consume their dirty status (by modifying their dirty state to be false). This is useful for operating only on leaf nodes that have changed (became dirty), and to limit time spent traversing the quadtree.

Parameters

• visitor: A closure that takes a reference to a leaf node as its only parameter.

Returns

The number of nodes traversed.

pub fn clear_dirty(&mut self, deep: bool)

Clear the dirty status of the root of this PixelMap, according to a shallow or deep strategy.

Shallow Clear

If dirty state is cleared in a shallow manner, the root node is marked clean, and the dirty state at any further depth is retained. Subsequent calls to other methods that navigate dirty nodes will not traverse any nodes, as none that are dirty are reachable (because the root node is no longer dirty). But, if branch A was dirty, Self::clear_dirty is called, and then branch B becomes dirty, both A and B will be traversed by Self::visit_dirty() or Self::drain_dirty().

Deep Clear

A deep clear traverses all dirty nodes and marks them as clean.

Parameters

• deep: If true, clear the dirty status of all nodes in this PixelMap, otherwise clear the dirty status of just the root node.

pub fn points<F>( &self, rect: &URect, offset: IVec2, predicate: F, ) -> HashSet<IVec2, BuildHasherDefault<FxHasher>>

where F: FnMut(&PNode<T, U>, &URect) -> bool,

Obtain the points of node region corners that overlap with the given rectangle, and match the given predicate. Calls #Self::collect_points internally, but takes a guess at a reasonable capacity for the resulting HashSet.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• offset: An offset to apply to returned points.
• predicate: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method. It returns true if the node matches the predicate, or false otherwise.

pub fn collect_points<F, H>( &self, rect: &URect, offset: IVec2, predicate: F, hash: &mut HashSet<IVec2, H>, )

where F: FnMut(&PNode<T, U>, &URect) -> bool, H: BuildHasher,

Collect the points of node region corners that overlap with the given rectangle, and match the given predicate.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• offset: An offset to apply to returned points.
• predicate: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method. It returns true if the node matches the predicate, or false otherwise.
• hash: A HashSet into which matching points will be inserted.

pub fn ray_cast<F>( &self, query: RayCastQuery, collision_check: F, ) -> RayCastResult

where F: FnMut(&PNode<T, U>) -> RayCast,

Visit all leaf nodes in this PixelMap for which the region overlaps with the line defined by the RayCastQuery.

Parameters

• query: A RayCastQuery that defines the line to cast.
• collision_check: A closure that takes a reference to a leaf node as its only parameter. It returns a RayCast value that determines if the node represents a collision or if the ray should continue.

Returns

A RayCastResult that contains the collision result and related information.

pub fn stats(&self) -> Stats

Collect statistics by traversing the PixelMap quadtree.

Returns

A Stats struct that contains information about PixelMap’s current state.

pub fn combine<P, F>(&mut self, other: &Self, offset: P, combiner: F)

where P: Into<UVec2>, F: Fn(&T, &T) -> T,

Combine another PixelMap with this one using a closure that decides how to combine the values of each pixel. This PixelMap’s region should overlap with the other PixelMap’s region, otherwise this operation has no effect.

Parameters

• other: The other PixelMap to combine with this one.
• offset: The other PixelMap is sampled according to this offset vector.
• combiner: A closure that takes two values and returns a resulting value.

Examples

This method can be used to implement boolean operations, such as union, intersection, disjunction, etc., according to the combiner function’s implementation.

To compute the union of two PixelMaps:

use pixel_map::{PixelMap, Region};
// Union (OR)
pixel_map.combine(&other, (0, 0), |c1, c2| {
    if c1 == &Color::BLACK || c2 == &Color::BLACK {
        Color::BLACK
    } else {
        Color::WHITE
    }
});

Compute an intersection of two PixelMaps:

use pixel_map::{PixelMap, Region};
// Intersection (AND)
pixel_map.combine(&other, (0, 0), |c1, c2| {
   if c1 == &Color::BLACK && c2 == &Color::BLACK {
      Color::BLACK
  } else {
     Color::WHITE
 }
});

pub fn non_uniform_quad_mesh<F>( &self, rect: &URect, predicate: F, size_estimate: usize, ) -> (Vec<UVec2>, Vec<[u32; 3]>)

where F: FnMut(&PNode<T, U>, &URect) -> bool,

Generate a quad mesh that contains a triangulated quad for each leaf node accepted by the predicate function. The returned quad mesh is non-uniform in that neighboring quads having differing sizes, according to the layout of the quadtree, will not be fully connected via triangulation.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• predicate: A closure that takes a reference to a leaf node, and a reference to a rectangle as parameters. This rectangle represents the intersection of the node’s region and the rect parameter supplied to this method. It returns true if the node matches the predicate, or false otherwise.
• size_estimate: An estimated (or known) capacity of each returned vec.

Returns

A tuple having a vec of unique vertex points, and a vec of triangle indices. Each element in the index vec is a slice of each index in a triangle, in counter-clockwise winding.

pub fn contour<F>(&self, rect: &URect, predicate: F) -> Vec<IsoLine>

where F: FnMut(&PNode<T, U>, &URect) -> bool,

Obtain a list of line segments that contour the shapes determined by the given predicate closure. In other words, if the predicate returns true, the node is considered to be part of the shape for which a contour is being generated.

Note: This implementation is likely to change in the future which may affect the characteristics of the returned data.

Parameters

• rect: The rectangle in which contained or overlapping nodes will be visited.
• predicate: A closure that takes a reference to a leaf node, and a reference to the rectangle that is the effective intersection of the node’s region and the rect parameter supplied to this method.

Returns

A list of line segments that contour the shapes determined by the given predicate closure. The number of segments returned are the minimum possible, in that one segment does not share continuity with any other segment.

Trait Implementations

impl<T: Clone + Copy + PartialEq, U: Clone + Unsigned + NumCast + Copy + Debug> Clone for PixelMap<T, U>

fn clone(&self) -> PixelMap<T, U>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Copy + PartialEq, U: Unsigned + NumCast + Copy + Debug> Debug for PixelMap<T, U>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: PartialEq + Copy + PartialEq, U: PartialEq + Unsigned + NumCast + Copy + Debug> PartialEq for PixelMap<T, U>

fn eq(&self, other: &PixelMap<T, U>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Copy + PartialEq, U: Unsigned + NumCast + Copy + Debug> StructuralPartialEq for PixelMap<T, U>