Broad Phase - IPC Toolkit

enum class ipc::BroadPhaseMethod¶

Enumeration of implemented broad phase methods.

Values:

enumerator BRUTE_FORCE¶

enumerator HASH_GRID¶

enumerator SPATIAL_HASH¶

enumerator BVH¶

enumerator SWEEP_AND_PRUNE¶

enumerator SWEEP_AND_TINIEST_QUEUE¶

enumerator NUM_METHODS¶

static constexpr BroadPhaseMethod ipc::DEFAULT_BROAD_PHASE_METHOD
    = BroadPhaseMethod::HASH_GRID¶

class BroadPhase¶

Inheritence diagram for ipc::BroadPhase:

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

Public Functions

inline virtual ~BroadPhase()¶

virtual void build(const Eigen::MatrixXd& vertices, const Eigen::MatrixXi& edges, const Eigen::MatrixXi& faces, const double inflation_radius = 0)¶

Build the broad phase for static collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices¶: Vertex positions
const Eigen::MatrixXi &edges¶: Collision mesh edges
const Eigen::MatrixXi &faces¶: Collision mesh faces
const double inflation_radius = 0¶: Radius of inflation around all elements.

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

Build the broad phase for continuous collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices_t0¶: Starting vertices of the vertices.
const Eigen::MatrixXd &vertices_t1¶: Ending vertices of the vertices.
const Eigen::MatrixXi &edges¶: Collision mesh edges
const Eigen::MatrixXi &faces¶: Collision mesh faces
const double inflation_radius = 0¶: Radius of inflation around all elements.

virtual void clear()¶: Clear any built data.

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.

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

Public Members

std::function<bool(size_t, size_t)> can_vertices_collide = default_can_vertices_collide ¶: Function for determining if two vertices can collide.

Public Static Functions

static std::shared_ptr<BroadPhase> make_broad_phase( const BroadPhaseMethod method)¶

Construct a registered broad phase object.

Parameters:¶

const BroadPhaseMethod method¶: The broad phase method to use.

Returns:¶

The constructed broad phase object.

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

class BruteForce : public ipc::BroadPhase¶

Inheritence diagram for ipc::BruteForce:

Collaboration diagram for ipc::BruteForce:

Public Functions

BruteForce() = default¶

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.

class HashGrid : public ipc::BroadPhase¶

Inheritence diagram for ipc::HashGrid:

Collaboration diagram for ipc::HashGrid:

Public Functions

HashGrid() = default¶

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

Build the broad phase for static collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices¶: Vertex positions
const Eigen::MatrixXi &edges¶: Collision mesh edges
const Eigen::MatrixXi &faces¶: Collision mesh faces
double inflation_radius = 0¶: Radius of inflation around all elements.

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

Build the broad phase for continuous collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices_t0¶: Starting vertices of the vertices.
const Eigen::MatrixXd &vertices_t1¶: Ending vertices of the vertices.
const Eigen::MatrixXi &edges¶: Collision mesh edges
const 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(const ArrayMax3d& domain_min, const 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.

class SpatialHash : public ipc::BroadPhase¶

Inheritence diagram for ipc::SpatialHash:

Collaboration diagram for ipc::SpatialHash:

Public Functions

SpatialHash() = default¶

inline SpatialHash(const Eigen::MatrixXd& vertices, const Eigen::MatrixXi& edges, const Eigen::MatrixXi& faces, double inflation_radius = 0, double voxel_size = -1)¶

inline SpatialHash(const Eigen::MatrixXd& vertices_t0, const Eigen::MatrixXd& vertices_t1, const Eigen::MatrixXi& edges, const Eigen::MatrixXi& faces, double inflation_radius = 0, double voxel_size = -1)¶

inline virtual void build(const Eigen::MatrixXd& vertices, const Eigen::MatrixXi& edges, const Eigen::MatrixXi& faces, double inflation_radius = 0) override¶

Build the broad phase for static collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices¶: Vertex positions
const Eigen::MatrixXi &edges¶: Collision mesh edges
const Eigen::MatrixXi &faces¶: Collision mesh faces
double inflation_radius = 0¶: Radius of inflation around all elements.

inline virtual void build(const Eigen::MatrixXd& vertices_t0, const Eigen::MatrixXd& vertices_t1, const Eigen::MatrixXi& edges, const Eigen::MatrixXi& faces, double inflation_radius = 0) override¶

Build the broad phase for continuous collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices_t0¶: Starting vertices of the vertices.
const Eigen::MatrixXd &vertices_t1¶: Ending vertices of the vertices.
const Eigen::MatrixXi &edges¶: Collision mesh edges
const Eigen::MatrixXi &faces¶: Collision mesh faces
double inflation_radius = 0¶: Radius of inflation around all elements.

void build(const Eigen::MatrixXd& vertices, const Eigen::MatrixXi& edges, const Eigen::MatrixXi& faces, double inflation_radius, double voxel_size)¶

void build(const Eigen::MatrixXd& vertices_t0, const Eigen::MatrixXd& vertices_t1, const Eigen::MatrixXi& edges, const 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(const VectorMax3d& p) const¶

ArrayMax3i locate_voxel_axis_index(const VectorMax3d& p) const¶

void locate_box_voxel_axis_index(ArrayMax3d min_corner, ArrayMax3d max_corner, ArrayMax3i& min_index, ArrayMax3i& max_index, const double inflation_radius = 0) const¶

int voxel_axis_index_to_voxel_index( const 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.

class BVH : public ipc::BroadPhase¶

Inheritence diagram for ipc::BVH:

Collaboration diagram for ipc::BVH:

Public Functions

BVH() = default¶

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

Build the broad phase for static collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices¶: Vertex positions
const Eigen::MatrixXi &edges¶: Collision mesh edges
const Eigen::MatrixXi &faces¶: Collision mesh faces
const double inflation_radius = 0¶: Radius of inflation around all elements.

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

Build the broad phase for continuous collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices_t0¶: Starting vertices of the vertices.
const Eigen::MatrixXd &vertices_t1¶: Ending vertices of the vertices.
const Eigen::MatrixXi &edges¶: Collision mesh edges
const 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.

class SweepAndPrune : public ipc::BroadPhase¶

Inheritence diagram for ipc::SweepAndPrune:

Collaboration diagram for ipc::SweepAndPrune:

Public Functions

SweepAndPrune() = default¶

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

Build the broad phase for static collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices¶: Vertex positions
const Eigen::MatrixXi &edges¶: Collision mesh edges
const Eigen::MatrixXi &faces¶: Collision mesh faces
double inflation_radius = 0¶: Radius of inflation around all elements.

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

Build the broad phase for continuous collision detection.

Parameters:¶

const Eigen::MatrixXd &vertices_t0¶: Starting vertex positions
const Eigen::MatrixXd &vertices_t1¶: Ending vertex positions
const Eigen::MatrixXi &edges¶: Collision mesh edges
const 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¶

class AABB¶

Axis aligned bounding-box of some type.

Public Functions

AABB() = default¶

AABB(const ArrayMax3d& min, const 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<long, 3> vertex_ids¶: Vertex IDs attached to the AABB.

Public Static Functions

static AABB from_point( const VectorMax3d& p, const double inflation_radius = 0)¶

Construct an AABB for a static point.

Parameters:¶

const 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(const VectorMax3d& p_t0, const VectorMax3d& p_t1, const double inflation_radius = 0)¶

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

temporal edge).

Parameters:¶

const VectorMax3d &p_t0¶: The point’s position at time t=0.
const 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(ArrayMax3d& min, ArrayMax3d& max, const double inflation_radius)¶: Compute a conservative inflation of the AABB.

Broad Phase¶

Broad Phase¶

Brute Force¶

Hash Grid¶

Spatial Hash¶

BVH¶

Sweep and Prune¶

Sweep and Tiniest Queue¶

AABB¶