从数组中查找重复的 3D 顶点

Question

我有一系列点。每个点都有位置(x, y, z) 和法向量(xn, yn, zn) ，一共6个双精度数。考虑到浮点容差，我需要在此数组中找到唯一元素并删除重复条目。

什么是简单有效的实施方式？我考虑构建一些 space 分部结构，例如 BSP 或 KD-Tree。但我认为应该有更优化的方式，比如智能哈希字典或其他东西。

所以我正在寻求建议，是否有已经实现它的轻量级 C++ 库？

Answer 1

最简单的方法是四舍五入到最接近的 epsilon 并将点数置于整数范围内（将所有内容乘以 1/epsilon）。一旦它们是整数哈希就可以正常工作（std::unordered_set、std::unordered_map）。这可能会遗漏一些 2 点接近但四舍五入不同的情况。您可以通过四舍五入并考虑与任一结果的冲突来克服这个问题。

如果您使用 std::set/std::map，请注意它们具有 log(N) 访问复杂性（与哈希版本的常量相比）。在这一点上，你同样擅长使用 BSP 或 KD-Tree（只要你已经有一些库已经实现了它们）。

Answer 2

我的实现：

class VertexMap {
public:
  VertexMap(double tolerance): m_tolerance(tolerance), m_invTolerance(1 / tolerance), m_offset(m_tolerance * 0.1) {
    m_offset = m_tolerance * 0.1;
    m_offset2 = m_offset * 2.0;
  }
  void add(const MbFloatPoint3D &pos, const MbFloatVector3D &normal, const MbFloatPoint &texture, size_t index) {
    m_vertices.emplace(pos, normal, texture, index, m_invTolerance);
  }

  size_t findIndex(const MbFloatPoint3D &pos, const MbFloatVector3D &normal, const MbFloatPoint &texture) {
    auto vertex = Vertex(pos, normal, texture, 0, m_invTolerance);
    auto it = m_vertices.find(vertex);
    auto itEnd = m_vertices.end();
    if (it == itEnd) {
      vertex.pos.x -= m_offset;
      vertex.pos.y -= m_offset;
      vertex.pos.z -= m_offset;
      it = m_vertices.find(vertex); // (---)
      if (it == itEnd) {
        vertex.pos.x += m_offset2;
        it = m_vertices.find(vertex); // (+--)
        if (it != itEnd) {
          vertex.pos.y += m_offset2;
          it = m_vertices.find(vertex); // (++-)
          if (it != itEnd) {
            vertex.pos.x -= m_offset2;
            it = m_vertices.find(vertex); // (-+-)
            if (it != itEnd) {
              vertex.pos.z += m_offset2;
              it = m_vertices.find(vertex); // (-++)
              if (it != itEnd) {
                vertex.pos.y -= m_offset2;
                it = m_vertices.find(vertex); // (--+)
                if (it != itEnd) {
                  vertex.pos.x += m_offset2;
                  it = m_vertices.find(vertex); // (+-+)
                  if (it != itEnd) {
                    vertex.pos.y += m_offset2;
                    it = m_vertices.find(vertex); // (+++)
                  }
                }
              }
            }
          }
        }
      }
    }
    if (it != itEnd)
      return it->index;
    else
      return SIZE_MAX;
  }

private:
  class Vertex {
  public:
    Vertex(const MbFloatPoint3D &pos, const MbFloatVector3D &normal, const MbFloatPoint &texture, size_t index, double invTolerance):
        pos(pos), normal(normal),texture(texture), index(index) {
      normalizedx = pos.x * invTolerance;
      normalizedy = pos.y * invTolerance;
      normalizedz = pos.z * invTolerance;
    }
    MbFloatPoint3D pos;
    MbFloatVector3D normal;
    MbFloatPoint texture;
    size_t index;
    int64_t normalizedx;
    int64_t normalizedy;
    int64_t normalizedz;

    bool operator==(const Vertex &other) const {
      return Equalsd(pos, other.pos) && Equalsd(normal, other.normal) && Equalsd(texture, other.texture);
    }
  };

  struct VertexHasher
  {
      size_t operator()(const Vertex& k) const
      {
        size_t h1 = std::hash<int64_t>()(k.normalizedx);
        size_t h2 = std::hash<int64_t>()(k.normalizedy);
        size_t h3 = std::hash<int64_t>()(k.normalizedz);
        return (h1 ^ (h2 << 1)) ^ h3;
      }
  };

  double m_tolerance;
  double m_invTolerance;
  double m_offset;
  double m_offset2;
  std::unordered_set<Vertex, VertexHasher> m_vertices;
};

从数组中查找重复的 3D 顶点

Find duplicate 3D vertices from array

c++

algorithm

3d

hashtable