OutOfBound value in BinarySearch (CotegoricalParameter with custom probabilities)

[nicoarnaise]

Hello, I've got an out of bounds value error on selecting a foreground object with custom probabilities. I think the issue comes from this line : https://github.com/Unity-Technologies/com.unity.perception/blob/fa182305196025965c4fd7aa501e9b7bb7c04f5e/com.unity.perception/Runtime/Randomization/Parameters/CategoricalParameter.cs#L159 After trying to reproduce what is described, I still don't get why it should be ++mid and not just mid ? When the key is exactly 1.0 (what may happen), return ++mid will return m_NormalizedProbabilities.Length which is an out of bound value. Did I understand well or is there something I didn't get ? Kind regards, Nicolas

[nicoarnaise]

Well I may have missed something because the error still occurs with this change. I've clamped the returned values between 0 and m_NormalizedProbabilities.Length - 1 to make sure it solves the issue, but it's not really a clean fix ^^'

[aryan-mann]

Hey @nicoarnaise, thanks for reporting it 👍 I'll take a look and update this thread when I have a resolution. Do you have a case that can reproduce this? From what I gather, seems like just having one element with 1.0 probability might be one.

[nicoarnaise]

The bug happens at iteration ~17000 with seed 539662031 in a Fixed Length Scenario with 8 prefabs in a ForegroundObjectPlacementRandomizer with 0.3 for the first prefab and 0.1 for the other. I'll try reproduce it with a smaller config.

[nicoarnaise]

1. Create a HDRP projet
2. Add this MonoBehaviour to a GameObject :

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

public class TestBinarySearch : MonoBehaviour
{
    public List<float> probabilities;
    public float key;
    float[] m_NormalizedProbabilities;

    // Update is called once per frame
    void Update()
    {
        if (probabilities.Count > 0)
        {
            NormalizeProbabilities();
            Debug.Log(BinarySearch(key));
        }
    }

    void NormalizeProbabilities()
    {
        var totalProbability = 0f;
        for (var i = 0; i < probabilities.Count; i++)
        {
            var probability = probabilities[i];
            if (probability < 0f)
                throw new ParameterValidationException($"Found negative probability at index {i}");
            totalProbability += probability;
        }

        if (totalProbability <= 0f)
            throw new ParameterValidationException("Total probability must be greater than 0");

        var sum = 0f;
        m_NormalizedProbabilities = new float[probabilities.Count];
        for (var i = 0; i < probabilities.Count; i++)
        {
            sum += probabilities[i] / totalProbability;
            m_NormalizedProbabilities[i] = sum;
        }
    }

    int BinarySearch(float key)
    {
        var minNum = 0;
        var maxNum = m_NormalizedProbabilities.Length - 1;

        while (minNum <= maxNum)
        {
            var mid = (minNum + maxNum) / 2;
            // ReSharper disable once CompareOfFloatsByEqualityOperator
            if (key == m_NormalizedProbabilities[mid])
            {
                return ++mid;
            }
            if (key < m_NormalizedProbabilities[mid])
            {
                maxNum = mid - 1;
            }
            else
            {
                minNum = mid + 1;
            }
        }
        return minNum;
    }

    class ParameterValidationException : Exception
    {
        public ParameterValidationException(string msg) : base(msg) { }
        public ParameterValidationException(string msg, Exception innerException) : base(msg, innerException) { }
    }
}

3. Add at least one probability, whatever the values
4. Set the key value to 1
5. You'll see in logs (after pressing play button) that BinarySearch returns len(probabilities) when key = 1.0

[aryan-mann]

Thanks a lot @nicoarnaise for the steps for reproduction. I'll add this to our backlog and update this thread when we have a resolution!

[RuiyuZ]

Thanks @noahjnichols for the detailed reproduction guide! the fix on this error will be included in the next release of the perception package. For now, can you try to replace the binary search https://github.com/Unity-Technologies/com.unity.perception/blob/fa182305196025965c4fd7aa501e9b7bb7c04f5e/com.unity.perception/Runtime/Randomization/Parameters/CategoricalParameter.cs#L151 with the following script and see if that fixes the issue?

        int BinarySearch(float key)
        {
            var minNum = 0;
            var maxNum = m_NormalizedProbabilities.Length - 1;

            while (minNum <= maxNum)
            {
                var mid = minNum + (maxNum - minNum) / 2;
                // ReSharper disable once CompareOfFloatsByEqualityOperator
                if (key == m_NormalizedProbabilities[mid])
                {
                    return mid;
                }
                if (key < m_NormalizedProbabilities[mid])
                {
                    maxNum = mid - 1;
                }
                else
                {
                    minNum = mid + 1;
                }
            }

            //when the minNum exceeds the length of input array, return last index
            if (minNum >= m_NormalizedProbabilities.Length)
            {
                return m_NormalizedProbabilities.Length - 1;
            }
            return minNum;
        }

[aryan-mann]

Hey @nicoarnaise, we just released 🎉 Perception 1.0 🎉, a major update to the toolset (more details here: Perception 1.0: Expanding the Open Source Toolbox for Synthetic Data)! This should be fixed in the newest release which is out right now.

Closing this for now, feel free to open it back up if there are any issues.