Broad Phase¶

Broad Phase¶

class BroadPhase;¶

Inheritance diagram for ipc::BroadPhase:

Collaboration diagram for ipc::BroadPhase:

Base class for broad phase collision detection methods.

Subclassed by ipc::BruteForce, ipc::HashGrid, ipc::LBVH, ipc::SpatialHash, ipc::SweepAndPrune, ipc::SweepAndTiniestQueue, ipc::cuda::LBVH

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 build(const AABBs& vertex_boxes,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces, const uint8_t dim);¶

Build the broad phase for collision detection.

Parameters:¶

const AABBs &vertex_boxes¶

AABBs for the vertices.

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

Collision mesh edges

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

Collision mesh faces

const uint8_t dim¶

Dimension of the simulation (2D or 3D)

virtual void clear();¶

Clear any built data.

void detect_collision_candidates(Candidates& candidates) const;¶

Detect all collision candidates needed for a given dimensional simulation.

Parameters:¶

Candidates &candidates¶

The detected collision candidates (cleared first).

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 (cleared first).

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 (cleared first).

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 (cleared first).

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 (cleared first).

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 (cleared first).

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 (cleared first).

Public Members¶

CollisionFilter can_vertices_collide;¶

Filter for determining if two vertices can collide.

Protected Functions¶

virtual void build(Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces);¶

Build the broad phase for collision detection.

Note

Assumes the vertex_boxes have been built.

Parameters:¶

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

Collision mesh edges

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

Collision mesh faces

void compute_mesh_aabb(Eigen::Ref<Eigen::Array3d> mesh_min,
    Eigen::Ref<Eigen::Array3d> mesh_max) const;¶

Compute the axis-aligned bounding box (AABB) of the mesh.

Parameters:¶

Eigen::Ref<Eigen::Array3d> mesh_min¶

[out] Minimum corner of the mesh AABB.

Eigen::Ref<Eigen::Array3d> mesh_max¶

[out] Maximum corner of the mesh AABB.

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¶

AABBs vertex_boxes;¶

AABBs for the vertices.

AABBs edge_boxes;¶

AABBs for the edges.

AABBs face_boxes;¶

AABBs for the faces.

uint8_t dim = 0;¶

Dimension of the simulation for which the broad phase was built.

Brute Force¶

class BruteForce : public ipc::BroadPhase;¶

Inheritance diagram for ipc::BruteForce:

Collaboration diagram for ipc::BruteForce:

Brute force broad phase collision detection.

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 AABBs& boxes0, const AABBs& 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 AABBs &boxes0¶

[in] First set of boxes.

const AABBs &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:

Hash grid broad phase collision detection.

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.

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 Eigen::Array3i& grid_size() const;¶

inline const Eigen::Array3d& domain_min() const;¶

inline const Eigen::Array3d& domain_max() const;¶

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 build(const AABBs& vertex_boxes,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces, const uint8_t dim);¶

Build the broad phase for collision detection.

Parameters:¶

const AABBs &vertex_boxes¶

AABBs for the vertices.

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

Collision mesh edges

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

Collision mesh faces

const uint8_t dim¶

Dimension of the simulation (2D or 3D)

virtual void build(Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces);¶

Build the broad phase for collision detection.

Note

Assumes the vertex_boxes have been built.

Parameters:¶

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

Collision mesh edges

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

Collision mesh faces

Protected Functions¶

virtual void build(Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces) override;

Build the broad phase for collision detection.

Note

Assumes the vertex_boxes have been built.

Parameters:¶

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

Collision mesh edges

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

Collision mesh faces

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

void insert_boxes();¶

void insert_boxes(
    const AABBs& 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 = -1;¶

Eigen::Array3i m_grid_size;¶

Eigen::Array3d m_domain_min;¶

Eigen::Array3d 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 AABBs& boxes0,
    const AABBs& 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 AABBs &boxes0¶

[in] First set’s boxes.

const AABBs &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 AABBs& 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 AABBs &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:

Spatial hash broad phase collision detection.

Public Functions¶

SpatialHash();¶

~SpatialHash();¶

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,
    const double inflation_radius = 0) override;¶

Build the spatial hash 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.

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,
    const double inflation_radius = 0) override;¶

Build the spatial hash 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.

inline virtual void build(const AABBs& _vertex_boxes,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    const uint8_t _dim) override;¶

Build the spatial hash from vertex boxes.

Parameters:¶

const AABBs &_vertex_boxes¶

AABB boxes for each vertex.

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

Collision mesh edges

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

Collision mesh faces

const uint8_t _dim¶

Dimension of the simulation (2D or 3D)

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

Build the spatial hash 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¶

Radius of inflation around all elements.

double voxel_size¶

Size of the voxels used in the spatial hash.

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

Build the spatial hash 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¶

Radius of inflation around all elements.

double voxel_size¶

Size of the voxels used in the spatial hash.

void build(const AABBs& vertex_boxes,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces, const uint8_t dim,
    double voxel_size);¶

Build the spatial hash from vertex boxes.

Parameters:¶

const AABBs &vertex_boxes¶

AABB boxes for each vertex.

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

Collision mesh edges

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

Collision mesh faces

const uint8_t dim¶

Dimension of the simulation (2D or 3D)

double voxel_size¶

Size of the voxels used in the spatial hash.

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.

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 build(const AABBs& vertex_boxes,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces, const uint8_t dim);

Build the broad phase for collision detection.

Parameters:¶

const AABBs &vertex_boxes

AABBs for the vertices.

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

Collision mesh edges

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

Collision mesh faces

const uint8_t dim

Dimension of the simulation (2D or 3D)

virtual void build(Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces);¶

Build the broad phase for collision detection.

Note

Assumes the vertex_boxes have been built.

Parameters:¶

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

Collision mesh edges

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

Collision mesh faces

Private Functions¶

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

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

Eigen::Array3i locate_voxel_axis_index(
    Eigen::ConstRef<Eigen::Array3d> p) const;¶

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

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

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

Private Members¶

Eigen::Array3d left_bottom_corner;¶

The left bottom corner of the world bounding box.

Eigen::Array3d right_top_corner;¶

The right top corner of the world bounding box.

Eigen::Array3i voxel_count;¶

The number of voxels in each dimension.

std::unique_ptr<Impl> impl;¶

Pointer to the implementation details.

double one_div_voxel_size = -1;¶

1.0 / voxel_size

int voxel_count_0x1 = -1;¶

The number of voxels in the first two dimensions.

struct Impl;¶

Public Functions¶

inline void fill_voxel_to_primitives();¶

inline void clear();¶

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.

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

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

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

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

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

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

Public Members¶

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.

int edge_start_ind = -1;¶

The index of the first edge in voxel_occupancies.

int tri_start_ind = -1;¶

The index of the first triangle in voxel_occupancies.

LBVH —

class LBVH : public ipc::BroadPhase;¶

Inheritance diagram for ipc::LBVH:

Collaboration diagram for ipc::LBVH:

Linear Bounding Volume Hierarchy (LBVH) broad phase collision detection.

Public Types¶

using Nodes = std::vector<Node, DefaultInitAllocator<Node>>;¶

using MortonCodeElements = std::vector<MortonCodeElement,
    DefaultInitAllocator<MortonCodeElement>>;¶

using RightmostLeaves
    = std::vector<int32_t, DefaultInitAllocator<int32_t>>;¶

For each node, the index of the rightmost leaf reachable from it.

Used to skip subtrees during triangular (self-collision) traversal.

Public Functions¶

LBVH();¶

~LBVH();¶

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

inline const Nodes& vertex_nodes() const;¶

inline const Nodes& edge_nodes() const;¶

inline const Nodes& face_nodes() const;¶

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 build(const AABBs& vertex_boxes,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces, const uint8_t dim);¶

Build the broad phase for collision detection.

Parameters:¶

const AABBs &vertex_boxes¶

AABBs for the vertices.

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

Collision mesh edges

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

Collision mesh faces

const uint8_t dim¶

Dimension of the simulation (2D or 3D)

virtual void build(Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces);¶

Build the broad phase for collision detection.

Note

Assumes the vertex_boxes have been built.

Parameters:¶

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

Collision mesh edges

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

Collision mesh faces

Public Members¶

Eigen::Array3d min;¶

Eigen::Array3d max;¶

Public Static Attributes¶

static constexpr index_t INVALID_ID = 0xFFFFFFFF;¶

Protected Functions¶

virtual void build(Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces) override;

Build the broad phase for collision detection.

Note

Assumes the vertex_boxes have been built.

Parameters:¶

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

Collision mesh edges

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

Collision mesh faces

void init_bvh(const AABBs& boxes, Nodes& lbvh,
    RightmostLeaves& rightmost_leaves) const;¶

Initialize a LBVH from a set of boxes.

Parameters:¶

const AABBs &boxes¶

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

Nodes &lbvh¶

[out] The LBVH to initialize.

RightmostLeaves &rightmost_leaves¶

[out] For each node, the rightmost leaf index reachable. Values are the leaf’s position in the Morton-sorted leaf array from [0, n) where n is the number of primitives.

inline bool has_vertices() const;¶

inline bool has_edges() const;¶

inline bool has_faces() const;¶

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¶

Nodes vertex_bvh;¶

BVH containing the vertices.

RightmostLeaves vertex_rightmost_leaves;¶

Rightmost leaf indices for vertex BVH (used for self-collision skip).

Values are from [0, n) where n is the number of primitives. Values are the leaf’s position in the Morton-sorted leaf array.

Nodes edge_bvh;¶

BVH containing the edges.

RightmostLeaves edge_rightmost_leaves;¶

Rightmost leaf indices for edge BVH (used for self-collision skip).

Values are from [0, n) where n is the number of primitives. Values are the leaf’s position in the Morton-sorted leaf array.

Nodes face_bvh;¶

BVH containing the faces.

RightmostLeaves face_rightmost_leaves;¶

Rightmost leaf indices for face BVH (used for self-collision skip).

Values are from [0, n) where n is the number of primitives. Values are the leaf’s position in the Morton-sorted leaf array.

Protected Static Functions¶

template <typename Candidate, bool swap_order = false,
    bool triangular = false>
static void detect_candidates(const Nodes& source,
    const Nodes& target, const RightmostLeaves& rightmost_leaves,
    const std::function<bool(size_t, size_t)>& can_collide,
    std::vector<Candidate>& candidates);¶

Detect candidate collisions between a LBVH 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 LBVH id when adding to the candidates.

bool triangular = false¶

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

Parameters:¶

const Nodes &source¶

[in] The LBVH to traverse.

const Nodes &target¶

[in] The LBVH to traverse.

const RightmostLeaves &rightmost_leaves¶

[in] The rightmost leaf indices for the target LBVH (used for self-collision skip).

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.

template <typename Candidate>
static inline void detect_candidates(const Nodes& source_and_target,
    const RightmostLeaves& rightmost_leaves,
    const std::function<bool(size_t, size_t)>& can_collide,
    std::vector<Candidate>& candidates);¶

Detect candidate collisions between a single LBVH and itself.

Template Parameters:¶

typename Candidate¶

Type of candidate collision.

Parameters:¶

const Nodes &source_and_target¶

[in] The LBVH to traverse.

const RightmostLeaves &rightmost_leaves¶

[in] The rightmost leaf indices for the LBVH (used for self-collision skip).

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.

Private Types¶

using HostConstructionInfo = ConstructionInfo<std::atomic<int>>;¶

using ConstructionInfos = std::vector<HostConstructionInfo,
    DefaultInitAllocator<HostConstructionInfo>>;¶

using EdgeIndices = std::vector<std::array<index_t, 2>,
    DefaultInitAllocator<std::array<index_t, 2>>>;¶

using FaceIndices = std::vector<std::array<index_t, 3>,
    DefaultInitAllocator<std::array<index_t, 3>>>;¶

Private Members¶

EdgeIndices edge_vertex_ids;¶

Edge vertices in the original mesh order.

FaceIndices face_vertex_ids;¶

Face vertices in the original mesh order.

struct ipc::LBVH mesh_aabb;¶

The axis-aligned bounding box of the entire mesh.

template <typename Counter> struct ConstructionInfo;¶

Per-internal-node scratch for the bottom-up build.

See also

ipc::details::build_hierarchy_from_leaf

Template Parameters:¶

typename Counter¶

The visitation counter’s type: std::atomic<int> here, and a plain int for the device build in ipc::cuda::LBVH, where atomicAdd() supplies the atomicity.

Public Members¶

int left_range;¶

Left range endpoint passed up by the left child.

int right_range;¶

Right range endpoint passed up by the right child.

Counter visitation_count;¶

Number of threads that arrived at this node.

struct MortonCodeElement;¶

Public Members¶

uint64_t morton_code;¶

Key for sorting.

size_t box_id;¶

Pointer into boxes buffer.

struct Node;¶

Public Functions¶

inline bool is_inner() const;¶

Check if this node is an inner node.

inline bool is_leaf() const;¶

Check if this node is a leaf node.

inline bool is_valid() const;¶

Check if this node is valid.

inline bool intersects(const Node& other) const;¶

Check if this node’s AABB intersects with another node’s AABB.

Public Members¶

Eigen::Array3f aabb_min;¶

The min corner of the AABB.

Eigen::Array3f aabb_max;¶

The max corner of the AABB.

Public Static Attributes¶

static constexpr int32_t INVALID_POINTER = 0x0;¶

Sweep and Prune¶

class SweepAndPrune : public ipc::BroadPhase;¶

Inheritance diagram for ipc::SweepAndPrune:

Collaboration diagram for ipc::SweepAndPrune:

Sweep and Prune broad phase collision detection.

Public Functions¶

SweepAndPrune();¶

~SweepAndPrune();¶

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 build(const AABBs& vertex_boxes,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces,
    const uint8_t dim) override;¶

Build the broad phase from precomputed AABBs.

Parameters:¶

const AABBs &vertex_boxes¶

Precomputed vertex AABBs

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

Collision mesh edges

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

Collision mesh faces

const uint8_t dim¶

Dimension of the simulation (2D or 3D)

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.

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 build(const AABBs& vertex_boxes,
    Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces, const uint8_t dim);

Build the broad phase for collision detection.

Parameters:¶

const AABBs &vertex_boxes¶

AABBs for the vertices.

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

Collision mesh edges

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

Collision mesh faces

const uint8_t dim¶

Dimension of the simulation (2D or 3D)

virtual void build(Eigen::ConstRef<Eigen::MatrixXi> edges,
    Eigen::ConstRef<Eigen::MatrixXi> faces);¶

Build the broad phase for collision detection.

Note

Assumes the vertex_boxes have been built.

Parameters:¶

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

Collision mesh edges

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

Collision mesh faces

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::unique_ptr<Boxes> 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;¶

struct Boxes;¶

Public Functions¶

~Boxes() = default;¶

Public Members¶

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

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

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