# 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_*`

from`Collision`

and`Collisions`

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`

and`FrictionPotential`

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`

and`ccd`

from`CollisionStencil`

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`

and`barrier_hessian`

renamed to`barrier_first_derivative`

and`barrier_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`

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

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`

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¶

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`

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 #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 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 functionsFriction 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 #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()`

, 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 defaultCMake 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 gradientAssertions 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 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 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