ENH: Use one fast exact duplicate-vertex finder in all duplicate-vertex code
Maintainer thường phản hồi trong vòng 6 ngày
Chưa có ai nhận issue này.
Đánh giá
- Độ khó
- 5/5
- Thời gian dự kiến
- Hơn một tuần
- Mức phù hợp với người mới
- 35/100
- Loại issue
- Tính năng
- Độ rõ ràng
- Khá rõ ràng
- Mức độ hoạt động
- Sôi nổi
- Công nghệ
- cpp
- Lĩnh vực
- backend, data, performance
Hướng nghiên cứu
Start by reading GeometryUtilities::EliminateDuplicateNodes in src/simplnx/Utilities/GeometryUtilities.cpp and MeshingUtilities::OrderSharedVertices / HasDuplicateVertices in src/simplnx/Utilities/Meshing/VertexUtilities.cpp, along with issue #1908 item L19. The issue leaves the algorithm and memory budget open, so first compare the existing paths against the exact-equality, parallel, cancellable, out-of-core requirements. Done means one shared finder is used by all listed filters and keeps the first vertex in each duplicate group.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Mô tả
Summary
Request: one shared, fast duplicate-vertex finder that every filter which looks for duplicate vertices uses. It should find vertices whose X, Y and Z coordinates are exactly equal, run in parallel, scale with the number of vertices, and work with out-of-core (OOC) data.
Why it is needed
simplnx has two separate duplicate-vertex finders. They have different weaknesses:
GeometryUtilities::EliminateDuplicateNodes(GeometryUtilities.hpp:119, FindUniqueIdsImpl) puts each vertex into a spatial bin and compares, in parallel, every pair of vertices inside each bin with exact==. It is fast for typical STL files, but:- The grid always has 100 × 100 × 100 bins, whatever the number of vertices. The comparison inside a bin is O(k²). A flat mesh uses only one layer of 100 × 100 bins, and dense lattice meshes (surface meshes made from voxel data) put many vertices into each bin.
- The bins (one
std::vectorper bin, about 24 MB when empty) and theInt64DataStoreof unique IDs are always in memory, so the memory use is about 16 bytes or more per vertex, with no OOC path. - A NaN coordinate makes the bin index cast undefined behavior, and an infinite coordinate breaks the bounding box. Neither case is checked.
MeshingUtilities::OrderSharedVertices/HasDuplicateVertices(VertexUtilities.cpp) sort the vertex indices and compare neighbors. Issue #1908 item L19 (same defect as #1783) changes this code to exact equality with a sort on (x, y, z, input index). That sort is O(N log N), single threaded, and reads each coordinate through the DataStore's virtual accessor. With an OOC store, these reads come in random order through the chunk cache, because the sort compares vertices in random order.
Filters affected
- Through
EliminateDuplicateNodes: Read STL File, Combine STL Files (it runs Read STL File for each file), Slice Triangle Geometry and Extract Feature Boundaries 2D. - Through
OrderSharedVertices/HasDuplicateVertices: Identify Duplicate Vertices and Verify Triangle Winding.
Expected behavior (the rule chosen for L19)
- Two vertices are duplicates only when X, Y and Z are exactly equal (
==, so -0.0 equals +0.0). A vertex with a NaN coordinate is never a duplicate. - In each group of equal vertices, the first vertex in input order is kept.
- The run can be cancelled.
Measurements (from the L19 review, macOS ARM64, in memory, one thread, about 4 million vertices on a 200³ lattice in random order, no duplicates): the old one-axis sort took 0.42 s (but it misses duplicates), and the L19 sort takes 1.30 s. A scan that compares all vertices with the same primary coordinate took about 117 s.
Still open: the algorithm (hash on the exact coordinate bits, bins sized from the vertex count, or a sort that runs on chunks and then merges them for OOC data) and the memory budget that is allowed.
- Ngôn ngữ chính
- C++
- Star
- 18
- Fork
- 15
- Merge trung bình
- 4 ngày 23 giờ
- Pull request đã merge (30 ngày)
- 42
Chuẩn bị môi trường
- Không có Dockerfile hay tệp Docker Compose
- Có mẫu pull request
- Đọc hướng dẫn đóng góp
Bắt đầu từ đâu
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Issue khác của BlueQuartzSoftware/simplnx
-
bug
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
BlueQuartzSoftware/simplnx#1987 ·
Maintainer thường phản hồi trong vòng 6 ngày
-
documentation
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 74/100
BlueQuartzSoftware/simplnx#1980 ·
Maintainer thường phản hồi trong vòng 6 ngày
-
Testing
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 62/100
BlueQuartzSoftware/simplnx#1979 ·
Maintainer thường phản hồi trong vòng 6 ngày
-
documentation
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 65/100
BlueQuartzSoftware/simplnx#1978 ·
Maintainer thường phản hồi trong vòng 6 ngày
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 82/100
BlueQuartzSoftware/simplnx#1945 ·
Maintainer thường phản hồi trong vòng 6 ngày
Tất cả issue của BlueQuartzSoftware/simplnx
Issue tương tự
-
bug triage
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 75/100
Maintainer thường phản hồi trong vòng 1 ngày
-
26.04 bug dark-mode Easy Hack impress symptom: visual
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 68/100
CollaboraOnline/online#16421 · 1 bình luận ·
-
area/cs bug
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 82/100
ydb-platform/ydb#59881 · 1 bình luận ·
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 64/100
Maintainer thường phản hồi trong vòng 1 ngày
-
documentation enhancement lua server
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 66/100