diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2012-06-26 13:46:24 +0400 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2012-06-26 13:46:24 +0400 |
commit | cd6ed0bee5c1bc7b73eae5f869b13b121aa00a4b (patch) | |
tree | 10c861d1b38f0a40ccbcfa27f81350f33962be76 /source/blender/blenlib/intern/voronoi.c | |
parent | bf19327465ab180c547436c56f6efbb55640b06d (diff) |
Optimization of keying screen node
When creating tile data include only triangles which have got intersection
with tile's rectangle only. This saves quite a lot of per-pixel iterations
through triangles which simply can not affect on current tile.
In fact, it's AABB check is used here. It could be improved further, but
it'll slowdown tile data generation with questionable speedup.
Another major slowdown is in fact caused by voronoi triangulation code.
Currently it's used naive algorithm which is O(N^2) where N is number
of edges. Added few euristics there and removed unused part of code, which
gave quite noticeable speedup already.
This could be improved further, but this node is not ment to be used for
lots of markers. It's also generates wrong triangulation when there're
many sites used. Need to be investigated further.
Diffstat (limited to 'source/blender/blenlib/intern/voronoi.c')
-rw-r--r-- | source/blender/blenlib/intern/voronoi.c | 13 |
1 files changed, 6 insertions, 7 deletions
diff --git a/source/blender/blenlib/intern/voronoi.c b/source/blender/blenlib/intern/voronoi.c index 727e42dc8de..accfbfc8c3c 100644 --- a/source/blender/blenlib/intern/voronoi.c +++ b/source/blender/blenlib/intern/voronoi.c @@ -790,16 +790,15 @@ void BLI_voronoi_triangulate(const VoronoiSite *sites, int sites_total, ListBase int ok_start = TRUE, ok_end = TRUE; while (test_edge) { - float v1[2], v2[2]; - - sub_v2_v2v2(v1, edge->start, sites[i].co); - sub_v2_v2v2(v2, edge->end, sites[i].co); - - if (ok_start && !testVoronoiEdge(sites[i].co, edge->start, test_edge)) + if (ok_start && !testVoronoiEdge(sites[i].co, edge->start, test_edge)) { ok_start = FALSE; + break; + } - if (ok_end && !testVoronoiEdge(sites[i].co, edge->end, test_edge)) + if (ok_end && !testVoronoiEdge(sites[i].co, edge->end, test_edge)) { ok_end = FALSE; + break; + } test_edge = test_edge->next; } |