vanruesc / sparse-octree

A sparse octree data structure.
zlib License
117 stars 20 forks source link

Setting a point a second time in PointOctree sets data to the wrong index #45

Closed TimmyTommy closed 2 years ago

TimmyTommy commented 2 years ago

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]. https://github.com/vanruesc/sparse-octree/blob/96296c57dbefa5ded8724b9cc5e7c58b0cd3f3d2/src/points/PointOctree.ts#L84

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:

image

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;
    }
}
vanruesc commented 2 years ago

Thanks for the report!

Should be fixed in sparse-octree@7.1.6.