1
\$\begingroup\$

Why do solutions such as Recast voxelize a 3D scene before transforming it back into polygons?

Would it not be possible to just determine intersections of meshes, check for slope angles and adjust triangulations in that way? I think agent height problems could also be solved by testing sweeps upwards against the other meshes.

\$\endgroup\$
1
  • \$\begingroup\$ Nothing ever needs to be voxelized or rasterized. But people do it anyway because it is useful. You've tried computing the intersections as you describe already, I presume, and had trouble with it, which is why you came here to ask for help. You know first-hand how hairy and error-prone it gets. Is that not enough reason to try to simplify the problem to a regular grid? \$\endgroup\$
    – DMGregory
    May 17 at 10:48
2
\$\begingroup\$

DMGregory's point about voxelization's simplicity seems about right. Another reason though, is performance. With these navmesh algorithims, you need a way to reduce the complexity of a scene.

Voxelization is a way of reducing the complexity of high poly meshes. Additionally it has the same effect as spatial partitioning whereby the number of potential neighbors of any feature (triangle/voxel) is reduced to a small, finite amount. You can imagine, depending on the mesh, that a long triangle could require intersection checks with a large portion of the scene, while that will never be the case with a voxel.

If you're interested in different approaches then Recast, here's a video by Casey Muratori in which he explains the (real-time) walking system he developed for the Witness. From what I remember, instead of voxels, he uses sort of poles to quantize the world (thereby simplifying it)

\$\endgroup\$
2
  • \$\begingroup\$ I've also seen voxelization used as a way to eliminate problems with non-watertight/non-manifold geometry, so I suspect that's in play here too. \$\endgroup\$
    – DMGregory
    May 18 at 3:55
  • \$\begingroup\$ yeah I think Casey talks about this exact issue in his video. I've made some procedural IK crawlies before which use raycasts > navmeshes and they basically run into this problem unless the level geometry is made with special care and attention. \$\endgroup\$
    – Charly
    May 18 at 4:05

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.