Triangle Raycasting

[gordonnl]

Hi Nathan,
Here is a draft: examples/raycasting-triangles.html

Please do not look at the code inside the html page, i've tried different options, copied & pasted some of your example, without cleaning anything... ok.

Here are the line that compute the triangle raycast. Not so much. I wrote it my style (no semicolon, leading blank line, no inline-if) because it's a draft, if there's a PR i will rewrite it in ogl actual style.

It's not exactly the same code than three.js which i do not really understand in the details, but we are trying to solve the same equation.

The one i use is O + k * D = A + ku * U + kv * V

For better performances, i prefer to dereference all the component (x, y, z) from the vector, and write directly dot and cross product rather than calling function (since calculations are not as dense as in the case of matrices). Generally speaking i do not think that seeking optimization in javascript is a primary goal, but here, since meshes can have thousands of triangles, i prefer to be careful.

If the code for raycast triangle seems ok, i still have bug with non-indexed geometry (sometimes hover produce flickering, triangles are not drawn under the mouse):
examples/raycasting-triangles.html?fox=true.

I do not have time yet to understand why. A first bug came from null triangle than can be provided in models, so i wrote a check first. For non-indexed geometries, every 3 vertices from the position attributes represent a triangle right?

Also, raycast may have some option (backface culling, distance max), actually i only return the closest triangles, but it may be useful to have all the triangles (in case of non-convex geometries). And also actually the test is made mesh by mesh, but may be done from any node (eg: scene) by walking through every child.

At last, is there actually a way to display debug lines / dot / vectors?
It could be useful to display pivot from any Transform, normal from raycast etc. What could be the best option to achieve that do you think?

Many questions. Not sure the current issue is really concerned. Should we move the discussion elsewhere?

Originally posted by @jniac in #38 (comment)

[gordonnl]

hey @jniac
Thanks so much for your work, it seems to be working great already in your example. Obviously I moved the discussion to this new issue as per your final point.

To answer your questions/points:

• Generally using the math functions should already be pretty optimal - I definitely wouldn't suggest creating any new Math instances (Vec3 etc) in these functions, instead I would create helper/dummy instances that I re-use for each iteration of the function.
• You're correct for non-indexed meshes, the vertices listed in order, repeating vertex values where necessary for each triangle.
• I'm more than happy with your approach, but in general Threejs is a fantastic reference as they have many extremely talented devs constantly improving and optimising where they can - especially for these sorts of lower-level math functions.
• extra options could be passed in with a second argument object (backface culling etc).
• For now, I would keep the argument approach the same as intersectBounds where you pass in an array of meshes. Parsing children is sometimes handy, sometimes unwanted, and it can create confusion (I've done it this way before).
• There's no pre-made class for line helpers, but if you have a geometry of two points, and render it with the mesh mode set to gl.LINES that should give you a quick and easy line. For dots, if it's just one I generally make a sphere, if it's lots I use a point cloud by setting the mesh mode to gl.POINTS.

Thanks again mate!

[jniac]

hi @gordonnl
Yep ThreeJS is a great reference, since i've found a vulnerabilities with my approach (when direction.x === 0 && direction.y === 0) i will look closer to the solution that implemented ThreeJS, which derived directly from the one published by https://www.geometrictools.com/.

So i give back here the different links:
ThreeJS Ray.js intersectTriangle
GeometricTools original C++ code
GeometricTools Linear Planar Intersection page
GeomtricTools seems provide exhaustive documentation and code (from 2D algorithms (blur, level lines) to 3D geometry & physics).

I hope you're not in a hurry about triangle raycasting. I would like to give my solution a second chance before implementing the one from geometrictools (which seems more straight). I'm interested in art and techniques and i have to manage a subtle balance between the two. Some domains seems too hard to deal with (3D physics), but 3D general geometry (as primitives intersections, raycasting) seems accessible to me and may inspire some visual creation. I would like to take the opportunity to learn a little more.

Ok for the intersectBounds approach.
I'll probably will develop a little helper to draw line over all (base on the gl.LINES mode).

[gordonnl]

No rush for me mate! Take your time ;)

[gordonnl]

Hey I actually needed this for a project, so I have implemented something based on Threejs' approach in this commit: 680be51.

Thanks again for your help!

[jniac]

I'm glad you implemented the feature, i really would like to do it, but between work, children and confinement, I ran out of time.