Pen Settings

HTML

CSS

CSS Base

Vendor Prefixing

Add External Stylesheets/Pens

Any URLs added here will be added as <link>s in order, and before the CSS in the editor. You can use the CSS from another Pen by using its URL and the proper URL extension.

+ add another resource

JavaScript

Babel includes JSX processing.

Add External Scripts/Pens

Any URL's added here will be added as <script>s in order, and run before the JavaScript in the editor. You can use the URL of any other Pen and it will include the JavaScript from that Pen.

+ add another resource

Packages

Add Packages

Search for and use JavaScript packages from npm here. By selecting a package, an import statement will be added to the top of the JavaScript editor for this package.

Behavior

Auto Save

If active, Pens will autosave every 30 seconds after being saved once.

Auto-Updating Preview

If enabled, the preview panel updates automatically as you code. If disabled, use the "Run" button to update.

Format on Save

If enabled, your code will be formatted when you actively save your Pen. Note: your code becomes un-folded during formatting.

Editor Settings

Code Indentation

Want to change your Syntax Highlighting theme, Fonts and more?

Visit your global Editor Settings.

HTML

              
                <head>
    <script type="importmap">
        {
            "imports": {
                "three": "https://unpkg.com/three@0.157.0/build/three.module.js",
                "OrbitControls": "https://unpkg.com/three@0.157.0/examples/jsm/controls/OrbitControls.js"
            }
        }
    </script>
</head>

<canvas id="c">
</canvas>

<script src="https://unpkg.com/delaunator@3.0.2/delaunator.js"></script>
<script src="https://josephg.github.io/noisejs/perlin.js"></script>
              
            
!

CSS

              
                html, body {
  height: 100%;
  margin: 0;
}

#c {
  width: 100%;
  height: 100%;
  display: block;
}

              
            
!

JS

              
                import * as THREE from 'three';
import { OrbitControls } from 'OrbitControls';

function resizeRendererToDisplaySize(renderer, camera) {
  const canvas = renderer.domElement;
  const width = canvas.clientWidth;
  const height = canvas.clientHeight;
  const needResize = canvas.width !== width || canvas.height !== height;
  if (needResize) {
    renderer.setSize(width, height, false);
    camera.aspect = window.innerWidth / window.innerHeight;
    camera.updateProjectionMatrix();
  }
  return needResize;
}


const canvas = document.querySelector('#c');
var gui = new dat.GUI();

var scene = new THREE.Scene();

//create some camera
var camera = new THREE.PerspectiveCamera(55, window.innerWidth / window.innerHeight, 0.1, 1000);
camera.position.x = 0;
camera.position.y = 0;
camera.position.z = 1;
camera.lookAt(0, 0, 0);

var renderer = new THREE.WebGLRenderer({
  canvas, 
  antialias: true
});
//renderer.setSize(window.innerWidth, window.innerHeight);
renderer.setPixelRatio(1.5);
renderer.setClearColor(new THREE.Color(0x595959));
//document.body.appendChild(renderer.domElement);

var controls = new OrbitControls(camera, renderer.domElement);

// white spotlight shining from the side, casting a shadow
var spotLight = new THREE.SpotLight(0xffffff, 2.5, 25, Math.PI / 6);
spotLight.position.set(4, 10, 7);
scene.add(spotLight);




//
function lerp(v0, v1, u) {
  return v0 + (v1-v0) * u
}

function mod(x, y){
  return ((x % y) + y) % y;
}



function clamp(a, min, max){
  return Math.max(Math.min(a, max), min);
}
function fitrange(value, min1, max1, min2, max2){
  return min2 + (value - min1) * (max2 - min2) / (max1 - min1); 
}


function smoothstep(h,l,x){
  var t = clamp((x - h) / (l - h), 0.0, 1.0);
  return t * t * (3.0 - 2.0 * t);
}
//does argmin and index into list all at once for speed
function get_nearest_Q(Q, dists){
  let min = 1e10;
  let index = -1;
  for(let i = 0; i < Q.length; i++){
    if(dists[Q[i]] < min){
      min = dists[Q[i]];
      index = i;
    }
  }
  return index;
}



function perlin2_grad(pos){
    let h = .01;
    let dx = noise.perlin2(pos.x - h, pos.y) - noise.perlin2(pos.x + h, pos.y);
    let dy = noise.perlin2(pos.x, pos.y - h) - noise.perlin2(pos.x, pos.y + h);
    return new THREE.Vector3(dx / h, 0, dy / h);
}

function perlin2_grad2(pos){
    let h = .01;
    let dx = noise.perlin2(pos.x - h, pos.y) - noise.perlin2(pos.x + h, pos.y);
    let dy = noise.perlin2(pos.x, pos.y - h) - noise.perlin2(pos.x, pos.y + h);
    return new THREE.Vector2(dx / h, dy / h);
}

function outerproduct2(u){
    return [u.x * u.x, u.x * u.y, 
            u.y * u.x, u.y * u.y];
}
function add2(u, v){
  return [u[0] + v[0], u[1] + v[1], u[2] + v[2], u[3] + v[3]]
}

function determinant2(q){
  return q[0] * q[3] - q[1] * q[2];
}
function eigvals2(q){
  //https://www.johndcook.com/blog/2021/05/07/trick-for-2x2-eigenvalues/
  let m = (q[0] + q[3]) / 2.0;
  let d = determinant2(q);
  return [m + Math.sqrt(m * m - d), m - Math.sqrt(m * m - d)];
}

function eigvectors2(q, eigvals){
  //https://people.math.harvard.edu/~knill/teaching/math21b2004/exhibits/2dmatrices/index.html
  let [g0, g1] = eigvals;
  if(q[3] != 0){
    return [[g0 - q[3], q[2]], [g1 - q[3], q[2]]];
  }
  if(q[2] != 0){
    return [ [q[1], g0 - q[0]], [q[1], g1 - q[0]] ];
  }
  return [[1,0],[0,1]];
}


function normalize2(u){
  let mag = Math.sqrt(u[0] * u[0] + u[1] * u[1]);
  if(mag == 0.0){
    return [0,0];
  }
  return [u[0] / mag, u[1] / mag]
}
function make_metric(vec2_in, anisotropy){
  let q = outerproduct2(vec2_in);
  let [g0,g1] = eigvals2(q);
  let [e0, e1] = eigvectors2(q, [g0,g1]);
  e0 = normalize2(e0); e1 = normalize2(e1);
  function gamma(x, n){
    return Math.pow(n + Math.abs(x), -1);
  }
  let n = 1 - anisotropy;
  if(n == 0) n += 1e-7;
  let gamma_g0 = gamma(g0, n);
  let gamma_g1 = gamma(g1, n);
  let h0 = outerproduct2(new THREE.Vector2(e0[0] * gamma_g0, e0[1] * gamma_g0));
  let h1 = outerproduct2(new THREE.Vector2(e1[0] * gamma_g1, e1[1] * gamma_g1));
  return add2(h0, h1);

}

function vec2m2x2(A, u){

  return new THREE.Vector2(A[0] * u.x + A[2] * u.y, A[1] * u.x + A[3] * u.y);
}


class Graph{
  constructor(Geometry){
      this.geometry = Geometry;
      this.neighbours_list = this.build_neighborhood();
      this.vert_count = this.neighbours_list.length;
      this.positions = this.geometry.getAttribute("position").array;
      this.edge_weights = [];
  }
  build_neighborhood(){
    let indices = this.geometry.index.array;
    let n_indices = indices.length;
    let neighbours = [];
    for(let i  = 0; i < n_indices; i++){
        let start = Math.floor(i / 3) * 3;
        let offset = i - start;
        let nb_index0 = indices[((offset + 1) % 3) + start];
        let nb_index1 = indices[((offset + 2) % 3) + start];
        if(neighbours[indices[i]] === undefined) neighbours[indices[i]] = [];
        if(!neighbours[indices[i]].includes(nb_index0)) neighbours[indices[i]].push(nb_index0);
        if(!neighbours[indices[i]].includes(nb_index1)) neighbours[indices[i]].push(nb_index1);
    }
    return neighbours;
  }
  build_edgeWeightsMetric(edge_funct){ //edge function needs to return a vector2
    let weights = [];
    for(let i = 0; i < this.vert_count; i++){
      let nbs = this.neighbours(i);
      if(weights[i] === undefined) weights[i] = [];
      for(let j = 0; j < nbs.length; j++){
          let p0 = this.P(i);
          let p1 = this.P(nbs[j]);
          let Pavg = p0.add(p1).multiplyScalar(.5); //middle of edge
          let edge_dir = p1.sub(p0);
          let edge_dir2 = new THREE.Vector2(edge_dir.x, edge_dir.y); 
          let metric = make_metric(edge_funct(Pavg), .9999);
          weights[i][j] = edge_dir2.dot(vec2m2x2(metric, edge_dir2));
      }
    }
    this.edge_weights = weights;
  }
  neighbours(index){
    return this.neighbours_list[index];
  }
  P(index){
    return new THREE.Vector3(this.positions[index * 3 + 0], this.positions[index * 3 + 1], this.positions[index * 3 + 2]);
  }
}

let direction_function_selector = {
  0: x => {return curl_noise(x,  scene_parms["Noise Scale"])},
  1: x => {return new THREE.Vector2(1,0)},
  2: x => {return new THREE.Vector2(0,1)},
}

let scene_parms = {
  "Number of Nodes": 8000,
  "Toggle Vector Visualizers": true,
  "Source Point": 0,
  "Metric Weighted Dijkstras": true,
  "Visualizer Scale": .0075,
  "Normalize Visualizers": true,
  "Noise Function": 0,
  "Noise Scale": 2,
  update_graph: function (){
    this.graph = new Graph(make_mesh(scene, this["Number of Nodes"]));
    return;
  },
  graph: new Graph(make_mesh(scene, 8000)) ,
}



function make_mesh(scene, number_of_nodes){
  //detect if dijkstras exists already and blast it away :)
  var old_mesh = scene.getObjectByName("backplane_mesh");
  if(old_mesh != undefined){
    scene.remove(old_mesh);
 }

  var size = { x: 1, y: 1 };
  var points3d = [];
  for (let i = 0; i < number_of_nodes; i++) {
    let x = (THREE.MathUtils.seededRandom(i) - .5) * size.x;
    let y = (THREE.MathUtils.seededRandom(i + number_of_nodes) - .5) *  size.y;
    points3d.push(new THREE.Vector3(x, y, 0));
  }


  var geometry = new THREE.BufferGeometry().setFromPoints(points3d);
  var cloud = new THREE.Points(
    geometry,
    new THREE.PointsMaterial({ color: 0x99ccff, size: 2 })
  );

  // triangulate x, z
  var indexDelaunay = Delaunator.from(
    points3d.map(v => {
      return [v.x, v.y];
    })
  );

  var meshIndex = []; // delaunay index => three.js index
  for (let i = 0; i < indexDelaunay.triangles.length; i++){
    meshIndex.push(indexDelaunay.triangles[i]);
  }

  geometry.setIndex(meshIndex); // add three.js index to the existing geometry
  geometry.computeVertexNormals();
  const material = new THREE.MeshBasicMaterial( {color: "blue", side: THREE.DoubleSide, wireframe: true, transparent: true, opacity: .1} );
  const plane = new THREE.Mesh( geometry.clone().translate(0,-.001,0), material );
  plane.name = "backplane_mesh";
  scene.add( plane );
  return geometry;
}



function curl_noise(pos, scale = 4){
  let noise = perlin2_grad2(pos.clone().multiplyScalar(scale));
  return new THREE.Vector2(noise.y, -noise.x); 
}







function dijkstras(Graph, source, use_edge_weights){
  let dists = Array(Graph.vert_count).fill(1e15); //infinity values for initial dists
  let prev = Array(Graph.vert_count).fill(-1); //undefined values for prev
  let Q = [...Array(Graph.vert_count).keys()]; //array with index values
  dists[source] = 0.0;
  while(Q.length != 0){
    let Q_u = get_nearest_Q(Q, dists); //finds the argmin of the lowest distance value in Q
    var u = Q[Q_u];
    Q.splice(Q_u,1); // remove u from Q
    let nbs = Graph.neighbours(u);
    for(let i = 0; i < nbs.length; i++){
        let v = nbs[i];
        if(!Q.includes(v)) continue; //if neighbor not in Q, continue 
        let alt = dists[u];
        if(!use_edge_weights){
          alt += Graph.P(u).distanceToSquared(Graph.P(v)); //get distance from Pu to Pv
        }else{
          alt +=  Graph.edge_weights[u][nbs.indexOf(v)]; //get distance from Pu to Pv
        }
        if(alt < dists[v]){ //if the distance is less than the current distance
          dists[v] = alt; //update distance 
          prev[v] = u; //update previous node
        }
    }

  }

  return [dists, prev];
}





function generate_dijkstras_wire(scene, scene_parms){ //graph, graph_source_index, use_edge_weights, edge_weight_function = curl_noise){

  //detect if dijkstras exists already and blast it away :)
  var old_lines = scene.getObjectByName("dijkstra_lines");
  var old_viz = scene.getObjectByName("viz_lines");
  if(old_lines != undefined){
    scene.remove(old_lines);
    scene.remove(old_viz);
  }
  let graph = scene_parms.graph;

  let edge_funct = direction_function_selector[scene_parms["Noise Function"]];
  if(scene_parms["Metric Weighted Dijkstras"]){
    graph.build_edgeWeightsMetric(edge_funct);
  }
  let [dists, prev] = dijkstras(graph, Math.min(Math.floor(scene_parms["Source Point"]), scene_parms["Number of Nodes"] - 1), scene_parms["Metric Weighted Dijkstras"]);

  
  let wire_indices = [];
  let wire_verts = [];
  const wire_buffer = new THREE.BufferGeometry();
  let wire_index_value = 0;

  let viz_indices = [];
  let viz_verts = [];
  const viz_buffer = new THREE.BufferGeometry();
  let viz_index_value = 0;
  for(let i = 0; i < prev.length; i++){
      if(prev[i] == -1) continue;
      wire_indices.push(wire_index_value++, wire_index_value++);
      viz_indices.push(viz_index_value++, viz_index_value++);

      let P0 = graph.P(i);
      let P1 = graph.P(prev[i]);
      let Pavg = new THREE.Vector3((P0.x + P1.x) / 2, (P0.y + P1.y) / 2, (P0.z + P1.z) / 2);
      let noise_vec = edge_funct(Pavg.clone());
      if(scene_parms["Normalize Visualizers"]) noise_vec.normalize();
      noise_vec.multiplyScalar(scene_parms["Visualizer Scale"]);

      wire_verts.push(P0.x, P0.y, P0.z, P1.x, P1.y, P1.z);
      viz_verts.push(Pavg.x, Pavg.y, Pavg.z, Pavg.x + noise_vec.x, Pavg.y + noise_vec.y, Pavg.z);
  }


  wire_buffer.setIndex(wire_indices);
  wire_buffer.setAttribute('position', new THREE.Float32BufferAttribute( wire_verts, 3 ));
  
  const wire_material = new THREE.LineBasicMaterial( {
    color: 0xffffff,
    linewidth: 1,
    linecap: 'round', //ignored by WebGLRenderer
    linejoin:  'round' //ignored by WebGLRenderer
  } );
  
  viz_buffer.setIndex(viz_indices);
  viz_buffer.setAttribute('position', new THREE.Float32BufferAttribute( viz_verts, 3 ));
  
  const viz_material = new THREE.LineBasicMaterial( {
    transparent: true,
    color: "yellow",
    linewidth: 1,
    linecap: 'round', //ignored by WebGLRenderer
    linejoin:  'round' //ignored by WebGLRenderer
  } );
  let new_lines = new THREE.LineSegments(wire_buffer, wire_material);
  let new_viz =  new THREE.LineSegments(viz_buffer, viz_material);
  new_lines.name = "dijkstra_lines";
  new_viz.name = "viz_lines";

  scene.add(new_lines);
  scene.add(new_viz);
}
generate_dijkstras_wire(scene, scene_parms);





//----------- UI ------------------//



gui.add(scene_parms, "Metric Weighted Dijkstras").onChange(x => { generate_dijkstras_wire(scene, scene_parms)} );
const noise_folder = gui.addFolder("Noise Settings")
noise_folder.add(scene_parms, "Noise Function", {"Curl Noise":0, "X+":1, "Y+":2}).onChange(x => { generate_dijkstras_wire(scene, scene_parms) } );
noise_folder.add(scene_parms, "Noise Scale", 1, 5).onFinishChange(x => {  generate_dijkstras_wire(scene, scene_parms) } );
gui.add(scene_parms, "Number of Nodes", 100, 10000, 1).onFinishChange(x => { scene_parms.update_graph(); generate_dijkstras_wire(scene, scene_parms);} );
let src_pt_controller = gui.add(scene_parms, "Source Point", 0, scene_parms["Number of Nodes"] - 1, 1).onFinishChange(x => {generate_dijkstras_wire(scene, scene_parms) } );
const viz_folder = gui.addFolder("Visualizer Settings")
viz_folder.add(scene_parms, "Toggle Vector Visualizers");
viz_folder.add(scene_parms, "Visualizer Scale", .001, .01).onChange(x => { generate_dijkstras_wire(scene, scene_parms)});
viz_folder.add(scene_parms, "Normalize Visualizers").onChange(x => { generate_dijkstras_wire(scene, scene_parms)});




var size = 0.005;
var vertGeometry = new THREE.BoxGeometry(size, size, size);
var vertMaterial = new THREE.MeshBasicMaterial({
  color: "Red",
  transparent: false
});


let source_p = scene_parms.graph.P(Math.floor(scene_parms["Source Point"]));

vertGeometry.translate(source_p)
console.log(source_p,vertGeometry);
scene.add(new THREE.Mesh(vertGeometry, vertMaterial))

function animate() {
  resizeRendererToDisplaySize(renderer, camera);

  var viz_geo = scene.getObjectByName("viz_lines");
  if(scene_parms["Toggle Vector Visualizers"]){
    viz_geo.material.opacity = 1;
  }else{
    viz_geo.material.opacity = 0;
  }
  //clamp source point to max number of nodes
  if(scene_parms["Number of Nodes"] - 1 != src_pt_controller._max){
    src_pt_controller.max(scene_parms["Number of Nodes"]);
    if(src_pt_controller.getValue() >= scene_parms["Number of Nodes"]){
      src_pt_controller.setValue(scene_parms["Number of Nodes"] - 1);
      scene_parms["Source Point"] = scene_parms["Number of Nodes"] - 1;
      generate_dijkstras_wire(scene, scene_parms)
    }
   
  }
  //move source visualizer
  if(scene_parms.graph.P(Math.floor(scene_parms["Source Point"])) != source_p){
    vertGeometry.translate(source_p.negate());
    source_p = scene_parms.graph.P(Math.floor(scene_parms["Source Point"]));
    vertGeometry.translate(source_p);
  }

  

  requestAnimationFrame(animate);
  controls.update();
  renderer.render(scene, camera);

};

animate();



//*/
              
            
!
999px

Console