From 5d385b9a9a6f6981f849706397fd63d1511803ae Mon Sep 17 00:00:00 2001 From: Monique Dewanchand Date: Fri, 25 Jan 2013 09:47:28 +0000 Subject: 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 --- .../operations/COM_DilateErodeOperation.cpp | 155 +++++++++++++++------ 1 file changed, 111 insertions(+), 44 deletions(-) (limited to 'source/blender/compositor/operations') diff --git a/source/blender/compositor/operations/COM_DilateErodeOperation.cpp b/source/blender/compositor/operations/COM_DilateErodeOperation.cpp index f0fffa770f8..07b958cc335 100644 --- a/source/blender/compositor/operations/COM_DilateErodeOperation.cpp +++ b/source/blender/compositor/operations/COM_DilateErodeOperation.cpp @@ -337,38 +337,73 @@ void *DilateStepOperation::initializeTileData(rcti *rect) 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 @@ void *ErodeStepOperation::initializeTileData(rcti *rect) 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(); -- cgit v1.2.3