Efficiently snap to vertices in threejs

Question

I wanted to make a snapping functionality to snap to my mesh vertices. I experimented with several solutions.

One solution is to add THREE.Sprite instances for all vertices in my scene and then using a rayCaster to decide whether there is a snap point in the intersects array. It works pretty well; here is a fiddle with a demo.
The idea is to hide the sprites in the final solution so they won't be rendered, but my scenes are pretty big so it would still mean adding lots of sprites to my scene (for every vertex one so possibly thousands of sprites) to detect snap points with my rayCaster.

var intersects = rayCaster.intersectObject(scene, true);
var snap = null;
if (intersects.length > 0) {
    var index = 0;
    var intersect = intersects[index];
    while (intersect && intersect.object.name === 'snap') {
        snap = sprite.localToWorld(sprite.position.clone());
        index++
        intersect = intersects[index];
    }
    if (intersect) {
        var face = intersect.face;
        var point = intersect.point;
        var object = intersect.object;
        mouse3D.copy(point);
    }
}
if (snap) {
    renderer.domElement.style.cursor = 'pointer';
} else {
    renderer.domElement.style.cursor = 'no-drop';
}

---

I also thought of an alternative solution by doing the math using results from the rayCaster. That solution is demonstrated in this fiddle.
The idea here is to test all vertices from the geometry of the object (mesh) that is intersected and then check whether the distance between the intersect point and those vertices from the geometry is smaller then the snap threshold.

var intersects = rayCaster.intersectObject(mesh, true);
if (intersects.length > 0) {
    var distance, intersect = intersects[0];
    var face = intersects[0].face;
    var point = intersects[0].point;
    var object = intersects[0].object;
    var snap = null;
    var test = object.worldToLocal(point);
    var points = object.geometry.vertices;
    for (var i = 0, il = points.length; i < il; i++) {
        distance = points[i].distanceTo(test);
        if (distance > threshold) {
            continue;
        }
        snap = object.localToWorld(points[i]);
    }
    if (snap) {
        sphereHelper.position.copy(snap);
        sphereHelper.visible = true;
        renderer.domElement.style.cursor = 'pointer';
    } else {
        sphereHelper.visible = false;
        renderer.domElement.style.cursor = 'no-drop';
    }
}

The sad thing is that in the second solution snap will only work when the mouse is moved from the surface of the intersected object towards a vertex. In case the mouse is moved from outside the object (so there is no intersection) the snapping won't work. In that respect the first solution with sprites is much more usable...

My question, am I overcomplicating things and is there a better/simpler/more efficient way to do this? Any suggestions for alternative approaches are welcome.

Answer 1

I looked into @meepzh his suggestion of using an octree and made the following solution using this threeoctree repository from github. The THREE.Octree class did not solve all my problems out-of-the-box so I added custom method findClosestVertex to the THREE.Octree class that can be used like this.

var snap = octree.findClosestVertex(position, radius);

snap is null in case no vertices within the radius of position and returns the closest point (THREE.Vector3) in world space otherwise.

I made a Pull-Request here on github for the new method.

Here is a demo in a fiddle