Optimization of keying screen node
authorSergey Sharybin <sergey.vfx@gmail.com>
Tue, 26 Jun 2012 09:46:24 +0000 (09:46 +0000)
committerSergey Sharybin <sergey.vfx@gmail.com>
Tue, 26 Jun 2012 09:46:24 +0000 (09:46 +0000)
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.

source/blender/blenlib/intern/voronoi.c
source/blender/compositor/operations/COM_KeyingScreenOperation.cpp
source/blender/compositor/operations/COM_KeyingScreenOperation.h

index 727e42dc8dea89384c5217d8537a84efa7922076..accfbfc8c3c4350dcd6f3cb5d82977224be2c150 100644 (file)
@@ -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;
                        }
index 0fbe0aea555f1a740fad915ed85560f85c77e295..0341fe9ddac8efad4894f04ff323a67f13612527 100644 (file)
@@ -133,6 +133,7 @@ KeyingScreenOperation::TriangulationData *KeyingScreenOperation::buildVoronoiTri
                        continue;
 
                site = &sites[i];
+
                pattern_ibuf = BKE_tracking_get_pattern_imbuf(ibuf, track, marker, TRUE, FALSE);
 
                zero_v3(site->color);
@@ -199,19 +200,64 @@ KeyingScreenOperation::TriangulationData *KeyingScreenOperation::buildVoronoiTri
 
 void *KeyingScreenOperation::initializeTileData(rcti *rect, MemoryBuffer **memoryBuffers)
 {
+       TileData *tile_data;
+       TriangulationData *triangulation;
+       int triangles_allocated = 0;
+       int chunk_size = 20;
+       int i;
+       rctf rect_float;
+
        if (this->m_movieClip == NULL)
                return NULL;
 
-       if (this->m_cachedTriangulation)
-               return this->m_cachedTriangulation;
+       if (!this->m_cachedTriangulation) {
+               lockMutex();
+               if (this->m_cachedTriangulation == NULL) {
+                       this->m_cachedTriangulation = buildVoronoiTriangulation();
+               }
+               unlockMutex();
+       }
+
+       BLI_init_rctf(&rect_float, rect->xmin, rect->xmax, rect->ymin, rect->ymax);
+
+       triangulation = this->m_cachedTriangulation;
+       tile_data = (TileData *) MEM_callocN(sizeof(TileData), "keying screen tile data");
+
+       for (i = 0; i < triangulation->triangles_total; i++) {
+               bool ok = BLI_isect_rctf(&rect_float, &triangulation->triangles_AABB[i], NULL);
 
-       lockMutex();
-       if (this->m_cachedTriangulation == NULL) {
-               this->m_cachedTriangulation = buildVoronoiTriangulation();
+               if (ok) {
+                       tile_data->triangles_total++;
+
+                       if (tile_data->triangles_total > triangles_allocated) {
+                               if (!tile_data->triangles) {
+                                       tile_data->triangles = (int *) MEM_mallocN(sizeof(int) * chunk_size,
+                                                                                  "keying screen tile triangles chunk");
+                               }
+                               else {
+                                       tile_data->triangles = (int *) MEM_reallocN(tile_data->triangles,
+                                                                                   sizeof(int) * (triangles_allocated + chunk_size));
+                               }
+
+                               triangles_allocated += chunk_size;
+                       }
+
+                       tile_data->triangles[tile_data->triangles_total - 1] = i;
+               }
        }
-       unlockMutex();
 
-       return this->m_cachedTriangulation;
+       return tile_data;
+}
+
+void KeyingScreenOperation::deinitializeTileData(rcti *rect, MemoryBuffer **memoryBuffers, void *data)
+{
+       TileData *tile_data = (TileData *) data;
+
+       if (tile_data->triangles) {
+               MEM_freeN(tile_data->triangles);
+       }
+
+       MEM_freeN(tile_data);
 }
 
 void KeyingScreenOperation::determineResolution(unsigned int resolution[], unsigned int preferredResolution[])
@@ -240,15 +286,17 @@ void KeyingScreenOperation::executePixel(float *color, int x, int y, MemoryBuffe
        color[3] = 1.0f;
 
        if (this->m_movieClip && data) {
-               TriangulationData *triangulation = (TriangulationData *) data;
+               TriangulationData *triangulation = this->m_cachedTriangulation;
+               TileData *tile_data = (TileData *) data;
                int i;
                float co[2] = {(float) x, (float) y};
 
-               for (i = 0; i < triangulation->triangles_total; i++) {
-                       rctf *rect = &triangulation->triangles_AABB[i];
+               for (i = 0; i < tile_data->triangles_total; i++) {
+                       int triangle_idx = tile_data->triangles[i];
+                       rctf *rect = &triangulation->triangles_AABB[triangle_idx];
 
                        if (IN_RANGE_INCL(x, rect->xmin, rect->xmax) && IN_RANGE_INCL(y, rect->ymin, rect->ymax)) {
-                               int *triangle = triangulation->triangles[i];
+                               int *triangle = triangulation->triangles[triangle_idx];
                                VoronoiTriangulationPoint *a = &triangulation->triangulated_points[triangle[0]],
                                                          *b = &triangulation->triangulated_points[triangle[1]],
                                                          *c = &triangulation->triangulated_points[triangle[2]];
index 7cf7ad3e9591694925ccb9ce812911e6cd657fa4..95815cd39307b825af97b85a5ccfde5944e81faf 100644 (file)
@@ -50,6 +50,11 @@ protected:
                rctf *triangles_AABB;
        } TriangulationData;
 
+       typedef struct TileData {
+               int *triangles;
+               int triangles_total;
+       } TileData;
+
        MovieClip *m_movieClip;
        int m_framenumber;
        TriangulationData *m_cachedTriangulation;
@@ -69,6 +74,7 @@ public:
        void deinitExecution();
 
        void *initializeTileData(rcti *rect, MemoryBuffer **memoryBuffers);
+       void deinitializeTileData(rcti *rect, MemoryBuffer **memoryBuffers, void *data);
 
        void setMovieClip(MovieClip *clip) {this->m_movieClip = clip;}
        void setTrackingObject(const char *object) {strncpy(this->m_trackingObject, object, sizeof(this->m_trackingObject));}