Optimizing world with double link list

Post Reply
CookieMonster
Posts: 49
Joined: Sun Jan 29, 2012 10:01 pm

Optimizing world with double link list

Post by CookieMonster »

I am trying to optimize the Bullet engine by keeping a non allocating double link list of each active rigid body so that the world don't have to ask each sleeping body if it is active.
The only thing missing is a way to know when a rigid body has changed it's activation state so that isActive() gives another result.
I noticed that all methods for setting the activation state in btCollisionObject are not virtual so that I can't get a call from it without having to recompile the library.

Code: Select all

#ifndef DoubleLinkListIsDeclared
#define DoubleLinkListIsDeclared

template <class el>
struct DoubleLinkListBody; // Forward declaration

// This is stored where you want to access the list
// There can be multiple heads using the same relation as long as they are mutually exclusive
template <class el>
struct DoubleLinkListHead {
	DoubleLinkListBody<el>* Head;
	void ResetMemory(void) {
		Head = NULL;
	}
	void Insert(DoubleLinkListBody<el>* Element,el* Content);
	void Remove(DoubleLinkListBody<el>* Element);
};

template <class el>
void DoubleLinkListHead<el>::Insert(DoubleLinkListBody<el>* Element,el* Content) {
	if (!(Element->Included)) { // If the element is not included
		Element->Included = true; // The element is included
		Element->Previous = NULL; // The first element has no previous element
		Element->Next = Head; // Take the previous head as the tail
		Element->Content = Content;
		Head = Element; // Use the new element as the head
	}
}

template <class el>
void DoubleLinkListHead<el>::Remove(DoubleLinkListBody<el>* Element) {
	if (Element->Included) { // If the element belongs to something
		Element->Included = false; // The element is no longer a member
		if (Head == Element) { // If the element is first in this collection
			Head = Element->Next; // The head becomes the element's tail
		} else if (Element->Previous) { // If the element has a previous element
			Element->Previous->Next = Element->Next; // The previous element inherits it's next element no matter if it is null
		}
		if (Element->Next) { // If the element has a next element
			Element->Next->Previous = Element->Previous; // The next element inherits it's previous element no matter if it is null
		}
		Element->Next = NULL; // The element have no next element
		Element->Previous = NULL; // The element have no previous element
	}
}

// This is stored in each element
// It can at most declare membership to one list and can therefor not be used for many to many relations
template <class el>
struct DoubleLinkListBody {
	DoubleLinkListBody<el>* Previous;
	DoubleLinkListBody<el>* Next;
	el* Content;
	bool Included;
	void ResetMemory(void) {
		Previous = NULL;
		Next = NULL;
		Content = NULL;
		Included = false;
	}
};

#endif
I put the head in my world class inheriting from btDiscreteDynamicsWorld

Code: Select all

DoubleLinkListHead<ModifiedRigidBody> LL_ActiveRigidBodies;
I put the body with the next and previous pointers and a pointer to the world's head in my rigid body class inheriting from btRigidBody.
Both the head and the body is named LL_ActiveRigidBodies to show that they belong to the same link list.

Code: Select all

DoubleLinkListBody<ModifiedRigidBody> LL_ActiveRigidBodies;
DoubleLinkListHead<ModifiedRigidBody>* ActiveRigidBodiesHead;
The ResetMemory methods are used as constructors but can be called wherever the list is stored without having to use placement new.

The rigid body use these methods for adding and removing itself from the list.

Code: Select all

void ModifiedRigidBody::AddToActiveList(void) {
	ActiveRigidBodiesHead->Insert(&LL_ActiveRigidBodies,this);
}

void ModifiedRigidBody::RemoveFromActiveList(void) {
	ActiveRigidBodiesHead->Remove(&LL_ActiveRigidBodies); 
}
This is how I get each element in the list.

Code: Select all

DoubleLinkListBody<ModifiedRigidBody>* Iterator = LL_ActiveRigidBodies.Head;
while (Iterator) {
	UseRigidBody(Iterator->Content);
	Iterator = Iterator->Next;
}
Post Reply