[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [54096] trunk/blender/source/blender/ compositor/operations/COM_DilateErodeOperation.cpp: committed patch [#33972 ] dilate/erode optimization

[Monique Dewanchand]

Revision: 54096
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=54096
Author:   mdewanchand
Date:     2013-01-25 09:47:28 +0000 (Fri, 25 Jan 2013)
Log Message:
-----------
committed patch [#33972] dilate/erode optimization

this patch optimizes the dilate/erode step method (hopefully without any functional change),
making its speed not depend on the distance anymore.

Couldn't detect funtional changes so committing. Haven't tested for speed gain.

 * credits to erwin94 David M

Modified Paths:
--------------
    trunk/blender/source/blender/compositor/operations/COM_DilateErodeOperation.cpp

Modified: trunk/blender/source/blender/compositor/operations/COM_DilateErodeOperation.cpp
===================================================================
--- trunk/blender/source/blender/compositor/operations/COM_DilateErodeOperation.cpp	2013-01-25 07:31:29 UTC (rev 54095)
+++ trunk/blender/source/blender/compositor/operations/COM_DilateErodeOperation.cpp	2013-01-25 09:47:28 UTC (rev 54096)
@@ -337,38 +337,73 @@
 		MemoryBuffer *buffer = (MemoryBuffer *)this->m_inputProgram->initializeTileData(NULL);
 		float *rectf = buffer->convertToValueBuffer();
 		int x, y, i;
-		float *p;
 		int bwidth = buffer->getWidth();
 		int bheight = buffer->getHeight();
-		for (i = 0; i < this->m_iterations; i++) {
-			for (y = 0; y < bheight; y++) {
-				for (x = 0; x < bwidth - 1; x++) {
-					p = rectf + (bwidth * y + x);
-					*p = max(*p, *(p + 1));
+
+		/*
+		  The following is based on the van Herk/Gil-Werman algorithm for morphology operations.
+		 */
+		int half_window = this->m_iterations;
+		int window = half_window * 2 + 1;
+		float *temp = (float *)MEM_mallocN((2*window - 1) * sizeof(float), "dilate erode temp");
+		float *buf = (float *)MEM_mallocN((max(bwidth, bheight) + 5*half_window) * sizeof(float), "dilate erode buf");
+
+		for (y = 0; y < bheight; y++) {
+			for (x = 0; x < window - 1; x++) {
+				buf[x] = -MAXFLOAT;
+			}
+			for (x = 0; x < bwidth; x++) {
+				buf[x + window - 1] = rectf[bwidth * y + x];
+			}
+			for (x = bwidth + window - 1; x < bwidth + 5*half_window; x++) {
+				buf[x] = -MAXFLOAT;
+			}
+
+			for(i = 0; i < (bwidth + 3*half_window) / window; i++) {
+				int start = (i + 1) * window - 1;
+
+				temp[window - 1] = buf[start];
+				for (x = 1; x < window; x++) {
+					temp[window - 1 - x] = max(temp[window - x], buf[start - x]);
+					temp[window - 1 + x] = max(temp[window + x - 2], buf[start + x]);
 				}
+
+				start = half_window + (i-1) * window + 1;
+				for (x = -min(0, start); x < window - max(0, start+window - bwidth); x++) {
+					rectf[bwidth * y + (start + x)] = max(temp[x], temp[x + window - 1]);
+				}
 			}
-		
+		}
+
+		for (x = 0; x < bwidth; x++) {
+			for (y = 0; y < window - 1; y++) {
+				buf[y] = -MAXFLOAT;
+			}
 			for (y = 0; y < bheight; y++) {
-				for (x = bwidth - 1; x >= 1; x--) {
-					p = rectf + (bwidth * y + x);
-					*p = max(*p, *(p - 1));
-				}
+				buf[y + window - 1] = rectf[bwidth * y + x];
 			}
-		
-			for (x = 0; x < bwidth; x++) {
-				for (y = 0; y < bheight - 1; y++) {
-					p = rectf + (bwidth * y + x);
-					*p = max(*p, *(p + bwidth));
-				}
+			for (y = bheight + window - 1; y < bheight + 5*half_window; y++) {
+				buf[y] = -MAXFLOAT;
 			}
-		
-			for (x = 0; x < bwidth; x++) {
-				for (y = bheight - 1; y >= 1; y--) {
-					p = rectf + (bwidth * y + x);
-					*p = max(*p, *(p - bwidth));
+
+			for(i = 0; i < (bheight + 3*half_window) / window; i++) {
+				int start = (i + 1) * window - 1;
+
+				temp[window - 1] = buf[start];
+				for (y = 1; y < window; y++) {
+					temp[window - 1 - y] = max(temp[window - y], buf[start - y]);
+					temp[window - 1 + y] = max(temp[window + y - 2], buf[start + y]);
 				}
+
+				start = half_window + (i-1) * window + 1;
+				for (y = -min(0, start); y < window - max(0, start+window - bheight); y++) {
+					rectf[bwidth * (y + start) + x] = max(temp[y], temp[y + window - 1]);
+				}
 			}
 		}
+
+		MEM_freeN(temp);
+		MEM_freeN(buf);
 		this->m_cached_buffer = rectf;
 	}
 	unlockMutex();
@@ -424,38 +459,70 @@
 		MemoryBuffer *buffer = (MemoryBuffer *)this->m_inputProgram->initializeTileData(NULL);
 		float *rectf = buffer->convertToValueBuffer();
 		int x, y, i;
-		float *p;
 		int bwidth = buffer->getWidth();
 		int bheight = buffer->getHeight();
-		for (i = 0; i < this->m_iterations; i++) {
-			for (y = 0; y < bheight; y++) {
-				for (x = 0; x < bwidth - 1; x++) {
-					p = rectf + (bwidth * y + x);
-					*p = MIN2(*p, *(p + 1));
+
+		int half_window = this->m_iterations;
+		int window = half_window * 2 + 1;
+		float *temp = (float *)MEM_mallocN((2*window - 1) * sizeof(float), "dilate erode temp");
+		float *buf = (float *)MEM_mallocN((max(bwidth, bheight) + 5*half_window) * sizeof(float), "dilate erode buf");
+
+		for (y = 0; y < bheight; y++) {
+			for (x = 0; x < window - 1; x++) {
+				buf[x] = MAXFLOAT;
+			}
+			for (x = 0; x < bwidth; x++) {
+				buf[x + window - 1] = rectf[bwidth * y + x];
+			}
+			for (x = bwidth + window - 1; x < bwidth + 5*half_window; x++) {
+				buf[x] = MAXFLOAT;
+			}
+
+			for(i = 0; i < (bwidth + 3*half_window) / window; i++) {
+				int start = (i + 1) * window - 1;
+
+				temp[window - 1] = buf[start];
+				for (x = 1; x < window; x++) {
+					temp[window - 1 - x] = min(temp[window - x], buf[start - x]);
+					temp[window - 1 + x] = min(temp[window + x - 2], buf[start + x]);
 				}
+
+				start = half_window + (i-1) * window + 1;
+				for (x = -min(0, start); x < window - max(0, start+window - bwidth); x++) {
+					rectf[bwidth * y + (start + x)] = min(temp[x], temp[x + window - 1]);
+				}
 			}
-		
+		}
+
+		for (x = 0; x < bwidth; x++) {
+			for (y = 0; y < window - 1; y++) {
+				buf[y] = MAXFLOAT;
+			}
 			for (y = 0; y < bheight; y++) {
-				for (x = bwidth - 1; x >= 1; x--) {
-					p = rectf + (bwidth * y + x);
-					*p = MIN2(*p, *(p - 1));
-				}
+				buf[y + window - 1] = rectf[bwidth * y + x];
 			}
-		
-			for (x = 0; x < bwidth; x++) {
-				for (y = 0; y < bheight - 1; y++) {
-					p = rectf + (bwidth * y + x);
-					*p = MIN2(*p, *(p + bwidth));
-				}
+			for (y = bheight + window - 1; y < bheight + 5*half_window; y++) {
+				buf[y] = MAXFLOAT;
 			}
-		
-			for (x = 0; x < bwidth; x++) {
-				for (y = bheight - 1; y >= 1; y--) {
-					p = rectf + (bwidth * y + x);
-					*p = MIN2(*p, *(p - bwidth));
+
+			for(i = 0; i < (bheight + 3*half_window) / window; i++) {
+				int start = (i + 1) * window - 1;
+
+				temp[window - 1] = buf[start];
+				for (y = 1; y < window; y++) {
+					temp[window - 1 - y] = min(temp[window - y], buf[start - y]);
+					temp[window - 1 + y] = min(temp[window + y - 2], buf[start + y]);
 				}
+
+				start = half_window + (i-1) * window + 1;
+				for (y = -min(0, start); y < window - max(0, start+window - bheight); y++) {
+					rectf[bwidth * (y + start) + x] = min(temp[y], temp[y + window - 1]);
+				}
 			}
 		}
+
+		MEM_freeN(temp);
+		MEM_freeN(buf);
 		this->m_cached_buffer = rectf;
 	}
 	unlockMutex();