vanruesc / sparse-octree Goto Github PK

It looks like raycasting works just fine, but unit tests must still be written to consolidate that functionality.

Can there be any way this library removes its dependency from math-ds?

If this library is used with three-js, we end up having two math libraries living in the application bundle.

The raycast method creates multiple Vector3 instances each time it's called. This could be prevented by using static objects.

Hello,

children and data attributes are not declared as being possibly null in Octant class but are set to null in the constructor (https://github.com/vanruesc/sparse-octree/blob/92ad93cb9d59d9a081fc24a9d0aae46c3ccee4b4/src/core/Octant.ts#LL18C2-L18C19)

I believe definitions should look like something like that if you want to use null:

interface Node {
  children: Node[] | null;
}

interface DataContainer {
  data: T | null;
}

class Octant implements Node, DataContainer {
  children: Octant[] | null;
  data: T | null;
}

Otherwise, you could let the undefined types

interface Node {
  children?: Node[];
}

interface DataContainer {
  data?: T;
}

class Octant implements Node, DataContainer {
  children?: Octant[];
  data?: T;

  constructor() {
    this.children = null; // Remove this line or set to undefined
    this.data = null; // Remove this line or set to undefined
  }
}

This would allow us to have correct types for writing new kind of Octree.

The center of octants doesn't need to be recalculated for each distanceToCenterSquared call.
See here.

The duplicate detection logic is slow and needs to be improved.

Hello,

Thank you for this great library!

Unfortunately I found a bug when using the PointOctree.

When setting the same Point in the Octree the data is set wrong the second time.
The data is set to the index -1 of the data array.

I think this line should not use pointData.data[index - 1] but pointData.data[index].

I used this code to show reproduce the error:

private testOctree() {
	const min = new Vector3(-1, -1, -1);
	const max = new Vector3(1, 1, 1);
	const octree = new PointOctree(min, max);
	
	const myData1 = "test1";
	const myData2 = "test2";
	const p1 = new Vector3(0, 0, 0);
	const p2 = new Vector3(0, 0, 0);
	
	octree.set(p1, myData1);
	console.log((octree as any).root.data.data);
	octree.set(p2, myData2);
	console.log((octree as any).root.data.data);
	console.log(octree);
}

This is the console output:

I temporarily fixed the issue with patching your PointOctree.set method:

let sparseOctreePatched: boolean = true;
function tryPatchSparseOctree() {
    if (!sparseOctreePatched) {
        PointOctree.prototype.set = function(point, data) {
            return fixedOctreeSet(point, data, this, (this as any).root, 0);
        }
        function fixedOctreeSet<T>(point: any, data: T, octree: PointOctree<T>, octant: PointOctant<T>, depth: number): boolean {
            let children = octant.children;
            let exists = false;
            let done = false;
            if (octant.contains(point, octree.getBias())) {
                if (children === null) {
                    let index = 0;
                    if (octant.data === null) {
                        octant.data = new PointData();
                    } else {
                        const pointData2 = octant.data;
                        const points = pointData2.points;
                        for (let i = 0, l = points.length; !exists && i < l; ++i) {
                            exists = points[i].equals(point);
                            index = i;
                        }
                    }
                    const pointData = octant.data;
                    if (exists) {
                        pointData.data[index] = data; // <======================== Changed [index - 1] to [index]
                        done = true;
                    } else if (pointData.points.length < octree.getMaxPoints() || depth === octree.getMaxDepth()) {
                        pointData.points.push(point.clone());
                        pointData.data.push(data);
                        done = true;
                    } else {
                        octant.split();
                        octant.redistribute(octree.getBias());
                        children = octant.children;
                    }
                }
                if (children !== null) {
                    ++depth;
                    for (let i = 0, l = children.length; !done && i < l; ++i) {
                        done = fixedOctreeSet(point, data, octree, children[i] as PointOctant<T>, depth);
                    }
                }
            }
            return done;
        }
        sparseOctreePatched = true;
    }
}

This may be related to #40, or it may be caused by it (I'm not sure yet).

What happens is when I call OctreeRaycaster's intersectOctree, the PointOctree raycast function returns an error: pointData is undefined:

if(pointData !== null) {

	pointData.testPoints(raycaster, result);

}

The problem is that pointData is undefined, and therefore passes the not-null check.

Would this be solved if the call to raycastOctant in intersectOctree passed the root node of the octree, rather than the octree itself?

	static intersectOctree(octree: Tree, ray: Ray): Node[] {

		const result: Node[] = [];
		const t = intersectOctree(octree, ray, flags);

		if(t !== null) {
			// Shouldn't raycastOctant take a Node here? --
			raycastOctant(octree, t[0], t[1], t[2], t[3], t[4], t[5], result);

		}

		return result;

	}

I think I'm describing the issue properly, although I'm a bit new to octrees in general, so any help would be appreciated.

I'm creating a PointOctree to represent the centerpoints of objects in a scene. What I'm seeing is that when my worlds have fewer then 8 items, calling leaves(frustum) returns an empty iterator.

I can see that the transition happens between when root.data has 8 elements, and when root.data becomes null (presumably because adding the 9th item shifts points + data down into lower children leaves).

Is there a way to contain multiple data at the same point without overwriting the previous point?

Is there a way to use this in the broswer? I couldn't find a link/way to do this.

Hello, I have a 1000x1000x1000 3d sparse space and I want to convert it to an octree. I'm wondering how does it work in term of performance: initilization of the tree, insertion time and retrieve time?

Right now I use a Map to store/retrieve data but basically I convert 3d position to a new number that I then use as a key in the map - that is quite inefficient and I hope octree can help me achieve almost real-time performance for everything!

Great work!

I faced this issue when I try to find the nearest point in the point cloud. I used findNearestPoint method to do it but I have got an incorrect result. I investigated this problem.
There is the following code in PointOctree.js.

child = sortedChildren[i].octant;
if(child.contains(point, bestDist))
      childResult = findNearestPoint(point, bestDist, skipSelf, child);

You use contains from PointOctant.js and pass bestDist as a parameter where bestDist is squared distance. But this function expects a linear value of bias.

Hello Folks!

I am implementing a window selection feature within a three.js viewer, the idea is that user drags a 2d window over the model and the logic needs to select all components encompassed inside the projected volume.

A basic version of it works but I'm dealing with models which may have a large number of components, especially small parts inside a building. I currently check only bounding boxes of all components with a for loop which is very inefficient in complex models so looking for an optimized approach.

Could you give me some directions on how I may be able to use that library in order to create an octree of those bounding boxes and do an optimized check?

Thanks for any insights :)

An alternative should be developed to create more than one point in the same position.

Data aggregation makes this piece of code quite awkward. It would be easier to just let each Set have at least one null item, but there might be better solutions.