koobas.hobune.stream
Find all integer grid points inside sphere
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;
}
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.
Wow, Vector3Int is a thing apparently. That's going to make my life so much easier, lots of happy refactoring to do now.
I chose HashSet because I saw performance analysis in various threads/posts that it out-performs at larger index sizes. $$anonymous$$aybe I can do a few tests for my own situation and try out your capacity recommendation as well.
The main purpose of this post was to ensure I wasn't missing something stupidly obvious like a built-in function or easy math to iterate over a defined int grid (besides a cubed for-loop, which as you mentioned the 48% loss). Thanks for all the help/suggestions!
Edit: Vector3Int.forward doesn't exist? Neat.
No, HashSet will be as slow as an default sized List if not slower when it comes to adding elements. As you can read over here:
If Count already equals the capacity of the
HashSet<T>object, the capacity is automatically adjusted to accommodate the new item.If Count is less than the capacity of the internal array, this method is an O(1) operation. If the
HashSet<T>object must be resized, this method becomes an O(n) operation, where n is Count.
That behaviour is similar to List but with a List you can actually preallocate the memory (If you know how much you're going to need). Also note that most collections will simply double the capacity when it runs out of space. So typical default values are 4 or 8 elements. That means after every power of two elements the old internal array would be thrown away (up for garbage collection) and a new one with double the size would be allocated. So if for example "radiusCeil" is 5 (an 11x11x11 area) the sphere would contain roughly 697 points. So the structure would need to grow to 8,16,32,64,128,256,512 and finally to 1024. When you set the capacity to 11²*0.55 == 732 to begin with all points should fit inside that structure.
Note that a HashSet is there to represent the mathematical concept of a set. You only want to use such a structure when you want to perform set operations like a testing of a certain value exists in the set. If you don't need this there's no point in using a HashSet. As I said If you need to test somewhere else if a certain point is in the sphere, you can simply use the same math you used to create your hash set on the fly.
Yes Vector3Int does not have a forward property. Actually the Vector3 forward property is a bit slower than just using new Vector3(0,0,1) Actually Vector3.forward is just 3 characters shorter so not a huge benefit. Yes it's slightly more readable but not really necessary.
