spatial/kdtree: Go generics ideas based on user experience

[soypat]

Props

Let me start by saying I am amazed by the kdtree implementation. I can't believe how fast I was up and running making a kdtree based SDF (didn't work perfect, but it did things!) I had NO idea what kdtree was before I started using this package- my knowledge of kdtrees was limited to gimmicky 80's movies CGI.

What are you trying to do?

I am attempting to transform a mesh into a signed distance function. To do this I must have a data structure that allows me to get the triangles of the mesh closest to a point in space in a reasonable amount of time.

What did you try?

Using current kdtree.

How does Gonum not allow you to achieve your goal?

The issue I ran into was that the current kdtree implementation was more suited to problems where kdtree.Comparable (the base data structure) was the representation of a point of Dim dimensionality.

When working with a Triangle as a Comparable type there is a lot of superfluous data that is thrown around:

• BoundingBox is composed of Min and Max Comparables, which are also triangles. These should be points
• kdtree.Tree.Nearest(Comparable) should take a point in my case- which means Comparable.Distance() should also take a point as an argument if my rudimentary reasoning is correct
• Compare(Comparable, Dim) float64 I'm unsure how this is implemented in my case. Looking at the documentation for this method it seems very likely leaving it as Comparable is the soundest choice. Maybe worth adding a ComparePoint() method for the reduced case?

I'll end the issue on this flat not since I'm very new to the advanced data structure scene. These are just loose ideas we can discuss.

Given these changes, the kdtree types could look something like this if written with Go Generics (click to display):

// Interface is the set of methods required for construction of efficiently
// searchable k-d trees. A k-d tree may be constructed without using the
// Interface type, but it is likely to have reduced search performance.
type Interface[P any, T Comparable[P]] interface {
	// Index returns the ith element of the list of points.
	Index(i int) T

	// Len returns the length of the list.
	Len() int

	// Pivot partitions the list based on the dimension specified.
	Pivot(Dim) int

	// Slice returns a slice of the list using zero-based half
	// open indexing equivalent to built-in slice indexing.
	Slice(start, end int) Interface[P, T]
}

// Bounder returns a bounding volume containing the list of points. Bounds may return nil.
type Bounder[P any] interface {
	Bounds() *Bounding[P]
}

type bounder[P any, T Comparable[P]] interface {
	Interface[P, T]
	Bounder[P]
}

// Dim is an index into a point's coordinates.
type Dim int

// Comparable is the element interface for values stored in a k-d tree.
type Comparable[P any] interface {
	// Compare returns the signed distance of a from the plane passing through
	// b and perpendicular to the dimension d.
	//
	// Given c = a.Compare(b, d):
	//  c = a_d - b_d
	//
	Compare(Comparable[P], Dim) float64
	ComparePoint(P, Dim) float64
	// Dims returns the number of dimensions described in the Comparable.
	Dims() int

	// Distance returns the squared Euclidean distance between the receiver and
	// the parameter.
	Distance(P) float64
}

// Extender is a Comparable that can increase a bounding volume to include the
// point represented by the Comparable.
type Extender[P any] interface {
	Comparable[P]

	// Extend returns a bounding box that has been extended to include the
	// receiver. Extend may return nil.
	Extend(*Bounding[P]) *Bounding[P]
}

// Bounding represents a volume bounding box.
type Bounding[P any] struct {
	Min, Max P
}

[kortschak]

I'd be happy for this (and the other spatial containers) to be rewritten as type-parameterised code. It would be in the v0.12 milestone.

For your specific case, I'd suggest making the distance compares between triangle centers (first convert your triangles to cows and then convert those to idealised point masses, which is already a solved problem). Alternatively, you can choose either the closest or furthest vertex; whichever is better for your use case.

[soypat]

Awesome! So does adding a second type parameter P for the point type make sense to you?

[kortschak]

Yes, I think so. I'd like to see an implementation.

[soypat]

Not entirely happy with how it turned out. Feel like there are some knobs that could be turned

• kdtree algorithm: https://github.com/soypat/go-play3d/blob/main/kdtree/kdtree.go
• implementation of kdtree interface: https://github.com/soypat/go-play3d/blob/main/triangle_kdtree.go
  Instantiation: kdtree.New[kdPoint, *kdTriangle](kdMesh{tri: kdtri}, true)