Sign in to follow this  
Purgatorio

What Would You Need for a Solar System Simulation?

Recommended Posts

Purgatorio    118
I am interested in creating something that is very similar to a solar system simulation -- the creation, movement and effects of what is present in the simulation is important.

Ex. If a Supernova occurred and there were surrounding planets and stars, the engine/graphics/etc would need to know how and what it is supposed to do.

Further, a part of this 'simulation' is the ability to create a system or galaxy, and the engine/graphics/physics/etc. would need to be able to allow for the logical processes, effects and other etcetera that occur (forming stars, making stars/suns go supernova, etc).

So with that said, this would be something to be used on the iPad and iPhone, using gestures similar to what a mousepad would offer + some (pinching, pulling, flicking, etc.).

- What engine(s) would be best for creating this program
- What languages would be best for creating this program
- What software would be best for generating the effects/graphics (lights, particles, gaseous forms)
And is there anything else I would need to know or consider in the pursuit of this program?

Because I am asking these questions, it's possible that what I've mentioned is not feasible for the console I mentioned; if that's the case, please let me know.

Thanks.

Share this post


Link to post
Share on other sites
Purgatorio    118
[font="arial, verdana, tahoma, sans-serif"][size="2"]You'll have to forgive me if I say something that doesn't make sense (I'm not a programmer), how huge of a programming undertaking might this be? I gather that this will involve algorithms (that I am equally unfamiliar with), but what level of expertise/knowledge would a user need to do a mock up in Unity?[/size][/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][size="2"]I should say just to avoid any issues: I'm attempting to research the graphical/programming requirements of creating such a program, so when/if I am given an opportunity to create it, I know what to look and ask for.[/size][/font]

Share this post


Link to post
Share on other sites
shadowisadog    3217
[quote name='Purgatorio' timestamp='1313797656' post='4851432']
[font="arial, verdana, tahoma, sans-serif"][size="2"]You'll have to forgive me if I say something that doesn't make sense (I'm not a programmer), how huge of a programming undertaking might this be? I gather that this will involve algorithms (that I am equally unfamiliar with), but what level of expertise/knowledge would a user need to do a mock up in Unity?[/size][/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][size="2"]I should say just to avoid any issues: I'm attempting to research the graphical/programming requirements of creating such a program, so when/if I am given an opportunity to create it, I know what to look and ask for.[/size][/font]
[/quote]

I can tell you that the program you are describing seems unrealistic from a number of perspectives. The computational requirements sound immense for the scope you are describing. the iPad/iPhone does not have near the processing power for "forming stars, making stars/suns go supernova, etc)" especially in real time. You could make a very scaled back, precomputed and low geometry (relatively) version of a galaxy with enough trickery but it wouldn't be anywhere near what you are describing.

I will provide the advice that if you are potentially going to receive an offer to do this for money, that you not do it. If you are not a programmer and you do not know the scope of the project, you are simply not in a position to be able to reliably create it (or even know what you are getting yourself into).

Share this post


Link to post
Share on other sites
Purgatorio    118
[quote name='shadowisadog' timestamp='1313809089' post='4851464']
[quote name='Purgatorio' timestamp='1313797656' post='4851432']
[font="arial, verdana, tahoma, sans-serif"][size="2"]You'll have to forgive me if I say something that doesn't make sense (I'm not a programmer), how huge of a programming undertaking might this be? I gather that this will involve algorithms (that I am equally unfamiliar with), but what level of expertise/knowledge would a user need to do a mock up in Unity?[/size][/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][size="2"]I should say just to avoid any issues: I'm attempting to research the graphical/programming requirements of creating such a program, so when/if I am given an opportunity to create it, I know what to look and ask for.[/size][/font]
[/quote]

I can tell you that the program you are describing seems unrealistic from a number of perspectives. The computational requirements sound immense for the scope you are describing. the iPad/iPhone does not have near the processing power for "forming stars, making stars/suns go supernova, etc)" especially in real time. You could make a very scaled back, precomputed and low geometry (relatively) version of a galaxy with enough trickery but it wouldn't be anywhere near what you are describing.

I will provide the advice that if you are potentially going to receive an offer to do this for money, that you not do it. If you are not a programmer and you do not know the scope of the project, you are simply not in a position to be able to reliably create it (or even know what you are getting yourself into).
[/quote]

It's possible that I made it sound more complicated than I intend for it to be. Here's what I was going for, with a bit more depth:

The first mode would provide a 'canvas' of space and gaseous forms/debris. The user would use gestures to compact, swirl, move and manipulate the gas to form solid entities that could be further manipulated to create stars, planets, nebulas, etc. This isn't looking to present an exact model, but there would be events that could occur during use (supernovae) that would destroy and change what they've created, or in certain events, open access to new creations (molecular clouds).

Ex. A system of planets and stars has been created, but due to the proximity of certain celestial entities, a supernova has begun; as it runs its course and completes, the effects of a supernova would occur: the colors and forms would expand, explode -- what have you.

So it's less about being an exact replica of the myriad processes, and more a basic yet visually appealing version of what goes on in space. At the moment I can't think of a game to compare it to, but hopefully I've explained it a bit more accurately.

So what you mentioned, "a very scaled back, precomputed..." version sounds like what I am going for. I was just interested in finding out what engine would be best in handling and replicating effects for the particles, gas, etc. for the target console (iPad/iPhone). It's also possible that even a scaled down version like this still couldn't function on the newest generation of ipads, but essentially it would be intended for anything with touch/motion capability (PS3, Kinect, etc). I appreciate your candor, however; I definitely was not looking to explore the mathematical computations of our universe, but was hoping that I could present something that offered the same awe and beauty of the ever-changing cosmos without bogging the user down with the unknown science of it.

Share this post


Link to post
Share on other sites
frob    44974
[quote name='Purgatorio' timestamp='1313810642' post='4851469']
It's possible that I made it sound more complicated than I intend for it to be. Here's what I was going for, with a bit more depth:

The first mode would provide a 'canvas' of space and gaseous forms/debris. The user would use gestures to compact, swirl, move and manipulate the gas to form solid entities that could be further manipulated to create stars, planets, nebulas, etc. This isn't looking to present an exact model, but there would be events that could occur during use (supernovae) that would destroy and change what they've created, or in certain events, open access to new creations (molecular clouds).

Ex. A system of planets and stars has been created, but due to the proximity of certain celestial entities, a supernova has begun; as it runs its course and completes, the effects of a supernova would occur: the colors and forms would expand, explode -- what have you.

So it's less about being an exact replica of the myriad processes, and more a basic yet visually appealing version of what goes on in space. At the moment I can't think of a game to compare it to, but hopefully I've explained it a bit more accurately.

So what you mentioned, "a very scaled back, precomputed..." version sounds like what I am going for. I was just interested in finding out what engine would be best in handling and replicating effects for the particles, gas, etc. for the target console (iPad/iPhone). It's also possible that even a scaled down version like this still couldn't function on the newest generation of ipads, but essentially it would be intended for anything with touch/motion capability (PS3, Kinect, etc). I appreciate your candor, however; I definitely was not looking to explore the mathematical computations of our universe, but was hoping that I could present something that offered the same awe and beauty of the ever-changing cosmos without bogging the user down with the unknown science of it.
[/quote]

How many particles of gaseous forms and debris are you talking about? Hundreds? Thousands? Millions?


The iPad 2 has 1024x768, or 786432 pixels on the display, so you're probably going to want a few tens of thousands of particles to fill your screen enough to be pretty. More would look nicer, but it would be unrealistic.



How will they "compact, swirl, move and manipulate the gas"? Faking it with a simple relaxation system and a few hundred particles wouldn't be too bad to process. To follow the actual physics equations would not be something the iPad could do in real-time since every particle can have interactions with every other particle thanks to gravity and other effects. There are tricks to estimate the values using spatial partitioning, but the math involved is still daunting.

It sounds like you want every particle to interact with all the other particles, with everything updating in real time. That's an all-to-all comparison. You can optimize it into blocks, making it an all-to-many comparison. Either way, it is a polynomial growth algorithm. It is similar [url="http://en.wikipedia.org/wiki/File:Exponential.svg"]to the blue line in this wikipedia image[/url], only the value will be much bigger than 3. But the x^3 is a good starting point for a simple example. Note how in that simple example, just ten items would result in 1000 compares. Having 100,000 particles in a naive all-to-all simulation would result in over 1 quadrillion (1E16) comparisons.




That means a naive implementation of 100,000 particles would take about 12 days to calculate a single frame on the iPad, if you are lucky.

(This is why modern graphics cards are so incredible for processing. The GTX 590 clocks in at about 2.5 teraflops, meaning it could do that same work in about 16 minutes.)





Here's a simple sanity check.

Assume just 1000 particles. Each particle can be any size, you can mix star-size particles, planet-sized particles, dust-size particles, whatever, but only 1000 of them. The iPhone and iPad have 1GHz processors. They have very small caches, so the particle system simulation will clearly be cache-bound (which requires serious programming work to overcome), followed by CPU bound. Considering the update speed for interactivity and the load from other apps, you get about 15 million processor cycles per graphics update. Divide that by 1000 particles and you've got a mere 15 thousand processor cycles to check against the other 999 particles. That's roughly 15 math instructions per particle comparison. A few 'simple' physics equations like the fluid dynamics of swirling and the pull from gravity are going to take a several thousand operations per update, not 15 cycles. Using spatial optimizations and fairly fake physics you could probably get that number down to around 1000 total cycles per particle per update, although it is probably worse because of the small cache. 1000+ cycles is a long way from the roughly 15 cycles you have in an all-to-many update system.

If you reduce it to about 500 particles, you start to get into a feasible processing range on the hardware. It will still take some serious computer science work to encode the equations, optimize to use the processor's cache effectively, and a good knowledge of the math and approximation trickery involved to keep the processing effort from exploding with all-to-all comparisons, but it would at least be feasible.


Using a set of fake physics in a relaxation system could probably handle 1000-2000 particles if you work really hard at the math behind the magic. If you are only pushing around a few items near the touch point you could probably get into the 5000 or slightly higher range, but it sounded like you wanted every particle to remain fluid.

Neither of these gets you anywhere close to the few tens of thousands of particles you would need for a pretty and realistic display on the iPad.

Share this post


Link to post
Share on other sites
Purgatorio    118
Frob @ Would it be possible to make the gaseous forms follow liquid physics but just present them, visually, as having more of a particle/dust effect or appearance? As opposed to dealing with that number of individual particles? I wouldn't actually want each particle to interact with each other, but rather different types of particles. So if the gaseous cloud is made of red particles, and I compress a chunk of them -- they become a larger, solid blue particle. Each type of particle would be assigned a set of characteristics, ideally. And a gaseous form would be its own entity that can be combined with other gaseous forms, or divided into chunks, but it wouldn't have to go so far as separating individual particles, of which as you've said, could and would be many.

ex. Red particles can be swirled, compacted and moved with the touch of your finger (so you're moving the entire cloud of gas as if it were a liquid)
Blue particles would attract red particles when in a certain proximity and can keep them in orbit or be enlarged by 'rolling' it through more Red particles
Yellow particles cause all other particles to experience a reverse in their properties while in proximity, over a slow period of time ( Blue particles would repel Red particles, etc).

It's quite possible that I'm simply trying to explain the same thing you've already told me, and if that's the case I apologize. What you've said makes sense though. I just thought this sort of thing would be a next experience, but if it's too impossible for the mobile devices I'd likely just keep it in my portfolio as a concept.

Share this post


Link to post
Share on other sites
shadowisadog    3217
[quote name='Purgatorio' timestamp='1313851019' post='4851606']
Frob @ Would it be possible to make the gaseous forms follow liquid physics but just present them, visually, as having more of a particle/dust effect or appearance? As opposed to dealing with that number of individual particles? I wouldn't actually want each particle to interact with each other, but rather different types of particles. So if the gaseous cloud is made of red particles, and I compress a chunk of them -- they become a larger, solid blue particle. Each type of particle would be assigned a set of characteristics, ideally. And a gaseous form would be its own entity that can be combined with other gaseous forms, or divided into chunks, but it wouldn't have to go so far as separating individual particles, of which as you've said, could and would be many.

ex. Red particles can be swirled, compacted and moved with the touch of your finger (so you're moving the entire cloud of gas as if it were a liquid)
Blue particles would attract red particles when in a certain proximity and can keep them in orbit or be enlarged by 'rolling' it through more Red particles
Yellow particles cause all other particles to experience a reverse in their properties while in proximity, over a slow period of time ( Blue particles would repel Red particles, etc).

It's quite possible that I'm simply trying to explain the same thing you've already told me, and if that's the case I apologize. What you've said makes sense though. I just thought this sort of thing would be a next experience, but if it's too impossible for the mobile devices I'd likely just keep it in my portfolio as a concept.
[/quote]

Well the more you simplify things down, the further away you go from a "Solar System Simulation" which is the topic of your thread. If you really want to do it for the experience, why don't you simply try it? Even if you fail you are likely to learn a good bit in the process and you should gain a better understanding of the iPad processing limitations.

Share this post


Link to post
Share on other sites
frob    44974
[quote name='Purgatorio' timestamp='1313851019' post='4851606']
Frob @ Would it be possible to make the gaseous forms follow liquid physics but just present them, visually, as having more of a particle/dust effect or appearance? As opposed to dealing with that number of individual particles? I wouldn't actually want each particle to interact with each other, but rather different types of particles. So if the gaseous cloud is made of red particles, and I compress a chunk of them -- they become a larger, solid blue particle. Each type of particle would be assigned a set of characteristics, ideally. And a gaseous form would be its own entity that can be combined with other gaseous forms, or divided into chunks, but it wouldn't have to go so far as separating individual particles, of which as you've said, could and would be many.

ex. Red particles can be swirled, compacted and moved with the touch of your finger (so you're moving the entire cloud of gas as if it were a liquid)
Blue particles would attract red particles when in a certain proximity and can keep them in orbit or be enlarged by 'rolling' it through more Red particles
Yellow particles cause all other particles to experience a reverse in their properties while in proximity, over a slow period of time ( Blue particles would repel Red particles, etc).

It's quite possible that I'm simply trying to explain the same thing you've already told me, and if that's the case I apologize. What you've said makes sense though. I just thought this sort of thing would be a next experience, but if it's too impossible for the mobile devices I'd likely just keep it in my portfolio as a concept.
[/quote]

That's a totally different question.

Can you make a simple particle system with tens of thousands of particles or sprites that you can interact with in real time? Sure.

Can you make it look pretty? Sure.

Can it be interactive? Probably, as long as you don't have too many particles getting updated every frame. Once you get too many moving you will see framerate drop rapidly.

Will that be even remotely accurate for real physics? Nope. Not even close.


Will this give a realistic view of a star going supernova, or collapsing dense areas into a star? Absolutely not. Even if you broke such a star into 1kg chunks you'd still be looking at 10^30 particles.




There are simple relaxation models where you only need to compute the particles that get bumped into as it moves. It isn't Newtonian physics, nor it is a fluid dynamics simulation, but would be something animating and potentially swirling.

A person or small team could make a fake, pretty-looking, processor intensive simulation that has nothing to do with physical reality. That wouldn't be too bad if you knew what you were doing.



The real difficulty comes when you introduce all-to-all or all-to-many interactions. Those are rather terrible polynomial growth that won't give interactive results on any current single machine.

There is a very good reason that those who model and study these things invest fortunes into supercomputers. The work involved in physically-accurate processing is incredible.

Share this post


Link to post
Share on other sites
Hiwas    5807
[quote name='Purgatorio' timestamp='1313810642' post='4851469']
[quote name='shadowisadog' timestamp='1313809089' post='4851464']
[quote name='Purgatorio' timestamp='1313797656' post='4851432']
[font="arial, verdana, tahoma, sans-serif"][size="2"]You'll have to forgive me if I say something that doesn't make sense (I'm not a programmer), how huge of a programming undertaking might this be? I gather that this will involve algorithms (that I am equally unfamiliar with), but what level of expertise/knowledge would a user need to do a mock up in Unity?[/size][/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"][size="2"]I should say just to avoid any issues: I'm attempting to research the graphical/programming requirements of creating such a program, so when/if I am given an opportunity to create it, I know what to look and ask for.[/size][/font]
[/quote]

I can tell you that the program you are describing seems unrealistic from a number of perspectives. The computational requirements sound immense for the scope you are describing. the iPad/iPhone does not have near the processing power for "forming stars, making stars/suns go supernova, etc)" especially in real time. You could make a very scaled back, precomputed and low geometry (relatively) version of a galaxy with enough trickery but it wouldn't be anywhere near what you are describing.

I will provide the advice that if you are potentially going to receive an offer to do this for money, that you not do it. If you are not a programmer and you do not know the scope of the project, you are simply not in a position to be able to reliably create it (or even know what you are getting yourself into).
[/quote]

It's possible that I made it sound more complicated than I intend for it to be. Here's what I was going for, with a bit more depth:

The first mode would provide a 'canvas' of space and gaseous forms/debris. The user would use gestures to compact, swirl, move and manipulate the gas to form solid entities that could be further manipulated to create stars, planets, nebulas, etc. This isn't looking to present an exact model, but there would be events that could occur during use (supernovae) that would destroy and change what they've created, or in certain events, open access to new creations (molecular clouds).

Ex. A system of planets and stars has been created, but due to the proximity of certain celestial entities, a supernova has begun; as it runs its course and completes, the effects of a supernova would occur: the colors and forms would expand, explode -- what have you.

So it's less about being an exact replica of the myriad processes, and more a basic yet visually appealing version of what goes on in space. At the moment I can't think of a game to compare it to, but hopefully I've explained it a bit more accurately.

So what you mentioned, "a very scaled back, precomputed..." version sounds like what I am going for. I was just interested in finding out what engine would be best in handling and replicating effects for the particles, gas, etc. for the target console (iPad/iPhone). It's also possible that even a scaled down version like this still couldn't function on the newest generation of ipads, but essentially it would be intended for anything with touch/motion capability (PS3, Kinect, etc). I appreciate your candor, however; I definitely was not looking to explore the mathematical computations of our universe, but was hoping that I could present something that offered the same awe and beauty of the ever-changing cosmos without bogging the user down with the unknown science of it.
[/quote]

Having done a fair amount of work on an aborted god game based on something similar to this, I can tell you that this stuff is not easy on several levels and it is also very memory intensive:

1. Massive levels of detail are required. Most engines won't be able to handle the requirements since you have to have potentially hundreds of levels of detail with bidirectional merge/expand abilities.
2. Simulation accuracy goes out the door, you can't maintain the detail levels as you zoom out. It has been a long time but basically it is a case of exponential memory requirements for your various levels of detail. We used an octree system and as you zoom in we replace a single particle in a node with potentially hundreds, as you zoom out you merge hundreds into a single particle. The back and forth means that accuracy is constantly being lost.
3. Float/double accuracy is not even vaguely close enough to deal with most of this. You need multiple levels of coordinate system rescaling. This is actually one of the more difficult problems as all the underlying systems have to be promoted to screen space prior to rendering which gets costly with so many levels of detail involved.

All said and done, we managed to get this working on 10 year old hardware which is about equivalent to an iPad anymore but once this was working there was hardly any CPU/Memory left to make a game. Actually rendering things is fairly simple once the above complications are dealt with, marching cubes, empirical surfaces etc for the larger things and particles for most of the detail work. It is all rather complicated but nothing especially unheard of.

Share this post


Link to post
Share on other sites
Purgatorio    118
[quote name='shadowisadog' timestamp='1313854012' post='4851618']
Well the more you simplify things down, the further away you go from a "Solar System Simulation" which is the topic of your thread. If you really want to do it for the experience, why don't you simply try it? Even if you fail you are likely to learn a good bit in the process and you should gain a better understanding of the iPad processing limitations.
[/quote]

I'm not looking to program anything personally. And a simulation doesn't necessitate an exact replica, at least that wasn't my ultimate goal; I didn't actually think the examples I gave would be this intensive of a program. I see explosions that affect objects in games all of the time, I was merely wondering if you could break down the same elements and principals into a simplistic idea of planets and stars, rather than guns, ammo, bombs, buildings, etc. Like a proof of concept for technology/programming.

The general consensus seems to be that this isn't practical, at least as it has been described. The concept was to present an empty amount of space with raw resource/material that could be used to create other entities. I'd probably just be typing at myself at this point to give further explanation. Perhaps I can revisit this at a later time.

Thanks.

Share this post


Link to post
Share on other sites
way2lazy2care    790
[quote name='shadowisadog' timestamp='1313854012' post='4851618']
Well the more you simplify things down, the further away you go from a "Solar System Simulation" which is the topic of your thread. If you really want to do it for the experience, why don't you simply try it? Even if you fail you are likely to learn a good bit in the process and you should gain a better understanding of the iPad processing limitations.
[/quote]

I feel like you could optimize the problem a bit using some sort of flow graph similar to fluid dynamics without losing that much accuracy at all. Then it would just be an O(n*m) problem where n is the number of particles and m is the resolution of your graph. I actually think you could get it pretty precise.

This is a fun problem. I'm going to try to think of some other groovy stuff you might be able to do. It seems like there should be some way to get the n-body problem down to near constant time if we consider it more like n body's interacting with one space-time object and vice versa. It seems like you could boil it down to the sum of the equations for every body's influence then reapplied to each body. Still have to think about if it's even possible to implement that as trivially as it sounds (edit: I feel like the most trivial way would be what I said earlier, but I'm bored and I want to think about it more)

Share this post


Link to post
Share on other sites
Antheus    2409
[quote name='frob' timestamp='1313813492' post='4851477']
It sounds like you want every particle to interact with all the other particles, with everything updating in real time. That's an all-to-all comparison. You can optimize it into blocks, making it an all-to-many comparison. Either way, it is a polynomial growth algorithm. It is similar [url="http://en.wikipedia.org/wiki/File:Exponential.svg"]to the blue line in this wikipedia image[/url], only the value will be much bigger than 3. But the x^3 is a good starting point for a simple example. Note how in that simple example, just ten items would result in 1000 compares. Having 100,000 particles in a naive all-to-all simulation would result in over 1 quadrillion (1E16) comparisons.[/quote]

It's doable in real-time, but the method to do so requires understanding of astrophysics and some fairly specialized programming skills. The algorithms, if chosen and implemented properly are O(n) and can be tweaked to have very low constant factors. For a toy-like simulation which doesn't need accuracy it's quite possible to hit memory bandwidth before CPU becomes an issue.

But it's doable, I used to toy around with problems like this, but a native application is too difficult to distribute (aka monetize) and various managed platforms aren't capable of doing it.

But it's simply not something a non-programmer can do.

Share this post


Link to post
Share on other sites
way2lazy2care    790
[quote name='Antheus' timestamp='1314032296' post='4852389']
It's doable in real-time, but the method to do so requires understanding of astrophysics and some fairly specialized programming skills. The algorithms, if chosen and implemented properly are O(n) and can be tweaked to have very low constant factors. For a toy-like simulation which doesn't need accuracy it's quite possible to hit memory bandwidth before CPU becomes an issue.
[/quote]

Care to share so I don't waste my afternoon on stuff people have done already? <3

Share this post


Link to post
Share on other sites
frob    44974
[quote name='Antheus' timestamp='1314032296' post='4852389']
It's doable in real-time, but the method to do so requires understanding of astrophysics and some fairly specialized programming skills. The algorithms, if chosen and implemented properly are O(n) and can be tweaked to have very low constant factors. For a toy-like simulation which doesn't need accuracy it's quite possible to hit memory bandwidth before CPU becomes an issue.
[/quote]

Out of curiosity, how do you turn the all-to-many comparisons into an O(n) problem? By definition all-to-all or all-to-many problems are complexity O(n[sup]x[/sup]).

You can reduce the value of x to a low number through spatial tricks, you can make one pass to block out the space into zones, but even then you still must do a pass at every node with every block, which still stays polynomial with x>1.

Share this post


Link to post
Share on other sites
Antheus    2409
[quote name='frob' timestamp='1314035318' post='4852413']
Out of curiosity, how do you turn the all-to-many comparisons into an O(n) problem? By definition all-to-all or all-to-many problems are complexity O(n[sup]x[/sup]). [/quote]
Barnes Hut (or variation of tree code) or Fast Multipole Method (or whatever multipole representation you choose). They are both approximations by definition but have been shown to work well in practice, even for actual astrophysical simulation. There is also a rant from Barnes on how CS experts could never come up with such clever optimization...

BH is nlogn. FMM is O(28n). Now you can solve nlogN = 28N and get that, for practical purposes (CS academia would cry foul) you can assume that both are O(n), but for less than 2^28 elements (billion particles, ~4-8GB of memory, vastly beyond reasonable non-clustered problems), BH has lower constant factor. Tree construction of BH can be performed what is essentially a radix sort, which is O(n) and benefits greatly from Morton ordering. FMM uses implicit grid.

BH is branch and bound, runs well on CPU, easy to parallelize, benefits from uneven distribution. FMM prefers even distributions, but is best suited for GPU. BH variations using kd-tree instead of quad or oct-tree exist, but do not benefit much from GPU.

Rendering is a matter of available hardware.


As said, it's doable. But either method will use all the computing power you throw at it, so iPad or iPhone are not ideal targets, but likely are doable for small n.

For trivial cosmological simulation, create n particles (of same or slightly different mass), vary initial velocity a bit and let it run. Use the information provided by methods above (meta nodes in BH or coarse grid of FMM) to resolve collisions. Tweak the algorithm a bit to compensate for very large objects.

And you get a rudimentary simulation of solar system evolution. n=1,000,000 is perfectly doable on a mid-range PC, especially if you take into account numeric ranges and implement everything using integers (initial particle mass = 1, sum(particles) < 2^64). Hence the "specialized programming knowledge", you need to aggressively optimize at expense of accuracy (works for toy problems). Simulating 2D only reduces constant factors further.

A possible tweak would be to run multi-level simulation. "gas" particles are simulated by one simulation (perhaps even fluid solver) while "things that clumped" are simulated by another, making collision between tangible objects simpler.

For accurate simulations, CPU does become a problem, since individual interactions need to be resolved within a certain error, but those run on clusters for days, so it's a different problem.

Share this post


Link to post
Share on other sites
frob    44974
[quote name='Antheus' timestamp='1314036841' post='4852430']
[quote name='frob' timestamp='1314035318' post='4852413']
Out of curiosity, how do you turn the all-to-many comparisons into an O(n) problem? By definition all-to-all or all-to-many problems are complexity O(n[sup]x[/sup]). [/quote]
Barnes Hut (or variation of tree code) or Fast Multipole Method (or whatever multipole representation you choose). They are both approximations by definition but have been shown to work well in practice, even for actual astrophysical simulation. There is also a rant from Barnes on how CS experts could never come up with such clever optimization...
[/quote]


Thanks, that's some interesting reading.

Follow up papers from those show the error is about 0.1% per iteration for 10,000 particles with near-uniform distribution, a little more for non-uniform distributions. That's horrible error for scientific purposes that need to run for for an extended period, but reasonable for a toy app like this.

The constant part is quite large and it jumps around in data reads, so I still doubt it would be feasible in real time on such a small cache processor as the iPad for this scale of particles.

Share this post


Link to post
Share on other sites
Antheus    2409
[quote name='frob' timestamp='1314040711' post='4852459']

Follow up papers from those show the error is about 0.1% per iteration for 10,000 particles with near-uniform distribution, a little more for non-uniform distributions. That's horrible error for scientific purposes that need to run for for an extended period, but reasonable for a toy app like this.[/quote]
It depends. 0.1 may lead to evolution of Universe B instead of Universe A. But how do you know which one is "correct"? Even with full computation you still have rounding errors.

For purpose listed above, one important criteria is stability of orbits and that can be controlled in different ways. Other effects may matter less.

[quote]The constant part is quite large and it jumps around in data reads, so I still doubt it would be feasible in real time on such a small cache processor as the iPad for this scale of particles.
[/quote]

iPad is a bit on the low side, but as said, algorithms scale really well.

But I still don't know of any engine that would be suitable for such task out-of-box. The physics would need to be not only tailored for the problem, but also squeezed small enough to fit into mobile devices.

There is a lot of potential uses for touch/gesture interfaces, if only they had the power of PC gaming rigs. Then we could do some completely crazy stuff.

Share this post


Link to post
Share on other sites
Purgatorio    118
Things wouldn't need to necessarily occur in real-time. There could be a brief cinematic to show the effects and when it ends, you're left with the results of the event. Not as awesome, of course, but again -- this didn't need to be an exact, real-time replica. Just simulate likely outcomes and processes. And by simulate I mean produce -- nothing happens without the player's direct or indirect involvement.

Everything that's been said on this topic has been way over my head.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this