Optimizing world with double link list
Posted: Tue May 01, 2012 6:17 pm
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.
I put the head in my world class inheriting from btDiscreteDynamicsWorld
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.
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.
This is how I get each element in the list.
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
Code: Select all
DoubleLinkListHead<ModifiedRigidBody> LL_ActiveRigidBodies;
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 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);
}
Code: Select all
DoubleLinkListBody<ModifiedRigidBody>* Iterator = LL_ActiveRigidBodies.Head;
while (Iterator) {
UseRigidBody(Iterator->Content);
Iterator = Iterator->Next;
}