1//
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions
4// are met:
5// * Redistributions of source code must retain the above copyright
6// notice, this list of conditions and the following disclaimer.
7// * Redistributions in binary form must reproduce the above copyright
8// notice, this list of conditions and the following disclaimer in the
9// documentation and/or other materials provided with the distribution.
10// * Neither the name of NVIDIA CORPORATION nor the names of its
11// contributors may be used to endorse or promote products derived
12// from this software without specific prior written permission.
13//
14// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
15// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
18// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25//
26// Copyright (c) 2008-2021 NVIDIA Corporation. All rights reserved.
27// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
28// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
29
30#ifndef SQ_PRUNER_H
31#define SQ_PRUNER_H
32
33#include "foundation/PxBounds3.h"
34#include "geometry/PxGeometry.h"
35#include "PxQueryReport.h"
36#include "PxQueryFiltering.h"
37#include "PsUserAllocated.h"
38#include "SqPruningStructure.h"
39#include "GuSphere.h"
40#include "GuBox.h"
41#include "GuCapsule.h"
42
43namespace physx
44{
45 namespace Gu
46 {
47 class ShapeData;
48 class BVHStructure;
49 }
50}
51
52namespace physx
53{
54 namespace Cm
55 {
56 class RenderOutput;
57 }
58
59namespace Sq
60{
61
62typedef PxU32 PrunerHandle;
63typedef PxU32 PrunerCompoundId;
64
65static const PrunerHandle INVALID_PRUNERHANDLE = 0xFFffFFff;
66static const PxReal SQ_PRUNER_INFLATION = 1.01f; // pruner test shape inflation (not narrow phase shape)
67
68struct PrunerPayload
69{
70 size_t data[2];
71
72 PX_FORCE_INLINE bool operator == (const PrunerPayload& other) const
73 {
74 return (data[0] == other.data[0]) && (data[1] == other.data[1]);
75 }
76};
77
78struct PrunerCallback
79{
80 virtual PxAgain invoke(PxReal& distance, const PrunerPayload& payload) = 0;
81 virtual ~PrunerCallback() {}
82};
83
84class Pruner : public Ps::UserAllocated
85{
86public:
87
88 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
89 /**
90 * \brief Adds objects to the pruner.
91 * \param results [out] an array for resulting handles
92 * \param bounds [in] an array of bounds. These bounds are used as-is so they should be pre-inflated if inflation is needed.
93 * \param userData [in] an array of object data
94 * \param count [in] the number of objects in the arrays
95 * \param hasPruningStructure [in] if added objects have pruning structure. The structure will be merged later, adding the objects will not invalidate the pruner.
96 *
97 * \return true if success, false if internal allocation failed. The first failing add results in a INVALID_PRUNERHANDLE.
98 *
99 * Handles are usable as indices. Each handle is either be a recycled handle returned by the client via removeObjects(),
100 * or a fresh handle that is either zero, or one greater than the last fresh handle returned.
101 *
102 * Objects and bounds in the arrays have the same number of elements and ordering.
103 */
104 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
105 virtual bool addObjects(PrunerHandle* results, const PxBounds3* bounds, const PrunerPayload* userData, PxU32 count, bool hasPruningStructure) = 0;
106
107 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
108 /**
109 * Removes objects from the pruner.
110 * \param handles [in] the objects to remove
111 * \param count [in] the number of objects to remove
112 */
113 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
114 virtual void removeObjects(const PrunerHandle* handles, PxU32 count) = 0;
115
116 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
117 /**
118 * Updates objects after manually updating their bounds via "getPayload" calls.
119 * \param handles [in] the objects to update
120 * \param count [in] the number of objects to update
121 */
122 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
123 virtual void updateObjectsAfterManualBoundsUpdates(const PrunerHandle* handles, PxU32 count) = 0;
124
125 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
126 /**
127 * Updates objects with new indexed bounds.
128 * \param handles [in] the objects to update
129 * \param indices [in] the indices of the bounds in the bounds array
130 * \param newBounds [in] updated bounds array
131 * \param count [in] the number of objects to update
132 *
133 * \warning THESE BOUNDS WILL BE INFLATED ON-THE-FLY. So this is inconsistent with the "addObjects" behavior.
134 * \warning The inflation value is hardcoded in Sq::inflateBounds().
135 */
136 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
137 virtual void updateObjectsAndInflateBounds(const PrunerHandle* handles, const PxU32* indices, const PxBounds3* newBounds, PxU32 count) = 0;
138
139 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
140 /**
141 * Makes the queries consistent with previous changes.
142 * This function must be called before starting queries on an updated Pruner and assert otherwise.
143 */
144 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
145 virtual void commit() = 0;
146
147 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
148 /**
149 * Merges pruning structure to current pruner, parameters may differ for each pruner implementation
150 * \param mergeParams [in] Pruning structure to merge.
151 */
152 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
153 virtual void merge(const void* mergeParams) = 0;
154
155 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
156 /**
157 * Query functions
158 *
159 * Note: return value may disappear if PrunerCallback contains the necessary information
160 * currently it is still used for the dynamic pruner internally (to decide if added objects must be queried)
161 */
162 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
163 virtual PxAgain raycast(const PxVec3& origin, const PxVec3& unitDir, PxReal& inOutDistance, PrunerCallback&) const = 0;
164 virtual PxAgain overlap(const Gu::ShapeData& queryVolume, PrunerCallback&) const = 0;
165 virtual PxAgain sweep(const Gu::ShapeData& queryVolume, const PxVec3& unitDir, PxReal& inOutDistance, PrunerCallback&) const = 0;
166
167 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
168 /**
169 * Retrieve the object data associated with the handle
170 *
171 * \param handle The handle returned by addObjects()
172 *
173 * \return A reference to the object data
174 */
175 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
176 virtual const PrunerPayload& getPayload(PrunerHandle handle) const = 0;
177
178 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
179 /**
180 * Retrieve the object data associated with the handle, plus the destination address for its matrix. The user is then expected to write the new AABB there.
181 *
182 * \param handle [in] The handle returned by addObjects()
183 * \param bounds [out] destination address for this object's bounds
184 *
185 * \return A reference to the object data
186 */
187 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
188 virtual const PrunerPayload& getPayload(PrunerHandle handle, PxBounds3*& bounds) const = 0;
189
190 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
191 /**
192 * Preallocate space
193 *
194 * \param entries the number of entries to preallocate space for
195 */
196 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
197 virtual void preallocate(PxU32 entries) = 0;
198
199 // shift the origin of the pruner objects
200 virtual void shiftOrigin(const PxVec3& shift) = 0;
201
202 virtual ~Pruner() {}
203
204 // additional 'internal' interface
205 virtual void visualize(Cm::RenderOutput&, PxU32) const {}
206};
207
208//////////////////////////////////////////////////////////////////////////
209/**
210* Pruner building accel structure over time base class
211*/
212//////////////////////////////////////////////////////////////////////////
213class IncrementalPruner: public Pruner
214{
215public:
216 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
217 /**
218 * gets rid of internal accel struct.
219 */
220 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
221 virtual void purge() = 0;
222
223 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
224 /**
225 * sets the rebuild hint rate used for step building the accel structure.
226 */
227 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
228 virtual void setRebuildRateHint(PxU32 nbStepsForRebuild) = 0;
229
230 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
231 /**
232 * Steps the accel structure build.
233 * synchronousCall specifies if initialization can happen. It should not initialize build when called from a different thread
234 * returns true if finished
235 */
236 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
237 virtual bool buildStep(bool synchronousCall = true) = 0;
238
239 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
240 /**
241 * Prepares new tree build
242 * returns true if new tree is needed
243 */
244 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
245 virtual bool prepareBuild() = 0;
246};
247
248
249//////////////////////////////////////////////////////////////////////////
250// Compound flag to use for static/dynamic filtering atm
251struct CompoundFlag
252{
253 enum Enum
254 {
255 STATIC_COMPOUND = (1<<0),
256 DYNAMIC_COMPOUND = (1<<1)
257 };
258};
259
260PX_COMPILE_TIME_ASSERT(PxQueryFlag::eSTATIC & CompoundFlag::STATIC_COMPOUND);
261PX_COMPILE_TIME_ASSERT(PxQueryFlag::eDYNAMIC & CompoundFlag::DYNAMIC_COMPOUND);
262
263//////////////////////////////////////////////////////////////////////////
264/**
265* Pruner holding compound objects
266*/
267//////////////////////////////////////////////////////////////////////////
268class CompoundPruner: public Ps::UserAllocated
269{
270public:
271 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
272 /**
273 * \brief Adds compound to the pruner.
274 * \param results [out] an array for resulting handles
275 * \param bvhStructure [in] BVH structure holding bounds and BVH.
276 * \param compoundId [in] compound id
277 * \param transform [in] compound transform
278 * \param userData [in] an array of object data
279 *
280 * \return true if success, false if internal allocation failed. The first failing add results in a INVALID_PRUNERHANDLE.
281 *
282 * Handles are usable as indices. Each handle is either be a recycled handle returned by the client via removeObjects(),
283 * or a fresh handle that is either zero, or one greater than the last fresh handle returned.
284 *
285 */
286 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
287 virtual bool addCompound(PrunerHandle* results, const Gu::BVHStructure& bvhStructure, PrunerCompoundId compoundId, const PxTransform& transform, CompoundFlag::Enum flags, const PrunerPayload* userData) = 0;
288
289 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
290 /**
291 * Removes compound from the pruner.
292 * \param compoundId [in] compound to remove
293 */
294 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
295 virtual void removeCompound(PrunerCompoundId compoundId) = 0;
296
297 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
298 /**
299 * Updates compound object
300 * \param compoundId [in] compound to update
301 * \param transform [in] compound transformation
302 */
303 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
304 virtual void updateCompound(PrunerCompoundId compoundId, const PxTransform& transform) = 0;
305
306 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
307 /**
308 * Updates object after manually updating their bounds via "getPayload" calls.
309 * \param compoundId [in] compound that the object belongs to
310 * \param handle [in] the object to update
311 */
312 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
313 virtual void updateObjectAfterManualBoundsUpdates(PrunerCompoundId compoundId, const PrunerHandle handle) = 0;
314
315 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
316 /**
317 * Removes object from compound pruner.
318 * \param compoundId [in] compound that the object belongs to
319 * \param handle [in] the object to remove
320 */
321 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
322 virtual void removeObject(PrunerCompoundId compoundId, const PrunerHandle handle) = 0;
323
324 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
325 /**
326 * \brief Adds object to the pruner.
327 * \param compoundId [in] compound that the object belongs to
328 * \param result [out] an array for resulting handles
329 * \param bounds [in] an array of bounds. These bounds are used as-is so they should be pre-inflated if inflation is needed.
330 * \param userData [in] an array of object data
331 *
332 * \return true if success, false if internal allocation failed. The first failing add results in a INVALID_PRUNERHANDLE.
333 */
334 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
335 virtual bool addObject(PrunerCompoundId compoundId, PrunerHandle& result, const PxBounds3& bounds, const PrunerPayload userData) = 0;
336
337 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
338 /**
339 * Query functions
340 *
341 * Note: return value may disappear if PrunerCallback contains the necessary information
342 * currently it is still used for the dynamic pruner internally (to decide if added objects must be queried)
343 */
344 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
345 virtual PxAgain raycast(const PxVec3& origin, const PxVec3& unitDir, PxReal& inOutDistance, PrunerCallback&, PxQueryFlags flags) const = 0;
346 virtual PxAgain overlap(const Gu::ShapeData& queryVolume, PrunerCallback&, PxQueryFlags flags) const = 0;
347 virtual PxAgain sweep(const Gu::ShapeData& queryVolume, const PxVec3& unitDir, PxReal& inOutDistance, PrunerCallback&, PxQueryFlags flags) const = 0;
348
349 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
350 /**
351 * Retrieve the object data associated with the handle
352 *
353 * \param handle [in] The handle returned by addObjects()
354 * \param compoundId [in] The compound id
355 *
356 * \return A reference to the object data
357 */
358 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
359 virtual const PrunerPayload& getPayload(PrunerHandle handle, PrunerCompoundId compoundId) const = 0;
360
361 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
362 /**
363 * Retrieve the object data associated with the handle, plus the destination address for its matrix. The user is then expected to write the new AABB there.
364 *
365 * \param handle [in] The handle returned by addObjects()
366 * \param compoundId [in] The compound id
367 * \param bounds [out] destination address for this object's bounds
368 *
369 * \return A reference to the object data
370 */
371 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
372 virtual const PrunerPayload& getPayload(PrunerHandle handle, PrunerCompoundId compoundId, PxBounds3*& bounds) const = 0;
373
374
375 // shift the origin of the pruner objects
376 virtual void shiftOrigin(const PxVec3& shift) = 0;
377
378 virtual ~CompoundPruner() {}
379
380 // additional 'internal' interface
381 virtual void visualize(Cm::RenderOutput&, PxU32) const {}
382
383};
384
385
386//////////////////////////////////////////////////////////////////////////
387/**
388* Creates AABBPruner
389*/
390//////////////////////////////////////////////////////////////////////////
391IncrementalPruner* createAABBPruner(bool incrementalRebuild);
392
393}
394
395}
396
397#endif // SQ_PRUNER_H
398

source code of qtquick3dphysics/src/3rdparty/PhysX/source/scenequery/include/SqPruner.h