#include <gjk.h>
Public Types | |
| typedef vector3_type_ | vector3_type |
| typedef vector3_type::value_traits | value_traits |
| typedef vector3_type::value_type | real_type |
Public Member Functions | |
| GJK () | |
| template<typename convex_shape_type1 , typename convex_shape_type2 > | |
| bool | is_intersecting (convex_shape_type1 &A, convex_shape_type2 &B, vector3_type &g) |
| template<typename convex_shape_type1 , typename convex_shape_type2 > | |
| bool | get_common_point (convex_shape_type1 &A, convex_shape_type2 &B, vector3_type &g, vector3_type &pa, vector3_type &pb) |
| template<typename convex_shape_type1 , typename convex_shape_type2 > | |
| void | get_closest_points (convex_shape_type1 &A, convex_shape_type2 &B, vector3_type &pa, vector3_type &pb) |
Protected Attributes | |
| real_type | m_rel_error |
| Relative error in the computed distance. | |
| real_type | m_abs_error |
| Absolute error if the distance is almost zero. | |
| real_type | m_abs_error2 |
| Absolute squared error. | |
| vector3_type | m_p [4] |
| Support points of object A. | |
| vector3_type | m_q [4] |
| Support points of object B. | |
| vector3_type | m_y [4] |
| Support points of A - B. | |
| int | m_bits |
| Identifies current simplex. | |
| int | m_last |
| Identifies last found support point. | |
| int | m_last_bit |
| last_bit = 1<<last | |
| int | m_all_bits |
| all_bits = bits|last_bit | |
| real_type | m_det [16][4] |
| Cached sub-determinants. | |
| real_type | m_dp [4][4] |
| Cached dot products. | |
GJK Algorithm. This class implements the Gilbert, Johnson and Keerthi collision detection algorithm, also known as GJK.
The algorithm is an iterative simplex based algorithm, our implementation is based on the original code implemented by Gino van den Bergen in his GJK-engine (which later has become part of his SOLID collision detection library), thanks Gino:-)
For details on GJK, we refer to
[1] Uffe ??? and Niels ???: ???. DIKU master thesis no. 01-01-2, pp. 49-77 [2] Gino van den Bergen: A Fast and Robust GJK Implementation for Collision Detection of Convex Objects. Journal of Graphics Tools, 4(2):7-25 (1999).
In [1] there is an excellent explanation and proof of the sub-algorithm in GJK, it also contains a new method for dealing with numerical errors. The authors claim their method is more robust than Gino's. We have not implemented it, but sugest it as a possible resolution in case we ever get into numerical problems with GJK.
Support Mapping Function
p = get_support_point(v)
This method is needed by GJK. The method computes the extremum point in a given direction of a convex point set.
| v | A pointer to a vector, holding the direction |
| typedef vector3_type::value_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::real_type |
| typedef vector3_type::value_traits OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::value_traits |
| typedef vector3_type_ OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::vector3_type |
| OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::GJK | ( | ) | [inline] |
| void OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::get_closest_points | ( | convex_shape_type1 & | A, | |
| convex_shape_type2 & | B, | |||
| vector3_type & | pa, | |||
| vector3_type & | pb | |||
| ) | [inline] |
Closest Point Queury. This is the GJK version as Gino van den Bergen has presented it.
| A | A pointer to one convex volume | |
| B | A pointer to another convex volume | |
| pa | A pointer to a vector, which upon return contains a closest point on A to B | |
| pb | A pointer to a vector, which upon return contains a closest point on B to A |
| bool OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::get_common_point | ( | convex_shape_type1 & | A, | |
| convex_shape_type2 & | B, | |||
| vector3_type & | g, | |||
| vector3_type & | pa, | |||
| vector3_type & | pb | |||
| ) | [inline] |
Common Point Queury. In case of intersection a common point between the two specified convex volumes is computed.
Note both pa and pb will contain the same value, this is because we assume that A and B are represented in the same coordinate frame. GJK could take affine transformations of A and B into account. Meaning that A and B could be given in their local frame, but we have no need for this!!!
| A | A pointer to one convex volume | |
| B | A pointer to another convex volume | |
| g | A pointer to a vector, which contains an inital guess for a separation axe, between A and B. Upon return the vector will contain the separation axe, computed by GJK. | |
| pa | A pointer to a vector, which upon return contains a closest point on A to B | |
| pb | A pointer to a vector, which upon return contains a closest point on B to A |
| bool OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::is_intersecting | ( | convex_shape_type1 & | A, | |
| convex_shape_type2 & | B, | |||
| vector3_type & | g | |||
| ) | [inline] |
Intersection Query. This is the ISA-GJK version. Note if coherence should be exploited one should surply the method with the separation axe computed from the previous iteration. The initial value could be any arbitary vector, we sugest that you use the difference between the centers of A and B.
| A | A pointer to one convex volume | |
| B | A pointer to another convex volume | |
| g | A pointer to a vector, which contains an inital guess for a separation axe, between A and B. Upon return the vector will contain the separation axe, computed by GJK. |
real_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_abs_error [protected] |
Absolute error if the distance is almost zero.
real_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_abs_error2 [protected] |
Absolute squared error.
int OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_all_bits [protected] |
all_bits = bits|last_bit
int OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_bits [protected] |
Identifies current simplex.
real_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_det[16][4] [protected] |
Cached sub-determinants.
real_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_dp[4][4] [protected] |
Cached dot products.
int OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_last [protected] |
Identifies last found support point.
int OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_last_bit [protected] |
last_bit = 1<<last
vector3_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_p[4] [protected] |
Support points of object A.
vector3_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_q[4] [protected] |
Support points of object B.
real_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_rel_error [protected] |
Relative error in the computed distance.
vector3_type OpenTissue::gjk::obsolete::detail::GJK< vector3_type_ >::m_y[4] [protected] |
Support points of A - B.
1.7.1