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. |
39 | typedef 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). |
43 | template<class T, int N> |
44 | class BVH_RadixSorter : public BVH_Sorter<T, N> |
45 | { |
46 | public: |
47 | |
48 | typedef typename BVH::VectorType<T, N>::Type BVH_VecNt; |
49 | |
50 | public: |
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 | |
64 | protected: |
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 |
74 | namespace 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 | // ======================================================================= |
173 | template<class T, int N> |
174 | void 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 |