Changelog¶
v1.3.0 (Aug 03, 2024)¶
Separated the collision set and potential computations. This allows us to more easily add new potentials in the future. This will require updating calls to
compute_potential_*
. See the tutorial for details.Add a
Barrier
class to enable dynamic selection of barrier function.Add a
NarrowPhaseCCD
class to enable dynamic selection of narrow-phase CCD method.
Details¶
Refactor potentials in #83
Replace “constraint” and “contact” names with “collision”
Removed
compute_potential_*
fromCollision
andCollisions
Add a new class hierarchy
Potential
which represents computing the sum of individual potentials per collisionImplement the barrier potential and friction dissipative potential as Potentials:
BarrierPotential
andFrictionPotential
Now,
Collisions
serve solely as the set of active collisionsAdd the distance mollifier to all collisions with a
is_mollified()
functionThe default mollifier is $m(x) = 1$, and only
EdgeEdgeCollision
overrides this
Remove versions of
compute_distance
andccd
fromCollisionStencil
which take the full mesh as inputInstead, expose the versions that take the collision stencil’s vertex positions directly
Polymorphic barrier in #84
Make the barrier function an object so it can be changed at runtime
Add a virtual class
Barrier
as an interface for generic barriersAdd
ClampedLogBarrier
class which implements the smoothly clamped log barrier functions from [Li et al. 2020]barrier_gradient
andbarrier_hessian
renamed tobarrier_first_derivative
andbarrier_second_derivative
respectivelyCo-authored by @arvigj
Update compiler warnings in #88
Add
-Werror=enum-conversion
and-Wfloat-conversion
Fix 🐛 hash when not using Abseil in #90
Clean-up SpatialHash Broad Phase in #91
Replace
IPC_TOOLKIT_WITH_CORRECT_CCD
withIPC_TOOLKIT_WITH_INEXACT_CCD
Always include Tight Inclusion CCD because it is used by Nonlinear CCD
Add support for face-face collision (not used anywhere but for completeness and future-proof nonlinear face-face)
Add and use generic functions to
SpatialHash
Replace
camelCase
withsnake_case
inSpatialHash
andHashGrid
Update Scalable CCD in #92
Updated Scalable CCD (i.e., Sweep and Tiniest Queue and CUDA Tight Inclusion CCD) to the unified repository with support for generic collision pairs.
Renamed
SWEEP_AND_TINIEST_QUEUE
toSWEEP_AND_PRUNE
to reflect that it is a standard implementation of the sweep and prune algorithm (see, e.g., “Real-Time Collision Detection” [Ericson 2004])Renamed
SWEEP_AND_TINIEST_QUEUE_GPU
toSWEEP_AND_TINIEST_QUEUE
to reflect that it is the only existing implementation of the sweep and tiniest queue algorithm
Mark single argument constructors explicit in #93
Mark
BarrierPotential(double)
andFrictionPotential(double)
as explicit constructors to avoid implicit conversions from double
Add clang-format check action in #96
Add new project PSD option by @Huangzizhou in #95
Instead of clamping the negative eigenvalues to zero, add the option to flips the sign of negative eigenvalues according to [Chen et al. 2024]
Fix 🐛 Python bindings for Numpy 2 in #100
Make faces an optional parameter to
CollisionMesh
in #105Fix Python documentation by @rc in #108
Polymorphic CCD in #110
Add narrow phase CCD parent class; pass CCD object to choose method
Replace
tolerance
andmax_iterations
parameters withconst NarrowPhaseCCD& narrow_phase_ccd
parameterNarrowPhaseCCD
is a virtual class containing the CCD methods for point-point, point-edge, edge-edge, and point-triangle CCDNarrowPhaseCCD
is implemented byInexactCCD
,TightInclusionCCD
, andAdditiveCCD
classes[Breaking] The optional parameter order to
is_step_collision_free
andcompute_collision_free_stepsize
is changed fromconst BroadPhaseMethod broad_phase_method = DEFAULT_BROAD_PHASE_METHOD, const double min_distance = 0.0, const double tolerance = DEFAULT_CCD_TOLERANCE, const long max_iterations = DEFAULT_CCD_MAX_ITERATIONS);
to
const double min_distance = 0.0, const BroadPhaseMethod broad_phase_method = DEFAULT_BROAD_PHASE_METHOD, const NarrowPhaseCCD& narrow_phase_ccd = DEFAULT_NARROW_PHASE_CCD);
The inexact floating-point CCD can be enabled beside the Tight Inclusion CCD rather than replacing it
v1.2.1 (Jul 12, 2024)¶
Bug fixes 🐛 :
Update Pybind11 to support Numpy 2.0. Fixes segmentation fault as described in #102.
v1.2.0 (Dec 11, 2023)¶
Various new features 🚀 and some bug fixes 🐛.
Implement the improved max approximator as described in [Li et al. 2023]
Add a port of the Additive CCD method from [Li et al. 2021]
Add a generic implementation of the nonlinear CCD (of linear geometry) algorithm from [Ferguson et al. 2021]
Add missing codimensional collision support (point-point and point-edge)
Details¶
Simplify tangential basis Jacobian calculation thanks to @halehOssadat and @jpanetta in #56
Update
FindSIMD.cmake
to now add support for Neon (Arm/Apple Silicon SIMD instruction set) in #58Credit:
FindSIMD.cmake
from Project CHRONO under BSD 3-Clause “New” or “Revised” License.
Improve the max approximator used (i.e., sum over constraints) as described in [Li et al. 2023] in #55
Add a
dtype
to EE collisions to keep track of the distance type for mollified constraintsInitialize mesh adjacencies by default
Use edge length as the area weighting for codimensional edges
Improve documentation and tutorials in #61
Add documentation describing the convergent formulation
Add documentation describing the constraint offset/minimum distance
Add documentation for broad- and narrow-phase CCD
Add documentation for High-Order IPC
Also, renames
CollisionConstraint::minimum_distance
toCollisionConstraint::dmin
Add a port of the Additive CCD method from [Li et al. 2021] in #62
This is a modified version of the original open-source implementation which is under the Appache-2.0 License.
Modifications: remove broad phase functions, refactor code to use a single implementation of the
additive_ccd
algorithm, utilize our distance function rather than porting the Codim-IPC versions, returntrue
if the initial distance is less than the minimum distance, and add an explicittmax
parameter rather than relying on the initial value oftoi
.This is mostly for reference comparison and it is not integrated into the full code. This also includes the ability to pull the sample CCD queries and run them in a unit-test (requires GMP).
This adds missing feature mentioned in #63
Add Codecov to get a report of unit test code coverage in #64
Add more tests to improve code coverage and fix small bugs in #65
Fix the symmetric matrix assertion in
project_to_psd
andproject_to_pd
in #67Handle codim. point-point collisions in #66
This adds missing feature as discussed in #63
In CCD, check the initial distance when no motion occurs in #71
Add a generic implementation of the nonlinear CCD (of linear geometry) algorithm from [Ferguson et al. 2021] in #72
Generic nonlinear trajectories are specified through a
NonlinearTrajectory
virtual class. By default the maximum distance between the trajectory and a linearized version is computed using interval arithmetic. That is\[\begin{split}\max_{t \in [0, 1]} \Vert p(\mathrm{lerp}(t_0, t_1, t)) - \mathrm{lerp}(p(t_0), p(t_1), t) \Vert_2 \\ \leq \sup(\Vert p([t_0, t_1]) - \mathrm{lerp}(p(t_0), p(t_1), [0, 1]) \Vert_2)\end{split}\]where \(p\) is the point’s position over time, \(\mathrm{lerp}(a, b, t) := (b - a) t + a\) and \(\sup([a,b]):=b\). Because this can be an overly conservative approximation, users can override the
NonlinearTrajectory::max_distance_from_linear
function to compute the max directly in closed form, if known.We perform interval arithmetic using filib which has been shown to be “the only library that is correct, consistent, portable, and efficient” [Tang et al. 2022].
Add a nonlinear CCD tutorial to the docs in #78
Add additional compiler warnings and resolve them to be warning-free in #73
Add Python bindings for
igl::predicate::segment_segment_intersect
in #74Fix the shape derivative of mollified edge-edge contact in #76
Additionally, this makes the shape derivative computation object-oriented.
Update Python bindings with recent changes and unified comments in #77
Add support for collision between codimensional edges and points in 3D in #79
Implements missing features discussed in #63.
v1.1.1 (Aug 18, 2023)¶
Fix vertex-vertex
==
and<
functions to be order independentThis allows vertex-vertex constraints merge correctly
Update Tight Inclusion CCD
v1.1.0 (Jul 25, 2023)¶
Large refactoring to make the code more object-oriented rather than passing objects to functions. Other changes include the friction potential now being a function of velocity, bug fixes, and a new tutorial.
Details¶
Large Refactor in #25
construct_collision_candidates(..., candidates)
→candidates.build(...)
is_step_collision_free(candidates, ...)
→candidates.is_step_collision_free(...)
compute_collision_free_stepsize(candidates, ...)
→candidates.compute_collision_free_stepsize(...)
compute_barrier_potential*(constraints, ...)
→constraints.compute_potential*(...)
compute_shape_derivative(constraints, ...)
→constraints.compute_shape_derivative(...)
compute_minimum_distance(constraints, ...)
→constraints.compute_minimum_distance(...)
construct_friction_constraint_set(..., friction_constraints)
→friction_constraints.build(...)
compute_friction_*(..., friction_constraints, ...)
→friction_constraints.compute_*(...)
Generic
CollisionStencil
parent class toCandidates
,CollisionConstraints
, andFrictionConstraints
.Renamed
Constraints
toCollisionConstraints
Replaced single letter variable names
V
,E
,F
withvertices
/positions
,edges
,faces
Renamed
*_index
→*_id
Replaced
inflation_radius = min_distance / 1.99
withinflation_radius = min_distance / 2
and use rounding mode to conservativly inflate AABBsCollisionConstraints::use_convergent_formulation
andare_shape_derivatives_enabled
must now be accessed through getter and setter functionsFriction potentials are now functions of velocity. Previously
V0
andV1
were passed andU = V1-V0
. This limited the integration scheme to implicit Euler. Upstream this means you need to multiply the potential by \(1/(dv/dx)\) to get the correct friction force.Change input \(\epsilon_vh\) to \(\epsilon_v\) in #37 to reflect the fact that friction is defined in terms of velocity instead of displacement now.
Changed default
project_hessian_to_psd
tofalse
in #30Update website with a tutorial (#31) and version dropdown list (#34)
Switch from templates to using
Eigen::Ref
in #28Speed up the CCD by limiting the maximum minimum distance to
1e-4
in #43Fix the bug pointed out in #41 in #42. Namely, to get units of distance in the barrier we should divide the original function by \(\hat{d}\cdot(\hat{d} + 2d_{\min})^2\) when using distance squared. Before it was being divided by \(2d_{\min} \hat{d} + \hat{d}^2\).
Fix build for IPC_TOOLKIT_WITH_CORRECT_CCD=OFF in #44
Switched from FetchContent to CPM in #48. This provides better caching between builds. Additionally, made robin-map and Abseil optional dependencies.
Add the CFL-Inspired Culling of CCD as described in Section 3 of the Technical Supplement to IPC in #50
v1.0.0 (Feb 21, 2023)¶
This is the first official release. 🚀
This is a stable release of the toolkit prior to refactoring the code and making updates to the API.
Details¶
Added a minimum distance optional parameter to all CCD functions (
const double min_distance = 0.0
) in #22. This is placed as the first optional argument which can break calling code if optional parameters were previously used.Added
CollisionMesh
in #7 to wrap up face and edges into a single data structure.Removes Support for ignoring internal vertices. Instead, users should use the CollisionMesh to map from the full mesh to the surface mesh.
This also includes a
to_full_dof
function that can map the reduced gradient/hessian to the full mesh’s DOF.
Pre-v1.0.0¶
2021-10-05 (9e2cc2a)¶
Added¶
Added implicits source folder to organize point-plane collisions
2021-09-05 (9e2cc2a)¶
Added¶
Added support for point vs. (static) analytical plane contact
2021-08-21 (acf2a80)¶
Changed¶
Changed CMake target name to
ipc::toolkit
2021-07-26 (1479aae)¶
Changed¶
Updated the CMake system to use modern
FetchContent
to download externals
2021-07-22 (e24c76d)¶
Fixed¶
Updated CCD strategy when using Tight Inclusion to only perform
no_zero_toi=true
when there is no minimum distance
2021-07-17 (a20f7a2)¶
Added¶
Added
detect_edge_face_collision_candidates_brute_force
for 3D intersection broad-phaseAdded ability to save an obj of collision candidates
Added tests for has_intersection (all pass after fixes)
Fixed¶
Fixed possible numerical rounding problems in HashGrid
AABB::are_overlapping
Fixed HashGrid’s function for getting edge-face intersection candidates
2021-07-15 (7301b42)¶
Fixed¶
Use
ignore_codimensional_vertices
in the brute force broad-phase methodFixed AABB inflation in brute force and SpatialHash methods
2021-07-08 (86ae4e5)¶
Changed¶
Replaced vertex group ids with more powerful can_collide function. By default everything can collide with everything (same as before)
Reordered parameters in
construct_constraint_set()
,is_collision_free()
, andcompute_collision_free_stepsize()
update_barrier_stiffness
now requires theconstraint_set
rather than building itupdate_barrier_stiffness
dropped dhat parameter
Fixed¶
SpatialHash for 2D
Removed¶
Verison of
initial_barrier_stiffness
that computes the constraint set and barrier gradient because there are a lot of parameters to these functions
2021-07-05 (4d16954)¶
Changed¶
Renamed directory
src/spatial_hash/
→src/broad_phase/
Renamed files
src/ccd/broad_phase.*
→src/ccd/aabb.*
2021-07-05 (b3808e1)¶
Added¶
Select the broad-phase method for CCD and distance constraints
Methods:
HASH_GRID
,SPATIAL_HASH
,BRUTE_FORCE
CCD parameters for Tight Inclusion’s tolerance and maximum iterations
Changed¶
ignore_codimensional_vertices
tofalse
by defaultCMake option
TIGHT_INCLUSION_WITH_NO_ZERO_TOI=ON
as default
2021-06-18 (aa59aeb)¶
Changed¶
construct_friction_constraint_set
now clears the givenfriction_constraint_set
2021-05-18 (245b13b)¶
Changed¶
Use TightInclusion degenerate edge-edge for point-point and point-edge CCD
2021-05-11 (5c34dcd)¶
Changed¶
char*
exceptions tostd::exceptions
2021-05-06 (24056cc)¶
Changed¶
Gave
dhat_epsilon_scale
a default value of1e-9
inupdate_barrier_stiffness
- warning:
Changed order of parameters to
update_barrier_stiffness
Flipped
bbox_diagonal
anddhat_epsilon_scale
2021-05-06 (81d65f3)¶
Fixed¶
Bug in output min distance of
update_barrier_stiffness
2021-05-04 (59ec167)¶
Changed¶
Moved eigen_ext functions into ipc namespace
Renamed max size matrices with
Max
Eigen::VectorX([0-9])
→ipc::VectorMax$1
Eigen::MatrixXX([0-9])
→ipc::VectorMax$1
Eigen::ArrayMax([0-9])
→ipc::ArrayMax$1
2021-05-03 (664d65f)¶
Added¶
Added utility function to check for edge-edge intersection in 2D and edge-triangle intersection in 3D.
Optionally: use GMP for exact edge-triangle intersection checks
2021-05-03 (9b4ebfc)¶
Added¶
voxel_size_heuristic.cpp which suggests a good voxel size for the
SpatialHash
andHashGrid
Changed¶
Changed HashGrid voxel size to be the average edge length not considering displacement length. This results in better performance, but can result in large memory usage.
2021-04-29 (293d0ad)¶
Added¶
Added TBB parallel loops to the main function (
compute_potential
,compute_friction_potential
,compute_collision_free_stepsize
, etc.)Added function
addVerticesFromEdges
that adds the vertices connected to edges in parallel and avoids duplicates
Changed¶
Changed the HashGrid to use
ArrayMax3
overVectorX3
to simplify the code
Fixed¶
Fixed some parameters that were not by reference
2021-04-21 (c8a6d5)¶
Added¶
Added the SpatialHash from the original IPC code base with some modification to get all candidates in parallel
Benchmark results indicate this SpatialHash is faster than the HashGrid with multithreading
TODO: Improve HashGrid or fully integrate SpatialHash into ipc.hpp
2021-02-11 (9c7493)¶
Changed¶
Switched to the correct (conservative) CCD of Wang et al. [2021]
Can select Etienne Vouga’s CCD in the CMake (see README.md)
2021-02-01 (b510253)¶
Added¶
Added minimum seperation distance (thickness) to distance constraints
Based on “Codimensional Incremental Potential Contact” [Li et al., 2021]
2021-02-01 (a395175)¶
Added¶
Added 2D friction model based on the 3D formulation.
TODO: Test this further
2021-01-12 (deee6d0)¶
Added¶
Added and optional parameter
F2E
toconstruct_constraint_set()
. This is similar toF
(which maps faces to vertices), but maps faces to edges. This is optional, but recommended for better performance. If not provided a simple linear search will be done per face edge!TODO: Add a function to compute this mapping.
2021-01-09 (deee6d0)¶
Changed¶
Replaced VectorXd and MatrixXd with static size versions for local gradient and hessians
2020-11-20 (93143ad)¶
Changed¶
Removed TBB parallelization form the hash grid because we get better performance without it.
TODO: Improve parallelization in the hash grid or switch to the original IPC spatial hash
2020-11-06 (4553509)¶
Fixed¶
Fixed multiplicity for point-triangle distance computation to avoid duplicate point-point and point-edge pairs.
2020-10-22 (51f4903)¶
Fixed¶
Projection of the hessian to PSD. This was completely broken as the projected matrix was never used.
2020-10-22 (9be6c0f)¶
Fixed¶
Mollification of EE constraints that have a distance type of PP or PE
If there is no mollification needed then the PP and PE constraints are stored with multiplicity
Set the parallel EE friction constraint threshold to eps_x like in IPC
This avoid needing the mollification for the normal force and these forces are small anyways
2020-10-10 (cb8b53f)¶
Fixed¶
Assertions in
compute_collision_free_stepsize
2020-10-10 (4a5f84f)¶
Fixed¶
Point-triangle distance type by replacing it with the one used in the original IPC code
2020-10-10 (1d51a61)¶
Added¶
Boolean parameter in
compute_friction_potential_hessian
that controls if the hessian is projected to PSD
2020-10-09 (b737fb0)¶
Added¶
Parameter for vertex group IDs to exclude some collisions (e.g., self collisions)
2020-10-08 (6ee60ae)¶
Added¶
Second version of
update_barrier_stiffness()
that takes an already computed minimum distance and world bounding box diagonal
2020-10-08 (cc3947d)¶
Added¶
Second version of
initial_barrier_stiffness()
that takes an already computed barrier gradientAssertions on
initial_barrier_stiffness()
inputaverage_mass > 0 && min_barrier_stiffness_scale > 0
Changed¶
Fixed typo in
initial_barrier_stiffness()
name (wasintial_barrier_stiffness()
)
2020-10-07 (5582582)¶
Added¶
FrictionConstraint
structures to store friction information (i.e., tangent basis, normal force magnitude, closest points, and coefficient of friction)Unit test that compares the original IPC code’s friction components with the toolkit’s
Changed¶
compute_friction_bases()
is nowconstruct_friction_constraint_set()
It now takes the coefficient of friction (
mu
)It now puts all information inside of the
FrictionConstraints
(friction_constraint_set
)
2020-10-06 (b48ba0e)¶
Changed¶
During
construct_constraint_set()
the constraints are added based on distance typeDuplicate vertex-vertex and edge-vertex constraints are handled by a multiplicity multiplier
Edge-edge constraints are always line-line distances
Point-triangle constraints are always point-plane distances
2020-10-05 (9a4576b)¶
Fixed¶
Fixed a bug in the point-triangle closest points and tangent basis computed in
compute_friction_bases()
Fixed a bug in
edge_edge_tangent_basis()
used to compute the tangent basis for friction
2020-09-19 (31a37e0)¶
Added¶
spdlog for logging information
2020-09-19 (acb7664)¶
Changed¶
Headers are now include with the prefix
ipc/
E.g.,
#include <ipc.hpp>
→#include <ipc/ipc.hpp>
2020-09-04 (7dd2ab7)¶
Added¶
Collision constraint to store distance constraint pairs
EdgeEdgeConstraint
stores the edge-edge mollifier threshold (eps_x
)
Changed¶
Input parameter
dhat_squared
is nowdhat
(i.e., non-squared value)Input parameter
epsv_times_h_squared
is nowepsv_times_h
(i.e., non-squared value)Constraints
replacedCandidates
construct_constraint_set()
now takes the rest vertex position (V_rest
)compute_barrier_potential*()
no longer take the rest vertex position