diff options
Diffstat (limited to 'web/pw-frontend')
25 files changed, 7 insertions, 4939 deletions
diff --git a/web/pw-frontend/package.json b/web/pw-frontend/package.json index f011162..94d95a0 100644 --- a/web/pw-frontend/package.json +++ b/web/pw-frontend/package.json @@ -5,7 +5,7 @@ "scripts": { "dev": "vite", "build": "vite build", - "build-wasm": "wasm-pack build ./planetwars-rs --target web", + "build-wasm": "wasm-pack build ../planetwars-rs --target web", "preview": "vite preview", "check": "svelte-check --tsconfig ./tsconfig.json" }, @@ -13,7 +13,6 @@ "@originjs/vite-plugin-commonjs": "^1.0.1", "@sveltejs/vite-plugin-svelte": "^1.0.0-next.30", "@tsconfig/svelte": "^2.0.1", - "rollup-plugin-polyfill-node": "^0.8.0", "svelte": "^3.44.0", "svelte-check": "^2.2.7", "svelte-preprocess": "^4.9.8", @@ -23,11 +22,8 @@ "vite-plugin-wasm-pack": "^0.1.9" }, "dependencies": { - "buffer": "^6.0.3", - "extract-svg-path": "^2.1.0", - "load-svg": "^1.0.0", "moment": "^2.29.1", - "svg-mesh-3d": "^1.1.0", - "ts-heap": "^1.1.3" + "pw-visualizer": "file:../pw-visualizer", + "planetwars-rs": "file:../planetwars-rs/pkg" } } diff --git a/web/pw-frontend/planetwars-rs/.gitignore b/web/pw-frontend/planetwars-rs/.gitignore deleted file mode 100644 index a04eea2..0000000 --- a/web/pw-frontend/planetwars-rs/.gitignore +++ /dev/null @@ -1,2 +0,0 @@ -pkg/** -target/** diff --git a/web/pw-frontend/planetwars-rs/Cargo.toml b/web/pw-frontend/planetwars-rs/Cargo.toml deleted file mode 100644 index a5dc949..0000000 --- a/web/pw-frontend/planetwars-rs/Cargo.toml +++ /dev/null @@ -1,44 +0,0 @@ -[package] -name = "planetwars-rs" -version = "0.1.0" -authors = ["ajuvercr <arthur.vercruysse@ugent.be>"] -edition = "2018" - -[package.metadata.wasm-pack.profile.release] -wasm-opt = ["-Oz", "--enable-mutable-globals"] - -[lib] -crate-type = ["cdylib", "rlib"] - -[features] -default = ["console_error_panic_hook"] - -[dependencies] -wasm-bindgen = "0.2.63" - -# The `console_error_panic_hook` crate provides better debugging of panics by -# logging them with `console.error`. This is great for development, but requires -# all the `std::fmt` and `std::panicking` infrastructure, so isn't great for -# code size when deploying. -console_error_panic_hook = { version = "0.1.6", optional = true } - -# `wee_alloc` is a tiny allocator for wasm that is only ~1K in code size -# compared to the default allocator's ~10K. It is slower than the default -# allocator, however. -# -# Unfortunately, `wee_alloc` requires nightly Rust when targeting wasm for now. -wee_alloc = { version = "0.4.5", optional = true } -serde = "1.0.100" -serde_derive = "1.0.100" -serde_json = "1.0" -octoon-math = "0.1.7" -voronoi = "0.1.4" - -[dev-dependencies] -wasm-bindgen-test = "0.3.13" - -[profile.release] -# Tell `rustc` to optimize for small code size. -opt-level = "s" - -[workspace]
\ No newline at end of file diff --git a/web/pw-frontend/planetwars-rs/src/lib.rs b/web/pw-frontend/planetwars-rs/src/lib.rs deleted file mode 100644 index f2ba7e1..0000000 --- a/web/pw-frontend/planetwars-rs/src/lib.rs +++ /dev/null @@ -1,373 +0,0 @@ -extern crate serde; -#[macro_use] -extern crate serde_derive; -extern crate octoon_math; -extern crate serde_json; -extern crate voronoi; - -use octoon_math::Mat3; -use voronoi::{make_polygons, voronoi, Point}; - -mod types; -mod utils; - -use std::collections::HashMap; -use wasm_bindgen::prelude::*; - -macro_rules! console_log { - // Note that this is using the `log` function imported above during - // `bare_bones` - ($($t:tt)*) => (log(&format_args!($($t)*).to_string())) -} - -// When the `wee_alloc` feature is enabled, use `wee_alloc` as the global -// allocator. -#[cfg(feature = "wee_alloc")] -#[global_allocator] -static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT; - -#[derive(Debug, Clone)] -pub struct Circle { - r: f32, - x: f32, - y: f32, - a0: f32, - ad: f32, - distance: usize, -} - -use std::f32::consts::PI; -fn spr(from: f32) -> f32 { - let pi2 = PI * 2.; - ((from % pi2) + pi2) % pi2 -} - -impl Circle { - pub fn new(p1: &types::Planet, p2: &types::Planet) -> Self { - let x1 = p1.x; - let y1 = p1.y; - let x2 = p2.x; - let y2 = p2.y; - - // Distance between planets - let q = ((x2 - x1).powi(2) + (y2 - y1).powi(2)).sqrt(); - // Center of between planets - let x3 = (x1 + x2) / 2.0; - let y3 = (y1 + y2) / 2.0; - - // Radius of circle - let r = q * 1.0; - - // Center of circle - let x = x3 + (r.powi(2) - (q / 2.0).powi(2)).sqrt() * (y1 - y2) / q; - let y = y3 + (r.powi(2) - (q / 2.0).powi(2)).sqrt() * (x2 - x1) / q; - // console_log!("{},{} -> {},{} ({},{} r={})", x1, y1, x2, y2, x, y, r); - - let a0 = spr((y - y1).atan2(x - x1)); - let a2 = spr((y - y2).atan2(x - x2)); - - let mut ad = spr(a0 - a2); - if ad > PI { - ad = spr(a2 - a0); - } - // console_log!("a1 {} a2 {} ad {}", a0/PI * 180.0, a2/PI * 180.0, ad/PI*180.0); - - let distance = q.ceil() as usize + 1; - Self { - r, - x, - y, - a0, - ad, - distance, - } - } - - pub fn get_for_remaining(&self, remaining: usize) -> ((Mat3<f32>, f32), (Mat3<f32>, f32)) { - ( - self.get_remaining(remaining), - self.get_remaining((remaining + 1).min(self.distance - 1)), - ) - } - - fn get_remaining(&self, remaining: usize) -> (Mat3<f32>, f32) { - let alpha = self.a0 + (1.0 - (remaining as f32 / self.distance as f32)) * self.ad; - - let cos = alpha.cos(); - let sin = alpha.sin(); - ( - Mat3::new( - 0.3, - 0.0, - 0.0, - 0.0, - 0.3, - 0.0, - -self.x + cos * self.r, - -self.y + sin * self.r, - 0.3, - ), - alpha, - ) - } -} - -fn create_voronoi(planets: &Vec<types::Planet>, bbox: f32) -> (Vec<f32>, Vec<usize>) { - let mut verts: Vec<[f32; 2]> = planets.iter().map(|p| [p.x, p.y]).collect(); - let mut ids = Vec::new(); - - let vor_points = planets - .iter() - .map(|p| Point::new(p.x as f64, p.y as f64)) - .collect(); - - let vor = voronoi(vor_points, bbox as f64); - let vor = make_polygons(&vor); - - for poly in vor.iter() { - // Get planet index for planet that is inside this poligon - let idx = 0; - - let mut prev = ids.len() + poly.len() - 1; - for p in poly.iter() { - let now = verts.len(); - verts.push([p.x.0 as f32, p.y.0 as f32]); - - ids.push(idx); - ids.push(now); - ids.push(prev); - prev = now; - } - } - - (verts.concat(), ids) -} - -#[wasm_bindgen] -pub struct Game { - states: Vec<types::State>, - turn: usize, - - planet_map: HashMap<(String, String), Circle>, - - /* put extra shit here */ - view_box: Vec<f32>, - - planets: Vec<f32>, - planet_ships: Vec<usize>, - - ship_locations: Vec<f32>, - ship_label_locations: Vec<f32>, - ship_colours: Vec<f32>, - ship_counts: Vec<usize>, - - current_planet_colours: Vec<f32>, - - voronoi_vertices: Vec<f32>, - voronoi_colors: Vec<f32>, - voronoi_indices: Vec<usize>, -} - -#[wasm_bindgen] -impl Game { - pub fn new(file: &str) -> Self { - utils::set_panic_hook(); - - // First line is fucked but we just filter out things that cannot parse - let states: Vec<types::State> = file - .split("\n") - .filter_map(|line| serde_json::from_str(line).ok()) - .collect(); - - let mut planet_map = HashMap::new(); - - // Iterator? - for p1 in states[0].planets.iter() { - for p2 in states[0].planets.iter() { - planet_map.insert((p1.name.clone(), p2.name.clone()), Circle::new(&p1, &p2)); - } - } - let view_box = utils::caclulate_viewbox(&states[0].planets); - - let (voronoi_vertices, voronoi_indices) = - create_voronoi(&states[0].planets, view_box[2].max(view_box[3])); - - let voronoi_colors: Vec<f32> = voronoi_indices - .iter() - .map(|_| [0.0, 0.0, 0.0]) - .collect::<Vec<[f32; 3]>>() - .concat(); // Init these colours on black - - Self { - planets: utils::get_planets(&states[0].planets, 2.0), - planet_ships: Vec::new(), - view_box, - - planet_map, - turn: 0, - states, - ship_locations: Vec::new(), - ship_label_locations: Vec::new(), - ship_colours: Vec::new(), - ship_counts: Vec::new(), - current_planet_colours: Vec::new(), - - voronoi_vertices, - voronoi_indices, - voronoi_colors, - } - } - - pub fn push_state(&mut self, state_str: &str) { - if let Ok(state) = serde_json::from_str(state_str) { - self.states.push(state); - } - } - - pub fn get_viewbox(&self) -> Vec<f32> { - self.view_box.clone() - } - - pub fn get_planets(&self) -> Vec<f32> { - self.planets.clone() - } - - pub fn get_planet_ships(&self) -> Vec<usize> { - self.planet_ships.clone() - } - - pub fn get_planet_colors(&self) -> Vec<f32> { - self.current_planet_colours.clone() - } - - pub fn turn_count(&self) -> usize { - self.states.len() - } - - pub fn update_turn(&mut self, turn: usize) -> usize { - self.turn = turn.min(self.states.len() - 1); - - self.update_planet_ships(); - self.update_planet_colours(); - self.update_voronoi_colors(); - self.update_ship_locations(); - self.update_ship_counts(); - - self.turn - } - - fn update_planet_ships(&mut self) { - self.planet_ships = self.states[self.turn] - .planets - .iter() - .map(|p| p.ship_count as usize) - .collect(); - } - - fn update_voronoi_colors(&mut self) { - for (i, p) in self.states[self.turn].planets.iter().enumerate() { - let color = utils::COLORS[p.owner.unwrap_or(0) as usize % utils::COLORS.len()]; - self.voronoi_colors[i * 3 + 0] = color[0]; - self.voronoi_colors[i * 3 + 1] = color[1]; - self.voronoi_colors[i * 3 + 2] = color[2]; - } - } - - fn update_planet_colours(&mut self) { - let mut new_vec: Vec<[f32; 3]> = Vec::new(); - let planets_now = self.states[self.turn].planets.iter(); - let planets_later = self.states[(self.turn + 1).min(self.states.len() - 1)] - .planets - .iter(); - - for (p1, p2) in planets_now.zip(planets_later) { - new_vec - .push(utils::COLORS[p1.owner.unwrap_or(0) as usize % utils::COLORS.len()].into()); - new_vec - .push(utils::COLORS[p2.owner.unwrap_or(0) as usize % utils::COLORS.len()].into()); - } - - self.current_planet_colours = new_vec.concat::<f32>(); - } - - fn update_ship_locations(&mut self) { - let mut new_sl = Vec::new(); - let mut new_sll = Vec::new(); - - let t = Mat3::new(0.2, 0., 0., 0., 0.2, 0.0, 0., -0.5, 0.2); - - for ship in self.states[self.turn].expeditions.iter() { - let ((o1, a1), (o2, a2)) = self - .planet_map - .get(&(ship.origin.clone(), ship.destination.clone())) - .unwrap() - .get_for_remaining(ship.turns_remaining as usize); - new_sl.push((o1 * Mat3::rotate_z(a1)).to_array()); - new_sl.push((o2 * Mat3::rotate_z(a2)).to_array()); - - new_sll.push((o1 + t).to_array()); - new_sll.push((o2 + t).to_array()); - } - - self.ship_locations = new_sl.concat(); - self.ship_label_locations = new_sll.concat(); - - self.ship_colours = self.states[self.turn] - .expeditions - .iter() - .map(|s| utils::COLORS[s.owner as usize % utils::COLORS.len()]) - .collect::<Vec<[f32; 3]>>() - .concat(); - } - - fn update_ship_counts(&mut self) { - self.ship_counts = self.states[self.turn] - .expeditions - .iter() - .map(|s| s.ship_count as usize) - .collect(); - } - - pub fn get_max_ships(&self) -> usize { - self.states - .iter() - .map(|s| s.expeditions.len()) - .max() - .unwrap() - } - - pub fn get_ship_locations(&self) -> Vec<f32> { - self.ship_locations.clone() - } - - pub fn get_ship_label_locations(&self) -> Vec<f32> { - self.ship_label_locations.clone() - } - - pub fn get_ship_colours(&self) -> Vec<f32> { - self.ship_colours.clone() - } - - pub fn get_ship_counts(&self) -> Vec<usize> { - self.ship_counts.clone() - } - - pub fn get_voronoi_verts(&self) -> Vec<f32> { - self.voronoi_vertices.clone() - } - - pub fn get_voronoi_colours(&self) -> Vec<f32> { - self.voronoi_colors.clone() - } - - pub fn get_voronoi_inds(&self) -> Vec<usize> { - self.voronoi_indices.clone() - } -} - -#[wasm_bindgen] -extern "C" { - fn alert(s: &str); - #[wasm_bindgen(js_namespace = console)] - fn log(s: &str); -} diff --git a/web/pw-frontend/planetwars-rs/src/types.rs b/web/pw-frontend/planetwars-rs/src/types.rs deleted file mode 100644 index 2d7d8c0..0000000 --- a/web/pw-frontend/planetwars-rs/src/types.rs +++ /dev/null @@ -1,45 +0,0 @@ -#[derive(Debug, Clone, Serialize, Deserialize)] -pub struct Expedition { - pub id: u64, - pub ship_count: u64, - pub origin: String, - pub destination: String, - pub owner: u64, - pub turns_remaining: u64, -} - -#[derive(Debug, Clone, Serialize, Deserialize)] -pub struct Planet { - pub ship_count: u64, - pub x: f32, - pub y: f32, - pub owner: Option<u32>, - pub name: String, -} - -use std::hash::{Hash, Hasher}; -use std::mem; - -impl Hash for Planet { - fn hash<H: Hasher>(&self, state: &mut H) { - unsafe { - let x: u32 = mem::transmute_copy(&self.x); - let y: u32 = mem::transmute_copy(&self.y); - state.write_u32(x); - state.write_u32(y); - } - } -} - -impl PartialEq for Planet { - fn eq(&self, other: &Self) -> bool { - (self.x - other.x).abs() < 0.0001 && (self.y - other.y).abs() < 0.0001 - } -} -impl Eq for Planet {} - -#[derive(Debug, Clone, Serialize, Deserialize)] -pub struct State { - pub planets: Vec<Planet>, - pub expeditions: Vec<Expedition>, -} diff --git a/web/pw-frontend/planetwars-rs/src/utils.rs b/web/pw-frontend/planetwars-rs/src/utils.rs deleted file mode 100644 index a903912..0000000 --- a/web/pw-frontend/planetwars-rs/src/utils.rs +++ /dev/null @@ -1,65 +0,0 @@ -pub fn set_panic_hook() { - // When the `console_error_panic_hook` feature is enabled, we can call the - // `set_panic_hook` function at least once during initialization, and then - // we will get better error messages if our code ever panics. - // - // For more details see - // https://github.com/rustwasm/console_error_panic_hook#readme - #[cfg(feature = "console_error_panic_hook")] - console_error_panic_hook::set_once(); -} - -/// this is total extra, so it the planet viewbox is like 100px wide, it will now be in total 110 pixels wide -static VIEWBOX_SCALE: f32 = 0.1; - -pub static COLORS: [[f32; 3]; 10] = [ - [0.5, 0.5, 0.5], - [1.0, 0.50, 0.0], // #FF8000 - [0.0, 0.50, 1.0], // #0080ff - [1.0, 0.4, 0.58], // #FF6693 - [0.24, 0.79, 0.33], // #3fcb55 - [0.79, 0.76, 0.24], // #cbc33f - [0.81, 0.25, 0.91], // #cf40e9 - [0.94, 0.32, 0.32], // #FF3F0D - [0.11, 0.93, 0.94], // #1beef0 - [0.05, 0.77, 1.0], // #0DC5FF -]; - -use super::types; - -pub fn caclulate_viewbox(planets: &Vec<types::Planet>) -> Vec<f32> { - let mut iter = planets.iter(); - - let init = match iter.next() { - Some(p) => (p.x, p.y, p.x, p.y), - None => return vec![0.0, 0.0, 0.0, 0.0], - }; - let (min_x, min_y, max_x, max_y) = - planets - .iter() - .fold(init, |(min_x, min_y, max_x, max_y), p| { - ( - min_x.min(p.x), - min_y.min(p.y), - max_x.max(p.x), - max_y.max(p.y), - ) - }); - - let (width, height) = (max_x - min_x, max_y - min_y); - let (dx, dy) = ( - (VIEWBOX_SCALE * width).max(6.0), - (VIEWBOX_SCALE * height).max(6.0), - ); - - vec![min_x - dx / 2.0, min_y - dy / 2.0, width + dx, height + dy] -} - -pub fn get_planets(planets: &Vec<types::Planet>, r: f32) -> Vec<f32> { - planets.iter().fold(Vec::new(), |mut cum, p| { - cum.push(p.x); - cum.push(p.y); - cum.push(r); - cum - }) -} diff --git a/web/pw-frontend/src/lib/Visualizer.svelte b/web/pw-frontend/src/lib/Visualizer.svelte index 297659c..bcd6c7a 100644 --- a/web/pw-frontend/src/lib/Visualizer.svelte +++ b/web/pw-frontend/src/lib/Visualizer.svelte @@ -1,6 +1,6 @@ <script lang="ts"> import { onMount } from 'svelte'; - import * as visualizer from '../lib/visualizer/index'; + import * as visualizer from "pw-visualizer"; export let matchLog = null; @@ -20,6 +20,7 @@ visualizer.set_loading(false); } } + </script> <div id="main" class="loading"> @@ -57,5 +58,5 @@ </div> <style scoped> - @import 'visualizer/style.css'; + @import 'pw-visualizer/src/style.css'; </style> diff --git a/web/pw-frontend/src/lib/visualizer/LICENSE-MIT b/web/pw-frontend/src/lib/visualizer/LICENSE-MIT deleted file mode 100644 index 8d459d1..0000000 --- a/web/pw-frontend/src/lib/visualizer/LICENSE-MIT +++ /dev/null @@ -1,25 +0,0 @@ -Copyright (c) 2018 Arthur Vercruysse - -Permission is hereby granted, free of charge, to any -person obtaining a copy of this software and associated -documentation files (the "Software"), to deal in the -Software without restriction, including without -limitation the rights to use, copy, modify, merge, -publish, distribute, sublicense, and/or sell copies of -the Software, and to permit persons to whom the Software -is furnished to do so, subject to the following -conditions: - -The above copyright notice and this permission notice -shall be included in all copies or substantial portions -of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF -ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED -TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A -PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT -SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY -CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION -OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR -IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER -DEALINGS IN THE SOFTWARE. diff --git a/web/pw-frontend/src/lib/visualizer/README.md b/web/pw-frontend/src/lib/visualizer/README.md deleted file mode 100644 index aaba256..0000000 --- a/web/pw-frontend/src/lib/visualizer/README.md +++ /dev/null @@ -1 +0,0 @@ -Original by the amazing Arthur Vercruysse!
\ No newline at end of file diff --git a/web/pw-frontend/src/lib/visualizer/index.html b/web/pw-frontend/src/lib/visualizer/index.html deleted file mode 100644 index c2b2c33..0000000 --- a/web/pw-frontend/src/lib/visualizer/index.html +++ /dev/null @@ -1,102 +0,0 @@ -<!DOCTYPE html> -<html> - <head> - <meta charset="utf-8"> - <title>Hello wasm-pack!</title> - <link rel="stylesheet" type="text/css" href="static/res/style.css"> - </head> - <body> - <input type="file" id="fileselect" style="display: none"> - <div id=wrapper> - - <div id="main" class="loading"> - <canvas id="c"></canvas> - <div id="name"></div> - <div id="addbutton" class="button"></div> - - <div id="meta"> - <div id="turnCounter"> - 0 / 0 - </div> - <div> - <span>Ms per frame: </span> - <input type="number" id="speed" value="100"> - </div> - <div class="slidecontainer"> - <input type="range" min="0" max="1" value="1" class="slider" id="turnSlider"> - </div> - </div> - </div> - - <div class=".options" id=options> - <div class="option"> - Option one - </div> - <div class="option"> - Option two - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div><div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - <div class="option"> - Option three - </div><div class="option"> - Option three - </div> - <div class="option"> - Option three - </div> - </div> - - </div> - - - <noscript>This page contains webassembly and javascript content, please enable javascript in your browser.</noscript> - <script src="bootstrap.js"></script> - <script> - const URL = window.location.origin + window.location.pathname; - const LOCATION = URL.substring(0, URL.lastIndexOf("/") + 1); - - const game_location = LOCATION + "static/games/Chandra Garrett.json"; - const name = "Chandra Garrett"; - window.setTimeout( - () => visualizer.handle(game_location, name), 1000 - ) - </script> - </body> -</html> diff --git a/web/pw-frontend/src/lib/visualizer/index.ts b/web/pw-frontend/src/lib/visualizer/index.ts deleted file mode 100644 index 363a1c5..0000000 --- a/web/pw-frontend/src/lib/visualizer/index.ts +++ /dev/null @@ -1,666 +0,0 @@ -import { Game } from "planetwars-rs"; -// import { memory } from "planetwars-rs/planetwars_rs_bg"; -// const memory = planetwars_bg.memory; -import type { Dictionary } from './webgl/util'; -import type { BBox } from "./voronoi/voronoi-core"; - -import { - Resizer, - resizeCanvasToDisplaySize, - FPSCounter, - url_to_mesh, - Mesh, -} from "./webgl/util"; -import { - Shader, - Uniform4f, - Uniform3fv, - Uniform1f, - Uniform2f, - ShaderFactory, - Uniform3f, - UniformMatrix3fv, - UniformBool, -} from "./webgl/shader"; -import { Renderer } from "./webgl/renderer"; -import { VertexBuffer, IndexBuffer } from "./webgl/buffer"; -import { VertexBufferLayout, VertexArray } from "./webgl/vertexBufferLayout"; -import { defaultLabelFactory, LabelFactory, Align, Label } from "./webgl/text"; -import { VoronoiBuilder } from "./voronoi/voronoi"; - -// svg-mesh requires global to exist -(window as any).global = window; - - - -function to_bbox(box: number[]): BBox { - return { - xl: box[0], - xr: box[0] + box[2], - yt: box[1], - yb: box[1] + box[3], - }; -} - -// function f32v(ptr: number, size: number): Float32Array { -// return new Float32Array(memory.buffer, ptr, size); -// } - -// function i32v(ptr: number, size: number): Int32Array { -// return new Int32Array(memory.buffer, ptr, size); -// } - -export function set_game_name(name: string) { - ELEMENTS["name"].innerHTML = name; -} - -export function set_loading(loading: boolean) { - if (loading) { - if (!ELEMENTS["main"].classList.contains("loading")) { - ELEMENTS["main"].classList.add("loading"); - } - } else { - ELEMENTS["main"].classList.remove("loading"); - } -} - -const ELEMENTS: any = {}; -var CANVAS: any; -var RESOLUTION: any; -var GL: any; -var ms_per_frame: any; - -const LAYERS = { - vor: -1, // Background - planet: 1, - planet_label: 2, - ship: 3, - ship_label: 4, -}; - -const COUNTER = new FPSCounter(); - - - -export function init() { - [ - "name", - "turnCounter", - "main", - "turnSlider", - "fileselect", - "speed", - "canvas", - ].forEach((n) => (ELEMENTS[n] = document.getElementById(n))); - - CANVAS = ELEMENTS["canvas"]; - RESOLUTION = [CANVAS.width, CANVAS.height]; - - ms_per_frame = parseInt(ELEMENTS["speed"].value); - - GL = CANVAS.getContext("webgl"); - - GL.clearColor(0, 0, 0, 1); - GL.clear(GL.COLOR_BUFFER_BIT); - - GL.enable(GL.BLEND); - GL.blendFunc(GL.SRC_ALPHA, GL.ONE_MINUS_SRC_ALPHA); - - window.addEventListener( - "resize", - function () { - resizeCanvasToDisplaySize(CANVAS); - - if (game_instance) { - game_instance.on_resize(); - } - }, - { capture: false, passive: true } - ); - - ELEMENTS["turnSlider"].oninput = function () { - if (game_instance) { - game_instance.updateTurn(parseInt(ELEMENTS["turnSlider"].value)); - } - }; - - ELEMENTS["speed"].onchange = function () { - ms_per_frame = parseInt(ELEMENTS["speed"].value); - }; -} - -export class GameInstance { - resizer: Resizer; - game: Game; - - shader: Shader; - vor_shader: Shader; - image_shader: Shader; - - text_factory: LabelFactory; - planet_labels: Label[]; - ship_labels: Label[]; - - ship_ibo: IndexBuffer; - ship_vao: VertexArray; - // TODO: find a better way - max_num_ships: number; - - renderer: Renderer; - planet_count: number; - - vor_builder: VoronoiBuilder; - - vor_counter = 3; - use_vor = true; - playing = true; - time_stopped_delta = 0; - last_time = 0; - frame = -1; - - turn_count = 0; - - constructor( - game: Game, - meshes: Mesh[], - ship_mesh: Mesh, - shaders: Dictionary<ShaderFactory> - ) { - this.game = game; - const planets = game.get_planets(); - this.planet_count = planets.length; - - this.shader = shaders["normal"].create_shader(GL, { - MAX_CIRCLES: "" + planets.length, - }); - this.image_shader = shaders["image"].create_shader(GL); - this.vor_shader = shaders["vor"].create_shader(GL, { - PLANETS: "" + planets.length, - }); - - this.text_factory = defaultLabelFactory(GL, this.image_shader); - this.planet_labels = []; - this.ship_labels = []; - - this.resizer = new Resizer(CANVAS, [...game.get_viewbox()], true); - this.renderer = new Renderer(); - this.game.update_turn(0); - - // Setup key handling - document.addEventListener("keydown", this.handleKey.bind(this)); - - // List of [(x, y, r)] for all planets - this._create_voronoi(planets); - this._create_planets(planets, meshes); - - // create_shipes - this.ship_ibo = new IndexBuffer(GL, ship_mesh.cells); - const ship_positions = new VertexBuffer(GL, ship_mesh.positions); - const ship_layout = new VertexBufferLayout(); - ship_layout.push(GL.FLOAT, 3, 4, "a_position"); - this.ship_vao = new VertexArray(); - this.ship_vao.addBuffer(ship_positions, ship_layout); - this.max_num_ships = 0; - - // Set slider correctly - this.turn_count = game.turn_count(); - ELEMENTS["turnSlider"].max = this.turn_count - 1 + ""; - } - - push_state(state: string) { - this.game.push_state(state); - - if (this.frame == this.turn_count - 1) { - this.playing = true; - } - - // Set slider correctly - this.turn_count = this.game.turn_count(); - this.updateTurnCounters(); - } - - _create_voronoi(planets: Float32Array) { - const planet_points = []; - for (let i = 0; i < planets.length; i += 3) { - planet_points.push({ x: -planets[i], y: -planets[i + 1] }); - } - - const bbox = to_bbox(this.resizer.get_viewbox()); - - this.vor_builder = new VoronoiBuilder( - GL, - this.vor_shader, - planet_points, - bbox - ); - this.renderer.addRenderable(this.vor_builder.getRenderable(), LAYERS.vor); - } - - _create_planets(planets: Float32Array, meshes: Mesh[]) { - for (let i = 0; i < this.planet_count; i++) { - { - const transform = new UniformMatrix3fv([ - 1, - 0, - 0, - 0, - 1, - 0, - -planets[i * 3], - -planets[i * 3 + 1], - 1, - ]); - - const indexBuffer = new IndexBuffer( - GL, - meshes[i % meshes.length].cells - ); - const positionBuffer = new VertexBuffer( - GL, - meshes[i % meshes.length].positions - ); - - const layout = new VertexBufferLayout(); - layout.push(GL.FLOAT, 3, 4, "a_position"); - const vao = new VertexArray(); - vao.addBuffer(positionBuffer, layout); - - this.renderer.addToDraw( - indexBuffer, - vao, - this.shader, - { - u_trans: transform, - u_trans_next: transform, - }, - [], - LAYERS.planet - ); - } - - { - const transform = new UniformMatrix3fv([ - 1, - 0, - 0, - 0, - 1, - 0, - -planets[i * 3], - -planets[i * 3 + 1] - 1.2, - 1, - ]); - - const label = this.text_factory.build(GL, transform); - this.planet_labels.push(label); - this.renderer.addRenderable(label.getRenderable(), LAYERS.planet_label); - } - } - } - - on_resize() { - this.resizer = new Resizer(CANVAS, [...this.game.get_viewbox()], true); - const bbox = to_bbox(this.resizer.get_viewbox()); - this.vor_builder.resize(GL, bbox); - } - - _update_state() { - this._update_planets(); - this._update_ships(); - } - - _update_planets() { - const colours = this.game.get_planet_colors(); - const planet_ships = this.game.get_planet_ships(); - - this.vor_shader.uniform(GL, "u_planet_colours", new Uniform3fv(colours)); - - for (let i = 0; i < this.planet_count; i++) { - const u = new Uniform3f( - colours[i * 6], - colours[i * 6 + 1], - colours[i * 6 + 2] - ); - this.renderer.updateUniform( - i, - (us) => (us["u_color"] = u), - LAYERS.planet - ); - const u2 = new Uniform3f( - colours[i * 6 + 3], - colours[i * 6 + 4], - colours[i * 6 + 5] - ); - this.renderer.updateUniform( - i, - (us) => (us["u_color_next"] = u2), - LAYERS.planet - ); - - this.planet_labels[i].setText( - GL, - "*" + planet_ships[i], - Align.Middle, - Align.Begin - ); - } - } - - _update_ships() { - const ships = this.game.get_ship_locations(); - const labels = this.game.get_ship_label_locations(); - const ship_counts = this.game.get_ship_counts(); - const ship_colours = this.game.get_ship_colours(); - - for (let i = this.max_num_ships; i < ship_counts.length; i++) { - this.renderer.addToDraw( - this.ship_ibo, - this.ship_vao, - this.shader, - {}, - [], - LAYERS.ship - ); - - const label = this.text_factory.build(GL); - this.ship_labels.push(label); - this.renderer.addRenderable(label.getRenderable(), LAYERS.ship_label); - } - if (ship_counts.length > this.max_num_ships) - this.max_num_ships = ship_counts.length; - - // TODO: actually remove obsolete ships - for (let i = 0; i < this.max_num_ships; i++) { - if (i < ship_counts.length) { - this.ship_labels[i].setText( - GL, - "" + ship_counts[i], - Align.Middle, - Align.Middle - ); - - this.renderer.enableRenderable(i, LAYERS.ship); - this.renderer.enableRenderable(i, LAYERS.ship_label); - - const u = new Uniform3f( - ship_colours[i * 3], - ship_colours[i * 3 + 1], - ship_colours[i * 3 + 2] - ); - - const t1 = new UniformMatrix3fv(ships.slice(i * 18, i * 18 + 9)); - const t2 = new UniformMatrix3fv(ships.slice(i * 18 + 9, i * 18 + 18)); - - const tl1 = new UniformMatrix3fv(labels.slice(i * 18, i * 18 + 9)); - const tl2 = new UniformMatrix3fv(labels.slice(i * 18 + 9, i * 18 + 18)); - - this.renderer.updateUniform( - i, - (us) => { - us["u_color"] = u; - us["u_color_next"] = u; - us["u_trans"] = t1; - us["u_trans_next"] = t2; - }, - LAYERS.ship - ); - - this.renderer.updateUniform( - i, - (us) => { - us["u_trans"] = tl1; - us["u_trans_next"] = tl2; - }, - LAYERS.ship_label - ); - } else { - this.renderer.disableRenderable(i, LAYERS.ship); - this.renderer.disableRenderable(i, LAYERS.ship_label); - } - } - } - - render(time: number) { - COUNTER.frame(time); - - if (COUNTER.delta(time) < 30) { - this.vor_counter = Math.min(3, this.vor_counter + 1); - } else { - this.vor_counter = Math.max(-3, this.vor_counter - 1); - } - - if (this.vor_counter < -2) { - this.use_vor = false; - } - - // If not playing, still reder with different viewbox, so people can still pan etc. - if (!this.playing) { - this.last_time = time; - - this.shader.uniform( - GL, - "u_viewbox", - new Uniform4f(this.resizer.get_viewbox()) - ); - this.vor_shader.uniform( - GL, - "u_viewbox", - new Uniform4f(this.resizer.get_viewbox()) - ); - this.image_shader.uniform( - GL, - "u_viewbox", - new Uniform4f(this.resizer.get_viewbox()) - ); - - this.renderer.render(GL); - return; - } - - // Check if turn is still correct - if (time > this.last_time + ms_per_frame) { - this.last_time = time; - this.updateTurn(this.frame + 1); - if (this.frame == this.turn_count - 1) { - this.playing = false; - } - } - - // Do GL things - GL.bindFramebuffer(GL.FRAMEBUFFER, null); - GL.viewport(0, 0, GL.canvas.width, GL.canvas.height); - GL.clear(GL.COLOR_BUFFER_BIT | GL.DEPTH_BUFFER_BIT); - - this.vor_shader.uniform( - GL, - "u_time", - new Uniform1f((time - this.last_time) / ms_per_frame) - ); - this.vor_shader.uniform( - GL, - "u_viewbox", - new Uniform4f(this.resizer.get_viewbox()) - ); - this.vor_shader.uniform(GL, "u_resolution", new Uniform2f(RESOLUTION)); - this.vor_shader.uniform(GL, "u_vor", new UniformBool(this.use_vor)); - - this.shader.uniform( - GL, - "u_time", - new Uniform1f((time - this.last_time) / ms_per_frame) - ); - this.shader.uniform( - GL, - "u_mouse", - new Uniform2f(this.resizer.get_mouse_pos()) - ); - this.shader.uniform( - GL, - "u_viewbox", - new Uniform4f(this.resizer.get_viewbox()) - ); - this.shader.uniform(GL, "u_resolution", new Uniform2f(RESOLUTION)); - - this.image_shader.uniform( - GL, - "u_time", - new Uniform1f((time - this.last_time) / ms_per_frame) - ); - this.image_shader.uniform( - GL, - "u_mouse", - new Uniform2f(this.resizer.get_mouse_pos()) - ); - this.image_shader.uniform( - GL, - "u_viewbox", - new Uniform4f(this.resizer.get_viewbox()) - ); - this.image_shader.uniform(GL, "u_resolution", new Uniform2f(RESOLUTION)); - - // Render - this.renderer.render(GL); - - COUNTER.frame_end(); - } - - updateTurn(turn: number) { - this.frame = Math.max(0, turn); - const new_frame = this.game.update_turn(this.frame); - if (new_frame < this.frame) { - this.frame = new_frame; - this.playing = false; - } else { - this._update_state(); - this.playing = true; - } - - this.updateTurnCounters(); - } - - updateTurnCounters() { - ELEMENTS["turnCounter"].innerHTML = - this.frame + " / " + (this.turn_count - 1); - ELEMENTS["turnSlider"].value = this.frame + ""; - ELEMENTS["turnSlider"].max = this.turn_count - 1 + ""; - } - - handleKey(event: KeyboardEvent) { - // Space - if (event.keyCode == 32) { - if (this.playing) { - this.playing = false; - } else { - this.playing = true; - } - } - - // Arrow left - if (event.keyCode == 37) { - // This feels more natural than -1 what it should be, I think - this.updateTurn(this.frame - 2); - } - - // Arrow right - if (event.keyCode == 39) { - this.updateTurn(this.frame + 1); - } - - // d key - if (event.keyCode == 68) { - ELEMENTS["speed"].value = ms_per_frame + 10 + ""; - ELEMENTS["speed"].onchange(undefined); - } - - // a key - if (event.keyCode == 65) { - ELEMENTS["speed"].value = Math.max(ms_per_frame - 10, 0) + ""; - ELEMENTS["speed"].onchange(undefined); - } - } -} - -var game_instance: GameInstance; -var meshes: Mesh[]; -var shaders: Dictionary<ShaderFactory>; - -export async function set_instance(source: string): Promise<GameInstance> { - if (!meshes || !shaders) { - const mesh_promises = ["ship.svg", "earth.svg", "mars.svg", "venus.svg"] - .map((name) => "/static/res/assets/" + name) - .map(url_to_mesh); - - const shader_promies = [ - (async () => - <[string, ShaderFactory]>[ - "normal", - await ShaderFactory.create_factory( - "/static/shaders/frag/simple.glsl", - "/static/shaders/vert/simple.glsl" - ), - ])(), - (async () => - <[string, ShaderFactory]>[ - "vor", - await ShaderFactory.create_factory( - "/static/shaders/frag/vor.glsl", - "/static/shaders/vert/vor.glsl" - ), - ])(), - (async () => - <[string, ShaderFactory]>[ - "image", - await ShaderFactory.create_factory( - "/static/shaders/frag/image.glsl", - "/static/shaders/vert/simple.glsl" - ), - ])(), - ]; - let shaders_array: [string, ShaderFactory][]; - [meshes, shaders_array] = await Promise.all([ - Promise.all(mesh_promises), - Promise.all(shader_promies), - ]); - - shaders = {}; - shaders_array.forEach(([name, fac]) => (shaders[name] = fac)); - } - - resizeCanvasToDisplaySize(CANVAS); - - game_instance = new GameInstance( - Game.new(source), - meshes.slice(1), - meshes[0], - shaders - ); - - set_loading(false); - start(); - return game_instance; -} - -var _animating = false; - -export function start() { - if (_animating) { - // already running - return; - } - _animating = true; - requestAnimationFrame(step); -} - -export function stop() { - _animating = false; -} - -function step(time: number) { - if (game_instance) { - game_instance.render(time); - } - - if (_animating) { - requestAnimationFrame(step); - } -} diff --git a/web/pw-frontend/src/lib/visualizer/src/games.ts b/web/pw-frontend/src/lib/visualizer/src/games.ts deleted file mode 100644 index 4b9e7e2..0000000 --- a/web/pw-frontend/src/lib/visualizer/src/games.ts +++ /dev/null @@ -1,47 +0,0 @@ - -import { set_game_name, set_loading, set_instance } from '../index' - -var game_name, game_file; - -document.getElementById("addbutton").onclick = function () { - const loc = window.location; - const query = `?game=${game_file}&name=${game_name}`; - navigator.clipboard.writeText(loc.origin + loc.pathname + encodeURI(query)).then(() => { - console.log("Success"); - }, () => { - console.log("Failed"); - }); -} - -async function on_load() { - const options = document.getElementsByClassName("options"); - const urlVars = new URLSearchParams(window.location.search); - - if (urlVars.get("game") && urlVars.get("name")) { - console.log(urlVars.get("game") + ' ' + urlVars.get("name")) - handle(urlVars.get("game"), urlVars.get("name")) - } else if (options[0]) { - const options_div = <HTMLDivElement>options[0]; - if (options_div.children[0]) { - options_div.children[0].dispatchEvent(new Event('click')); - } - } -} - -window.addEventListener("load", on_load, false); - -export function handle(location: string, name: string) { - game_file = location; - game_name = name; - - set_loading(true); - - fetch(location) - .then((r) => r.text()) - .then((response) => { - set_instance(response); - set_game_name(name); - }).catch(console.error); -} - -on_load(); diff --git a/web/pw-frontend/src/lib/visualizer/style.css b/web/pw-frontend/src/lib/visualizer/style.css deleted file mode 100644 index 8c5119e..0000000 --- a/web/pw-frontend/src/lib/visualizer/style.css +++ /dev/null @@ -1,309 +0,0 @@ - * { - margin: 0; - padding: 0; - } - - body { - background-color: #333; - } - - p { - padding: 3px 0; - } - - #wrapper { - max-height: 100%; - min-height: 100%; - width: 100%; - height: 100%; - display: flex; - } - - #main { - height: 100%; - flex-grow: 1; - position: relative; - } - - #name { - position: absolute; - top: 10px; - left: 10px; - color: white; - } - - #meta { - padding: 10px 2%; - color: white; - position: absolute; - bottom: 0; - width: 96%; - } - - .options { - background-color: black; - max-width: 300px; - width: 20%; - min-width: 150px; - height: 100%; - display: flex; - flex-direction: column; - overflow-y: auto; - } - - .option { - color: white; - margin: 0 0 20px 0; - padding: 10px; - background-color: #333; - } - - .option:last-child { - margin: 0; - } - - .option:hover { - background-color: #777; - } - - .lds-roller { - display: none; - } - - .loading>.lds-roller { - display: inline-block; - } - - .lds-roller { - position: absolute; - left: 50%; - top: 50%; - transform: translate(-50%, -50%); - width: 80px; - height: 80px; - } - - .lds-roller div { - animation: lds-roller 1.2s cubic-bezier(0.5, 0, 0.5, 1) infinite; - transform-origin: 40px 40px; - } - - .lds-roller div:after { - content: " "; - display: block; - position: absolute; - width: 7px; - height: 7px; - border-radius: 50%; - background: #fff; - margin: -4px 0 0 -4px; - } - - .lds-roller div:nth-child(1) { - animation-delay: -0.036s; - } - - .lds-roller div:nth-child(1):after { - top: 63px; - left: 63px; - } - - .lds-roller div:nth-child(2) { - animation-delay: -0.072s; - } - - .lds-roller div:nth-child(2):after { - top: 68px; - left: 56px; - } - - .lds-roller div:nth-child(3) { - animation-delay: -0.108s; - } - - .lds-roller div:nth-child(3):after { - top: 71px; - left: 48px; - } - - .lds-roller div:nth-child(4) { - animation-delay: -0.144s; - } - - .lds-roller div:nth-child(4):after { - top: 72px; - left: 40px; - } - - .lds-roller div:nth-child(5) { - animation-delay: -0.18s; - } - - .lds-roller div:nth-child(5):after { - top: 71px; - left: 32px; - } - - .lds-roller div:nth-child(6) { - animation-delay: -0.216s; - } - - .lds-roller div:nth-child(6):after { - top: 68px; - left: 24px; - } - - .lds-roller div:nth-child(7) { - animation-delay: -0.252s; - } - - .lds-roller div:nth-child(7):after { - top: 63px; - left: 17px; - } - - .lds-roller div:nth-child(8) { - animation-delay: -0.288s; - } - - .lds-roller div:nth-child(8):after { - top: 56px; - left: 12px; - } - - @keyframes lds-roller { - 0% { - transform: rotate(0deg); - } - 100% { - transform: rotate(360deg); - } - } - - #speed { - width: 100px; - } - - #canvas { - position: relative; - background-color: black; - width: 100%; - height: 100%; - } - - .button { - position: absolute; - top: 10px; - right: 10px; - width: 0; - height: 0; - } - - .button::before { - content: ""; - display: block; - float: left; - margin: 0 -20px 0 0; - font-family: 'fontawesome'; - content: "\f1e1"; - transform: translate(-1em, 0px); - color: antiquewhite; - font-size: 1.5em; - } - - .button:hover::before { - color: #ff7f00; - } - /* ---------------------------------------------- - * Generated by Animista on 2019-9-17 14:35:13 - * Licensed under FreeBSD License. - * See http://animista.net/license for more info. - * w: http://animista.net, t: @cssanimista - * ---------------------------------------------- */ - /** - * ---------------------------------------- - * animation slide-top - * ---------------------------------------- - */ - - @-webkit-keyframes slide-top { - 0% { - -webkit-transform: translate(-50%, 50%); - transform: translate(-50%, 50%); - } - 100% { - -webkit-transform: translate(-50%, -150%); - transform: translate(-50%, -150%); - } - } - - @keyframes slide-top { - 0% { - -webkit-transform: translate(-50%, 50%); - transform: translate(-50%, 50%); - } - 100% { - -webkit-transform: translate(-50%, -150%); - transform: translate(-50%, -150%); - } - } - /** - * ---------------------------------------- - * Copy from https://www.w3schools.com/howto/howto_js_rangeslider.asp - * ---------------------------------------- - */ - - .slidecontainer { - margin-top: 10px; - width: 100%; - /* Width of the outside container */ - } - - .slider { - -webkit-appearance: none; - width: 100%; - height: 15px; - border-radius: 5px; - background: #d3d3d3; - outline: none; - opacity: 0.7; - -webkit-transition: .2s; - transition: opacity .2s; - } - - .slider::-webkit-slider-thumb { - -webkit-appearance: none; - appearance: none; - width: 25px; - height: 25px; - border-radius: 50%; - background: #ff7000; - cursor: pointer; - } - - .slider::-moz-range-thumb { - width: 25px; - height: 25px; - border-radius: 50%; - background: #ff7000; - cursor: pointer; - } - - ::-webkit-scrollbar-track { - -webkit-box-shadow: inset 0 0 6px rgba(0, 0, 0, 0.3); - box-shadow: inset 0 0 6px rgba(0, 0, 0, 0.3); - border-radius: 10px; - background-color: #444; - border-radius: 10px; - } - - ::-webkit-scrollbar { - width: 10px; - background-color: #444; - } - - ::-webkit-scrollbar-thumb { - border-radius: 10px; - background-color: #F90; - background-image: -webkit-linear-gradient(45deg, rgba(255, 255, 255, .2) 25%, transparent 25%, transparent 50%, rgba(255, 255, 255, .2) 50%, rgba(255, 255, 255, .2) 75%, transparent 75%, transparent) - }
\ No newline at end of file diff --git a/web/pw-frontend/src/lib/visualizer/voronoi/voronoi-core.d.ts b/web/pw-frontend/src/lib/visualizer/voronoi/voronoi-core.d.ts deleted file mode 100644 index e908fbb..0000000 --- a/web/pw-frontend/src/lib/visualizer/voronoi/voronoi-core.d.ts +++ /dev/null @@ -1,56 +0,0 @@ - -declare namespace Voronoi { - class Point { - x: number; - y: number; - } - - class Site { - x: number; - y: number; - voronoiId: number; - } - - class Cell { - site: Site; - halfedges: HalfEdge[]; - closeMe: boolean; - } - - class Edge { - lSite: Site; - rSite: Site; - vb: Point; - va: Point; - } - - class HalfEdge { - site: Site; - edge: Edge; - angle: number; - getStartpoint(): Point; - getEndpoint(): Point; - } - - class BBox { - xl: number; - xr: number; - yt: number; - yb: number; - } - - class VoronoiDiagram { - site: any; - cells: Cell[]; - edges: Edge[]; - vertices: Point[]; - execTime: number; - } -} - -declare class Voronoi { - constructor(); - compute(sites: Voronoi.Point[], bbox: Voronoi.BBox): Voronoi.VoronoiDiagram; -} - -export = Voronoi; diff --git a/web/pw-frontend/src/lib/visualizer/voronoi/voronoi-core.js b/web/pw-frontend/src/lib/visualizer/voronoi/voronoi-core.js deleted file mode 100644 index 9dcc5b3..0000000 --- a/web/pw-frontend/src/lib/visualizer/voronoi/voronoi-core.js +++ /dev/null @@ -1,1726 +0,0 @@ -/*! -Copyright (C) 2010-2013 Raymond Hill: https://github.com/gorhill/Javascript-Voronoi -MIT License: See https://github.com/gorhill/Javascript-Voronoi/LICENSE.md -*/ -/* -Author: Raymond Hill (rhill@raymondhill.net) -Contributor: Jesse Morgan (morgajel@gmail.com) -File: rhill-voronoi-core.js -Version: 0.98 -Date: January 21, 2013 -Description: This is my personal Javascript implementation of -Steven Fortune's algorithm to compute Voronoi diagrams. - -License: See https://github.com/gorhill/Javascript-Voronoi/LICENSE.md -Credits: See https://github.com/gorhill/Javascript-Voronoi/CREDITS.md -History: See https://github.com/gorhill/Javascript-Voronoi/CHANGELOG.md - -## Usage: - - var sites = [{x:300,y:300}, {x:100,y:100}, {x:200,y:500}, {x:250,y:450}, {x:600,y:150}]; - // xl, xr means x left, x right - // yt, yb means y top, y bottom - var bbox = {xl:0, xr:800, yt:0, yb:600}; - var voronoi = new Voronoi(); - // pass an object which exhibits xl, xr, yt, yb properties. The bounding - // box will be used to connect unbound edges, and to close open cells - result = voronoi.compute(sites, bbox); - // render, further analyze, etc. - -Return value: - An object with the following properties: - - result.vertices = an array of unordered, unique Voronoi.Vertex objects making - up the Voronoi diagram. - result.edges = an array of unordered, unique Voronoi.Edge objects making up - the Voronoi diagram. - result.cells = an array of Voronoi.Cell object making up the Voronoi diagram. - A Cell object might have an empty array of halfedges, meaning no Voronoi - cell could be computed for a particular cell. - result.execTime = the time it took to compute the Voronoi diagram, in - milliseconds. - -Voronoi.Vertex object: - x: The x position of the vertex. - y: The y position of the vertex. - -Voronoi.Edge object: - lSite: the Voronoi site object at the left of this Voronoi.Edge object. - rSite: the Voronoi site object at the right of this Voronoi.Edge object (can - be null). - va: an object with an 'x' and a 'y' property defining the start point - (relative to the Voronoi site on the left) of this Voronoi.Edge object. - vb: an object with an 'x' and a 'y' property defining the end point - (relative to Voronoi site on the left) of this Voronoi.Edge object. - - For edges which are used to close open cells (using the supplied bounding - box), the rSite property will be null. - -Voronoi.Cell object: - site: the Voronoi site object associated with the Voronoi cell. - halfedges: an array of Voronoi.Halfedge objects, ordered counterclockwise, - defining the polygon for this Voronoi cell. - -Voronoi.Halfedge object: - site: the Voronoi site object owning this Voronoi.Halfedge object. - edge: a reference to the unique Voronoi.Edge object underlying this - Voronoi.Halfedge object. - getStartpoint(): a method returning an object with an 'x' and a 'y' property - for the start point of this halfedge. Keep in mind halfedges are always - countercockwise. - getEndpoint(): a method returning an object with an 'x' and a 'y' property - for the end point of this halfedge. Keep in mind halfedges are always - countercockwise. - -TODO: Identify opportunities for performance improvement. - -TODO: Let the user close the Voronoi cells, do not do it automatically. Not only let - him close the cells, but also allow him to close more than once using a different - bounding box for the same Voronoi diagram. -*/ - -/*global Math */ - -// --------------------------------------------------------------------------- - -function Voronoi() { - this.vertices = null; - this.edges = null; - this.cells = null; - this.toRecycle = null; - this.beachsectionJunkyard = []; - this.circleEventJunkyard = []; - this.vertexJunkyard = []; - this.edgeJunkyard = []; - this.cellJunkyard = []; - } - -// --------------------------------------------------------------------------- - -Voronoi.prototype.reset = function() { - if (!this.beachline) { - this.beachline = new this.RBTree(); - } - // Move leftover beachsections to the beachsection junkyard. - if (this.beachline.root) { - var beachsection = this.beachline.getFirst(this.beachline.root); - while (beachsection) { - this.beachsectionJunkyard.push(beachsection); // mark for reuse - beachsection = beachsection.rbNext; - } - } - this.beachline.root = null; - if (!this.circleEvents) { - this.circleEvents = new this.RBTree(); - } - this.circleEvents.root = this.firstCircleEvent = null; - this.vertices = []; - this.edges = []; - this.cells = []; - }; - -Voronoi.prototype.sqrt = Math.sqrt; -Voronoi.prototype.abs = Math.abs; -Voronoi.prototype.ε = Voronoi.ε = 1e-9; -Voronoi.prototype.invε = Voronoi.invε = 1.0 / Voronoi.ε; -Voronoi.prototype.equalWithEpsilon = function(a,b){return this.abs(a-b)<1e-9;}; -Voronoi.prototype.greaterThanWithEpsilon = function(a,b){return a-b>1e-9;}; -Voronoi.prototype.greaterThanOrEqualWithEpsilon = function(a,b){return b-a<1e-9;}; -Voronoi.prototype.lessThanWithEpsilon = function(a,b){return b-a>1e-9;}; -Voronoi.prototype.lessThanOrEqualWithEpsilon = function(a,b){return a-b<1e-9;}; - -// --------------------------------------------------------------------------- -// Red-Black tree code (based on C version of "rbtree" by Franck Bui-Huu -// https://github.com/fbuihuu/libtree/blob/master/rb.c - -Voronoi.prototype.RBTree = function() { - this.root = null; - }; - -Voronoi.prototype.RBTree.prototype.rbInsertSuccessor = function(node, successor) { - var parent; - if (node) { - // >>> rhill 2011-05-27: Performance: cache previous/next nodes - successor.rbPrevious = node; - successor.rbNext = node.rbNext; - if (node.rbNext) { - node.rbNext.rbPrevious = successor; - } - node.rbNext = successor; - // <<< - if (node.rbRight) { - // in-place expansion of node.rbRight.getFirst(); - node = node.rbRight; - while (node.rbLeft) {node = node.rbLeft;} - node.rbLeft = successor; - } - else { - node.rbRight = successor; - } - parent = node; - } - // rhill 2011-06-07: if node is null, successor must be inserted - // to the left-most part of the tree - else if (this.root) { - node = this.getFirst(this.root); - // >>> Performance: cache previous/next nodes - successor.rbPrevious = null; - successor.rbNext = node; - node.rbPrevious = successor; - // <<< - node.rbLeft = successor; - parent = node; - } - else { - // >>> Performance: cache previous/next nodes - successor.rbPrevious = successor.rbNext = null; - // <<< - this.root = successor; - parent = null; - } - successor.rbLeft = successor.rbRight = null; - successor.rbParent = parent; - successor.rbRed = true; - // Fixup the modified tree by recoloring nodes and performing - // rotations (2 at most) hence the red-black tree properties are - // preserved. - var grandpa, uncle; - node = successor; - while (parent && parent.rbRed) { - grandpa = parent.rbParent; - if (parent === grandpa.rbLeft) { - uncle = grandpa.rbRight; - if (uncle && uncle.rbRed) { - parent.rbRed = uncle.rbRed = false; - grandpa.rbRed = true; - node = grandpa; - } - else { - if (node === parent.rbRight) { - this.rbRotateLeft(parent); - node = parent; - parent = node.rbParent; - } - parent.rbRed = false; - grandpa.rbRed = true; - this.rbRotateRight(grandpa); - } - } - else { - uncle = grandpa.rbLeft; - if (uncle && uncle.rbRed) { - parent.rbRed = uncle.rbRed = false; - grandpa.rbRed = true; - node = grandpa; - } - else { - if (node === parent.rbLeft) { - this.rbRotateRight(parent); - node = parent; - parent = node.rbParent; - } - parent.rbRed = false; - grandpa.rbRed = true; - this.rbRotateLeft(grandpa); - } - } - parent = node.rbParent; - } - this.root.rbRed = false; - }; - -Voronoi.prototype.RBTree.prototype.rbRemoveNode = function(node) { - // >>> rhill 2011-05-27: Performance: cache previous/next nodes - if (node.rbNext) { - node.rbNext.rbPrevious = node.rbPrevious; - } - if (node.rbPrevious) { - node.rbPrevious.rbNext = node.rbNext; - } - node.rbNext = node.rbPrevious = null; - // <<< - var parent = node.rbParent, - left = node.rbLeft, - right = node.rbRight, - next; - if (!left) { - next = right; - } - else if (!right) { - next = left; - } - else { - next = this.getFirst(right); - } - if (parent) { - if (parent.rbLeft === node) { - parent.rbLeft = next; - } - else { - parent.rbRight = next; - } - } - else { - this.root = next; - } - // enforce red-black rules - var isRed; - if (left && right) { - isRed = next.rbRed; - next.rbRed = node.rbRed; - next.rbLeft = left; - left.rbParent = next; - if (next !== right) { - parent = next.rbParent; - next.rbParent = node.rbParent; - node = next.rbRight; - parent.rbLeft = node; - next.rbRight = right; - right.rbParent = next; - } - else { - next.rbParent = parent; - parent = next; - node = next.rbRight; - } - } - else { - isRed = node.rbRed; - node = next; - } - // 'node' is now the sole successor's child and 'parent' its - // new parent (since the successor can have been moved) - if (node) { - node.rbParent = parent; - } - // the 'easy' cases - if (isRed) {return;} - if (node && node.rbRed) { - node.rbRed = false; - return; - } - // the other cases - var sibling; - do { - if (node === this.root) { - break; - } - if (node === parent.rbLeft) { - sibling = parent.rbRight; - if (sibling.rbRed) { - sibling.rbRed = false; - parent.rbRed = true; - this.rbRotateLeft(parent); - sibling = parent.rbRight; - } - if ((sibling.rbLeft && sibling.rbLeft.rbRed) || (sibling.rbRight && sibling.rbRight.rbRed)) { - if (!sibling.rbRight || !sibling.rbRight.rbRed) { - sibling.rbLeft.rbRed = false; - sibling.rbRed = true; - this.rbRotateRight(sibling); - sibling = parent.rbRight; - } - sibling.rbRed = parent.rbRed; - parent.rbRed = sibling.rbRight.rbRed = false; - this.rbRotateLeft(parent); - node = this.root; - break; - } - } - else { - sibling = parent.rbLeft; - if (sibling.rbRed) { - sibling.rbRed = false; - parent.rbRed = true; - this.rbRotateRight(parent); - sibling = parent.rbLeft; - } - if ((sibling.rbLeft && sibling.rbLeft.rbRed) || (sibling.rbRight && sibling.rbRight.rbRed)) { - if (!sibling.rbLeft || !sibling.rbLeft.rbRed) { - sibling.rbRight.rbRed = false; - sibling.rbRed = true; - this.rbRotateLeft(sibling); - sibling = parent.rbLeft; - } - sibling.rbRed = parent.rbRed; - parent.rbRed = sibling.rbLeft.rbRed = false; - this.rbRotateRight(parent); - node = this.root; - break; - } - } - sibling.rbRed = true; - node = parent; - parent = parent.rbParent; - } while (!node.rbRed); - if (node) {node.rbRed = false;} - }; - -Voronoi.prototype.RBTree.prototype.rbRotateLeft = function(node) { - var p = node, - q = node.rbRight, // can't be null - parent = p.rbParent; - if (parent) { - if (parent.rbLeft === p) { - parent.rbLeft = q; - } - else { - parent.rbRight = q; - } - } - else { - this.root = q; - } - q.rbParent = parent; - p.rbParent = q; - p.rbRight = q.rbLeft; - if (p.rbRight) { - p.rbRight.rbParent = p; - } - q.rbLeft = p; - }; - -Voronoi.prototype.RBTree.prototype.rbRotateRight = function(node) { - var p = node, - q = node.rbLeft, // can't be null - parent = p.rbParent; - if (parent) { - if (parent.rbLeft === p) { - parent.rbLeft = q; - } - else { - parent.rbRight = q; - } - } - else { - this.root = q; - } - q.rbParent = parent; - p.rbParent = q; - p.rbLeft = q.rbRight; - if (p.rbLeft) { - p.rbLeft.rbParent = p; - } - q.rbRight = p; - }; - -Voronoi.prototype.RBTree.prototype.getFirst = function(node) { - while (node.rbLeft) { - node = node.rbLeft; - } - return node; - }; - -Voronoi.prototype.RBTree.prototype.getLast = function(node) { - while (node.rbRight) { - node = node.rbRight; - } - return node; - }; - -// --------------------------------------------------------------------------- -// Diagram methods - -Voronoi.prototype.Diagram = function(site) { - this.site = site; - }; - -// --------------------------------------------------------------------------- -// Cell methods - -Voronoi.prototype.Cell = function(site) { - this.site = site; - this.halfedges = []; - this.closeMe = false; - }; - -Voronoi.prototype.Cell.prototype.init = function(site) { - this.site = site; - this.halfedges = []; - this.closeMe = false; - return this; - }; - -Voronoi.prototype.createCell = function(site) { - var cell = this.cellJunkyard.pop(); - if ( cell ) { - return cell.init(site); - } - return new this.Cell(site); - }; - -Voronoi.prototype.Cell.prototype.prepareHalfedges = function() { - var halfedges = this.halfedges, - iHalfedge = halfedges.length, - edge; - // get rid of unused halfedges - // rhill 2011-05-27: Keep it simple, no point here in trying - // to be fancy: dangling edges are a typically a minority. - while (iHalfedge--) { - edge = halfedges[iHalfedge].edge; - if (!edge.vb || !edge.va) { - halfedges.splice(iHalfedge,1); - } - } - - // rhill 2011-05-26: I tried to use a binary search at insertion - // time to keep the array sorted on-the-fly (in Cell.addHalfedge()). - // There was no real benefits in doing so, performance on - // Firefox 3.6 was improved marginally, while performance on - // Opera 11 was penalized marginally. - halfedges.sort(function(a,b){return b.angle-a.angle;}); - return halfedges.length; - }; - -// Return a list of the neighbor Ids -Voronoi.prototype.Cell.prototype.getNeighborIds = function() { - var neighbors = [], - iHalfedge = this.halfedges.length, - edge; - while (iHalfedge--){ - edge = this.halfedges[iHalfedge].edge; - if (edge.lSite !== null && edge.lSite.voronoiId != this.site.voronoiId) { - neighbors.push(edge.lSite.voronoiId); - } - else if (edge.rSite !== null && edge.rSite.voronoiId != this.site.voronoiId){ - neighbors.push(edge.rSite.voronoiId); - } - } - return neighbors; - }; - -// Compute bounding box -// -Voronoi.prototype.Cell.prototype.getBbox = function() { - var halfedges = this.halfedges, - iHalfedge = halfedges.length, - xmin = Infinity, - ymin = Infinity, - xmax = -Infinity, - ymax = -Infinity, - v, vx, vy; - while (iHalfedge--) { - v = halfedges[iHalfedge].getStartpoint(); - vx = v.x; - vy = v.y; - if (vx < xmin) {xmin = vx;} - if (vy < ymin) {ymin = vy;} - if (vx > xmax) {xmax = vx;} - if (vy > ymax) {ymax = vy;} - // we dont need to take into account end point, - // since each end point matches a start point - } - return { - x: xmin, - y: ymin, - width: xmax-xmin, - height: ymax-ymin - }; - }; - -// Return whether a point is inside, on, or outside the cell: -// -1: point is outside the perimeter of the cell -// 0: point is on the perimeter of the cell -// 1: point is inside the perimeter of the cell -// -Voronoi.prototype.Cell.prototype.pointIntersection = function(x, y) { - // Check if point in polygon. Since all polygons of a Voronoi - // diagram are convex, then: - // http://paulbourke.net/geometry/polygonmesh/ - // Solution 3 (2D): - // "If the polygon is convex then one can consider the polygon - // "as a 'path' from the first vertex. A point is on the interior - // "of this polygons if it is always on the same side of all the - // "line segments making up the path. ... - // "(y - y0) (x1 - x0) - (x - x0) (y1 - y0) - // "if it is less than 0 then P is to the right of the line segment, - // "if greater than 0 it is to the left, if equal to 0 then it lies - // "on the line segment" - var halfedges = this.halfedges, - iHalfedge = halfedges.length, - halfedge, - p0, p1, r; - while (iHalfedge--) { - halfedge = halfedges[iHalfedge]; - p0 = halfedge.getStartpoint(); - p1 = halfedge.getEndpoint(); - r = (y-p0.y)*(p1.x-p0.x)-(x-p0.x)*(p1.y-p0.y); - if (!r) { - return 0; - } - if (r > 0) { - return -1; - } - } - return 1; - }; - -// --------------------------------------------------------------------------- -// Edge methods -// - -Voronoi.prototype.Vertex = function(x, y) { - this.x = x; - this.y = y; - }; - -Voronoi.prototype.Edge = function(lSite, rSite) { - this.lSite = lSite; - this.rSite = rSite; - this.va = this.vb = null; - }; - -Voronoi.prototype.Halfedge = function(edge, lSite, rSite) { - this.site = lSite; - this.edge = edge; - // 'angle' is a value to be used for properly sorting the - // halfsegments counterclockwise. By convention, we will - // use the angle of the line defined by the 'site to the left' - // to the 'site to the right'. - // However, border edges have no 'site to the right': thus we - // use the angle of line perpendicular to the halfsegment (the - // edge should have both end points defined in such case.) - if (rSite) { - this.angle = Math.atan2(rSite.y-lSite.y, rSite.x-lSite.x); - } - else { - var va = edge.va, - vb = edge.vb; - // rhill 2011-05-31: used to call getStartpoint()/getEndpoint(), - // but for performance purpose, these are expanded in place here. - this.angle = edge.lSite === lSite ? - Math.atan2(vb.x-va.x, va.y-vb.y) : - Math.atan2(va.x-vb.x, vb.y-va.y); - } - }; - -Voronoi.prototype.createHalfedge = function(edge, lSite, rSite) { - return new this.Halfedge(edge, lSite, rSite); - }; - -Voronoi.prototype.Halfedge.prototype.getStartpoint = function() { - return this.edge.lSite === this.site ? this.edge.va : this.edge.vb; - }; - -Voronoi.prototype.Halfedge.prototype.getEndpoint = function() { - return this.edge.lSite === this.site ? this.edge.vb : this.edge.va; - }; - - - -// this create and add a vertex to the internal collection - -Voronoi.prototype.createVertex = function(x, y) { - var v = this.vertexJunkyard.pop(); - if ( !v ) { - v = new this.Vertex(x, y); - } - else { - v.x = x; - v.y = y; - } - this.vertices.push(v); - return v; - }; - -// this create and add an edge to internal collection, and also create -// two halfedges which are added to each site's counterclockwise array -// of halfedges. - -Voronoi.prototype.createEdge = function(lSite, rSite, va, vb) { - var edge = this.edgeJunkyard.pop(); - if ( !edge ) { - edge = new this.Edge(lSite, rSite); - } - else { - edge.lSite = lSite; - edge.rSite = rSite; - edge.va = edge.vb = null; - } - - this.edges.push(edge); - if (va) { - this.setEdgeStartpoint(edge, lSite, rSite, va); - } - if (vb) { - this.setEdgeEndpoint(edge, lSite, rSite, vb); - } - this.cells[lSite.voronoiId].halfedges.push(this.createHalfedge(edge, lSite, rSite)); - this.cells[rSite.voronoiId].halfedges.push(this.createHalfedge(edge, rSite, lSite)); - return edge; - }; - -Voronoi.prototype.createBorderEdge = function(lSite, va, vb) { - var edge = this.edgeJunkyard.pop(); - if ( !edge ) { - edge = new this.Edge(lSite, null); - } - else { - edge.lSite = lSite; - edge.rSite = null; - } - edge.va = va; - edge.vb = vb; - this.edges.push(edge); - return edge; - }; - -Voronoi.prototype.setEdgeStartpoint = function(edge, lSite, rSite, vertex) { - if (!edge.va && !edge.vb) { - edge.va = vertex; - edge.lSite = lSite; - edge.rSite = rSite; - } - else if (edge.lSite === rSite) { - edge.vb = vertex; - } - else { - edge.va = vertex; - } - }; - -Voronoi.prototype.setEdgeEndpoint = function(edge, lSite, rSite, vertex) { - this.setEdgeStartpoint(edge, rSite, lSite, vertex); - }; - -// --------------------------------------------------------------------------- -// Beachline methods - -// rhill 2011-06-07: For some reasons, performance suffers significantly -// when instanciating a literal object instead of an empty ctor -Voronoi.prototype.Beachsection = function() { - }; - -// rhill 2011-06-02: A lot of Beachsection instanciations -// occur during the computation of the Voronoi diagram, -// somewhere between the number of sites and twice the -// number of sites, while the number of Beachsections on the -// beachline at any given time is comparatively low. For this -// reason, we reuse already created Beachsections, in order -// to avoid new memory allocation. This resulted in a measurable -// performance gain. - -Voronoi.prototype.createBeachsection = function(site) { - var beachsection = this.beachsectionJunkyard.pop(); - if (!beachsection) { - beachsection = new this.Beachsection(); - } - beachsection.site = site; - return beachsection; - }; - -// calculate the left break point of a particular beach section, -// given a particular sweep line -Voronoi.prototype.leftBreakPoint = function(arc, directrix) { - // http://en.wikipedia.org/wiki/Parabola - // http://en.wikipedia.org/wiki/Quadratic_equation - // h1 = x1, - // k1 = (y1+directrix)/2, - // h2 = x2, - // k2 = (y2+directrix)/2, - // p1 = k1-directrix, - // a1 = 1/(4*p1), - // b1 = -h1/(2*p1), - // c1 = h1*h1/(4*p1)+k1, - // p2 = k2-directrix, - // a2 = 1/(4*p2), - // b2 = -h2/(2*p2), - // c2 = h2*h2/(4*p2)+k2, - // x = (-(b2-b1) + Math.sqrt((b2-b1)*(b2-b1) - 4*(a2-a1)*(c2-c1))) / (2*(a2-a1)) - // When x1 become the x-origin: - // h1 = 0, - // k1 = (y1+directrix)/2, - // h2 = x2-x1, - // k2 = (y2+directrix)/2, - // p1 = k1-directrix, - // a1 = 1/(4*p1), - // b1 = 0, - // c1 = k1, - // p2 = k2-directrix, - // a2 = 1/(4*p2), - // b2 = -h2/(2*p2), - // c2 = h2*h2/(4*p2)+k2, - // x = (-b2 + Math.sqrt(b2*b2 - 4*(a2-a1)*(c2-k1))) / (2*(a2-a1)) + x1 - - // change code below at your own risk: care has been taken to - // reduce errors due to computers' finite arithmetic precision. - // Maybe can still be improved, will see if any more of this - // kind of errors pop up again. - var site = arc.site, - rfocx = site.x, - rfocy = site.y, - pby2 = rfocy-directrix; - // parabola in degenerate case where focus is on directrix - if (!pby2) { - return rfocx; - } - var lArc = arc.rbPrevious; - if (!lArc) { - return -Infinity; - } - site = lArc.site; - var lfocx = site.x, - lfocy = site.y, - plby2 = lfocy-directrix; - // parabola in degenerate case where focus is on directrix - if (!plby2) { - return lfocx; - } - var hl = lfocx-rfocx, - aby2 = 1/pby2-1/plby2, - b = hl/plby2; - if (aby2) { - return (-b+this.sqrt(b*b-2*aby2*(hl*hl/(-2*plby2)-lfocy+plby2/2+rfocy-pby2/2)))/aby2+rfocx; - } - // both parabolas have same distance to directrix, thus break point is midway - return (rfocx+lfocx)/2; - }; - -// calculate the right break point of a particular beach section, -// given a particular directrix -Voronoi.prototype.rightBreakPoint = function(arc, directrix) { - var rArc = arc.rbNext; - if (rArc) { - return this.leftBreakPoint(rArc, directrix); - } - var site = arc.site; - return site.y === directrix ? site.x : Infinity; - }; - -Voronoi.prototype.detachBeachsection = function(beachsection) { - this.detachCircleEvent(beachsection); // detach potentially attached circle event - this.beachline.rbRemoveNode(beachsection); // remove from RB-tree - this.beachsectionJunkyard.push(beachsection); // mark for reuse - }; - -Voronoi.prototype.removeBeachsection = function(beachsection) { - var circle = beachsection.circleEvent, - x = circle.x, - y = circle.ycenter, - vertex = this.createVertex(x, y), - previous = beachsection.rbPrevious, - next = beachsection.rbNext, - disappearingTransitions = [beachsection], - abs_fn = Math.abs; - - // remove collapsed beachsection from beachline - this.detachBeachsection(beachsection); - - // there could be more than one empty arc at the deletion point, this - // happens when more than two edges are linked by the same vertex, - // so we will collect all those edges by looking up both sides of - // the deletion point. - // by the way, there is *always* a predecessor/successor to any collapsed - // beach section, it's just impossible to have a collapsing first/last - // beach sections on the beachline, since they obviously are unconstrained - // on their left/right side. - - // look left - var lArc = previous; - while (lArc.circleEvent && abs_fn(x-lArc.circleEvent.x)<1e-9 && abs_fn(y-lArc.circleEvent.ycenter)<1e-9) { - previous = lArc.rbPrevious; - disappearingTransitions.unshift(lArc); - this.detachBeachsection(lArc); // mark for reuse - lArc = previous; - } - // even though it is not disappearing, I will also add the beach section - // immediately to the left of the left-most collapsed beach section, for - // convenience, since we need to refer to it later as this beach section - // is the 'left' site of an edge for which a start point is set. - disappearingTransitions.unshift(lArc); - this.detachCircleEvent(lArc); - - // look right - var rArc = next; - while (rArc.circleEvent && abs_fn(x-rArc.circleEvent.x)<1e-9 && abs_fn(y-rArc.circleEvent.ycenter)<1e-9) { - next = rArc.rbNext; - disappearingTransitions.push(rArc); - this.detachBeachsection(rArc); // mark for reuse - rArc = next; - } - // we also have to add the beach section immediately to the right of the - // right-most collapsed beach section, since there is also a disappearing - // transition representing an edge's start point on its left. - disappearingTransitions.push(rArc); - this.detachCircleEvent(rArc); - - // walk through all the disappearing transitions between beach sections and - // set the start point of their (implied) edge. - var nArcs = disappearingTransitions.length, - iArc; - for (iArc=1; iArc<nArcs; iArc++) { - rArc = disappearingTransitions[iArc]; - lArc = disappearingTransitions[iArc-1]; - this.setEdgeStartpoint(rArc.edge, lArc.site, rArc.site, vertex); - } - - // create a new edge as we have now a new transition between - // two beach sections which were previously not adjacent. - // since this edge appears as a new vertex is defined, the vertex - // actually define an end point of the edge (relative to the site - // on the left) - lArc = disappearingTransitions[0]; - rArc = disappearingTransitions[nArcs-1]; - rArc.edge = this.createEdge(lArc.site, rArc.site, undefined, vertex); - - // create circle events if any for beach sections left in the beachline - // adjacent to collapsed sections - this.attachCircleEvent(lArc); - this.attachCircleEvent(rArc); - }; - -Voronoi.prototype.addBeachsection = function(site) { - var x = site.x, - directrix = site.y; - - // find the left and right beach sections which will surround the newly - // created beach section. - // rhill 2011-06-01: This loop is one of the most often executed, - // hence we expand in-place the comparison-against-epsilon calls. - var lArc, rArc, - dxl, dxr, - node = this.beachline.root; - - while (node) { - dxl = this.leftBreakPoint(node,directrix)-x; - // x lessThanWithEpsilon xl => falls somewhere before the left edge of the beachsection - if (dxl > 1e-9) { - // this case should never happen - // if (!node.rbLeft) { - // rArc = node.rbLeft; - // break; - // } - node = node.rbLeft; - } - else { - dxr = x-this.rightBreakPoint(node,directrix); - // x greaterThanWithEpsilon xr => falls somewhere after the right edge of the beachsection - if (dxr > 1e-9) { - if (!node.rbRight) { - lArc = node; - break; - } - node = node.rbRight; - } - else { - // x equalWithEpsilon xl => falls exactly on the left edge of the beachsection - if (dxl > -1e-9) { - lArc = node.rbPrevious; - rArc = node; - } - // x equalWithEpsilon xr => falls exactly on the right edge of the beachsection - else if (dxr > -1e-9) { - lArc = node; - rArc = node.rbNext; - } - // falls exactly somewhere in the middle of the beachsection - else { - lArc = rArc = node; - } - break; - } - } - } - // at this point, keep in mind that lArc and/or rArc could be - // undefined or null. - - // create a new beach section object for the site and add it to RB-tree - var newArc = this.createBeachsection(site); - this.beachline.rbInsertSuccessor(lArc, newArc); - - // cases: - // - - // [null,null] - // least likely case: new beach section is the first beach section on the - // beachline. - // This case means: - // no new transition appears - // no collapsing beach section - // new beachsection become root of the RB-tree - if (!lArc && !rArc) { - return; - } - - // [lArc,rArc] where lArc == rArc - // most likely case: new beach section split an existing beach - // section. - // This case means: - // one new transition appears - // the left and right beach section might be collapsing as a result - // two new nodes added to the RB-tree - if (lArc === rArc) { - // invalidate circle event of split beach section - this.detachCircleEvent(lArc); - - // split the beach section into two separate beach sections - rArc = this.createBeachsection(lArc.site); - this.beachline.rbInsertSuccessor(newArc, rArc); - - // since we have a new transition between two beach sections, - // a new edge is born - newArc.edge = rArc.edge = this.createEdge(lArc.site, newArc.site); - - // check whether the left and right beach sections are collapsing - // and if so create circle events, to be notified when the point of - // collapse is reached. - this.attachCircleEvent(lArc); - this.attachCircleEvent(rArc); - return; - } - - // [lArc,null] - // even less likely case: new beach section is the *last* beach section - // on the beachline -- this can happen *only* if *all* the previous beach - // sections currently on the beachline share the same y value as - // the new beach section. - // This case means: - // one new transition appears - // no collapsing beach section as a result - // new beach section become right-most node of the RB-tree - if (lArc && !rArc) { - newArc.edge = this.createEdge(lArc.site,newArc.site); - return; - } - - // [null,rArc] - // impossible case: because sites are strictly processed from top to bottom, - // and left to right, which guarantees that there will always be a beach section - // on the left -- except of course when there are no beach section at all on - // the beach line, which case was handled above. - // rhill 2011-06-02: No point testing in non-debug version - //if (!lArc && rArc) { - // throw "Voronoi.addBeachsection(): What is this I don't even"; - // } - - // [lArc,rArc] where lArc != rArc - // somewhat less likely case: new beach section falls *exactly* in between two - // existing beach sections - // This case means: - // one transition disappears - // two new transitions appear - // the left and right beach section might be collapsing as a result - // only one new node added to the RB-tree - if (lArc !== rArc) { - // invalidate circle events of left and right sites - this.detachCircleEvent(lArc); - this.detachCircleEvent(rArc); - - // an existing transition disappears, meaning a vertex is defined at - // the disappearance point. - // since the disappearance is caused by the new beachsection, the - // vertex is at the center of the circumscribed circle of the left, - // new and right beachsections. - // http://mathforum.org/library/drmath/view/55002.html - // Except that I bring the origin at A to simplify - // calculation - var lSite = lArc.site, - ax = lSite.x, - ay = lSite.y, - bx=site.x-ax, - by=site.y-ay, - rSite = rArc.site, - cx=rSite.x-ax, - cy=rSite.y-ay, - d=2*(bx*cy-by*cx), - hb=bx*bx+by*by, - hc=cx*cx+cy*cy, - vertex = this.createVertex((cy*hb-by*hc)/d+ax, (bx*hc-cx*hb)/d+ay); - - // one transition disappear - this.setEdgeStartpoint(rArc.edge, lSite, rSite, vertex); - - // two new transitions appear at the new vertex location - newArc.edge = this.createEdge(lSite, site, undefined, vertex); - rArc.edge = this.createEdge(site, rSite, undefined, vertex); - - // check whether the left and right beach sections are collapsing - // and if so create circle events, to handle the point of collapse. - this.attachCircleEvent(lArc); - this.attachCircleEvent(rArc); - return; - } - }; - -// --------------------------------------------------------------------------- -// Circle event methods - -// rhill 2011-06-07: For some reasons, performance suffers significantly -// when instanciating a literal object instead of an empty ctor -Voronoi.prototype.CircleEvent = function() { - // rhill 2013-10-12: it helps to state exactly what we are at ctor time. - this.arc = null; - this.rbLeft = null; - this.rbNext = null; - this.rbParent = null; - this.rbPrevious = null; - this.rbRed = false; - this.rbRight = null; - this.site = null; - this.x = this.y = this.ycenter = 0; - }; - -Voronoi.prototype.attachCircleEvent = function(arc) { - var lArc = arc.rbPrevious, - rArc = arc.rbNext; - if (!lArc || !rArc) {return;} // does that ever happen? - var lSite = lArc.site, - cSite = arc.site, - rSite = rArc.site; - - // If site of left beachsection is same as site of - // right beachsection, there can't be convergence - if (lSite===rSite) {return;} - - // Find the circumscribed circle for the three sites associated - // with the beachsection triplet. - // rhill 2011-05-26: It is more efficient to calculate in-place - // rather than getting the resulting circumscribed circle from an - // object returned by calling Voronoi.circumcircle() - // http://mathforum.org/library/drmath/view/55002.html - // Except that I bring the origin at cSite to simplify calculations. - // The bottom-most part of the circumcircle is our Fortune 'circle - // event', and its center is a vertex potentially part of the final - // Voronoi diagram. - var bx = cSite.x, - by = cSite.y, - ax = lSite.x-bx, - ay = lSite.y-by, - cx = rSite.x-bx, - cy = rSite.y-by; - - // If points l->c->r are clockwise, then center beach section does not - // collapse, hence it can't end up as a vertex (we reuse 'd' here, which - // sign is reverse of the orientation, hence we reverse the test. - // http://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon - // rhill 2011-05-21: Nasty finite precision error which caused circumcircle() to - // return infinites: 1e-12 seems to fix the problem. - var d = 2*(ax*cy-ay*cx); - if (d >= -2e-12){return;} - - var ha = ax*ax+ay*ay, - hc = cx*cx+cy*cy, - x = (cy*ha-ay*hc)/d, - y = (ax*hc-cx*ha)/d, - ycenter = y+by; - - // Important: ybottom should always be under or at sweep, so no need - // to waste CPU cycles by checking - - // recycle circle event object if possible - var circleEvent = this.circleEventJunkyard.pop(); - if (!circleEvent) { - circleEvent = new this.CircleEvent(); - } - circleEvent.arc = arc; - circleEvent.site = cSite; - circleEvent.x = x+bx; - circleEvent.y = ycenter+this.sqrt(x*x+y*y); // y bottom - circleEvent.ycenter = ycenter; - arc.circleEvent = circleEvent; - - // find insertion point in RB-tree: circle events are ordered from - // smallest to largest - var predecessor = null, - node = this.circleEvents.root; - while (node) { - if (circleEvent.y < node.y || (circleEvent.y === node.y && circleEvent.x <= node.x)) { - if (node.rbLeft) { - node = node.rbLeft; - } - else { - predecessor = node.rbPrevious; - break; - } - } - else { - if (node.rbRight) { - node = node.rbRight; - } - else { - predecessor = node; - break; - } - } - } - this.circleEvents.rbInsertSuccessor(predecessor, circleEvent); - if (!predecessor) { - this.firstCircleEvent = circleEvent; - } - }; - -Voronoi.prototype.detachCircleEvent = function(arc) { - var circleEvent = arc.circleEvent; - if (circleEvent) { - if (!circleEvent.rbPrevious) { - this.firstCircleEvent = circleEvent.rbNext; - } - this.circleEvents.rbRemoveNode(circleEvent); // remove from RB-tree - this.circleEventJunkyard.push(circleEvent); - arc.circleEvent = null; - } - }; - -// --------------------------------------------------------------------------- -// Diagram completion methods - -// connect dangling edges (not if a cursory test tells us -// it is not going to be visible. -// return value: -// false: the dangling endpoint couldn't be connected -// true: the dangling endpoint could be connected -Voronoi.prototype.connectEdge = function(edge, bbox) { - // skip if end point already connected - var vb = edge.vb; - if (!!vb) {return true;} - - // make local copy for performance purpose - var va = edge.va, - xl = bbox.xl, - xr = bbox.xr, - yt = bbox.yt, - yb = bbox.yb, - lSite = edge.lSite, - rSite = edge.rSite, - lx = lSite.x, - ly = lSite.y, - rx = rSite.x, - ry = rSite.y, - fx = (lx+rx)/2, - fy = (ly+ry)/2, - fm, fb; - - // if we reach here, this means cells which use this edge will need - // to be closed, whether because the edge was removed, or because it - // was connected to the bounding box. - this.cells[lSite.voronoiId].closeMe = true; - this.cells[rSite.voronoiId].closeMe = true; - - // get the line equation of the bisector if line is not vertical - if (ry !== ly) { - fm = (lx-rx)/(ry-ly); - fb = fy-fm*fx; - } - - // remember, direction of line (relative to left site): - // upward: left.x < right.x - // downward: left.x > right.x - // horizontal: left.x == right.x - // upward: left.x < right.x - // rightward: left.y < right.y - // leftward: left.y > right.y - // vertical: left.y == right.y - - // depending on the direction, find the best side of the - // bounding box to use to determine a reasonable start point - - // rhill 2013-12-02: - // While at it, since we have the values which define the line, - // clip the end of va if it is outside the bbox. - // https://github.com/gorhill/Javascript-Voronoi/issues/15 - // TODO: Do all the clipping here rather than rely on Liang-Barsky - // which does not do well sometimes due to loss of arithmetic - // precision. The code here doesn't degrade if one of the vertex is - // at a huge distance. - - // special case: vertical line - if (fm === undefined) { - // doesn't intersect with viewport - if (fx < xl || fx >= xr) {return false;} - // downward - if (lx > rx) { - if (!va || va.y < yt) { - va = this.createVertex(fx, yt); - } - else if (va.y >= yb) { - return false; - } - vb = this.createVertex(fx, yb); - } - // upward - else { - if (!va || va.y > yb) { - va = this.createVertex(fx, yb); - } - else if (va.y < yt) { - return false; - } - vb = this.createVertex(fx, yt); - } - } - // closer to vertical than horizontal, connect start point to the - // top or bottom side of the bounding box - else if (fm < -1 || fm > 1) { - // downward - if (lx > rx) { - if (!va || va.y < yt) { - va = this.createVertex((yt-fb)/fm, yt); - } - else if (va.y >= yb) { - return false; - } - vb = this.createVertex((yb-fb)/fm, yb); - } - // upward - else { - if (!va || va.y > yb) { - va = this.createVertex((yb-fb)/fm, yb); - } - else if (va.y < yt) { - return false; - } - vb = this.createVertex((yt-fb)/fm, yt); - } - } - // closer to horizontal than vertical, connect start point to the - // left or right side of the bounding box - else { - // rightward - if (ly < ry) { - if (!va || va.x < xl) { - va = this.createVertex(xl, fm*xl+fb); - } - else if (va.x >= xr) { - return false; - } - vb = this.createVertex(xr, fm*xr+fb); - } - // leftward - else { - if (!va || va.x > xr) { - va = this.createVertex(xr, fm*xr+fb); - } - else if (va.x < xl) { - return false; - } - vb = this.createVertex(xl, fm*xl+fb); - } - } - edge.va = va; - edge.vb = vb; - - return true; - }; - -// line-clipping code taken from: -// Liang-Barsky function by Daniel White -// http://www.skytopia.com/project/articles/compsci/clipping.html -// Thanks! -// A bit modified to minimize code paths -Voronoi.prototype.clipEdge = function(edge, bbox) { - var ax = edge.va.x, - ay = edge.va.y, - bx = edge.vb.x, - by = edge.vb.y, - t0 = 0, - t1 = 1, - dx = bx-ax, - dy = by-ay; - // left - var q = ax-bbox.xl; - if (dx===0 && q<0) {return false;} - var r = -q/dx; - if (dx<0) { - if (r<t0) {return false;} - if (r<t1) {t1=r;} - } - else if (dx>0) { - if (r>t1) {return false;} - if (r>t0) {t0=r;} - } - // right - q = bbox.xr-ax; - if (dx===0 && q<0) {return false;} - r = q/dx; - if (dx<0) { - if (r>t1) {return false;} - if (r>t0) {t0=r;} - } - else if (dx>0) { - if (r<t0) {return false;} - if (r<t1) {t1=r;} - } - // top - q = ay-bbox.yt; - if (dy===0 && q<0) {return false;} - r = -q/dy; - if (dy<0) { - if (r<t0) {return false;} - if (r<t1) {t1=r;} - } - else if (dy>0) { - if (r>t1) {return false;} - if (r>t0) {t0=r;} - } - // bottom - q = bbox.yb-ay; - if (dy===0 && q<0) {return false;} - r = q/dy; - if (dy<0) { - if (r>t1) {return false;} - if (r>t0) {t0=r;} - } - else if (dy>0) { - if (r<t0) {return false;} - if (r<t1) {t1=r;} - } - - // if we reach this point, Voronoi edge is within bbox - - // if t0 > 0, va needs to change - // rhill 2011-06-03: we need to create a new vertex rather - // than modifying the existing one, since the existing - // one is likely shared with at least another edge - if (t0 > 0) { - edge.va = this.createVertex(ax+t0*dx, ay+t0*dy); - } - - // if t1 < 1, vb needs to change - // rhill 2011-06-03: we need to create a new vertex rather - // than modifying the existing one, since the existing - // one is likely shared with at least another edge - if (t1 < 1) { - edge.vb = this.createVertex(ax+t1*dx, ay+t1*dy); - } - - // va and/or vb were clipped, thus we will need to close - // cells which use this edge. - if ( t0 > 0 || t1 < 1 ) { - this.cells[edge.lSite.voronoiId].closeMe = true; - this.cells[edge.rSite.voronoiId].closeMe = true; - } - - return true; - }; - -// Connect/cut edges at bounding box -Voronoi.prototype.clipEdges = function(bbox) { - // connect all dangling edges to bounding box - // or get rid of them if it can't be done - var edges = this.edges, - iEdge = edges.length, - edge, - abs_fn = Math.abs; - - // iterate backward so we can splice safely - while (iEdge--) { - edge = edges[iEdge]; - // edge is removed if: - // it is wholly outside the bounding box - // it is looking more like a point than a line - if (!this.connectEdge(edge, bbox) || - !this.clipEdge(edge, bbox) || - (abs_fn(edge.va.x-edge.vb.x)<1e-9 && abs_fn(edge.va.y-edge.vb.y)<1e-9)) { - edge.va = edge.vb = null; - edges.splice(iEdge,1); - } - } - }; - -// Close the cells. -// The cells are bound by the supplied bounding box. -// Each cell refers to its associated site, and a list -// of halfedges ordered counterclockwise. -Voronoi.prototype.closeCells = function(bbox) { - var xl = bbox.xl, - xr = bbox.xr, - yt = bbox.yt, - yb = bbox.yb, - cells = this.cells, - iCell = cells.length, - cell, - iLeft, - halfedges, nHalfedges, - edge, - va, vb, vz, - lastBorderSegment, - abs_fn = Math.abs; - - while (iCell--) { - cell = cells[iCell]; - // prune, order halfedges counterclockwise, then add missing ones - // required to close cells - if (!cell.prepareHalfedges()) { - continue; - } - if (!cell.closeMe) { - continue; - } - // find first 'unclosed' point. - // an 'unclosed' point will be the end point of a halfedge which - // does not match the start point of the following halfedge - halfedges = cell.halfedges; - nHalfedges = halfedges.length; - // special case: only one site, in which case, the viewport is the cell - // ... - - // all other cases - iLeft = 0; - while (iLeft < nHalfedges) { - va = halfedges[iLeft].getEndpoint(); - vz = halfedges[(iLeft+1) % nHalfedges].getStartpoint(); - // if end point is not equal to start point, we need to add the missing - // halfedge(s) up to vz - if (abs_fn(va.x-vz.x)>=1e-9 || abs_fn(va.y-vz.y)>=1e-9) { - - // rhill 2013-12-02: - // "Holes" in the halfedges are not necessarily always adjacent. - // https://github.com/gorhill/Javascript-Voronoi/issues/16 - - // find entry point: - switch (true) { - - // walk downward along left side - case this.equalWithEpsilon(va.x,xl) && this.lessThanWithEpsilon(va.y,yb): - lastBorderSegment = this.equalWithEpsilon(vz.x,xl); - vb = this.createVertex(xl, lastBorderSegment ? vz.y : yb); - edge = this.createBorderEdge(cell.site, va, vb); - iLeft++; - halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null)); - nHalfedges++; - if ( lastBorderSegment ) { break; } - va = vb; - // fall through - - // walk rightward along bottom side - case this.equalWithEpsilon(va.y,yb) && this.lessThanWithEpsilon(va.x,xr): - lastBorderSegment = this.equalWithEpsilon(vz.y,yb); - vb = this.createVertex(lastBorderSegment ? vz.x : xr, yb); - edge = this.createBorderEdge(cell.site, va, vb); - iLeft++; - halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null)); - nHalfedges++; - if ( lastBorderSegment ) { break; } - va = vb; - // fall through - - // walk upward along right side - case this.equalWithEpsilon(va.x,xr) && this.greaterThanWithEpsilon(va.y,yt): - lastBorderSegment = this.equalWithEpsilon(vz.x,xr); - vb = this.createVertex(xr, lastBorderSegment ? vz.y : yt); - edge = this.createBorderEdge(cell.site, va, vb); - iLeft++; - halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null)); - nHalfedges++; - if ( lastBorderSegment ) { break; } - va = vb; - // fall through - - // walk leftward along top side - case this.equalWithEpsilon(va.y,yt) && this.greaterThanWithEpsilon(va.x,xl): - lastBorderSegment = this.equalWithEpsilon(vz.y,yt); - vb = this.createVertex(lastBorderSegment ? vz.x : xl, yt); - edge = this.createBorderEdge(cell.site, va, vb); - iLeft++; - halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null)); - nHalfedges++; - if ( lastBorderSegment ) { break; } - va = vb; - // fall through - - // walk downward along left side - lastBorderSegment = this.equalWithEpsilon(vz.x,xl); - vb = this.createVertex(xl, lastBorderSegment ? vz.y : yb); - edge = this.createBorderEdge(cell.site, va, vb); - iLeft++; - halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null)); - nHalfedges++; - if ( lastBorderSegment ) { break; } - va = vb; - // fall through - - // walk rightward along bottom side - lastBorderSegment = this.equalWithEpsilon(vz.y,yb); - vb = this.createVertex(lastBorderSegment ? vz.x : xr, yb); - edge = this.createBorderEdge(cell.site, va, vb); - iLeft++; - halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null)); - nHalfedges++; - if ( lastBorderSegment ) { break; } - va = vb; - // fall through - - // walk upward along right side - lastBorderSegment = this.equalWithEpsilon(vz.x,xr); - vb = this.createVertex(xr, lastBorderSegment ? vz.y : yt); - edge = this.createBorderEdge(cell.site, va, vb); - iLeft++; - halfedges.splice(iLeft, 0, this.createHalfedge(edge, cell.site, null)); - nHalfedges++; - if ( lastBorderSegment ) { break; } - // fall through - - default: - throw "Voronoi.closeCells() > this makes no sense!"; - } - } - iLeft++; - } - cell.closeMe = false; - } - }; - -// --------------------------------------------------------------------------- -// Debugging helper -/* -Voronoi.prototype.dumpBeachline = function(y) { - console.log('Voronoi.dumpBeachline(%f) > Beachsections, from left to right:', y); - if ( !this.beachline ) { - console.log(' None'); - } - else { - var bs = this.beachline.getFirst(this.beachline.root); - while ( bs ) { - console.log(' site %d: xl: %f, xr: %f', bs.site.voronoiId, this.leftBreakPoint(bs, y), this.rightBreakPoint(bs, y)); - bs = bs.rbNext; - } - } - }; -*/ - -// --------------------------------------------------------------------------- -// Helper: Quantize sites - -// rhill 2013-10-12: -// This is to solve https://github.com/gorhill/Javascript-Voronoi/issues/15 -// Since not all users will end up using the kind of coord values which would -// cause the issue to arise, I chose to let the user decide whether or not -// he should sanitize his coord values through this helper. This way, for -// those users who uses coord values which are known to be fine, no overhead is -// added. - -Voronoi.prototype.quantizeSites = function(sites) { - var ε = this.ε, - n = sites.length, - site; - while ( n-- ) { - site = sites[n]; - site.x = Math.floor(site.x / ε) * ε; - site.y = Math.floor(site.y / ε) * ε; - } - }; - -// --------------------------------------------------------------------------- -// Helper: Recycle diagram: all vertex, edge and cell objects are -// "surrendered" to the Voronoi object for reuse. -// TODO: rhill-voronoi-core v2: more performance to be gained -// when I change the semantic of what is returned. - -Voronoi.prototype.recycle = function(diagram) { - if ( diagram ) { - if ( diagram instanceof this.Diagram ) { - this.toRecycle = diagram; - } - else { - throw 'Voronoi.recycleDiagram() > Need a Diagram object.'; - } - } - }; - -// --------------------------------------------------------------------------- -// Top-level Fortune loop - -// rhill 2011-05-19: -// Voronoi sites are kept client-side now, to allow -// user to freely modify content. At compute time, -// *references* to sites are copied locally. - -Voronoi.prototype.compute = function(sites, bbox) { - // to measure execution time - var startTime = new Date(); - - // init internal state - this.reset(); - - // any diagram data available for recycling? - // I do that here so that this is included in execution time - if ( this.toRecycle ) { - this.vertexJunkyard = this.vertexJunkyard.concat(this.toRecycle.vertices); - this.edgeJunkyard = this.edgeJunkyard.concat(this.toRecycle.edges); - this.cellJunkyard = this.cellJunkyard.concat(this.toRecycle.cells); - this.toRecycle = null; - } - - // Initialize site event queue - var siteEvents = sites.slice(0); - siteEvents.sort(function(a,b){ - var r = b.y - a.y; - if (r) {return r;} - return b.x - a.x; - }); - - // process queue - var site = siteEvents.pop(), - siteid = 0, - xsitex, // to avoid duplicate sites - xsitey, - cells = this.cells, - circle; - - // main loop - for (;;) { - // we need to figure whether we handle a site or circle event - // for this we find out if there is a site event and it is - // 'earlier' than the circle event - circle = this.firstCircleEvent; - - // add beach section - if (site && (!circle || site.y < circle.y || (site.y === circle.y && site.x < circle.x))) { - // only if site is not a duplicate - if (site.x !== xsitex || site.y !== xsitey) { - // first create cell for new site - cells[siteid] = this.createCell(site); - site.voronoiId = siteid++; - // then create a beachsection for that site - this.addBeachsection(site); - // remember last site coords to detect duplicate - xsitey = site.y; - xsitex = site.x; - } - site = siteEvents.pop(); - } - - // remove beach section - else if (circle) { - this.removeBeachsection(circle.arc); - } - - // all done, quit - else { - break; - } - } - - // wrapping-up: - // connect dangling edges to bounding box - // cut edges as per bounding box - // discard edges completely outside bounding box - // discard edges which are point-like - this.clipEdges(bbox); - - // add missing edges in order to close opened cells - this.closeCells(bbox); - - // to measure execution time - var stopTime = new Date(); - - // prepare return values - var diagram = new this.Diagram(); - diagram.cells = this.cells; - diagram.edges = this.edges; - diagram.vertices = this.vertices; - diagram.execTime = stopTime.getTime()-startTime.getTime(); - - // clean up - this.reset(); - - return diagram; - }; - -/******************************************************************************/ - -if ( typeof module !== 'undefined' ) { - module.exports = Voronoi; -} - -export default Voronoi; diff --git a/web/pw-frontend/src/lib/visualizer/voronoi/voronoi.ts b/web/pw-frontend/src/lib/visualizer/voronoi/voronoi.ts deleted file mode 100644 index a63bc9a..0000000 --- a/web/pw-frontend/src/lib/visualizer/voronoi/voronoi.ts +++ /dev/null @@ -1,165 +0,0 @@ -import type { Shader } from "../webgl/shader"; -import type { BBox, Point } from "./voronoi-core"; -import Voronoi from "./voronoi-core"; -import { DefaultRenderable } from "../webgl/renderer"; -import { IndexBuffer, VertexBuffer } from "../webgl/buffer"; -import { VertexBufferLayout, VertexArray } from "../webgl/vertexBufferLayout"; - -function arcctg(x: number): number { return Math.PI / 2 - Math.atan(x); } - -function to_key(p: Point): string { - return [p.x, p.y] + ""; -} - -function round_point(center: Point, point: Point, amount_fn = (b: number) => 0.7): Point { - const d = dist(center, point, true); - const x = center.x + amount_fn(d) * (point.x - center.x); - const y = center.y + amount_fn(d) * (point.y - center.y); - return { 'x': x, 'y': y }; -} - -function median_point(c: Point, p: Point, n: Point, d = 0.1): number[] { - const dd = 1.0 - 2 * d; - return [ - dd * c.x + d * p.x + d * n.x, - dd * c.y + d * p.y + d * n.y, - ] -} - -function build_point_map(es: Voronoi.HalfEdge[]): (point: Point) => Point { - const mean = es.map(e => dist(e.getStartpoint(), e.getEndpoint())).reduce((a, b) => a + b, 0) / es.length; - const map = {}; - - for (let edge of es) { - const start = edge.getStartpoint(); - const end = edge.getEndpoint(); - - if (dist(start, end) < 0.03 * mean) { // These points have to be merged - const middle = { 'x': (start.x + end.x) / 2, 'y': (start.y + end.y) / 2 }; - map[to_key(start)] = middle; - map[to_key(end)] = middle; - } - } - - return (p) => map[to_key(p)] || p; -} - -function get_round_fn(dist_mean: number, amount = 0.7): (d: number) => number { - return (d) => arcctg((d - dist_mean) / dist_mean) / Math.PI + 0.6; -} - -function dist(a: Point, b: Point, norm = false): number { - const dx = a.x - b.x; - const dy = a.y - b.y; - if (norm) return Math.sqrt(dx * dx + dy * dy); - return dx * dx + dy * dy; -} - -export class VoronoiBuilder { - inner: DefaultRenderable; - - vor: Voronoi; - planets: Point[]; - - - constructor(gl: WebGLRenderingContext, shader: Shader, planets: Point[], bbox: BBox) { - this.vor = new Voronoi(); - this.planets = planets; - - const ib = new IndexBuffer(gl, []); - const vb = new VertexBuffer(gl, []); - - const layout = new VertexBufferLayout(); - layout.push(gl.FLOAT, 2, 4, "a_pos"); - layout.push(gl.FLOAT, 2, 4, "a_center"); - layout.push(gl.FLOAT, 1, 4, "a_own"); - layout.push(gl.FLOAT, 1, 4, "a_intensity"); - - const vao = new VertexArray(); - vao.addBuffer(vb, layout); - - this.inner = new DefaultRenderable(ib, vao, shader, [], {}); - - this.resize(gl, bbox); - } - - getRenderable(): DefaultRenderable { - return this.inner; - } - - resize(gl: WebGLRenderingContext, bbox: BBox) { - const start = new Date().getTime(); - - // This voronoi sorts the planets, then owners don't align anymore - const own_map = {}; - this.planets.forEach((p, i) => own_map[to_key(p)] = i); - - const vor = this.vor.compute(this.planets, bbox); - - const attrs = []; - const ids = []; - - let vertCount = 0; - - for (let i = 0; i < vor.cells.length; i++) { - const cell = vor.cells[i]; - const planetId = own_map[to_key(cell.site)]; - const point_map = build_point_map(cell.halfedges); - - const centerId = vertCount++; - - attrs.push(cell.site.x, cell.site.y); - attrs.push(cell.site.x, cell.site.y); - attrs.push(planetId); - attrs.push(1); - - const dist_mean = cell.halfedges.map(e => { - const start = e.getStartpoint(); - const end = e.getEndpoint(); - return dist(cell.site, start, true) + dist(cell.site, { 'x': (start.x + end.x) / 2, 'y': (start.y + end.y) / 2 }, true) - }).reduce((a, b) => a + b, 0) / cell.halfedges.length / 2; - const round_fn = get_round_fn(dist_mean); - - for (let edge of cell.halfedges) { - let start = point_map(edge.getStartpoint()); - let end = point_map(edge.getEndpoint()); - let center = { 'x': (start.x + end.x) / 2, 'y': (start.y + end.y) / 2 }; - - if (to_key(start) == to_key(end)) continue; - - start = round_point(cell.site, start, round_fn); - center = round_point(cell.site, center, round_fn); - end = round_point(cell.site, end, round_fn); - - ids.push(centerId); - ids.push(vertCount++); - attrs.push(start.x, start.y); - attrs.push(cell.site.x, cell.site.y); - attrs.push(planetId); - attrs.push(0); - - ids.push(vertCount++); - attrs.push(center.x, center.y); - attrs.push(cell.site.x, cell.site.y); - attrs.push(planetId); - attrs.push(0); - - ids.push(centerId); - ids.push(vertCount - 1); - - ids.push(vertCount++); - attrs.push(end.x, end.y); - attrs.push(cell.site.x, cell.site.y); - attrs.push(planetId); - attrs.push(0); - } - } - - this.inner.updateIndexBuffer(gl, ids); - this.inner.updateVAOBuffer(gl, 0, attrs); - - console.log(`Vor things took ${new Date().getTime() - start} ms!`) - } -} - -export default VoronoiBuilder;
\ No newline at end of file diff --git a/web/pw-frontend/src/lib/visualizer/webgl/buffer.ts b/web/pw-frontend/src/lib/visualizer/webgl/buffer.ts deleted file mode 100644 index 2739fbe..0000000 --- a/web/pw-frontend/src/lib/visualizer/webgl/buffer.ts +++ /dev/null @@ -1,55 +0,0 @@ - -export class Buffer { - buffer: WebGLBuffer; - data: any; - count: number; - type: number; - - constructor(gl: WebGLRenderingContext, data: number[], type: number) { - this.buffer = gl.createBuffer(); - this.type = type; - - if (data) - this.updateData(gl, data); - } - - _toArray(data: number[]): any { - return new Float32Array(data); - } - - updateData(gl: WebGLRenderingContext, data: number[]) { - this.data = data; - this.count = data.length; - gl.bindBuffer(this.type, this.buffer); - gl.bufferData(this.type, this._toArray(data), gl.STATIC_DRAW); - } - - bind(gl: WebGLRenderingContext) { - gl.bindBuffer(this.type, this.buffer); - } - - getCount(): number { - return this.count; - } -} - -export class VertexBuffer extends Buffer { - constructor(gl: WebGLRenderingContext, data: any) { - super(gl, data, gl.ARRAY_BUFFER); - } - - _toArray(data: number[]): any { - return new Float32Array(data); - } -} - - -export class IndexBuffer extends Buffer { - constructor(gl: WebGLRenderingContext, data: any) { - super(gl, data, gl.ELEMENT_ARRAY_BUFFER); - } - - _toArray(data: number[]): any { - return new Uint16Array(data); - } -} diff --git a/web/pw-frontend/src/lib/visualizer/webgl/index.ts b/web/pw-frontend/src/lib/visualizer/webgl/index.ts deleted file mode 100644 index fdb7886..0000000 --- a/web/pw-frontend/src/lib/visualizer/webgl/index.ts +++ /dev/null @@ -1,122 +0,0 @@ -import { Uniform4f, Uniform1f, Uniform2f, ShaderFactory, UniformMatrix3fv, Uniform3f } from './shader'; -import { resizeCanvasToDisplaySize, FPSCounter, onload2promise, Resizer, url_to_mesh } from "./util"; -import { VertexBuffer, IndexBuffer } from './buffer'; -import { VertexArray, VertexBufferLayout } from './vertexBufferLayout'; -import { Renderer } from './renderer'; -import { Texture } from './texture'; - -const URL = window.location.origin+window.location.pathname; -const LOCATION = URL.substring(0, URL.lastIndexOf("/") + 1); - -async function create_texture_from_svg(gl: WebGLRenderingContext, name: string, path: string, width: number, height: number): Promise<Texture> { - - const [mesh, factory] = await Promise.all([ - url_to_mesh(path), - ShaderFactory.create_factory(LOCATION + "static/shaders/frag/static_color.glsl", LOCATION + "static/shaders/vert/svg.glsl") - ]); - - const program = factory.create_shader(gl); - const renderer = new Renderer(); - - var positionBuffer = new VertexBuffer(gl, mesh.positions); - var layout = new VertexBufferLayout(); - layout.push(gl.FLOAT, 3, 4, "a_position"); - - const vao = new VertexArray(); - vao.addBuffer(positionBuffer, layout); - - program.bind(gl); - vao.bind(gl, program); - - var indexBuffer = new IndexBuffer(gl, mesh.cells); - indexBuffer.bind(gl); - - renderer.addToDraw(indexBuffer, vao, program, {}); - - return Texture.fromRenderer(gl, name, width, height, renderer); -} - - -async function main() { - - // Get A WebGL context - var canvas = <HTMLCanvasElement>document.getElementById("c"); - const resolution = [canvas.width, canvas.height]; - - const resizer = new Resizer(canvas, [-10, -10, 20, 20], true); - - var gl = canvas.getContext("webgl"); - if (!gl) { - return; - } - - const mesh = await url_to_mesh("static/res/images/earth.svg"); - console.log(Math.max(...mesh.positions), Math.min(...mesh.positions)); - const renderer = new Renderer(); - - const factory = await ShaderFactory.create_factory(LOCATION + "static/shaders/frag/static_color.glsl", LOCATION + "static/shaders/vert/simple.glsl"); - const program = factory.create_shader(gl); - - var positionBuffer = new VertexBuffer(gl, mesh.positions); - var layout = new VertexBufferLayout(); - layout.push(gl.FLOAT, 3, 4, "a_position"); - // layout.push(gl.FLOAT, 2, 4, "a_tex"); - - const vao = new VertexArray(); - vao.addBuffer(positionBuffer, layout); - - resizeCanvasToDisplaySize(<HTMLCanvasElement>gl.canvas); - - // Tell WebGL how to convert from clip space to pixels - gl.viewport(0, 0, gl.canvas.width, gl.canvas.height); - - // Clear the canvas - gl.clearColor(0, 0, 0, 0); - gl.clear(gl.COLOR_BUFFER_BIT); - - gl.enable(gl.BLEND); - gl.blendFunc(gl.SRC_ALPHA, gl.ONE_MINUS_SRC_ALPHA); - - program.bind(gl); - vao.bind(gl, program); - - var indexBuffer = new IndexBuffer(gl, mesh.cells); - indexBuffer.bind(gl); - - renderer.addToDraw(indexBuffer, vao, program, {}); - - const counter = new FPSCounter(); - - const step = function (time: number) { - - // console.log(resizer.get_viewbox()); - - program.uniform(gl, "u_time", new Uniform1f(time * 0.001)); - program.uniform(gl, "u_mouse", new Uniform2f(resizer.get_mouse_pos())); - program.uniform(gl, "u_viewbox", new Uniform4f(resizer.get_viewbox())); - program.uniform(gl, "u_resolution", new Uniform2f(resolution)); - program.uniform(gl, "u_trans", new UniformMatrix3fv([1, 0, 0, 0, 1, 0, 0, 0, 1])); - program.uniform(gl, "u_color", new Uniform3f(1.0, 0.5, 0.0)); - - renderer.render(gl); - - counter.frame(time); - requestAnimationFrame(step); - } - - requestAnimationFrame(step); -} - - -main(); - -document.getElementById("loader").classList.remove("loading"); - -// const loader = document.getElementById("loader"); -// setInterval(() => { -// if (loader.classList.contains("loading")) { -// loader.classList.remove("loading") -// } else { -// loader.classList.add("loading"); -// } -// }, 2000); diff --git a/web/pw-frontend/src/lib/visualizer/webgl/renderer.ts b/web/pw-frontend/src/lib/visualizer/webgl/renderer.ts deleted file mode 100644 index c3b219f..0000000 --- a/web/pw-frontend/src/lib/visualizer/webgl/renderer.ts +++ /dev/null @@ -1,157 +0,0 @@ -import type { IndexBuffer } from './buffer'; -import type { VertexArray } from './vertexBufferLayout'; -import type { Texture } from './texture'; -import type { Dictionary } from './util'; -import type { Shader, Uniform } from './shader'; -import { Uniform1i } from './shader'; - -function sortedIndex(array, value) { - var low = 0, - high = array.length; - - while (low < high) { - var mid = (low + high) >>> 1; - if (array[mid] < value) low = mid + 1; - else high = mid; - } - return low; -} - -export interface Renderable { - getUniforms() : Dictionary<Uniform>; - render(gl: WebGLRenderingContext): void; - updateVAOBuffer(gl: WebGLRenderingContext, index: number, data: number[]); - updateIndexBuffer(gl: WebGLRenderingContext, data: number[]); -} - -export class DefaultRenderable implements Renderable { - ibo: IndexBuffer; - va: VertexArray; - shader: Shader; - textures: Texture[]; - uniforms: Dictionary<Uniform>; - - constructor( - ibo: IndexBuffer, - va: VertexArray, - shader: Shader, - textures: Texture[], - uniforms: Dictionary<Uniform>, - ) { - this.ibo = ibo; - this.va = va; - this.shader = shader; - this.textures = textures; - this.uniforms = uniforms; - } - - getUniforms(): Dictionary<Uniform> { - return this.uniforms; - } - - updateVAOBuffer(gl: WebGLRenderingContext, index: number, data: number[]) { - this.va.updateBuffer(gl, index, data); - } - - updateIndexBuffer(gl: WebGLRenderingContext, data: number[]) { - this.ibo.updateData(gl, data); - } - - render(gl: WebGLRenderingContext): void { - - const indexBuffer = this.ibo; - const vertexArray = this.va; - const uniforms = this.uniforms; - - const shader = this.shader; - const textures = this.textures; - let texLocation = 0; - - for (let texture of textures) { - - shader.uniform(gl, texture.name, new Uniform1i(texLocation)); - texture.bind(gl, texLocation); - - texLocation ++; - // if (texLocation > maxTextures) { - // console.error("Using too many textures, this is not supported yet\nUndefined behaviour!"); - // } - } - - if (vertexArray && shader && uniforms) { - for(let key in uniforms) { - shader.uniform(gl, key, uniforms[key]); - } - - vertexArray.bind(gl, shader); - - if (indexBuffer) { - indexBuffer.bind(gl); - gl.drawElements(gl.TRIANGLES, indexBuffer.getCount(), gl.UNSIGNED_SHORT, 0); - } else { - console.error("IndexBuffer is required to render, for now"); - } - } - - } -} - -export class Renderer { - renderables: { [id: number] : [Renderable, boolean][]; }; - renderable_layers: number[]; - - constructor() { - this.renderables = {}; - this.renderable_layers = []; - } - - updateUniform(i: number, f: (uniforms: Dictionary<Uniform>) => void, layer=0, ) { - f(this.renderables[layer][i][0].getUniforms()); - } - - disableRenderable(i: number, layer=0) { - this.renderables[layer][i][1] = false; - } - - enableRenderable(i: number, layer=0) { - this.renderables[layer][i][1] = true; - } - - addRenderable(item: Renderable, layer=0): number { - if(!this.renderables[layer]) { - const idx = sortedIndex(this.renderable_layers, layer); - this.renderable_layers.splice(idx, 0, layer); - this.renderables[layer] = []; - } - - this.renderables[layer].push([item, true]); - return this.renderables[layer].length - 1; - } - - addToDraw(indexBuffer: IndexBuffer, vertexArray: VertexArray, shader: Shader, uniforms?: Dictionary<Uniform>, texture?: Texture[], layer=0): number { - return this.addRenderable( - new DefaultRenderable( - indexBuffer, - vertexArray, - shader, - texture || [], - uniforms || {}, - ), layer - ); - } - - render(gl: WebGLRenderingContext, frameBuffer?: WebGLFramebuffer, width?: number, height?: number) { - gl.bindFramebuffer(gl.FRAMEBUFFER, frameBuffer); - gl.viewport(0, 0, width || gl.canvas.width, height || gl.canvas.height); - gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT); - - const maxTextures = gl.getParameter(gl.MAX_VERTEX_TEXTURE_IMAGE_UNITS); - - for (let layer of this.renderable_layers) { - for (let [r, e] of this.renderables[layer]) { - if (!e) continue; - r.render(gl); - } - } - } -} diff --git a/web/pw-frontend/src/lib/visualizer/webgl/shader.ts b/web/pw-frontend/src/lib/visualizer/webgl/shader.ts deleted file mode 100644 index 942c4c2..0000000 --- a/web/pw-frontend/src/lib/visualizer/webgl/shader.ts +++ /dev/null @@ -1,327 +0,0 @@ -import type { Dictionary } from './util'; - -function error(msg: string) { - console.error(msg); -} - -const defaultShaderType = [ - "VERTEX_SHADER", - "FRAGMENT_SHADER" -]; - -/// Create Shader from Source string -function loadShader( - gl: WebGLRenderingContext, - shaderSource: string, - shaderType: number, - opt_errorCallback: any, -): WebGLShader { - var errFn = opt_errorCallback || error; - // Create the shader object - var shader = gl.createShader(shaderType); - - // Load the shader source - gl.shaderSource(shader, shaderSource); - - // Compile the shader - gl.compileShader(shader); - - // Check the compile status - var compiled = gl.getShaderParameter(shader, gl.COMPILE_STATUS); - if (!compiled) { - // Something went wrong during compilation; get the error - var lastError = gl.getShaderInfoLog(shader); - errFn("*** Error compiling shader '" + shader + "':" + lastError); - gl.deleteShader(shader); - return null; - } - - return shader; -} - -/// Actually Create Program with Shader's -function createProgram( - gl: WebGLRenderingContext, - shaders: WebGLShader[], - opt_attribs: string[], - opt_locations: number[], - opt_errorCallback: any, -): WebGLProgram { - var errFn = opt_errorCallback || error; - var program = gl.createProgram(); - shaders.forEach(function (shader) { - gl.attachShader(program, shader); - }); - if (opt_attribs) { - opt_attribs.forEach(function (attrib, ndx) { - gl.bindAttribLocation( - program, - opt_locations ? opt_locations[ndx] : ndx, - attrib); - }); - } - gl.linkProgram(program); - - // Check the link status - var linked = gl.getProgramParameter(program, gl.LINK_STATUS); - if (!linked) { - // something went wrong with the link - var lastError = gl.getProgramInfoLog(program); - errFn("Error in program linking:" + lastError); - - gl.deleteProgram(program); - return null; - } - return program; -} - -export class ShaderFactory { - frag_source: string; - vert_source: string; - - static async create_factory(frag_url: string, vert_url: string): Promise<ShaderFactory> { - const sources = await Promise.all([ - fetch(frag_url).then((r) => r.text()), - fetch(vert_url).then((r) => r.text()), - ]); - - return new ShaderFactory(sources[0], sources[1]); - } - - constructor(frag_source: string, vert_source: string ) { - this.frag_source = frag_source; - this.vert_source = vert_source; - } - - create_shader( - gl: WebGLRenderingContext, - context?: Dictionary<string>, - opt_attribs?: string[], - opt_locations?: number[], - opt_errorCallback?: any, - ): Shader { - let vert = this.vert_source.slice(); - let frag = this.frag_source.slice(); - for (let key in context) { - vert = vert.replace(new RegExp("\\$" + key, 'g'), context[key]); - frag = frag.replace(new RegExp("\\$" + key, 'g'), context[key]); - } - - const shaders = [ - loadShader(gl, vert, gl.VERTEX_SHADER, opt_errorCallback), - loadShader(gl, frag, gl.FRAGMENT_SHADER, opt_errorCallback), - ]; - - return new Shader(createProgram(gl, shaders, opt_attribs, opt_locations, opt_errorCallback)); - } -} - -export class Shader { - shader: WebGLProgram; - uniformCache: Dictionary<WebGLUniformLocation>; - attribCache: Dictionary<number>; - - static async createProgramFromUrls( - gl: WebGLRenderingContext, - vert_url: string, - frag_url: string, - context?: Dictionary<string>, - opt_attribs?: string[], - opt_locations?: number[], - opt_errorCallback?: any, - ): Promise<Shader> { - const sources = (await Promise.all([ - fetch(vert_url).then((r) => r.text()), - fetch(frag_url).then((r) => r.text()), - ])).map(x => { - for (let key in context) { - x = x.replace(new RegExp("\\$" + key, 'g'), context[key]); - } - return x; - }); - - const shaders = [ - loadShader(gl, sources[0], 35633, opt_errorCallback), - loadShader(gl, sources[1], 35632, opt_errorCallback), - ]; - return new Shader(createProgram(gl, shaders, opt_attribs, opt_locations, opt_errorCallback)); - } - - constructor(shader: WebGLProgram) { - this.shader = shader; - this.uniformCache = {}; - this.attribCache = {}; - } - - bind(gl: WebGLRenderingContext) { - gl.useProgram(this.shader); - } - - // Different locations have different types :/ - getUniformLocation(gl: WebGLRenderingContext, name: string): WebGLUniformLocation { - if (this.uniformCache[name] === undefined) { - this.uniformCache[name] = gl.getUniformLocation(this.shader, name); - } - - return this.uniformCache[name]; - } - - getAttribLocation(gl: WebGLRenderingContext, name: string): number { - if (this.attribCache[name] === undefined) { - this.attribCache[name] = gl.getAttribLocation(this.shader, name); - } - - return this.attribCache[name]; - } - - uniform<T extends Uniform>( - gl: WebGLRenderingContext, - name: string, - uniform: T, - ) { - this.bind(gl); - const location = this.getUniformLocation(gl, name); - if (location < 0) { - console.error("No location found with name " + name); - } - - uniform.setUniform(gl, location); - } - - clear(gl: WebGLRenderingContext) { - gl.deleteProgram(this.shader); - } -} - -export interface Uniform { - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation): void; -} - -export class Uniform2fv implements Uniform { - data: number[] | Float32Array; - constructor(data: number[] | Float32Array) { - this.data = data; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform2fv(location, this.data); - } -} - -export class Uniform3fv implements Uniform { - data: number[] | Float32Array; - constructor(data: number[] | Float32Array) { - this.data = data; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform3fv(location, this.data); - } -} - -export class Uniform3f implements Uniform { - x: number; - y: number; - z: number; - - constructor(x: number, y: number, z: number) { - this.x = x; - this.y = y; - this.z = z; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform3f(location, this.x ,this.y, this.z); - } -} - -export class Uniform1iv implements Uniform { - data: number[] | Int32List; - constructor(data: number[] | Int32List) { - this.data = data; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform1iv(location, this.data); - } -} - -export class Uniform1i implements Uniform { - texture: number; - - constructor(texture: number) { - this.texture = texture; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform1i(location, this.texture); - } -} - -export class Uniform1f implements Uniform { - texture: number; - - constructor(texture: number) { - this.texture = texture; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform1f(location, this.texture); - } -} - -export class Uniform2f implements Uniform { - x: number; - y: number; - - constructor(xy: number[]) { - this.x = xy[0]; - this.y = xy[1]; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform2f(location, this.x, this.y); - } -} - -export class Uniform4f implements Uniform { - v0: number; - v1: number; - v2: number; - v3: number; - - constructor(xyzw: number[]) { - this.v0 = xyzw[0]; - this.v1 = xyzw[1]; - this.v2 = xyzw[2]; - this.v3 = xyzw[3]; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform4f(location, this.v0, this.v1, this.v2, this.v3); - } -} - -export class UniformMatrix3fv implements Uniform { - data: number[] | Float32Array; - constructor(data: number[] | Float32Array) { - this.data = data; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniformMatrix3fv(location, false, this.data); - } -} - -export class UniformBool implements Uniform { - data: boolean; - constructor(data: boolean) { - this.data = data; - } - - setUniform(gl: WebGLRenderingContext, location: WebGLUniformLocation) { - gl.uniform1i(location, this.data ? 1 : 0); - } -} - -export default Shader;
\ No newline at end of file diff --git a/web/pw-frontend/src/lib/visualizer/webgl/text.ts b/web/pw-frontend/src/lib/visualizer/webgl/text.ts deleted file mode 100644 index 3f1cec6..0000000 --- a/web/pw-frontend/src/lib/visualizer/webgl/text.ts +++ /dev/null @@ -1,192 +0,0 @@ -import type { Dictionary } from "./util"; -import type { Shader, UniformMatrix3fv } from "./shader"; -import { Texture } from "./texture"; -import { DefaultRenderable } from "./renderer"; -import { IndexBuffer, VertexBuffer } from "./buffer"; -import { VertexBufferLayout, VertexArray } from "./vertexBufferLayout"; - - -export enum Align { - Begin, - End, - Middle, -} - -export class GlypInfo { - x: number; - y: number; - width: number; -} - -export class FontInfo { - letterHeight: number; - spaceWidth: number; - spacing: number; - textureWidth: number; - textureHeight: number; - glyphInfos: Dictionary<GlypInfo>; -} - -export class LabelFactory { - texture: Texture; - font: FontInfo; - shader: Shader; - - constructor(gl: WebGLRenderingContext, loc: string, font: FontInfo, shader: Shader) { - this.texture = Texture.fromImage(gl, loc, 'font'); - this.font = font; - this.shader = shader; - } - - build(gl: WebGLRenderingContext, transform?: UniformMatrix3fv): Label { - return new Label(gl, this.shader, this.texture, this.font, transform); - } -} - -export class Label { - inner: DefaultRenderable; - - font: FontInfo; - - constructor(gl: WebGLRenderingContext, shader: Shader, tex: Texture, font: FontInfo, transform?: UniformMatrix3fv) { - this.font = font; - - const uniforms = transform ? { "u_trans": transform, "u_trans_next": transform, } : {}; - const ib = new IndexBuffer(gl, []); - const vb_pos = new VertexBuffer(gl, []); - const vb_tex = new VertexBuffer(gl, []); - - const layout_pos = new VertexBufferLayout(); - layout_pos.push(gl.FLOAT, 2, 4, "a_position"); - - const layout_tex = new VertexBufferLayout(); - layout_tex.push(gl.FLOAT, 2, 4, "a_texCoord"); - - const vao = new VertexArray(); - vao.addBuffer(vb_pos, layout_pos); - vao.addBuffer(vb_tex, layout_tex); - - this.inner = new DefaultRenderable(ib, vao, shader, [tex], uniforms); - } - - getRenderable(): DefaultRenderable { - return this.inner; - } - - setText(gl: WebGLRenderingContext, text: string, h_align = Align.Begin, v_align = Align.Begin) { - const idxs = []; - const verts_pos = []; - const verts_tex = []; - - const letterHeight = this.font.letterHeight / this.font.textureHeight; - let xPos = 0; - - switch (h_align) { - case Align.Begin: - break; - case Align.End: - xPos = -1 * [...text].map(n => this.font.glyphInfos[n] ? this.font.glyphInfos[n].width : this.font.spaceWidth).reduce((a, b) => a + b, 0) / this.font.letterHeight; - break; - case Align.Middle: - xPos = -1 * [...text].map(n => this.font.glyphInfos[n] ? this.font.glyphInfos[n].width : this.font.spaceWidth).reduce((a, b) => a + b, 0) / this.font.letterHeight / 2; - break; - } - let yStart = 0; - switch (v_align) { - case Align.Begin: - break; - case Align.End: - yStart = 1; - break; - case Align.Middle: - yStart = 0.5; - break; - } - - let j = 0; - for (let i = 0; i < text.length; i++) { - const info = this.font.glyphInfos[text[i]]; - if (info) { - const dx = info.width / this.font.letterHeight; - const letterWidth = info.width / this.font.textureWidth; - const x0 = info.x / this.font.textureWidth; - const y0 = info.y / this.font.textureHeight; - verts_pos.push(xPos, yStart); - verts_pos.push(xPos + dx, yStart); - verts_pos.push(xPos, yStart-1); - verts_pos.push(xPos + dx, yStart-1); - - verts_tex.push(x0, y0); - verts_tex.push(x0 + letterWidth, y0); - verts_tex.push(x0, y0 + letterHeight); - verts_tex.push(x0 + letterWidth, y0 + letterHeight); - - xPos += dx; - - idxs.push(j+0, j+1, j+2, j+1, j+2, j+3); - j += 4; - } else { - // Just move xPos - xPos += this.font.spaceWidth / this.font.letterHeight; - } - } - - this.inner.updateIndexBuffer(gl, idxs); - this.inner.updateVAOBuffer(gl, 0, verts_pos); - this.inner.updateVAOBuffer(gl, 1, verts_tex); - } -} - -export function defaultLabelFactory(gl: WebGLRenderingContext, shader: Shader): LabelFactory { - const fontInfo = { - letterHeight: 8, - spaceWidth: 8, - spacing: -1, - textureWidth: 64, - textureHeight: 40, - glyphInfos: { - 'a': { x: 0, y: 0, width: 8, }, - 'b': { x: 8, y: 0, width: 8, }, - 'c': { x: 16, y: 0, width: 8, }, - 'd': { x: 24, y: 0, width: 8, }, - 'e': { x: 32, y: 0, width: 8, }, - 'f': { x: 40, y: 0, width: 8, }, - 'g': { x: 48, y: 0, width: 8, }, - 'h': { x: 56, y: 0, width: 8, }, - 'i': { x: 0, y: 8, width: 8, }, - 'j': { x: 8, y: 8, width: 8, }, - 'k': { x: 16, y: 8, width: 8, }, - 'l': { x: 24, y: 8, width: 8, }, - 'm': { x: 32, y: 8, width: 8, }, - 'n': { x: 40, y: 8, width: 8, }, - 'o': { x: 48, y: 8, width: 8, }, - 'p': { x: 56, y: 8, width: 8, }, - 'q': { x: 0, y: 16, width: 8, }, - 'r': { x: 8, y: 16, width: 8, }, - 's': { x: 16, y: 16, width: 8, }, - 't': { x: 24, y: 16, width: 8, }, - 'u': { x: 32, y: 16, width: 8, }, - 'v': { x: 40, y: 16, width: 8, }, - 'w': { x: 48, y: 16, width: 8, }, - 'x': { x: 56, y: 16, width: 8, }, - 'y': { x: 0, y: 24, width: 8, }, - 'z': { x: 8, y: 24, width: 8, }, - '0': { x: 16, y: 24, width: 8, }, - '1': { x: 24, y: 24, width: 8, }, - '2': { x: 32, y: 24, width: 8, }, - '3': { x: 40, y: 24, width: 8, }, - '4': { x: 48, y: 24, width: 8, }, - '5': { x: 56, y: 24, width: 8, }, - '6': { x: 0, y: 32, width: 8, }, - '7': { x: 8, y: 32, width: 8, }, - '8': { x: 16, y: 32, width: 8, }, - '9': { x: 24, y: 32, width: 8, }, - '-': { x: 32, y: 32, width: 8, }, - '*': { x: 40, y: 32, width: 8, }, - '!': { x: 48, y: 32, width: 8, }, - '?': { x: 56, y: 32, width: 8, }, - }, - }; - - return new LabelFactory(gl, '/static/res/assets/font.png', fontInfo, shader); -} diff --git a/web/pw-frontend/src/lib/visualizer/webgl/texture.ts b/web/pw-frontend/src/lib/visualizer/webgl/texture.ts deleted file mode 100644 index 9d6adcf..0000000 --- a/web/pw-frontend/src/lib/visualizer/webgl/texture.ts +++ /dev/null @@ -1,106 +0,0 @@ -import type { Renderer } from "./renderer"; - -export class Texture { - texture: WebGLTexture; - width: number; - height: number; - loaded: boolean; - name: string; - - static fromImage( - gl: WebGLRenderingContext, - path: string, - name: string, - ): Texture { - const out = new Texture(gl, name); - - const image = new Image(); - image.onload = out.setImage.bind(out, gl, image); - image.onerror = error; - image.src = path; - - return out; - } - - static fromRenderer( - gl: WebGLRenderingContext, - name: string, - width: number, - height: number, - renderer: Renderer - ): Texture { - const out = new Texture(gl, name); - out.width = width; - out.height = height; - - gl.texImage2D( - gl.TEXTURE_2D, 0, gl.RGBA, width, height, 0, - gl.RGBA, gl.UNSIGNED_BYTE, null); - - const fb = gl.createFramebuffer(); - gl.bindFramebuffer(gl.FRAMEBUFFER, fb); - - const attachmentPoint = gl.COLOR_ATTACHMENT0; - gl.framebufferTexture2D(gl.FRAMEBUFFER, attachmentPoint, gl.TEXTURE_2D, out.texture, 0); - - renderer.render(gl, fb, width, height); - - out.loaded = true; - - return out; - } - - constructor( - gl: WebGLRenderingContext, - name: string, - ) { - this.loaded = false; - this.name = name; - - this.texture = gl.createTexture(); - this.bind(gl); - - gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_S, gl.CLAMP_TO_EDGE); - gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_T, gl.CLAMP_TO_EDGE); - gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MIN_FILTER, gl.NEAREST); - gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MAG_FILTER, gl.NEAREST); - - gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA, 1, 1, 0, gl.RGBA, - gl.UNSIGNED_BYTE, new Uint8Array([255, 0, 0, 255])); - } - - setImage(gl: WebGLRenderingContext, image: HTMLImageElement) { - this.bind(gl); - this.width = image.width; - this.height = image.height; - - gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA, gl.RGBA, gl.UNSIGNED_BYTE, image); - - this.unbind(gl); - - this.loaded = true; - } - - bind(gl: WebGLRenderingContext, location=0) { - gl.activeTexture(gl.TEXTURE0 + location); - gl.bindTexture(gl.TEXTURE_2D, this.texture); - } - - unbind(gl: WebGLRenderingContext) { - gl.bindTexture(gl.TEXTURE_2D, null); - } - - - getWidth(): number { - return this.width; - } - - getHeight(): number { - return this.height; - } -} - -function error(e: any) { - console.error("IMAGE LOAD ERROR"); - console.error(e); -} diff --git a/web/pw-frontend/src/lib/visualizer/webgl/util.ts b/web/pw-frontend/src/lib/visualizer/webgl/util.ts deleted file mode 100644 index 3ed2b4d..0000000 --- a/web/pw-frontend/src/lib/visualizer/webgl/util.ts +++ /dev/null @@ -1,229 +0,0 @@ -import { parse as parsePath } from 'extract-svg-path'; -import svgMesh3d from 'svg-mesh-3d'; - -export interface Dictionary<T> { - [Key: string]: T; -} - - -interface OnLoadable { - onload: any; -} - -export function onload2promise<T extends OnLoadable>(obj: T): Promise<T> { - return new Promise(resolve => { - obj.onload = () => resolve(obj); - }); -} - -export function resizeCanvasToDisplaySize( - canvas: HTMLCanvasElement, - multiplier?: number, -): boolean { - multiplier = multiplier || 1; - var width = canvas.clientWidth * multiplier | 0; - var height = canvas.clientHeight * multiplier | 0; - if (canvas.width !== width || canvas.height !== height) { - canvas.width = width; - canvas.height = height; - return true; - } - return false; -} - -export class FPSCounter { - last: number; - count: number; - _delta: number; - _prev: number; - - _frame_start: number; - _total_frametime: number; - - constructor() { - this.last = 0; - this.count = 0; - this._delta = 0; - this._prev = 0; - } - - frame(now: number) { - this._frame_start = performance.now(); - this.count += 1; - this._delta = now - this._prev; - this._prev = now; - - if (now - this.last > 1000) { - this.last = now; - console.log(`${this.count} fps, ${(this._total_frametime / this.count).toFixed(2)}ms avg per frame`); - this.count = 0; - this._total_frametime = 0; - } - } - - frame_end() { - this._total_frametime += (performance.now() - this._frame_start); - } - - delta(now: number): number { - return this._delta; - } -} - -export class Resizer { - hoovering = false; - dragging = false; - - mouse_pos = [0, 0]; - last_drag = [0, 0]; - - viewbox: number[]; - orig_viewbox: number[]; - - el_box: number[]; - - scaleX = 1; - scaleY = 1; - - constructor(el: HTMLCanvasElement, viewbox: number[], keep_aspect_ratio=false) { - viewbox = [-viewbox[0] - viewbox[2], - viewbox[1] - viewbox[3], viewbox[2], viewbox[3]]; - this.viewbox = [...viewbox]; - this.el_box = [el.width, el.height]; - - if (keep_aspect_ratio) { - const or_width = this.viewbox[2]; - const or_height = this.viewbox[3]; - - const width_percentage = this.viewbox[2] / el.width; - const height_percentage = this.viewbox[3] / el.height; - - if (width_percentage < height_percentage) { - // width should be larger - this.viewbox[2] = height_percentage * el.width; - } else { - // height should be larger - this.viewbox[3] = width_percentage * el.height; - } - - this.viewbox[0] -= (this.viewbox[2] - or_width) / 2; - this.viewbox[1] -= (this.viewbox[3] - or_height) / 2; - - this.scaleX = this.viewbox[2] / this.viewbox[3]; - } - - this.orig_viewbox = [...this.viewbox]; - - el.addEventListener("mouseenter", this.mouseenter.bind(this), { capture: false, passive: true}); - el.addEventListener("mouseleave", this.mouseleave.bind(this), { capture: false, passive: true}); - el.addEventListener("mousemove", this.mousemove.bind(this), { capture: false, passive: true}); - el.addEventListener("mousedown", this.mousedown.bind(this), { capture: false, passive: true}); - el.addEventListener("mouseup", this.mouseup.bind(this), { capture: false, passive: true}); - - window.addEventListener('wheel', this.wheel.bind(this), { capture: false, passive: true}); - } - - _clip_viewbox() { - this.viewbox[0] = Math.max(this.viewbox[0], this.orig_viewbox[0]); - this.viewbox[1] = Math.max(this.viewbox[1], this.orig_viewbox[1]); - - this.viewbox[0] = Math.min(this.viewbox[0] + this.viewbox[2], this.orig_viewbox[0] + this.orig_viewbox[2]) - this.viewbox[2]; - this.viewbox[1] = Math.min(this.viewbox[1] + this.viewbox[3], this.orig_viewbox[1] + this.orig_viewbox[3]) - this.viewbox[3]; - } - - mouseenter() { - this.hoovering = true; - } - - mouseleave() { - this.hoovering = false; - } - - mousemove(e: MouseEvent) { - this.mouse_pos = [e.offsetX, this.el_box[1] - e.offsetY]; - - if (this.dragging) { - const scaleX = this.viewbox[2] / this.el_box[0]; - const scaleY = this.viewbox[3] / this.el_box[1]; - - this.viewbox[0] += (this.last_drag[0] - this.mouse_pos[0]) * scaleX; - this.viewbox[1] += (this.last_drag[1] - this.mouse_pos[1]) * scaleY; - - this.last_drag = [...this.mouse_pos]; - - this._clip_viewbox(); - } - } - - mousedown() { - this.dragging = true; - this.last_drag = [...this.mouse_pos]; - } - - mouseup() { - this.dragging = false; - } - - wheel(e: WheelEvent) { - if (this.hoovering) { - const delta = e.deltaY > 0 ? 0.1 * this.viewbox[2] : -0.1 * this.viewbox[2]; - const dx = delta * this.scaleX; - const dy = delta * this.scaleY; - - const mouse_dx = this.mouse_pos[0] / this.el_box[0]; - const mouse_dy = this.mouse_pos[1] / this.el_box[1]; - - this._zoom([dx, dy], [mouse_dx, mouse_dy]); - } - } - - _zoom(deltas: number[], center: number[]) { - this.viewbox[2] += deltas[0]; - this.viewbox[0] -= deltas[0] * center[0]; - this.viewbox[2] = Math.min(this.viewbox[2], this.orig_viewbox[2]); - - this.viewbox[3] += deltas[1]; - this.viewbox[1] -= deltas[1] * center[1]; - this.viewbox[3] = Math.min(this.viewbox[3], this.orig_viewbox[3]); - - this._clip_viewbox(); - } - - get_viewbox(): number[] { - return this.viewbox; - } - - get_mouse_pos(): number[] { - return this.mouse_pos; - } -} - -export class Mesh { - cells: number[]; - positions: number[]; - - constructor(mesh: any) { - this.cells = mesh.cells.flat(); - this.positions = mesh.positions.flat(); - } -} - -export async function url_to_mesh(url: string): Promise<Mesh> { - - return new Promise(function(resolve) { - fetch(url) - .then(resp => resp.text()) - .then(data => { - // var div = document.createElement('div'); - // div.innerHTML = data; - // var svg = div.querySelector('svg'); - - var svgPath = parsePath(data); - var mesh = svgMesh3d(svgPath, { - delaunay: false, - scale: 10, - }); - - resolve(new Mesh(mesh)); - }) - }); -} diff --git a/web/pw-frontend/src/lib/visualizer/webgl/vertexBufferLayout.ts b/web/pw-frontend/src/lib/visualizer/webgl/vertexBufferLayout.ts deleted file mode 100644 index f44ed47..0000000 --- a/web/pw-frontend/src/lib/visualizer/webgl/vertexBufferLayout.ts +++ /dev/null @@ -1,115 +0,0 @@ -import type { VertexBuffer } from './buffer'; -import type { Shader } from './shader'; - -export class VertexBufferElement { - type: number; - amount: number; - type_size: number; - normalized: boolean; - index: string; - - constructor( - type: number, - amount: number, - type_size: number, - index: string, - normalized: boolean, - ) { - this.type = type; - this.amount = amount; - this.type_size = type_size; - this.normalized = normalized; - this.index = index; - } -} - -export class VertexBufferLayout { - elements: VertexBufferElement[]; - stride: number; - offset: number; - - constructor(offset = 0) { - this.elements = []; - this.stride = 0; - this.offset = offset; - } - - // Maybe wrong normalized type - push( - type: number, - amount: number, - type_size: number, - index: string, - normalized = false, - ) { - this.elements.push(new VertexBufferElement(type, amount, type_size, index, normalized)); - this.stride += amount * type_size; - } - - getElements(): VertexBufferElement[] { - return this.elements; - } - - getStride(): number { - return this.stride; - } -} - -// glEnableVertexAttribArray is to specify what location of the current program the follow data is needed -// glVertexAttribPointer tells gl that that data is at which location in the supplied data -export class VertexArray { - // There is no renderer ID, always at bind buffers and use glVertexAttribPointer - buffers: VertexBuffer[]; - layouts: VertexBufferLayout[]; - - constructor() { - this.buffers = []; - this.layouts = []; - } - - addBuffer(vb: VertexBuffer, layout: VertexBufferLayout) { - this.buffers.push(vb); - this.layouts.push(layout); - } - - updateBuffer(gl: WebGLRenderingContext, index: number, data: number[]) { - this.buffers[index].updateData(gl, data); - } - - /// Bind buffers providing program data - bind(gl: WebGLRenderingContext, shader: Shader) { - shader.bind(gl); - for(let i = 0; i < this.buffers.length; i ++) { - const buffer = this.buffers[i]; - const layout = this.layouts[i]; - - buffer.bind(gl); - const elements = layout.getElements(); - let offset = layout.offset; - - for (let j = 0; j < elements.length; j ++) { - const element = elements[j]; - const location = shader.getAttribLocation(gl, element.index); - - if (location >= 0) { - gl.enableVertexAttribArray(location); - gl.vertexAttribPointer( - location, element.amount, element.type, - element.normalized, layout.stride, offset - ); - } - - offset += element.amount * element.type_size; - } - } - } - - /// Undo bind operation - unbind(gl: WebGLRenderingContext) { - this.layouts.forEach((layout) => { - layout.getElements().forEach((_, index) => { - gl.disableVertexAttribArray(index); - }); - }) - } -} diff --git a/web/pw-frontend/vite.config.js b/web/pw-frontend/vite.config.js index a7fcc74..84889ec 100644 --- a/web/pw-frontend/vite.config.js +++ b/web/pw-frontend/vite.config.js @@ -7,7 +7,7 @@ import wasmPack from 'vite-plugin-wasm-pack'; export default defineConfig({ plugins: [ svelte(), - wasmPack(["./planetwars-rs"]), + wasmPack([], ["planetwars-rs"]), viteCommonjs({ transformMixedEsModules: true, }), |