Поиск ближайшего полигона

@Igor3D · Регистрация: 01.10.2012

Студворк — интернет-сервис помощи студентам

Добрый день

С задачами (быстрого) поиска сталкивался не раз, но здесь что-то ничего не приходит в голову

Есть обычная полигонная модель. Создать структуру данных для быстрого поиска полигона ближайшего к заданной точке.

Модель представлена в виде контейнера вертексов (точек x, y, z) и контейнера индексов (int), напр по 3 на полигон/треугольник. "Ближайший полигон" - с минимальным расстоянием от принадлежащей ему точки до заданной/запросной. Ну вроде все разжевал

Спасибо

@Storm Screamer · 30.06.2025, 19:38

Использование комбинации Bounding Volume Hierarchy (BVH) и kd-дерева:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
#include <vector>
#include <limits>
#include <algorithm>
#include <memory>
#include <cmath>
 
struct Vec3 {
    float x, y, z;
    
    Vec3() : x(0), y(0), z(0) {}
    Vec3(float x, float y, float z) : x(x), y(y), z(z) {}
    
    float distanceSquared(const Vec3& other) const {
        float dx = x - other.x;
        float dy = y - other.y;
        float dz = z - other.z;
        return dx*dx + dy*dy + dz*dz;
    }
    
    Vec3 operator-(const Vec3& other) const {
        return Vec3(x - other.x, y - other.y, z - other.z);
    }
    
    Vec3 cross(const Vec3& other) const {
        return Vec3(
            y * other.z - z * other.y,
            z * other.x - x * other.z,
            x * other.y - y * other.x
        );
    }
    
    float dot(const Vec3& other) const {
        return x * other.x + y * other.y + z * other.z;
    }
    
    float length() const {
        return std::sqrt(x*x + y*y + z*z);
    }
};
 
struct Triangle {
    Vec3 v0, v1, v2;
    int index;
    
    Triangle(const Vec3& v0, const Vec3& v1, const Vec3& v2, int idx) 
        : v0(v0), v1(v1), v2(v2), index(idx) {}
    
    Vec3 centroid() const {
        return Vec3(
            (v0.x + v1.x + v2.x) / 3.0f,
            (v0.y + v1.y + v2.y) / 3.0f,
            (v0.z + v1.z + v2.z) / 3.0f
        );
    }
    
    float distanceSquaredToPoint(const Vec3& point) const {
        // Algorithm based on "Real-Time Collision Detection" by Christer Ericson
        Vec3 ab = v1 - v0;
        Vec3 ac = v2 - v0;
        Vec3 ap = point - v0;
        
        float d1 = ab.dot(ap);
        float d2 = ac.dot(ap);
        
        if (d1 <= 0.0f && d2 <= 0.0f) {
            return ap.dot(ap);
        }
        
        Vec3 bp = point - v1;
        float d3 = ab.dot(bp);
        float d4 = ac.dot(bp);
        
        if (d3 >= 0.0f && d4 <= d3) {
            return bp.dot(bp);
        }
        
        Vec3 cp = point - v2;
        float d5 = ab.dot(cp);
        float d6 = ac.dot(cp);
        
        if (d6 >= 0.0f && d5 <= d6) {
            return cp.dot(cp);
        }
        
        float vc = d1*d4 - d3*d2;
        if (vc <= 0.0f && d1 >= 0.0f && d3 <= 0.0f) {
            float v = d1 / (d1 - d3);
            return (ap - ab * v).dot(ap - ab * v);
        }
        
        float vb = d5*d2 - d1*d6;
        if (vb <= 0.0f && d2 >= 0.0f && d6 <= 0.0f) {
            float v = d2 / (d2 - d6);
            return (ap - ac * v).dot(ap - ac * v);
        }
        
        float va = d3*d6 - d5*d4;
        if (va <= 0.0f && (d4 - d3) >= 0.0f && (d5 - d6) >= 0.0f) {
            float v = (d4 - d3) / ((d4 - d3) + (d5 - d6));
            return (bp - (v2 - v1) * v).dot(bp - (v2 - v1) * v);
        }
        
        float denom = 1.0f / (va + vb + vc);
        float v = vb * denom;
        float w = vc * denom;
        
        return (ap - ab * v - ac * w).dot(ap - ab * v - ac * w);
    }
};
 
struct AABB {
    Vec3 min, max;
    
    AABB() : min(Vec3(std::numeric_limits<float>::max(), 
                     std::numeric_limits<float>::max(), 
                     std::numeric_limits<float>::max())),
             max(Vec3(std::numeric_limits<float>::lowest(), 
                     std::numeric_limits<float>::lowest(), 
                     std::numeric_limits<float>::lowest())) {}
    
    void expand(const Vec3& point) {
        min.x = std::min(min.x, point.x);
        min.y = std::min(min.y, point.y);
        min.z = std::min(min.z, point.z);
        max.x = std::max(max.x, point.x);
        max.y = std::max(max.y, point.y);
        max.z = std::max(max.z, point.z);
    }
    
    void expand(const AABB& other) {
        expand(other.min);
        expand(other.max);
    }
    
    float distanceSquared(const Vec3& point) const {
        float dx = std::max(std::max(min.x - point.x, point.x - max.x), 0.0f);
        float dy = std::max(std::max(min.y - point.y, point.y - max.y), 0.0f);
        float dz = std::max(std::max(min.z - point.z, point.z - max.z), 0.0f);
        return dx*dx + dy*dy + dz*dz;
    }
    
    bool contains(const Vec3& point) const {
        return point.x >= min.x && point.x <= max.x &&
               point.y >= min.y && point.y <= max.y &&
               point.z >= min.z && point.z <= max.z;
    }
};
 
struct BVHNode {
    AABB bounds;
    std::vector<Triangle> triangles;
    std::unique_ptr<BVHNode> left;
    std::unique_ptr<BVHNode> right;
    
    bool isLeaf() const { return left == nullptr && right == nullptr; }
};
 
class BVH {
private:
    std::unique_ptr<BVHNode> root;
    
    std::unique_ptr<BVHNode> build(std::vector<Triangle>& triangles, int start, int end, int axis) {
        if (start >= end) return nullptr;
        
        auto node = std::make_unique<BVHNode>();
        AABB bounds;
        
        for (int i = start; i < end; ++i) {
            bounds.expand(triangles[i].v0);
            bounds.expand(triangles[i].v1);
            bounds.expand(triangles[i].v2);
        }
        node->bounds = bounds;
        
        if (end - start <= 4) { // Leaf node threshold
            node->triangles.assign(triangles.begin() + start, triangles.begin() + end);
            return node;
        }
        
        // Sort triangles along the longest axis
        Vec3 extent = bounds.max - bounds.min;
        int splitAxis = (extent.x > extent.y && extent.x > extent.z) ? 0 : 
                        (extent.y > extent.z) ? 1 : 2;
        
        auto mid = start + (end - start) / 2;
        std::nth_element(triangles.begin() + start, triangles.begin() + mid, 
                         triangles.begin() + end, 
                         [splitAxis](const Triangle& a, const Triangle& b) {
                             return a.centroid().x < b.centroid().x;
                         });
        
        node->left = build(triangles, start, mid, (splitAxis + 1) % 3);
        node->right = build(triangles, mid, end, (splitAxis + 1) % 3);
        
        return node;
    }
    
    void searchNearest(const BVHNode* node, const Vec3& point, float& minDistSq, int& nearestIndex) const {
        if (!node) return;
        
        if (node->isLeaf()) {
            for (const auto& triangle : node->triangles) {
                float distSq = triangle.distanceSquaredToPoint(point);
                if (distSq < minDistSq) {
                    minDistSq = distSq;
                    nearestIndex = triangle.index;
                }
            }
            return;
        }
        
        float leftDist = node->left ? node->left->bounds.distanceSquared(point) : std::numeric_limits<float>::max();
        float rightDist = node->right ? node->right->bounds.distanceSquared(point) : std::numeric_limits<float>::max();
        
        if (leftDist < rightDist) {
            if (leftDist < minDistSq) {
                searchNearest(node->left.get(), point, minDistSq, nearestIndex);
            }
            if (rightDist < minDistSq) {
                searchNearest(node->right.get(), point, minDistSq, nearestIndex);
            }
        } else {
            if (rightDist < minDistSq) {
                searchNearest(node->right.get(), point, minDistSq, nearestIndex);
            }
            if (leftDist < minDistSq) {
                searchNearest(node->left.get(), point, minDistSq, nearestIndex);
            }
        }
    }
    
public:
    void build(const std::vector<Vec3>& vertices, const std::vector<int>& indices) {
        std::vector<Triangle> triangles;
        for (size_t i = 0; i < indices.size(); i += 3) {
            triangles.emplace_back(
                vertices[indices[i]],
                vertices[indices[i+1]],
                vertices[indices[i+2]],
                i / 3
            );
        }
        root = build(triangles, 0, triangles.size(), 0);
    }
    
    int findNearest(const Vec3& point) const {
        if (!root) return -1;
        
        float minDistSq = std::numeric_limits<float>::max();
        int nearestIndex = -1;
        searchNearest(root.get(), point, minDistSq, nearestIndex);
        return nearestIndex;
    }
};
 
// Пример использования:
// std::vector<Vec3> vertices = {...};
// std::vector<int> indices = {...}; // по 3 на треугольник
// BVH bvh;
// bvh.build(vertices, indices);
// Vec3 queryPoint = {...};
// int nearestPolygonIndex = bvh.findNearest(queryPoint);

@Igor3D · 01.07.2025, 00:11 **[ТС]**

Сообщение от Storm Screamer

Использование комбинации Bounding Volume Hierarchy (BVH) и kd-дерева:

У такого дерева ноды перекрываются, и тогда, по-моему, отбрасывать "дальний нод" (leftDist < rightDist) неправомерно, ближайший может находиться и в дальнем

В любом случае спасибо за интересный, содержательный ответ

@Igor3D · 01.07.2025, 12:45 **[ТС]**

Сообщение от Igor3D

отбрасывать "дальний нод" (leftDist < rightDist) неправомерно, ближайший может находиться и в дальнем

"Придется удовлетвориться квасом" - отбрасывать нод если расстояние до него превышает текущее ближайшее. И дерево, к сожалению, получается очень "жирным". Тем не менее, это решение, "acceleration structure" есть

Новые блоги и статьи Все статьи Все блоги /
попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .

Поиск ближайшего полигона

Решение