Poisson Disc Sampling Throws Index Out Of Range

Question

here's Poisson Disc Sampling Algorithm realization that I use:

using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;

namespace Assets.Scripts.Algorithms
{
    public static class PoissonDiscSampling
    {
        public static List<Vector2> GeneratePoints(int seed, float radius, Vector2 sampleRegionSize, int sampleAmount)
        {
            Random.InitState(seed);
            float cellSize = radius / Mathf.Sqrt(2);
            var grid = new int[Mathf.FloorToInt(sampleRegionSize.x / cellSize), Mathf.FloorToInt(sampleRegionSize.y / cellSize)];
            var points = new List<Vector2>();
            var spawnPoints = new List<Vector2>
            {
                sampleRegionSize / 2
            };

            while (spawnPoints.Count > 0)
            {
                int spawnIndex = Random.Range(0, spawnPoints.Count);
                Vector2 spawnCenter = spawnPoints[spawnIndex];
                bool accepted = false;

                for (int i = 0; i < sampleAmount; i++)
                {
                    float angle = Random.value * Mathf.PI * 2;
                    var direction = new Vector2(Mathf.Sin(angle), Mathf.Cos(angle));
                    Vector2 candidate = spawnCenter + direction * Random.Range(radius, radius * 2);

                    if (IsValid(candidate, sampleRegionSize, cellSize, radius, points, grid))
                    {
                        points.Add(candidate);
                        spawnPoints.Add(candidate);

                        grid[(int)(candidate.x / cellSize), (int)(candidate.y / cellSize)] = points.Count;

                        accepted = true;

                        break;
                    }
                }

                if (!accepted)
                {
                    spawnPoints.RemoveAt(spawnIndex);
                }
            }

            return points;
        }

        private static bool IsValid(Vector2 candidate, Vector2 sampleRegionSize, float cellSize, float radius,
            IList<Vector2> points, int[,] grid)
        {
            if (candidate.x >= 0 && candidate.x < sampleRegionSize.x && candidate.y >= 0 && candidate.y < sampleRegionSize.y)
            {
                int cellX = (int)(candidate.x / cellSize);
                int cellY = (int)(candidate.y / cellSize);
                int searchStartX = Mathf.Max(0, cellX - 2);
                int searchStartY = Mathf.Max(0, cellY - 2);
                int searchEndX = Mathf.Min(cellX + 2, grid.GetLength(0) - 1);
                int searchEndY = Mathf.Min(cellY + 2, grid.GetLength(1) - 1);

                for (int x = searchStartX; x <= searchEndX; x++)
                {
                    for (int y = searchStartY; y <= searchEndY; y++)
                    {
                        int pointIndex = grid[x, y] - 1;

                        if (pointIndex != -1)
                        {
                            float sqrDistance = (candidate - points[pointIndex]).sqrMagnitude;

                            if (sqrDistance < radius * radius)
                            {
                                return false;
                            }
                        }
                    }
                }
            }

            return true;
        }
    }
}

But there's a slight problem with this algorithm realization. On the line:

grid[(int)(candidate.x / cellSize), (int)(candidate.y / cellSize)] = points.Count;

After few iterations it throws

Index Out Of Range Exception

Somehow (I am still not sure why) It goes beyond the size of the grid, sometimes it can be negative and sometimes it can be basically equal the size of the grid.

I'm stuck and I don't know what to do. It seems that there's something that I simply don't see.

Thanks!

score 1 · Answer 1 · answered Jun 03 '20 at 19:00

Lets assume cellSize is 1 and sampleRegionSize.X is 10.9. This would result in a grid of size 10. candidate.X must be less than sampleRegionSize.X to be valid, but 10.8 would be fine. Cast it to int and you would end up with 10. Since arrays are zero indexed 10 will be out of range.

Moral of the story; do not trust floating point math. If you need to convert a floating point coordinate to an index, check that the index is valid before trying to use it. There are many articles on the dangers of floating point math.

Poisson Disc Sampling Throws Index Out Of Range

1 Answers1