(It uses Processing for the implementation.)
\u2615 Support my Work:) \/ Coffee Supplier on Patreon<\/a><\/strong><\/p>\n\n\n\n
<\/p>\n\n\n\n
What is Spatial Partitioning?<\/h2>\n\n\n\n
Spatial partitioning is a technique that classifies objects into specific regions to reduce computational costs. Representative algorithms include:<\/p>\n\n\n\n
- \n
- Grid-based Partitioning<\/strong>: Divides space into a grid and assigns objects to each cell.<\/li>\n\n\n\n
- Quadtree<\/strong>: A data structure that recursively subdivides 2D space into four parts.<\/li>\n\n\n\n
- Octree<\/strong>: A data structure that recursively subdivides 3D space into eight parts.<\/li>\n<\/ul>\n\n\n\n
<\/p>\n\n\n\n
What is Grid-based Partitioning?<\/h2>\n\n\n\n
In grid-based partitioning, the simulation area is divided into cells of a specified size. Particles within each cell are managed in a list, and when calculating interactions between particles, only those in the target cell and its neighboring cells are considered. This approach reduces the number of calculations by focusing only on nearby particles, rather than all particles.<\/p>\n\n\n\n
1. Determining Cell Size<\/h3>\n\n\n\n
Deciding the cell size (cellSize) is one of the most crucial factors in spatial partitioning. If the cell size is too large, the calculation range becomes too broad, reducing efficiency. Conversely, if it’s too small, the number of cells increases, leading to higher management overhead.<\/p>\n\n\n\n
The cell size is determined based on MAX_DISTANCE (the maximum distance between particles). A suitable cellSize can be estimated using the following formula:<\/p>\n\n\n\n
\nint range = ceil(float(MAX_DISTANCE) \/ cellSize);\n<\/code><\/pre>\n\n\n\nMAX_DISTANCE<\/code><\/th>cellSize<\/code><\/th>MAX_DISTANCE \/ cellSize<\/code><\/th>range<\/code> \u306e\u7406\u60f3\u5024<\/th><\/tr><\/thead>100<\/td> 50<\/td> 2.0<\/td> ceil(2.0) = 2<\/code><\/td><\/tr>100<\/td> 100<\/td> 1.0<\/td> ceil(1.0) = 1<\/code><\/td><\/tr>100<\/td> 200<\/td> 0.5<\/td> ceil(0.5) = 1<\/code><\/td><\/tr>150<\/td> 50<\/td> 3.0<\/td> ceil(3.0) = 3<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<\/p>\n\n\n\n
2. Grid Structure<\/h3>\n\n\n\n
The grid is typically implemented as a two-dimensional array. The size of the array is determined by dividing the width and height of the simulation space by cellSize. Each cell contains a list of particles present in the corresponding area.<\/p>\n\n\n\n
\n\/\/ Creating the grid\ncols = width \/ cellSize;\nrows = height \/ cellSize;\ngrid = new ArrayList[rows][cols];\n\n\/\/ Adding particles to cells\nfor (int i = 0; i < MAX_PARTICLES; i++) {\n Particle p = new Particle();\n grid[int(p.pos.y \/ cellSize)][int(p.pos.x \/ cellSize)].add(p);\n}\n<\/code><\/pre>\n\n\n\n<\/p>\n\n\n\n
3. Neighbor Search<\/h3>\n\n\n\n
The advantage of spatial partitioning becomes evident when calculating interactions between particles. Each particle searches only its own cell and the surrounding cells. The search range is determined based on the previously set range. If range is 1, the particle examines its own cell and the surrounding eight cells.<\/p>\n\n\n\n\n\n
In the above code, by using range, the particle searches its own cell and neighboring cells, interacting only with nearby particles.<\/p>\n\n\n\n
<\/p>\n\n\n\n
4. Advantages and Disadvantages<\/h2>\n\n\n\n
Advantages<\/h3>\n\n\n\n
- \n
- Reduction in Computation<\/strong>: By focusing only on particles in nearby cells instead of comparing all particles, computational load is significantly reduced.<\/li>\n\n\n\n
- Scalability<\/strong>: Even as the number of particles increases, the computational load does not increase drastically.<\/li>\n\n\n\n
- Efficient Memory Management<\/strong>: Managing particles by cell improves memory utilization efficiency.<\/li>\n<\/ul>\n\n\n\n
Disadvantages<\/h3>\n\n\n\n
- \n
- Overhead in Cell Management<\/strong>: There is a certain overhead in managing cells, especially when the cell size is small or the simulation space is large.<\/li>\n\n\n\n
- Balance in Spatial Partitioning<\/strong>: If the cell size is not set appropriately, the method may not function efficiently.<\/li>\n<\/ul>\n\n\n\n
5. Optimization Points<\/h2>\n\n\n\n
- \n
- Optimizing Cell Size<\/strong>: By appropriately setting cellSize based on MAX_DISTANCE, computational load can be minimized.<\/li>\n\n\n\n
- Adjusting Search Range<\/strong>: By adjusting the value of range, the number of cells to be calculated can be controlled, further reducing computational load.<\/li>\n\n\n\n
- Considering Parallelization<\/strong>: Since the calculation of interactions between particles is independent, utilizing parallel processing (e.g., leveraging the GPU) can achieve further speed improvements.<\/li>\n<\/ul>\n\n\n\n
Comparison<\/h2>\n\n\n\n
Below is a comparison between cases without and with spatial partitioning, showing the frame rate when running with 10,000 particles.<\/p>\n\n\n\n
- Adjusting Search Range<\/strong>: By adjusting the value of range, the number of cells to be calculated can be controlled, further reducing computational load.<\/li>\n\n\n\n
- Balance in Spatial Partitioning<\/strong>: If the cell size is not set appropriately, the method may not function efficiently.<\/li>\n<\/ul>\n\n\n\n
- Scalability<\/strong>: Even as the number of particles increases, the computational load does not increase drastically.<\/li>\n\n\n\n
- Quadtree<\/strong>: A data structure that recursively subdivides 2D space into four parts.<\/li>\n\n\n\n
![\"\"](\"https:\/\/barbegenerativediary.com\/en\/wp-content\/uploads\/2025\/02\/250209-Grid-based-Partitioning1.webp\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/barbegenerativediary.com\/en\/wp-content\/uploads\/2025\/02\/250209-Grid-based-Partitioning2.webp\")
<\/figure>\n\n\n\n![\"Grid-Systems-Raster-Systeme\"](\"https:\/\/barbegenerativediary.com\/en\/wp-content\/uploads\/2023\/06\/Grid-Systems-Raster-Systeme.webp\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/barbegenerativediary.com\/en\/wp-content\/uploads\/2024\/07\/240801_bandcamp-top-BGD_SOUNDS.webp\")
<\/figure>\n","protected":false},"excerpt":{"rendered":"