spatial

package
v0.12.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 10, 2023 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package spatial provides data structures and algorithms for working with spatial objects and sub-spaces.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type DynamicOctree added in v0.11.0 

type DynamicOctree[T any] struct {
	// contains filtered or unexported fields
}

DynamicOctree is a spatial structure that uses a loose octree implementation with biased placement to enable the fast search of items within a region.

func NewDynamicOctree added in v0.11.0 

func NewDynamicOctree[T any](settings DynamicOctreeSettings) *DynamicOctree[T]

NewDynamicOctree creates a new DynamicOctree using the provided settings.

func (*DynamicOctree[T]) Insert added in v0.11.0 

func (t *DynamicOctree[T]) Insert(position dprec.Vec3, radius float64, value T) DynamicOctreeItemID

Insert adds an item to this octree at the specified position and taking the specified radius into account.

func (*DynamicOctree[T]) Remove added in v0.11.0 

func (t *DynamicOctree[T]) Remove(id DynamicOctreeItemID)

Remove removes the item with the specified id from this data structure.

func (*DynamicOctree[T]) Stats added in v0.11.0 

func (t *DynamicOctree[T]) Stats() DynamicOctreeStats

Stats returns statistics on the current state of this octree.

func (*DynamicOctree[T]) Update added in v0.11.0 

func (t *DynamicOctree[T]) Update(id DynamicOctreeItemID, position dprec.Vec3, radius float64)

Update repositions the item with the specified id to the new position and radius.

func (*DynamicOctree[T]) VisitHexahedronRegion added in v0.11.0 

func (t *DynamicOctree[T]) VisitHexahedronRegion(region *HexahedronRegion, visitor Visitor[T])

VisitHexahedronRegion finds all items that are inside or intersect the specified hexahedron region. It calls the specified visitor for each item found.

func (*DynamicOctree[T]) VisitStats added in v0.11.0 

func (t *DynamicOctree[T]) VisitStats() DynamicOctreeVisitStats

VisitStats returns statistics information on the last executed search in this octree.

type DynamicOctreeItemID added in v0.11.0 

type DynamicOctreeItemID uint32

DynamicOctreeItemID is an identifier used to control the placement of an item into a dynamic octree.

type DynamicOctreeSettings added in v0.11.0 

type DynamicOctreeSettings struct {

	// Size specifies the dimension of the octree cube. If not specified,
	// then a default size of 4096 will be used. Inserting an item outside
	// these bounds will be suboptimal (placed in root node).
	Size opt.T[float64]

	// MaxDepth controls the maximum depth that the octree could reach. If not
	// specified, then a default max depth of 8 will be used.
	MaxDepth opt.T[int32]

	// BiasRatio is multiplied to the item radius in order to force items to
	// be placed upper in the octree hierarchy. This can lead to better
	// performance in certain cases, as it can prevent double visibility check
	// on both the item and the (tightly fit) node that contains it.
	//
	// The value must not be smaller than 1.0 and is 2.0 by default.
	BiasRatio opt.T[float64]

	// InitialNodeCapacity is a hint as to the number of nodes that will be
	// needed to place all items. Usually one would find that number empirically.
	// This allows the octree to preallocate memory and avoid dynamic allocations.
	//
	// By default the initial capacity is 4096.
	InitialNodeCapacity opt.T[int32]

	// InitialItemCapacity is a hint as to the likely upper bound of items that
	// will be inserted into the octree. This allows the octree to preallocate
	// memory and avoid dynamic allocations during insertion.
	//
	// By default the initial capacity is 1024.
	InitialItemCapacity opt.T[int32]
}

DynamicOctreeSettings contains the settings for a DynamicOctree.

type DynamicOctreeStats added in v0.11.0 

type DynamicOctreeStats struct {
	NodeCount          int32
	ItemCount          int32
	ItemsCountPerDepth []int32
}

DynamicOctreeStats represents the current state of a DynamicOctree.

type DynamicOctreeVisitStats added in v0.11.0 

type DynamicOctreeVisitStats struct {
	NodeCount         int32
	NodeCountVisited  int32
	NodeCountAccepted int32
	NodeCountRejected int32
	ItemCount         int32
	ItemCountVisited  int32
	ItemCountAccepted int32
	ItemCountRejected int32
}

DynamicOctreeVisitStats represents statistics on the last visit operation performed on a DynamicOctree.

type DynamicSet added in v0.11.0 

type DynamicSet[T any] struct {
	// contains filtered or unexported fields
}

DynamicSet is a spatial structure that uses brute force to figure out which items are visible during a Visit.

It allows only the insertion of static items. Such items cannot be resized, repositioned, or removed from the set.

func NewDynamicSet added in v0.11.0 

func NewDynamicSet[T any](settings DynamicSetSettings) *DynamicSet[T]

NewDynamicSet creates a new DynamicSet using the provided settings.

func (*DynamicSet[T]) Insert added in v0.11.0 

func (t *DynamicSet[T]) Insert(position dprec.Vec3, radius float64, item T) DynamicSetItemID

Insert adds an item to this set.

func (*DynamicSet[T]) Remove added in v0.11.0 

func (t *DynamicSet[T]) Remove(id DynamicSetItemID)

Remove removes the item with the specified it from this data structure.

func (*DynamicSet[T]) Update added in v0.11.0 

func (t *DynamicSet[T]) Update(id DynamicSetItemID, position dprec.Vec3, radius float64)

Update repositions the item with the specified id to the new position and radius.

func (*DynamicSet[T]) VisitHexahedronRegion added in v0.11.0 

func (t *DynamicSet[T]) VisitHexahedronRegion(region *HexahedronRegion, visitor Visitor[T])

VisitHexahedronRegion finds all items that are inside or intersect the specified hexahedron region. It calls the specified visitor for each item found.

type DynamicSetItemID added in v0.11.0 

type DynamicSetItemID uint32

DynamicSetItemID is an identifier used to control the placement of an item into a dynamic set.

type DynamicSetSettings added in v0.11.0 

type DynamicSetSettings struct {

	// InitialItemCapacity is a hint as to the likely upper bound of items that
	// will be inserted into the set. This allows the set to preallocate
	// memory and avoid dynamic allocations during insertion.
	//
	// By default the initial capacity is 1024.
	InitialItemCapacity opt.T[int32]
}

DynamicSetSettings contains the settings for a DynamicSet.

type HexahedronRegion 

type HexahedronRegion [6]Plane

HexahedronRegion represents a region in space that is defined by six clipping planes pointing inwards. It is possible to use the HexahedronRegion to define a region through fewer planes by repeating one of the plane definitions one or more times.

func CuboidRegion 

func CuboidRegion(position, size dprec.Vec3) HexahedronRegion

CuboidRegion creates a new HexahedronRegion that represents a Cuboid shape using the specified position and size.

func ProjectionRegion 

func ProjectionRegion(matrix dprec.Mat4) HexahedronRegion

ProjectionRegion creates a new HexahedronRegion using the specified projection matrix. The provided matrix could be a transformed projection matrix (e.g. projection * view).

type PairVisitor added in v0.11.0 

type PairVisitor[T any] interface {
	// Visit is called for each observed pair of items.
	Visit(first, second T)
}

PairVisitor represents a callback mechanism to pass pairs of items back to the client.

type PairVisitorBucket added in v0.11.0 

type PairVisitorBucket[T any] struct {
	// contains filtered or unexported fields
}

PairVisitorBucket is an implementation of PairVisitor that stores observed item pairs into a buffer for faster and more cache-friendly iteration afterwards.

func NewPairVisitorBucket added in v0.11.0 

func NewPairVisitorBucket[T any](initCapacity int) *PairVisitorBucket[T]

NewPairVisitorBucket creates a new PairVisitorBucket instance with the specified initial capacity, which is only used to preallocate memory. It is allowed to exceed the initial capacity.

func (*PairVisitorBucket[T]) Each added in v0.11.0 

func (r *PairVisitorBucket[T]) Each(cb func(first, second T))

Each calls the provided closure function for each item pair in the buffer.

func (*PairVisitorBucket[T]) Reset added in v0.11.0 

func (r *PairVisitorBucket[T]) Reset()

Reset rewinds the item buffer.

func (*PairVisitorBucket[T]) Visit added in v0.11.0 

func (r *PairVisitorBucket[T]) Visit(first, second T)

Visit records the passed item pair into the buffer.

type PairVisitorFunc added in v0.11.0 

type PairVisitorFunc[T any] func(first, second T)

PairVisitorFunc is an implementation of PairVisitor that passes each observed pair of items to the wrapped function.

func (PairVisitorFunc[T]) Visit added in v0.11.0 

func (f PairVisitorFunc[T]) Visit(first, second T)

Visit calls the wrapped function.

type Plane 

type Plane dprec.Vec4

Plane represents a plane that can be used to split a 3D space into two sub-spaces. It is represented through the mathematical formula 

a*x + b*y + c*z + d = 0

A point (x, y, z) that produces zero in the left part of the equation is considered to lay on the plane. A positive value indicates that the point is inside the sub-region defined by the plane. A negative value indicates that the point is outside the sub-region.

func (Plane) ContainsPoint 

func (p Plane) ContainsPoint(position dprec.Vec3) bool

ContainsPoint checks whether a point with the specified position is inside the sub-region of this Plane or at least partailly inside.

The Plane need not be normalized.

func (Plane) ContainsSphere 

func (p Plane) ContainsSphere(position dprec.Vec3, radius float64) bool

ContainsSphere checks whether a sphere with the specified position and radius is inside the sub-region of this Plane or at least partailly inside.

For this method to work, the Plane must be normalized.

func (Plane) Normalized 

func (p Plane) Normalized() Plane

Normalized returns a normalized Plane, which is a plane that has a normal component (a, b, c) that is of unit length.

Normalized clipping planes produce correct distances to the plane when multiplied (dot product) by a 4D positional vector.

type SphericalRegion 

type SphericalRegion struct {
	Position dprec.Vec3
	Radius   float64
}

SphericalRegion represents a region in space that is defined by a position and a radius around that position.

type StaticOctree added in v0.11.0 

type StaticOctree[T any] struct {
	// contains filtered or unexported fields
}

StaticOctree represents an octree spatial structure that only allows the insertion of static items. Such items cannot be resized, repositioned, or removed from the tree.

func NewStaticOctree added in v0.11.0 

func NewStaticOctree[T any](settings StaticOctreeSettings) *StaticOctree[T]

NewStaticOctree creates a new StaticOctree using the provided settings.

func (*StaticOctree[T]) Insert added in v0.11.0 

func (t *StaticOctree[T]) Insert(position dprec.Vec3, radius float64, item T)

Insert adds an item to this octree at the specified position and taking the specified radius into account.

func (*StaticOctree[T]) Stats added in v0.11.0 

func (t *StaticOctree[T]) Stats() StaticOctreeStats

Stats returns statistics on the current state of this octree.

func (*StaticOctree[T]) VisitHexahedronRegion added in v0.11.0 

func (t *StaticOctree[T]) VisitHexahedronRegion(region *HexahedronRegion, visitor Visitor[T])

VisitHexahedronRegion finds all items that are inside or intersect the specified hexahedron region. It calls the specified visitor for each item found.

func (*StaticOctree[T]) VisitStats added in v0.11.0 

func (t *StaticOctree[T]) VisitStats() StaticOctreeVisitStats

VisitStats returns statistics information on the last executed search in this octree.

type StaticOctreeSettings added in v0.11.0 

type StaticOctreeSettings struct {

	// Size specifies the dimension of the octree cube. If not specified,
	// then a default size of 4096 will be used. Inserting an item outside
	// these bounds will be suboptimal (placed in root node).
	Size opt.T[float64]

	// MaxDepth controls the maximum depth that the octree could reach. If not
	// specified, then a default max depth of 8 will be used.
	MaxDepth opt.T[int32]

	// BiasRatio is multiplied to the item radius in order to force items to
	// be placed upper in the octree hierarchy. This can lead to better
	// performance in certain cases, as it can prevent double visibility check
	// on both the item and the (tightly fit) node that contains it.
	//
	// The value must not be smaller than 1.0 and is 2.0 by default.
	BiasRatio opt.T[float64]

	// InitialNodeCapacity is a hint as to the number of nodes that will be
	// needed to place all items. Usually one would find that number empirically.
	// This allows the octree to preallocate memory and avoid dynamic allocations.
	//
	// By default the initial capacity is 4096.
	InitialNodeCapacity opt.T[int32]

	// InitialItemCapacity is a hint as to the likely upper bound of items that
	// will be inserted into the octree. This allows the octree to preallocate
	// memory and avoid dynamic allocations during insertion.
	//
	// By default the initial capacity is 1024.
	InitialItemCapacity opt.T[int32]
}

StaticOctreeSettings contains the settings for a StaticOctree.

type StaticOctreeStats added in v0.11.0 

type StaticOctreeStats struct {
	NodeCount          int32
	ItemCount          int32
	ItemsCountPerDepth []int32
}

StaticOctreeStats represents the current state of a StaticOctree.

type StaticOctreeVisitStats added in v0.11.0 

type StaticOctreeVisitStats struct {
	NodeCount         int32
	NodeCountVisited  int32
	NodeCountAccepted int32
	NodeCountRejected int32
	ItemCount         int32
	ItemCountVisited  int32
	ItemCountAccepted int32
	ItemCountRejected int32
}

StaticOctreeVisitStats represents statistics on the last visit operation performed on a StaticOctree.

type StaticSet added in v0.11.0 

type StaticSet[T any] struct {
	// contains filtered or unexported fields
}

StaticSet is a spatial structure that uses brute force to figure out which items are visible during a Visit.

It allows only the insertion of static items. Such items cannot be resized, repositioned, or removed from the set.

func NewStaticSet added in v0.11.0 

func NewStaticSet[T any](settings StaticSetSettings) *StaticSet[T]

NewStaticSet creates a new StaticSet using the provided settings.

func (*StaticSet[T]) Insert added in v0.11.0 

func (t *StaticSet[T]) Insert(position dprec.Vec3, radius float64, item T)

Insert adds an item to this set.

func (*StaticSet[T]) VisitHexahedronRegion added in v0.11.0 

func (t *StaticSet[T]) VisitHexahedronRegion(region *HexahedronRegion, visitor Visitor[T])

VisitHexahedronRegion finds all items that are inside or intersect the specified hexahedron region. It calls the specified visitor for each item found.

type StaticSetSettings added in v0.11.0 

type StaticSetSettings struct {

	// InitialItemCapacity is a hint as to the likely upper bound of items that
	// will be inserted into the set. This allows the set to preallocate
	// memory and avoid dynamic allocations during insertion.
	//
	// By default the initial capacity is 1024.
	InitialItemCapacity opt.T[int32]
}

StaticSetSettings contains the settings for a StaticSet.

type SweepPruneItemID added in v0.11.0 

type SweepPruneItemID uint32

SweepPruneItemID is an identifier used to control the placement of an item into the sweep and prune set.

type SweepPruneSet added in v0.11.0 

type SweepPruneSet[T any] struct {
	// contains filtered or unexported fields
}

SweepPruneSet is a spatial data structure that uses the sweep and prune algorithm to determine potentially intersecting item pairs.

func NewSweepPruneSet added in v0.11.0 

func NewSweepPruneSet[T any](settings SweepPruneSetSettings) *SweepPruneSet[T]

NewSweepPruneSet creates a new SweepPruneSet using the provided settings.

func (*SweepPruneSet[T]) Insert added in v0.11.0 

func (s *SweepPruneSet[T]) Insert(position dprec.Vec3, radius float64, value T) SweepPruneItemID

Insert adds an item to this set.

func (*SweepPruneSet[T]) Remove added in v0.11.0 

func (s *SweepPruneSet[T]) Remove(id SweepPruneItemID)

Remove removes the item with the specified id from this data structure.

func (*SweepPruneSet[T]) Update added in v0.11.0 

func (s *SweepPruneSet[T]) Update(id SweepPruneItemID, position dprec.Vec3, radius float64)

Update repositions the item with the specified id to the new position and radius.

func (*SweepPruneSet[T]) VisitOverlapping added in v0.11.0 

func (s *SweepPruneSet[T]) VisitOverlapping(visitor PairVisitor[T])

VisitOverlapping finds all potentially intersecting item pairs in this set. It calls the specified visitor for each pair found.

type SweepPruneSetSettings added in v0.11.0 

type SweepPruneSetSettings struct {

	// InitialItemCapacity is a hint as to the likely upper bound of items that
	// will be inserted into the set. This allows the set to preallocate
	// memory and avoid dynamic allocations during insertion.
	//
	// By default the initial capacity is 1024.
	InitialItemCapacity opt.T[int32]
}

SweepPruneSetSettings contains the settings for a SweepPruneSet.

type Visitor 

type Visitor[T any] interface {
	// Visit is called for each observed item.
	Visit(item T)
}

Visitor represents a callback mechanism to pass items back to the client.

type VisitorBucket 

type VisitorBucket[T any] struct {
	// contains filtered or unexported fields
}

VisitorBucket is an implementation of Visitor that stores observed items into a buffer for faster and more cache-friendly iteration afterwards.

func NewVisitorBucket 

func NewVisitorBucket[T any](initCapacity int) *VisitorBucket[T]

NewVisitorBucket creates a new VisitorBucket instance with the specified initial capacity, which is only used to preallocate memory. It is allowed to exceed the initial capacity.

func (*VisitorBucket[T]) Each 

func (r *VisitorBucket[T]) Each(cb func(item T))

Each calls the provided closure function for each item in the buffer.

func (*VisitorBucket[T]) Items 

func (r *VisitorBucket[T]) Items() []T

Items returns the items stored in the buffer. The returned slice is valid only until the Reset function is called.

func (*VisitorBucket[T]) Reset 

func (r *VisitorBucket[T]) Reset()

Reset rewinds the item buffer.

func (*VisitorBucket[T]) Visit 

func (r *VisitorBucket[T]) Visit(item T)

Visit records the passed item into the buffer.

type VisitorFunc 

type VisitorFunc[T any] func(item T)

VisitorFunc is an implementation of Visitor that passes each observed item to the wrapped function.

func (VisitorFunc[T]) Visit 

func (f VisitorFunc[T]) Visit(item T)

Visit calls the wrapped function.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.