Dev:Source/Physics/Collision Modifier

	This page is outdated
	This page was last updated in 2008, it is outdated. If you have questions, ask in #blendercoders at IRC

Collision Modifier

The collision modifier gets created automatically through pressing the "Deflection" button in the "Deflection" panel or using the Softbody deflection panel.

Internals

What does it do

The collision modifier safes the position of the vertices of the object at the corresponding position on the modifier stack. It does this for the current and the last position using GLOBAL coordinates. The data is only valid as long as

• you don't skip ahead/back several frames [TODO: should be enhanced later]
• the number of vertices don't change on the modifier stack.

If any of these events happens, the safed position will get reseted.

Structure

typedef struct CollisionModifierData {
	ModifierData	modifier;
	
	struct MVert *x; /* position at the beginning of the frame */
	struct MVert *xnew; /* position at the end of the frame */
	struct MVert *xold; /* unsued atm, but was discussed during sprint */
	struct MVert *current_xnew; /* new position at the actual inter-frame step */
	struct MVert *current_x; /* position at the actual inter-frame step */
	struct MVert *current_v; /* (xnew - x) at the actual inter-frame step */
	
	struct MFace *mfaces; /* object face data */
	
	unsigned int numverts;
	unsigned int numfaces;
	int pad;
	float time;		/* cfra time of modifier */
	struct BVH *tree;	/* collision tree (kdop bvh) for this cloth object */
} CollisionModifierData;

Usage

collision_move_object

That's a function to set the position of the object to a specific time (is using linear interpolation):

void collision_move_object(CollisionModifierData *collmd, float step, float prevstep);

• collmd: Pointer to collision modifier data

• step: Time at the end of timestep
• prevstep: Time at the start of timestep

step and prevstep are limited from 0 to 1 which would mean that at 0 all vertices are put at the start positions of the frame and 1 put the vertices at the end of the frame.

Example usage of collision_move_object

collision_move_object(collmd, step + dt, step);

where dt means an arbitrary timestep deltatime and step calculated as

step += dt;

Additional functions

The collision modifier can be also used as a partner for a KDOP BVH collision query. The KDOP BVH collision query tests 2 bounding boxes if they overlap (see at bottom).

Here the sample code:

bvh_traverse((ModifierData *)clmd, (ModifierData *)collmd, cloth_bvh->root,
             collmd->tree->root, step, cloth_collision_static, 0);

Context Example

if (collmd->tree) 
{
	/* get pointer to bounding volume hierarchy */	
	BVH *coll_bvh = collmd->tree; 
		
	/* move object to position (step) in time */		
	collision_move_object(collmd, step + dt, step); 
	
	/* search for overlapping collision pairs */		
	bvh_traverse((ModifierData *)clmd, 
                     (ModifierData *)collmd, 
                     cloth_bvh->root, 
                     coll_bvh->root, 
                     step, cloth_collision_static, 0);
}

KDOP BVH

The kdop bvh is a bounding volume hierarchy structure which can be used to test if two bounding boxes oberlap. If they do, a predefined callback function is called for each overlapping leaf.

Internals

Definition of traverse function to test if two BVH structures overlap:

int bvh_traverse ( ModifierData * md1, ModifierData * md2, CollisionTree * tree1,
                   CollisionTree * tree2, float step, 
                   CM_COLLISION_RESPONSE collision_response, int selfcollision);

Definition of CollisionTree:

typedef struct CollisionTree
{
	struct CollisionTree *nodes[4]; // 4 children --> quad-tree
	struct CollisionTree *parent;
	struct CollisionTree *nextLeaf;
	struct CollisionTree *prevLeaf;
	float	bv[26]; // Bounding volume of all nodes / we have 7 axes on a 14-DOP
	unsigned int tri_index; // this saves the index of the face
	int	count_nodes; // how many nodes are used
	int	traversed;  // how many nodes already traversed until this level?
	int	isleaf;
	float alpha; /* for selfcollision */
	float normal[3]; /* for selfcollision */
}
CollisionTree;

Since you get the corresponding leafs/CollisionTrees as arguments of the CM_COLLISION_RESPONSE callback function you can e.g. easily lookup their vertices and check if the two faces really collided.

Defition of callback function:

typedef void ( *CM_COLLISION_RESPONSE ) ( ModifierData *md1, ModifierData *md2,
                                          CollisionTree *tree1, CollisionTree *tree2 );

Creating a CollisionTree

You can create a collition tree out of every mesh. You just alloc a BVH structure and fill the specific structures with the information according to your mesh structure and call the bvh_build() function. You can also use existing functions which do the trick for you (like bvh_build_from_mvert).

Information to be set in the BVH structure before calling bvh_build():

• epsilon: Thickness / minimum distance (higher results in more overlapping leafs)
• numfaces: Number of faces
• mfaces: Pointer to faces (Type: MFace *)
• numverts: Number of vertices
• current_x: Has to be alloc'ed and fill edwith current vertex positions

Definition of bvh_build function

Builds the BVH KDOP hierarchy structure out of a prealloc'ed and filled BVH structure.

void bvh_build (BVH *bvh);

Example of filling and using the bvh_build function (content of bvh_build_from_mvert function)

	BVH *bvh=NULL;
	
	bvh = MEM_callocN(sizeof(BVH), "BVH");
	if (bvh == NULL) 
	{
		printf("bvh: Out of memory.\n");
		return NULL;
	}
	
	// in the moment, return zero if no faces there
	if(!numfaces)
		return NULL;

	bvh->epsilon = epsilon;
	bvh->numfaces = numfaces;
	bvh->mfaces = mfaces;
	
	// we have no faces, we save seperate points
	if(!mfaces)
	{
		bvh->numfaces = numverts;
	}

	bvh->numverts = numverts;
	bvh->current_x = MEM_dupallocN(x);
	
	bvh_build(bvh);

Definition of bvh_build_from_mvert function

Allocs, fills and builds a BVH KDOP structureout of MVert vertex structure which is ready for use.

BVH *bvh_build_from_mvert (MFace *mfaces, 
                           unsigned int numfaces, 
                           MVert *x, 
                           unsigned int numverts, 
                           float epsilon);

Updating bvh structure

There is also an option to update the position of the vertices / of the bounding box hierarchy. You just put the new positions into bvh->current_x and bvh->current_xold and call the bvh_update function. You can also use existing functions like bvh_update_from_mvert which uses MVert structure to update the hierarchy.

void bvh_update(BVH * bvh, int moving);

• bvh: Pointer to ready initialized and build BVH structure
• moving: Can be 0 or 1. 0 means static object, only bvh->current_xold will be used for updating positions. 1 means dynamic/moving resulting that also bvh->current_x will be used for positions update at the end of the timeframe. It's used to catch fast moving object collisions.

There is also a function which does all the trick for you using a MVert structure:

void bvh_update_from_mvert(BVH * bvh, MVert *x, unsigned int numverts, 
                           MVert *xnew, int moving);

• bvh: Pointer to ready initialized and build BVH structure
• x: Current vertex positions
• numverts: Number of vertices
• xnew: Positions of vertices at the end of the timestep (only used if moving is 1)
• moving: Can be 0 or 1. 0 means static object, only bvh->current_xold will be used for updating positions. 1 means dynamic/moving resulting that also bvh->current_x will be used for positions update at the end of the timeframe. It's used to catch fast moving object collisions.