From bda4432c80fd340a3d75ba077830ed93724fd9f1 Mon Sep 17 00:00:00 2001 From: Miikka Heikkinen Date: Wed, 28 May 2014 09:23:54 +0300 Subject: Implement binary search for determining surface sample space MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Task-number: QTRD-3066 Change-Id: I3a6d727c528e37e914aa1c3f08ee6d268a2c5230 Reviewed-by: Tomi Korpipää --- .../doc/src/qtdatavisualization.qdoc | 44 +++--- src/datavisualization/engine/surface3drenderer.cpp | 147 +++++++++++---------- src/datavisualization/engine/surface3drenderer_p.h | 6 - 3 files changed, 104 insertions(+), 93 deletions(-) (limited to 'src') diff --git a/src/datavisualization/doc/src/qtdatavisualization.qdoc b/src/datavisualization/doc/src/qtdatavisualization.qdoc index cdbd4e4b..c3196dee 100644 --- a/src/datavisualization/doc/src/qtdatavisualization.qdoc +++ b/src/datavisualization/doc/src/qtdatavisualization.qdoc @@ -238,9 +238,18 @@ and which role specifies the value of the item. When the proxy resolves the data from the model, it uses these mappings to generate the rows and columns of the bar graph. + Often the item models will have a single role that contains information you want to map to + multiple values. A typical example of this is a timestamp field when generating a bar graph + with two time related axes, for example years and months. To enable mapping a single item + model role to more than one data field, pattern matching and replacing mechanism is provided + by item model proxies. You can also use this mechanism to reformat data even in one-to-one + mapping cases. + Depending on the visualization type, proxies may support other functionalities as well, such as QItemModelBarDataProxy optionally mapping QAbstractItemModel rows and columns directly - into bar graph rows and columns. See individual proxy classes for more information and examples + into bar graph rows and columns. + + See individual proxy classes for more information and examples about how to use them: QItemModelBarDataProxy, QItemModelScatterDataProxy, and QItemModelSurfaceDataProxy. @@ -257,28 +266,27 @@ When you have a data set that updates rapidly, it is important to handle data properly to ensure good performance. Since memory allocation is a costly operation, always use - QList::reserve() and QVector::resize() where possible to avoid reallocations when constructing - the array to give to the proxy. If you need to change the entire data set for each frame, - it is in most cases best to reuse the existing array - especially if the array dimensions do not - change. If you need to add, insert, remove, or change several rows or items for each frame, it - is always more efficient to do it with one method call instead of multiple calls affecting - a single row or item each. For example, adding ten rows with a single QBarDataProxy::addRows() call - is much more efficient than ten separate QBarDataProxy::addRow() calls. - - Bars renderer is optimized to access only data that is within the data window and thus should not - suffer noticeable slowdown even if more data is continually added to the proxy. + QList::reserve() and QVector::resize() where possible to avoid unnecessary reallocations when + constructing the array to give to the proxy. If you need to change the entire data set + for each frame, it is in most cases best to reuse the existing array - especially if the + array dimensions do not change. If you need to add, insert, remove, or change several + rows or items for each frame, it is always more efficient to do it with one method call + instead of multiple calls affecting a single row or item each. For example, adding ten + rows with a single QBarDataProxy::addRows() call is much more efficient than ten + separate QBarDataProxy::addRow() calls. + + Bars renderer is optimized to access only data that is within the data window and thus + should not suffer noticeable slowdown even if more data is continually added to the proxy. Due to the unsorted nature of the scatter data, any change in the data window ranges requires all data points to be checked for visibility, which can cause increasing slowdown if data is - continually added to the proxy. + continually added to the proxy. For the best performance with the scatter graphs, only keep + the data you need in the proxy. Surface data, while on item level similar to scatter data, is already assigned into rows and - columns, so the surface renderer can do some optimization by making the assumption that the data in - rows and columns is sorted along their respective axes, but it is nowhere near as efficient - as in the bars case. Surface rendering can suffer significant slowdown if the data size grows unchecked. - - For the best performance with the scatter and surface graphs, only keep the data you need in the - proxy. + columns, so the surface renderer can optimize drawing by making the assumption that + the data in the rows and columns is sorted along their respective axes. It is not quite as + efficient as in the bars case, but nearly so. */ /*! diff --git a/src/datavisualization/engine/surface3drenderer.cpp b/src/datavisualization/engine/surface3drenderer.cpp index 6fc0aec1..ea750c78 100644 --- a/src/datavisualization/engine/surface3drenderer.cpp +++ b/src/datavisualization/engine/surface3drenderer.cpp @@ -68,12 +68,6 @@ Surface3DRenderer::Surface3DRenderer(Surface3DController *controller) m_scaleZ(0.0f), m_scaleXWithBackground(0.0f), m_scaleZWithBackground(0.0f), - m_minVisibleColumnValue(0.0f), - m_maxVisibleColumnValue(0.0f), - m_minVisibleRowValue(0.0f), - m_maxVisibleRowValue(0.0f), - m_visibleColumnRange(0.0f), - m_visibleRowRange(0.0f), m_depthTexture(0), m_depthModelTexture(0), m_depthFrameBuffer(0), @@ -561,43 +555,78 @@ void Surface3DRenderer::updateSliceObject(SurfaceSeriesRenderCache *cache, const } } +inline static float getDataValue(const QSurfaceDataArray &array, bool searchRow, int index) +{ + if (searchRow) + return array.at(0)->at(index).x(); + else + return array.at(index)->at(0).z(); +} + +inline static int binarySearchArray(const QSurfaceDataArray &array, int maxIdx, float limitValue, + bool searchRow, bool lowBound, bool ascending) +{ + int min = 0; + int max = maxIdx; + int mid = 0; + int retVal; + while (max >= min) { + mid = (min + max) / 2; + float arrayValue = getDataValue(array, searchRow, mid); + if (arrayValue == limitValue) + return mid; + if (ascending) { + if (arrayValue < limitValue) + min = mid + 1; + else + max = mid - 1; + } else { + if (arrayValue > limitValue) + min = mid + 1; + else + max = mid - 1; + } + } + + // Exact match not found, return closest depending on bound. + // The boundary is between last mid and min/max. + if (lowBound == ascending) { + if (mid > max) + retVal = mid; + else + retVal = min; + } else { + if (mid > max) + retVal = max; + else + retVal = mid; + } + if (retVal < 0 || retVal > maxIdx) { + retVal = -1; + } else if (lowBound) { + if (getDataValue(array, searchRow, retVal) < limitValue) + retVal = -1; + } else { + if (getDataValue(array, searchRow, retVal) > limitValue) + retVal = -1; + } + return retVal; +} + QRect Surface3DRenderer::calculateSampleRect(const QSurfaceDataArray &array) { QRect sampleSpace; - const int rowCount = array.size(); - const int columnCount = array.at(0)->size(); - - const float axisMinX = m_axisCacheX.min(); - const float axisMaxX = m_axisCacheX.max(); - const float axisMinZ = m_axisCacheZ.min(); - const float axisMaxZ = m_axisCacheZ.max(); + const int maxRow = array.size() - 1; + const int maxColumn = array.at(0)->size() - 1; // We assume data is ordered sequentially in rows for X-value and in columns for Z-value. // Determine if data is ascending or descending in each case. - const bool ascendingX = array.at(0)->at(0).x() < array.at(0)->at(columnCount - 1).x(); - const bool ascendingZ = array.at(0)->at(0).z() < array.at(rowCount - 1)->at(0).z(); - - const int minCol = ascendingX ? 0 : columnCount - 1; - const int maxCol = ascendingX ? columnCount - 1 : 0; - const int colStep = ascendingX ? 1 : -1; - const int minRow = ascendingZ ? 0 : rowCount - 1; - const int maxRow = ascendingZ ? rowCount - 1 : 0; - const int rowStep = ascendingZ ? 1 : -1; - - bool found = false; - int idx = 0; - int i = 0; - // m_minVisibleColumnValue - for (i = 0, idx = minCol, found = false; i < columnCount; i++) { - if (array.at(0)->at(idx).x() >= axisMinX) { - found = true; - break; - } - idx += colStep; - } - if (found) { - m_minVisibleColumnValue = array.at(0)->at(idx).x(); + const bool ascendingX = array.at(0)->at(0).x() < array.at(0)->at(maxColumn).x(); + const bool ascendingZ = array.at(0)->at(0).z() < array.at(maxRow)->at(0).z(); + + int idx = binarySearchArray(array, maxColumn, m_axisCacheX.min(), true, true, ascendingX); + if (idx != -1) { if (ascendingX) sampleSpace.setLeft(idx); else @@ -607,16 +636,8 @@ QRect Surface3DRenderer::calculateSampleRect(const QSurfaceDataArray &array) return sampleSpace; } - // m_maxVisibleColumnValue - for (i = 0, idx = maxCol, found = false; i < columnCount; i++) { - if (array.at(0)->at(idx).x() <= axisMaxX) { - found = true; - break; - } - idx -= colStep; - } - if (found) { - m_maxVisibleColumnValue = array.at(0)->at(idx).x(); + idx = binarySearchArray(array, maxColumn, m_axisCacheX.max(), true, false, ascendingX); + if (idx != -1) { if (ascendingX) sampleSpace.setRight(idx); else @@ -626,16 +647,8 @@ QRect Surface3DRenderer::calculateSampleRect(const QSurfaceDataArray &array) return sampleSpace; } - // m_minVisibleRowValue - for (i = 0, idx = minRow, found = false; i < rowCount; i++) { - if (array.at(idx)->at(0).z() >= axisMinZ) { - found = true; - break; - } - idx += rowStep; - } - if (found) { - m_minVisibleRowValue = array.at(idx)->at(0).z(); + idx = binarySearchArray(array, maxRow, m_axisCacheZ.min(), false, true, ascendingZ); + if (idx != -1) { if (ascendingZ) sampleSpace.setTop(idx); else @@ -645,16 +658,8 @@ QRect Surface3DRenderer::calculateSampleRect(const QSurfaceDataArray &array) return sampleSpace; } - // m_maxVisibleRowValue - for (i = 0, idx = maxRow, found = false; i < rowCount; i++) { - if (array.at(idx)->at(0).z() <= axisMaxZ) { - found = true; - break; - } - idx -= rowStep; - } - if (found) { - m_maxVisibleRowValue = array.at(idx)->at(0).z(); + idx = binarySearchArray(array, maxRow, m_axisCacheZ.max(), false, false, ascendingZ); + if (idx != -1) { if (ascendingZ) sampleSpace.setBottom(idx); else @@ -664,9 +669,6 @@ QRect Surface3DRenderer::calculateSampleRect(const QSurfaceDataArray &array) return sampleSpace; } - m_visibleColumnRange = m_maxVisibleColumnValue - m_minVisibleColumnValue; - m_visibleRowRange = m_maxVisibleRowValue - m_minVisibleRowValue; - return sampleSpace; } @@ -2203,11 +2205,18 @@ void Surface3DRenderer::updateSelectionTextures() void Surface3DRenderer::createSelectionTexture(SurfaceSeriesRenderCache *cache, uint &lastSelectionId) { + // Create the selection ID image. Each grid corner gets 2x2 pixel area of // ID color so that each vertex (data point) has 4x4 pixel area of ID color const QRect &sampleSpace = cache->sampleSpace(); int idImageWidth = (sampleSpace.width() - 1) * 4; int idImageHeight = (sampleSpace.height() - 1) * 4; + + if (idImageHeight < 0 || idImageWidth < 0) { + cache->setSelectionIdRange(-1, -1); + return; + } + int stride = idImageWidth * 4 * sizeof(uchar); // 4 = number of color components (rgba) uint idStart = lastSelectionId; diff --git a/src/datavisualization/engine/surface3drenderer_p.h b/src/datavisualization/engine/surface3drenderer_p.h index 9af3f47d..0c286136 100644 --- a/src/datavisualization/engine/surface3drenderer_p.h +++ b/src/datavisualization/engine/surface3drenderer_p.h @@ -67,12 +67,6 @@ private: GLfloat m_scaleZ; GLfloat m_scaleXWithBackground; GLfloat m_scaleZWithBackground; - GLfloat m_minVisibleColumnValue; - GLfloat m_maxVisibleColumnValue; - GLfloat m_minVisibleRowValue; - GLfloat m_maxVisibleRowValue; - GLfloat m_visibleColumnRange; - GLfloat m_visibleRowRange; GLuint m_depthTexture; GLuint m_depthModelTexture; GLuint m_depthFrameBuffer; -- cgit v1.2.3