I have been working on a rigid body physics program using verlet integration. I have the entire thing working the way I want it. The problem is that it was terribly slow. I'm now in the processes of optimization. Originally I was using trig in my constraint procedure, this was only temporary. Now I'm trying to switch it over to using vectors. There is a problem in the procedure, however. In my test I have a box made from nodes and binds which falls. It used to bounce around and stop they way it should, now it kinda explodes when it hits the bottom. And the problem is definatly in the constraint code. I just can't spot my error.
Here is the procedure as it is now.

Code:

Public Sub Constrain(p1 As SpringNode, p2 As SpringNode, Dist As Double)
Dim BindVect As Vector2
Dim BindUnit As Vector2
Dim Length As Double
Dim DeltaLen#
Dim p1need#, p2need#
'get the vector
BindVect.X = p2.X - p1.X
BindVect.Y = p2.Y - p1.Y
'get the vector length
Length = Sqr(BindVect.X * BindVect.X + BindVect.Y * BindVect.Y)
'get the unit vector of the bind vector
BindUnit.X = BindVect.X / Length
BindUnit.Y = BindVect.Y / Length
'find the total distance that needs to be moved
DeltaLen = Length - Dist
'find distance each needs to move
p1need = DeltaLen * p1.mass / (p1.mass + p2.mass)
p2need = DeltaLen * p2.mass / (p1.mass + p2.mass)
'move the points to the new position
p1.X = p1.X + (BindUnit.X * p1need)
p1.Y = p1.Y + (BindUnit.Y * p1need)
p2.X = p2.X + (BindUnit.X * p2need)
p2.Y = p2.Y + (BindUnit.Y * p2need)
End Sub

__________________
There are 10 different kinds of people in this world: Those who know binary and those who dont.

Dist is the distance there should be between the nodes. Length is the distance between the nodes as of when the procedure was called. DeltaLen is the difference of those two, or in otherwords how much the nodes need to be moved in total to be the correct distance apart. Later I find out what percentage of that distance each node needs to move based on the mass (larger masses move a smaller amount, and vice versa). Then multiply that by DeltaLen to get the actual amount each needs to move and store those into p1need and p2need. Then the last part is moving the nodes in the right direction. I stored a direction vector earlier so I could move the nodes in the correct direction when constraining. Hope that explains a little bit.

__________________
There are 10 different kinds of people in this world: Those who know binary and those who dont.

Oh and about the nodes themselves. I have a couple of data structures I use right now, I may change this later.

Code:

Public Type Binding
Index As Long
RestLength As Double
End Type
Public Type SpringNode
X As Double
Y As Double
LastX As Double
LastY As Double
Accy As Double
Accx As Double
Mass As Double
NumBinds As Long
Binds(4) As Binding
End Type

Each node has a position and mass. They have a member, Binds, which can link this node to anyother node in the node array. The Binds tell what node its connecting to and how far away from that node it should normally be. When I constrain the nodes to each other I will use this information in the procedure call to let it know how far it needs to be (the Dist variable in the header).

__________________
There are 10 different kinds of people in this world: Those who know binary and those who dont.

I figured out my error.. after doing a lot of stepping thru the code and finding out that it exploded sorta randomly and not because of the collision itself, I rewrote the procedure again. I wacked myself on the head cuz I realized it was exactly the same except this...

Lexdysic, I made a very similar program to you once, only I never got around to converting from trig to vectors. Anyway it looks like we have both been reading the "Advanced Character Physics" article by Thomas Jakobsen.

I found that in order to make the box bounce I have to reverse the speed of the node that hits the floor. Not only that but I have to double or tripple the speed in order to make it look a little more realistic. How do you handle the collision response for your bouncing box?

__________________
Check out my free Download Meter prog written in VB6.
Having trouble using the registry in VB? Try my free registry control.

Actually I haven't even seen that article before, I was just working on my own from what little I already knew. I have a few tests that I use- rope, net, box, rag doll. I'm in the process of getting the calculations as fast as possible. I still have a lot to go thru. I haven't gotten to the point where I need to worry about having things bounce correctly. Right now its as if it hits a frictionless floor so it will slid. The only thing that slows it is air friction. Im in the middle of overhauling the binds that I use between the nodes. I can only have one type of bind as of right now (single distance). I would like to be able to have more options (min, max, angles, etc.). After I get all of that out of the way I can worry about getting the rest of the physics aligned. Unfortuatly I get very little time to work on it, so its a slow process.

__________________
There are 10 different kinds of people in this world: Those who know binary and those who dont.

Well,
I thought I'd see how far I would get doing this, with close to zero knowledge of how this is usually done in game programming but a sound physics background.
Using DeX's sample project as a starting point, I replaced his constraint-based method by a mechanics-based one. The result looks better than I expected, after fiddling around with the parameters for a bit.
There probably is at least one bug somewhere, because I don't understand the values at which the object explodes, and I have the feeling that I should understand them. Oh, and there is no friction yet, so the square keeps stupidly sliding across the bottom once it stops bouncing.
Anyway, here you go, maybe it's useful for one of you or someone else coming across this thread. Bug reports and comments as always welcome.

ps: This models a solid square, not a wireframe, btw.

pps: I can try and explain the "internal dissipation" part that's really the heart of this method, but I'd rather not have to

__________________
"To learn without thinking is to labour in vain" - Confucius

Alright, So I have implemented the rest of the contraints that I wanted. I ended up with these- Static distance, Max Distance, Min Distance, Static Angle, Max Angle, and Min Angle constraints. It took many nights after work to finish rehauling the engine. It all seems to work alright. But I do have a problem that I'm not too sure how to go about fixing. It has to do with angle restraints. It all seems to work just fine when I bind the one of the nodes to the mouse. It will keep all the restraints exactly as they should be. The lengths stay in bounds and the angle is constant and there are no problems when I test things that way. But when I have the same constraints with a free falling body it likes to explode on impact. I tracked down the problem to the angle constraints. When writing the code for the angle constraints I was unsure how to go about it. The way I devised follows:

A) First make two vectors from three points A, B, and C: BA^^ and BC^^ (for now ^^ will represent the vector symbol).
B) I then find the angle between the BA^^ and BC^^ using ArcCos
C) Find the difference in the actual angle and the constrained angle
D) If they dont match, then rotate A and C around B using the apporiate weighted rotation for each.

I beleive the problem here is that this method only affects A and C. It just assumes that B will stay in place and moves the other points around it. This is my conclusion after doing a test that reacted completly wrong. Do one of you know of a better way of constraining angles? I beleive I'm very close its just what I do to A, B, and C that is slightly wrong.

Here is the code snippet that I use currently, please let me know if you wish to see more code.

Code:

Public Enum RigidBindType
BindMaxLength = 1 'The length between the nodes denoted by A and B cannot be longer then Data
BindMinLength = 2 'The length between the nodes denoted by A and B cannot be shorter then Data
BindStaticLength = 4 'The length between the nodes denoted by A and B must be Data
BindMaxAngle = 8 'The angle between the binds denoted by A and B must be shorter then Data
BindMinAngle = 16 'The angle between the binds denoted by A and B must be greater then Data
BindStaticAngle = 32 'The angle between the binds denoted by A and B must be Data
BindLength = BindMaxLength Or BindMinLength Or BindStaticLength
BindAngle = BindMaxAngle Or BindMinAngle Or BindStaticAngle
End Enum
Public Type RigidBinding
BindType As RigidBindType 'What type of bind is this
A As Double 'Will refer to a node if the type is length or a length bind if type is angle
B As Double 'Will refer to a node if the type is length or a length bind if type is angle
Data As Double 'Either the a distance or an angle depending on type
Var As Double 'Variance of data to prevent over calculating
End Type
Public Type RigidNode
x As Double
y As Double
LastX As Double
LastY As Double
Accy As Double
Accx As Double
Mass As Double
Friction As Double
End Type
Public Type RigidBody
NumNodes As Long
Nodes() As RigidNode
NumBinds As Long
Binds() As RigidBinding
End Type
...
If Body.Binds(BindIndex).BindType And BindAngle Then
'Store some local variables so we don't have to keep referencing
With Body
B1 = .Binds(BindIndex).A 'Bind index 1
B2 = .Binds(BindIndex).B 'Bind index 2
NAng = .Binds(BindIndex).Data 'Bounding Angle
A = .Binds(B1).A 'Node index A
B = .Binds(B1).B 'Node index B
C = .Binds(B2).A 'Node index C
D = .Binds(B2).B 'Node index D
End With
'Two of the four node indecies are the same
'We need to find the ones that matches and make that index B
'The remaining unmatching two will be stored in A and C
If A = B Then
A = D
B = B
C = C
ElseIf A = C Then
dummy = A
A = B
B = dummy
C = D
ElseIf A = D Then
dummy = A
A = B
B = dummy
C = C
ElseIf B = C Then
A = A
B = B
C = D
ElseIf B = D Then
A = A
B = B
C = C
ElseIf C = D Then
A = A
B = C
C = D
Else
'They are all different
Exit Sub
End If
'At this point B will be the common node and A and C will be the other two.
'Now we can construct our vectors.
With Body
u.x = .Nodes(B).x - .Nodes(A).x
u.y = .Nodes(B).y - .Nodes(A).y
v.x = .Nodes(B).x - .Nodes(C).x
v.y = .Nodes(B).y - .Nodes(C).y
End With
'Get the norms of the vectors
LenU = Norm2(u)
LenV = Norm2(v)
'If either is the zero vector we can quit now
If LenU = 0 Or LenV = 0 Then Exit Sub
'Get the angle between the vectors
ang = ArcCos(DotProduct2(u, v) / (LenU * LenV))
With Body
'This determines if the angle needs to be adjusted.
'It checks what type of bind this is and whether the
'current angle is incorrect for it.
If (.Binds(BindIndex).BindType = BindStaticAngle And Not InRange(ang, NAng, .Binds(BindIndex).Var)) _
Or (.Binds(BindIndex).BindType = BindMaxAngle And ang > NAng) _
Or (.Binds(BindIndex).BindType = BindMinAngle And ang < NAng) Then
lngCount = lngCount + 1
'Just reuse Ang to store the angle that we need to rotate
ang = ang - NAng
'Now get the weighted angle that the end of each vector must move
AngU = ang * .Nodes(A).Mass / (.Nodes(A).Mass + .Nodes(C).Mass)
AngV = ang * .Nodes(C).Mass / (.Nodes(A).Mass + .Nodes(C).Mass)
'Rotate around point B
RotatePointCenter .Nodes(A).x, .Nodes(A).y, .Nodes(B).x, .Nodes(B).y, AngU
RotatePointCenter .Nodes(C).x, .Nodes(C).y, .Nodes(B).x, .Nodes(B).y, -AngV
End If
End With
End If

__________________
There are 10 different kinds of people in this world: Those who know binary and those who dont.

'Now get the weighted angle that the end of each vector must move
AngU = ang * .Nodes(A).Mass / (.Nodes(A).Mass + .Nodes(C).Mass)
AngV = ang * .Nodes(C).Mass / (.Nodes(A).Mass + .Nodes(C).Mass)

Thought experiment: Mass(A) = 1, Mass(C) = 0.
Your expressions would give AngU = ang, AngV = 0, whereas it should be the other way around (massless node moves the whole distance, massive one remains stationary).
I doubt that this is the problem though, since I assume that all nodes would be equimassive for the simple tests you've done so far (?)

Thirdly, I'm not sure that all the angles get the proper sign, I usually have a lot more Abs()es in code dealing with angles. Hard to tell from looking at the code, best checked by strategically placing Debug.Prints.

It might be easiest to help if you could post the whole sample project so we can play around with it, if that's possible...?

__________________
"To learn without thinking is to labour in vain" - Confucius

Thank you very much, TeraBlight, for the complements.
You're correct in that I do use the same mass for all nodes in my experiments. Though, I'm not sure that the angle calculations are wrong. When I change it to the other way it makes it react backwards. What I mean is that it makes it look as though the heavy mass is actually lighter. Maybe its just that my other functions are still wrong, not sure tho.

About the signs of the angles- I'm fairly sure that what I have will not need extra Abs()es. This is because the angle that I get between the vectors will always be between 0 and pi. It should never return a negative. So its like it already has a built in Abs().

I have posted what have so far. If you would like to use one of the experiments I have already set up you can undocument any that you wish. They are all in CreateBody(), as for now its is the wedge example because its the easiest to debug and still have an angle constraint. You can also create your own, its very easy and should be intuitive. There are two pairs of lines that you can undocument to constrain different nodes to the mouse. One is stable because it is balanced, the other is very wild.

I would very much like to hear your feedback on this.

__________________
There are 10 different kinds of people in this world: Those who know binary and those who dont.

- When you say "explode", do you mean the behaviour of the object as a whole (shooting off off the screen, not conserving kinetic energy), or do you mean the fact that e.g. the box collapses into a wedge?

- Is there an easy way to redirect the DirectDraw output into a window rather than to fullscreen it, so I can see the debug window while the physics is unfolding? This is probably a dumb question, but I'm really clueless about Direct graphics stuff...

__________________
"To learn without thinking is to labour in vain" - Confucius

The exploding is when it just shoots off the screen. The box should never collapse because it has the angular constraints, but obiously there is something wrong there.

The engine has a bug in it that I never figured out, its wierd. When you move the window in windowed mode it actually changes where it all draws to. I will just attach one that works in windowed. It will still work the same it just wont look right.

Nevermind, I found the error in my render engine and have it all fixed, I just uploaded the fixed version.

__________________
There are 10 different kinds of people in this world: Those who know binary and those who dont.

Last edited by Lexdysic; 07-25-2005 at 08:22 PM.
Reason: Added Fixed Attachment

I don't know if this will help in your situation but I definately think it would be a good idea to read Chris Heckler's rigid body physics articles. They are well written although a little indepth. Number 2 deals with angular movement. http://www.d6.com/users/checker/dynamics.htm

__________________
Check out my free Download Meter prog written in VB6.
Having trouble using the registry in VB? Try my free registry control.

I've eliminated the cause for the explosions for the wedge and the box now. Ironically, the error wasn't in the Constraints but in the Physics Sub, you basically had

x = x0 + v + a t^2

instead of

x = x0 + v t + a t^2

Also, the "box" case only had one angular constraint, which explains why the box collapsed to a wedge.
The ragdoll is giving me a headache though, it just refuses to behave. I'm trying to move B instead of rotating A and C to adjust the angles, but there's some very non-trivial geometry involved
Anyway, I *think* I should have something sometime today...

__________________
"To learn without thinking is to labour in vain" - Confucius

Allright, I give up. This is beginning to freak me out
It works quite well now, apart from the ragdoll which still does weird things sometimes when it touches the circles. But I think that's more of a problem of how you implement the interaction with the circles, which is just temp code anyway, so I'm not too worried about that.

The reason I'm a little freaked out is because I don't have any idea WHY it works now. I messed around with your approach for a while (rotating A and C about B) but couldn't get the ragdoll to stabilize, it would keep spinning about the fixed point when disturbed. So, I tried a different approach, namely moving B instead of rotating A and C. This didn't work at all, the objects would either blow up or behave as if they had a gyroscope inside: no matter how they collided with the circles, I couldn't get them to tip over.

So, just now, I went back to rotation. And it just worked, just like that. Bah.

I'm going to try and briefly describe the changes I made in the next two posts and leave it to you to clean up all the mess I made - at least you have lots of commented out code to play with

EDIT: Actually, the ragdoll still goes crazy if you hold it at one of the extremities and disturb it in the right way. I think it's got something to do with a joint being "overstretched" and the whole body moving to compensate... I'm attaching the project set up so you are holding the doll by the left knee. It seems alright, until you touch a circle or move the mouse violently enough

__________________
"To learn without thinking is to labour in vain" - Confucius

Last edited by TeraBlight; 07-29-2005 at 01:22 AM.

First off, some points that have nothing to do with the RigidBody problem, but I thought I should mention/correct anyway:

The correct usage of dynamic arrays is the following:

Code:

Dim a() As Long 'or "a() As Long" in the Type definition
'resize
ReDim a(5) '<- putting an "As Type" here is bad practice! VB merely tolerates this
' as long as it's the same as in the declaration, otherwise you get an RTE.
ReDim a(1 To 10)
ReDim a(10 To 20)
'reset to empty
Erase a 'not "ReDim a(0)", that leaves an element in the array

Then, I found a few typos in your maths lib, but as you're not using any of these functions, they too have nothing to do with anything (corrections in red):

Code:

Public Function Factorial(ByVal x As Long) As Long
Factorial = x * [B][COLOR=Red]Factorial[/COLOR][/B](x - 1)
End Function
Public Function Normalize3(v As Vector3) As Vector3
Dim Length As Double
Length = Norm3(v)
Normalize3.x = v.x / Length
Normalize3.y = v.y / Length
Normalize3.[COLOR=Red][B]z[/B][/COLOR] = v.z / Length
End Function
Public Function DotProduct3(u As Vector3, v As Vector3) As Double
DotProduct3 = u.x * v.x + u.y * v.y + u.z [B][COLOR=Red]*[/COLOR][/B] v.z
End Function

__________________
"To learn without thinking is to labour in vain" - Confucius

The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET. subscribe