RaycastNonAlloc sort collision from furthest to closest?

So this has been an issue for a while now (since at least 2017.3 irrc) and it's getting quite cumbersome as it means I can never actually be sure that using RaycastNonAlloc with an RaycastHit[1] sized array will actually hit the thing I expect it to. As a result I often have to supply a much larger buffer than I need followed by a squared distance comparison to find the collision I'm actually interested in.

Up until now, I had assumed this was just intentional behavior for optimization reasons, but I recently found a conversation here https://answers.unity.com/questions/1240670/raycastnonalloc-return-value-ordering.html, where @MelvMay suggest that this is not how RaycastNonAlloc works. Apparently, they should in fact be ordered from closest to furthest.

I can confirm absolutely that sorting does not always work this way. It's been an issue that I've had to solve on many occasions now because I keep forgetting about it until some unexpected bug pops up due to lack of sorting functionality implemented in my own code.

I've posted a video on youtube to demonstrate this bug manifested in my most recent feature. It's a fairly simple system of rendering blobw shadows by using Raycasts to detect where they should be placed. What I find most strange about this particular case is that you can clearly see the sorting changes order based on where the raycast strikes the box collider. This makes me think that sorting might somehow be based on the central pivot of the collider it is striking?

https://www.youtube.com/watch?v=r1XgF3rXrpc

https://docs.unity3d.com/ScriptReference/Physics.RaycastNonAlloc.html
[quote]
Like Physics.RaycastAll, but generates no garbage.
[/quote]

https://docs.unity3d.com/ScriptReference/Physics.RaycastAll.html
[quote]
Casts a ray through the scene and returns all hits. Note that order is not guaranteed.
[/quote]

BTW, do you mind if I ask why do you use this function at all? In the video you absolutely don't use the main feature of this solution: multiple hits. You only care about the closest hit, which the simple Physics.Raycast does with the out hit parameter. So why not use that?

2 Likes

[quote]
https://docs.unity3d.com/ScriptReference/Physics.RaycastNonAlloc.html

https://docs.unity3d.com/ScriptReference/Physics.RaycastAll.html

BTW, do you mind if I ask why do you use this function at all? In the video you absolutely don't use the main feature of this solution: multiple hits. You only care about the closest hit, which the simple Physics.Raycast does with the out hit parameter. So why not use that?
[/quote]

Indeed, as I stated before I just assumed that sorting order wasn't guaranteed - until I read that particular post on Unity Answers. Regardless of whether or not it is, it seems odd that the results returned wouldn't be ordered. I mean, if there is no ordering then the only way you could ever ensure that the correct object is found would be to provide an array that is the maximum size of objects you'd ever expect to be hit and then sort through it every time. That seems silly to me, especially when in ninety-nine percent of all cases I'm sure people would only want the very first thing that was hit. The closest thing. I suppose for the sake of optimization it might be necessary though.

Really the whole thing might be moot though because...

The reason I've been using the multi-hit version was due to the fact that in the past the single-hit version produced garbage for a time (Unless it was just me being a dummy and not profiling outside of the editor. It was a long time ago). Admittedly, I haven't tested it in a long time so I went ahead and did that now. It does indeed appear to be garbage-free again so yeah... now I feel a little silly. I guess I can go back to using that one again.

[quote=“Sluggy1”, post:3, topic: 722697]
until I read that particular post on Unity Answers
[/quote]
I would always believe in the documentation more than in a guy on a site no matter what. Especially if the documentation explicit says something.

[quote=“Sluggy1”, post:3, topic: 722697]
it seems odd that the results returned wouldn’t be ordered
[/quote]
Actually that’s not odd at all. If you don’t care about order, you get the list of things you hit. So you get away with less work. If you need order, you can order for yourself. Less work mean faster, more efficient application. I’m with Unity on this one.

[quote=“Sluggy1”, post:3, topic: 722697]
the only way you could ever ensure that the correct object is found would be to provide an array that is the maximum size of objects you’d ever expect to be hit and then sort through it every time. That seems silly to me, especially when in ninety-nine percent of all cases I’m sure people would only want the very first thing that was hit. The closest thing. I suppose for the sake of optimization it might be necessary though.
[/quote]
That’s what the RayCast method is for. So it should not be repeated in the multi-hit version.

1 Like

[quote]
I would always believe in the documentation more than in a guy on a site no matter what. Especially if the documentation explicit says something.
[/quote]
Oh come now, I'd hardly call MelvMay 'a guy on a website' ;)

In all seriousness though, it's a pretty common thing that the documentation says one thing and a Unity Technologies person says another. And there have been cases in the past where both have been wrong, outdated, or some way not congruent with reality (even if it's just due to a bug).

All in the all, the problem appears to be solved so I'm glad for that. It only took about... looks at watch two years? But hey, at least it all works as the documentation says it should now! :smile: Thanks for hint. I might never have actually considered using the single-hit Raycast again had you not mentioned it. I honestly forgot it even existed hahaha!

4 Likes

[quote=“Sluggy1”, post:5, topic: 722697]
Oh come now, I’d hardly call MelvMay ‘a guy on a website’ :wink:

In all seriousness though, it’s a pretty common thing that the documentation says one thing and a Unity Technologies person says another. And there have been cases in the past where both have been wrong, outdated, or some way not congruent with reality (even if it’s just due to a bug).

All in the all, the problem appears to be solved so I’m glad for that. It only took about… looks at watch two years? But hey, at least it all works as the documentation says it should now! :smile: Thanks for hint. I might never have actually considered using the single-hit Raycast again had you not mentioned it. I honestly forgot it even existed hahaha!
[/quote]
In this case, maybe both are right. MelvMay (pardon my ignorance I don’t really know the 2D world, so I don’t really know who we are talking about either) talked about Physics2D and in that case it is sorted: https://docs.unity3d.com/ScriptReference/Physics2D.RaycastAll.html

But we were talking about (and also the video were in) 3D. Where it isn’t sorted.

1 Like

All 2D physics queries that return distance are sorted, always have been. In that link you referred to it was talking explicitly about 2D physics. I don’t think the 3D ones are as is stated in the docs but I could look through the source to find out.

AFAIK the Physics.Raycast with the signature:

 public static bool Raycast(Vector3 origin, Vector3 direction, out RaycastHit hitInfo, float maxDistance, int layerMask, QueryTriggerInteraction queryTriggerInteraction);

returns the first hit only.

[quote=“Sluggy1”, post:5, topic: 722697]
All in the all, the problem appears to be solved so I’m glad for that. It only took about… looks at watch two years?
[/quote]
I’m curious, what took two years? AFAIK it’s always been like the above but maybe my memory fails me.

1 Like

[quote=“MelvMay”, post:7, topic: 722697]
I’m curious, what took two years? AFAIK it’s always been like the above but maybe my memory fails me.
[/quote]
Specifically I was refering to the garbage generated by the single-hit raycast. This was introduced sometime in Unity 5 but has apparently been fixed since then. I recal discovering this at some point and consequently replacing all versions of the single-hit with the non-allocating multi-hit in my code. It’s just become such a habit that I never thought to look back.

Silly me for not realizing that was the 2D physics. I didn’t notice ‘2D’ in the function prototypes in the title so I just assumed 3D.

1 Like

I’m not aware of any old GC-alloc bugs in that function as it returns a struct so very odd but glad you are okay using it now.

I'am in Unity 2018.3, but the implementation is the worse case. I can live with the order:

int rayCastRet = Physics.RaycastNonAlloc(ray, results, 500, HitThisLayers);
            if (rayCastRet == 0) {
                return;
            }

            Array.Sort(results, delegate(RaycastHit hit1, RaycastHit hit2) { return hit1.distance.CompareTo(hit2.distance); } );

But not that the first 'n' hits are not in the array. I see no use in this method. A better way would be to use single raycast, remember the position, and make a new raycast and so on. DO NOT USE THIS "RaycastNonAlloc" and RaycastNon!!! Dear Unity team, I would recommend to deprecate and remove it later, or implement it correctly.

[quote=“mkgame”, post:10, topic: 722697]
But not that the first ‘n’ hits are not in the array. I see no use in this method. A better way would be to use single raycast, remember the position, and make a new raycast and so on. DO NOT USE THIS “RaycastNonAlloc” and RaycastNon!!! Dear Unity team, I would recommend to deprecate and remove it later, or implement it correctly.
[/quote]
It would help if you could be clear on exactly what problem you’re having.

[quote=“mkgame”, post:10, topic: 722697]
But not that the first ‘n’ hits are not in the array.
[/quote]
You’re saying that you’re missing hits? If so, have you created a bug report or have a repro case that can be passed along to the 3D physics team? (I’m not in that team btw). Note that if this is the case, it’s also off-topic from the thread.

For eg. if I set the RaycastHit array to a length of 2, and I have about 8 colliders that can be hit, then in this case the RaycastAll method returns non determined 2 of the 8 collider hits, not the first and the second closest.

I already implemented a solution, sorted and returns the closests first. It also has a stop layer mask for optimization (eg. stop after hitting the terrain or water layer):

        public static int RaycastAllNonAlloc(Ray ray, RaycastHit[] hits, float range, LayerMask HitLayers, LayerMask StopLayers) {
            int maxHits = hits.Length;
            if (maxHits == 0) {
                Debug.LogError("This RaycastAll makes no sense with empty hits array.");
                return 0;
            }

            int index = 0;
            while (Physics.Raycast(ray, out hits[index], range, HitLayers)) {
                if ((1 << hits[index].collider.gameObject.layer & StopLayers.value) > 0) {
                    index++;
                    break;
                }

                range = range - Vector3.Distance(ray.origin, hits[index].point);
                ray.origin = hits[index].point + ray.direction * 0.001f;
                if (range <= 0) {
                    index++;
                    break;
                }

                index++;

                if (index == maxHits) {
                    break;
                }
            }

            return index;
        }

For the c++ compiler the loop should be a for loop, else the CPU cannot process the branches in different pipelines.

Yes, that's because the results are not sorted in 3D. The idea with the non-alloc stuff is that you provide an array large enough and reuse it. They'll probably add List support at some point same as 2D physics.

A list based container for RaycastAll woud be better, but as I know, RaycastAll already returns all the RaycastHits. In case of RaycastNonAlloc it must be an array. RaycastNonAlloc has the advantage, that by the array length the max number of RaycastHits is defined and it doesn't allocate memory on the heap additionally. If the RaycastNonAlloc would hit too much colliders, then the limitation of RaycastHits could save the FPS.

[quote=“mkgame”, post:14, topic: 722697]
A list based container for RaycastAll woud be better, but as I know, RaycastAll already returns all the RaycastHits. In case of RaycastNonAlloc it must be an array. RaycastNonAlloc has the advantage, that by the array length the max number of RaycastHits is defined and it doesn’t allocate memory on the heap additionally.
[/quote]
I’m not sure you’re following what I meant. The difference is that RaycastAll creates a list for you whereas the lists-based ones I was referring to in 2D physics allow you to pass/reuse your own list as an argument meaning they don’t allocate e.g. Physics2D.Raycast.

Passing an array limits you to the size of the array and you have to create one large enough for all results but you don’t know if you exceeded it and results were dropped.

[quote=“MelvMay”, post:15, topic: 722697]
I’m not sure you’re following what I meant. The difference is that RaycastAll creates a list for you whereas the lists-based ones I was referring to in 2D physics allow you to pass/reuse your own list as an argument meaning they don’t allocate e.g. Physics2D.Raycast.

Passing an array limits you to the size of the array and you have to create one large enough for all results but you don’t know if you exceeded it and results were dropped.
[/quote]

If you add a new RaycastHit to the list, then the RaycastHit must be created, the default constructor will be called. In case of a pre-instantiated RaycastHit in an array, the RaycastHit must not be instantiated, just values must be assigned, like ‘point’, ‘collider’. I don’t know how this has been implemented, but this is the only one way how this can work as non allocating.

[quote=“mkgame”, post:16, topic: 722697]
If you add a new RaycastHit to the list, then the RaycastHit must be created, the default constructor will be called. In case of a pre-instantiated RaycastHit in an array, the RaycastHit must not be instantiated, just values must be assigned, like ‘point’, ‘collider’. I don’t know how this has been implemented, but this is the only one way how this can work as non allocating.
[/quote]
Whilst you didn’t ask a question and I’m not sure I exactly follow what you’re getting at maybe just saying that all the non-allocating calls all return the number of hits populated in the array as a return value helps. Only those ones will be fully initialised. Any others are undefined and may still be left as they were if previously used.

In other words, if you pass an array with 1000 elements and the return value is 3 then only those 3 will be fully populated. I know there was a bug previously where the whole array was reset by the script binding system which cause massive CPU spikes if you passed very large arrays but that was fixed (it affect both 2D & 3D because it was a common script binding issue). Now the remaining items in the array beyond the result count are left untouched.

[quote=“MelvMay”, post:17, topic: 722697]
Whilst you didn’t ask a question and I’m not sure I exactly follow what you’re getting at maybe just saying that all the non-allocating calls all return the number of hits populated in the array as a return value helps. Only those ones will be fully initialised. Any others are undefined and may still be left as they were if previously used.

In other words, if you pass an array with 1000 elements and the return value is 3 then only those 3 will be fully populated. I know there was a bug previously where the whole array was reset by the script binding system which cause massive CPU spikes if you passed very large arrays but that was fixed (it affect both 2D & 3D because it was a common script binding issue). Now the remaining items in the array beyond the result count are left untouched.
[/quote]

I agree, the only one thing I wanted to tell is, that c# List will always allocate memory on the heap and that the signature of the RaycastNonAlloc is fine, but not the result. I also agree with RaycastAll, that returns an Array yet, could return in the future a List. I would also recommend to introduce a Stop-Mask, because why not use the fast mask/layer check to limit the raycast checks.
However, I’am happy with the short funktion I posted here, and I’am pretty sure, that I will not use the built in RaycastAll methods at all, because of the strange results.

[quote=“mkgame”, post:18, topic: 722697]
However, I’am happy with the short funktion I posted here, and I’am pretty sure, that I will not use the built in RaycastAll methods at all, because of the strange results.
[/quote]
What strange results? It’s not clear from what you’ve posted what exactly is wrong.

All 2D physics queries in 2019.1 now allow you to pass a List to be populated.

[quote=“mkgame”, post:18, topic: 722697]
I would also recommend to introduce a Stop-Mask, because why not use the fast mask/layer check to limit the raycast checks
[/quote]
Physics queries already have this. You specify the layer-mask to select which items you want.

[quote=“MelvMay”, post:19, topic: 722697]
What strange results? It’s not clear from what you’ve posted what exactly is wrong.

All 2D physics queries in 2019.1 now allow you to pass a List to be populated.

Physics queries already have this. You specify the layer-mask to select which items you want.
[/quote]

This post is about sorting order for 3D raycasts. I read the first comments and read the title. My comments belongs to this post. I’m not interested in the 2D raycast version, for that maybe a new post shoud be made.

The 3D version for RaycastAll and RaycastNonAlloc provides strange results, non sorted and not the first hits, if the buffer is limited in the non alloc raycast.

A stop mask would simply break and he loop for performance reasons in my implementation, not sure how Unity implementation could use it.