draco/point_cloud/point_cloud.cc

// Copyright 2016 The Draco Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
#include "draco/point_cloud/point_cloud.h"

#include <algorithm>
#include <unordered_map>

namespace draco {

PointCloud::PointCloud() : num_points_(0) {}

int32_t PointCloud::NumNamedAttributes(GeometryAttribute::Type type) const {
  if (type == GeometryAttribute::INVALID ||
      type >= GeometryAttribute::NAMED_ATTRIBUTES_COUNT) {
    return 0;
  }
  return static_cast<int32_t>(named_attribute_index_[type].size());
}

int32_t PointCloud::GetNamedAttributeId(GeometryAttribute::Type type) const {
  return GetNamedAttributeId(type, 0);
}

int32_t PointCloud::GetNamedAttributeId(GeometryAttribute::Type type,
                                        int i) const {
  if (NumNamedAttributes(type) <= i) {
    return -1;
  }
  return named_attribute_index_[type][i];
}

const PointAttribute *PointCloud::GetNamedAttribute(
    GeometryAttribute::Type type) const {
  return GetNamedAttribute(type, 0);
}

const PointAttribute *PointCloud::GetNamedAttribute(
    GeometryAttribute::Type type, int i) const {
  const int32_t att_id = GetNamedAttributeId(type, i);
  if (att_id == -1) {
    return nullptr;
  }
  return attributes_[att_id].get();
}

const PointAttribute *PointCloud::GetNamedAttributeByUniqueId(
    GeometryAttribute::Type type, uint32_t unique_id) const {
  for (size_t att_id = 0; att_id < named_attribute_index_[type].size();
       ++att_id) {
    if (attributes_[named_attribute_index_[type][att_id]]->unique_id() ==
        unique_id) {
      return attributes_[named_attribute_index_[type][att_id]].get();
    }
  }
  return nullptr;
}

const PointAttribute *PointCloud::GetAttributeByUniqueId(
    uint32_t unique_id) const {
  const int32_t att_id = GetAttributeIdByUniqueId(unique_id);
  if (att_id == -1) {
    return nullptr;
  }
  return attributes_[att_id].get();
}

int32_t PointCloud::GetAttributeIdByUniqueId(uint32_t unique_id) const {
  for (size_t att_id = 0; att_id < attributes_.size(); ++att_id) {
    if (attributes_[att_id]->unique_id() == unique_id) {
      return static_cast<int32_t>(att_id);
    }
  }
  return -1;
}

int PointCloud::AddAttribute(std::unique_ptr<PointAttribute> pa) {
  SetAttribute(static_cast<int>(attributes_.size()), std::move(pa));
  return static_cast<int>(attributes_.size() - 1);
}

int PointCloud::AddAttribute(
    const GeometryAttribute &att, bool identity_mapping,
    AttributeValueIndex::ValueType num_attribute_values) {
  auto pa = CreateAttribute(att, identity_mapping, num_attribute_values);
  if (!pa) {
    return -1;
  }
  const int32_t att_id = AddAttribute(std::move(pa));
  return att_id;
}

std::unique_ptr<PointAttribute> PointCloud::CreateAttribute(
    const GeometryAttribute &att, bool identity_mapping,
    AttributeValueIndex::ValueType num_attribute_values) const {
  if (att.attribute_type() == GeometryAttribute::INVALID) {
    return nullptr;
  }
  std::unique_ptr<PointAttribute> pa =
      std::unique_ptr<PointAttribute>(new PointAttribute(att));
  // Initialize point cloud specific attribute data.
  if (!identity_mapping) {
    // First create mapping between indices.
    pa->SetExplicitMapping(num_points_);
  } else {
    pa->SetIdentityMapping();
    num_attribute_values = std::max(num_points_, num_attribute_values);
  }
  if (num_attribute_values > 0) {
    pa->Reset(num_attribute_values);
  }
  return pa;
}

void PointCloud::SetAttribute(int att_id, std::unique_ptr<PointAttribute> pa) {
  DRACO_DCHECK(att_id >= 0);
  if (static_cast<int>(attributes_.size()) <= att_id) {
    attributes_.resize(att_id + 1);
  }
  if (pa->attribute_type() < GeometryAttribute::NAMED_ATTRIBUTES_COUNT) {
    named_attribute_index_[pa->attribute_type()].push_back(att_id);
  }
  pa->set_unique_id(att_id);
  attributes_[att_id] = std::move(pa);
}

void PointCloud::DeleteAttribute(int att_id) {
  if (att_id < 0 || att_id >= attributes_.size()) {
    return;  // Attribute does not exist.
  }
  const GeometryAttribute::Type att_type =
      attributes_[att_id]->attribute_type();
  const uint32_t unique_id = attribute(att_id)->unique_id();
  attributes_.erase(attributes_.begin() + att_id);
  // Remove metadata if applicable.
  if (metadata_) {
    metadata_->DeleteAttributeMetadataByUniqueId(unique_id);
  }

  // Remove the attribute from the named attribute list if applicable.
  if (att_type < GeometryAttribute::NAMED_ATTRIBUTES_COUNT) {
    const auto it = std::find(named_attribute_index_[att_type].begin(),
                              named_attribute_index_[att_type].end(), att_id);
    if (it != named_attribute_index_[att_type].end()) {
      named_attribute_index_[att_type].erase(it);
    }
  }

  // Update ids of all subsequent named attributes (decrease them by one).
  for (int i = 0; i < GeometryAttribute::NAMED_ATTRIBUTES_COUNT; ++i) {
    for (int j = 0; j < named_attribute_index_[i].size(); ++j) {
      if (named_attribute_index_[i][j] > att_id) {
        named_attribute_index_[i][j]--;
      }
    }
  }
}

#ifdef DRACO_ATTRIBUTE_INDICES_DEDUPLICATION_SUPPORTED
void PointCloud::DeduplicatePointIds() {
  // Hashing function for a single vertex.
  auto point_hash = [this](PointIndex p) {
    PointIndex::ValueType hash = 0;
    for (int32_t i = 0; i < this->num_attributes(); ++i) {
      const AttributeValueIndex att_id = attribute(i)->mapped_index(p);
      hash = static_cast<uint32_t>(HashCombine(att_id.value(), hash));
    }
    return hash;
  };
  // Comparison function between two vertices.
  auto point_compare = [this](PointIndex p0, PointIndex p1) {
    for (int32_t i = 0; i < this->num_attributes(); ++i) {
      const AttributeValueIndex att_id0 = attribute(i)->mapped_index(p0);
      const AttributeValueIndex att_id1 = attribute(i)->mapped_index(p1);
      if (att_id0 != att_id1) {
        return false;
      }
    }
    return true;
  };

  std::unordered_map<PointIndex, PointIndex, decltype(point_hash),
                     decltype(point_compare)>
      unique_point_map(num_points_, point_hash, point_compare);
  int32_t num_unique_points = 0;
  IndexTypeVector<PointIndex, PointIndex> index_map(num_points_);
  std::vector<PointIndex> unique_points;
  // Go through all vertices and find their duplicates.
  for (PointIndex i(0); i < num_points_; ++i) {
    const auto it = unique_point_map.find(i);
    if (it != unique_point_map.end()) {
      index_map[i] = it->second;
    } else {
      unique_point_map.insert(std::make_pair(i, PointIndex(num_unique_points)));
      index_map[i] = num_unique_points++;
      unique_points.push_back(i);
    }
  }
  if (num_unique_points == num_points_) {
    return;  // All vertices are already unique.
  }

  ApplyPointIdDeduplication(index_map, unique_points);
  set_num_points(num_unique_points);
}

void PointCloud::ApplyPointIdDeduplication(
    const IndexTypeVector<PointIndex, PointIndex> &id_map,
    const std::vector<PointIndex> &unique_point_ids) {
  int32_t num_unique_points = 0;
  for (PointIndex i : unique_point_ids) {
    const PointIndex new_point_id = id_map[i];
    if (new_point_id >= num_unique_points) {
      // New unique vertex reached. Copy attribute indices to the proper
      // position.
      for (int32_t a = 0; a < num_attributes(); ++a) {
        attribute(a)->SetPointMapEntry(new_point_id,
                                       attribute(a)->mapped_index(i));
      }
      num_unique_points = new_point_id.value() + 1;
    }
  }
  for (int32_t a = 0; a < num_attributes(); ++a) {
    attribute(a)->SetExplicitMapping(num_unique_points);
  }
}
#endif

#ifdef DRACO_ATTRIBUTE_VALUES_DEDUPLICATION_SUPPORTED
bool PointCloud::DeduplicateAttributeValues() {
  // Go over all attributes and create mapping between duplicate entries.
  if (num_points() == 0) {
    return true;  // Nothing to deduplicate.
  }
  // Deduplicate all attributes.
  for (int32_t att_id = 0; att_id < num_attributes(); ++att_id) {
    if (!attribute(att_id)->DeduplicateValues(*attribute(att_id))) {
      return false;
    }
  }
  return true;
}
#endif

// TODO(b/199760503): Consider to cache the BBox.
BoundingBox PointCloud::ComputeBoundingBox() const {
  BoundingBox bounding_box;
  auto pc_att = GetNamedAttribute(GeometryAttribute::POSITION);
  // TODO(b/199760503): Make the BoundingBox a template type, it may not be easy
  // because PointCloud is not a template.
  // Or simply add some preconditioning here to make sure the position attribute
  // is valid, because the current code works only if the position attribute is
  // defined with 3 components of DT_FLOAT32.
  // Consider using pc_att->ConvertValue<float, 3>(i, &p[0]) (Enforced
  // transformation from Vector with any dimension to Vector3f)
  Vector3f p;
  for (AttributeValueIndex i(0); i < static_cast<uint32_t>(pc_att->size());
       ++i) {
    pc_att->GetValue(i, &p[0]);
    bounding_box.Update(p);
  }
  return bounding_box;
}
}  // namespace draco