Example standard-cell placement engine for the LibrEDA-Rust framework. This placement algorithm simulates the movement of electric charges that are sparsely connected by springs (wires).
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

290 lines
9.6 KiB

/*
* Copyright (c) 2019-2020 Thomas Kramer.
*
* This file is part of LibrEDA
* (see https://codeberg.org/libreda).
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
use super::types::*;
#[derive(Clone, PartialEq, Debug)]
enum TreeNode {
None,
Leaf(Particle),
SubTree(Box<QuadTree>),
}
#[derive(Clone, Debug, PartialEq)]
pub struct QuadTree {
lower_left: Vec2D,
side_length: FloatType,
center_of_charge: Option<Particle>,
children: [TreeNode; 4],
}
impl QuadTree {
/// Construct a new quad-tree.
pub fn new<T: Into<Vec2D>>(lower_left: T, side_length: FloatType) -> Self {
QuadTree {
lower_left: lower_left.into(),
side_length,
center_of_charge: None,
children: [TreeNode::None, TreeNode::None, TreeNode::None, TreeNode::None],
}
}
fn get_subtree_index(right_subtree: bool, upper_subtree: bool) -> usize {
(right_subtree as usize) + (upper_subtree as usize) * 2
}
/// Recursively abstract all particles in the tree by a new particle with the sum of all charges
/// and the weighted-average location of the other particles.
pub fn update_center_of_charge(&mut self) -> () {
// Get centers-of-charge of all sub-trees.
let sub_centers = self.children.iter_mut().filter_map(|child|
match child {
TreeNode::None => None,
TreeNode::Leaf(p) => Some(*p),
TreeNode::SubTree(subtree) => {
subtree.update_center_of_charge();
Some(subtree.center_of_charge.unwrap())
}
}
);
// Sum up all locations weighted by the charge.
let (location_sum, total_charge) = sub_centers.fold(
(Vec2D::zero(), 0.0),
|(v, charge), particle: Particle|
(v + particle.location * particle.charge, charge + particle.charge),
);
// Calculate average of locations.
let avg_location = if total_charge != 0.0 {
location_sum / total_charge
} else {
Vec2D::zero()
};
// Create particle representing the center-of-charge.
let center_of_charge = Particle::new(avg_location, total_charge);
// Update center-of-charge.
self.center_of_charge = Some(center_of_charge);
}
/// Insert a particle into the quad-tree and recursively create new sub-trees
/// when necessary.
pub fn insert(&mut self, particle: Particle) -> () {
// Invalidate center-of-charge.
self.center_of_charge = None;
let (px, py) = particle.location.into();
let (ox, oy) = self.lower_left.into();
// Assert that the particle belongs to this tree.
debug_assert!(px >= ox);
debug_assert!(py >= oy);
debug_assert!(px - ox < self.side_length);
debug_assert!(py - oy < self.side_length);
let s_half = self.side_length / 2.0;
// Check to which sub-tree the particle would belong.
let right_subtree = px >= ox + s_half;
let upper_subtree = py >= oy + s_half;
let index = QuadTree::get_subtree_index(right_subtree, upper_subtree);
let new_child = match &mut self.children[index] {
TreeNode::None => TreeNode::Leaf(particle),
TreeNode::Leaf(p) if p.location == particle.location => {
let charge = p.charge + particle.charge;
let location = p.location;
TreeNode::Leaf(Particle { location, charge })
}
TreeNode::Leaf(p) => {
// Calculate side length of subtree.
let half_side = self.side_length / 2.0;
// Calculate lower left corner of sub-tree.
let lower_left = Vec2D {
x: if right_subtree {
ox + half_side
} else {
ox
},
y: if upper_subtree {
oy + half_side
} else {
oy
},
};
// Create a new sub-tree and insert the particles.
let mut subtree = QuadTree::new(lower_left, half_side);
subtree.insert(particle);
subtree.insert(*p);
TreeNode::SubTree(Box::new(subtree))
}
TreeNode::SubTree(subtree) => {
// Recursively insert particle into sub-tree.
subtree.insert(particle);
TreeNode::None
}
};
// Update child.
match new_child {
TreeNode::None => (),
c => self.children[index] = c
}
}
/// Calculate the force (and derivative) on a particle induced by the particles in the quad-tree.
pub fn force_onto_particle(&self, particle: &Particle, threshold: f64) -> Cost {
let sub_forces = self.children.iter()
.map(|child|
match child {
// If there is on particle, the force is zero.
TreeNode::None => Cost::zero(),
// Force calculation is trivial if there is only one particle.
TreeNode::Leaf(other) => particle.force_from(other),
// Recursively dive into the sub-tree.
TreeNode::SubTree(subtree) => {
debug_assert_ne!(subtree.center_of_charge, None);
// Calculate relative distance to the center of the sub-tree.
let sub_center = subtree.center_of_charge.unwrap();
let dist = (particle.location - sub_center.location).norm2();
let ratio = dist / self.side_length;
if ratio > threshold {
// Return approximate solution if distance to sub-tree center is large enough.
particle.force_from(&sub_center)
} else {
// Recursively dive into sub-tree to get more accurate solution.
subtree.force_onto_particle(&particle, threshold)
}
}
}
);
// Sum up all forces.
sub_forces.fold(Cost::zero(), |acc, x|
acc + x)
}
}
#[cfg(test)]
mod tests {
use super::*;
use rand::prelude::*;
#[test]
fn test_quad_tree_insertion() {
let p1 = Particle::new((0.1, 0.1), 1.);
let p2 = Particle::new((0.4, 0.4), 2.);
let mut qt = QuadTree::new((0.0, 0.0), 1.0);
assert_eq!(qt.children[0], TreeNode::None);
// Test inserting a single particle.
qt.insert(p1);
assert_eq!(qt.children[0], TreeNode::Leaf(p1));
// Test recursive sub-tree creation.
qt.insert(p2);
if let TreeNode::SubTree(st) = &qt.children[0] {
assert_eq!(st.children[0], TreeNode::Leaf(p1));
} else {
assert!(false);
}
if let TreeNode::SubTree(st) = &qt.children[0] {
assert_eq!(st.children[3], TreeNode::Leaf(p2));
} else {
assert!(false);
}
}
#[test]
fn test_center_of_charge() {
let p1 = Particle::new((0.25, 0.125), 1.);
let p2 = Particle::new((0.5, 0.5), 1.);
let p3 = Particle::new((0.75, 0.875), 1.);
let expected_center = Particle::new((0.5, 0.5), 3.);
let mut qt = QuadTree::new((0.0, 0.0), 1.0);
qt.insert(p1);
qt.insert(p2);
qt.insert(p3);
qt.update_center_of_charge();
assert_eq!(qt.center_of_charge, Some(expected_center));
}
#[test]
fn test_force_calculation() {
let p1 = Particle::new((0.25, 0.125), 1.);
let p2 = Particle::new((0.5, 0.5), 1.);
let p3 = Particle::new((0.75, 0.875), 1.);
let mut qt = QuadTree::new((0.0, 0.0), 1.0);
qt.insert(p1);
qt.insert(p2);
qt.insert(p3);
qt.update_center_of_charge();
let probe1 = Particle::new((0., 0.), 1.);
let probe2 = Particle::new((1., 1.), 1.);
let force1 = qt.force_onto_particle(&probe1, 2.).gradient;
assert!(force1.x < 0.);
assert!(force1.y < 0.);
let force2 = qt.force_onto_particle(&probe2, 2.).gradient;
assert!(force2.x > 0.);
assert!(force2.y > 0.);
}
#[test]
fn test_many_particles() {
let mut rng = rand::thread_rng();
let mut qt = QuadTree::new((0.0, 0.0), 1.0);
let n_particles = 1000;
let particles: Vec<Particle> = (0..n_particles).map(|_| {
let x: f64 = rng.gen_range(0.0..1.0);
let y: f64 = rng.gen_range(0.0..1.0);
Particle::new((x, y), 1.0)
}
).collect();
for &p in &particles {
qt.insert(p);
}
qt.update_center_of_charge();
let threshold = 0.5;
let _forces: Vec<Cost> = particles.iter().map(|p|
qt.force_onto_particle(p, threshold)
).collect();
}
}