diff options
author | Eric Abrahamsson <ecke101@gmail.com> | 2021-07-18 19:12:35 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2021-07-18 19:13:41 +0300 |
commit | 24801e0a4a8fb973b13e6de3c4d6f84852327349 (patch) | |
tree | d6298490b88bab37a1fb422290b7d93379d2c7ba /source/blender/blenlib/intern/delaunay_2d.cc | |
parent | fc32567cdaa57b39312fbea0ea217612d3543034 (diff) |
Speed up Delaunay raycast.
From Erik Abrahamsson, this uses parallel loops for raycasting.
It speeds up one example with many crossings of a bezier curve,
from 0.68s to 0.28s.
Diffstat (limited to 'source/blender/blenlib/intern/delaunay_2d.cc')
-rw-r--r-- | source/blender/blenlib/intern/delaunay_2d.cc | 45 |
1 files changed, 25 insertions, 20 deletions
diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc index 279fe6f38b4..162b05e1437 100644 --- a/source/blender/blenlib/intern/delaunay_2d.cc +++ b/source/blender/blenlib/intern/delaunay_2d.cc @@ -19,6 +19,7 @@ */ #include <algorithm> +#include <atomic> #include <fstream> #include <iostream> #include <sstream> @@ -30,6 +31,7 @@ #include "BLI_math_mpq.hh" #include "BLI_mpq2.hh" #include "BLI_set.hh" +#include "BLI_task.hh" #include "BLI_vector.hh" #include "BLI_delaunay_2d.h" @@ -2535,30 +2537,33 @@ template<typename T> void detect_holes(CDT_state<T> *cdt_state) mid.exact[1] = (f->symedge->vert->co.exact[1] + f->symedge->next->vert->co.exact[1] + f->symedge->next->next->vert->co.exact[1]) / 3; - int hits = 0; + std::atomic<int> hits = 0; /* TODO: Use CDT data structure here to greatly reduce search for intersections! */ - for (const CDTEdge<T> *e : cdt->edges) { - if (!is_deleted_edge(e) && is_constrained_edge(e)) { - if (e->symedges[0].face->visit_index == e->symedges[1].face->visit_index) { - continue; /* Don't count hits on edges between faces in same region. */ - } - auto isect = vec2<T>::isect_seg_seg(ray_end.exact, - mid.exact, - e->symedges[0].vert->co.exact, - e->symedges[1].vert->co.exact); - switch (isect.kind) { - case vec2<T>::isect_result::LINE_LINE_CROSS: { - hits++; - break; + threading::parallel_for(cdt->edges.index_range(), 256, [&](IndexRange range) { + for (const int i : range) { + const CDTEdge<T> *e = cdt->edges[i]; + if (!is_deleted_edge(e) && is_constrained_edge(e)) { + if (e->symedges[0].face->visit_index == e->symedges[1].face->visit_index) { + continue; /* Don't count hits on edges between faces in same region. */ + } + auto isect = vec2<T>::isect_seg_seg(ray_end.exact, + mid.exact, + e->symedges[0].vert->co.exact, + e->symedges[1].vert->co.exact); + switch (isect.kind) { + case vec2<T>::isect_result::LINE_LINE_CROSS: { + hits++; + break; + } + case vec2<T>::isect_result::LINE_LINE_EXACT: + case vec2<T>::isect_result::LINE_LINE_NONE: + case vec2<T>::isect_result::LINE_LINE_COLINEAR: + break; } - case vec2<T>::isect_result::LINE_LINE_EXACT: - case vec2<T>::isect_result::LINE_LINE_NONE: - case vec2<T>::isect_result::LINE_LINE_COLINEAR: - break; } } - } - f->hole = (hits % 2) == 0; + }); + f->hole = (hits.load() % 2) == 0; } /* Finally, propagate hole status to all holes of a region. */ |