• Categories

    Archives

  • More work on my physics engine

    3 Comments

    Over the last month I have been improving my physics engine for an upcoming team project. Some of my more recent work on it is contained in my “3D Convex Collision Detection” article series; however there are still things to talk about. Here is an overview of the major features of the engine:

     

    Rigid Body Dynamics:

    I have implemented Euler integration with linear damping for both linear and angular velocity. Angular velocity is dampened at a much greater rate to better approximate the air friction that a spinning airborne object would face.

    I also employ a sleep system that removes stable, non-moving, bodies from update consideration. The sleep state is controlled by the body’s level of motion, derived from its linear and angular velocities. When this parameter lingers below an epsilon for a long enough period of time the object is put to sleep. Objects are brought out of sleep by several different stimuli: a contact that wants to increase the body’s motion above the epsilon (i.e. not a resting contact in a stack) or the body’s methods for applying velocity and/or torque being called.

     

    Collision Detection:


    For collision detection I have implemented the robust Gilbert–Johnson–Keerthi (GJK) and Expanding Polytope Algorithms (EPA). I have already done detailed posts about these so I will not go into too much detail here. They allow me to perform generalized and efficient tests between any two convex bodies.

    hphy2_collisionskin

    They also allow me to easily add “collision skins” to my bodies. This is done by simply extending the support mapping point out a bit further in the desired direction. This technique serves two purposes, for one it allows multiple contacts to be cached before two objects are actually colliding, improving the results of the resolution stage, and it aids in the process of waking up sleeping bodies. Without the skins a stack of boxes would not properly be awoken if the box on the bottom were to be knocked out of place, leaving them hovering.

     

    Contact Resolution:

    Each frame, during the collision detection phase, every pair of intersecting bodies creates a new contact containing the point of contact, depth of penetration, and collision normal. These contacts are cached over several frames to ensure stability. Here is a 2D example:

     

    hphy2_collisioncache_1hphy2_collisioncache_2hphy2_collisioncache_3

    The red points are the contact points. With only a single contact point per frame the box would “wiggle” on the ground in a very unnatural way, making stacks of objects impossible.

    Contacts are resolved in two phases, first interpenetration is resolved in the order of deepest penetration and then velocities are resolved in the order of greatest required velocity change. Penetration is resolved by using a combination of linear motion in the contact normal direction and rotation in a direction perpendicular to the position of the contact relative to the center of mass and the contact normal, weighted based on inertia. Velocities are resolved by generating an impulse that describes the necessary change in linear and angular velocities, considering the friction coefficient of the contact (the average of that of the two objects).

    The number of contacts resolved per phase per frame is capped, and issues below a certain threshold are ignored. Existing contact positions and penetration values are updated in two places. At the end of a body’s update it updates all of the contacts it is involved in. Similarly when a contact is resolved all of the other contacts that share one or both of the bodies involved is updated.

     

    Spatial Partitioning:

    Collision detection is by far the most time-consuming phase of my engine. So to make it more efficient I have implemented a unique special partitioning system. My technique breaks the world down into grid sectors of finite size (testing shows that 20 units is the sweet-spot for the size of objects I am using). Each collider registers with the system, giving valid AABB extents, and calls a function each frame that synchronizes the partition registration’s position with that of the body. Each registration keeps a list of sectors that it is in and every sector (using a hashtable) keeps a list of all registrations within it. When the synchronization function is called a new valid list of sectors is calculated and compared to the registrations current one, if there is a discrepancy it is corrected.

    During the collision detection phase, instead of iterating over every object and checking it against every other object I build a list of test candidates by iterating over every sector’s list of registered objects.

    // function calls the lambda for each bucket (sector) of the spatial partition universe
    HDX_SPMAN->doIterateUniverseBuckets([&](spdata::bucket &bucket)->bool {
    	unsigned int bucketsize = bucket.mregs.size();
    	for(unsigned int i = 0; i < bucketsize; i++) {
    		component_Physics *cad = (component_Physics*)bucket.mregs[i]->muserdata;
    		for(unsigned int j = i+1; j < bucketsize; j++) {
    			component_Physics *cbd = (component_Physics*)bucket.mregs[j]->muserdata;
    			// lambda adds the the pair of colliders to the test checklist if at least one of
    			// them is nonstatic and not asleep, ignores if the pair is already in the list
    			lam_addToCheckList(cad,cbd);
    		}
    		// for infinitely large things, like planes, halfspaces, etc
    		for(auto opc = momnipresentcandidates.begin(); opc != momnipresentcandidates.end(); opc++) {
    			lam_addToCheckList(cad,*opc);
    		}
    	}
    
    	return false;
    },"physics");
    

    Tests:

    I have created a few test scenarios to demo the above features.

    The Funnel:

    In this test a grab-bag of objects are dropped into a funnel constructed from OBBs. Once they filter through they settle on a half space. This test shows that the simulation remains stable even in extreme conditions. It also shows how frictions work together and how arbitrary convex hull collision works with quadric shapes.

     

    Stacking:

    This test creates numerous stacks of boxes with varying heights. This tests shows that the power of the contact aggregation system, as it allows stacks of boxesto get quite high before they become unstable. (20 works OK, 30 slowly giggles itself apart {blame it on wind ;)})

     

    Launcher:

    This test stacks several small blocks onto a board resting halfway on a large static block. A medium sized block is dropped onto the board, launching the smaller blocks. This test shows the translation of linear force to rotation and then back to linear.

     

    Bridge:

    This test uses many bungee force generators to simulate a bridge composed of several planks. A stack of blocks is dropped onto the bridge to show how it reacts.

     

    Comment RSS

    3 Responses to “More work on my physics engine”

    1. Gerard Koury says:

      What’s up, the whole thing is going fine here and ofcourse every one is sharing facts, that’s genuinely good, keep up writing.|

    2. It’s all about Even rich people, who have more than they could ever use, want They don’t want to make people happy, they want more It’s just the nature of greed and

    3. Mmorpg online games is really a nice way to meet great people from around the world.

       

    Leave a Reply

  • Recent Posts

home login
content