从数组中查找重复的 3D 顶点
Find duplicate 3D vertices from array
我有一系列点。每个点都有位置(x, y, z) 和法向量(xn, yn, zn) ,一共6个双精度数。考虑到浮点容差,我需要在此数组中找到唯一元素并删除重复条目。
什么是简单有效的实施方式?
我考虑构建一些 space 分部结构,例如 BSP 或 KD-Tree。但我认为应该有更优化的方式,比如智能哈希字典或其他东西。
所以我正在寻求建议,是否有已经实现它的轻量级 C++ 库?
最简单的方法是四舍五入到最接近的 epsilon 并将点数置于整数范围内(将所有内容乘以 1/epsilon
)。一旦它们是整数哈希就可以正常工作(std::unordered_set
、std::unordered_map
)。这可能会遗漏一些 2 点接近但四舍五入不同的情况。您可以通过四舍五入并考虑与任一结果的冲突来克服这个问题。
如果您使用 std::set
/std::map
,请注意它们具有 log(N) 访问复杂性(与哈希版本的常量相比)。在这一点上,你同样擅长使用 BSP 或 KD-Tree(只要你已经有一些库已经实现了它们)。
我的实现:
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;
};
我有一系列点。每个点都有位置(x, y, z) 和法向量(xn, yn, zn) ,一共6个双精度数。考虑到浮点容差,我需要在此数组中找到唯一元素并删除重复条目。
什么是简单有效的实施方式? 我考虑构建一些 space 分部结构,例如 BSP 或 KD-Tree。但我认为应该有更优化的方式,比如智能哈希字典或其他东西。
所以我正在寻求建议,是否有已经实现它的轻量级 C++ 库?
最简单的方法是四舍五入到最接近的 epsilon 并将点数置于整数范围内(将所有内容乘以 1/epsilon
)。一旦它们是整数哈希就可以正常工作(std::unordered_set
、std::unordered_map
)。这可能会遗漏一些 2 点接近但四舍五入不同的情况。您可以通过四舍五入并考虑与任一结果的冲突来克服这个问题。
如果您使用 std::set
/std::map
,请注意它们具有 log(N) 访问复杂性(与哈希版本的常量相比)。在这一点上,你同样擅长使用 BSP 或 KD-Tree(只要你已经有一些库已经实现了它们)。
我的实现:
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;
};