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.


Last update: Nov 12, 2023