blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 749 Projects 19 Wiki Activity

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.
This commit is contained in:
Erik Abrahamsson 2021-07-18 12:12:35 -04:00 committed by Howard Trickey
parent fc32567cda
commit 24801e0a4a
1 changed files with 25 additions and 20 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

45
source/blender/blenlib/intern/delaunay_2d.cc
View File

@ -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. */