How to split 3d grid into regions

What formula can I use to create regions in a 3d grid?

Imagine a rubix cube. The cube as a whole is the entire 3d grid, and each mini cube is a region represented by an id.

The grid will be uniform, as well as the regions.
So for example, lets say the max grid size would be 100 x 100 x 100 (50 in positive and 50 in negative) and each region is 10 x 10 x 10.
What formula can I use to determine which region I am in based on my vector3?

I will also need to know what values that region represents.
So, for example, lets say I am given the region id of 5, I need to be able to reverse the formula to be given the min x y z vector (I can calculate the max based on the min).

The result will need to be consistent.
Any help is appreciated!

 

Look up octtrees. They are good for storing this data and accessing it.

 

Well, I already have something like this code below, but what I am asking for is if there is some kind of formula that just does this all instead of needing to manually create the ids, vectors, etc...

Its more of a curious question.

The code below has not been tested a lot, so watch out for bugs.

Spoiler: Click for code

Code (CSharp):

1. using System;
2. using UnityEngine;
3. using System.Collections.Generic;
4.  
5. public class CubeGridRegions
6. {
7.     public Vector3 origin {get; private set;}
8.     public Vector3 gridSize {get; private set;}
9.     public float regionSize {get; private set;}
10.     Dictionary<int, Vector3> regionIdToVector;
11.     Dictionary<Vector3, int> vectorToRegionId;
12.  
13.     public CubeGridRegions(int cubicMaxRegions, float regionSize) {CreateCubeGrid(cubicMaxRegions, regionSize);}
14.     public CubeGridRegions(Vector3 gridSize, float regionSize) : this(Vector3.zero, gridSize, regionSize){}
15.     public CubeGridRegions(Vector3 origin, Vector3 gridSize, float regionSize) {CreateCubeGrid(origin, gridSize, regionSize);}
16.  
17.     public void CreateCubeGrid(int cubicMaxRegions, float regionSize)
18.     {
19.         Vector3 uniformedCubicVector = Vector3.one * Mathf.Floor(ExtMathf.CubicRoot(cubicMaxRegions));
20.         CreateCubeGrid(Vector3.zero, uniformedCubicVector, regionSize);
21.     }
22.     public void CreateCubeGrid(Vector3 gridSize, float regionSize) {CreateCubeGrid(Vector3.zero, gridSize, regionSize);}
23.     public void CreateCubeGrid(Vector3 origin, Vector3 gridSize, float regionSize)
24.     {
25.         AssignVariables(origin, gridSize, regionSize);
26.  
27.         Vector3 originBottomCorner = (origin - (gridSize * regionSize)) / 2f;
28.  
29.         int id = 0;
30.         for(int i = 0; i < gridSize.x; i++)
31.         {
32.             for(int j = 0; j < gridSize.y; j++)
33.             {
34.                 for(int k = 0; k < gridSize.z; k++)
35.                 {
36.                     Vector3 regionCornerVector = originBottomCorner + (new Vector3(i, j, k) * regionSize);
37.  
38.                     //remember to remove this.
39.                     Debug.DrawRay(regionCornerVector, Vector3.up * regionSize, Color.magenta, Mathf.Infinity);
40.                     Debug.DrawRay(regionCornerVector, Vector3.right * regionSize, Color.magenta, Mathf.Infinity);
41.                     Debug.DrawRay(regionCornerVector, Vector3.forward * regionSize, Color.magenta, Mathf.Infinity);
42.  
43.                     regionIdToVector.Add(id, regionCornerVector);
44.                     vectorToRegionId.Add(regionCornerVector, id);
45.                    
46.                     id++;
47.                 }
48.             }
49.         }
50.     }
51.  
52.     public Vector3 RegionIdToVector(int id)
53.     {
54.         return regionIdToVector[id];
55.     }
56.  
57.     public int VectorToRegionId(Vector3 vector)
58.     {
59.         Vector3 vectorRegionValue = vector / regionSize;
60.         return vectorToRegionId[ExtVector3.Floor(vectorRegionValue) * regionSize];
61.     }
62.  
63.     void AssignVariables(Vector3 origin, Vector3 gridSize, float regionSize)
64.     {
65.         regionIdToVector = new Dictionary<int, Vector3>();
66.         vectorToRegionId = new Dictionary<Vector3, int>();
67.         this.origin = origin;
68.         this.gridSize = gridSize;
69.         this.regionSize = regionSize;
70.     }
71. }

 

Divide your position by 10 and cast it to int

 

This is what I see
5 5 5 = .5 .5 .5 = 0 0 0
-5 -5 -5 = -.5 -.5 -.5 = 0 0 0
15 0 15 = 1.5 0 1.5 = 1 0 1
56 89 20 = 5.6 8.9 2 = 5 8 2

Is 000, 101 and 582 the id?

I wasnt to detailed in terms of what I need. Ids must be unique, not negative and must not be greater than the number of regions.
So if I have 100 regions, there cant be an id of 582 as a result of a formula.

Your method is similar to what I am doing in the code I posted above "VectorToRegionId(Vector3 vector)"
The reason the numbers must not be negative and within a limit is due to networking reasons.
Unless if you meant something else by casting to an int. Is there a way to get a single id as I desire?

 

You got what I mean but but I would not work with negative numbers or in this case add 50 to each vector to get a range from 0-100 then you have 1000 regions the first one is from 0-10 in each direction the last from 90-100.

To get some usefull id you could make a second array[10,10,10] and then check it for its value/Id.

So for example current id = array[(int)posX/10,(int)posY/10,(int)posZ/10]

But you still have to set the Ids first ...

 

I think what Pavlon was doing was dividing by 10 to bring the grid back into a scale of 1.

your grid is 100 and each section is at a scale of 10? You also have another issue which is that your system starts at -50 -> + 50 which is not a problem but needs to be considered.

When calculating the grid index you need to offset the grid into the positive axis on all 3 axis. e.g. xOffset = 50 * 10 (max negative position multiplied by scale)

So your index is position + xOffset divided the scale (10) to bring into a scale of 1. Then divide the position grid size (100) to get the grid index.

You will need to check that you are inside the grid size... so either clamp output between 0 - 99 or dont bother calculating if your outside of the bounds.

Hope this helps!

 

(I haven't tested this code, but should give you the general idea)
To generate the IDs, I would treat it as though you're indexing into a 1D representation of a 3D grid:

Code (CSharp):

1. int gridID = (zIndex * (xCount * yCount)) + (yIndex * xCount) + xIndex;

And then to find the x, y, z indices from a vector, you want to "move" the grid so that the (0, 0, 0) grid cell starts at the origin, to make make the math easier. Then:

Code (CSharp):

1. Vector3 pos = new Vector3(...);
2. Vector3 gridOriginOffet = new Vector3(50, 50, 50);
3. Vector3 newPos = pos + gridOriginOffset;
4. int xIndex = Mathf.FloorToInt(newPos.x / 10);
5. int yIndex = Mathf.FloorToInt(newPos.y / 10);
6. int zIndex = Mathf.FloorToInt(newPos.z / 10);

And from there you can use the calculation above to get the ID.

To go from ID back to vector, you basically do the math in reverse:

Code (CSharp):

1. int xIndex = gridID - ((zIndex * (xCount * yCount)) + (yIndex * xCount));

etc...

Then you can calculate the vector from the indices:

Code (CSharp):

1. Vector3 offsetPos = new Vector3(xIndex * 10.0f, yIndex * 10.0f, zIndex * 10.0f);
2. Vector3 finalPos = offsetPos - gridOriginOffset;

That'll give you the min position of the grid cell. You can get the max pos by adding Vector3(10, 10, 10);

Like I said, I haven't double-checked all the math, but it should point you in the general direction.

Owen

 

Im assuming the Ids I get from that code will be large numbers though?

The general idea I am getting from you guys is...
Offset the grid so there are no negatives
divide by the regions size and floor the value
Take that new value and just merge it (not add) together into a single int.

Even though its not something I can use in my case due to requiring tight values, it does seem like you can avoid assigning ids and doing loops as I was originally doing.

I appreciate the feedback! =)

 

That code should return you IDs in the range [0, numberOfGridCells-1]. So if you have a 10x10x10 grid, you'll have 1000 cells. That code should return you a value between 0 and 999.

Owen

 

Ah yes, I was looking at it wrong.
I think that line of code is basically the formula I was looking for, thought I did not test it a lot.

Ill probably still stick to the method I already have since it doesnt need to keep calculating, though your way might be better in regards to avoiding a key not found for my dictionary. Ill have to decide =)

Thank you!