Broad Phase¶

Broad Phase¶

class BroadPhase;¶

Inheritance diagram for ipc::BroadPhase:

Subclassed by ipc::BVH, ipc::BruteForce, ipc::HashGrid, ipc::SpatialHash, ipc::SweepAndPrune

Public Functions¶

inline virtual ~BroadPhase();¶

virtual std::string name() const = 0;¶

Get the name of the broad phase method.

Returns:¶

The name of the broad phase method.

virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    const double inflation_radius = 0);¶

Build the broad phase for static collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices¶

Vertex positions

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

const double inflation_radius = 0¶

Radius of inflation around all elements.

virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
    Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    const double inflation_radius = 0);¶

Build the broad phase for continuous collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices_t0¶

Starting vertices of the vertices.

Eigen::ConstRef<Eigen::MatrixXd> vertices_t1¶

Ending vertices of the vertices.

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

const double inflation_radius = 0¶

Radius of inflation around all elements.

virtual void clear();¶

Clear any built data.

void detect_collision_candidates(
    int dim, Candidates& candidates) const;¶

Detect all collision candidates needed for a given dimensional simulation.

Parameters:¶

int dim¶

The dimension of the simulation (i.e., 2 or 3).

Candidates &candidates¶

The detected collision candidates.

virtual void detect_vertex_vertex_candidates(
    std::vector<VertexVertexCandidate>& candidates) const
    = 0;¶

Find the candidate vertex-vertex collisions.

Parameters:¶

std::vector<VertexVertexCandidate> &candidates¶

[out] The candidate vertex-vertex collisions.

virtual void detect_edge_vertex_candidates(
    std::vector<EdgeVertexCandidate>& candidates) const
    = 0;¶

Find the candidate edge-vertex collisions.

Parameters:¶

std::vector<EdgeVertexCandidate> &candidates¶

[out] The candidate edge-vertex collisions.

virtual void detect_edge_edge_candidates(
    std::vector<EdgeEdgeCandidate>& candidates) const
    = 0;¶

Find the candidate edge-edge collisions.

Parameters:¶

std::vector<EdgeEdgeCandidate> &candidates¶

[out] The candidate edge-edge collisions.

virtual void detect_face_vertex_candidates(
    std::vector<FaceVertexCandidate>& candidates) const
    = 0;¶

Find the candidate face-vertex collisions.

Parameters:¶

std::vector<FaceVertexCandidate> &candidates¶

[out] The candidate face-vertex collisions.

virtual void detect_edge_face_candidates(
    std::vector<EdgeFaceCandidate>& candidates) const
    = 0;¶

Find the candidate edge-face intersections.

Parameters:¶

std::vector<EdgeFaceCandidate> &candidates¶

[out] The candidate edge-face intersections.

virtual void detect_face_face_candidates(
    std::vector<FaceFaceCandidate>& candidates) const
    = 0;¶

Find the candidate face-face collisions.

Parameters:¶

std::vector<FaceFaceCandidate> &candidates¶

[out] The candidate face-face collisions.

Public Members¶

std::function<bool(size_t, size_t)> can_vertices_collide
    = default_can_vertices_collide;¶

Function for determining if two vertices can collide.

Protected Functions¶

virtual bool can_edge_vertex_collide(size_t ei, size_t vi) const;¶

virtual bool can_edges_collide(size_t eai, size_t ebi) const;¶

virtual bool can_face_vertex_collide(size_t fi, size_t vi) const;¶

virtual bool can_edge_face_collide(size_t ei, size_t fi) const;¶

virtual bool can_faces_collide(size_t fai, size_t fbi) const;¶

Protected Attributes¶

std::vector<AABB> vertex_boxes;¶

std::vector<AABB> edge_boxes;¶

std::vector<AABB> face_boxes;¶

Protected Static Functions¶

static inline bool default_can_vertices_collide(size_t, size_t);¶

Brute Force¶

class BruteForce : public ipc::BroadPhase;¶

Inheritance diagram for ipc::BruteForce:

Collaboration diagram for ipc::BruteForce:

Public Functions¶

BruteForce() = default;¶

inline virtual std::string name() const override;¶

Get the name of the broad phase method.

Returns:¶

The name of the broad phase method.

virtual void detect_vertex_vertex_candidates(
    std::vector<VertexVertexCandidate>& candidates) const override;¶

Find the candidate vertex-vertex collisions.

Parameters:¶

std::vector<VertexVertexCandidate> &candidates¶

[out] The candidate vertex-vertex collisions.

virtual void detect_edge_vertex_candidates(
    std::vector<EdgeVertexCandidate>& candidates) const override;¶

Find the candidate edge-vertex collisions.

Parameters:¶

std::vector<EdgeVertexCandidate> &candidates¶

[out] The candidate edge-vertex collisions.

virtual void detect_edge_edge_candidates(
    std::vector<EdgeEdgeCandidate>& candidates) const override;¶

Find the candidate edge-edge collisions.

Parameters:¶

std::vector<EdgeEdgeCandidate> &candidates¶

[out] The candidate edge-edge collisions.

virtual void detect_face_vertex_candidates(
    std::vector<FaceVertexCandidate>& candidates) const override;¶

Find the candidate face-vertex collisions.

Parameters:¶

std::vector<FaceVertexCandidate> &candidates¶

[out] The candidate face-vertex collisions.

virtual void detect_edge_face_candidates(
    std::vector<EdgeFaceCandidate>& candidates) const override;¶

Find the candidate edge-face intersections.

Parameters:¶

std::vector<EdgeFaceCandidate> &candidates¶

[out] The candidate edge-face intersections.

virtual void detect_face_face_candidates(
    std::vector<FaceFaceCandidate>& candidates) const override;¶

Find the candidate face-face collisions.

Parameters:¶

std::vector<FaceFaceCandidate> &candidates¶

[out] The candidate face-face collisions.

Private Functions¶

template <typename Candidate, bool triangular = false>
void detect_candidates(const std::vector<AABB>& boxes0,
    const std::vector<AABB>& boxes1,
    const std::function<bool(size_t, size_t)>& can_collide,
    std::vector<Candidate>& candidates) const;¶

Detect candidates for collisions between two sets of boxes.

Template Parameters:¶

typename Candidate¶

Type of the candidate.

bool triangular = false¶

Whether to consider (i, j) and (j, i) as the same.

Parameters:¶

const std::vector<AABB> &boxes0¶

[in] First set of boxes.

const std::vector<AABB> &boxes1¶

[in] Second set of boxes.

const std::function<bool(size_t, size_t)> &can_collide¶

[in] Function to determine if two primitives can collide given their ids.

std::vector<Candidate> &candidates¶

[out] The candidate collisions.

Hash Grid¶

class HashGrid : public ipc::BroadPhase;¶

Inheritance diagram for ipc::HashGrid:

Collaboration diagram for ipc::HashGrid:

Public Functions¶

HashGrid() = default;¶

inline virtual std::string name() const override;¶

Get the name of the broad phase method.

Returns:¶

The name of the broad phase method.

virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    double inflation_radius = 0) override;¶

Build the broad phase for static collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices¶

Vertex positions

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

double inflation_radius = 0¶

Radius of inflation around all elements.

virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
    Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    double inflation_radius = 0) override;¶

Build the broad phase for continuous collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices_t0¶

Starting vertices of the vertices.

Eigen::ConstRef<Eigen::MatrixXd> vertices_t1¶

Ending vertices of the vertices.

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

double inflation_radius = 0¶

Radius of inflation around all elements.

inline virtual void clear() override;¶

Clear the hash grid.

virtual void detect_vertex_vertex_candidates(
    std::vector<VertexVertexCandidate>& candidates) const override;¶

Find the candidate vertex-vertex collisions.

virtual void detect_edge_vertex_candidates(
    std::vector<EdgeVertexCandidate>& candidates) const override;¶

Find the candidate edge-vertex collisions.

Parameters:¶

std::vector<EdgeVertexCandidate> &candidates¶

[out] The candidate edge-vertex collisions.

virtual void detect_edge_edge_candidates(
    std::vector<EdgeEdgeCandidate>& candidates) const override;¶

Find the candidate edge-edge collisions.

Parameters:¶

std::vector<EdgeEdgeCandidate> &candidates¶

[out] The candidate edge-edge collisions.

virtual void detect_face_vertex_candidates(
    std::vector<FaceVertexCandidate>& candidates) const override;¶

Find the candidate face-vertex collisions.

Parameters:¶

std::vector<FaceVertexCandidate> &candidates¶

[out] The candidate face-vertex collisions.

virtual void detect_edge_face_candidates(
    std::vector<EdgeFaceCandidate>& candidates) const override;¶

Find the candidate edge-face intersections.

Parameters:¶

std::vector<EdgeFaceCandidate> &candidates¶

[out] The candidate edge-face intersections.

virtual void detect_face_face_candidates(
    std::vector<FaceFaceCandidate>& candidates) const override;¶

Find the candidate face-face collisions.

Parameters:¶

std::vector<FaceFaceCandidate> &candidates¶

[out] The candidate face-face collisions.

inline double cell_size() const;¶

inline const ArrayMax3i& grid_size() const;¶

inline const ArrayMax3d& domain_min() const;¶

inline const ArrayMax3d& domain_max() const;¶

Protected Functions¶

void resize(Eigen::ConstRef<ArrayMax3d> domain_min,
    Eigen::ConstRef<ArrayMax3d> domain_max, double cell_size);¶

void insert_boxes();¶

void insert_boxes(const std::vector<AABB>& boxes,
    std::vector<HashItem>& items) const;¶

void insert_box(const AABB& aabb, const long id,
    std::vector<HashItem>& items) const;¶

Add an AABB of the extents to the hash grid.

inline long hash(int x, int y, int z) const;¶

Create the hash of a cell location.

Protected Attributes¶

double m_cell_size;¶

ArrayMax3i m_grid_size;¶

ArrayMax3d m_domain_min;¶

ArrayMax3d m_domain_max;¶

std::vector<HashItem> vertex_items;¶

std::vector<HashItem> edge_items;¶

std::vector<HashItem> face_items;¶

Private Functions¶

template <typename Candidate>
void detect_candidates(const std::vector<HashItem>& items0,
    const std::vector<HashItem>& items1,
    const std::vector<AABB>& boxes0,
    const std::vector<AABB>& boxes1,
    const std::function<bool(size_t, size_t)>& can_collide,
    std::vector<Candidate>& candidates) const;¶

Find the candidate collisions between two sets of items.

Template Parameters:¶

typename Candidate¶

The type of collision candidate.

Parameters:¶

const std::vector<HashItem> &items0¶

[in] First set of items.

const std::vector<HashItem> &items1¶

[in] Second set of items.

const std::vector<AABB> &boxes0¶

[in] First set’s boxes.

const std::vector<AABB> &boxes1¶

[in] Second set’s boxes.

const std::function<bool(size_t, size_t)> &can_collide¶

[in] Function to determine if two items can collide.

std::vector<Candidate> &candidates¶

[out] The candidate collisions.

template <typename Candidate>
void detect_candidates(const std::vector<HashItem>& items,
    const std::vector<AABB>& boxes,
    const std::function<bool(size_t, size_t)>& can_collide,
    std::vector<Candidate>& candidates) const;¶

Find the candidate collisions among a set of items.

Template Parameters:¶

typename Candidate¶

The type of collision candidate.

Parameters:¶

const std::vector<HashItem> &items¶

[in] The set of items.

const std::vector<AABB> &boxes¶

[in] The items’ boxes.

const std::function<bool(size_t, size_t)> &can_collide¶

[in] Function to determine if two items can collide.

std::vector<Candidate> &candidates¶

[out] The candidate collisions.

Spatial Hash¶

class SpatialHash : public ipc::BroadPhase;¶

Inheritance diagram for ipc::SpatialHash:

Collaboration diagram for ipc::SpatialHash:

Public Functions¶

SpatialHash() = default;¶

inline SpatialHash(Eigen::ConstRef<Eigen::MatrixXd> vertices,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    double inflation_radius = 0, double voxel_size = -1);¶

inline SpatialHash(Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
    Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    double inflation_radius = 0, double voxel_size = -1);¶

inline virtual std::string name() const override;¶

Get the name of the broad phase method.

Returns:¶

The name of the broad phase method.

inline virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    double inflation_radius = 0) override;¶

Build the broad phase for static collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices¶

Vertex positions

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

double inflation_radius = 0¶

Radius of inflation around all elements.

inline virtual void build(
    Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
    Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    double inflation_radius = 0) override;¶

Build the broad phase for continuous collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices_t0¶

Starting vertices of the vertices.

Eigen::ConstRef<Eigen::MatrixXd> vertices_t1¶

Ending vertices of the vertices.

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

double inflation_radius = 0¶

Radius of inflation around all elements.

void build(Eigen::ConstRef<Eigen::MatrixXd> vertices,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces, double inflation_radius,
    double voxel_size);¶

void build(Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
    Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces, double inflation_radius,
    double voxel_size);¶

inline virtual void clear() override;¶

Clear any built data.

inline bool is_vertex_index(int idx) const;¶

Check if primitive index refers to a vertex.

inline bool is_edge_index(int idx) const;¶

Check if primitive index refers to an edge.

inline bool is_triangle_index(int idx) const;¶

Check if primitive index refers to a triangle.

inline int to_edge_index(int idx) const;¶

Convert a primitive index to an edge index.

inline int to_triangle_index(int idx) const;¶

Convert a primitive index to a triangle index.

virtual void detect_vertex_vertex_candidates(
    std::vector<VertexVertexCandidate>& candidates) const override;¶

Find the candidate vertex-vertex collisions.

virtual void detect_edge_vertex_candidates(
    std::vector<EdgeVertexCandidate>& candidates) const override;¶

Find the candidate edge-vertex collisions.

virtual void detect_edge_edge_candidates(
    std::vector<EdgeEdgeCandidate>& candidates) const override;¶

Find the candidate edge-edge collisions.

virtual void detect_face_vertex_candidates(
    std::vector<FaceVertexCandidate>& candidates) const override;¶

Find the candidate face-vertex collisions.

virtual void detect_edge_face_candidates(
    std::vector<EdgeFaceCandidate>& candidates) const override;¶

Find the candidate edge-face intersections.

virtual void detect_face_face_candidates(
    std::vector<FaceFaceCandidate>& candidates) const override;¶

Find the candidate face-face collisions.

Parameters:¶

std::vector<FaceFaceCandidate> &candidates¶

[out] The candidate face-face collisions.

Public Members¶

ArrayMax3d left_bottom_corner;¶

The left bottom corner of the world bounding box.

ArrayMax3d right_top_corner;¶

The right top corner of the world bounding box.

ArrayMax3i voxel_count;¶

The number of voxels in each dimension.

double one_div_voxelSize;¶

1.0 / voxel_size

int voxel_count_0x1;¶

The number of voxels in the first two dimensions.

int edge_start_ind;¶

int tri_start_ind;¶

unordered_map<int, std::vector<int>> voxel_to_primitives;¶

Map from voxel index to the primitive indices it contains.

std::vector<std::vector<int>> point_to_voxels;¶

Map from point index to the voxel indices it occupies.

std::vector<std::vector<int>> edge_to_voxels;¶

Map from edge index to the voxel indices it occupies.

std::vector<std::vector<int>> face_to_voxels;¶

Map from face index to the voxel indices it occupies.

Protected Functions¶

void query_point_for_points(
    int vi, unordered_set<int>& vert_inds) const;¶

void query_point_for_edges(
    int vi, unordered_set<int>& edge_inds) const;¶

void query_point_for_triangles(
    int vi, unordered_set<int>& tri_inds) const;¶

void query_edge_for_edges(
    int eai, unordered_set<int>& edge_inds) const;¶

void query_edge_for_triangles(
    int ei, unordered_set<int>& tri_inds) const;¶

void query_triangle_for_triangles(
    int ti, unordered_set<int>& tri_inds) const;¶

int locate_voxel_index(Eigen::ConstRef<VectorMax3d> p) const;¶

ArrayMax3i locate_voxel_axis_index(
    Eigen::ConstRef<VectorMax3d> p) const;¶

void locate_box_voxel_axis_index(ArrayMax3d min_corner,
    ArrayMax3d max_corner, Eigen::Ref<ArrayMax3i> min_index,
    Eigen::Ref<ArrayMax3i> max_index,
    const double inflation_radius = 0) const;¶

int voxel_axis_index_to_voxel_index(
    Eigen::ConstRef<ArrayMax3i> voxel_axis_index) const;¶

int voxel_axis_index_to_voxel_index(int ix, int iy, int iz) const;¶

Protected Attributes¶

int dim;¶

double built_in_radius;¶

Private Functions¶

template <typename Candidate, bool swap_order,
    bool triangular = false>
void detect_candidates(const std::vector<AABB>& boxesA,
    const std::vector<AABB>& boxesB,
    const std::function<void(int, unordered_set<int>&)>&
        query_A_for_Bs,
    const std::function<bool(int, int)>& can_collide,
    std::vector<Candidate>& candidates) const;¶

Detect candidate collisions between type A and type B.

Template Parameters:¶

typename Candidate¶

Type of candidate collision.

bool swap_order¶

Whether to swap the order of A and B when adding to the candidates.

bool triangular = false¶

Whether to consider (i, j) and (j, i) as the same.

Parameters:¶

const std::vector<AABB> &boxesA¶

[in] The boxes of type A to detect collisions with.

const std::vector<AABB> &boxesB¶

[in] The boxes of type B to detect collisions with.

const std::function<void(int, unordered_set<int>&)> &query_A_for_Bs¶

[in] Function to query boxes of type B for boxes of type A.

const std::function<bool(int, int)> &can_collide¶

[in] Function to determine if two primitives can collide given their ids.

std::vector<Candidate> &candidates¶

[out] The candidate collisions.

template <typename Candidate>
void detect_candidates(const std::vector<AABB>& boxesA,
    const std::function<void(int, unordered_set<int>&)>&
        query_A_for_As,
    const std::function<bool(int, int)>& can_collide,
    std::vector<Candidate>& candidates) const;¶

Detect candidate collisions between type A and type A.

Template Parameters:¶

typename Candidate¶

Type of candidate collision.

Parameters:¶

const std::vector<AABB> &boxesA¶

[in] The boxes of type A to detect collisions with.

const std::function<void(int, unordered_set<int>&)> &query_A_for_As¶

[in] Function to query boxes of type A for boxes of type A.

const std::function<bool(int, int)> &can_collide¶

[in] Function to determine if two primitives can collide given their ids.

std::vector<Candidate> &candidates¶

[out] The candidate collisions.

BVH¶

class BVH : public ipc::BroadPhase;¶

Inheritance diagram for ipc::BVH:

Collaboration diagram for ipc::BVH:

Public Functions¶

BVH() = default;¶

inline virtual std::string name() const override;¶

Get the name of the broad phase method.

Returns:¶

The name of the broad phase method.

virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    const double inflation_radius = 0) override;¶

Build the broad phase for static collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices¶

Vertex positions

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

const double inflation_radius = 0¶

Radius of inflation around all elements.

virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
    Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    const double inflation_radius = 0) override;¶

Build the broad phase for continuous collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices_t0¶

Starting vertices of the vertices.

Eigen::ConstRef<Eigen::MatrixXd> vertices_t1¶

Ending vertices of the vertices.

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

const double inflation_radius = 0¶

Radius of inflation around all elements.

virtual void clear() override;¶

Clear any built data.

virtual void detect_vertex_vertex_candidates(
    std::vector<VertexVertexCandidate>& candidates) const override;¶

Find the candidate vertex-vertex collisions.

Parameters:¶

std::vector<VertexVertexCandidate> &candidates¶

[out] The candidate vertex-vertex collisions.

virtual void detect_edge_vertex_candidates(
    std::vector<EdgeVertexCandidate>& candidates) const override;¶

Find the candidate edge-vertex collisions.

Parameters:¶

std::vector<EdgeVertexCandidate> &candidates¶

[out] The candidate edge-vertex collisions.

virtual void detect_edge_edge_candidates(
    std::vector<EdgeEdgeCandidate>& candidates) const override;¶

Find the candidate edge-edge collisions.

Parameters:¶

std::vector<EdgeEdgeCandidate> &candidates¶

[out] The candidate edge-edge collisions.

virtual void detect_face_vertex_candidates(
    std::vector<FaceVertexCandidate>& candidates) const override;¶

Find the candidate face-vertex collisions.

Parameters:¶

std::vector<FaceVertexCandidate> &candidates¶

[out] The candidate face-vertex collisions.

virtual void detect_edge_face_candidates(
    std::vector<EdgeFaceCandidate>& candidates) const override;¶

Find the candidate edge-face intersections.

Parameters:¶

std::vector<EdgeFaceCandidate> &candidates¶

[out] The candidate edge-face intersections.

virtual void detect_face_face_candidates(
    std::vector<FaceFaceCandidate>& candidates) const override;¶

Find the candidate face-face collisions.

Parameters:¶

std::vector<FaceFaceCandidate> &candidates¶

[out] The candidate face-face collisions.

Protected Attributes¶

SimpleBVH::BVH vertex_bvh;¶

BVH containing the vertices.

SimpleBVH::BVH edge_bvh;¶

BVH containing the edges.

SimpleBVH::BVH face_bvh;¶

BVH containing the faces.

Protected Static Functions¶

static void init_bvh(
    const std::vector<AABB>& boxes, SimpleBVH::BVH& bvh);¶

Initialize a BVH from a set of boxes.

Parameters:¶

const std::vector<AABB> &boxes¶

[in] Set of boxes to initialize the BVH with.

SimpleBVH::BVH &bvh¶

[out] The BVH to initialize.

template <typename Candidate, bool swap_order = false,
    bool triangular = false>
static void detect_candidates(const std::vector<AABB>& boxes,
    const SimpleBVH::BVH& bvh,
    const std::function<bool(size_t, size_t)>& can_collide,
    std::vector<Candidate>& candidates);¶

Detect candidate collisions between a BVH and a sets of boxes.

Template Parameters:¶

typename Candidate¶

Type of candidate collision.

bool swap_order = false¶

Whether to swap the order of box id with the BVH id when adding to the candidates.

bool triangular = false¶

Whether to consider (i, j) and (j, i) as the same.

Parameters:¶

const std::vector<AABB> &boxes¶

[in] The boxes to detect collisions with.

const SimpleBVH::BVH &bvh¶

[in] The BVH to detect collisions with.

const std::function<bool(size_t, size_t)> &can_collide¶

[in] Function to determine if two primitives can collide given their ids.

std::vector<Candidate> &candidates¶

[out] The candidate collisions.

Sweep and Prune¶

class SweepAndPrune : public ipc::BroadPhase;¶

Inheritance diagram for ipc::SweepAndPrune:

Collaboration diagram for ipc::SweepAndPrune:

Public Functions¶

SweepAndPrune() = default;¶

inline virtual std::string name() const override;¶

Get the name of the broad phase method.

Returns:¶

The name of the broad phase method.

virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    double inflation_radius = 0) override;¶

Build the broad phase for static collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices¶

Vertex positions

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

double inflation_radius = 0¶

Radius of inflation around all elements.

virtual void build(Eigen::ConstRef<Eigen::MatrixXd> vertices_t0,
    Eigen::ConstRef<Eigen::MatrixXd> vertices_t1,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    double inflation_radius = 0) override;¶

Build the broad phase for continuous collision detection.

Parameters:¶

Eigen::ConstRef<Eigen::MatrixXd> vertices_t0¶

Starting vertex positions

Eigen::ConstRef<Eigen::MatrixXd> vertices_t1¶

Ending vertex positions

Eigen::ConstRef<Eigen::MatrixXi> edges¶

Collision mesh edges

Eigen::ConstRef<Eigen::MatrixXi> faces¶

Collision mesh faces

double inflation_radius = 0¶

Radius of inflation around all elements.

virtual void clear() override;¶

Clear any built data.

virtual void detect_vertex_vertex_candidates(
    std::vector<VertexVertexCandidate>& candidates) const override;¶

Find the candidate vertex-vertex collisions.

Parameters:¶

std::vector<VertexVertexCandidate> &candidates¶

[out] The candidate vertex-vertex collisions.

virtual void detect_edge_vertex_candidates(
    std::vector<EdgeVertexCandidate>& candidates) const override;¶

Find the candidate edge-vertex collisions.

Parameters:¶

std::vector<EdgeVertexCandidate> &candidates¶

[out] The candidate edge-vertex collisions.

virtual void detect_edge_edge_candidates(
    std::vector<EdgeEdgeCandidate>& candidates) const override;¶

Find the candidate edge-edge collisions.

Parameters:¶

std::vector<EdgeEdgeCandidate> &candidates¶

[out] The candidate edge-edge collisions.

virtual void detect_face_vertex_candidates(
    std::vector<FaceVertexCandidate>& candidates) const override;¶

Find the candidate face-vertex collisions.

Parameters:¶

std::vector<FaceVertexCandidate> &candidates¶

[out] The candidate face-vertex collisions.

virtual void detect_edge_face_candidates(
    std::vector<EdgeFaceCandidate>& candidates) const override;¶

Find the candidate edge-face intersections.

Parameters:¶

std::vector<EdgeFaceCandidate> &candidates¶

[out] The candidate edge-face intersections.

virtual void detect_face_face_candidates(
    std::vector<FaceFaceCandidate>& candidates) const override;¶

Find the candidate face-face collisions.

Parameters:¶

std::vector<FaceFaceCandidate> &candidates¶

[out] The candidate face-face collisions.

Protected Functions¶

virtual bool can_edge_vertex_collide(
    size_t ei, size_t vi) const override;¶

virtual bool can_edges_collide(
    size_t eai, size_t ebi) const override;¶

virtual bool can_face_vertex_collide(
    size_t fi, size_t vi) const override;¶

virtual bool can_edge_face_collide(
    size_t ei, size_t fi) const override;¶

virtual bool can_faces_collide(
    size_t fai, size_t fbi) const override;¶

Protected Attributes¶

std::vector<scalable_ccd::AABB> vertex_boxes;¶

std::vector<scalable_ccd::AABB> edge_boxes;¶

std::vector<scalable_ccd::AABB> face_boxes;¶

mutable int vv_sort_axis = 0;¶

mutable int ev_sort_axis = 0;¶

mutable int ee_sort_axis = 0;¶

mutable int fv_sort_axis = 0;¶

mutable int ef_sort_axis = 0;¶

mutable int ff_sort_axis = 0;¶

Sweep and Tiniest Queue¶

AABB¶

class AABB;¶

Axis aligned bounding-box of some type.

Public Functions¶

AABB() = default;¶

AABB(Eigen::ConstRef<ArrayMax3d> min,
    Eigen::ConstRef<ArrayMax3d> max);¶

inline AABB(const AABB& aabb1, const AABB& aabb2);¶

inline AABB(
    const AABB& aabb1, const AABB& aabb2, const AABB& aabb3);¶

bool intersects(const AABB& other) const;¶

Check if another AABB intersects with this one.

Parameters:¶

const AABB &other¶

The other AABB.

Returns:¶

If the two AABBs intersect.

Public Members¶

ArrayMax3d min;¶

Minimum corner of the AABB.

ArrayMax3d max;¶

Maximum corner of the AABB.

std::array<index_t, 3> vertex_ids;¶

Vertex IDs attached to the AABB.

Public Static Functions¶

static AABB from_point(Eigen::ConstRef<VectorMax3d> p,
    const double inflation_radius = 0);¶

Construct an AABB for a static point.

Parameters:¶

Eigen::ConstRef<VectorMax3d> p¶

The point’s position.

const double inflation_radius = 0¶

Radius of a sphere around the point which the AABB encloses.

Returns:¶

The constructed AABB.

static inline AABB from_point(Eigen::ConstRef<VectorMax3d> p_t0,
    Eigen::ConstRef<VectorMax3d> p_t1,
    const double inflation_radius = 0);¶

Construct an AABB for a moving point (i.e.

temporal edge).

Parameters:¶

Eigen::ConstRef<VectorMax3d> p_t0¶

The point’s position at time t=0.

Eigen::ConstRef<VectorMax3d> p_t1¶

The point’s position at time t=1.

const double inflation_radius = 0¶

Radius of a capsule around the temporal edge which the AABB encloses.

Returns:¶

The constructed AABB.

static void conservative_inflation(Eigen::Ref<ArrayMax3d> min,
    Eigen::Ref<ArrayMax3d> max, const double inflation_radius);¶

Compute a conservative inflation of the AABB.