<commit_before>loadAll(['mesh/bunny.obj'], function(hash){
  var t1 = performance.now();
  var triangles = parseMesh(hash['mesh/bunny.obj']);
  //triangles = triangles.concat(parseMesh(hash['mesh/bunny.obj']));
  var bvh = new BVH(triangles, 4);
  console.log(bvh.serializeTree());
  console.log(performance.now() - t1);

  runTest(bvh);
  console.log(bvh)
});

function runTest(bvh){
  var canvas = document.getElementById('trace');
  canvas.width = canvas.height = 400;
  var ctx = canvas.getContext('2d');
  var t1;
  // t1 = performance.now();
  // naiveTrace(canvas, ctx, root);
  // console.log(performance.now() - t1);
  t1 = performance.now();
  //treeTrace(canvas, ctx, bvh.root);
  arrayTreeTrace(canvas, ctx, bvh.serializeTree());
  console.log(performance.now() - t1);
}

function drawPixels(canvas, ctx, algorithm){
  for(var i=0; i<canvas.width; i++){
    for(var j=0; j<canvas.height; j++){
      var shift = [0, 0.25, 0.75];
      var origin = [0, 0, -1];
      var halfWidth = canvas.width/2;
      var halfHeight = canvas.height/2;
      var light = [0, 5, -5];
      var dir = normalize(sub([ (i/halfWidth-1), -(j/halfHeight - 1), 0], origin));
      origin = add(origin, shift);
      var ray = new Ray(origin, dir);
      var res = algorithm(ray);
      if(res[0] < Infinity && res[0] > 0){
        origin = add(origin, scale(dir, res[0]));
        dir = normalize(sub(light, origin));
        ray = new Ray(origin, dir);
        var shadow = algorithm(ray);
        var color = getColor(res[1], shadow, dir, light, origin);
        ctx.fillStyle = "rgb("+color[0]+","+color[1]+","+color[2]+")";
      } else {
        ctx.fillStyle = "#ffffff";
      }
      ctx.fillRect( i, j, 1, 1 );
      ctx.fill()
    }
  }
}

function stacklessTreeTrace(canvas, ctx, array){
  var fromSibling = 0,
      fromChild = 1,
      fromParent = 2;
  var rootIdx = 0;
  var res = [Infinity, null];

  function orderedChildren(ray, split, rootIdx){
    var root = array[rootIdx].node,
        left = root.left,
        right = root.right;

    if(ray.dir[split] > 0){
      return {near: left, far: right}
    } else {
      return {near: right, far: left}
    }
  }

  function traverse(ray){
    var state = fromParent;
    var current = orderedChildren(ray, array[rootNode].node.split, rootIdx).near;
    while(true){
      var node = array[current].node;
      var ordered = orderedChildren(ray, node.split, current);
      switch(state){
        case fromChild:
          if(current == rootNode){
            return res;
          }
          var parentOrdered =
          if(current == array[ordered.near]){

          }
          break;
        case fromSibling:
          break;
        case fromParent:
          break;
      }
    }
  }
}

function arrayTreeTrace(canvas, ctx, array){
  var algorithm = function (ray) {
    return findTrianglesFlat(ray, array, 0)<commit_msg>software stackless traversal<commit_after>loadAll(['mesh/bunny.obj'], function(hash){
  var t1 = performance.now();
  var triangles = parseMesh(hash['mesh/bunny.obj']);
  //triangles = triangles.concat(parseMesh(hash['mesh/bunny.obj']));
  var bvh = new BVH(triangles, 4);
  console.log(bvh.serializeTree());
  console.log(performance.now() - t1);

  runTest(bvh);
  console.log(bvh)
});

function runTest(bvh){
  var canvas = document.getElementById('trace');
  canvas.width = canvas.height = 400;
  var ctx = canvas.getContext('2d');
  var t1;
  // t1 = performance.now();
  // naiveTrace(canvas, ctx, root);
  // console.log(performance.now() - t1);
  t1 = performance.now();
  //treeTrace(canvas, ctx, bvh.root);
  //arrayTreeTrace(canvas, ctx, bvh.serializeTree());
  stacklessTreeTrace(canvas, ctx, bvh.serializeTree());
  console.log(performance.now() - t1);
}

function drawPixels(canvas, ctx, algorithm){
  for(var i=0; i<canvas.width; i++){
    for(var j=0; j<canvas.height; j++){
      var shift = [0, 0.25, 0.75];
      var origin = [0, 0, -1];
      var halfWidth = canvas.width/2;
      var halfHeight = canvas.height/2;
      var light = [0, 5, -5];
      var dir = normalize(sub([ (i/halfWidth-1), -(j/halfHeight - 1), 0], origin));
      origin = add(origin, shift);
      var ray = new Ray(origin, dir);
      var res = algorithm(ray);
      if(res[0] < Infinity && res[0] > 0){
        origin = add(origin, scale(dir, res[0]));
        dir = normalize(sub(light, origin));
        ray = new Ray(origin, dir);
        var shadow = algorithm(ray);
        var color = getColor(res[1], shadow, dir, light, origin);
        ctx.fillStyle = "rgb("+color[0]+","+color[1]+","+color[2]+")";
      } else {
        ctx.fillStyle = "#ffffff";
      }
      ctx.fillRect( i, j, 1, 1 );
      ctx.fill()
    }
  }
}

function stacklessTreeTrace(canvas, ctx, array){
  var fromSibling = 0,
      fromChild = 1,
      fromParent = 2;
  var rootIdx = 0;
  var res = [Infinity, null];

  function orderedChildren(ray, nodeIdx){
    var node = array[nodeIdx].node,
        left = array[nodeIdx].left,
        right = array[nodeIdx].right;

    if(ray.dir[node.split] > 0){
      return {near: left, far: right}
    } else {
      return {near: right, far: left}
    }
  }

  function traverse(ray){
    var res = [Infinity, null];
    var state = fromParent;
    var current = orderedChildren(ray, rootIdx).near;
    while(true){
      var fromArray = array[current]
      var node = fromArray.node;
      var ordered = orderedChildren(ray, current);
      switch(state){
        case fromChild:
          if(current == rootIdx){
            return res;
          }
          var parentOrdered = orderedChildren(ray, fromArray.parent)
          if(current == parentOrdered.near){
            current = fromArray.sibling;
            state = fromSibling;
          } else {
            current = fromArray.parent
            state = fromChild;
          }
          break;
        case fromSibling:
          var test = rayBoxIntersect(ray, node.boundingBox)
          if(test == Infinity){
            current = fromArray.parent;
            state = fromChild;
          } else if (node.leaf) {
            processed = processLeaf(ray, node);
            if(processed[0] < res[0]){
              res = processed;
            }
            current = fromArray.parent;
            state = fromChild;
          } else {
            current = ordered.near
            state = fromParent;
          }
          break;
        case fromParent:
          var test = rayBoxIntersect(ray, node.boundingBox)
          if(test == Infinity){
            current = fromArray.sibling;
            state = fromSibling;
          } else if(node.leaf){
            processed = processLeaf(ray, node);
            if(processed[0] < res[0]){
              res = processed;
            }
            current = fromArray.sibling;
            state = fromSibling;
          } else {
            current = ordered.near;
            state = fromParent;
          }
          break;
      }
    }
  }
  drawPixels(canvas, ctx, traverse)
}

function arrayTreeTrace(canvas, ctx, array){
  var algorithm = function (ray) {
    return findTrianglesFlat(ray, array, 0)
{'fraction_non_alphanumeric': 0.1479870949642306, 'fraction_numerical': 0.014027212792818067, 'mean_word_length': 2.3178222429036763, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6384055', 'n_tokens_mistral': 2371, 'n_tokens_neox': 2271, 'n_words': 537}