The distortion comes from trying to map R^2 onto the surface of the mesh, since they have different curvature, so they only "match" near the origin.
But the random-walk algorithm doesn't actually need to happen in R^2; I think it should be relatively straightforward to adapt to walk directly on the mesh.
Instead of tracking an "angle", you just need to track the forward tangent vector. And then walk in very small steps using the geodesic walk algorithm, turning the tangent at each point proportional to the derivative and normal at the new location.
It will probably be slower, but it means it will be distortion-free, since you're no longer trying to force flat coordinates onto a non-flat surface.
Dealing with intersection is more complicated, though - I think you could probably just use an octree structure for acceleration (like the spatial tree in 2D). Since the segments can be each placed (almost) exactly on planar triangle faces, you can just project onto one/both of the segments' containing faces to check for intersection.
But the random-walk algorithm doesn't actually need to happen in R^2; I think it should be relatively straightforward to adapt to walk directly on the mesh.
Instead of tracking an "angle", you just need to track the forward tangent vector. And then walk in very small steps using the geodesic walk algorithm, turning the tangent at each point proportional to the derivative and normal at the new location.
It will probably be slower, but it means it will be distortion-free, since you're no longer trying to force flat coordinates onto a non-flat surface.
Dealing with intersection is more complicated, though - I think you could probably just use an octree structure for acceleration (like the spatial tree in 2D). Since the segments can be each placed (almost) exactly on planar triangle faces, you can just project onto one/both of the segments' containing faces to check for intersection.