Find all integer grid points inside sphere

Questions & Answers
1

Given a position (Vector3) and a radius (float) of a sphere, how do I grab all integer coordinates inside the sphere?

My current solution was originally a inefficient hack to get radius = ~1 working, but now that the surrounding functionality is complete I am currently drawing blanks for how to tackle this seemingly simple problem.

public HashSet<Vector3> GetGridPoints(Vector3 pos, float radius = 0.87f) {
    HashSet<Vector3> gridPoints = new HashSet<Vector3>();
    int radiusCeil = Mathf.CeilToInt(radius);
    for (int i = -radiusCeil; i <= radiusCeil; i++) {
        for (int j = -radiusCeil; j <= radiusCeil; j++) {
            for (int k = -radiusCeil; k <= radiusCeil; k++) {
                Vector3 gridPoint = new Vector3(Mathf.Floor(pos.x + i),
                                                Mathf.Floor(pos.y + j),
                                                Mathf.Floor(pos.z + k));
                if (Vector3.Distance(pos, gridPoint) <= radius) {
                    gridPoints.Add(gridPoint);
                }
            }
        }
    }
    return gridPoints;
}
2

Uhm I don’t really see any issues with your code. The overall approach is totally fine. What you can do is avoid Vector3.Distance and just use

float distSqr = gridPoint.x*gridPoint.x + gridPoint.y*gridPoint.y + gridPoint.z*gridPoint.z;
if (distSqr < radiusSqr)
    gridPoints.Add(gridPoint);

Since you want integer coordinates you might want to replace your Vector3 by Vector3Int. While using floating point numbers for integer values work pretty well for relatively small values, you could get into issues when the values are getting large.

Note that instead of calculating the squared length of the vector manually you could use gridPoint.sqrMagnitude which does the same thing. However inlined it will be faster.

Finally a sphere has about ‭52.36% volume as it’s bounding box. So yes, you’re checking about twice the points you will need in the end. It’s possible to slightly adapt the ranges of the for loops to cut away the corners of the bounding cube. However that requires quite a bit of math and overhead so it probably won’t help you with performance.

Another possible improvement is your choice of data structure. The HashSet class unfortunately doesn’t have a way to set the internal capacity. For a large number of additions that would result in several resize operations which will require to move all already stored elements into a new array.

If you don’t really need a hashset you should switch to a List instead. There you can simply set the capacity ahead of time to something like this:

a = radiusCell*2+1;
capacity = (int)(a*a*a* 0.55f);

This should result in a slightly larger capacity than what you actually need so no resize should happen.

If you really need a hashset I’m just wondering for what purpose. If you just want to test if a point is inside that sphere it would be simpler to just store the center and radius and do the exact same test on the fly for the point you want to test.

Finally keep in mind that using Vector3 in a hashset is dangerous since a Vector3 consists of 3 floating point values. You will only find an match if all 3 values are exactly the same. Even the slightest variation would make it a different value. Therefore Vector3Int is highly recommended in such a case.