Hey I'm trying to optimise particles.js library from Vincent Garrau in order to get 60fps @ 500 particles ~.
I've already refactored the code to use a quad tree instead but it does not seem to be enough. In fact, I saw no improvement using the quad tree. Maybe I implemented it incorrectly ?
What I'm doing ?
- Generating n number of particles
- For each frame : reset the quad tree. For each particle, move it a little and insert it into the tree. Then for each particles, check through a tree query if other particles are close. If there are, draw a line between them. Render the canvas.
Most code below. Full codepen here https://codepen.io/audrenbdb/pen/NWWVpmQ
function update () {
let particle
let ms = 0
quadTree.clear()
for (let i = 0, l = particlesList.length; i < l; i++) {
particle = particlesList[i]
ms = speed / 2
particle.x += particle.vx * ms
particle.y += particle.vy * ms
let new_pos = bounce
? {
x_left: size,
x_right: canvas.width,
y_top: size,
y_bottom: canvas.height
}
: {
x_left: -size,
x_right: canvas.width + size,
y_top: -size,
y_bottom: canvas.height + size
}
if (particle.x - size > canvas.width) {
particle.x = new_pos.x_left
particle.y = Math.random() * canvas.height
} else if (particle.x + size < 0) {
particle.x = new_pos.x_right
particle.y = Math.random() * canvas.height
}
if (particle.y - size > canvas.height) {
particle.y = new_pos.y_top
particle.x = Math.random() * canvas.width
} else if (particle.y + size < 0) {
particle.y = new_pos.y_bottom
particle.x = Math.random() * canvas.width
}
if (bounce) {
if (particle.x + size > canvas.width) particle.vx = -particle.vx
else if (particle.x - size < 0) particle.vx = -particle.vx
if (particle.y + size > canvas.height) particle.vy = -particle.vy
else if (particle.y - size < 0) particle.vy = -particle.vy
}
if (interaction.status === 'mousemove') {
repulse(particle)
}
draw(particle)
particle.circle.x = particle.x
particle.circle.y = particle.y
particle.circle.r = linkDistance
quadTree.insert(particle)
}
let explored = []
var i
var j
for (i = 0; i < particlesList.length; i++) {
let links = quadTree.query(particlesList[i].circle)
for (j = 0; j < links.length; j++) {
if (links[j] !== particlesList[i] && !explored.includes(links[j])) {
linkParticles(particlesList[i], links[j])
}
}
explored.push(particlesList[i])
}
}
function repulse (particle) {
const dx_mouse = particle.x - interaction.pos_x
const dy_mouse = particle.y - interaction.pos_y
const dist_mouse = Math.sqrt(Math.pow(dx_mouse, 2) + Math.pow(dy_mouse, 2))
const velocity = 100
const repulseFactor = Math.min(
Math.max(
(1 / repulseDistance) *
(-1 * Math.pow(dist_mouse / repulseDistance, 2) + 1) *
repulseDistance *
velocity,
0
),
50
)
let posX = particle.x + (dx_mouse / dist_mouse) * repulseFactor
let posY = particle.y + (dy_mouse / dist_mouse) * repulseFactor
if (bounce) {
if (posX - size > 0 && posX + size < canvas.width) particle.x = posX
if (posY - size > 0 && posY + size < canvas.height) particle.y = posY
} else {
particle.x = posX
particle.y = posY
}
}
function createParticle () {
let x = Math.random() * canvas.width
let y = Math.random() * canvas.height
const vx = Math.random() - 0.5
const vy = Math.random() - 0.5
if (x > canvas.width - size * 2) x -= size
else if (x < size * 2) x += size
if (y > canvas.height - size * 2) y -= size
else if (y < size * 2) y += size
let particle = {
x: x,
y: y,
vx: vx,
vy: vy,
circle: new Circle(x, y, size)
}
return particle
}
function setCanvasSize () {
canvas.height = canvas.offsetHeight
canvas.width = canvas.offsetWidth
boundary = new Rectangle(
canvas.width / 2,
canvas.height / 2,
canvas.width,
canvas.height
)
quadTree = new QuadTree(boundary, 4)
context = canvas.getContext('2d')
context.fillRect(0, 0, canvas.width, canvas.height)
context.fillStyle = `rgba(${particleRGB},1)`;
}
function linkParticles (particle1, particle2) {
let opacityValue = 1
const dist = Math.sqrt(
Math.pow(particle1.x - particle2.x, 2) +
Math.pow(particle1.y - particle2.y, 2)
)
opacityValue = 1 - dist / (.7 * linkDistance)
context.strokeStyle = `rgba(${linkRGB}, ${opacityValue})`
context.lineWidth = linkWidth
context.beginPath()
context.moveTo(particle1.x, particle1.y)
context.lineTo(particle2.x, particle2.y)
context.stroke()
context.closePath()
}
function draw (particle) {
context.beginPath()
context.arc(
Math.floor(particle.x),
Math.floor(particle.y),
size,
0,
Math.PI * 2,
false
)
context.closePath()
context.fill()
}
function animate () {
context.clearRect(0, 0, canvas.width, canvas.height)
update()
requestAnimationFrame(animate)
}
Quad tree code
class Circle {
constructor (x, y, r) {
this.x = x
this.y = y
this.r = r
}
contains (point) {
let d = Math.pow(point.x - this.x, 2) + Math.pow(point.y - this.y, 2)
return d <= this.r * this.r
}
intersects (range) {
let xDyst = Math.abs(range.x - this.x)
let yDist = Math.abs(range.y - this.y)
let r = this.r
let w = range.w
let h = range.h
let edges = Math.pow(xDist - w, 2) + Math.pow(yDist - h, 2)
if (xDist > r + w || yDist > r + h) return false
if (xDist <= w || yDist <= h) return true
return edges <= this.r * this.r
}
}
class Rectangle {
constructor (x, y, w, h) {
this.x = x
this.y = y
this.w = w
this.h = h
}
contains (point) {
return (
point.x >= this.x - this.w &&
point.x <= this.x + this.w &&
point.y >= this.y - this.h &&
point.y <= this.y + this.h
)
}
intersects (range) {
return !(
range.x - range.w > this.x + this.w ||
range.x + range.w < this.x - this.w ||
range.y - range.h > this.y + this.h ||
range.y + range.h < this.y - this.h
)
}
}
class QuadTree {
constructor (boundary, capacity) {
this.boundary = boundary
this.capacity = capacity
this.points = []
this.divided = false
}
insert (point) {
if (!this.boundary.contains(point)) return false
if (this.points.length < this.capacity) {
this.points.push(point)
return true
} else {
if (!this.divided) {
this.subdivide()
this.divided = true
}
if (this.northEast.insert(point)) return true
else if (this.northWest.insert(point)) return true
else if (this.southEast.insert(point)) return true
else if (this.southWest.insert(point)) return true
}
}
subdivide () {
let x = this.boundary.x
let y = this.boundary.y
let w = this.boundary.w
let h = this.boundary.h
let ne = new Rectangle(x + w / 2, y - h / 2, w / 2, h / 2)
let nw = new Rectangle(x - w / 2, y - h / 2, w / 2, h / 2)
let se = new Rectangle(x + w / 2, y + h / 2, w / 2, h / 2)
let sw = new Rectangle(x - w / 2, y + h / 2, w / 2, h / 2)
this.northWest = new QuadTree(ne, this.capacity)
this.northEast = new QuadTree(nw, this.capacity)
this.southWest = new QuadTree(se, this.capacity)
this.southEast = new QuadTree(sw, this.capacity)
this.divided = true
}
query (range, found = []) {
if (!this.boundary.intersects(range)) {
} else {
for (let p of this.points) {
if (range.contains(p)) {
found.push(p)
}
}
if (this.divided) {
this.northEast.query(range, found)
this.northWest.query(range, found)
this.southEast.query(range, found)
this.southWest.query(range, found)
}
return found
}
}
clear () {
if (this.divided) {
delete this.northEast
delete this.northWest
delete this.southEast
delete this.southWest
}
this.points = []
this.divided = false
}
}
