A computer-implemented method for animating hair, the method comprising: receiving data representing a plurality of hairs and a plurality of objects in a timestep of a frame of animation; populating a first tree to represent kinematic objects of the plurality of objects based on the received data; populating a second tree to represent dynamic objects of the plurality of objects based on the received data; creating a first elasticity preconditioner representing internal elastic energy of the plurality of hairs based on the received data; determining , based on the first tree and the second tree, a first set of potential contacts between two or more hairs of the plurality of hairs or between one or more hairs of the plurality of hairs and one or more objects of the plurality of objects; and determining positions of the plurality of hairs based on the determined first set of potential contacts and the first elasticity preconditioner, wherein determining positions of the plurality of hairs comprises iteratively: determining magnitudes of normal forces and friction forces for the first set of potential contacts; determining updated positions of the plurality of hairs based on the determined magnitudes of normal forces and friction forces; and for iterations after a first iteration of determining positions of the plurality of hairs based on the determined first set of potential contacts, detecting temporal collision between two or more hairs of the plurality of hairs or between one or more hairs of the plurality of hairs and one or more objects of the plurality of objects. receiving data representing a plurality of hairs and a plurality of objects in a timestep of a frame of animation; populating a first tree to represent kinematic objects of the plurality of objects based on the received data; populating a second tree to represent dynamic objects of the plurality of objects based on the received data; creating a first elasticity preconditioner representing internal elastic energy of the plurality of hairs based on the received data; determining , based on the first tree and the second tree, a first set of potential contacts between two or more hairs of the plurality of hairs or between one or more hairs of the plurality of hairs and one or more objects of the plurality of objects; and determining positions of the plurality of hairs based on the determined first set of potential contacts and the first elasticity preconditioner, wherein determining positions of the plurality of hairs comprises iteratively: determining magnitudes of normal forces and friction forces for the first set of potential contacts; determining updated positions of the plurality of hairs based on the determined magnitudes of normal forces and friction forces; and for iterations after a first iteration of determining positions of the plurality of hairs based on the determined first set of potential contacts, detecting temporal collision between two or more hairs of the plurality of hairs or between one or more hairs of the plurality of hairs and one or more objects of the plurality of objects. determining magnitudes of normal forces and friction forces for the first set of potential contacts; determining updated positions of the plurality of hairs based on the determined magnitudes of normal forces and friction forces; and for iterations after a first iteration of determining positions of the plurality of hairs based on the determined first set of potential contacts, detecting temporal collision between two or more hairs of the plurality of hairs or between one or more hairs of the plurality of hairs and one or more objects of the plurality of objects. <EOS>