concurrenthistogram.h 9.21 KB
Newer Older
schultezub's avatar
schultezub committed
1
2
3
4
5
6
7
// ================================================================================================
// 
// This file is part of the CAMPVis Software Framework.
// 
// If not explicitly stated otherwise: Copyright (C) 2012, all rights reserved,
//      Christian Schulte zu Berge <christian.szb@in.tum.de>
//      Chair for Computer Aided Medical Procedures
8
9
//      Technische Universität München
//      Boltzmannstr. 3, 85748 Garching b. München, Germany
schultezub's avatar
schultezub committed
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// For a full list of authors and contributors, please refer to the file "AUTHORS.txt".
// 
// The licensing of this softare is not yet resolved. Until then, redistribution in source or
// binary forms outside the CAMP chair is not permitted, unless explicitly stated in legal form.
// However, the names of the original authors and the above copyright notice must retain in its
// original state in any case.
// 
// Legal disclaimer provided by the BSD license:
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 
// AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 
// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
// 
// ================================================================================================

30
31
32
#ifndef CONCURRENTHISTOGRAM_H__
#define CONCURRENTHISTOGRAM_H__

33

34
35
#include "tgt/assert.h"
#include "tgt/logmanager.h"
36
#include "tgt/tgt_math.h"
37
#include <tbb/atomic.h>
38

schultezub's avatar
schultezub committed
39
namespace campvis {
40

41
42
43
44
45
46
47
48
    /**
     * Generic implementation of thread-safe n-D histograms.
     * After successfull creation ConcurrentGenericHistogramND ensures:
     *  * Calling addSample() is thread-safe.
     * 
     * \tparam  T   Base data type of the histogram elements
     * \tparam  ND  Dimensionality of the histogram
     */
49
50
51
    template<typename T, size_t ND>
    class ConcurrentGenericHistogramND {
    public:
52
53
54
55
56
57
        /**
         * Creates a new ND-histogram with the given bounds and number of buckets.
         * \param   mins        Array of mininum values for each dimension (must have at least ND elements)
         * \param   maxs        Array of maximum values for each dimension (must have at least ND elements)
         * \param   numBuckets  Array of number of buckets for each dimension (must have at least ND elements)
         */
58
59
        ConcurrentGenericHistogramND(T mins[ND], T maxs[ND], size_t numBuckets[ND]);

60
61
62
        /**
         * Destructor
         */
63
64
        virtual ~ConcurrentGenericHistogramND();

65
66
67
68
69
70
71
        /**
         * Returns the number of buckets for the given dimension.
         * \param   dimension   Dimension, must be smaller than ND.
         * \return  _numBuckets[dimension]
         */
        size_t getNumBuckets(size_t dimension) const;

72
73
74
75
76
77
78
79
80
81
82
        /**
         * Adds the given sample to the histogram.
         * \note    This method is thread-safe.
         * \param   sample  Sample to add, array of the values for each dimension (must have at least ND elements)
         */
        void addSample(T sample[ND]);

        /**
         * Returns a const pointer to the raw data.
         * \return  _buckets
         */
83
84
        const tbb::atomic<size_t>* getBuckets() const { return _buckets; };

85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
        /**
         * Returns the number of elements of the bucket with the given index.
         * \param   index   Array index of the bucket to return.
         * \return  _buckets[index]
         */
        size_t getNumElements(size_t index) const { return _buckets[index]; };

        /**
         * Returns the number of elements in the given bucket.
         * \param   bucket[ND]  Array of the bucket number for each dimension (must have at least ND elements)
         * \return  The number of elements in the given bucket.
         */
        size_t getNumElements(size_t bucket[ND]);

        /**
         * Get the total number of samples in this histogram.
         * \return  _numSamples
         */
103
104
        size_t getNumSamples() const { return _numSamples; };

105
106
107
108
109
110
        /**
         * Returns the number of elements in the bucket with the most samples.
         * \return  _maxFilling
         */
        size_t getMaxFilling() const { return _maxFilling; };

111
    protected:
112
113
114
115
116
117
        /**
         * Transforms the sample value for the given dimension into the corresponding bucket number.
         * \param   dimension   Dimension
         * \param   sample      Sample value to transform
         * \return  The bucket number for \a sample in the given dimension.
         */
118
119
        size_t getBucketNumber(size_t dimension, T sample) const;

120
121
122
123
124
        /**
         * Transforms the array of bucket numbers into the corresponding array index in _buckets.
         * \param   bucketNumbers   Array of the bucket number for each dimension (must have at least ND elements).
         * \return  The array index for the given bucket numbers.
         */
125
126
        size_t getArrayIndex(size_t* bucketNumbers) const;

127
128
129
130
131
132
        T _min[ND];                         ///< minimum value for each dimension
        T _max[ND];                         ///< maximum value for each dimension
        size_t _numBuckets[ND];             ///< number of buckets for each dimension
        size_t _arraySize;                  ///< size of _buckets (total number of buckets)
        tbb::atomic<size_t>* _buckets;      ///< array of the buckets storing the histogram
        tbb::atomic<size_t> _numSamples;    ///< total number of sampled elements
133
        tbb::atomic<size_t> _maxFilling;    ///< number of elements in the bucket with the most samples
134
135
136
137
138
    };

// ================================================================================================

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
139
    campvis::ConcurrentGenericHistogramND<T, ND>::ConcurrentGenericHistogramND(T mins[ND], T maxs[ND], size_t numBuckets[ND]) 
140
141
142
143
144
145
146
147
148
149
150
        : _arraySize(1)
        , _buckets(0)
    {
        for (size_t i = 0; i < ND; ++i) {
            _min[i] = mins[i];
            _max[i] = maxs[i];
            tgtAssert(_min[i] < _max[i], "Min must be smaller than Max!");
            _numBuckets[i] = numBuckets[i];
            _arraySize *= _numBuckets[i];
        }

151
        _buckets = new tbb::atomic<size_t>[_arraySize + 1];
152
153
        for (size_t i = 0; i < _arraySize; ++i)
            _buckets[i] = 0;
154
155
        _numSamples = 0;
        _maxFilling = 0;
156
157
158
    }

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
159
    campvis::ConcurrentGenericHistogramND<T, ND>::~ConcurrentGenericHistogramND() {
160
161
162
        delete [] _buckets;
    }

163
    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
164
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getNumBuckets(size_t dimension) const {
165
166
167
168
        tgtAssert(dimension < ND, "Dimension out of bounds.");
        return _numBuckets[dimension];
    }

169
    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
170
    void campvis::ConcurrentGenericHistogramND<T, ND>::addSample(T sample[ND]) {
171
172
        size_t bucketNumbers[ND];
        for(int i = 0; i < ND; ++i)
173
            bucketNumbers[i] = getBucketNumber(i, sample[i]);
174
175
176
177
178

        size_t index = getArrayIndex(bucketNumbers);
        ++(_buckets[index]);
        ++_numSamples;

179
180
181
182
183
184
185
186
        // thread-safe update of _maxFilling 
        size_t old = 0;
        do {
            old = _maxFilling;
            if (old >= _buckets[index])
                break;
        } while (_maxFilling.compare_and_swap(_buckets[index], old) != old);
    }
187
188

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
189
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getBucketNumber(size_t dimension, T sample) const {
190
        tgtAssert(dimension < ND, "Dimension out of bounds.");
191
192
193
194

        if (sample < _min[dimension] || sample > _max[dimension]) {
            return _numBuckets[dimension];
#ifdef CAMPVIS_DEBUG_NOTNOW
schultezub's avatar
schultezub committed
195
            LWARNINGC("CAMPVis.core.tools.ConcurrentGenericHistogramND", "Added sample " << sample << " out of bounds for dimension " << dimension << ".");
196
#endif
197
198
        }

199
200
201
202
203
        double ratio = static_cast<double>(sample - _min[dimension]) / static_cast<double>(_max[dimension] - _min[dimension]);
        return static_cast<size_t>(tgt::clamp(static_cast<int>(ratio * _numBuckets[dimension]), static_cast<int>(0), static_cast<int>(_numBuckets[dimension] - 1)));
    }

    template<typename T, size_t ND>
schultezub's avatar
schultezub committed
204
    size_t campvis::ConcurrentGenericHistogramND<T, ND>::getArrayIndex(size_t* bucketNumbers) const {
205
206
207
        size_t index = 0;
        size_t multiplier = 1;
        for (size_t i = 0; i < ND; ++i) {
208
209
210
            if (bucketNumbers[i] == _numBuckets[i])
                return _arraySize;

211
212
213
214
215
216
217
218
            index += multiplier * bucketNumbers[i];
            multiplier *= _numBuckets[i];
        }
        return index;
    }


}
219
220

#endif // CONCURRENTHISTOGRAM_H__