0
\$\begingroup\$

How can i determine if a ray was hitting an edge of a mesh?

The figure below shows what I want to achieve:

enter image description here

Any ideas?

\$\endgroup\$
2
  • \$\begingroup\$ Can you define what you mean by "an edge of a mesh" ? Do you mean any edge on any triangle that the mesh contains? What have you tried and why did it fail? \$\endgroup\$
    – TomTsagk
    Sep 11 '18 at 9:48
  • \$\begingroup\$ Hey, thanks for your reply! By edge I mean a corner of a building or generally a sharp edge in a 3D Model, not every single edge in a mesh. I think it could be very complicated and I tried nothing so far because I dont have a clue on that. \$\endgroup\$
    – Jupp Otto
    Sep 11 '18 at 10:01
1
\$\begingroup\$

Adjacency information like this isn't needed for most stuff we do with meshes in games, so unfortunately the out-of-the-box representations don't make it easy to access.

The simplest way to do this, especially if you have only a few, simple meshes that need this, is to hand-place a narrow capsule collider along each edge you want to detect with raycasts this way, then fire your raycast against the physics layer containing these edge mark-up shapes.


If you want to automatically detect these edges, I'd recommend applying a pre-processing step to help accelerate the queries. You can do this at edit time or in-game when you load a mesh that needs this metadata.

  1. Iterate over all the mesh's vertices and build a lookup table that associates vertices in the same position with a shared index.

  2. Prepare an associative map edges, keyed by the shared indices of the two vertices it joins (always put the lower index first, so you get the same key regardless of order)

  3. Iterate over all the mesh's triangles and compute a face normal for each one by averaging its vertex normals. Use the edge map to store a reference to this triangle and its normal associated with each edge of the triangle.

  4. When you find two triangles that share an edge, check the angle between their face normals. If it's less than some threshold you choose, we can call this an internal edge and ignore it. If it's greater, then we call this a sharp edge and mark it up for raycast hits as follows. (You could also take into account whether it's a smooth-shaded edge or creased, if you choose)

  5. Build an associative map of crease edges. This will be again be keyed by vertex indices, but we'll use their original indices this time, not the shared alias as we used before. And we'll list them in the key in the order in which they appear consecutively when we wind around the triangle, so the two triangles meeting at an edge give opposite orders (assuming manifold geometry).

  6. We add our newly-discovered sharp edge to this final map. The value we store with this key is a float tolerance range, computed as the maximum tolerance distance you choose for your raycasts (how far from the edge can we hit and still call it an "edge hit"?) divided by the length of the altitude of the parent triangle measured from this edge to the opposite vertex.

Okay, that was exhaustive. But now we can keep this final map structure for each mesh, and throw away the intermediate structures we built along the way.

Now when we get a candidate raycast hit, we can get its triangle index property, and use that to check whether any of the three edges of the triangle are in the mesh's sharp edge map. If so, we get the hit's barycentric coordinate property, and check whether the weight for the opposite vertex is less than the tolerance value we stored in our map for that edge. If so, then we have struck within our tolerance distance of a sharp edge! :D


Okay, so that was a lot of work. One last strategy we could try is somewhat empirical:

When you get a candidate raycast hit, get the triangle normal. Using this, you can predict an expected depth for subsequent raycasts fired from slightly offset positions (as if you were hitting a flat plane). Fire a few such raycasts in the same direction as your original, from positions slightly offset from the first hit. If the depth of any of these raycasts is much larger than the prediction, then you've grazed past an edge, and you can treat the original hit as an edge hit.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your answer. The first and last suggestion will not work in my case I think. I Import the meshes at runtime, so I can not manually attach some colliders. The last one is problematic if a ray hits a surface on a very low angle, but for some cases that would work and I thought about that too. The second suggestion is the most pratcial I think and I'll give it a try. Thank you! \$\endgroup\$
    – Jupp Otto
    Sep 11 '18 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.