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, bool all_types = false) const;¶

Detect all collision candidates needed for a given dimensional simulation.

Parameters:¶

Candidates &candidates¶

The detected collision candidates (cleared first).

bool all_types = false¶

Also detect the candidate types that only ESP contact needs (vertex-vertex, edge-vertex, edge-face, and face-face in 3D).

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.

void query_point(Eigen::ConstRef<RowVectorMax3d> q, double radius,
    std::vector<index_t>& vertex_ids,
    std::vector<index_t>& edge_ids,
    std::vector<index_t>& face_ids) const;¶

Find the primitives whose AABB is within a radius of a point.

We test the built boxes against a box of half-width radius centered at q, so this is a broad phase only: callers still need an exact distance check. The tree is typically built with zero inflation so one build serves queries at any radius, since we apply the radius to the query box instead.

Parameters:¶

Eigen::ConstRef<RowVectorMax3d> q¶

Query point (2D or 3D, matching the mesh).

double radius¶

Half-width of the query box around q.

std::vector<index_t> &vertex_ids¶

[out] Ids of the nearby vertices.

std::vector<index_t> &edge_ids¶

[out] Ids of the nearby edges.

std::vector<index_t> &face_ids¶

[out] Ids of the nearby faces. Empty in 2D, where no face tree is built.

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