Broad Phase¶

enum class ipc::BroadPhaseMethod;¶

Enumeration of implemented broad phase methods.

Values:

enumerator BRUTE_FORCE;¶

enumerator HASH_GRID;¶

enumerator SPATIAL_HASH;¶

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

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.

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

virtual void detect_edge_vertex_candidates( std::vector<EdgeVertexCandidate>& candidates) const = 0;¶

Find the candidate edge-vertex collisisons.

Parameters:¶

std::vector<EdgeVertexCandidate> &candidates¶: [out] The candidate edge-vertex collisisons.

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

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

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::unique_ptr<BroadPhase> make_broad_phase( const BroadPhaseMethod broad_phase_method);¶

Construct a registered broad phase object.

Parameters:¶

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

Returns:¶

The constructed broad phase object.

static inline bool default_can_vertices_collide(size_t, size_t);¶

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

Brute Force¶

class BruteForce : public ipc::BroadPhase;¶

Public Functions¶

virtual void detect_edge_vertex_candidates( std::vector<EdgeVertexCandidate>& candidates) const override;¶: Find the candidate edge-vertex collisisons.

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_edge_vertex_candidates( std::vector<EdgeVertexCandidate>& candidates) const override;¶

Find the candidate edge-vertex collisisons.

Parameters:¶

std::vector<EdgeVertexCandidate> &candidates¶: [out] The candidate edge-vertex collisisons.

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

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

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

void build(const Eigen::MatrixXd& vertices_t0, const Eigen::MatrixXd& vertices_t1, const Eigen::MatrixXi& edges, const Eigen::MatrixXi& faces, double inflation_radius, double voxelSize);¶

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

void queryPointForTriangles(const VectorMax3d& p, unordered_set<int>& triInds, double radius = 0) const;¶

void queryPointForTriangles(const VectorMax3d& p_t0, const VectorMax3d& p_t1, unordered_set<int>& triInds, double radius = 0) const;¶

void queryPointForPrimitives(const VectorMax3d& p_t0, const VectorMax3d& p_t1, unordered_set<int>& vertInds, unordered_set<int>& edgeInds, unordered_set<int>& triInds, double radius = 0) const;¶

void queryEdgeForPE(const VectorMax3d& e0, const VectorMax3d& e1, std::vector<int>& vertInds, std::vector<int>& edgeInds, double radius = 0) const;¶

void queryEdgeForEdges(const VectorMax3d& ea0, const VectorMax3d& ea1, std::vector<int>& edgeInds, double radius = 0, int eai = -1) const;¶

void queryEdgeForEdgesWithBBoxCheck(const Eigen::MatrixXd& vertices, const Eigen::MatrixXi& edges, const VectorMax3d& ea0, const VectorMax3d& ea1, std::vector<int>& edgeInds, double radius = 0, int eai = -1) const;¶

void queryEdgeForEdges(const VectorMax3d& ea0_t0, const VectorMax3d& ea1_t0, const VectorMax3d& ea0_t1, const VectorMax3d& ea1_t1, std::vector<int>& edgeInds, double radius = 0, int eai = -1) const;¶

void queryTriangleForPoints(const VectorMax3d& t0, const VectorMax3d& t1, const VectorMax3d& t2, unordered_set<int>& pointInds, double radius = 0) const;¶

void queryTriangleForPoints(const VectorMax3d& t0_t0, const VectorMax3d& t1_t0, const VectorMax3d& t2_t0, const VectorMax3d& t0_t1, const VectorMax3d& t1_t1, const VectorMax3d& t2_t1, unordered_set<int>& pointInds, double radius = 0) const;¶

void queryTriangleForEdges(const VectorMax3d& t0, const VectorMax3d& t1, const VectorMax3d& t2, unordered_set<int>& edgeInds, double radius = 0) const;¶

void queryEdgeForTriangles(const VectorMax3d& e0, const VectorMax3d& e1, unordered_set<int>& triInds, double radius = 0) const;¶

void queryPointForPrimitives(int vi, unordered_set<int>& vertInds, unordered_set<int>& edgeInds, unordered_set<int>& triInds) const;¶

void queryPointForEdges(int vi, unordered_set<int>& edgeInds) const;¶

void queryPointForTriangles( int vi, unordered_set<int>& triInds) const;¶

void queryEdgeForEdges(int eai, unordered_set<int>& edgeInds) const;¶

void queryEdgeForEdgesWithBBoxCheck( const Eigen::MatrixXd& vertices_t0, const Eigen::MatrixXd& vertices_t1, const Eigen::MatrixXi& edges, int eai, unordered_set<int>& edgeInds) const;¶

void queryEdgeForTriangles( int ei, unordered_set<int>& triInds) const;¶

virtual void detect_edge_vertex_candidates( std::vector<EdgeVertexCandidate>& candidates) const override;¶: Find the candidate edge-vertex collisisons.

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

ArrayMax3d rightTopCorner;¶

ArrayMax3i voxelCount;¶

double one_div_voxelSize;¶

int voxelCount0x1;¶

int edgeStartInd;¶

int triStartInd;¶

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

std::vector<std::vector<int>> pointAndEdgeOccupancy;¶

Protected Functions¶

int locateVoxelIndex(const VectorMax3d& p) const;¶

void locateVoxelAxisIndex( const VectorMax3d& p, ArrayMax3i& voxelAxisIndex) const;¶

void locateBoxVoxelAxisIndex(ArrayMax3d minCorner, ArrayMax3d maxCorner, ArrayMax3i& minIndex, ArrayMax3i& maxIndex, const double inflation_radius = 0) const;¶

int voxelAxisIndex2VoxelIndex( const ArrayMax3i& voxelAxisIndex) const;¶

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

Protected Attributes¶

int dim;¶

double builtInRadius;¶

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_edge_vertex_candidates( std::vector<EdgeVertexCandidate>& candidates) const override;¶

Find the candidate edge-vertex collisisons.

Parameters:¶

std::vector<EdgeVertexCandidate> &candidates¶: [out] The candidate edge-vertex collisisons.

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

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

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

Public Members¶

ArrayMax3d min;¶

ArrayMax3d max;¶

std::array<long, 3> vertex_ids;¶

Public Static Functions¶

static AABB from_point( const VectorMax3d& p, const double inflation_radius = 0);¶: Compute a AABB for a static point.

static inline AABB from_point(const VectorMax3d& p_t0, const VectorMax3d& p_t1, const double inflation_radius = 0);¶: Compute a AABB for a moving point (i.e. temporal edge).

static void conservative_inflation(ArrayMax3d& min, ArrayMax3d& max, const double inflation_radius);¶: Compute a conservative inflation of the AABB.