0
\$\begingroup\$

Goal: Render distance lines between two points on the surface of a mesh-based primitive (i.e. sphere, cube, etc).

Lines drawn on surface of sphere Current Solution: Iteratively traverse distance line between two end points and "reverse" raycast through this point somehow. Since the distance line directly connects both vertices through the mesh, the according points on the mesh surface are required.

Ray ray = new Ray();
RaycastHit raycastHit;
ray.origin = posOnDistanceLine;
ray.direction = raycastNormal.normalized;
// Reverse ray since we can't raycast from inside the mesh
ray.origin = ray.GetPoint(1);
ray.direction = -ray.direction;

Lines are then drawn using Unity's LineRenderer which is being populated with positions of vertices whenever a change in normals (to previous raycast) is identified.

Issues:

  • Horrible performance (as 100 rays are cast whenever the end points move).

  • Solution doesn't always work and produces unexpected, jagged lines / points.

Question: Is there a better approach to implement this?

\$\endgroup\$
  • \$\begingroup\$ Do you have any constraints on the mesh shape / topology? Solving problems like this on the most general case can get quite thorny, but if the meshes are generally "sphere-like" in some sense then there might be much more efficient options. \$\endgroup\$ – DMGregory Feb 27 at 23:55
  • \$\begingroup\$ I'd appreciate the algorithm to be applicable for common 3D primitives such as cubes, pyramids, cylinders and spheres. The idea is to give the user the possibility to measure simple shapes. \$\endgroup\$ – Adrian MK Feb 28 at 0:09
  • \$\begingroup\$ Ah, so does this solution also need to report back the distance traveled by the line? (For instance, I can imagine a shader-based solution that will draw the line on the GPU as part of rendering the mesh, but it will have no concept of length it could report back to the CPU) \$\endgroup\$ – DMGregory Feb 28 at 0:12
  • \$\begingroup\$ Yes, unfortunately, to overly complicate this task, the distance traveled by the line needs to be approximated as well. Given my current solution this is done by summation of the polyline defined by vertices in-between those two user-defined end points. It suffers from performance issues though and even if that's the only feasible solution, I can't seem to fully make it work. \$\endgroup\$ – Adrian MK Feb 28 at 0:16
0
\$\begingroup\$

This is effectively a navmesh pathing problem.

First, you'll iterate over your mesh data (vertex positions and triangle indices) and build a set of adjacency information - so you can associate each triangle with its adjacent edges, and from there to its neighbouring triangles. I describe a version of this process in another answer.

Next, you can use a pathfinding algorithm like A* to determine a path across the adjacency graph you've created, joining your initial triangle to your destination triangle. You can use a funnel algorithm to pull this path "taut," finding the crossing point along each edge that minimizes the length of the resulting path.

Lastly, you can walk over each segment of the resulting path, adding a point to your line renderer wherever it crosses a triangle edge, and summing the length of the segments you've built to determine the total measurement.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer! You don't happen to know a code sample / paper that features an in-depth tutorial explaining the entire "mesh as a graph in adjacency list" procedure? Your other answer, while decently written, is a little overwhelming at first glance, as I lack comparable expertise in the matter :-) \$\endgroup\$ – Adrian MK Feb 28 at 1:08

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.