From c5fc66ee58f2c60f2d226868bb1cf5b91badaf53 Mon Sep 17 00:00:00 2001 From: sanine Date: Sat, 1 Oct 2022 20:59:36 -0500 Subject: add ode --- .../GIMPACT/include/GIMPACT/gim_boxpruning.h | 323 +++++++++++++++++++++ 1 file changed, 323 insertions(+) create mode 100644 libs/ode-0.16.1/GIMPACT/include/GIMPACT/gim_boxpruning.h (limited to 'libs/ode-0.16.1/GIMPACT/include/GIMPACT/gim_boxpruning.h') diff --git a/libs/ode-0.16.1/GIMPACT/include/GIMPACT/gim_boxpruning.h b/libs/ode-0.16.1/GIMPACT/include/GIMPACT/gim_boxpruning.h new file mode 100644 index 0000000..cfa6c79 --- /dev/null +++ b/libs/ode-0.16.1/GIMPACT/include/GIMPACT/gim_boxpruning.h @@ -0,0 +1,323 @@ +#ifndef GIM_BOXPRUNING_H_INCLUDED +#define GIM_BOXPRUNING_H_INCLUDED + +/*! \file gim_boxpruning.h +\author Francisco León +*/ +/* +----------------------------------------------------------------------------- +This source file is part of GIMPACT Library. + +For the latest info, see http://gimpact.sourceforge.net/ + +Copyright (c) 2006 Francisco Leon. C.C. 80087371. +email: projectileman@yahoo.com + + This library is free software; you can redistribute it and/or + modify it under the terms of EITHER: + (1) The GNU Lesser General Public License as published by the Free + Software Foundation; either version 2.1 of the License, or (at + your option) any later version. The text of the GNU Lesser + General Public License is included with this library in the + file GIMPACT-LICENSE-LGPL.TXT. + (2) The BSD-style license that is included with this library in + the file GIMPACT-LICENSE-BSD.TXT. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files + GIMPACT-LICENSE-LGPL.TXT and GIMPACT-LICENSE-BSD.TXT for more details. + +----------------------------------------------------------------------------- +*/ + + +#include "GIMPACT/gim_radixsort.h" +#include "GIMPACT/gim_geometry.h" + +/*! \defgroup BOX_PRUNNING + +\brief +Tools for find overlapping objects on a scenary. These functions sort boxes for faster collisioin queries, using radix sort or quick sort as convenience. See \ref SORTING . + +*/ +//! @{ +//! Overlapping pair +struct GIM_PAIR +{ + GUINT32 m_index1; + GUINT32 m_index2; +}; +//typedef struct _GIM_PAIR GIM_PAIR; + +//! Box container +struct GIM_AABB_SET +{ + GUINT32 m_count; + aabb3f m_global_bound;//!< Global calculated bound of all boxes + aabb3f * m_boxes; + GUINT32 * m_maxcoords;//!m_sorted_mincoords == 0, then it allocs the sorted coordinates +*/ +void gim_aabbset_sort(GIM_AABB_SET * aabbset, char calc_global_bound); + +//! log(N) Complete box pruning. Returns a list of overlapping pairs of boxes, each box of the pair belongs to the same set. +/*! +\pre aabbset must be allocated and sorted, the boxes must be already set. +\param aabbset Must be sorted. Global bound isn't required +\param collision_pairs Array of GIM_PAIR elements. Must be initialized before (Reserve size ~ 100) +*/ +void gim_aabbset_self_intersections_sorted(GIM_AABB_SET * aabbset, GDYNAMIC_ARRAY * collision_pairs); + +//! NxN Complete box pruning. Returns a list of overlapping pairs of boxes, each box of the pair belongs to the same set. +/*! +\pre aabbset must be allocated, the boxes must be already set. +\param aabbset Global bound isn't required. Doen't need to be sorted. +\param collision_pairs Array of GIM_PAIR elements. Must be initialized before (Reserve size ~ 100) +*/ +void gim_aabbset_self_intersections_brute_force(GIM_AABB_SET * aabbset, GDYNAMIC_ARRAY * collision_pairs); + +//! log(N) Bipartite box pruning. Returns a list of overlapping pairs of boxes, each box of the pair belongs to a different set. +/*! +\pre aabbset1 and aabbset2 must be allocated and sorted, the boxes must be already set. +\param aabbset1 Must be sorted, Global bound is required. +\param aabbset2 Must be sorted, Global bound is required. +\param collision_pairs Array of GIM_PAIR elements. Must be initialized before (Reserve size ~ 100) +*/ +void gim_aabbset_bipartite_intersections_sorted(GIM_AABB_SET * aabbset1, GIM_AABB_SET * aabbset2, GDYNAMIC_ARRAY * collision_pairs); + +//! NxM Bipartite box pruning. Returns a list of overlapping pairs of boxes, each box of the pair belongs to a different set. +/*! +\pre aabbset1 and aabbset2 must be allocated and sorted, the boxes must be already set. +\param aabbset1 Must be sorted, Global bound is required. +\param aabbset2 Must be sorted, Global bound is required. +\param collision_pairs Array of GIM_PAIR elements. Must be initialized before (Reserve size ~ 100) +*/ +void gim_aabbset_bipartite_intersections_brute_force(GIM_AABB_SET * aabbset1,GIM_AABB_SET * aabbset2, GDYNAMIC_ARRAY * collision_pairs); + + +/* + Brute-Force Vs Sorted pruning +Different approaches must be applied when colliding sets with different number of +elements. When sets have less of 100 boxes, is often better to apply force brute +approach instead of sorted methods, because at lowlevel bruteforce routines gives +better perormance and consumes less resources, due of their simplicity. +But when sets are larger, the complexiity of bruteforce increases exponencially. +In the case of large sets, sorted approach is applied. So GIMPACT has the following +strategies: + +On Sorting sets: +!) When sets have more of 140 boxes, the boxes are sorted by its coded min coord +and the global box is calculated. But when sets are smaller (less of 140 boxes), +Is convenient to apply brute force approach. + +*******************************************************************************/ + +//! Constant for apply approaches between brute force and sorted pruning on bipartite queries +#define GIM_MIN_SORTED_BIPARTITE_PRUNING_BOXES 600 +//! Constant for apply approaches between brute force and sorted pruning for box collision +#define GIM_MIN_SORTED_PRUNING_BOXES 140 + + +//Use these functions for general initialization + +//! Initalizes the set. Sort Boxes if needed. +/*! +\pre aabbset must be allocated. And the boxes must be already set. +\post If the set has less of GIM_MIN_SORTED_BIPARTITE_PRUNING_BOXES boxes, only calcs the global box, + else it Sorts the entire set( Only applicable for large sets) +*/ +void gim_aabbset_update(GIM_AABB_SET * aabbset); + +///Use these functions for general collision + +//! Complete box pruning. Returns a list of overlapping pairs of boxes, each box of the pair belongs to the same set. +/*! +This function sorts the set and then it calls to gim_aabbset_self_intersections_brute_force or gim_aabbset_self_intersections_sorted. This is an example of how to use this function: +\code +//Create contact list +GDYNAMIC_ARRAY collision_pairs; +GIM_CREATE_PAIR_SET(collision_pairs); +//Do collision +gim_aabbset_self_intersections(&aabbset,&collision_pairs); +if(collision_pairs.m_size==0) +{ + GIM_DYNARRAY_DESTROY(collision_pairs);// + return; //no collisioin +} + +//pair pointer +GIM_PAIR *pairs = GIM_DYNARRAY_POINTER(GIM_PAIR,collision_pairs); +GUINT i, ti1,ti2; +for (i=0;im_count >= GIM_MIN_SORTED_PRUNING_BOXES, then it calls to gim_aabbset_sort and then to gim_aabbset_self_intersections_sorted. Global box won't be calculated. +*/ +void gim_aabbset_self_intersections(GIM_AABB_SET * aabbset, GDYNAMIC_ARRAY * collision_pairs); + +//! Collides two sets. Returns a list of overlapping pairs of boxes, each box of the pair belongs to a different set. +/*! +\pre aabbset1 and aabbset2 must be allocated and updated. See gim_aabbset_update. +\param aabbset1 Must be updated. +\param aabbset2 Must be updated. +\param collision_pairs Array of GIM_PAIR elements. Must be initialized before (Reserve size ~ 100) +*/ +void gim_aabbset_bipartite_intersections(GIM_AABB_SET * aabbset1, GIM_AABB_SET * aabbset2, GDYNAMIC_ARRAY * collision_pairs); + +///Function for create Box collision result set + +#define GIM_CREATE_BOXQUERY_LIST(dynarray) GIM_DYNARRAY_CREATE(GUINT32,dynarray,G_ARRAY_GROW_SIZE) + +//! Finds intersections between a box and a set. Return the colliding boxes of the set +/*! +\pre aabbset must be allocated and initialized. +\param test_aabb Box for collision query +\param aabbset Set of boxes .Global bound is required. +\param collided Array of GUINT elements, indices of boxes. Must be initialized before (Reserve size ~ 100) +*/ +void gim_aabbset_box_collision(aabb3f *test_aabb, GIM_AABB_SET * aabbset, GDYNAMIC_ARRAY * collided); + +//! Finds intersections between a box and a set. Return the colliding boxes of the set +/*! +\pre aabbset must be allocated and initialized. +\param vorigin Origin point of ray. +\param vdir Direction vector of ray. +\param tmax Max distance param for ray. +\param aabbset Set of boxes .Global bound is required. +\param collided Array of GUINT elements, indices of boxes. Must be initialized before (Reserve size ~ 100) +*/ +void gim_aabbset_ray_collision(vec3f vorigin,vec3f vdir, GREAL tmax, GIM_AABB_SET * aabbset, GDYNAMIC_ARRAY * collided); + + +/* +For sorting, each box corner must be discretized to a 32 bit integer. +For this, we take the x and z coordinates from the box corner (a vector vec3f) +Then convert the (x,z) pair to an integer. For convenience, we choose an error +constant for converting the coordinates (0.05). +*******************************************************************************/ + +/** + For fitting the coordinate to an integer, we need to constraint the range of its values. So each coord component (x, z) must lie between 0 and 65536. + 20 give us a 0.05 floating point error +*/ +#define ERROR_AABB 20.0f + +/** +An error of 0.05 allows to make coordinates up to 1638.0f and no less of -1638.0f. +So the maximum size of a room should be about 3276x3276 . Its dimensions must lie between [-1638,1638.0f] +*/ +#define MAX_AABB_SIZE 1638.0f + +//! Converts a vector coordinate to an integer for box sorting +/*! +\param vx X component +\param vz Z component +\param uint_key a GUINT +*/ +#define GIM_CONVERT_VEC3F_GUINT_XZ(vx,vz,uint_key)\ +{\ + GUINT32 _z = ((GUINT32)(vz*ERROR_AABB))+32768;\ + uint_key = ((GUINT32)(vx*ERROR_AABB))+32768;\ + uint_key = (uint_key<<16) + _z;\ +}\ + +//! Converts a vector coordinate to an integer for box sorting,rounding to the upper int +/*! +\param vx X component +\param vz Z component +\param uint_key a GUINT +*/ +#define GIM_CONVERT_VEC3F_GUINT_XZ_UPPER(vx,vz,uint_key)\ +{\ + GUINT32 _z = ((GUINT32)ceilf(vz*ERROR_AABB))+32768;\ + uint_key = ((GUINT32)ceilf(vx*ERROR_AABB))+32768;\ + uint_key = (uint_key<<16) + _z;\ +}\ + + +//! Converts a vector coordinate to an integer for box sorting. Secure clamped +/*! +\param vx X component +\param vz Z component +\param uint_key a GUINT +*/ +#define GIM_CONVERT_VEC3F_GUINT_XZ_CLAMPED(vx,vz,uint_key)\ +{\ + GREAL _cx = CLAMP(vx,-MAX_AABB_SIZE,MAX_AABB_SIZE);\ + GREAL _cz = CLAMP(vz,-MAX_AABB_SIZE,MAX_AABB_SIZE);\ + GUINT32 _z = ((GUINT32)(_cz*ERROR_AABB))+32768;\ + uint_key = ((GUINT32)(_cx*ERROR_AABB))+32768;\ + uint_key = (uint_key<<16) + _z;\ +}\ + +//! Converts a vector coordinate to an integer for box sorting. Secure clamped, rounded +/*! +\param vx X component +\param vz Z component +\param uint_key a GUINT +*/ +#define GIM_CONVERT_VEC3F_GUINT_XZ_UPPER_CLAMPED(vx,vz,uint_key)\ +{\ + GREAL _cx = CLAMP(vx,-MAX_AABB_SIZE,MAX_AABB_SIZE);\ + GREAL _cz = CLAMP(vz,-MAX_AABB_SIZE,MAX_AABB_SIZE);\ + GUINT32 _z = ((GUINT32)ceilf(_cz*ERROR_AABB))+32768;\ + uint_key = ((GUINT32)ceilf(_cx*ERROR_AABB))+32768;\ + uint_key = (uint_key<<16) + _z;\ +}\ + +//! @} + +#endif // GIM_BOXPRUNING_H_INCLUDED -- cgit v1.2.1