Sphere physics

[Petr Schreiber]

Hi,

Jordi Valles on PB forum posted very nice 2D demo of kind of sphere physics.
I ported it to ThinBasic, with pseudo 3D look ( calculations are still 2D ).

It is pretty computionally intensive.

How many sphere does your PC manage? I am reaching smoothness limit around 50. This could serve as interesting benchmark for optimizing raw ThinBasic parsing speed :)

How to use:

Click in the gray box to add spheres
Right-Click in the gray box to remove last sphere
Watch timing in window title


Bye,
Petr

[ErosOlmi]

:o very nice.

I reached 100 balls at 12 FPS
A good example to use for testing Core optimization.

Beautiful

[Michael Hartlef]

Nice example. 85 spheres at 12 FPS.

[kryton9]

I filled the box up around 79 balls and when I clicked to drop a ball it would say 14fps and then read 30 fps after that.

[Charles Pegge]

This is an interesting problem for collision detection - its a bit like a sort algorithmn. If you change the inner collision loop to:

for i = j+1 to nBalls

instead of:

for i=1 to nBalls

then you should double the performance

at 150 balls it went from 5fps to 10fps on my PC.

We are still faced with the processing time increasing as the square of the number of balls of course but the number of comparisons has now halved.

[Petr Schreiber]

Thanks Charles,

you are right! I can now get 81 spheres at 25FPS.
Great trick!


Petr

[Charles Pegge]

Here is an Oxygenated version. - I have put the inner collision detector loop into assembler and get a steady 34 fps all the way up to 200 balls.

But see how they quarrel and fight each other when the container gets too full! You would not want to be in there with them.

PS latest version with slimmer code. (better use of registers)

[ErosOlmi]

200 balls at 100 FPS !
The power of machine code.

[Petr Schreiber]

Wow ;D

Here comes slightly modified version, based on Oxygenized one:

You can choose 2 sphere detail levels
Bigger box
More spheres allowed
You can spawn objects by holding space and moving mouse



Petr

[ErosOlmi]

800 speres at 35 FPS here. Big improve. Impressive.

If it would be possible to develop some TBGL internals on collision detection I think all TBGL scripts would improve a lot.
But I know it is big job maybe not worth right now.

[Petr Schreiber]

Hi Eros,

good point. But one thing is to detect a collision, and second is to provide accurate reaction of the bodies.
I was thinking of ODE, but as Patrice Terrier noted it crashes on Vista + it has dependency on MSVS DLLs ... no longer sure about this one.

Well, summer is long, will see what I can do :)


Petr

[ErosOlmi]

Yes, I know.

Another option is to make thinBasic ... faster.
As you said, summer is long ;)

[Charles Pegge]

Thanks Petr, your new code makes a very good laboratory for testing collision dynamics.

Morphogenesis

This is one of those happy accidents. I was trying to prevent the balloons from getting into conflict and waging war on each other as the population approaches 600.

I introduced a small upwards displacement to prevent upper balloons from pummeling the ones below. This works quite well when the factor is small but when you increase it to about 0.05 the most extraordinary things begin to happen....

[Petr Schreiber]

that looks very interesting :)


Thanks,
Petr

[Charles Pegge]

Another variation:

The balloons expang a little, every time they collide. When they burst another balloon is created in the container.

[kryton9]

You guys are great. Such a fun demo and nice progression of creativity in each step. The performance is really impressive and it is fun to watch.

What is wrong with ODE Petr?

[Charles Pegge]

Hi Kent,

I am attemting an elastic collision algorithm for this model which is now working correctly for head-on collisions but I want to include glancing collisions. They are the more interesting ones. Then there's spin ..

The maths is not at all difficult but needs to be right in the hottest part of the program so I wonder if delegating this to an external library like ODE causes too much coding complexity.

You may also want to add all sorts of other effects like friction, stickyness and plastic deformation.

[Petr Schreiber]

Sounds great Charles!

Kent - ODE is quite nice, especially the 0.9, but as I said:

Problems with Vists
Dependency on MSVS...DLL


... are what I do not like. The syntax is quite easy to understand, but I do not like that body ( something like orientated mass point ) and geom ( collision shape ) are 2 separate things. Nothing wrapper could not fix ... I am searching for other solutions, no luck so far. We will see what Charles will spark out, as I know him it will be perfect for our purposes.


Petr

[kryton9]

Charles, your new ideas sound incredible. Good luck! I guess you love challenges as much as we do, but your challenges are much steeper walls than I can attempt :)

Petr, ODE is cross platform, why would it need Windows dlls?

What works with Vista anyways? Windows 7 is coming because of Vista sooner than later :)

[Charles Pegge]

Just to show how simple it is:

here is the algorithm for an elastic head-on collision obeying the law of conservation of momentum (mass * velocity)

speed of combined impacted body:

speedC = (mass1*speed1 + mass2*speed2) / (mass1 + mass2 )

then the two bodies part company from each other like this:

speed1=speedC*2 - speed1
speed2=speedC *2- speed2


speed can be a 2d or 3d vector: each of the x y and z components being calculated independently.

[Petr Schreiber]

Hi Charles,

seems nice job for SSE ;)

Kent - Windows version of ODE 0.9 is present in DLL form, and was compiled using MS VS probably.

Windows 7 might be out sooner or later, but I bet they will not throw away Vista code from it, just soften the edges.

So I think if ODE authors won't work on the reason of problem, it will still make troubles. I cannot confirm whether it really GPFs on Vista, I just follow what PT said to me.

The reason for crash is not "Vista is silly", but they probably have some real bug in code, just not manifesting on XPs or keeping hidden/ignored, like it was with working some Win98 proggies crashing on XPs.


Petr

[ErosOlmi]

The reason for crash is not "Vista is silly", but they probably have some real bug in code, just not manifesting on XPs or keeping hidden/ignored, like it was with working some Win98 proggies crashing on XPs.

Agree.

In my experience, almost 99.9999% of GPFs are errors of the programmer or the compiler producing bad code.
Again, in my experience, with PB compilers, 99.9999% of GPFs are errors of the programmer (me :D )

[Charles Pegge]

seems nice job for SSE ;)



The next bit might be a bit tricky for SSE. I am thinking aloud here:

Non Head-on collisions.

considering 2d:

In a head-on collision, the angle of the impact point on the sphere surfaces is the same as the angle of travel bringing the two spheres together.

But supposing the spheres brush past each other. The have made contact but they do not affect each other. These are two extremes. The point of contact in this case is at right angles to the angle of travel. When the spheres make contact the closing velocity between them is zero so there is no transfer of momentum.
(ignoring the possibility of spin for now.).

If we take the difference between the angle of travel and the angle of contact and apply ABS COS, we obtain a factor which reduces the effect of the impact, goind from 1 for head-on collision to 0 for brush-past.

Then the rest is fairly straight forward. We resolve the collision velocity into x and y velocities using the contact point angle.

These x & y velocities are then apportioned by mass to get the deflections for each sphere.

The trick is to get all the signs the right way round :)

[kryton9]

Charles you make it actually very understandable. Thanks for the explanations!

Eros and Petr, I know, I just enjoy knocking on Microsoft as many do, but seeing what goes on underneath and that they have thousands of coders writing for it, it is amazing it works at all, definitly a difficult task. On the otherhand, they had all these years to really bring the next generation OS together after NT based and I think they failed. They should have said the world has really changed, if you need to run old applications then XP will be last OS supporting those apps and continued XP for a couple more years. In the meantime introduced the next generation language, complete with no ancient dependencies. The only common thing would be supporting old data formats like in office products and db applications. This has nothing to with the OS, so that in a couple of years everyone could have transitioned to a better future. So that is a big opportunity that the world has missed this decade because of their decisions. So Microsoft in many ways has held where we could be today.
For example, it took them till the 1995 to get to where Apple was in 1984 except with support for color really being the only difference. And now since the introduction of XP till now, almost 7 years wasted on what could be the next true generation ground breaking OS.

[ErosOlmi]

Kent,

please consider that you can still execute applications written under 1995 Microsoft OS. Try to execute now an application designed for 1995 Macintosh: now way.
Microsoft has spent millions of work days in compatibility tests, in supporting developers, in keeping things compatible and documented. For me this is important.

Others (like Apple) made a technology jump but they could effort it for varius reasons: no vaste user basis, not many developer developing millions of different applications, they just ignore claims, they were just looking at candy and much less on substance.

What will be the NEXT version of whatever Microsoft OS, I'm sure I will still be able to execute my applications (if I followed MS documentations)

Ciao
Eros

[kryton9]

Eros, I understand that many like backward compatibilty and of course you can't lose work from recent times... so that is why they could have made XP the last one to support old apps.

Now make a totally new, you need new apps OS, this one can open data that is needed more than apps for companies usually. Then companies wanting to move to a new system and better OS can and invest in their programmers working on new OS made for the future instead of dealing with an OS filled with patches to adjust to the changes over the years.

Then companies in between who need their custom apps can use XP that will be supported giving them years to port their apps to the new OS. That is the route I think Microsoft should have made with Vista and dropped the ball. My opinion of course :)

[kryton9]

Charles found this tutorial example from MASM32 forums.

Is the correct type of code that I can study and work towards learning 32 bit assembly?

The author of this code is: Iczelion@galaxycorp.com
The code is from Tutorial 2

.386
.model flat, stdcall
option casemap:none
include \masm32\include\windows.inc
include \masm32\include\kernel32.inc
includelib kernel32.lib
include \masm32\include\user32.inc
includelib user32.lib

.data
MsgCaption db "Iczelion's tutorial no.2",0
MsgBoxText db "Win32 Assembly is Great!",0

.code
start:
invoke MessageBox, NULL,addr MsgBoxText, addr MsgCaption, MB_OK
invoke ExitProcess,NULL
end start

[Charles Pegge]

Hi Kent,
yes but this code is heavily laced with MASM macros so most of the raw assembler is hidden away. If you seek out the MASM tutorials that deal directly with the 32 bit instructions then that is a good starting point. Intel notation is the most widely used instruction format but you may also encount AT&T notation, (default for the GAS assembler), where all the operands are the opposite way round :-[. This format, I understand, is mostly emitted by compilers, not humans these days.

Elastic head-on collision model

Now before I ruin this code, I am posting the head-on collision model for the spheres. I had to correct the algorithm slightly - so simple yet elusive.

You will see that I have removed the downward displacement and given the balls velocity elements. Each ball kicks off with a random vx and vy to get it moving. There is commented out gravity force too, if you want to try it

[ErosOlmi]

Really fantastic!
Thanks

[Petr Schreiber]

Thanks Charles,

worked great! Just could not find where I can uncomment that gravity.


Petr

[ErosOlmi]

Petr, search for "gravity" in code.
It is just one line to un-comment.

[Petr Schreiber]

Thanks Eros,

I did it before but somehow missed where, now it works - thanks!


Petr

[Charles Pegge]

Right, I've emerged from my trance.

Here is the more complex but more realistic collision model - I've set it up with extra large balls limited to 24 in number so that the deflections can be seen in detail.

It was necessary to deploy a momentum governor which ensures that the overall momentum/mass is constant and does not escalate due to obstructed rebounds, which are inevitable when the ball positions are updated on a per-frame basis.

[ErosOlmi]

Absolutely realistic!

[Petr Schreiber]

Thanks Charles,

this is really good ( especially with gravity enabled )!


Thanks,
Petr

[kryton9]

Finally got thinbasic back on the eeepc. The new Demos are amazing Charles. I can't believe I am able to see that level of preformance on this 900Mhz cpu with intel built in graphics chip.

It is so much fun watching them bounce off of each other. Your module should be classified in a new section called Tubro Modules, or Turbo thinBasic Modules!!!

[Charles Pegge]

We can get further performance improvements in several ways:

- Take on the rest of the collision procedure.
- Make more use of the FPU stack.
- use bounding boxes to eliminate most radius testing.
- use zones for large population collision tests.

The last one is the most interesting; we are currently limited by this formula:

tests=(n*n-n)/2

which kills off performance rapidly as the population rises. This could be brought under control by splitting the container into a grid and maintaining a list of which spheres are in each cell. This localises the collision testing for each ball. - then we could do thousands :)

[Petr Schreiber]

Hi Charles,

very good plan.
I just do not understand the "Take on the rest of the collision procedure"? :-[


Thanks,
Petr

[Charles Pegge]

Simply to manage the outer loop, Petr including the velocity increment, gravity and container boundaries.

[Petr Schreiber]

Oh ... sure,

I am tired or something, I parsed "rest" as verb instead of ... you know the other kind of word ;D


Petr