README
¶
dyntree
A Dynamic BVH (Bounding Volume Hierarchy) using incremental refit and tree-rotations
This is a Go port of https://github.com/jeske/SimpleScene/tree/master/SimpleScene/Util/ssBVH
Warning
This is a very WIP translation of the C# implementation. There are likely bugs, and certainy not enough testing coverage to catch them. Any and all pull requests are appreciated as I move to make this library more stable.
Areas of focus
- Thread-Safe access (hopefully parallel eventually)
- Experimenting with allocationless strategies
- Better test coverage
Images
Benchmark Results
Graphical representation of a tree (red=boundary,green=entity):
Documentation
¶
Index ¶
- Constants
- func EntitiesSurfaceArea(ea []Entity, start, ct int) float64
- type Axis
- type BoundingBox
- type CustomDrawer
- type Entity
- type HitTest
- type Node
- func (n *Node) AssignVolume(pos Vec3, radius float64)
- func (n *Node) CompareDepth(n2 *Node) int
- func (n *Node) Equals(n2 *Node) bool
- func (n *Node) ExpandParentVolume(child *Node)
- func (n *Node) ExpandVolume(pos Vec3, radius float64)
- func (n *Node) GetSibling() *Node
- func (n *Node) HasParent() bool
- func (n *Node) IsLeaf() bool
- func (n *Node) IsValid() bool
- func (n *Node) IsValidBranch() bool
- func (n *Node) IsValidBranchNode() bool
- func (n *Node) IsValidLeafNode() bool
- type NodeSide
- type NodeState
- type Rot
- type RotOpt
- type SplitAxisOpt
- func (s *SplitAxisOpt) LeftEndIndex() int
- func (s *SplitAxisOpt) LeftItemCount() int
- func (s *SplitAxisOpt) LeftStartIndex() int
- func (s *SplitAxisOpt) RightEndIndex() int
- func (s *SplitAxisOpt) RightItemCount() int
- func (s *SplitAxisOpt) RightStartIndex() int
- func (s *SplitAxisOpt) TryImproveAxis(a Axis)
- type Tree
- func (t *Tree) Add(e Entity)
- func (t *Tree) AddItemToBranch(n *Node, e Entity)
- func (t *Tree) AddItemToLeaf(n *Node, e Entity)
- func (t *Tree) AddItemToNode(n *Node, e Entity)
- func (t *Tree) AddObjectToNode(n *Node, e Entity, b BoundingBox, sa float64)
- func (t *Tree) ChildRefit(cur *Node, propogate bool)
- func (t *Tree) ComputeVolume(n *Node)
- func (t *Tree) ConcurrentTraverse(test HitTest) []Entity
- func (t *Tree) ConcurrentTraverseNode(cur *Node, test HitTest) (hits []Entity)
- func (t *Tree) CreateNode(bucketIndex int) (n *Node)
- func (t *Tree) CreateNodeFromSplit(parent *Node, split *SplitAxisOpt, side NodeSide, depth, bucketIndex int) *Node
- func (t *Tree) FreeBucket(n *Node)
- func (t *Tree) FreeNode(n *Node)
- func (t *Tree) GetLeaf(e Entity) (n *Node, ok bool)
- func (t *Tree) GetOrCreateFreeBucket() (index int)
- func (t *Tree) Image(path string)
- func (t *Tree) IsEmpty(n *Node) bool
- func (t *Tree) ItemCount(n *Node) int
- func (t *Tree) MapLeaf(e Entity, n *Node)
- func (t *Tree) MoveItemBetweenNodes(from, to *Node, e Entity)
- func (t *Tree) Optimize()
- func (t *Tree) QueueForOptimize(e Entity) bool
- func (t *Tree) RefitVolume(n *Node) bool
- func (t *Tree) Remove(e Entity)
- func (t *Tree) RemoveItemFromNode(n *Node, e Entity)
- func (t *Tree) RemoveNode(n *Node) *Node
- func (t *Tree) SetDepth(n *Node, depth int)
- func (t *Tree) SplitIfNecessary(n *Node)
- func (t *Tree) SplitNode(n *Node)
- func (t *Tree) Traverse(test HitTest) []Entity
- func (t *Tree) TraverseNode(cur *Node, test HitTest) (hits []Entity)
- func (t *Tree) TryFindBetterNode(cur *Node, e Entity) (bn *Node, ok bool)
- func (t *Tree) TryRotate(n *Node)
- func (t *Tree) UnmapLeaf(e Entity)
- type Vec3
Constants ¶
Variables ¶
This section is empty.
Functions ¶
func EntitiesSurfaceArea ¶
Types ¶
type BoundingBox ¶
type BoundingBox struct {
Min, Max Vec3
}
func BoxFromEntity ¶
func BoxFromEntity(e Entity) BoundingBox
func (BoundingBox) Equals ¶
func (b BoundingBox) Equals(b2 BoundingBox) bool
func (BoundingBox) Expand ¶
func (b BoundingBox) Expand(b2 BoundingBox) BoundingBox
func (BoundingBox) Intersects ¶
func (b BoundingBox) Intersects(b2 BoundingBox) bool
func (BoundingBox) SurfaceArea ¶
func (b BoundingBox) SurfaceArea() float64
type CustomDrawer ¶
type HitTest ¶
type HitTest func(box BoundingBox) bool
type Node ¶
type Node struct {
Box BoundingBox
Parent *Node
Left *Node
Right *Node
Depth int
NodeIndex int
BucketIndex int
State NodeState
}
func (*Node) AssignVolume ¶
func (*Node) CompareDepth ¶
func (*Node) ExpandParentVolume ¶
func (*Node) ExpandVolume ¶
func (*Node) GetSibling ¶
func (*Node) IsValidBranch ¶
func (*Node) IsValidBranchNode ¶
func (*Node) IsValidLeafNode ¶
type SplitAxisOpt ¶
func (*SplitAxisOpt) LeftEndIndex ¶
func (s *SplitAxisOpt) LeftEndIndex() int
func (*SplitAxisOpt) LeftItemCount ¶
func (s *SplitAxisOpt) LeftItemCount() int
func (*SplitAxisOpt) LeftStartIndex ¶
func (s *SplitAxisOpt) LeftStartIndex() int
func (*SplitAxisOpt) RightEndIndex ¶
func (s *SplitAxisOpt) RightEndIndex() int
func (*SplitAxisOpt) RightItemCount ¶
func (s *SplitAxisOpt) RightItemCount() int
func (*SplitAxisOpt) RightStartIndex ¶
func (s *SplitAxisOpt) RightStartIndex() int
func (*SplitAxisOpt) TryImproveAxis ¶
func (s *SplitAxisOpt) TryImproveAxis(a Axis)
type Tree ¶
func (*Tree) AddItemToBranch ¶
func (*Tree) AddItemToLeaf ¶
func (*Tree) AddItemToNode ¶
func (*Tree) AddObjectToNode ¶
func (t *Tree) AddObjectToNode(n *Node, e Entity, b BoundingBox, sa float64)
func (*Tree) ChildRefit ¶
func (*Tree) ComputeVolume ¶
func (*Tree) ConcurrentTraverse ¶
func (*Tree) ConcurrentTraverseNode ¶
func (*Tree) CreateNode ¶
func (*Tree) CreateNodeFromSplit ¶
func (*Tree) FreeBucket ¶
func (*Tree) GetOrCreateFreeBucket ¶
func (*Tree) MoveItemBetweenNodes ¶
func (*Tree) QueueForOptimize ¶
func (*Tree) RefitVolume ¶
func (*Tree) RemoveItemFromNode ¶
func (*Tree) RemoveNode ¶
func (*Tree) SplitIfNecessary ¶
func (*Tree) TryFindBetterNode ¶
Source Files
Directories
Click to show internal directories.
Click to hide internal directories.