A bug in 3DGUT's k-closest finding algorithm?

[lch01234]

In official 3DGUT implmentation, the anyhit program use a insertion sort to find k-closest hits. But, I think this algoritm will skip some hit if the traversal order is very discete. For example , if inserted hits is (3,21,20,22,8) and hit buffer has 3 slots, then it will be filled with (3,20,21), 8 is skipped. This will casuse inconsistant behaviour, am I misunderstand this algorithm or it’s a potential bug? The implementation : implementation

[nicolasm]

Thanks a lot for your question.

If the hit buffer (in this case the number of payload hit values) is too small to handle the k-closest hits, the raygen shader will initiate another trace starting from the last processed hit. Then every non-occluded hits should be processed in-order.

Please let me know if I misunderstood your question, and provide more details on potential failing case.

Thanks again.

[dhart]

Hi @lch01234,

The thing to keep in mind with the anyhit program is that reporting an intersection does not stop traversal, it simply limits the max t value that can be traversed and reported. This means that in your example (3,21,20,22,8) when K==3, the first 3 values are inserted to the hit buffer. After that when the value t=22 is encountered, it will not be inserted in the hit buffer, but instead a hit with t=22 is reported back to OptiX and this time the anyhit shader does not call optixIgnoreIntersection(). After this, traversal will continue until OptiX knows that there are no more hits with t < 22. When t=8 is encountered, since 8 < 22, the anyhit program will be called with t=8, and it will be inserted into the hit buffer. This will evict the value 21 from the hit buffer, and it will end up with (3,8,20) as long as there are no further hits.

The next ray will be launched from t=20, and it will re-traverse the hits (21, 22). Larger values for K can help minimize the amount of re-traversal, at the cost of additional live state, memory & compute used for sorting the hits, so there’s a balance point somewhere, but I believe the algorithm won’t skip any important hits.

–

David.

[lch01234]

Thank you so much David,

I see, optixIgnoreIntersection() only updates max t value, and the control will not return to calling function untill traversal is completed(By checking primitives inside the interval by tmin and tmax like other BVH traversal I guess). I thought it will return to calling function if optixIgnoreIntersection() is called, which confused me.

[dhart]

Aha I see. Right, calling optixIgnoreIntersection() doesn’t stop traversal either, it’s actually intended to do the opposite almost, to continue traversal and let you peek at all the intersections along the way.

This doesn’t matter for 3DGUT, but just for completeness, the way to stop anyhit from processing any more intersections is to call optixTerminateRay(). That function will record the current hit and proceed immediately to the closest-hit shader. So even this option doesn’t quite return to the calling function where optixTrace() or optixTraverse() was called. You could think of using optixTerminateRay() as maybe similar in spirit to using OPTIX_RAY_FLAG_TERMINATE_ON_FIRST_HIT but the terminate function is more flexible and the function can be used if you require the use of an anyhit shader, whereas the flag is more appropriate for testing occlusion in cases where you don’t want to use an anyhit shader.

–

David.