Mesh picker

[sri-30]

Fixes # This PR adds a triangle class and set of bvh classes which allow for fast ray intersection lookups with mesh instances.

These lookups can be performed with the following code:

d = meshInstance.rayCast(ray)

This function returns the closest hitpoint of the ray on the mesh, relative to the ray origin, or null if there is no intersection.

Two new example have also been added to demonstrate this: mesh-picker and mesh-picker-animated. mesh-picker-animated demonstrates the BVH refitting with an animated mesh.

Mesh-picker example:

Mesh-picker animated example:

Credits to @kungfooman for the bounding-box area function

I confirm I have read the contributing guidelines and signed the Contributor License Agreement.

[sri-30]

Nice work, I know this is rather complicated so I wondered what resources you used.

I could find this one: https://jacco.ompf2.com/2022/04/21/how-to-build-a-bvh-part-3-quick-builds/ (looks like exact copies partly)

Thank you for your comments - I've acted on them and made the appropriate changes. Yes, it's almost entirely based on that tutorial series - I'm currently looking into other potential algorithms for building the BVH, while keeping the same base class structure.

[mvaligursky]

also, please add some screenshots of the examples to the PR.

[kungfooman]

A note about MeshInstance#rayCast(ray):

Returning the result in the form of a reference to a temporary variable isn't good practise, you can check how other methods are doing it, like transformVector(vec, res = new Vec3()) {

Basically the user tells the method where to save the result, and if the result is not specified, allocate it. As it is right now, it's impossible to save a bunch of results without .copy()-ing them manually (the results overwrite each other, as they are all the same reference).

Also every trace function I ever used returns more than just the end position, at least people need the surface normal aswell (e.g. to create bullet marks or place an otherwise aligned entity).

There is already a class for this which could be reused:

https://github.com/playcanvas/engine/blob/005871dc5ec721af3cd5ecb5c804e3ad98f7319b/src/framework/components/rigid-body/system.js#L22-L31

Another issue is that Ammo physics sets the standard here by having raycastFirst(start, end) and raycastAll(start, end).

IMO that makes more sense, for example if you do mouse/camera picking, you use camera.screenToWorld, nearClip and farClip giving you a pair of start/end points.

Since @willeastcott worked a lot with the Ammo API, what are your thoughts on this? Can e.g. RaycastResult just be exported and reused? Or maybe it should be separated, to reduce bundle/treeshaking issues. Or just a new "raycast result class" altogether.

[kungfooman]

I stress-tested the performance a little bit to see where it can be improved and without refitting, it boils down to:

And:

Both methods have lots of potential to be shortened/optimized by removing useless property lookups.

[kungfooman]

I reworked this locally a bit to not mix it up with Mesh and MeshInstance because not everyone requires Bvh and that makes tree-shaking tricky (and also somewhat Separation of Concerns here).

So my idea is just: Bvh and BvhInstance aswell.

So Bvh is holding the tree, but BvhInstance tells you the node for pos/rot/scale to rotate the raycasting ray around.

[mvaligursky]

I reworked this locally a bit to not mix it up with Mesh and MeshInstance because not everyone requires Bvh and that makes tree-shaking tricky (and also somewhat Separation of Concerns here).

Yep agreed, I was thinking about it few weeks ago and reached the same conclusion.

[issacclee]

Hi Guys, Am I right to assume that when this PR is done and merged, we'll effectively get the capabilities of three-mesh-bvh build into the Playcanvas main engine?

[mvaligursky]

.. we'll effectively get the capabilities of three-mesh-bvh build into the Playcanvas main engine

That is partially true. It will support fast ray to mesh intersection on CPU, but not on the GPU (yet anyways). It also does not in its current form handles morphing, skinning and instancing. But for common static meshes, that is the case.

[mvaligursky]

I'm closing this until we have time to address feedback / make it into a final form of API, at which time it can be reopened and worked on. The issue is here: https://github.com/playcanvas/engine/issues/4645