balance method

DBVTNode balance(DBVTNode node)

Balance the dynamic bounding volume node according to the input

Implementation

DBVTNode balance(DBVTNode node) {
  double nh = node.height;
  if(nh<2){
    return node;
  }
  var p = node.parent;
  DBVTNode l = node.child1!;
  DBVTNode r = node.child2!;
  double lh = l.height;
  double rh = r.height;
  double balance = lh-rh;
  int t;// for bit operation

  //          [ N ]
  //         /     \
  //    [ L ]       [ R ]
  //     / \         / \
  // [L-L] [L-R] [R-L] [R-R]

  // Is the tree balanced?
  if(balance>1){
    DBVTNode ll = l.child1!;
    DBVTNode lr = l.child2!;
    double llh = ll.height;
    double lrh = lr.height;

    // Is L-L higher than L-R?
    if(llh>lrh){
      // set N to L-R
      l.child2 = node;
      node.parent = l;

      //          [ L ]
      //         /     \
      //    [L-L]       [ N ]
      //     / \         / \
      // [...] [...] [ L ] [ R ]

      // set L-R
      node.child1 = lr;
      lr.parent = node;

      //          [ L ]
      //         /     \
      //    [L-L]       [ N ]
      //     / \         / \
      // [...] [...] [L-R] [ R ]

      // fix bounds and heights
      node.aabb.combine( lr.aabb, r.aabb );
      t = (lrh-rh).toInt();
      node.height=lrh-(t&t>>31)+1;
      l.aabb.combine(ll.aabb,node.aabb);
      t=(llh-nh).toInt();
      l.height=llh-(t&t>>31)+1;
    }
    else{
      // set N to L-L
      l.child1=node;
      node.parent=l;

      //          [ L ]
      //         /     \
      //    [ N ]       [L-R]
      //     / \         / \
      // [ L ] [ R ] [...] [...]

      // set L-L
      node.child1 = ll;
      ll.parent = node;

      //          [ L ]
      //         /     \
      //    [ N ]       [L-R]
      //     / \         / \
      // [L-L] [ R ] [...] [...]

      // fix bounds and heights
      node.aabb.combine(ll.aabb,r.aabb);
      t = (llh - rh).toInt();
      node.height=llh-(t&t>>31)+1;

      l.aabb.combine(node.aabb,lr.aabb);
      t=(nh-lrh).toInt();
      l.height=nh-(t&t>>31)+1;
    }
    // set new parent of L
    if(p!=null){
      if(p.child1==node){
        p.child1=l;
      }
      else{
        p.child2=l;
      }
    }
    else{
      root=l;
    }
    l.parent=p;
    return l;
  }
  else if(balance<-1){
    DBVTNode rl = r.child1!;
    DBVTNode rr = r.child2!;
    double rlh = rl.height;
    double rrh = rr.height;

    // Is R-L higher than R-R?
    if( rlh > rrh ) {
      // set N to R-R
      r.child2 = node;
      node.parent = r;

      //          [ R ]
      //         /     \
      //    [R-L]       [ N ]
      //     / \         / \
      // [...] [...] [ L ] [ R ]

      // set R-R
      node.child2 = rr;
      rr.parent = node;

      //          [ R ]
      //         /     \
      //    [R-L]       [ N ]
      //     / \         / \
      // [...] [...] [ L ] [R-R]

      // fix bounds and heights
      node.aabb.combine(l.aabb,rr.aabb);
      t = (lh-rrh).toInt();
      node.height = lh-(t&t>>31)+1;
      r.aabb.combine(rl.aabb,node.aabb);
      t =( rlh-nh).toInt();
      r.height = rlh-(t&t>>31)+1;
    }
    else{
      // set N to R-L
      r.child1 = node;
      node.parent = r;
      //          [ R ]
      //         /     \
      //    [ N ]       [R-R]
      //     / \         / \
      // [ L ] [ R ] [...] [...]

      // set R-L
      node.child2 = rl;
      rl.parent = node;

      //          [ R ]
      //         /     \
      //    [ N ]       [R-R]
      //     / \         / \
      // [ L ] [R-L] [...] [...]

      // fix bounds and heights
      node.aabb.combine(l.aabb,rl.aabb);
      t=(lh-rlh).toInt();
      node.height=lh-(t&t>>31)+1;
      r.aabb.combine(node.aabb,rr.aabb);
      t=(nh-rrh).toInt();
      r.height=nh-(t&t>>31)+1;
    }
    // set new parent of R
    if(p!=null){
      if(p.child1==node){
        p.child1=r;
      }
      else{
        p.child2=r;
      }
    }
    else{
        root=r;
    }
    r.parent=p;
    return r;
  }
  return node;
}