Search code examples
c#xnapath-findingraycasting

How can i use triangle picking to determine the exact location of a triangle in world space coordinates?

Im trying to implement point and click movement in my game, but at the moment im stumped about how i can select parts of a mesh for the player to walk to.

So what ive done is ive got a navigational mesh in my game, i can select points from it, but what i want to do is be able to select the navigational mesh in real time and be able to tell the player where to go on the navigational Mesh, how can i achieve this?

I thought triangle-picking might be one way to determine where im selecting the mesh with mouse unproject but i think i need a bit more accuracy than that, no?

How can i achieve point and click on a navigational mesh in real time?

Thanks

Solution

  • Disclaimer; I haven't used navigational meshes myself yet. But I would think it would work something like this:

    I would guess you should have this mesh in some kind of data structure that makes spacial searh easy (quad-/octree). You would then cast a ray from the mouse pointer along the camera.

    https://gamedev.stackexchange.com/questions/26106/screen-space-to-world-space

    you then do a search in your mesh, using the datastructure to reduce the number of points you need to check.

    If your mesh is essentially flat, you can also just use a fictional plane. This simplifies ths drasticly as you get a 3d-position that you can search for the nearest nav-point to instead of a ray to check intersection with.

    An other way of doing selection in 3D is to have an off-screen rendertarget that each selectable draws a special color to. You then just need to check what color you clicked and look that up in a Dictionary or something. Don't know how this would work with a navigation mesh, though.

    Edit (Quadtrees); Quadtrees in this context are basicly a way of distributing elements in your game by location. usually they are axis-aligned and positioned around the world origio ([0,0,0]). What they do is basicly splitting your list of elements into 4 based on which quadrant of the world they exist in on the x-z-plane. Let's call these Nodes. So if you look for an element that is close to an element at [10,0,15], you would look in the list for the node that belongs to quadrant [>0,*,>0].

    As your nodes get a lot of objects in their list, you split them into 4 again. So if your node is [0, -100, 0] to [100, 100, 100], the children will be:

    n0: [0,-100,0] to [50,100,50]
    n1: [50,-100,0] to [100,100,50]
    n2: [0,-100,50] to [50,100,100]
    n3: [50,-100,50] to [100,100,100]

    All nodes have a BoundingBox that you use to check intersection with to decide if you should continue searching inside the node.

    Case: Object @ [20,10,20] wants to find objects within 10 units in a world with 1.000 objects distributed from [-100,-100,-100] to [100,100,100];

    • Create a BoundingSphere around the position with radius 10.
    • Intersect-test 4 top-level nodes. n1 returns true ([0,-100,0] to [100,100,100])
    • n1 has its own children, so we intersect them also. n0 returns true ([0,-100,0] to [50,100,50])
    • n1/n0 has no children, so we check the 62 objects in its list and return those that has boundingspheres/boxes that intersect with the range-sphere.

    This way, we search a list of 62 objects instead of one with 1.000. to reduce the number of intersect-checks by 937 (we wouldn't check against the object itself anyway), we only had to do 8 intersect-tests; all top-level nodes (4) and n0's children (4).

    So intersect-tests went from 999 to 70. THAT is progress :)