0028824: Possibility to build OCCT 7.1.0 and above using Visual Studio 2008
[occt.git] / src / BVH / BVH_RadixSorter.hxx
CommitLineData
3a507ddb 1// Created on: 2016-04-13
2// Created by: Denis BOGOLEPOV
3// Copyright (c) 2013-2016 OPEN CASCADE SAS
4//
5// This file is part of Open CASCADE Technology software library.
6//
7// This library is free software; you can redistribute it and/or modify it under
8// the terms of the GNU Lesser General Public License version 2.1 as published
9// by the Free Software Foundation, with special exception defined in the file
10// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11// distribution for complete text of the license and disclaimer of any warranty.
12//
13// Alternatively, this file may be used under the terms of Open CASCADE
14// commercial license or contractual agreement.
15
16#ifndef _BVH_RadixSorter_Header
17#define _BVH_RadixSorter_Header
18
19#include <BVH_Sorter.hxx>
20#include <BVH_Builder.hxx>
3a507ddb 21#include <NCollection_Array1.hxx>
f5b72419 22#include <NCollection_Shared.hxx>
3a507ddb 23
e28f12b3 24#include <algorithm>
25
26#ifdef HAVE_TBB
27 // On Windows, function TryEnterCriticalSection has appeared in Windows NT
28 // and is surrounded by #ifdef in MS VC++ 7.1 headers.
29 // Thus to use it we need to define appropriate macro saying that we will
30 // run on Windows NT 4.0 at least
31 #if defined(_WIN32) && !defined(_WIN32_WINNT)
32 #define _WIN32_WINNT 0x0501
33 #endif
34
35 #include <tbb/parallel_invoke.h>
36#endif
37
3a507ddb 38//! Pair of Morton code and primitive ID.
39typedef std::pair<Standard_Integer, Standard_Integer> BVH_EncodedLink;
40
41//! Performs radix sort of a BVH primitive set using
42//! 10-bit Morton codes (or 1024 x 1024 x 1024 grid).
43template<class T, int N>
44class BVH_RadixSorter : public BVH_Sorter<T, N>
45{
46public:
47
48 typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
49
50public:
51
52 //! Creates new BVH radix sorter for the given AABB.
53 BVH_RadixSorter (const BVH_Box<T, N>& theBox) : myBox (theBox) { }
54
55 //! Sorts the set.
e28f12b3 56 virtual void Perform (BVH_Set<T, N>* theSet) Standard_OVERRIDE { Perform (theSet, 0, theSet->Size() - 1); }
3a507ddb 57
58 //! Sorts the given (inclusive) range in the set.
e28f12b3 59 virtual void Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal) Standard_OVERRIDE;
3a507ddb 60
61 //! Returns Morton codes assigned to BVH primitives.
62 const NCollection_Array1<BVH_EncodedLink>& EncodedLinks() const { return *myEncodedLinks; }
63
64protected:
65
66 //! Axis-aligned bounding box (AABB) to perform sorting.
67 BVH_Box<T, N> myBox;
68
69 //! Morton codes assigned to BVH primitives.
f5b72419 70 Handle(NCollection_Shared<NCollection_Array1<BVH_EncodedLink> >) myEncodedLinks;
3a507ddb 71
72};
73
e28f12b3 74namespace BVH
75{
76 // Radix sort STL predicate for 32-bit integer.
77 struct BitPredicate
78 {
79 Standard_Integer myBit;
80
81 //! Creates new radix sort predicate.
82 BitPredicate (const Standard_Integer theBit) : myBit (theBit) {}
83
84 //! Returns predicate value.
85 bool operator() (const BVH_EncodedLink theLink) const
86 {
87 const Standard_Integer aMask = 1 << myBit;
88 return !(theLink.first & aMask); // 0-bit to the left side
89 }
90 };
91
92 //! STL compare tool used in binary search algorithm.
93 struct BitComparator
94 {
95 Standard_Integer myBit;
96
97 //! Creates new STL comparator.
98 BitComparator (const Standard_Integer theBit) : myBit (theBit) {}
99
100 //! Checks left value for the given bit.
101 bool operator() (BVH_EncodedLink theLink1, BVH_EncodedLink /*theLink2*/)
102 {
103 return !(theLink1.first & (1 << myBit));
104 }
105 };
106
107 //! Tool object for sorting link array using radix sort algorithm.
108 class RadixSorter
109 {
110 public:
111
112 typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
113
114 private:
115
116 //! TBB functor class to run sorting.
117 struct Functor
118 {
119 LinkIterator myStart; //!< Start element of exclusive sorting range
120 LinkIterator myFinal; //!< Final element of exclusive sorting range
121 Standard_Integer myDigit; //!< Bit number used for partition operation
122
123 //! Creates new sorting functor.
124 Functor (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theDigit)
125 : myStart (theStart), myFinal (theFinal), myDigit (theDigit) {}
126
127 //! Runs sorting function for the given range.
128 void operator() () const
129 {
130 RadixSorter::Sort (myStart, myFinal, myDigit);
131 }
132 };
133
134 public:
135
136 static void Sort (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theDigit)
137 {
138 #ifdef HAVE_TBB
139 if (theDigit < 24)
140 {
141 BVH::RadixSorter::perform (theStart, theFinal, theDigit);
142 }
143 else
144 {
145 LinkIterator anOffset = std::partition (theStart, theFinal, BitPredicate (theDigit));
146 tbb::parallel_invoke (Functor (theStart, anOffset, theDigit - 1),
147 Functor (anOffset, theFinal, theDigit - 1));
148 }
149 #else
150 BVH::RadixSorter::perform (theStart, theFinal, theDigit);
151 #endif
152 }
153
154 protected:
155
156 // Performs MSD (most significant digit) radix sort.
157 static void perform (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theBit = 29)
158 {
159 while (theStart != theFinal && theBit >= 0)
160 {
161 LinkIterator anOffset = std::partition (theStart, theFinal, BitPredicate (theBit--));
162 perform (theStart, anOffset, theBit);
163 theStart = anOffset;
164 }
165 }
166 };
167}
168
169// =======================================================================
170// function : Perform
171// purpose :
172// =======================================================================
173template<class T, int N>
174void BVH_RadixSorter<T, N>::Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal)
175{
176 Standard_STATIC_ASSERT (N == 3 || N == 4);
177
178 const Standard_Integer aDimensionX = 1024;
179 const Standard_Integer aDimensionY = 1024;
180 const Standard_Integer aDimensionZ = 1024;
181
182 const BVH_VecNt aSceneMin = myBox.CornerMin();
183 const BVH_VecNt aSceneMax = myBox.CornerMax();
184
185 const T aReverseSizeX = static_cast<T> (aDimensionX) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.x() - aSceneMin.x());
186 const T aReverseSizeY = static_cast<T> (aDimensionY) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.y() - aSceneMin.y());
187 const T aReverseSizeZ = static_cast<T> (aDimensionZ) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.z() - aSceneMin.z());
188
f5b72419 189 myEncodedLinks = new NCollection_Shared<NCollection_Array1<BVH_EncodedLink> >(theStart, theFinal);
e28f12b3 190
191 // Step 1 -- Assign Morton code to each primitive
192 for (Standard_Integer aPrimIdx = theStart; aPrimIdx <= theFinal; ++aPrimIdx)
193 {
194 const BVH_VecNt aCenter = theSet->Box (aPrimIdx).Center();
195
196 Standard_Integer aVoxelX = BVH::IntFloor ((aCenter.x() - aSceneMin.x()) * aReverseSizeX);
197 Standard_Integer aVoxelY = BVH::IntFloor ((aCenter.y() - aSceneMin.y()) * aReverseSizeY);
198 Standard_Integer aVoxelZ = BVH::IntFloor ((aCenter.z() - aSceneMin.z()) * aReverseSizeZ);
199
200 aVoxelX = Max (0, Min (aVoxelX, aDimensionX - 1));
201 aVoxelY = Max (0, Min (aVoxelY, aDimensionY - 1));
202 aVoxelZ = Max (0, Min (aVoxelZ, aDimensionZ - 1));
203
204 aVoxelX = (aVoxelX | (aVoxelX << 16)) & 0x030000FF;
205 aVoxelX = (aVoxelX | (aVoxelX << 8)) & 0x0300F00F;
206 aVoxelX = (aVoxelX | (aVoxelX << 4)) & 0x030C30C3;
207 aVoxelX = (aVoxelX | (aVoxelX << 2)) & 0x09249249;
208
209 aVoxelY = (aVoxelY | (aVoxelY << 16)) & 0x030000FF;
210 aVoxelY = (aVoxelY | (aVoxelY << 8)) & 0x0300F00F;
211 aVoxelY = (aVoxelY | (aVoxelY << 4)) & 0x030C30C3;
212 aVoxelY = (aVoxelY | (aVoxelY << 2)) & 0x09249249;
213
214 aVoxelZ = (aVoxelZ | (aVoxelZ << 16)) & 0x030000FF;
215 aVoxelZ = (aVoxelZ | (aVoxelZ << 8)) & 0x0300F00F;
216 aVoxelZ = (aVoxelZ | (aVoxelZ << 4)) & 0x030C30C3;
217 aVoxelZ = (aVoxelZ | (aVoxelZ << 2)) & 0x09249249;
218
219 myEncodedLinks->ChangeValue (aPrimIdx) = BVH_EncodedLink (
220 aVoxelX | (aVoxelY << 1) | (aVoxelZ << 2), aPrimIdx);
221 }
222
223 // Step 2 -- Sort primitives by their Morton codes using radix sort
224 BVH::RadixSorter::Sort (myEncodedLinks->begin(), myEncodedLinks->end(), 29);
225
226 NCollection_Array1<Standard_Integer> aLinkMap (theStart, theFinal);
227 for (Standard_Integer aLinkIdx = theStart; aLinkIdx <= theFinal; ++aLinkIdx)
228 {
229 aLinkMap (myEncodedLinks->Value (aLinkIdx).second) = aLinkIdx;
230 }
231
232 // Step 3 -- Rearranging primitive list according to Morton codes (in place)
233 Standard_Integer aPrimIdx = theStart;
234 while (aPrimIdx <= theFinal)
235 {
236 const Standard_Integer aSortIdx = aLinkMap (aPrimIdx);
237 if (aPrimIdx != aSortIdx)
238 {
239 theSet->Swap (aPrimIdx, aSortIdx);
240 std::swap (aLinkMap (aPrimIdx),
241 aLinkMap (aSortIdx));
242 }
243 else
244 {
245 ++aPrimIdx;
246 }
247 }
248}
3a507ddb 249
250#endif // _BVH_RadixSorter_Header