Distance to StaticMesh
Distance to StaticMesh
Is there any quick way (even a hackish one) to calculate the distance of a kinematic entity to a StaticMesh? The AI in my game needs to be aware of it's surroundings, specifically the distance to large staticmesh models. The best thing I can think to do is use some sort of multi-dimensional binary tree structure to rapidly traverse the triangles to find the nearest vertices and measure distance to those, but that's neither accurate nor ideal, wondering if there's some better way I could accomplish with bepuphysics...
Re: Distance to StaticMesh
For general correct solutions, the static mesh's hierarchy is available. It's an object-aligned bounding box hierarchy. There is no built-in traversal which would provide the nearest triangles, unfortunately.
Algorithm wise, one option would be to implement a traversal which identifies a sufficiently deep node (if not a leaf node) which is close to (if not closest to) the entity position. Create a bounding sphere centered on the entity position with radius sufficient to contain the node entirely (distance to most distant bounding box corner in the node). Query the hierarchy with the bounding sphere to find all of the triangles to be tested. The deeper and closer the node search gets, the fewer triangles have to be tested.
Some approximate options:
-In the above, the closest node could be used directly without the secondary bounding sphere query. This might produce decent results depending on the mesh and accuracy requirements.
-In the case where the entity is very far away, computing the distance from the bounding box of the mesh to the position of the entity may be good enough.
-If you only care about determining the distance accurately when the object is less than some distance away, you could test a BoundingSphere against the StaticMesh's hierarchy. Assuming a reasonably small radius, the number of triangles to test would be cut substantially. You could also do a sort of binary search to a smaller sphere if the first sphere finds too many triangles (though there will need to be a balance between the cost of hierarchy queries and the cost of distance testing).
-If using a long-range approximation for the distance is possible, then local AI awareness could be solved with limited range ray cast feelers. Ray casts are easy to use, very fast, work for any object which is raycastable, and fit quite well for object avoidance or similar environment detection tasks. The cost of detecting the environment can be decreased significantly by performing only one or two ray casts a frame, but in such a way that the whole search area gets covered (randomly shooting them in a cone, for example).
Algorithm wise, one option would be to implement a traversal which identifies a sufficiently deep node (if not a leaf node) which is close to (if not closest to) the entity position. Create a bounding sphere centered on the entity position with radius sufficient to contain the node entirely (distance to most distant bounding box corner in the node). Query the hierarchy with the bounding sphere to find all of the triangles to be tested. The deeper and closer the node search gets, the fewer triangles have to be tested.
Some approximate options:
-In the above, the closest node could be used directly without the secondary bounding sphere query. This might produce decent results depending on the mesh and accuracy requirements.
-In the case where the entity is very far away, computing the distance from the bounding box of the mesh to the position of the entity may be good enough.
-If you only care about determining the distance accurately when the object is less than some distance away, you could test a BoundingSphere against the StaticMesh's hierarchy. Assuming a reasonably small radius, the number of triangles to test would be cut substantially. You could also do a sort of binary search to a smaller sphere if the first sphere finds too many triangles (though there will need to be a balance between the cost of hierarchy queries and the cost of distance testing).
-If using a long-range approximation for the distance is possible, then local AI awareness could be solved with limited range ray cast feelers. Ray casts are easy to use, very fast, work for any object which is raycastable, and fit quite well for object avoidance or similar environment detection tasks. The cost of detecting the environment can be decreased significantly by performing only one or two ray casts a frame, but in such a way that the whole search area gets covered (randomly shooting them in a cone, for example).