CCD

Broad Phase

enum class ipc::BroadPhaseMethod

Enumeration of implemented broad phase methods.

Values:

enumerator BRUTE_FORCE
enumerator HASH_GRID
enumerator SPATIAL_HASH
enumerator SWEEP_AND_TINIEST_QUEUE
enumerator SWEEP_AND_TINIEST_QUEUE_GPU
enumerator NUM_METHODS

Candidates

struct ContinuousCollisionCandidate

Virtual class for candidates that support CCD.

Subclassed by ipc::EdgeEdgeCandidate, ipc::EdgeVertexCandidate, ipc::FaceVertexCandidate

Public Functions

inline virtual ~ContinuousCollisionCandidate()
virtual bool ccd(const Eigen::MatrixXd &V0, const Eigen::MatrixXd &V1, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, double &toi, const double min_distance = 0.0, const double tmax = 1.0, const double tolerance = DEFAULT_CCD_TOLERANCE, const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS, const double conservative_rescaling = DEFAULT_CCD_CONSERVATIVE_RESCALING) const = 0

Perform narrow-phase CCD on the candidate.

Parameters:
const Eigen::MatrixXd &V0

[in] Mesh vertex positions at the start of the time step.

const Eigen::MatrixXd &V1

[in] Mesh vertex positions at the end of the time step.

const Eigen::MatrixXi &E

[in] Mesh edges as rows of indicies into V.

const Eigen::MatrixXi &F

[in] Mesh triangular faces as rows of indicies into V.

double &toi

[out] Computed time of impact (normalized).

const double min_distance = 0.0

[in] Minimum separation distance between primitives.

const double tmax = 1.0

[in] Maximum time (normalized) to look for collisions. Should be in [0, 1].

const double tolerance = DEFAULT_CCD_TOLERANCE

[in] CCD tolerance used by Tight-Inclusion CCD.

const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS

[in] Maximum iterations used by Tight-Inclusion CCD.

const double conservative_rescaling = DEFAULT_CCD_CONSERVATIVE_RESCALING

[in] Conservative rescaling value used to avoid taking steps exactly to impact.

Returns:

If the candidate had a collision over the time interval.

virtual void print_ccd_query(const Eigen::MatrixXd &V0, const Eigen::MatrixXd &V1, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const = 0
struct VertexVertexCandidate

Subclassed by ipc::VertexVertexConstraint, ipc::VertexVertexFrictionConstraint

Public Functions

VertexVertexCandidate(long vertex0_index, long vertex1_index)
inline int num_vertices() const
inline std::array<long, 4> vertex_indices(const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const

Get the indices of the vertices.

Parameters:
const Eigen::MatrixXi &E

edge matrix of mesh

const Eigen::MatrixXi &F

face matrix of mesh

Returns:

List of vertex indices

double compute_distance(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const
VectorMax6d compute_distance_gradient(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const
MatrixMax6d compute_distance_hessian(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const
bool operator==(const VertexVertexCandidate &other) const
bool operator!=(const VertexVertexCandidate &other) const
bool operator<(const VertexVertexCandidate &other) const

Compare EdgeVertexCandidates for sorting.

Public Members

long vertex0_index
long vertex1_index

Friends

template<typename H>
inline friend H AbslHashValue(H h, const VertexVertexCandidate &vv)
struct EdgeVertexCandidate : public ipc::ContinuousCollisionCandidate

Subclassed by ipc::EdgeVertexConstraint, ipc::EdgeVertexFrictionConstraint

Public Functions

EdgeVertexCandidate(long edge_index, long vertex_index)
inline int num_vertices() const
inline std::array<long, 4> vertex_indices(const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const
double compute_distance(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const PointEdgeDistanceType dtype = PointEdgeDistanceType::AUTO) const
VectorMax9d compute_distance_gradient(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const PointEdgeDistanceType dtype = PointEdgeDistanceType::AUTO) const
MatrixMax9d compute_distance_hessian(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const PointEdgeDistanceType dtype = PointEdgeDistanceType::AUTO) const
virtual bool ccd(const Eigen::MatrixXd &V0, const Eigen::MatrixXd &V1, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, double &toi, const double min_distance = 0.0, const double tmax = 1.0, const double tolerance = DEFAULT_CCD_TOLERANCE, const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS, const double conservative_rescaling = DEFAULT_CCD_CONSERVATIVE_RESCALING) const override

Perform narrow-phase CCD on the candidate.

Parameters:
const Eigen::MatrixXd &V0

[in] Mesh vertex positions at the start of the time step.

const Eigen::MatrixXd &V1

[in] Mesh vertex positions at the end of the time step.

const Eigen::MatrixXi &E

[in] Mesh edges as rows of indicies into V.

const Eigen::MatrixXi &F

[in] Mesh triangular faces as rows of indicies into V.

double &toi

[out] Computed time of impact (normalized).

const double tmax = 1.0

[in] Maximum time (normalized) to look for collisions. Should be in [0, 1].

const double tolerance = DEFAULT_CCD_TOLERANCE

[in] CCD tolerance used by Tight-Inclusion CCD.

const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS

[in] Maximum iterations used by Tight-Inclusion CCD.

const double conservative_rescaling = DEFAULT_CCD_CONSERVATIVE_RESCALING

[in] Conservative rescaling value used to avoid taking steps exactly to impact.

Returns:

If the candidate had a collision over the time interval.

virtual void print_ccd_query(const Eigen::MatrixXd &V0, const Eigen::MatrixXd &V1, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const override
bool operator==(const EdgeVertexCandidate &other) const
bool operator!=(const EdgeVertexCandidate &other) const
bool operator<(const EdgeVertexCandidate &other) const

Compare EdgeVertexCandidates for sorting.

Public Members

long edge_index
long vertex_index

Friends

template<typename H>
inline friend H AbslHashValue(H h, const EdgeVertexCandidate &ev)
struct EdgeEdgeCandidate : public ipc::ContinuousCollisionCandidate

Subclassed by ipc::EdgeEdgeConstraint, ipc::EdgeEdgeFrictionConstraint

Public Functions

EdgeEdgeCandidate(long edge0_index, long edge1_index)
inline int num_vertices() const
inline std::array<long, 4> vertex_indices(const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const
double compute_distance(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const EdgeEdgeDistanceType dtype = EdgeEdgeDistanceType::AUTO) const
VectorMax12d compute_distance_gradient(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const EdgeEdgeDistanceType dtype = EdgeEdgeDistanceType::AUTO) const
MatrixMax12d compute_distance_hessian(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const EdgeEdgeDistanceType dtype = EdgeEdgeDistanceType::AUTO) const
virtual bool ccd(const Eigen::MatrixXd &V0, const Eigen::MatrixXd &V1, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, double &toi, const double min_distance = 0.0, const double tmax = 1.0, const double tolerance = DEFAULT_CCD_TOLERANCE, const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS, const double conservative_rescaling = DEFAULT_CCD_CONSERVATIVE_RESCALING) const override

Perform narrow-phase CCD on the candidate.

Parameters:
const Eigen::MatrixXd &V0

[in] Mesh vertex positions at the start of the time step.

const Eigen::MatrixXd &V1

[in] Mesh vertex positions at the end of the time step.

const Eigen::MatrixXi &E

[in] Mesh edges as rows of indicies into V.

const Eigen::MatrixXi &F

[in] Mesh triangular faces as rows of indicies into V.

double &toi

[out] Computed time of impact (normalized).

const double tmax = 1.0

[in] Maximum time (normalized) to look for collisions. Should be in [0, 1].

const double tolerance = DEFAULT_CCD_TOLERANCE

[in] CCD tolerance used by Tight-Inclusion CCD.

const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS

[in] Maximum iterations used by Tight-Inclusion CCD.

const double conservative_rescaling = DEFAULT_CCD_CONSERVATIVE_RESCALING

[in] Conservative rescaling value used to avoid taking steps exactly to impact.

Returns:

If the candidate had a collision over the time interval.

virtual void print_ccd_query(const Eigen::MatrixXd &V0, const Eigen::MatrixXd &V1, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const override
bool operator==(const EdgeEdgeCandidate &other) const
bool operator!=(const EdgeEdgeCandidate &other) const
bool operator<(const EdgeEdgeCandidate &other) const

Compare EdgeEdgeCandidates for sorting.

Public Members

long edge0_index
long edge1_index

Friends

template<typename H>
inline friend H AbslHashValue(H h, const EdgeEdgeCandidate &ee)
struct EdgeFaceCandidate

Candidate for intersection between edge and face.

Not included in Candidates because it is not a collision candidate.

Public Functions

EdgeFaceCandidate(long edge_index, long face_index)
bool operator==(const EdgeFaceCandidate &other) const
bool operator!=(const EdgeFaceCandidate &other) const
bool operator<(const EdgeFaceCandidate &other) const

Compare EdgeFaceCandidate for sorting.

Public Members

long edge_index
long face_index

Friends

template<typename H>
inline friend H AbslHashValue(H h, const EdgeFaceCandidate &fv)
struct FaceVertexCandidate : public ipc::ContinuousCollisionCandidate

Subclassed by ipc::FaceVertexConstraint, ipc::FaceVertexFrictionConstraint

Public Functions

FaceVertexCandidate(long face_index, long vertex_index)
inline int num_vertices() const
inline std::array<long, 4> vertex_indices(const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const
double compute_distance(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const PointTriangleDistanceType dtype = PointTriangleDistanceType::AUTO) const
VectorMax12d compute_distance_gradient(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const PointTriangleDistanceType dtype = PointTriangleDistanceType::AUTO) const
MatrixMax12d compute_distance_hessian(const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, const PointTriangleDistanceType dtype = PointTriangleDistanceType::AUTO) const
virtual bool ccd(const Eigen::MatrixXd &V0, const Eigen::MatrixXd &V1, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F, double &toi, const double min_distance = 0.0, const double tmax = 1.0, const double tolerance = DEFAULT_CCD_TOLERANCE, const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS, const double conservative_rescaling = DEFAULT_CCD_CONSERVATIVE_RESCALING) const override

Perform narrow-phase CCD on the candidate.

Parameters:
const Eigen::MatrixXd &V0

[in] Mesh vertex positions at the start of the time step.

const Eigen::MatrixXd &V1

[in] Mesh vertex positions at the end of the time step.

const Eigen::MatrixXi &E

[in] Mesh edges as rows of indicies into V.

const Eigen::MatrixXi &F

[in] Mesh triangular faces as rows of indicies into V.

double &toi

[out] Computed time of impact (normalized).

const double min_distance = 0.0

[in] Minimum separation distance between primitives.

const double tmax = 1.0

[in] Maximum time (normalized) to look for collisions. Should be in [0, 1].

const double tolerance = DEFAULT_CCD_TOLERANCE

[in] CCD tolerance used by Tight-Inclusion CCD.

const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS

[in] Maximum iterations used by Tight-Inclusion CCD.

const double conservative_rescaling = DEFAULT_CCD_CONSERVATIVE_RESCALING

[in] Conservative rescaling value used to avoid taking steps exactly to impact.

Returns:

If the candidate had a collision over the time interval.

virtual void print_ccd_query(const Eigen::MatrixXd &V0, const Eigen::MatrixXd &V1, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const override
bool operator==(const FaceVertexCandidate &other) const
bool operator!=(const FaceVertexCandidate &other) const
bool operator<(const FaceVertexCandidate &other) const

Compare FaceVertexCandidate for sorting.

Public Members

long face_index
long vertex_index

Friends

template<typename H>
inline friend H AbslHashValue(H h, const FaceVertexCandidate &fv)
struct Candidates

Public Functions

inline Candidates()
size_t size() const
bool empty() const
void clear()
ContinuousCollisionCandidate &operator[](size_t idx)
const ContinuousCollisionCandidate &operator[](size_t idx) const
bool save_obj(const std::string &filename, const Eigen::MatrixXd &V, const Eigen::MatrixXi &E, const Eigen::MatrixXi &F) const

Public Members

std::vector<EdgeVertexCandidate> ev_candidates
std::vector<EdgeEdgeCandidate> ee_candidates
std::vector<FaceVertexCandidate> fv_candidates

Narrow Phase

static constexpr double ipc::DEFAULT_CCD_TOLERANCE = 1e-6

The default tolerance used with Tight-Inclusion CCD.

static constexpr long ipc::DEFAULT_CCD_MAX_ITERATIONS = 1e7

The default maximum number of iterations used with Tight-Inclusion CCD.

static constexpr double ipc::DEFAULT_CCD_CONSERVATIVE_RESCALING = 0.8

The default conservative rescaling value used to avoid taking steps exactly to impact.


Last update: January 26, 2023