void Octree::trim_octree()

in octree/octree/octree.cpp [1004:1135]

• 101 lines of code
• 35 McCabe index (conditional complexity)

void Octree::trim_octree() {
  if (!oct_info_.is_adaptive()) return;
  const int depth = oct_info_.depth();
  const int depth_adp = oct_info_.adaptive_layer();
  const float th_dist = oct_info_.threshold_distance();
  const float th_norm = oct_info_.threshold_normal();
  const bool has_dis = oct_info_.has_displace();

  // generate the drop flag
  enum TrimType { kDrop = 0, kDropChildren = 1,  kKeep = 2 };
  vector<vector<TrimType> > drop(depth + 1);
  for (int d = 0; d <= depth; ++d) {
    drop[d].resize(oct_info_.node_num(d), kKeep);
  }
  for (int d = depth_adp; d <= depth; ++d) {
    int nnum_dp = oct_info_.node_num(d - 1);
    const vector<int>& children_d = children_[d];
    const vector<int>& children_dp = children_[d - 1];
    vector<TrimType>& drop_d = drop[d];
    vector<TrimType>& drop_dp = drop[d - 1];

    bool all_drop = true;
    // generate the drop flag
    for (int i = 0; i < nnum_dp; ++i) {
      int t = children_dp[i];
      if (node_type(t) == kLeaf) continue;

      // generate the drop flag for 8 children nodes:
      // drop the node if its parent node is kDrop or kDropChildren,
      // set the node as kDropChildren if the error is smaller than a threshold
      for (int j = 0; j < 8; ++j) {
        int idx = t * 8 + j;
        if (drop_dp[i] == kKeep) {
          // note that for all the leaf nodes and the finest nodes,
          // distance_err_[d][i] is equal to 1.0e20f, so if it enters the following
          // "if" body, the node_type(children_d[idx]) must be kInternelNode
          //if (distance_err_[d][idx] < th_dist) {
          if ((!has_dis || (has_dis && distance_err_[d][idx] < th_dist)) &&
              normal_err_[d][idx] < th_norm) {
            drop_d[idx] = kDropChildren;
          }
        } else {
          drop_d[idx] = kDrop;
        }

        if (all_drop) {
          // all_drop is false: there is at least one internal node which is kept
          all_drop = !(drop_d[idx] == kKeep &&
                  node_type(children_d[idx]) == kInternelNode);
        }
      }
    }

    // make sure that there is at least one octree node in each layer
    if (all_drop) {
      int max_idx = 0;
      float max_err = -1.0f;
      for (int i = 0; i < nnum_dp; ++i) {
        int t = children_dp[i];
        if (node_type(t) == kLeaf || drop_dp[i] != kKeep) continue;

        for (int j = 0; j < 8; ++j) {
          int idx = t * 8 + j;
          if (node_type(children_d[idx]) == kInternelNode &&
              normal_err_[d][idx] > max_err) {
            max_err = normal_err_[d][idx];
            max_idx = idx;
          }
        }
      }
      drop_d[max_idx] = kKeep;
    }
  }

  // trim the octree
  for (int d = depth_adp; d <= depth; ++d) {
    int nnum_d = oct_info_.node_num(d);
    const vector<TrimType>& drop_d = drop[d];

    vector<uintk> key;
    for (int i = 0; i < nnum_d; ++i) {
      if (drop_d[i] == kDrop) continue;
      key.push_back(keys_[d][i]);
    }
    keys_[d].swap(key);

    vector<int> children;
    for (int i = 0, id = 0; i < nnum_d; ++i) {
      if (drop_d[i] == kDrop) continue;
      int ch = (drop_d[i] == kKeep && node_type(children_[d][i]) != kLeaf) ? id++ : -1;
      children.push_back(ch);
    }
    children_[d].swap(children);

    auto trim_data = [&](vector<float>& signal) {
      vector<float> data;
      int channel = signal.size() / nnum_d;
      if (channel == 0) return;
      for (int i = 0; i < nnum_d; ++i) {
        if (drop_d[i] == kDrop) continue;
        for (int c = 0; c < channel; ++c) {
          data.push_back(signal[c * nnum_d + i]);
        }
      }
      //signal.swap(data);
      // transpose
      int num = data.size() / channel;
      signal.resize(data.size());
      for (int i = 0; i < num; ++i) {
        for (int c = 0; c < channel; ++c) {
          signal[c * num + i] = data[i * channel + c];
        }
      }
    };

    trim_data(displacement_[d]);
    trim_data(avg_normals_[d]);
    trim_data(avg_features_[d]);
    trim_data(avg_labels_[d]);
  }

  // update the node number
  calc_node_num();

  // generate split label
  if (oct_info_.has_property(OctreeInfo::kSplit)) {
    calc_split_label();
  }

  // serialization
  serialize();
}