dyntree

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
  • func (a Axis) Next() Axis
• type BoundingBox
  • func BoxFromEntity(e Entity) BoundingBox
  • func (b BoundingBox) Equals(b2 BoundingBox) bool
  • func (b BoundingBox) Expand(b2 BoundingBox) BoundingBox
  • func (b BoundingBox) Intersects(b2 BoundingBox) bool
  • func (b BoundingBox) SurfaceArea() float64
• 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
  • func GetRotationSurfaceArea(n *Node, rot Rot, sa float64) RotOpt
  • func (best *RotOpt) FindBestRotation(n *Node, r Rot, sa float64)
• 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 NewTree() *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

const (
	X Axis = iota
	Y
	Z

	ROTNONE Rot = iota
	LEFTRIGHTLEFT
	LEFTRIGHTRIGHT
	RIGHTLEFTLEFT
	RIGHTLEFTRIGHT
	LEFTLEFTRIGHTRIGHT
	LEFTLEFTRIGHTLEFT

	OPTIMIZATIONQUEUED NodeState = iota

	LEFT NodeSide = iota
	RIGHT
)

Functions

func EntitiesSurfaceArea

func EntitiesSurfaceArea(ea []Entity, start, ct int) float64

Types

type Axis

type Axis int

region

func (Axis) Next

func (a Axis) Next() Axis

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 CustomDrawer interface {
	DrawImage(*image.RGBA)
}

type Entity

type Entity interface {
	Position() Vec3
	Radius() float64
}

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 (n *Node) AssignVolume(pos Vec3, radius float64)

func (*Node) CompareDepth

func (n *Node) CompareDepth(n2 *Node) int

func (*Node) Equals

func (n *Node) Equals(n2 *Node) bool

func (*Node) ExpandParentVolume

func (n *Node) ExpandParentVolume(child *Node)

func (*Node) ExpandVolume

func (n *Node) ExpandVolume(pos Vec3, radius float64)

func (*Node) GetSibling

func (n *Node) GetSibling() *Node

func (*Node) HasParent

func (n *Node) HasParent() bool

func (*Node) IsLeaf

func (n *Node) IsLeaf() bool

func (*Node) IsValid

func (n *Node) IsValid() bool

func (*Node) IsValidBranch

func (n *Node) IsValidBranch() bool

func (*Node) IsValidBranchNode

func (n *Node) IsValidBranchNode() bool

func (*Node) IsValidLeafNode

func (n *Node) IsValidLeafNode() bool

type NodeSide

type NodeSide int

type NodeState

type NodeState int

type Rot

type Rot int

type RotOpt

type RotOpt struct {
	Rot Rot
	SA  float64
}

func GetRotationSurfaceArea

func GetRotationSurfaceArea(n *Node, rot Rot, sa float64) RotOpt

func (*RotOpt) FindBestRotation

func (best *RotOpt) FindBestRotation(n *Node, r Rot, sa float64)

type SplitAxisOpt

type SplitAxisOpt struct {
	Axis       Axis
	Items      []Entity
	SplitIndex int
	SA         float64
	HasValue   bool
}

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

type Tree struct {
	IsCreated bool

	Buckets [][]Entity
	// contains filtered or unexported fields
}

func NewTree

func NewTree() *Tree

func (*Tree) Add

func (t *Tree) Add(e Entity)

func (*Tree) AddItemToBranch

func (t *Tree) AddItemToBranch(n *Node, e Entity)

func (*Tree) AddItemToLeaf

func (t *Tree) AddItemToLeaf(n *Node, e Entity)

func (*Tree) AddItemToNode

func (t *Tree) AddItemToNode(n *Node, e Entity)

func (*Tree) AddObjectToNode

func (t *Tree) AddObjectToNode(n *Node, e Entity, b BoundingBox, sa float64)

func (*Tree) ChildRefit

func (t *Tree) ChildRefit(cur *Node, propogate bool)

func (*Tree) ComputeVolume

func (t *Tree) ComputeVolume(n *Node)

func (*Tree) ConcurrentTraverse

func (t *Tree) ConcurrentTraverse(test HitTest) []Entity

func (*Tree) ConcurrentTraverseNode

func (t *Tree) ConcurrentTraverseNode(cur *Node, test HitTest) (hits []Entity)

func (*Tree) CreateNode

func (t *Tree) CreateNode(bucketIndex int) (n *Node)

func (*Tree) CreateNodeFromSplit

func (t *Tree) CreateNodeFromSplit(parent *Node, split *SplitAxisOpt, side NodeSide, depth, bucketIndex int) *Node

func (*Tree) FreeBucket

func (t *Tree) FreeBucket(n *Node)

func (*Tree) FreeNode

func (t *Tree) FreeNode(n *Node)

func (*Tree) GetLeaf

func (t *Tree) GetLeaf(e Entity) (n *Node, ok bool)

func (*Tree) GetOrCreateFreeBucket

func (t *Tree) GetOrCreateFreeBucket() (index int)

func (*Tree) Image

func (t *Tree) Image(path string)

func (*Tree) IsEmpty

func (t *Tree) IsEmpty(n *Node) bool

func (*Tree) ItemCount

func (t *Tree) ItemCount(n *Node) int

func (*Tree) MapLeaf

func (t *Tree) MapLeaf(e Entity, n *Node)

func (*Tree) MoveItemBetweenNodes

func (t *Tree) MoveItemBetweenNodes(from, to *Node, e Entity)

func (*Tree) Optimize

func (t *Tree) Optimize()

func (*Tree) QueueForOptimize

func (t *Tree) QueueForOptimize(e Entity) bool

func (*Tree) RefitVolume

func (t *Tree) RefitVolume(n *Node) bool

func (*Tree) Remove

func (t *Tree) Remove(e Entity)

func (*Tree) RemoveItemFromNode

func (t *Tree) RemoveItemFromNode(n *Node, e Entity)

func (*Tree) RemoveNode

func (t *Tree) RemoveNode(n *Node) *Node

func (*Tree) SetDepth

func (t *Tree) SetDepth(n *Node, depth int)

func (*Tree) SplitIfNecessary

func (t *Tree) SplitIfNecessary(n *Node)

func (*Tree) SplitNode

func (t *Tree) SplitNode(n *Node)

func (*Tree) Traverse

func (t *Tree) Traverse(test HitTest) []Entity

func (*Tree) TraverseNode

func (t *Tree) TraverseNode(cur *Node, test HitTest) (hits []Entity)

func (*Tree) TryFindBetterNode

func (t *Tree) TryFindBetterNode(cur *Node, e Entity) (bn *Node, ok bool)

func (*Tree) TryRotate

func (t *Tree) TryRotate(n *Node)

func (*Tree) UnmapLeaf

func (t *Tree) UnmapLeaf(e Entity)

type Vec3

type Vec3 struct {
	X, Y, Z float64
}