Changelog¶

v1.3.1 (Nov 08, 2024)¶

Move test data to an external repository in #113
- Download test data at compile time as needed using CMake
Individual convergent formulation flags in #120
- Replace the use_convergent_formulation flag in Collisions with two flags: use_area_weighting and use_improved_max_approximator.
- Move the physical barrier rescaling from collision weights into the BarrierPotential using a flag use_physcial_barrier.
Replace scalar tbb::enumerable_thread_specific with tbb::parallel_reduce in #121
Fix missing max_iterations and tolerance variables in compute_collision_free_stepsize when using SWEEP_AND_TINIEST_QUEUE by @antoinebou12 in #123
Add cuda.yml to test if the code compile with CUDA enabled in #125
Update filib to allow shared library build in #122
Fix friction_collisions.build tutorial (Issue #126) in #127
Sort includes using clang-format in #129
Add frequently asked questions page to the tutorial documentation
Fix barrier API documentation
On Apple, link Eigen against Accelerate as a BLAS/LAPACK backend
- Requires brew install lapack to install LAPACKE headers

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_* from Collision and Collisions
- Add a new class hierarchy Potential which represents computing the sum of individual potentials per collision
  - Implement the barrier potential and friction dissipative potential as Potentials: BarrierPotential and FrictionPotential
- Now, Collisions serve solely as the set of active collisions
- Add the distance mollifier to all collisions with a is_mollified() function
  - The default mollifier is $m(x) = 1$, and only EdgeEdgeCollision overrides this
- Remove versions of compute_distance and ccd from CollisionStencil which take the full mesh as input
  - Instead, 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 barriers
- Add ClampedLogBarrier class which implements the smoothly clamped log barrier functions from [Li et al. 2020]
- barrier_gradient and barrier_hessian renamed to barrier_first_derivative and barrier_second_derivative respectively
- Co-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 with IPC_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 with snake_case in SpatialHash and HashGrid
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 to SWEEP_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 to SWEEP_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) and FrictionPotential(double) as explicit constructors to avoid implicit conversions from double
Fix compatibility with the latest Eigen by @teseoch in #94
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 #105
Fix Python documentation by @rc in #108
Polymorphic CCD in #110
- Add narrow phase CCD parent class; pass CCD object to choose method
- Replace tolerance and max_iterations parameters with const NarrowPhaseCCD& narrow_phase_ccd parameter
- NarrowPhaseCCD is a virtual class containing the CCD methods for point-point, point-edge, edge-edge, and point-triangle CCD
- NarrowPhaseCCD is implemented by InexactCCD, TightInclusionCCD, and AdditiveCCD classes
- [Breaking] The optional parameter order to is_step_collision_free and compute_collision_free_stepsize is changed from
```
const 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¶

Update website URL to ipctk.xyz in #54
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 #58
- Credit: 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 constraints
- Initialize 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 to CollisionConstraint::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, return true if the initial distance is less than the minimum distance, and add an explicit tmax parameter rather than relying on the initial value of toi.
- 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 and project_to_pd in #67
Handle codim. point-point collisions in #66
- This adds missing feature as discussed in #63
Add tests of Python bindings using nose2 in #69
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 #74
Integrate SimpleBVH as a broad-phase method in #75
Fix 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)¶

Logo by @zfergus in #52
Fix vertex-vertex == and < functions to be order independent
- This 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 to Candidates, CollisionConstraints, and FrictionConstraints.
- Renamed Constraints to CollisionConstraints
- Replaced single letter variable names V, E, F with vertices/positions, edges, faces
- Renamed *_index → *_id
- Replaced inflation_radius = min_distance / 1.99 with inflation_radius = min_distance / 2 and use rounding mode to conservativly inflate AABBs
- CollisionConstraints::use_convergent_formulation and are_shape_derivatives_enabled must now be accessed through getter and setter functions
- Friction potentials are now functions of velocity. Previously V0 and V1 were passed and U = 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 to false in #30
Update website with a tutorial (#31) and version dropdown list (#34)
Switch from templates to using Eigen::Ref in #28
Speed up the CCD by limiting the maximum minimum distance to 1e-4 in #43
Fix 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-phase
Added 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 method
Fixed 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(), and compute_collision_free_stepsize()
update_barrier_stiffness now requires the constraint_set rather than building it
update_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 to false by default
CMake option TIGHT_INCLUSION_WITH_NO_ZERO_TOI=ON as default

2021-06-18 (aa59aeb)¶

Changed¶

construct_friction_constraint_set now clears the given friction_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 to std::exceptions

2021-05-06 (24056cc)¶

Changed¶

Gave dhat_epsilon_scale a default value of 1e-9 in update_barrier_stiffness
warning:

Changed order of parameters to update_barrier_stiffness
- Flipped bbox_diagonal and dhat_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 and HashGrid

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 over VectorX3 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 to construct_constraint_set(). This is similar to F (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 gradient
Assertions on initial_barrier_stiffness() input
- average_mass > 0 && min_barrier_stiffness_scale > 0

Changed¶

Fixed typo in initial_barrier_stiffness() name (was intial_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 now construct_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 type
- Duplicate 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 now dhat (i.e., non-squared value)
Input parameter epsv_times_h_squared is now epsv_times_h (i.e., non-squared value)
Constraints replaced Candidates
construct_constraint_set() now takes the rest vertex position (V_rest)
compute_barrier_potential*() no longer take the rest vertex position

Last update: Dec 12, 2024