THREE.js raycasting very slow against single > 500k poly (faces) object, line intersection with globe

Question

in my project I have a player walk around a globe. The globe is not just a sphere, it has mountains and valleys, so I need the players z position to change. For this I'm raycasting a single ray from player's position against a single object (the globe) and I get the point they intersect and change players position accordingly. I'm only raycasting when the player moves, not on every frame.

For a complex object it takes forever. It takes ~200ms for an object with ~1m polys (faces) (1024x512 segments sphere). Does raycasting cast against every single face ?

Is there a traditional fast way to achieve this in THREE, like some acceleration structure (octree? bvh? -- tbh from my google searches I haven't seem to find such a thing included in THREE) or some other thinking-out-of-the-box (no ray casting) method?

        var dir = g_Game.earthPosition.clone();
        var startPoint = g_Game.cubePlayer.position.clone();
        var directionVector = dir.sub(startPoint.multiplyScalar(10));
        g_Game.raycaster.set(startPoint, directionVector.clone().normalize());
        var t1 = new Date().getTime();
        var rayIntersects = g_Game.raycaster.intersectObject(g_Game.earth, true);
        if (rayIntersects[0]) {
            var dist = rayIntersects[0].point.distanceTo(g_Game.earthPosition);
            dist = Math.round(dist * 100 + Number.EPSILON) / 100;
            g_Player.DistanceFromCenter = dist + 5;
        }
        var t2 = new Date().getTime();
        console.log(t2-t1);

Thank you in advance

Answer 1

Do not use three.js Raycaster.

Consider Ray.js that offers function intersectTriangle(a, b, c, backfaceCulling, target)

Suggested optimizations:

1. If player starts from some known positions ⇒ you must know his initial height, − no need to raycast (or just do one time full mesh slow intersection)

2. if player moves with small steps ⇒ next raycast will most likely intersect the same face as before.

Optimization #1 − remember previous face, and raycast it first.

3. if player does not jump ⇒ next raycast will most likely intersect the adjacent face to the face where player was before.

Optimization #2 − build up a cache, so that given a face idx you could retrieve adjacent faces in O(1) time.

This cache may be loaded from the file, if your planet is not generated in real time.

---

So with my approach on each move you do O(1) read operation from cache and raycast 1-6 faces.

Win!