Broad Phase¶

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

enumerator SWEEP_AND_TINIEST_QUEUE_GPU¶

enumerator NUM_METHODS¶

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

Broad Phase¶

class BroadPhase¶

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

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

Protected Attributes

std::vector<AABB> vertex_boxes¶

std::vector<AABB> edge_boxes¶

std::vector<AABB> face_boxes¶

Protected Static Functions

static inline bool default_can_vertices_collide(size_t, size_t)¶

Brute Force¶

class BruteForce : public ipc::BroadPhase¶

Public Functions

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.

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¶

Hash Grid¶

class HashGrid : public ipc::BroadPhase¶

Public Functions

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.

inline double cellSize() const¶

inline const ArrayMax3i& gridSize() const¶

inline const ArrayMax3d& domainMin() const¶

inline const ArrayMax3d& domainMax() const¶

Protected Functions

void resize(
    const ArrayMax3d& min, const ArrayMax3d& max, double cellSize)¶

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

ArrayMax3i m_gridSize¶

ArrayMax3d m_domainMin¶

ArrayMax3d m_domainMax¶

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¶

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¶

Spatial Hash¶

class SpatialHash : public ipc::BroadPhase¶

Public Functions

inline SpatialHash()¶

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.

Public Members

ArrayMax3d left_bottom_corner¶

ArrayMax3d right_top_corner¶

ArrayMax3i voxel_count¶

double one_div_voxelSize¶

int voxel_count_0x1¶

int edge_start_ind¶

int tri_start_ind¶

unordered_map<int, std::vector<int>> voxel¶

std::vector<std::vector<int>> point_and_edge_occupancy¶

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¶

int locate_voxel_index(const VectorMax3d& p) const¶

void locate_voxel_axis_index(
    const VectorMax3d& p, ArrayMax3i& voxel_axis_index) 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 voxelAxisIndex2VoxelIndex(
    const ArrayMax3i& voxel_axis_index) const¶

int voxelAxisIndex2VoxelIndex(int ix, int iy, int iz) const¶

Protected Attributes

int dim¶

double built_in_radius¶

BVH¶

class BVH : public ipc::BroadPhase¶

Public Functions

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.

Protected Attributes

SimpleBVH::BVH vertex_bvh¶

SimpleBVH::BVH edge_bvh¶

SimpleBVH::BVH face_bvh¶

Protected Static Functions

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

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

Sweep and Tiniest Queue¶

class SweepAndTiniestQueue : public ipc::CopyMeshBroadPhase¶

Public Functions

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.

Protected Functions

long to_edge_id(long id) const¶

long to_face_id(long id) const¶

bool is_vertex(long id) const¶

bool is_edge(long id) const¶

bool is_face(long id) const¶

Protected Attributes

std::vector<stq::cpu::Aabb> boxes¶

std::vector<std::pair<int, int>> overlaps¶

long num_vertices¶

AABB¶

class AABB¶

Axis aligned bounding-box of some type.

Public Functions

inline AABB()¶

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.