Continuous Collision Detection¶

bool ipc::is_step_collision_free(const CollisionMesh& mesh,
    const Eigen::MatrixXd& vertices_t0,
    const Eigen::MatrixXd& vertices_t1,
    const double min_distance = 0.0,
    const BroadPhaseMethod broad_phase_method
    = DEFAULT_BROAD_PHASE_METHOD,
    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.

const Eigen::MatrixXd &vertices_t0¶

Surface vertex vertices at start as rows of a matrix.

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

const BroadPhaseMethod broad_phase_method = DEFAULT_BROAD_PHASE_METHOD¶

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, const Eigen::MatrixXd& vertices_t0,
    const Eigen::MatrixXd& vertices_t1,
    const double min_distance = 0.0,
    const BroadPhaseMethod broad_phase_method
    = DEFAULT_BROAD_PHASE_METHOD,
    const NarrowPhaseCCD& narrow_phase_ccd
    = DEFAULT_NARROW_PHASE_CCD)¶

Computes a maximal step size that is collision free.

Note

Assumes the trajectory is linear.

Parameters:¶

const CollisionMesh &mesh¶

The collision mesh.

const Eigen::MatrixXd &vertices_t0¶

Vertex vertices at start as rows of a matrix. Assumes vertices_t0 is intersection free.

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

const BroadPhaseMethod broad_phase_method = DEFAULT_BROAD_PHASE_METHOD¶

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.

Individual CCD Functions¶

Generic Interface¶

Additive CCD¶

Generic Interface¶

Nonlinear CCD¶

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

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.

Parameters:¶

const double t0¶

[in] Start time of the trajectory

const double t1¶

[in] End time of the trajectory

bool ipc::point_point_nonlinear_ccd(const NonlinearTrajectory& p0,
    const NonlinearTrajectory& p1, double& toi,
    const double tmax = 1.0, const double min_distance = 0,
    const double tolerance = TightInclusionCCD::DEFAULT_TOLERANCE,
    const long max_iterations
    = TightInclusionCCD::DEFAULT_MAX_ITERATIONS,
    const double conservative_rescaling
    = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING)¶

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 tmax = 1.0¶

[in] Maximum time to check for collision

const double min_distance = 0¶

[in] Minimum separation distance between the two points

const double tolerance = TightInclusionCCD::DEFAULT_TOLERANCE¶

[in] Tolerance for the linear CCD algorithm

const long max_iterations = TightInclusionCCD::DEFAULT_MAX_ITERATIONS¶

[in] Maximum number of iterations for the linear CCD algorithm

const double conservative_rescaling = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING¶

[in] Conservative rescaling of the time of impact

Returns:¶

True if the two points collide, false otherwise.

bool ipc::point_edge_nonlinear_ccd(const NonlinearTrajectory& p,
    const NonlinearTrajectory& e0, const NonlinearTrajectory& e1,
    double& toi, const double tmax = 1.0,
    const double min_distance = 0,
    const double tolerance = TightInclusionCCD::DEFAULT_TOLERANCE,
    const long max_iterations
    = TightInclusionCCD::DEFAULT_MAX_ITERATIONS,
    const double conservative_rescaling
    = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING)¶

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 tmax = 1.0¶

[in] Maximum time to check for collision

const double min_distance = 0¶

[in] Minimum separation distance between the point and the edge

const double tolerance = TightInclusionCCD::DEFAULT_TOLERANCE¶

[in] Tolerance for the linear CCD algorithm

const long max_iterations = TightInclusionCCD::DEFAULT_MAX_ITERATIONS¶

[in] Maximum number of iterations for the linear CCD algorithm

const double conservative_rescaling = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING¶

[in] Conservative rescaling of the time of impact

Returns:¶

True if the point and edge collide, false otherwise.

bool ipc::edge_edge_nonlinear_ccd(const NonlinearTrajectory& ea0,
    const NonlinearTrajectory& ea1, const NonlinearTrajectory& eb0,
    const NonlinearTrajectory& eb1, double& toi,
    const double tmax = 1.0, const double min_distance = 0,
    const double tolerance = TightInclusionCCD::DEFAULT_TOLERANCE,
    const long max_iterations
    = TightInclusionCCD::DEFAULT_MAX_ITERATIONS,
    const double conservative_rescaling
    = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING)¶

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 tmax = 1.0¶

[in] Maximum time to check for collision

const double min_distance = 0¶

[in] Minimum separation distance between the two edges

const double tolerance = TightInclusionCCD::DEFAULT_TOLERANCE¶

[in] Tolerance for the linear CCD algorithm

const long max_iterations = TightInclusionCCD::DEFAULT_MAX_ITERATIONS¶

[in] Maximum number of iterations for the linear CCD algorithm

const double conservative_rescaling = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING¶

[in] Conservative rescaling of the time of impact

Returns:¶

True if the two edges collide, false otherwise.

bool ipc::point_triangle_nonlinear_ccd(const NonlinearTrajectory& p,
    const NonlinearTrajectory& t0, const NonlinearTrajectory& t1,
    const NonlinearTrajectory& t2, double& toi,
    const double tmax = 1.0, const double min_distance = 0,
    const double tolerance = TightInclusionCCD::DEFAULT_TOLERANCE,
    const long max_iterations
    = TightInclusionCCD::DEFAULT_MAX_ITERATIONS,
    const double conservative_rescaling
    = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING)¶

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 tmax = 1.0¶

[in] Maximum time to check for collision

const double min_distance = 0¶

[in] Minimum separation distance between the two edges

const double tolerance = TightInclusionCCD::DEFAULT_TOLERANCE¶

[in] Tolerance for the linear CCD algorithm

const long max_iterations = TightInclusionCCD::DEFAULT_MAX_ITERATIONS¶

[in] Maximum number of iterations for the linear CCD algorithm

const double conservative_rescaling = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING¶

[in] Conservative rescaling of the time of impact

Returns:¶

True if the point and triangle collide, false otherwise.

Generic Interface¶

bool ipc::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 tmax = 1.0,
    const double min_distance = 0,
    const double conservative_rescaling
    = TightInclusionCCD::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 tmax = 1.0¶

[in] Maximum time to check for collision.

const double min_distance = 0¶

[in] Minimum separation distance between the objects.

const double conservative_rescaling = TightInclusionCCD::DEFAULT_CONSERVATIVE_RESCALING¶

[in] Conservative rescaling of the time of impact.

Returns:¶