Help How to query Obi geometry with raycasts?

[Hatchling]

Does Obi provide the ability to query the geometry of Obi Actors, like how Physics.Raycast, .Spherecast, etc. allows you to query colliders?

I'm assuming that most of the math involved for this has already been done somewhere in there in order to support collision detection.

---

I see there is ObiParticlePicker, but it seems like this approach isn't optimal:

• Only allows picking particles directly, instead of by their collision geometry (simplexes)
  
• Doesn't return a point on the surface that the ray first made contact
  
• Doesn't query the particle grid to filter out most of the tests
  
• Isn't written in efficient threaded code in the same way that other collision checks are
  
• Only considers one solver
  
• Cannot be invoked in a static way (like Physics.Raycast)
  

If I were more familiar with how to interface with the internal stuff of Obi, I'd be willing to write these queries myself. An interesting idea might be to provide some sort of base query class where you can implement custom queries (for example, getting the closest point on a simplex to the query point, within a certain radius (or infinite radius)). If I wrote something like this, I'd be willing to share the code with the hope that it'd be maintained as Obi is developed.

A global query would probably follow this procedure:

1. Test the query condition against the oriented bounding box of each solver. If a given solver passes, then...
   
2. Test the query condition against all occupied cells, OR, in cases where it is possible to determine which cells pass the query condition without enumerating through each cell, get a list of cells that pass the query condition. If a given cell passes, then...
   
3. Test the query condition against all simplexes occupying the cell.
   
4. For each simplex that passes the query condition, modify the query result.
   • In the case of a Raycast, replace the current hit point if its distance from the ray is closer. 
     
   • In the case of a RaycastAll, add the hit point to the list of hit points.
     
   • In the case of a Checksphere (which returns true if any object occupies a spherical volume, otherwise false), terminate the query and return "true" as the query result if and when a simplex passes the query condition, otherwise false. (A similar test could be done on the cell/solver bounding box itself if it is fully contained within the Checksphere volume.)
     

A solver specific query would be similar, sans step 1.

I'm guessing that it'd be wasteful to redo all of the work involved in calculating queries like these, given that collision tests between line simplexes and other types are already possible. (A line simplex can be treated like a raycast or a spherecast, with minor modifications.)

[josemendez]

Hi hatchling,

There's no support for spatial queries currently, mainly due to lack of user interest. Most use cases I've been presented with do fine with either simple raycasting against particles in a solver (ObiParticlePicker) or collision callbacks (with or without triggers).

This is much more common in rigidbody engines, as they're usually central to gameplay and used much more intensively throughout the game. Hundreds of raycast/spherecast queries per frame are more common and useful against world geometry than against character cloth or ropes, for instance.

This being said, I'm open to implementing this as most of the foundation is already there as you said. It is just a matter of designing an API and exposing it in a convenient way.
Out of curiosity, what would you use this for in your game?

kind regards,

[Hatchling]

This being said, I'm open to implementing this as most of the foundation is already there as you said. It is just a matter of designing an API and exposing it in a convenient way.
Out of curiosity, what would you use this for in your game?

kind regards,

I can't go into too much detail about our project, but one feature we have is climbing. It works great on Unity colliders: We query a volume around the character for a suitable grab point in the desired direction of travel. We use a series of checks (which could be more optimal if we had lower-level access to PhysX) that finds the closest point on a collider to the center of a sphere, if it overlaps with that sphere. The character then animates to that point and the cycle continues.

If a similar query could be done quickly for ropes, it'd allow the character to treat ropes in a similar way. And potentially cloth or soft bodies.

Similarly, we use queries to test whether he should fall, slide (surface is too steep), or remain standing. Also, we use a series of sphere-casts are used to find surfaces that a character should vault onto; if a wall is detected, it checks above to see if there is a surface above the wall to climb upon. In theory there's no reason that the same logic cannot be applied to Obi actors (especially if they are large and heavy enough).

Another use case for queries would be to check if the character is submerged in particle-based liquid and switch to a swimming state.

Another thing that'd be desirable is for bullet projectiles (e.g. hitscan) to impact particles and push them away appropriately depending on the surface normal the projectile impacts. If there are a lot of projectiles flying around every frame, it'd be necessary to prune checks similar to what happens with PhysX queries.

Also, when an explosion occurs, we'd need to check a potentially large volume for particles and apply forces to them.

There's also the stuff mentioned previously, like picking up an individual particle and moving it around. While these are certainly more sparse and don't require knowing the exact nearest surface interesection with a ray, the extra speed and precision would be at least "nice" or open opportunities for more complex manipulations.

Feature parity with PhysX in this sense would basically open up a lot of opportunities to use Obi as a "PhysX for everything PhysX can't do", like soft deformable objects, or complex systems of joints (which often PhysX fails with). Obi has the potential to be used for a lot more than fancy effects: Consider BeamNG, which is basically an elaborate cloth simulation made of particles and constriants. The ultimate goal would be to have a single API for querying and manipulating both the PhysX and Obi universes so the features we develop for PhysX interactions naturally carry over (and show off) Obi.

[josemendez]

Currently designing an API for spatial queries. This will be part of Obi at some point in the near future.

[Hatchling]

Currently designing an API for spatial queries. This will be part of Obi at some point in the near future.

Wow dude, I'm happy this is being developed, you're a cool dude. I also hope I'm not being a pain in the ass.

[josemendez]

I also hope I'm not being a pain in the ass.

Not at all! These are all reasonable requests.

A rough idea of how this could work:

ObiSolver has a Query() method, to which you pass an array of QueryShape structs, an array of AffineTransform structs (one per QueryShape) and it returns an array of QueryResult structs. Internally, calling solver.Query(shapes,transforms) schedules a job that parallelizes over all shapes.

QueryShape would have the following fields:

type (box, sphere, ray)
contactOffset (adds extra thickness to the shape, turning a ray into a capsule, rounding box corners, etc).
minDistance (minimum distance to look for simplices around the shape)
filter (category+mask, used for collision filtering)

QueryResult would have the following fields:

shapeIndex: index of the shape in the QueryShape array passed to the function.
simplexIndex: index of a simplex in the solver.
point: point in the surface of the shape closest to the simplex.
normal: direction of the shortest path between the shape and the simplex.
distance: distance between the shape and the simplex along the normal. negative if they overlap, positive otherwise.

I think this covers raycasts, spherecasts, overlap tests (check whether result distance is negative) and distance tests against capsules, spheres and boxes. What do you think?

[Hatchling]

Could you please write a simple script that shows how it'd be used?

Judging from what I understand so far, I'd recommend allowing a list to be provided for query results. I know you could just use a really huge array. But I understand if this could possibly mess up some sort of optimization or simplicity with regards to how the parallelization is done.

I'm guessing a raycast (similar to Physics.Raycast) would be done by enumerating through the results and:

• Discarding results that have a positive distance
  
• Converting the "point" result to a raycast distance using a dot product "dot(point-rayOrigin,rayDirection)" and discarding all but the smallest positive result (the closest point ahead of the ray).
  
• Returning the result if they weren't all discarded.
  

Also, I LOVE the idea of contactOffset! This is something I wish Unity exposed in UnityEngine.Physics.

[josemendez]

Could you please write a simple script that shows how it'd be used?

The following code is already functional in the development version:

Code:

using UnityEngine;
using Obi;

[RequireComponent(typeof(ObiSolver))]
public class QueryTests : MonoBehaviour
{
    ObiSolver solver;

    ObiNativeQueryShapeList queries;
    ObiNativeAffineTransformList transforms;
    ObiNativeContactShapeList results;


    void Start()
    {
    solver = GetComponent<ObiSolver>();

        queries = new ObiNativeQueryShapeList();
        transforms = new ObiNativeAffineTransformList();
        results = new ObiNativeContactShapeList();

        queries.Add(new QueryShape()
        {
            type = QueryShape.QueryType.Box,
            center = Vector3.zero,
            size = new Vector3(2, 1, 1),
            contactOffset = 0.01,
            distance = 1,
            filter = ObiUtils.MakeFilter(ObiUtils.CollideWithEverything, 0)
        });

        transforms.Add(new AffineTransform(Vector4.zero,Quaternion.identity,Vector4.one));
    }

    private void OnDestroy()
    {
        queries.Dispose();
        transforms.Dispose();
        results.Dispose();
    }

    void Update()
    {
        // perform query
        solver.SpatialQuery(queries,transforms, results);

        // draw results:
        for (int i = 0; i < results.count; ++i)
        {
            Debug.DrawRay(solver.transform.TransformPoint(results[i].pointB),
                          solver.transform.TransformVector(results[i].normal * results[i].distance), Color.red);
        }
    }
}

For query results, I'm currently reusing the same struct used for contacts. Many of its fields are unused, so I'll write a leaner struct with only what's needed by the query.

Judging from what I understand so far, I'd recommend allowing a list to be provided for query results. I know you could just use a really huge array. But I understand if this could possibly mess up some sort of optimization or simplicity with regards to how the parallelization is done.

Since results are written by multiple threads, there's two main ways to go about this:

- parallel writing results into a queue, then dequeuing into an array.
- using a really large array (num queries * max hits per query) and writing the result directly into queryIndex * hitCount.

I went for the first option. Pros: no wasted memory, no missed hits. Cons: hits appear in no particular order, so you have to iterate trough them all and look at their queryIndex to correlate with the query that spawned them. You can't get the results of a specific query without iterating trough all the results, but usually you're interested in all the results (otherwise you'd make one single solver.SpatialQuery() call) so I guess this is ok?

Unity's RaycastCommands use the second option. Pros: you can access the results of a specific ray/query at queryIndex * maxHits. Cons: forces you to tradeoff memory for accuracy: either use a very large maxHits value thus allocating a huge array, or miss hits.

I'm guessing a raycast (similar to Physics.Raycast) would be done by enumerating through the results and:

• Discarding results that have a positive distance
  
• Converting the "point" result to a raycast distance using a dot product "dot(point-rayOrigin,rayDirection)" and discarding all but the smallest positive result (the closest point ahead of the ray).
  
• Returning the result if they weren't all discarded.
  

Yes, that's how you'd do it. I'm going to also add helper methods to perform single distance/overlap queries (no need to manually allocate lists for input/results) and perform single/multiple raycasts, all built on top of SpatialQuery(). No need to do this yourself.

[josemendez]

This is mostly done, I'm now writing unit tests and performing benchmark scenes.

Here's an example:



The API looks like this:

Code:

// Multiple general queries: pass a list of heterogeneous query shapes, return list of results.
// All other query methods are built on top of this one.
public void SpatialQuery(ObiNativeQueryShapeList shapes, ObiNativeAffineTransformList transforms, ObiNativeQueryResultList results);

Code:

// Single general query: pass a single query shape, returns the result.
public QueryResult[] SpatialQuery(QueryShape shape, AffineTransform transform)

Code:

// Multiple raycasts: pass a list of rays, returns list of hits.
public QueryResult[] Raycast(List<Ray> rays, int filter, float maxDistance = 100, float rayThickness = 0)

Code:

// Single raycast: pass a single ray, returns whether it hit, and the hit result.
public bool Raycast(Ray ray, out QueryResult hitInfo, int filter, float maxDistance = 100, float rayThickness = 0)

QueryResult struct:

Code:

public Vector4 simplexBary;        /**< Barycentric coords of nearest point in simplex  */
public Vector4 queryPoint;        /**< Nearest point in query shape*/
public Vector4 normal;       /**< Closest direction between simplex and query shape. */
public float distance;         /** < distance between simplex and query shape.*/
public int simplexIndex;            /** < simplex index*/
public int queryIndex;               /** < query index*/

The code used in the above sample scene, to perform multiple raycasts in parallel:

Code:

using System.Collections.Generic;
using UnityEngine;
using Obi;

public class RaycastLasers : MonoBehaviour
{
    public ObiSolver solver;
    public LineRenderer[] lasers;

    List<Ray> rays = new List<Ray>();

    void Update()
    {
        rays.Clear();

        for (int i = 0; i < lasers.Length; ++i)
        {
            lasers[i].useWorldSpace = true;
            lasers[i].positionCount = 2;
            lasers[i].SetPosition(0, lasers[i].transform.position);
            rays.Add(new Ray(lasers[i].transform.position, lasers[i].transform.up));
        }

        int filter = ObiUtils.MakeFilter(ObiUtils.CollideWithEverything, 0);

        var results = solver.Raycast(rays, filter);

        if (results != null)
        {
            for (int i = 0; i < results.Length; ++i)
            {
                lasers[i].SetPosition(1, rays[i].GetPoint(results[i].distance));

                if (results[i].bodyA >= 0)
                {
                    lasers[i].startColor = Color.red;
                    lasers[i].endColor = Color.red;
                }
                else
                {
                    lasers[i].startColor = Color.blue;
                    lasers[i].endColor = Color.blue;
                }
            }
        }
    }
}

Using this API requires particle collisions to be enabled in the solver, otherwise the spatial structure used to perform collision queries (multilevel grid) isn't built. You can set particle collision iterations to zero if you only want queries, but no collisions.

Also, queries work both for regular particle-based collisions and surface-based collisions.

You can specify a ray thickness for raycasts. If the ray hits a simplex, it will return a point on the simplex. If it merely passes near the simplex (within its thickness distance, but no actual hit), it will return the point on the ray closest to the simplex surface.

Internally, this works by iterating trough all occupied cells in the simplex grid. For each cell, tests if the cell intersects the query shape's bounds. If it does, it iterates trough all simplices in the cell, calculating their distance to the query shape (using the same method used for collision detection). Pseudocode:

Code:

parallel foreach (query in queries)
{
   var bounds = calculateQueryBounds(query);
   foreach (occupiedCell in grid)
   {
        if (Intersects(bounds,cell))
        {
            foreach(simplex in occupiedCell)
                 AppendQueryResult(Result(query,simplex));
        }
   }
}

For raycasts I'm not using Bresenham/DDA algorithm as long rays would visit a lot of empty cells (tried it, not good). It's much cheaper to treat them like any other shape: iterate trough all cells we know to have any contents, and reject/accept them based on aabb.

[Hatchling]

For a raycast, I know you can approximate a point of impact by getting the closest point between the ray and a simplex. For example, you could get the closest point between a ray and line segment, and if the distance is less than the thickness of the ray + the thickness of the line segment, it is a hit, and the closest point on the ray is the hit point. But this isn't accurate; it shouldn't be the point of deepest penetration, but of first penetration, which requires a bit more weird math to compute. Are you using the approximate or exact method (or some other method) to calculate the hit point?

Also, I'm guessing the Bresenham algorithm is a way to enumerate through cells that intersect with a line. I'm guessing it intuitively just checks what face of a cell intersects with a line, and then navigates to the neighbor on the other side of that face, repeating until the end of the line or grid is reached. I think Wolfenstein did something similar to this to render their grid-based 2.5d worlds.
I can see this being slower than just enumerating through a small list of occupied cells, though it might be faster when there are a lot of them... which shouldn't happen too often (maybe it'd be more a problem with fluid?). (I can see this approach being especially costly when you have to also search neighbors when using a thick ray.)
I wonder what % of occupied cells would be required for the more complex enumeration to be worthwhile. ::thinkingface::
In any case, this is just food for thought. I'm sure this is plenty!

Regarding the collision-detection stuff needing to be enabled for raycasts to work (as otherwise the simplex grid isn't built), it might be a good idea to make note of that on the solver in the inspector, just for the sake of making it easier for future users. Perhaps name the collision module "Collision/Queries" and when unfolded, it shows a HelpBox() in there. *shrug*

---

Oh, and on a side note, I'm imagining how cool it'd be to have a level in a game where some of the walkable surfaces are cloth.  Like, a room with a tarp draped over a gigantic pit.(Though, I can see tunneling being an issue unless the cloth is especially thick.)