Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[alway]

Latest screenshot:

Spoiler (click to show/hide)

First off, the purpose of this thread is to bounce ideas off a wall, and hopefully figure some things out. I currently have decent knowledge of C++ and am teaching myself Direct3D.

This program is meant to simulate collisions between two objects, deforming both based on the physics involved in the collision. This is done through several independant code modules, each of which have the ability to be reused in similar programs, possibly extending the simulation ability to include non-moving objects through the application of outside forces. Lol, that's not gonna happen.

So, here are the primary modules:
1. The Collision Detection Module

Spoiler (click to show/hide)

will consist of fairly standard collision detection algorithms. These will also determine whether or not the objects are moving towards one another at a speed exceeding minimum deformation velocity (preset; possibly modified based on material data). If Materials are on collision course and above minimum speed, proceed to module 2.

2. The Collision Path Generation Module

Spoiler (click to show/hide)

will consist of two main parts. The first will use the minimum/maximum x/y/z values to find the center of both objects. This point will then be taken to part 2. In part 2, this point will be turned into a line by application of velocities of both objects (to create lines relative to each object). Forces acting on objects will be assumed the same [may change at later date].

3. The Node Generation Module

Spoiler (click to show/hide)

will be responsible for creating the grid of nodes used in the collisions. In this step, points will be seeded within both objects, with the desity of nodes increasing as the distance from the expected line of impact decreases. This will allow for more accurate collision in areas which matter while reducing CPU draw; see Finite Element Method wiki page. Uses "slice method" for calculating whether nodes are within object boundaries. The generation of the nodes themselves will consist of generating multiple grids of nodes with distances between nodes being double the next higher density. These grids will then be put into expanding spheres [although due to there being more than one point from which distance is measured, the end result will be more cylindrical than spherical in an ideal case] outwards from the center point, with the innermost grid being the radius distances given for the object, in order to have the minimum distance grid cover the entire (or almost entire) area of direct impact. The difference in radii distances will be equal to 4 times the length of the bonds in the areas bounded by them.

4. The Bond Generation Module

Spoiler (click to show/hide)

involves connecting neighboring nodes with elastic bonds in preparation for collision. This involves creating a list of bonds which will be put into a vector; each bond will also have two pointers to it stored in the nodes which contain it. Each node will have up to 6 pointers to bonds. Bond length and strength will vary based on distance between connected nodes. The bond characteristics will also be able to be altered based on direction in which the bonds face at generation. This will allow for splintering/peeling in strips, giving the simulation a much better ability to simulate more complex materials such as wood or stone. The most likely method for accomplishing this module will be to start with a single node at a collision point from module 2 and work outward from there. This method would involve combining node and bond modules into one while leaving slice method code separate [for portability] and yet as a neccessary header file. [note: if this method used, will need to ensure code is in place to prevent node overlap and other similar issues]

5. The Physics Based Collision Module

Spoiler (click to show/hide)

will be responsible for the heavy calculating which needs to be done as the collision takes place. Looping force/velocity/position code will be here as well as code for bond deformation and bond failure. Forces calculated will include: external forces, bond forces, repulsive forces. External forces will be an input into this module; likely will have little effect on simulation unless very large. Bond forces will be calculated based on bond length. Repulsive forces will be calculated based on node distances. Bond deformation will enable bonds to stretch/contract in length. Bond failure will sever bond when it becomes overly stretched or when force from bond exceeds a large force determined based on material information.

6. The Cleanup Module

Spoiler (click to show/hide)

will be responsible for re-assembling the output from the collision module into something capable of being rendered and appearing reasonable. For now, only focusing on non-textured meshes. Will involve turning severed debris into new objects or particle effects. Will involve removing most interior nodes, editing/adding/deleting triangles of object. Will refit triangles to include external nodes[slice method should be useful here as well for determining whether a node is an external or internal node]. [note: this module still needs a large amount of conceptual work before module coding can begin, ideas still relatively sketchy]

7. Slice Method Module

Spoiler (click to show/hide)

 consists of the basic functions required to use the slice method to find whether a point is in, out of, or on the edge of, a 3d object. "Slice Method" [there is probably a more technical name for it; look up later] involves cutting a 2 dimensional slice from 3d object followed by checking another axis. If the other axis collides with an even number of lines, the point is outside the object; if odd number, inside. This holds true in nearly all cases of closed objects, the case of edge lines being the exception; may need to add 'if' statements in slice stage to ensure proper behavior. Will use Y axis for slicing, followed by an x axis line. Due to complex exception handling required, slice method code is rather bulky.

The most interesting thing about this is how it could be used to simulate such a large number of materials. By altering parameters for the bonds, one could create a material which acts like rock (easy to break, but won't really bend), material which acts like metal (easy to bend, hard to break), or even wood by altering the x and y bond strength and adding in a bit of random factor while leaving z strong resulting in splintering.

Edit: this post has been VERY heavily edited to reflect changes made during design and implementation process. I am currently changing based on my typed up design docs which serve as both general docs reminding me of what to do as well as notes.

Spoiler: General Overall Progress (click to show/hide)

This section I will be updating occassionally to reflect generally how the parts of the project are doing
1. Planning: 100%
Coding: 100%
2. Planning: 100%
Coding: 100%
3. Planning: 100%
Coding: 100%
4. Planning: 100%
Coding: 100%
5. Planning: 100%
Coding: 100%
6. Planning: 90%
Coding: 50%
7. Planning 100%
Coding 100%
Front end(D3D, DirectX 9) Planning: 100%
Front end Coding: 90%
Note: these figures were extracted from excretory system, may not accurately represent actual progress

[Lord Dullard]

Well, my first gut-response is this: it'd work for any object wherein the interior texture would exactly match the exterior texture, or for any model with a single uniform type of interior, but for any other model you're going to start running into a lot of difficulties.

To elaborate: if you blow up a watermelon, that sounds like something that could reasonably work here. A watermelon has a relatively uniform interior that could all just be textured in the same way.

Blow up an alarm clock, though, and you run into some serious problems. There are wires in there, and often circuitry pieces or mechanical gears, and probably quite a lot of formed plastic bits. Unless you literally model and texture the interior of all these kinds of objects in vast detail, and determine the strength of the bonds between each of the pieces - which is going to be a huge load on graphics processing and regular processing (probably) - you won't get realistic results.

[Bricks]

Your idea bears more than a passing resemblance to the way "Sodaplay" works.  I haven't played with that webtoy in ages, but an ongoing (and perhaps now satisfied) community desire was to have collisions between moving objects, not just the boundaries of the screen or, as in a beta version, static player-placed walls.

The notion of increasing the simulation complexity near collision-prone points is interesting.  I think that would be the biggest hurdle and probably the most original part of your implementation.  Distortion and severing of objects would be pretty cool, but as far as human perception goes, distortion is either too fast or too slight to notice.  Severing would be useful in a few specific circumstances, though making that look nice would be tough.

I've found that the collision system you decide to use for a game often dictates the graphics style.  Visually-complex games rarely implement such advanced collision systems, since trying to illustrate how a particular wooden plank bends, cracks, and breaks could take months.  Games like N have a very smooth system for detecting collisions (and the creator wrote a great article describing how it worked), but graphically there isn't a whole lot going on.

The physics engine for "Star Wars: The Force Unleashed" had some cool distortion/severing effects, although it wasn't the best style of gameplay to show it off.

[alway]

Lord: I see your point, and it is one of the limitations to this sort of system. I hadn't really thought to deeply about the actual texturing... However, if the nodes were given another member in the form of an int/string telling what texture they used, it might not be overly difficult to at least make something which looks reasonable.

Bricks: Heh, sodaplay was fun. As for the system of generating the nodes, I have considered 2 possibilities:
1. Create nodes starting from the area of predicted impact (difficult, but probably more efficient)
2. Create a very large number of nodes, then use an algorithm based on distance from predicted impact to cull the unwanted ones (quite a bit easier, but involves generating literally millions of nodes which will merely be thrown away)

[Bricks]

I think method 1 would be very possible as long as the objects in question aren't moving/spinning too quickly relative to your time interval.  For those that are, you could do some rough collision calculations to give you an idea of where nodes needs to be spawned.  I imagine you'd also need a way to analyze how many objects are possibly involved in a collision so you don't end up with weird clipping or certain objects taking priority over others.

Another issue to be mindful of:  Very springy objects would also have to check for collisions with themselves.  That could be very processor-heavy, so objects that have a chance of self-intersection should either have special code, or should be made of separate, strongly-linked objects.  For example, a simple wire spring could actually be made of a series of half-turns pieced together.  Bodies could be split into their articulatory parts.

[Sean Mirrsen]

1: Download "Sumotori Dreams"
2: Disassemble
3:
4: Profit!

It doesn't do dynamic deformation, but neatly handles fracturing. And it's a demo-scene app.

[alway]

As for the issues you brought up in the first paragraph, something which will happen probably in between steps 1 and 2 (collision detection and node generation) would be the creation of an estimated trajectory. Many of the collisions will take place in between rendered frames, and as such it should be relatively easy to get a decent enough path as there will be no changing forces affecting it (basicly they will be affected by the same forces between end of frame and end of collision aside from the collision itself). As for more than 2 object collisions, how those would work I probably won't bother figuring out until/unless the system works with 2 object collisions.

Self collision will definately need to be dealt with within a collision (in fact, I think I will edit the way the repulsive forces work in the physics part to include all non-bonded nodes). However, other self-intersections would not be dealt with. Partly because nearly all would be sent to normal non-dynamic collision detection due to not meeting the minimum velocity requirement set to prevent static and non-deforming collisions from exploding the CPU. A separate system to accomidate such things would probably work. However, as this is more or less a standalone program which I'm making for fun, I probably won't create said system.

[monkey]

check this out
http://www.realmatter.com/
http://www.ogre3d.org/forums/viewtopic.php?f=11&t=24788

[eerr]

Someday you will blow up the world.

[alway]

I'm slowly making progress on this project as well as managing to confuse both my physics and calculus proffessors who can't quite grasp what I am trying to do. I am currently putting any attempts at making it equation based physics in the back corner and I am beginning work on prototyping a simple version of the stepwise physics calculations. If I'm lucky, I will be able to get that working by the end of the month before starting on building modules for the actual program itself.

[Bricks]

What do you mean by "equation based?"  Do you mean you want a closed-form solution that will tell you exactly how physical bodies will collide without simulating each action procedurally?  I can already tell that you will encounter a lot of situation that will require a numerical integration or an Euler's method approximation, so doing it stepwise makes the most sense in the first place.

If that's not what you mean, you could describe it and I might start working it out as much as I can.

[eerr]

In Super Smash Brothers Brawl impacts stop both characters in their tracks.
I wonder if that would be acceptable in a physics engine?

I just bring it up because it looks dam cool. But if you use 3d there isn't much point because people will usually have to turn to see, rather than just glancing at that sweet explosion/smash attack.

[alway]

What do you mean by "equation based?"  Do you mean you want a closed-form solution that will tell you exactly how physical bodies will collide without simulating each action procedurally?  I can already tell that you will encounter a lot of situation that will require a numerical integration or an Euler's method approximation, so doing it stepwise makes the most sense in the first place.

If that's not what you mean, you could describe it and I might start working it out as much as I can.

Ya, I've pretty much given up on that method. The reason I wanted to use it is because it probably would require a small fraction of the computing power of a stepwise method. The way I figure though, it will be better to have a working, albiet slow, version than a hypothetically faster version which I probably wouldn't get to work anytime soon. I'm hoping to get the first versions done by April so when I visit RIT I have something to brown-nose the programming proffessors with even before my first year there. 

@eerr: I may end up doing something like that, but it all depends on how fast it is able to go through the collision code. If it takes under 1 second to go through it, probably not, but if it takes something more like 5 seconds I almost certainly will render some of the collision frames just so the veiwer isn't left wondering why the game froze for 5 seconds every time 2 objects collide. On a side note, that would probably make it the first bullet-time event which actually has a raison d'etre.

[alfie275]

Make it like toribash, but you can walk around, it will have normal collision here, but at any time you can press space and enter the turn base melee mode/bullet time.

[alway]

While searching for a way to determine whether a point is within a volume for step 2, I stumbled across Delaunay triangluation, which then lead me to this: http://en.wikipedia.org/wiki/Finite_element_method
Seems my ideas aren't new... Which is actually a good thing. After all, it means I will now have some more material to work off of (although I find it is usually easier to come up with on my own than searching for on internet, not to mention more fun).
And it also means it is at least possible to do...

Further wiki-walking shows me it is nearly impossible, if not impossible to do fully equations based collisions, since it involves no less than 15 partial differential equations. http://en.wikipedia.org/wiki/Structural_analysis#Elasticity_methods 

On another note, I scrapped my first attempt at a prototype due to fundamental flaws in its writing (had seperate objects for nodes and bonds, but due to poor coding, ended up with issues involving multiple copies of the same node and/or bond floating around in vectors with differing values, causing all sorts of trouble. From this I have decided to store only pointers to the bonds (themselves stored nicely away in the main bond container) in the nodes. Aside from that, I still have to figure out what equations I will use for calculating forces. For the repelling force between nodes, I will likely use "modifier/(dist^2)" as this allows for the force to increase very quickly as objects approach one another, and decreasing to negligible amounts quickly, thus allowing for lower radius in which to check for repelling nodes. However, whether I use simple elastic (k*displacement) or some other equation for bonds is still very much up the air. I probably won't nail down these two equations until the program is both working and I am able to test it thoroughly. Another thing I will likely do is store the bonds and nodes in trees, allowing for much more rapid binary searching, as opposed to the standard vector iterations which require much longer to search through the (very large) lists of nodes and bonds.

I have also come up with a solution to finding a method for determining whether a point is in or out of any closed 3d volume given the points and triangle indicies which, although somewhat computationally taxing, should be made much more efficient by the fact that my nodes will initially be lined up in grids (which will keep the worst of the calculations to a minimum). Rather than going into a long description of this system, I think it would suffice to say it involves taking a 2 dimensional slice of the 3d object and using the number of intersecting lines on an axis to determine if it is in or out. There is only one flaw I can see in this method, but it is out of the ordinary enough that it should be relatively easy to compensate for it in the slicing stage.