Changelog

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

  • 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

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: Apr 03, 2024