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 double min_distance = 0.0,
    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 double min_distance = 0.0¶: The minimum distance allowable between any two elements.
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 double min_distance = 0.0,
    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 double min_distance = 0.0¶: The minimum distance allowable between any two elements.
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.

class NarrowPhaseCCD;¶

Inheritance diagram for ipc::NarrowPhaseCCD:

Narrow Phase Continuous Collision Detection (CCD) interface.

Subclassed by ipc::AdditiveCCD, ipc::TightInclusionCCD

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 = 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.

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 = 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.

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 = 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.

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 = 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.

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.

class TightInclusionCCD : public ipc::NarrowPhaseCCD;¶

Inheritance diagram for ipc::TightInclusionCCD:

Collaboration 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 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.

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 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.

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 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.

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 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.

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;¶

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.

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;¶

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.

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);¶

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.

Returns:¶

True if a collision was detected, false otherwise.

class AdditiveCCD : public ipc::NarrowPhaseCCD;¶

Inheritance diagram for ipc::AdditiveCCD:

Collaboration 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 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.

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 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.

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 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.

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 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.

Returns:¶

True if a collision was detected, false otherwise.

Public Members¶

long max_iterations;¶: Maximum number of iterations.

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].

Private Functions¶

bool additive_ccd(VectorMax12d x, Eigen::ConstRef<VectorMax12d> dx, const std::function<double(Eigen::ConstRef<VectorMax12d>)>& distance_squared, const double max_disp_mag, double& toi, const double min_distance = 0.0, const double tmax = 1.0) 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 std::function<double(Eigen::ConstRef<VectorMax12d>)> &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.

Returns:¶

True if a collision was detected, false otherwise.

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.

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.

virtual double max_distance_from_linear( const double t0, const double t1) const = 0;¶

Compute the maximum distance from the nonlinear trajectory to a linearized trajectory.

Parameters:¶

const double t0¶: [in] Start time of the trajectory
const double t1¶: [in] End time of the trajectory

class IntervalNonlinearTrajectory
    : public virtual ipc::NonlinearTrajectory;¶

Inheritance diagram for ipc::IntervalNonlinearTrajectory:

Collaboration 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.

Parameters:¶

const filib::Interval &t¶: [in] The time interval

Returns:¶

The point’s position at time t as an interval

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.

Parameters:¶

const double t0¶: [in] Start time of the trajectory
const double t1¶: [in] End time of the trajectory

Returns:¶

The maximum distance from the nonlinear trajectory to a linearized trajectory

class NonlinearCCD;¶

Public Functions¶

NonlinearCCD(const double tolerance = DEFAULT_TOLERANCE, const long max_iterations = DEFAULT_MAX_ITERATIONS, const double conservative_rescaling = DEFAULT_CONSERVATIVE_RESCALING);¶

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.

Public Members¶

double tolerance;¶: Solver tolerance.

long max_iterations;¶: Maximum number of iterations.

double conservative_rescaling;¶: Conservative rescaling of the time of impact.

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.
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] Conservative rescaling of the time of impact.

Returns:¶

True if a collision was detected, false otherwise.

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.

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.

Continuous Collision Detection¶

Narrow Phase CCD¶

Tight Inclusion CCD¶

Additive CCD¶

Inexact CCD¶

Nonlinear CCD¶

Miscellaneous¶