Early last semester I wrote a post talking about what we were planning for the engine. I saved it as a draft and never posted it, so instead I'll mention what we did. I'll keep this somewhat brief, as we are planning a demo for some of the school soon and we will have a more impressive demo level.
So what did we do? Well for starters, we finally got UI in. It's a pretty awesome UI if I may say so myself, although it still needs a lot of tweaking. However, we have a property grid to edit all of our objects and we just got in tools for object spawning, parenting, joint connecting, etc...We also have transform widgets that work with groups.
This leads me to another feature which I personally worked on, Composite bodies. This is the concept of "parenting" one object to another with a relative transformation to the parent. This means we can create complex shapes, such as tables and chairs, and have accurate collision with them. In fact, we even calculate what the correct center of mass and inertia tensor for the object is so that the movement is correct. And due to a recent re-architecting, we can support (although not supper efficiently yet) non-flat hierarchies. By this I mean A is parented to B who is parented to C who is parented to D...Overall, it's a very cool feature that allows us to create cool shapes that I will show off soon, such as a jeep, seesaw, box, table, chair, etc...
We also got in collision with static meshes, so we have a big ground map to play around on. Along with this, one of my fellow devs has been working on a player controller. This is progressing quite well as the player can run on the terrain, jump, push objects, slide up inclines that aren't too steep and even auto climb small staircases. We still have to make the player walk down inclines instead of falling, and make the player use a volume cast instead of a ray cast to determine if anything is in front of him.
And as for constraints, I have been spending a great deal of time cleaning up and polishing them. I even threw in an "alternate" solving method. By this I mean instead of having a constraint solve itself in a standard C++ style, the constraints can offload all the data needed to solve itself generically into a constraint row. This row basically contains the jacobian, bias, accumulated impulse and what objects are associated with it. From this I create a large, packed array of constraints to loop through. This ends up yielding a rather large speed boost, at least 30%, to the constraint solver. I still plan to SSE this at some point to gain an even larger performance boost.
On top of this, contacts are overall improved, although much improvement will always be needed. Stacks are much better due to friction tweaks, although I still need to align each point of contact's primary friction direction with the direction of movement. I also added in a persistent manifold based heavily on Bullet's. This allows much better interaction between MPR objects so we can even stack Cylinders.
There's more we have done, but in the interest of not rambling I will stop here. Although just for the fun of it, here's a small video of something I felt like making...
Tuesday, January 25, 2011
Sunday, August 15, 2010
DigiPen Game Engine Post Mortem
The summer semester has finally ended and so I wanted to give a rough postmortem of the engine I worked on as well as describe some cool features.
Architecture
First of all, we made the physics engine more component based than anything I had done before. We split the main components up into the following categories: Collider, Rigid Body, Constraint, Controller, Region, Effects and Spaces.
The collider and rigid body were the two main components. The collider contained the collision data as well as a position. The rigid body contained the center of mass and velocity. Each one also contained more data, but that was the main differentiation. The idea behind the separation was to split the functionality in a logical way. If a collider and a rigid body were placed on an object, then it would behave just as one would expect. However, if no rigid body was present then the object would be static and considered to have infinite mass. Unfortunately, despite trying to separate out functionality, there was still a strange dependency that the rigid body had on the collider. Most notably, a rigid body requires a collider and it also has to be initialized after the collider. Overall, I think this is a better structure than one massive physics object, but further experimentation and tweaks are still in order.
One benefit that we have not pursued yet is to have multi-object bodies. Currently, an object can only have one collider. The plan for this next semester is to extend objects to have one body for a set of colliders. This is a very nice component driven method of handling the non-convex object issue. I personally plan to implement this the upcoming fall semester.
The space component basically replaced a normal engine. The engine still exists, but now it does very little. The engine has a list of spaces and does almost no work apart from updating each space. Each space then in turn updates all its objects. This provides a very clean way to separate out rooms or other such physical space separations. This also allows different spaces to operate on different time scales. We had a timespace component that each space would use to figure out its update speed. This meant we could pause physics but still have UI running in a very clean manner. And yes, we enjoyed making lots of naming puns with the space component such as timespace, spacelink, geospace, etc...
The region was a nifty idea we had to make an area that would affect objects in various ways. How it would affect something was based upon what effects were placed on it, such as a drag or a random force. On top of this, effects could be placed on spaces and colliders. Collider effects would only be applied on the object while space effects would be global. This becomes very useful to apply gravity or drag globally to the world. The one thing we plan to change is to actually remove regions all together. A region basically kept a record of what was inside of the collider that defined it and applied the effects, however we can actually just have a collider do this with less work due to some things mentioned in the constraint layout section below.
The constraint component was exactly as one would expect, a constraint. This made adding all constraints much easier and allowed for constraints to actually be objects themselves. Along with constraints, we created a new system component called a connection to replace the transform. A constraint tends to not have a position, but two objects that it is connected to. This allowed the engine and other systems to understand this connection better, as well as deal with serialization cleanly.
The controller is what would be used by logic to control something, however this is not a component we actually implemented this semester.
Broadphase Tracker
One the coolest features we made we dubbed the broadphase tracker. The idea was to make a manager of sorts for the testing of broadphases. The tracker has two sets of broadphases, static and dynamic. The separation is a commonly made one since some structures can be more efficiently created if they are given a chunk of time up front.
One of the most useful features of the tracker was to track the accuracy of multiple broadphases and compare them. We did this by determining how often the broadphase and narrowphase agreed. This allowed us to figure out how useful a broadphase may be in a given scenario. Also, this allowed us to check if any broadphases had an error. If any broadphase reported that there was no collision but the narrowphase said otherwise, then there is an error since there should only be false positives. Therefore, the implementation of a new broadphase would be less frustrating as a basic N-squared could be used as a comparison to make sure no false negatives were ever reported. This was actually useful as we found an error in my old Sweep and Prune code both by it missing a test and by noticing that its accuracy was not the same as an N-squared bounding box test.
Another benefit that was not fully implemented was the timing of each broadphase. The one other thing we still want to add is a analyzer of sorts. the analyzer would load up lots of broadphases and tracker how well they do. Over the course of time it would drop bad ones and then at the end of a run it would provide the top 3. This would make finding the best broadphase for a game much easier.
Constraint System
The constraint system was what I spent most of my time on. My code was also very heavily influenced by Erin Catto's Box2D. One of the best designs in implementing this system was in the use of an Intrusive Linked List (InList) courtesy of Chris Peters (my boss). This allowed really quick insertion and removal of objects. This was also helpful in the overall structure. Unfortunately, it is a bit hard to describe this structure but I will try anyways. One day I'll make a nice picture or maybe even an ascii picture in the comments...
Each collider has an InList of edges. An edge then points to the constraint it is a part as well as the collider it is attached to. Each constraint then has two edges, one for each object. The edge that is in the collider's InList is one of the ones that the collider owns. From this crazy structure, a collider can figure out all of the objects it has a constraint with which allows islanding. Also, a constraint can remove and add itself to objects in constant time.
One other thing I did for future console extension was to remove as many virtual calls as I could. This was done by putting each constraint into a separate InList on the solver. The main disadvantage to this is the maintenance, but I spent some time to reduce this with macros. The idea was to make the solver define a macro then use it. The thing is that the macro was used in a header that just had all of the name of the constraints. This header would then be included so that some functionality could be done for all types of constraints. This was used for creating add and remove functions, iteration solving and more. If any macro did a large amount of work, a template function was made which did all the real work, such as solving constraints. This also meant that when updating, some of the templates could be specialized if a constraint, such as a contact, needed special behavior. Because of this the work to add new constraints is greatly reduced.
The problem is, due to islanding, constraints have to be added to the solver each frame and I have to figure out which InList to add it to. Because of this a virtual add call is used. This means each constraint still has a virtual call, but it is only once per frame instead of for every call during iteration. To further help this issue, contact constraints were separated and put in its own edge InList. Contacts are the most plentiful constraint, therefore separating it should take care of more than half of all constraints. This also means that it can be easier to check contact only relationships between objects such as the region effects mentioned above.
Materials
We decided to create a material system to define what each collider is made of. The system is rather simple, but it makes life for designers much easier. The material includes friction, restitution and density. We might add more terms later, but this is what seemed useful now. Because of this we can define soft objects or bouncy objects which is what a designer would really want to add. The one main problem is that we can have bouncy heavy or bouncy light, so defining all different types could be painful. To make matters worse, the bouncy heavy could be expanded to be slippery or rough due to friction. Because of this, we decided to only define a few materials and let it be configurable for the user. We thought of maybe using names like stone, but we wanted to avoid names that implied textures since they are completely different systems.
Recap
We did a lot of cool things in this project, most notably is the broadphase tracker. The component splitting also worked very well, but a lot of refining is still needed. As for the constraints, the system works very well overall, but I would like to spend some time to make it simpler and more readable.
I would like to put up a video of some of the cool stuff we have, but I have just recently reformatted my computer and so I do not have fraps or anything at the moment. Hopefully I'll get around to that within the next week.
As for what's next, I plan to continue working on this project next semester, although this is a little contingent on what happens with finding a job. My main tasks for next semester will probably be to clean up and polish some of the constraints and motors, add multiple colliders per body and work on a new broadphase. We might also work on a SSE math library.
Architecture
First of all, we made the physics engine more component based than anything I had done before. We split the main components up into the following categories: Collider, Rigid Body, Constraint, Controller, Region, Effects and Spaces.
The collider and rigid body were the two main components. The collider contained the collision data as well as a position. The rigid body contained the center of mass and velocity. Each one also contained more data, but that was the main differentiation. The idea behind the separation was to split the functionality in a logical way. If a collider and a rigid body were placed on an object, then it would behave just as one would expect. However, if no rigid body was present then the object would be static and considered to have infinite mass. Unfortunately, despite trying to separate out functionality, there was still a strange dependency that the rigid body had on the collider. Most notably, a rigid body requires a collider and it also has to be initialized after the collider. Overall, I think this is a better structure than one massive physics object, but further experimentation and tweaks are still in order.
One benefit that we have not pursued yet is to have multi-object bodies. Currently, an object can only have one collider. The plan for this next semester is to extend objects to have one body for a set of colliders. This is a very nice component driven method of handling the non-convex object issue. I personally plan to implement this the upcoming fall semester.
The space component basically replaced a normal engine. The engine still exists, but now it does very little. The engine has a list of spaces and does almost no work apart from updating each space. Each space then in turn updates all its objects. This provides a very clean way to separate out rooms or other such physical space separations. This also allows different spaces to operate on different time scales. We had a timespace component that each space would use to figure out its update speed. This meant we could pause physics but still have UI running in a very clean manner. And yes, we enjoyed making lots of naming puns with the space component such as timespace, spacelink, geospace, etc...
The region was a nifty idea we had to make an area that would affect objects in various ways. How it would affect something was based upon what effects were placed on it, such as a drag or a random force. On top of this, effects could be placed on spaces and colliders. Collider effects would only be applied on the object while space effects would be global. This becomes very useful to apply gravity or drag globally to the world. The one thing we plan to change is to actually remove regions all together. A region basically kept a record of what was inside of the collider that defined it and applied the effects, however we can actually just have a collider do this with less work due to some things mentioned in the constraint layout section below.
The constraint component was exactly as one would expect, a constraint. This made adding all constraints much easier and allowed for constraints to actually be objects themselves. Along with constraints, we created a new system component called a connection to replace the transform. A constraint tends to not have a position, but two objects that it is connected to. This allowed the engine and other systems to understand this connection better, as well as deal with serialization cleanly.
The controller is what would be used by logic to control something, however this is not a component we actually implemented this semester.
Broadphase Tracker
One the coolest features we made we dubbed the broadphase tracker. The idea was to make a manager of sorts for the testing of broadphases. The tracker has two sets of broadphases, static and dynamic. The separation is a commonly made one since some structures can be more efficiently created if they are given a chunk of time up front.
One of the most useful features of the tracker was to track the accuracy of multiple broadphases and compare them. We did this by determining how often the broadphase and narrowphase agreed. This allowed us to figure out how useful a broadphase may be in a given scenario. Also, this allowed us to check if any broadphases had an error. If any broadphase reported that there was no collision but the narrowphase said otherwise, then there is an error since there should only be false positives. Therefore, the implementation of a new broadphase would be less frustrating as a basic N-squared could be used as a comparison to make sure no false negatives were ever reported. This was actually useful as we found an error in my old Sweep and Prune code both by it missing a test and by noticing that its accuracy was not the same as an N-squared bounding box test.
Another benefit that was not fully implemented was the timing of each broadphase. The one other thing we still want to add is a analyzer of sorts. the analyzer would load up lots of broadphases and tracker how well they do. Over the course of time it would drop bad ones and then at the end of a run it would provide the top 3. This would make finding the best broadphase for a game much easier.
Constraint System
The constraint system was what I spent most of my time on. My code was also very heavily influenced by Erin Catto's Box2D. One of the best designs in implementing this system was in the use of an Intrusive Linked List (InList) courtesy of Chris Peters (my boss). This allowed really quick insertion and removal of objects. This was also helpful in the overall structure. Unfortunately, it is a bit hard to describe this structure but I will try anyways. One day I'll make a nice picture or maybe even an ascii picture in the comments...
Each collider has an InList of edges. An edge then points to the constraint it is a part as well as the collider it is attached to. Each constraint then has two edges, one for each object. The edge that is in the collider's InList is one of the ones that the collider owns. From this crazy structure, a collider can figure out all of the objects it has a constraint with which allows islanding. Also, a constraint can remove and add itself to objects in constant time.
One other thing I did for future console extension was to remove as many virtual calls as I could. This was done by putting each constraint into a separate InList on the solver. The main disadvantage to this is the maintenance, but I spent some time to reduce this with macros. The idea was to make the solver define a macro then use it. The thing is that the macro was used in a header that just had all of the name of the constraints. This header would then be included so that some functionality could be done for all types of constraints. This was used for creating add and remove functions, iteration solving and more. If any macro did a large amount of work, a template function was made which did all the real work, such as solving constraints. This also meant that when updating, some of the templates could be specialized if a constraint, such as a contact, needed special behavior. Because of this the work to add new constraints is greatly reduced.
The problem is, due to islanding, constraints have to be added to the solver each frame and I have to figure out which InList to add it to. Because of this a virtual add call is used. This means each constraint still has a virtual call, but it is only once per frame instead of for every call during iteration. To further help this issue, contact constraints were separated and put in its own edge InList. Contacts are the most plentiful constraint, therefore separating it should take care of more than half of all constraints. This also means that it can be easier to check contact only relationships between objects such as the region effects mentioned above.
Materials
We decided to create a material system to define what each collider is made of. The system is rather simple, but it makes life for designers much easier. The material includes friction, restitution and density. We might add more terms later, but this is what seemed useful now. Because of this we can define soft objects or bouncy objects which is what a designer would really want to add. The one main problem is that we can have bouncy heavy or bouncy light, so defining all different types could be painful. To make matters worse, the bouncy heavy could be expanded to be slippery or rough due to friction. Because of this, we decided to only define a few materials and let it be configurable for the user. We thought of maybe using names like stone, but we wanted to avoid names that implied textures since they are completely different systems.
Recap
We did a lot of cool things in this project, most notably is the broadphase tracker. The component splitting also worked very well, but a lot of refining is still needed. As for the constraints, the system works very well overall, but I would like to spend some time to make it simpler and more readable.
I would like to put up a video of some of the cool stuff we have, but I have just recently reformatted my computer and so I do not have fraps or anything at the moment. Hopefully I'll get around to that within the next week.
As for what's next, I plan to continue working on this project next semester, although this is a little contingent on what happens with finding a job. My main tasks for next semester will probably be to clean up and polish some of the constraints and motors, add multiple colliders per body and work on a new broadphase. We might also work on a SSE math library.
Thursday, July 1, 2010
Quick update
So unfortunately, I have been to busy to be working on my own physics engine on top of my other projects. I do not expect this to change at all for the next couple of months.
Both of my current projects are coming along quite nicely. The game I'm working on, Redivivus, is doing well, we still haven't found the sweet spot for the game idea yet though.
As for the open source DigiPen engine, that is working out very nicely. It is a completely constraint based engine and has a lot of cool features. I plan to write a postmortem once the semester ends. I'll also make some videos to show what we have.
Both of my current projects are coming along quite nicely. The game I'm working on, Redivivus, is doing well, we still haven't found the sweet spot for the game idea yet though.
As for the open source DigiPen engine, that is working out very nicely. It is a completely constraint based engine and has a lot of cool features. I plan to write a postmortem once the semester ends. I'll also make some videos to show what we have.
Wednesday, May 5, 2010
Update
So the semester at DigiPen has finally ended. I have replaced the old Sandbox download with the most recent version of it that was the final result for my classes. I have not taken the time to strip out the features that are not %100 finished, so some things will not work as desired, most notably is soft bodies.
Also, my game has been finished and now has a new video as shown below:
Now for an update as to what I am doing now. First, I will not be continuing on my current team, but will instead be joining team Semi-Mobile from DigiPen on their game Redivivus to polish it up for competitions.
Exactly what I will be doing on the team is not decided, but I will most likely be doing some tools, along with helping out on physics and wherever else is needed.
Another thing that I will be doing this summer is working on an open source game engine that one of my teachers is making for eventual public consumption. Me along with 2 other guys (one from Redivivus) will be doing the physics, math library and collision tests for the engine.
Along with this, I will still be working on my own Sandbox, but I am currently ripping apart large sections of it and re-doing how a number of things work given that I know how to set things up much better now. I would hope to have a working version of my sandbox within a month. Most likely, nothing will look different, maybe I'll get around to putting shaders in, but most of the changes will be internal structure changes.
Also, my game has been finished and now has a new video as shown below:
Now for an update as to what I am doing now. First, I will not be continuing on my current team, but will instead be joining team Semi-Mobile from DigiPen on their game Redivivus to polish it up for competitions.
Exactly what I will be doing on the team is not decided, but I will most likely be doing some tools, along with helping out on physics and wherever else is needed.
Another thing that I will be doing this summer is working on an open source game engine that one of my teachers is making for eventual public consumption. Me along with 2 other guys (one from Redivivus) will be doing the physics, math library and collision tests for the engine.
Along with this, I will still be working on my own Sandbox, but I am currently ripping apart large sections of it and re-doing how a number of things work given that I know how to set things up much better now. I would hope to have a working version of my sandbox within a month. Most likely, nothing will look different, maybe I'll get around to putting shaders in, but most of the changes will be internal structure changes.
Friday, April 16, 2010
Dimension of constraints
So I currently have a very basic motor in, just achieves a certain angular velocity as an equality constraint, but I thought I'd mention an issue I ran into.
Constraints can only be solved on one dimension at a time in constraint space. Well what does this mean? When a constraint is moved from normal euclidean (or another space) into constraint space it becomes a generalized coordinate. An example of such things is the contact constraint. When we look at it we see that the constraint is in multiple directions, the x,y,z. But in reality the constraint is along one dimension, the normal. So what becomes a two dimensional constraint space problem? How about friction. Friction constrains the movement in the plane perpendicular to the normal. Well there are an infinite number of directions to pick from if you use only one, but if you use two then you can cover the entire space. This brings me to where I actually learned this issue, with motors. If you want to make a motor have a target angular velocity of 1 about the x, 0 about the y and 5 about the z, well you can't, at least not with once constraint. As some may recall, we have three degrees of rotational freedom, so obviously we can only constrain 1 degree at a time. So to take care of this issue we have to have 3 constraints, one for each axis angle we want to rotate about.
I'm trying to get a better way to manipulate my motors, mainly via the arrow keys so I can control a player, but things aren't set up well for that right now on top of the fact that our gold at DigiPen is due in less than a week now. After this semester I might be re-gutting most of my engine, but I'll try to get a basic video up before then.
Constraints can only be solved on one dimension at a time in constraint space. Well what does this mean? When a constraint is moved from normal euclidean (or another space) into constraint space it becomes a generalized coordinate. An example of such things is the contact constraint. When we look at it we see that the constraint is in multiple directions, the x,y,z. But in reality the constraint is along one dimension, the normal. So what becomes a two dimensional constraint space problem? How about friction. Friction constrains the movement in the plane perpendicular to the normal. Well there are an infinite number of directions to pick from if you use only one, but if you use two then you can cover the entire space. This brings me to where I actually learned this issue, with motors. If you want to make a motor have a target angular velocity of 1 about the x, 0 about the y and 5 about the z, well you can't, at least not with once constraint. As some may recall, we have three degrees of rotational freedom, so obviously we can only constrain 1 degree at a time. So to take care of this issue we have to have 3 constraints, one for each axis angle we want to rotate about.
I'm trying to get a better way to manipulate my motors, mainly via the arrow keys so I can control a player, but things aren't set up well for that right now on top of the fact that our gold at DigiPen is due in less than a week now. After this semester I might be re-gutting most of my engine, but I'll try to get a basic video up before then.
Monday, March 29, 2010
Constraints Update
So here is a powerpoint on constraints that I created and recently lectured on at the game physics club at Digipen. Slides Download
If anyone has questions on anything in the slides, feel free to ask.
Here are some new videos that are not in debug mode with cooler features.
This is just a cooler looking rope bridge with smaller length constraints than before.
And here is a small "structure" made using stick constraints instead of ropes. Currently, the constraints do not have a "strength" value, so all constraints have an equal strength. This means that when I hang objects from the top, the bottom tends to be violated. I could always add more constraints to the bottom to "reinforce" it, but I would like to give it a strength at some point.
I have also added a lot of other cool features in my GUI that cannot be seen on this video, including deleting specific constraints and editing them as well.
Also a newer video of our game with properly exported character models. I would show the new character, but he can't do much without me networking this...we'll have to record an official video at some point as a team.
I might try to throw in some velocity motors in the near future, but the semester is ending soon and the game will require more attention.
If anyone has questions on anything in the slides, feel free to ask.
Here are some new videos that are not in debug mode with cooler features.
This is just a cooler looking rope bridge with smaller length constraints than before.
And here is a small "structure" made using stick constraints instead of ropes. Currently, the constraints do not have a "strength" value, so all constraints have an equal strength. This means that when I hang objects from the top, the bottom tends to be violated. I could always add more constraints to the bottom to "reinforce" it, but I would like to give it a strength at some point.
I have also added a lot of other cool features in my GUI that cannot be seen on this video, including deleting specific constraints and editing them as well.
Also a newer video of our game with properly exported character models. I would show the new character, but he can't do much without me networking this...we'll have to record an official video at some point as a team.
I might try to throw in some velocity motors in the near future, but the semester is ending soon and the game will require more attention.
Tuesday, March 16, 2010
Sandbox Fixed
So I decided to actually try my sandbox on a different computer and it turned out it would crash on XP because of some dll linking issues. After some time I tracked it down to an issue in my crash handler. Anyways, I have fixed it and re-uploaded it. The download links have also been fixed.
Edit: forgot to also mention that I have now included the ability to make distance joint constraints since I have that working now. Instructions for how to use it are in the readme.
Download
Edit: forgot to also mention that I have now included the ability to make distance joint constraints since I have that working now. Instructions for how to use it are in the readme.
Download
Subscribe to:
Posts (Atom)
