-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
106 lines (92 loc) · 5.7 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
<!DOCTYPE html>
<html lang="en" dir="ltr">
<head>
<meta charset="utf-8">
<title>Spatial Hashing Demo</title>
<!-- MOBILE––––––––––––––––––––––– -->
<meta name="viewport" content="width=device-width, initial-scale=1">
<link href="https://api.fonts.coollabs.io/css2?family=Raleway:wght@300;400;600&display=swap" rel="stylesheet">
<!-- CSS––––––––––––––––––––––– -->
<link rel="stylesheet" href="css/normalize.css">
<link rel="stylesheet" href="css/skeleton.css">
<link rel="stylesheet" href="css/darkskelleton.css" media="(prefers-color-scheme: dark)">
<link rel="stylesheet" href="css/style.css">
<meta name="description" content="A simple demo of the spatial hashing algorithm for physics simulations">
</head>
<body>
<div class="container">
<a href="/">Back to Home</a>
<div class="row" style="margin-top:3rem;">
<article class="column">
<h1>Spatial Hashing Demo</h1>
<p>
A demo of spatial hashing for physics simulations. In this example the algorithm is used to reduce the number of
collision checks per frame, by dividing the world into a grid of cells, and then only checking for collisions between objects that are in the same cell.
</p>
<canvas class="u-full-width" id="canvas" width="800" height="800"></canvas>
</article>
</div>
<hr>
<div class="row">
<div class="one-half column">
<button type="button" name="optimization button" onclick="toggleOptimization()">
Toggle optimization</button>
</div>
<div class="one-half column">
<button type="button" id="debugBtn" name="debug button" onclick="debug()">debug on</button>
</div>
</div>
<div class="row">
<div class="one-half column">
<input id="cellsize" type="range" min="10" max="100" value="25" class="slider"
oninput="document.getElementById('cellsizeo').textContent=this.value"
onchange="spatialHash.cellSize = parseInt(this.value);
spatialHash.rebuild();">
<label for="cellsize">cell size</label>
<output id="cellsizeo" class="u-pull-right" name="result">25</output class="u-pull-right">
<input id="springstrength" type="range" min="1" max="100" value="30" class="slider"
oninput="springstrength = parseInt(this.value); document.getElementById('springstrengtho').textContent=this.value">
<label for="springstrength">spring strength</label>
<output id="springstrengtho" class="u-pull-right" name="result">30</output class="u-pull-right">
</div>
<div class="one-half column">
<input id="gravity" type="range" min="-100" max="100" value="15" class="slider"
oninput="gravity = parseInt(this.value); document.getElementById('gravityo').textContent=this.value">
<label for="gravity">gravity</label>
<output id="gravityo" class="u-pull-right" name="result">15</output class="u-pull-right">
<input id="resistance" type="range" min="1" max="50" value="5" class="slider"
oninput="resistance = parseInt(this.value); document.getElementById('resistanceo').textContent=this.value">
<label for="resistance">air resistance</label>
<output id="resistanceo" class="u-pull-right" name="result">5</output class="u-pull-right">
</div>
</div>
<article class="row" style="margin-top:12rem;">
<p><b> Turn on the debug grid</b>, to see which cells are being checked for collisions. Cells with lots of checks are colored in <b>red</b>, less expensive cells are <b>green</b>. There's a percentage indicator in the top left corner,
showing how many collisions have been saved compared to the brute force "check everything against everything" approach.
</p>
<h2>Implementation Details</h2>
<p>
The objects are assigned to the cells by rounding their positions to the next multiple of the cell size on x and y axis.
These are then used as keys in a hash table, which is a dictionary with the rounded positions as keys.
<br>
<br>
A sensible cell size is crucial for this problem. Too small of a cell size means large objects can overlap several cells and actually decrease performance worse, because their collision is checked against objects in each cell they occupy.
On the other hand, a large cell size means that objects that lots of objects may occupy the same cell, leading to a O(n<sup>2</sup>) collision check within that cell.
<br>
<br>
The specific hashing function for creating the key from x and y coordinates is called a <a href="https://en.wikipedia.org/wiki/Pairing_function">pairing function</a>,
specifically Szudzik's pairing function.
<code>a >= b ? a * a + a + b : a + b * b;</code> where a, b >= 0 (positive coordinates)
This is a bijecive function, which can easily be reversed to get the original coordinates, e.g. when drawing the occupied debug grid cells.
</p>
<h2>Simulation</h2>
<p>Every particle is modelled as a spring-mass system, with individual weight and spring stiffness. This model is an example for <a href="https://en.wikipedia.org/wiki/Smoothed-particle_hydrodynamics">smoothed particle hydrodynamics</a>, a type of particle based fluid simulation.
After some time the lighter circles will float on top of the heavier rectangles, a phase separation occurs.
</p>
</article>
</div>
<script type="text/javascript" src="debug.js"></script>
<script type="text/javascript" src="spatialHash.js"></script>
<script type="text/javascript" src="script.js" onload="loadStorageValues()"></script>
</body>
</html>