Continuous Collision Detection¶
-
bool ipc::is_step_collision_free(const CollisionMesh& mesh,
Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
const std::optional<double> min_distance = std::nullopt,
BroadPhase* broad_phase = nullptr,
const NarrowPhaseCCD& narrow_phase_ccd
= DEFAULT_NARROW_PHASE_CCD);¶ Determine if the step is collision free.
Note
Assumes the trajectory is linear.
- Parameters:¶
- const CollisionMesh &mesh¶
The collision mesh.
- Eigen::ConstRef<Eigen::MatrixXd> vertices_t0¶
Surface vertex vertices at start as rows of a matrix.
- Eigen::ConstRef<Eigen::MatrixXd> vertices_t1¶
Surface vertex vertices at end as rows of a matrix.
- const std::optional<double> min_distance = std::nullopt¶
Deprecated: give the mesh a thickness (CollisionMesh::set_thickness()) instead. If given, every pair keeps this distance and the mesh’s thickness is ignored; otherwise each pair keeps its two primitives’ thicknesses (zero without a thickness).
- BroadPhase *broad_phase = nullptr¶
The broad phase method to use.
- const NarrowPhaseCCD &narrow_phase_ccd = DEFAULT_NARROW_PHASE_CCD¶
The narrow phase CCD algorithm to use.
- Returns:¶
True if any collisions occur.
-
double ipc::compute_collision_free_stepsize(
const CollisionMesh& mesh,
Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
const std::optional<double> min_distance = std::nullopt,
BroadPhase* broad_phase = nullptr,
const NarrowPhaseCCD& narrow_phase_ccd
= DEFAULT_NARROW_PHASE_CCD);¶ Computes a maximal step size that is collision free.
Note
Assumes the trajectory is linear.
Note
When using SweepAndTiniestQueue broad phase, tolerance and max_iterations are extracted from TightInclusionCCD if provided, otherwise defaults are used.
- Parameters:¶
- const CollisionMesh &mesh¶
The collision mesh.
- Eigen::ConstRef<Eigen::MatrixXd> vertices_t0¶
Vertex vertices at start as rows of a matrix. Assumes vertices_t0 is intersection free.
- Eigen::ConstRef<Eigen::MatrixXd> vertices_t1¶
Surface vertex vertices at end as rows of a matrix.
- const std::optional<double> min_distance = std::nullopt¶
Deprecated: give the mesh a thickness (CollisionMesh::set_thickness()) instead. If given, every pair keeps this distance and the mesh’s thickness is ignored; otherwise each pair keeps its two primitives’ thicknesses (zero without a thickness).
- BroadPhase *broad_phase = nullptr¶
The broad phase method to use.
- const NarrowPhaseCCD &narrow_phase_ccd = DEFAULT_NARROW_PHASE_CCD¶
The narrow phase CCD algorithm to use.
- Returns:¶
A step-size \(\in [0, 1]\) that is collision free. A value of 1.0 if a full step and 0.0 is no step.
Narrow Phase CCD¶
- class NarrowPhaseCCD;¶
Inheritance diagram for ipc::NarrowPhaseCCD:
Narrow Phase Continuous Collision Detection (CCD) interface.
Subclassed by ipc::AdditiveCCD, ipc::InexactCCD, ipc::TightInclusionCCD
Public Types¶
- enum class Mode : uint8_t;¶
How a narrow-phase CCD query is used.
Values:
- enumerator STANDALONE;¶
A standalone query: the method applies its own conservative strategy (minimum-distance inflation, small-TOI reruns, and rescaling).
- enumerator COMPONENT;¶
The per-piece linear CCD inside a piecewise driver (e.g., NonlinearCCD), which supplies its own conservative margins (a target separation inflated by the linearization error as the minimum separation, and subdivision on zero TOI).
The method skips its standalone strategy and returns the raw time of impact.
- enumerator COMPONENT_NO_ZERO_TOI;¶
Like COMPONENT, but the caller cannot accept a time of impact of exactly zero (it knows the start of the piece is separated).
Public Functions¶
- NarrowPhaseCCD() = default;¶
- virtual ~NarrowPhaseCCD() = default;¶
-
virtual bool point_point_ccd(Eigen::ConstRef<VectorMax3d> p0_t0,
Eigen::ConstRef<VectorMax3d> p1_t0,
Eigen::ConstRef<VectorMax3d> p0_t1,
Eigen::ConstRef<VectorMax3d> p1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const Mode mode = Mode::STANDALONE) const
= 0;¶ Perform narrow phase CCD between two points.
- Parameters:¶
- Eigen::ConstRef<VectorMax3d> p0_t0¶
The starting position of the first point.
- Eigen::ConstRef<VectorMax3d> p1_t0¶
The starting position of the second point.
- Eigen::ConstRef<VectorMax3d> p0_t1¶
The ending position of the first point.
- Eigen::ConstRef<VectorMax3d> p1_t1¶
The ending position of the second point.
- double &toi¶
The time of impact.
- const double min_distance = 0.0¶
The minimum distance between the two points.
- const double tmax = 1.0¶
The maximum time to check for collision.
- const Mode mode = Mode::STANDALONE¶
How the query is used (see Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool point_edge_ccd(Eigen::ConstRef<VectorMax3d> p_t0,
Eigen::ConstRef<VectorMax3d> e0_t0,
Eigen::ConstRef<VectorMax3d> e1_t0,
Eigen::ConstRef<VectorMax3d> p_t1,
Eigen::ConstRef<VectorMax3d> e0_t1,
Eigen::ConstRef<VectorMax3d> e1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const Mode mode = Mode::STANDALONE) const
= 0;¶ Perform narrow phase CCD between a point and a linear edge.
- Parameters:¶
- Eigen::ConstRef<VectorMax3d> p_t0¶
The starting position of the point.
- Eigen::ConstRef<VectorMax3d> e0_t0¶
The starting position of the first endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> e1_t0¶
The starting position of the second endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> p_t1¶
The ending position of the point.
- Eigen::ConstRef<VectorMax3d> e0_t1¶
The ending position of the first endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> e1_t1¶
The ending position of the second endpoint of the edge.
- double &toi¶
The time of impact.
- const double min_distance = 0.0¶
The minimum distance between the point and the edge.
- const double tmax = 1.0¶
The maximum time to check for collision.
- const Mode mode = Mode::STANDALONE¶
How the query is used (see Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool point_triangle_ccd(
Eigen::ConstRef<Eigen::Vector3d> p_t0,
Eigen::ConstRef<Eigen::Vector3d> t0_t0,
Eigen::ConstRef<Eigen::Vector3d> t1_t0,
Eigen::ConstRef<Eigen::Vector3d> t2_t0,
Eigen::ConstRef<Eigen::Vector3d> p_t1,
Eigen::ConstRef<Eigen::Vector3d> t0_t1,
Eigen::ConstRef<Eigen::Vector3d> t1_t1,
Eigen::ConstRef<Eigen::Vector3d> t2_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const Mode mode = Mode::STANDALONE) const
= 0;¶ Perform narrow phase CCD between a point and a linear triangle.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector3d> p_t0¶
The starting position of the point.
- Eigen::ConstRef<Eigen::Vector3d> t0_t0¶
The starting position of the first vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t1_t0¶
The starting position of the second vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t2_t0¶
The starting position of the third vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> p_t1¶
The ending position of the point.
- Eigen::ConstRef<Eigen::Vector3d> t0_t1¶
The ending position of the first vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t1_t1¶
The ending position of the second vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t2_t1¶
The ending position of the third vertex of the triangle.
- double &toi¶
The time of impact.
- const double min_distance = 0.0¶
The minimum distance between the point and the triangle.
- const double tmax = 1.0¶
The maximum time to check for collision.
- const Mode mode = Mode::STANDALONE¶
How the query is used (see Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool edge_edge_ccd(Eigen::ConstRef<Eigen::Vector3d> ea0_t0,
Eigen::ConstRef<Eigen::Vector3d> ea1_t0,
Eigen::ConstRef<Eigen::Vector3d> eb0_t0,
Eigen::ConstRef<Eigen::Vector3d> eb1_t0,
Eigen::ConstRef<Eigen::Vector3d> ea0_t1,
Eigen::ConstRef<Eigen::Vector3d> ea1_t1,
Eigen::ConstRef<Eigen::Vector3d> eb0_t1,
Eigen::ConstRef<Eigen::Vector3d> eb1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const Mode mode = Mode::STANDALONE) const
= 0;¶ Perform narrow phase CCD between two linear edges.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector3d> ea0_t0¶
The starting position of the first edge’s first endpoint.
- Eigen::ConstRef<Eigen::Vector3d> ea1_t0¶
The starting position of the first edge’s second endpoint.
- Eigen::ConstRef<Eigen::Vector3d> eb0_t0¶
The starting position of the second edge’s first endpoint.
- Eigen::ConstRef<Eigen::Vector3d> eb1_t0¶
The starting position of the second edge’s second endpoint.
- Eigen::ConstRef<Eigen::Vector3d> ea0_t1¶
The ending position of the first edge’s first endpoint.
- Eigen::ConstRef<Eigen::Vector3d> ea1_t1¶
The ending position of the first edge’s second endpoint.
- Eigen::ConstRef<Eigen::Vector3d> eb0_t1¶
The ending position of the second edge’s first endpoint.
- Eigen::ConstRef<Eigen::Vector3d> eb1_t1¶
The ending position of the second edge’s second endpoint.
- double &toi¶
The time of impact.
- const double min_distance = 0.0¶
The minimum distance between the two edges.
- const double tmax = 1.0¶
The maximum time to check for collision.
- const Mode mode = Mode::STANDALONE¶
How the query is used (see Mode).
- Returns:¶
True if a collision was detected, false otherwise.
Public Members¶
- double conservative_rescaling;¶
The conservative rescaling value used to avoid taking steps exactly to impact.
This is used to creat a effective minimum distance between objects, which can help prevent numerical issues when objects are very close to each other.
I.e., min_effective_distance = (1.0 - conservative_rescaling) * (initial_distance - min_distance)
If the time of impact is small (e.g. 1e-6), then the CCD will be rerun without a effective minimum distance to try to get a more accurate time of impact. In this case, the conservative rescaling will be used to scale the time of impact to avoid taking steps exactly to impact.
- enum class ipc::NarrowPhaseCCD::Mode : uint8_t;
How a narrow-phase CCD query is used.
Values:
- enumerator STANDALONE;
A standalone query: the method applies its own conservative strategy (minimum-distance inflation, small-TOI reruns, and rescaling).
- enumerator COMPONENT;
The per-piece linear CCD inside a piecewise driver (e.g., NonlinearCCD), which supplies its own conservative margins (a target separation inflated by the linearization error as the minimum separation, and subdivision on zero TOI).
The method skips its standalone strategy and returns the raw time of impact.
- enumerator COMPONENT_NO_ZERO_TOI;
Like COMPONENT, but the caller cannot accept a time of impact of exactly zero (it knows the start of the piece is separated).
Tight Inclusion CCD¶
- class TightInclusionCCD : public ipc::NarrowPhaseCCD;¶
Inheritance diagram for ipc::TightInclusionCCD:
Tight-Inclusion Continuous Collision Detection (CCD) algorithm.
Public Functions¶
-
explicit TightInclusionCCD(
const double tolerance = DEFAULT_TOLERANCE,
const long max_iterations = DEFAULT_MAX_ITERATIONS,
const double conservative_rescaling
= DEFAULT_CONSERVATIVE_RESCALING);¶ Construct a new AdditiveCCD object.
- Parameters:¶
- const double tolerance = DEFAULT_TOLERANCE¶
The tolerance used for the CCD algorithm.
- const long max_iterations = DEFAULT_MAX_ITERATIONS¶
The maximum number of iterations for the CCD algorithm.
- const double conservative_rescaling = DEFAULT_CONSERVATIVE_RESCALING¶
The conservative rescaling value used to avoid taking steps exactly to impact.
-
virtual bool point_point_ccd(Eigen::ConstRef<VectorMax3d> p0_t0,
Eigen::ConstRef<VectorMax3d> p1_t0,
Eigen::ConstRef<VectorMax3d> p0_t1,
Eigen::ConstRef<VectorMax3d> p1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const override;¶ Computes the time of impact between two points using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<VectorMax3d> p0_t0¶
[in] The initial position of the first point.
- Eigen::ConstRef<VectorMax3d> p1_t0¶
[in] The initial position of the second point.
- Eigen::ConstRef<VectorMax3d> p0_t1¶
[in] The final position of the first point.
- Eigen::ConstRef<VectorMax3d> p1_t1¶
[in] The final position of the second point.
- double &toi¶
[out] The time of impact between the two points.
- const double min_distance = 0.0¶
[in] The minimum distance between the points.
- const double tmax = 1.0¶
[in] The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
[in] How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool point_edge_ccd(Eigen::ConstRef<VectorMax3d> p_t0,
Eigen::ConstRef<VectorMax3d> e0_t0,
Eigen::ConstRef<VectorMax3d> e1_t0,
Eigen::ConstRef<VectorMax3d> p_t1,
Eigen::ConstRef<VectorMax3d> e0_t1,
Eigen::ConstRef<VectorMax3d> e1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const override;¶ Computes the time of impact between a point and an edge using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<VectorMax3d> p_t0¶
[in] The initial position of the point.
- Eigen::ConstRef<VectorMax3d> e0_t0¶
[in] The initial position of the first endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> e1_t0¶
[in] The initial position of the second endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> p_t1¶
[in] The final position of the point.
- Eigen::ConstRef<VectorMax3d> e0_t1¶
[in] The final position of the first endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> e1_t1¶
[in] The final position of the second endpoint of the edge.
- double &toi¶
[out] The time of impact between the point and the edge.
- const double min_distance = 0.0¶
[in] The minimum distance between the objects.
- const double tmax = 1.0¶
[in] The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
[in] How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool edge_edge_ccd(Eigen::ConstRef<Eigen::Vector3d> ea0_t0,
Eigen::ConstRef<Eigen::Vector3d> ea1_t0,
Eigen::ConstRef<Eigen::Vector3d> eb0_t0,
Eigen::ConstRef<Eigen::Vector3d> eb1_t0,
Eigen::ConstRef<Eigen::Vector3d> ea0_t1,
Eigen::ConstRef<Eigen::Vector3d> ea1_t1,
Eigen::ConstRef<Eigen::Vector3d> eb0_t1,
Eigen::ConstRef<Eigen::Vector3d> eb1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const override;¶ Computes the time of impact between two edges in 3D using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector3d> ea0_t0¶
[in] The initial position of the first endpoint of the first edge.
- Eigen::ConstRef<Eigen::Vector3d> ea1_t0¶
[in] The initial position of the second endpoint of the first edge.
- Eigen::ConstRef<Eigen::Vector3d> eb0_t0¶
[in] The initial position of the first endpoint of the second edge.
- Eigen::ConstRef<Eigen::Vector3d> eb1_t0¶
[in] The initial position of the second endpoint of the second edge.
- Eigen::ConstRef<Eigen::Vector3d> ea0_t1¶
[in] The final position of the first endpoint of the first edge.
- Eigen::ConstRef<Eigen::Vector3d> ea1_t1¶
[in] The final position of the second endpoint of the first edge.
- Eigen::ConstRef<Eigen::Vector3d> eb0_t1¶
[in] The final position of the first endpoint of the second edge.
- Eigen::ConstRef<Eigen::Vector3d> eb1_t1¶
[in] The final position of the second endpoint of the second edge.
- double &toi¶
[out] The time of impact between the two edges.
- const double min_distance = 0.0¶
[in] The minimum distance between the objects.
- const double tmax = 1.0¶
[in] The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
[in] How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool point_triangle_ccd(
Eigen::ConstRef<Eigen::Vector3d> p_t0,
Eigen::ConstRef<Eigen::Vector3d> t0_t0,
Eigen::ConstRef<Eigen::Vector3d> t1_t0,
Eigen::ConstRef<Eigen::Vector3d> t2_t0,
Eigen::ConstRef<Eigen::Vector3d> p_t1,
Eigen::ConstRef<Eigen::Vector3d> t0_t1,
Eigen::ConstRef<Eigen::Vector3d> t1_t1,
Eigen::ConstRef<Eigen::Vector3d> t2_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const override;¶ Computes the time of impact between a point and a triangle in 3D using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector3d> p_t0¶
[in] The initial position of the point.
- Eigen::ConstRef<Eigen::Vector3d> t0_t0¶
[in] The initial position of the first vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t1_t0¶
[in] The initial position of the second vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t2_t0¶
[in] The initial position of the third vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> p_t1¶
[in] The final position of the point.
- Eigen::ConstRef<Eigen::Vector3d> t0_t1¶
[in] The final position of the first vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t1_t1¶
[in] The final position of the second vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t2_t1¶
[in] The final position of the third vertex of the triangle.
- double &toi¶
[out] The time of impact between the point and the triangle.
- const double min_distance = 0.0¶
[in] The minimum distance between the objects.
- const double tmax = 1.0¶
[in] The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
[in] How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
Public Members¶
- double tolerance;¶
Solver tolerance.
- long max_iterations;¶
Maximum number of iterations.
Public Static Attributes¶
- static constexpr double DEFAULT_TOLERANCE = 1e-6;¶
The default tolerance used with Tight-Inclusion CCD.
- static constexpr long DEFAULT_MAX_ITERATIONS = 10'000'000L;¶
The default maximum number of iterations used with Tight-Inclusion CCD.
- static constexpr double DEFAULT_CONSERVATIVE_RESCALING = 0.8;¶
The default conservative rescaling value used to avoid taking steps exactly to impact.
- static constexpr double SMALL_TOI = 1e-6;¶
Tolerance for small time of impact which triggers rerunning CCD without a minimum separation.
Private Functions¶
-
bool point_point_ccd_3D(Eigen::ConstRef<Eigen::Vector3d> p0_t0,
Eigen::ConstRef<Eigen::Vector3d> p1_t0,
Eigen::ConstRef<Eigen::Vector3d> p0_t1,
Eigen::ConstRef<Eigen::Vector3d> p1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const;¶ Computes the time of impact between two points in 3D using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector3d> p0_t0¶
[in] The initial position of the first point.
- Eigen::ConstRef<Eigen::Vector3d> p1_t0¶
[in] The initial position of the second point.
- Eigen::ConstRef<Eigen::Vector3d> p0_t1¶
[in] The final position of the first point.
- Eigen::ConstRef<Eigen::Vector3d> p1_t1¶
[in] The final position of the second point.
- double &toi¶
[out] The time of impact between the two points.
- const double min_distance = 0.0¶
[in] The minimum distance between the objects.
- const double tmax = 1.0¶
[in] The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
[in] How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
bool point_edge_ccd_3D(Eigen::ConstRef<Eigen::Vector3d> p_t0,
Eigen::ConstRef<Eigen::Vector3d> e0_t0,
Eigen::ConstRef<Eigen::Vector3d> e1_t0,
Eigen::ConstRef<Eigen::Vector3d> p_t1,
Eigen::ConstRef<Eigen::Vector3d> e0_t1,
Eigen::ConstRef<Eigen::Vector3d> e1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const;¶ Computes the time of impact between a point and an edge in 3D using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector3d> p_t0¶
[in] The initial position of the point.
- Eigen::ConstRef<Eigen::Vector3d> e0_t0¶
[in] The initial position of the first endpoint of the edge.
- Eigen::ConstRef<Eigen::Vector3d> e1_t0¶
[in] The initial position of the second endpoint of the edge.
- Eigen::ConstRef<Eigen::Vector3d> p_t1¶
[in] The final position of the point.
- Eigen::ConstRef<Eigen::Vector3d> e0_t1¶
[in] The final position of the first endpoint of the edge.
- Eigen::ConstRef<Eigen::Vector3d> e1_t1¶
[in] The final position of the second endpoint of the edge.
- double &toi¶
[out] The time of impact between the point and the edge.
- const double min_distance = 0.0¶
[in] The minimum distance between the objects.
- const double tmax = 1.0¶
[in] The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
[in] How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
Private Static Functions¶
-
static bool ccd_strategy(
const std::function<bool(double, bool, double&)>& ccd,
const double min_distance, const double initial_distance,
const double conservative_rescaling, double& toi,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE);¶ Perform the CCD strategy outlined by Li et al.
[2020].
- Parameters:¶
- const std::function<bool(double, bool, double&)> &ccd¶
[in] The continuous collision detection function.
- const double min_distance¶
[in] The minimum distance between the objects.
- const double initial_distance¶
[in] The initial distance between the objects.
- const double conservative_rescaling¶
[in] The conservative rescaling of the time of impact.
- double &toi¶
[out] Output time of impact.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
[in] How the query is used. Outside STANDALONE the strategy is skipped and ccd runs once with min_distance.
- Returns:¶
True if a collision was detected, false otherwise.
-
explicit TightInclusionCCD(
Additive CCD¶
- class AdditiveCCD : public ipc::NarrowPhaseCCD;¶
Inheritance diagram for ipc::AdditiveCCD:
Additive Continuous Collision Detection (CCD) from [Li et al. 2021].
Public Functions¶
-
explicit AdditiveCCD(
const long max_iterations = UNLIMITTED_ITERATIONS,
const double conservative_rescaling
= DEFAULT_CONSERVATIVE_RESCALING);¶ Construct a new AdditiveCCD object.
- Parameters:¶
- const long max_iterations = UNLIMITTED_ITERATIONS¶
The maximum number of iterations to use for the CCD algorithm. If set to UNLIMITTED_ITERATIONS, the algorithm will run until it converges.
- const double conservative_rescaling = DEFAULT_CONSERVATIVE_RESCALING¶
The conservative rescaling value used to avoid taking steps exactly to impact.
-
virtual bool point_point_ccd(Eigen::ConstRef<VectorMax3d> p0_t0,
Eigen::ConstRef<VectorMax3d> p1_t0,
Eigen::ConstRef<VectorMax3d> p0_t1,
Eigen::ConstRef<VectorMax3d> p1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const override;¶ Computes the time of impact between two points using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<VectorMax3d> p0_t0¶
The initial position of the first point.
- Eigen::ConstRef<VectorMax3d> p1_t0¶
The initial position of the second point.
- Eigen::ConstRef<VectorMax3d> p0_t1¶
The final position of the first point.
- Eigen::ConstRef<VectorMax3d> p1_t1¶
The final position of the second point.
- double &toi¶
[out] The time of impact between the two points.
- const double min_distance = 0.0¶
The minimum distance between two objects.
- const double tmax = 1.0¶
The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool point_edge_ccd(Eigen::ConstRef<VectorMax3d> p_t0,
Eigen::ConstRef<VectorMax3d> e0_t0,
Eigen::ConstRef<VectorMax3d> e1_t0,
Eigen::ConstRef<VectorMax3d> p_t1,
Eigen::ConstRef<VectorMax3d> e0_t1,
Eigen::ConstRef<VectorMax3d> e1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const override;¶ Computes the time of impact between a point and an edge using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<VectorMax3d> p_t0¶
The initial position of the point.
- Eigen::ConstRef<VectorMax3d> e0_t0¶
The initial position of the first endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> e1_t0¶
The initial position of the second endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> p_t1¶
The final position of the point.
- Eigen::ConstRef<VectorMax3d> e0_t1¶
The final position of the first endpoint of the edge.
- Eigen::ConstRef<VectorMax3d> e1_t1¶
The final position of the second endpoint of the edge.
- double &toi¶
[out] The time of impact between the point and the edge.
- const double min_distance = 0.0¶
The minimum distance between two objects.
- const double tmax = 1.0¶
The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool point_triangle_ccd(
Eigen::ConstRef<Eigen::Vector3d> p_t0,
Eigen::ConstRef<Eigen::Vector3d> t0_t0,
Eigen::ConstRef<Eigen::Vector3d> t1_t0,
Eigen::ConstRef<Eigen::Vector3d> t2_t0,
Eigen::ConstRef<Eigen::Vector3d> p_t1,
Eigen::ConstRef<Eigen::Vector3d> t0_t1,
Eigen::ConstRef<Eigen::Vector3d> t1_t1,
Eigen::ConstRef<Eigen::Vector3d> t2_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const override;¶ Computes the time of impact between a point and a triangle using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector3d> p_t0¶
The initial position of the point.
- Eigen::ConstRef<Eigen::Vector3d> t0_t0¶
The initial position of the first vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t1_t0¶
The initial position of the second vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t2_t0¶
The initial position of the third vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> p_t1¶
The final position of the point.
- Eigen::ConstRef<Eigen::Vector3d> t0_t1¶
The final position of the first vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t1_t1¶
The final position of the second vertex of the triangle.
- Eigen::ConstRef<Eigen::Vector3d> t2_t1¶
The final position of the third vertex of the triangle.
- double &toi¶
[out] The time of impact between the point and the triangle.
- const double min_distance = 0.0¶
The minimum distance between two objects.
- const double tmax = 1.0¶
The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
virtual bool edge_edge_ccd(Eigen::ConstRef<Eigen::Vector3d> ea0_t0,
Eigen::ConstRef<Eigen::Vector3d> ea1_t0,
Eigen::ConstRef<Eigen::Vector3d> eb0_t0,
Eigen::ConstRef<Eigen::Vector3d> eb1_t0,
Eigen::ConstRef<Eigen::Vector3d> ea0_t1,
Eigen::ConstRef<Eigen::Vector3d> ea1_t1,
Eigen::ConstRef<Eigen::Vector3d> eb0_t1,
Eigen::ConstRef<Eigen::Vector3d> eb1_t1, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const override;¶ Computes the time of impact between two edges using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector3d> ea0_t0¶
The initial position of the first endpoint of the first edge.
- Eigen::ConstRef<Eigen::Vector3d> ea1_t0¶
The initial position of the second endpoint of the first edge.
- Eigen::ConstRef<Eigen::Vector3d> eb0_t0¶
The initial position of the first endpoint of the second edge.
- Eigen::ConstRef<Eigen::Vector3d> eb1_t0¶
The initial position of the second endpoint of the second edge.
- Eigen::ConstRef<Eigen::Vector3d> ea0_t1¶
The final position of the first endpoint of the first edge.
- Eigen::ConstRef<Eigen::Vector3d> ea1_t1¶
The final position of the second endpoint of the first edge.
- Eigen::ConstRef<Eigen::Vector3d> eb0_t1¶
The final position of the first endpoint of the second edge.
- Eigen::ConstRef<Eigen::Vector3d> eb1_t1¶
The final position of the second endpoint of the second edge.
- double &toi¶
[out] The time of impact between the two edges.
- const double min_distance = 0.0¶
The minimum distance between two objects.
- const double tmax = 1.0¶
The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
Public Static Attributes¶
- static constexpr long DEFAULT_MAX_ITERATIONS = 10'000'000L;¶
The default maximum number of iterations used with Tight-Inclusion CCD.
- static constexpr long UNLIMITTED_ITERATIONS = -1;¶
Unlimitted number of iterations.
- static constexpr double DEFAULT_CONSERVATIVE_RESCALING = 0.9;¶
The default conservative rescaling value used to avoid taking steps exactly to impact.
Value choosen to based on [Li et al. 2021].
- static constexpr double COMPONENT_CONSERVATIVE_RESCALING = 0.99;¶
The conservative rescaling used for component queries (see NarrowPhaseCCD::Mode::COMPONENT).
Additive CCD terminates by advancing until the remaining gap shrinks to (1 - conservative_rescaling) times the initial gap, so a truly raw TOI (rescaling -> 1) never terminates and values above 0.99 behave badly; 0.99 is as raw as it can safely get. Component queries ignore the member value in favor of this.
Private Functions¶
-
bool handle_initial_proximity(const double initial_distance_sq,
double& min_distance, const NarrowPhaseCCD::Mode mode,
double& toi) const;¶ Handle a query whose initial distance is within the minimum separation.
For COMPONENT_NO_ZERO_TOI queries with a positive initial distance, the minimum separation is halved until the initial distance clears it, trading separation margin for a positive TOI (mirroring Tight Inclusion’s small-TOI rerun). Otherwise this reports toi = 0, at trace level for COMPONENT queries (the piecewise driver handles it by subdividing) and at warn level for STANDALONE queries.
- Parameters:¶
- const double initial_distance_sq¶
The squared initial distance between the objects.
- double &min_distance¶
[inout] The minimum separation (possibly reduced).
- const NarrowPhaseCCD::Mode mode¶
How the query is used (see NarrowPhaseCCD::Mode).
- double &toi¶
[out] Set to 0 when returning true.
- Returns:¶
True if the query should return early (toi = 0), false to continue.
-
template <typename DistanceSqrFunc>
bool additive_ccd(VectorMax12d x, Eigen::ConstRef<VectorMax12d> dx,
const DistanceSqrFunc& distance_squared,
const double max_disp_mag, double& toi,
const double min_distance = 0.0, const double tmax = 1.0,
const NarrowPhaseCCD::Mode mode
= NarrowPhaseCCD::Mode::STANDALONE) const;¶ Computes the time of impact between two objects using additive continuous collision detection.
- Parameters:¶
- VectorMax12d x¶
Initial positions
- Eigen::ConstRef<VectorMax12d> dx¶
Displacements
- const DistanceSqrFunc &distance_squared¶
A function that computes the squared distance between the two objects at a given time.
- const double max_disp_mag¶
The maximum displacement magnitude.
- double &toi¶
[out] The time of impact between the two objects.
- const double min_distance = 0.0¶
The minimum distance between the objects.
- const double tmax = 1.0¶
The maximum time to check for collisions.
- const NarrowPhaseCCD::Mode mode = NarrowPhaseCCD::Mode::STANDALONE¶
How the query is used (see NarrowPhaseCCD::Mode).
- Returns:¶
True if a collision was detected, false otherwise.
-
explicit AdditiveCCD(
Inexact CCD¶
Note
This method is disabled by default. To enable it, set the
IPC_TOOLKIT_WITH_INEXACT_CCD CMake option to ON.
-
bool ipc::inexact_point_edge_ccd_2D(
Eigen::ConstRef<Eigen::Vector2d> p_t0,
Eigen::ConstRef<Eigen::Vector2d> e0_t0,
Eigen::ConstRef<Eigen::Vector2d> e1_t0,
Eigen::ConstRef<Eigen::Vector2d> p_t1,
Eigen::ConstRef<Eigen::Vector2d> e0_t1,
Eigen::ConstRef<Eigen::Vector2d> e1_t1, double& toi,
const double conservative_rescaling);¶ Inexact continuous collision detection between a point and an edge in 2D.
- Parameters:¶
- Eigen::ConstRef<Eigen::Vector2d> p_t0¶
[in] The initial position of the point.
- Eigen::ConstRef<Eigen::Vector2d> e0_t0¶
[in] The initial position of the first endpoint of the edge.
- Eigen::ConstRef<Eigen::Vector2d> e1_t0¶
[in] The initial position of the second endpoint of the edge.
- Eigen::ConstRef<Eigen::Vector2d> p_t1¶
[in] The final position of the point.
- Eigen::ConstRef<Eigen::Vector2d> e0_t1¶
[in] The final position of the first endpoint of the edge.
- Eigen::ConstRef<Eigen::Vector2d> e1_t1¶
[in] The final position of the second endpoint of the edge.
- double &toi¶
[out] Output time of impact.
- const double conservative_rescaling¶
[in] The conservative rescaling of the time of impact.
- Returns:¶
True if a collision was detected, false otherwise.
Nonlinear CCD¶
- class NonlinearTrajectory;¶
Inheritance diagram for ipc::NonlinearTrajectory:
A nonlinear trajectory is a function that maps time to a point in space.
Subclassed by ipc::IntervalNonlinearTrajectory
Public Functions¶
- virtual ~NonlinearTrajectory() = default;¶
- virtual VectorMax3d operator()(const double t) const = 0;¶
Compute the point’s position at time t.
-
class IntervalNonlinearTrajectory
: public virtual ipc::NonlinearTrajectory;¶ Inheritance diagram for ipc::IntervalNonlinearTrajectory:
A nonlinear trajectory with an implementation of the max_distance_from_linear function using interval arithmetic.
Public Functions¶
- virtual ~IntervalNonlinearTrajectory() = default;¶
- virtual VectorMax3I operator()(const filib::Interval& t) const = 0;¶
Compute the point’s position over a time interval t.
-
virtual double max_distance_from_linear(
const double t0, const double t1) const;¶ Compute the maximum distance from the nonlinear trajectory to a linearized trajectory.
Note
This uses interval arithmetic to compute the maximum distance. If you know a tighter bound on the maximum distance, it is recommended to override this function.
- virtual VectorMax3d operator()(const double t) const = 0;¶
Compute the point’s position at time t.
- class NonlinearCCD;¶
Public Functions¶
Construct a new NonlinearCCD object.
The narrow-phase CCD used for the per-piece linear CCD (if null, a default-constructed TightInclusionCCD is used). Each per-piece query is made with a COMPONENT NarrowPhaseCCD::Mode, so the object is not modified and may be shared with standalone users.
Fraction of the initial gap (above min_distance) a step may close: the CCD reports an impact once the distance shrinks to min_distance + (1 - conservative_rescaling) * (d₀ - min_distance).
-
explicit NonlinearCCD(const double tolerance,
const long max_iterations = DEFAULT_MAX_ITERATIONS,
const double conservative_rescaling
= DEFAULT_CONSERVATIVE_RESCALING);¶ Construct a NonlinearCCD whose per-piece CCD is a TightInclusionCCD.
- Deprecated :;
Use NonlinearCCD(std::make_shared<TightInclusionCCD>(tolerance, max_iterations), conservative_rescaling).
- Parameters:¶
- const double tolerance¶
Tight Inclusion’s solver tolerance.
- const long max_iterations = DEFAULT_MAX_ITERATIONS¶
Tight Inclusion’s maximum number of iterations.
- const double conservative_rescaling = DEFAULT_CONSERVATIVE_RESCALING¶
Fraction of the initial gap (above min_distance) a step may close: the CCD reports an impact once the distance shrinks to min_distance + (1 - conservative_rescaling) * (d₀ - min_distance).
- virtual ~NonlinearCCD() = default;¶
-
virtual bool point_point_ccd(const NonlinearTrajectory& p0,
const NonlinearTrajectory& p1, double& toi,
const double min_distance = 0, const double tmax = 1.0) const;¶ Perform nonlinear CCD between two points moving along nonlinear trajectories.
- Parameters:¶
- const NonlinearTrajectory &p0¶
[in] First point’s trajectory
- const NonlinearTrajectory &p1¶
[in] Second point’s trajectory
- double &toi¶
[out] Output time of impact
- const double min_distance = 0¶
[in] Minimum separation distance between the two points
- const double tmax = 1.0¶
[in] Maximum time to check for collision
- Returns:¶
True if the two points collide, false otherwise.
-
virtual bool point_edge_ccd(const NonlinearTrajectory& p,
const NonlinearTrajectory& e0, const NonlinearTrajectory& e1,
double& toi, const double min_distance = 0,
const double tmax = 1.0) const;¶ Perform nonlinear CCD between a point and a linear edge moving along nonlinear trajectories.
- Parameters:¶
- const NonlinearTrajectory &p¶
[in] Point’s trajectory
- const NonlinearTrajectory &e0¶
[in] Edge’s first endpoint’s trajectory
- const NonlinearTrajectory &e1¶
[in] Edge’s second endpoint’s trajectory
- double &toi¶
[out] Output time of impact
- const double min_distance = 0¶
[in] Minimum separation distance between the point and the edge
- const double tmax = 1.0¶
[in] Maximum time to check for collision
- Returns:¶
True if the point and edge collide, false otherwise.
-
virtual bool edge_edge_ccd(const NonlinearTrajectory& ea0,
const NonlinearTrajectory& ea1, const NonlinearTrajectory& eb0,
const NonlinearTrajectory& eb1, double& toi,
const double min_distance = 0, const double tmax = 1.0) const;¶ Perform nonlinear CCD between two linear edges moving along nonlinear trajectories.
- Parameters:¶
- const NonlinearTrajectory &ea0¶
[in] First edge’s first endpoint’s trajectory
- const NonlinearTrajectory &ea1¶
[in] First edge’s second endpoint’s trajectory
- const NonlinearTrajectory &eb0¶
[in] Second edge’s first endpoint’s trajectory
- const NonlinearTrajectory &eb1¶
[in] Second edge’s second endpoint’s trajectory
- double &toi¶
[out] Output time of impact
- const double min_distance = 0¶
[in] Minimum separation distance between the two edges
- const double tmax = 1.0¶
[in] Maximum time to check for collision
- Returns:¶
True if the two edges collide, false otherwise.
-
virtual bool point_triangle_ccd(const NonlinearTrajectory& p,
const NonlinearTrajectory& t0, const NonlinearTrajectory& t1,
const NonlinearTrajectory& t2, double& toi,
const double min_distance = 0.0, const double tmax = 1.0) const;¶ Perform nonlinear CCD between a point and a linear triangle moving along nonlinear trajectories.
- Parameters:¶
- const NonlinearTrajectory &p¶
[in] Point’s trajectory
- const NonlinearTrajectory &t0¶
[in] Triangle’s first vertex’s trajectory
- const NonlinearTrajectory &t1¶
[in] Triangle’s second vertex’s trajectory
- const NonlinearTrajectory &t2¶
[in] Triangle’s third vertex’s trajectory
- double &toi¶
[out] Output time of impact
- const double min_distance = 0.0¶
[in] Minimum separation distance between the two edges
- const double tmax = 1.0¶
[in] Maximum time to check for collision
- Returns:¶
True if the point and triangle collide, false otherwise.
Set the narrow-phase CCD used for the per-piece linear CCD.
The narrow-phase CCD to use (if null, a default-constructed TightInclusionCCD is used).
-
inline std::shared_ptr<const NarrowPhaseCCD>
narrow_phase_ccd() const;¶ The narrow-phase CCD used for the per-piece linear CCD (never null).
Public Members¶
- double conservative_rescaling;¶
Fraction of the initial gap (above min_distance) a step may close: the CCD reports an impact once the distance shrinks to min_distance + (1 - conservative_rescaling) * (d₀ - min_distance).
Public Static Functions¶
-
static bool conservative_piecewise_linear_ccd(
const std::function<double(const double)>& distance,
const std::function<double(const double, const double)>&
max_distance_from_linear,
const std::function<bool(const double, const double,
const double, const bool, double&)>& linear_ccd,
double& toi, const double min_distance = 0,
const double tmax = 1.0,
const double conservative_rescaling
= DEFAULT_CONSERVATIVE_RESCALING);¶ Perform conservative piecewise linear CCD of a nonlinear trajectories.
- Parameters:¶
- const std::function<double(const double)> &distance¶
[in] Return the distance for a given time in [0, 1].
- const std::function<double(const double, const double)> &max_distance_from_linear¶
[in] Return the maximum distance from the linearized trajectory for a given time interval.
- const std::function<bool(const double, const double, const double, const bool, double&)> &linear_ccd¶
[in] Perform linear CCD on a given time interval. Receives the piece interval, the target separation inflated by the piece’s linearization error, and a no_zero_toi flag (true on the first piece, whose start is known to be more than min_distance apart).
- double &toi¶
[out] Output time of impact.
- const double min_distance = 0¶
[in] Minimum separation distance between the objects.
- const double tmax = 1.0¶
[in] Maximum time to check for collision.
- const double conservative_rescaling = DEFAULT_CONSERVATIVE_RESCALING¶
[in] Fraction of the initial gap (above min_distance) a step may close: the CCD reports an impact once the distance shrinks to min_distance + (1 - conservative_rescaling) * (d₀ - min_distance).
- Returns:¶
True if a collision was detected, false otherwise.
Public Static Attributes¶
- static constexpr double DEFAULT_TOLERANCE = 1e-6;¶
The default tolerance of the TightInclusionCCD built by the deprecated (tolerance, max_iterations) constructor.
- static constexpr long DEFAULT_MAX_ITERATIONS = 10'000'000L;¶
The default maximum number of iterations of the TightInclusionCCD built by the deprecated (tolerance, max_iterations) constructor.
- static constexpr double DEFAULT_CONSERVATIVE_RESCALING = 0.8;¶
The default conservative rescaling, which keeps 20% of the initial gap so steps never go exactly to impact.
Private Members¶
- std::shared_ptr<const NarrowPhaseCCD> m_narrow_phase_ccd;¶
The narrow-phase CCD used for the per-piece linear CCD (never null).
Note
The piecewise driver passes each piece’s linearization error as the minimum separation distance, so the narrow phase must support minimum separation (both TightInclusionCCD and AdditiveCCD do).
Miscellaneous¶
-
bool ipc::point_static_plane_ccd(Eigen::ConstRef<VectorMax3d> p_t0,
Eigen::ConstRef<VectorMax3d> p_t1,
Eigen::ConstRef<VectorMax3d> plane_origin,
Eigen::ConstRef<VectorMax3d> plane_normal, double& toi,
const double conservative_rescaling
= TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING);¶ Computes the time of impact between a point and a static plane in 3D using continuous collision detection.
- Parameters:¶
- Eigen::ConstRef<VectorMax3d> p_t0¶
[in] The initial position of the point.
- Eigen::ConstRef<VectorMax3d> p_t1¶
[in] The final position of the point.
- Eigen::ConstRef<VectorMax3d> plane_origin¶
[in] The origin of the plane.
- Eigen::ConstRef<VectorMax3d> plane_normal¶
[in] The normal of the plane.
- double &toi¶
[out] Output time of impact.
- const double conservative_rescaling = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING¶
[in] Conservative rescaling of the time of impact.
- Returns:¶
True if a collision was detected, false otherwise.