Contact Generation

1y ago
86 Views
1 Downloads
1.11 MB
78 Pages
Last View : 4d ago
Last Download : 9m ago
Upload by : Amalia Wilborn
Transcription

Contact GenerationErwin CoumansSony Computer Entertainment US R&D

Contact generation Pipeline overviewA single contact pointContact clippingMultiple contact points using perturbationPersistent contact cachingInternal edges and contact normalsDynamic aabb tree acceleration structure

Physics PipelineCollision DataCollisionshapesObjectAABBsDynamics avityContactpointsPredicttransformsForward tecontactpointsCollision DetectionComputationAABB axis aligned bounding boxSetupconstraintsSolveconstraintsForward DynamicsComputationIntegrateposition

Collision Detection PipelineCollision on DetectionWorldtransforms etectoverlappingchild shapes(compound)Midphase (concave)Collision Detectionculling using acceleration structuresComputeclosestpointsGeneratefull contactmanifoldNarrowphaseCollision Detection

Contact generation Pipeline overviewA single contact pointContact clippingMultiple contact points using perturbationPersistent contact cachingInternal edges and contact normalsDynamic aabb tree acceleration structure

Closest point computationvoid computeClosestPoints( ); Black box is discussed in Erin Catto’s GJK talk GJK needs companion algorithm for penetration

Touching contactdistance 0

Shortest distanceShapeAdistance 0ShapeB

Closest points (witness)

Separating vectors

Minimum translational distancedistance 0

Points of deepest penetration

Minimum separating vector

What is a contact point? Distance A separating normal Pair of closest pointsShapeAShapeB

Removing redundancy a b n*dShapeAandbShapeB

Contact point structurestruct ContactPoint{floatm distance;Vector3m normalB;Vector3m pointOnB;};

Single contact

Single contact point Works fast and stable for simple cases

Single contact

Single contact

Single contact

Contact generation Pipeline overviewA single contact pointContact clippingMultiple contact points using perturbationPersistent contact cachingInternal edges and contact normalsDynamic aabb tree acceleration structure

Box-Box Clipping Setup Identify referenceface Identify incident faceincidentreferencen

Box-Box Clippingclipping planes Clip incident faceagainst referenceface side planes(but not thereference face). Consider clip pointswith positivepenetration.n

Contact generation Pipeline overviewA single contact pointContact clippingMultiple contact points using perturbationPersistent contact cachingInternal edges and contact normalsDynamic aabb tree acceleration structure

Multiple points for general convex General convex might not have vertices/faces Compute multiple closest point samples All “single shot” within this simulation step

Perturbing around normal Works well but costs additional GJK queries

Perturbation pseudo codecontact computeContact(shapeA,transA,shapeB,transB, ho1);Matrix3x3 R p MatrixFromAxisAngle (ortho0, perturbationAngle);float angle 360 / number of iterations;for (i 0 ; i number of iterations;i ){Matrix3x3 Rn rbedA Rn.inverse() * R p * Rn * ,transB,.);updateContactDistance(transA,transB);}

Perturbing around normal Issue with round shapes: they start rolling

Perturbing around normal Replace contact at actual position Keep perturbation small Last resort: apply damping or skip round shapes

Perturbating in 3D

DEMO!!!

Contact generation Pipeline overviewA single contact pointContact clippingMultiple contact points using perturbationPersistent contact cachingInternal edges and contact normalsDynamic aabb tree acceleration structure

Incremental contact caching Add a single point at a time to small cache Refresh cache, update or remove points

Adding points to cache Check for duplicate points Use feature id or distance tolerance Reduce points when more than 4 points Always keep point with deepest penetration Try to maximize area

Cache local closest pointsShapeAandanbbShapeBd‘

Update contact distanceworldPosA transA(localPosA);worldPosB transB(localPosB);distance (worldPosA-worldPosB).dot(worldNormalB);anbd

Removing pointsanbd‘

Hybrid method Single shot manifold to build a full cache Only add a single point to a full cache Google for btPersistentManifold

Collision margins GJK doesn’t work in penetrating cases and penetration depth calculation is a bit slower

Collision margins Sphere can be a point with radius as margin

Compensate for margins

Collision margin approximationBcore shapeB

Collision margin approximationerrorerror

DEMO!!!

Contact generation Pipeline overviewA single contact pointContact clippingMultiple contact points using perturbationPersistent contact cachingInternal edges and contact normalsDynamic aabb tree acceleration structure

Internal edge collisions3D viewtriangle Btriangle Ainternal edge2D view

Internal edge collisions Object is colliding against triangle B Contact normal is pointing against velocitytriangle Btriangle A2D viewinternal edge

Solution 1: triangle normal Works well for flat connected trianglescorrectedcontact normaltriangle normal Btriangle A2D viewinternal edge

Solution 1: triangle normal Works well for concave edgescorrectedcontact normaltriangle normal Btriangle A2D viewinternal edge

Cliff problem Object can be pushed of a clifftriangle Acorrectedcontact normal2D viewtriangle normal Binternal edge

Solution 2: use voronoi regions Only adjust normal outside voronoi regiontriangle normal Aedge voronoi regiontriangle A2D viewtriangle normal Binternal edge

Solution 2: use voronoi regions No correction neededtriangle normal Aedge voronoi regiontriangle A2D viewtriangle normal Binternal edgetriangle B

Solution 2: use voronoi regions Rotate normal towards voronoi regiontriangle normal Aedge voronoi regiontriangle A2D viewtriangle normal Binternal edgetriangle B

Implementation Google for btInternalEdgeUtility

Contact generation Pipeline overviewA single contact pointContact clippingMultiple contact points using perturbationPersistent contact cachingInternal edges and contact normalsDynamic aabb tree acceleration structure

Collision Detection PipelineCollision on DetectionWorldtransforms etectoverlappingchild shapes(compound)Midphase (concave)Collision Detectionculling using acceleration structuresComputeclosestpointsGeneratefull contactmanifoldNarrowphaseCollision Detection

Concave shapes

Convex decomposition

Concave triangle mesh

Concave triangle mesh

Contact for concave shapes GJK and EPA can only deal with convex objectsConvex decompositionTriangle meshes: a single triangle is convexConcave mesh is just a collection of trianglesDeal with each triangle individually

Concave Shapes: AABB treessplitting axis

AABB tree structureroot nodeinternal nodes(don’t contain geometry)convexleaf nodes

AABB tree queries by traversal Find overlapping nodes given a AABB Find overlapping nodes given a Ray (from,to)

AABB tree traversal Recursive Stackless with skip indices History tracking (see Harada’s talk)

AABB tree Static AABB tree Can be optimized and quantized Allows for basic tree refit operator Dynamic AABB tree Can deal with change in topologyAdd and remove nodesIncrementally rebalance treeIs very general purpose

Adding a node Find leaf with smallest Manhattan distance

Implementation insert leaf nodevoid insertleaf(btDbvt* pdbvt,btDbvtNode* root,btDbvtNode* leaf) {if(!pdbvt- m root){pdbvt- m root leaf;leaf- parent 0;}if(!root- isleaf()) {do {root root- childs[Select(leaf- volume,root- childs[0]- volume,root- childs[1]- volume)];} while(!root- isleaf());}btDbvtNode* prev root- parent;btDbvtNode*node createnode(pdbvt,prev,leaf- volume,root- volume,0);if(prev) {prev- childs[indexof(root)] node;node- childs[0] root;root- parent node;node- childs[1] leaf;leaf- parent node;do {if(!prev- volume.Contain(node- volume))Merge(prev- childs[0]- volume,prev- childs[1]- volume,prev- volume);elsebreak;node prev;} while(0! (prev node- parent));}else {node- childs[0] root;root- parent node;node- childs[1] leaf;leaf- parent node;pdbvt- m root node;}}

Removing a leaf node Find and remove node and relink

Implementation remove leaf1: btDbvtNode*removeleaf(btDbvt* pdbvt, btDbvtNode* leaf){2:if(leaf pdbvt- m root){ pdbvt- m root 0; return(0);}3:btDbvtNode*parent leaf- parent;4:btDbvtNode*prev parent- parent;5:btDbvtNode*sibling parent- childs[1-indexof(leaf)];6:if(prev)7:{8:prev- childs[indexof(parent)] sibling;9:sibling- parent prev;10:deletenode(pdbvt,parent);11:while(prev) {12:const btDbvtVolumepb prev- volume;13:Merge(prev- childs[0]- volume,prev- childs[1]- volume,prev- volume);14:if(NotEqual(pb,prev- volume)){15:prev prev- parent;16:} else break;17:}18:return(prev?prev:pdbvt- m root);19: }20: else21: {22:pdbvt- m root sibling;23:sibling- parent 0;24:deletenode(pdbvt,parent);25:return(pdbvt- m root);26: }27: }

Update/move a leaf node If new AABB is contained by old do nothing Otherwise remove and re-insert leaf Re-insert at closest ancestor that was not resizedduring remove (see line 18 previous page) Expand AABB with margin Avoid updates due to jitter or small randommotion Expand AABB with velocity Handle the case of linear motion over n frames

Incremental tree optimization Rebalance tree removing and inserting a fewleaf nodes at a time

Dynamic AABB tree broadphaseFCBDA012FCD12BA131014FD3E58E71115CEAB

Dynamic BVH tree broadphase Keep two dynamic trees, one for movingobjects, other for objects (sleeping/static) Find neighbor pairs: Overlap M versus M and Overlap M versus SM: Moving DBVTS: Non-moving DBVTFPDCEABQRSTU

DEMO!!!

Summary Use a persistent manifold for multiple points keep contacts in local space and update distance Adjust normals to avoid internal edge collisions only if normal outside edge voronoi region Dynamic AABB trees are fast and versatileacceleration structure for broadphase pair search and ray test midphase for triangle meshes, cloth, deformables occlusion and view frustum culling

Bullet An open source 3D physics engine http://bulletphysics.org Written in C

culling using acceleration structures. Contact generation Pipeline overview A single contact point Contact clipping . DEMO!!! Contact generation Pipeline overview A single contact point Contact clipping Multiple contact points using perturbation Persistent contact caching

Related Documents:

Modelos de iPod/iPhone que pueden conectarse a esta unidad Made for iPod nano (1st generation) iPod nano (2nd generation) iPod nano (3rd generation) iPod nano (4th generation) iPod nano (5th generation) iPod with video iPod classic iPod touch (1st generation) iPod touch (2nd generation) Works with

NEW BMW 7 SERIES. DR. FRIEDRICH EICHINER MEMBER OF THE BOARD OF MANAGEMENT OF BMW AG, FINANCE. The sixth-generation BMW 7 Series. TRADITION. 5th generation 2008-2015 1st generation 1977-1986 2nd generation 1986-1994 3rd generation 1994-2001 4th generation 2001-2008 6th generation 2015. Six

The following iPod, iPod nano, iPod classic, iPod touch and iPhone devices can be used with this system. Made for. iPod touch (5th generation)*. iPod touch (4th generation). iPod touch (3rd generation). iPod touch (2nd generation). iPod touch (1st generation). iPod classic. iPod nano (7th generation)*. iPod nano (6th generation)*

BASPINAL@SHAW.CA (Office Email) Contact Info Contact Info Contact Info Contact Info Contact Info Contact Info Contact Info Contact Info 8 JAG-2013-02024 s.22. FIGR0171 2013-12-04 10:55 AM Business Licences Expiring Between 2013-Dec-

span class "news_dt" Oct 09, 2017 /span  · strong 2018 Stewardship theme: “Generation to Generation /strong ” It is my privilege to announce Trinity’s 2018 strong Stewardship /strong campaign! The theme for 2018, “Generation to Generation,” is a spot-on description of Trinity’s generational commitment to strong generosity /strong of spirit and resources! Although Trinity church has been around almost 200 years,

8 critical success factors for lead generation Brian J. Carroll 2 8 critical success factors for lead generation My book, Lead Generation for the Complex Sale (McGraw-Hill, 2006), was inspired by the inarguable fact that concerted lead generation endeavors were primarily that in name only until recently. Until now, "lead generation"

Address The contact’s address. Address 2 The contact’s address. City The contact’s city. State / Province / Region The contact’s state, province, or region. Postal Code The contact’s ZIP or Postal Code. Business Phone The contact’s business phone number. Cell Phone The contact’s cell phone num

Tourism is not limited only to activities in the accommodation and hospitality sector, transportation sector and entertainment sector with visitor attractions, such as, theme parks, amusement parks, sports facilities, museums etc., but tourism and its management are closely connected to all major functions, processes and procedures that are practiced in various areas related to tourism as a .