#### Archived

This topic is now archived and is closed to further replies.

# Solving the 'sandbox' desire, geniuses needed!

This topic is 5775 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Imagine, a snowlandscape where you are in, the northpole, everything is snow, snow masses. The ''sandbox'' feature: Being able to manipulate these snow masses and shape all kinds of things out of it. A simple tactic to manipulate that landscape with an avatar would be ''sucking'' and ''spitting''. You can ''suck'' snow into your mouth and spit it out again. Objective: building cities (and having snowbal fights)Question: Is it possible? A possible solution, or how such a map could be build, a 3d cube divided into very tiny cubes all next to eachother. Those little cubes, almost invisible for the eye, like a pixel, have two possible states, ''on'' or ''off'', eather visible, the mass is visible, the snow is there or ''off'', no snow, empty, air. Who has more information on this? Is this possible to implement and how would you do it? Anyone seen something before that looks like this? Anyone able to realize this?

##### Share on other sites
From what I heard, it''s extremely difficult to model any kind of fluid behavior. But if someone can come up with a good way, I want to know too

##### Share on other sites
fun... I wouldnt make it be 3d. Do something like worms armegetton (sp?) (2D) except 1) without the weapons (mabye) (except the ninga rope) 2) realtime 3) worms "suck and spit" the dirt..

##### Share on other sites
Yes, it can be done. If it can be done in realtime on consumer level hardware is another question. But, if you optimize it to the extreme, and use some kind of LOD scheme, it might work on a good 3D card.

This is how you do it:

You have a 3D volume of space that is divided with a 3D grid, creating voxels. Now, what makes your snow flakes flow around ? Air. So, you have to model air dynamics. You have to apply a fluid dynamics simulation onto that 3D voxel grid, for example the Navier Stokes equations, that are commonly used for that kind of problem. You can see it as a huge 3D integrator that processes forces applied to the grid cells, computes cell pressure, air velocity and movement.

You now have a dynamic pressure field. Next step is to create flow-lines along the 3D isobares, that are visualized as long splines, flowing through the 3D volume, according to winds and acting forces. Your snowflakes are particles, that have to be programmed to follow those flowlines, with a certain amount of fractal variancy (eg. Perlin noise).

While the result is very impressive, it''s *extremly* hard to code that, esp. a stable 3D NSE solver with implicit integrator (the standard Euler integrator won''t bring you very far here). I have done something similar for a smoke / vapour simulator, it was *very * hard to get it approx. stable. But it works in realtime.

If you''re serious about doing that, I could dig out some interesting papers, with equations, etc. There is a lot of research being done in this domain.

##### Share on other sites
Very interesting idea, I''ve never even thought about this. Basically making snow forts and having snowball fights for territories, right?

Now do you assume you can dig down into the terrain or do you just add to it?
If you just add you can ''get'' snow that doesn''t effect the amount on the floor, and then use this snow to build stuff or throw.
The other option is to allow the terrain to be altered. Where getting snow decreases the amount on the ground.

This sounds like a very doable engine if designed correctly. I would think that a polygon terrain engine would be prefered, a voxel engine might be interesting however not many people have designed full voxel engines and it is has not been explored.

The primary issue that would be is the level of complexity. To create realistic scenes of snow you would need a very high density. While you could have a variable lod for rendering just the memory usage would be high.

Say a terrain that is 100ft x 100ft, a moderate size area, to have somewhat realistic terrain you would probably want to model down to inches. So that''s an array of 1200 x 1200, now you would also have to have a good gradient of ''depths'' so I''d think that you would want 16bit so that''s 1200x1200x2 bytes, now each vertex would also have to store a color (it''s snow so just various white),that could be another byte (probably could also have realtime shadows). Now that''s 4.3MB, not too bad. However if you want to have 3d terrain, ie able to go under snow, say making a igloo, you would have to be able to store 3 layers, the top layer, bottom of top layer, top of bottom layer. So that would be about 12.9MB which is alot bigger. Other options would be able to store a static terrain, and dynamic ''stuctures'' above ground.

Another option could be something like the cube 3d engine posted a while back on opengl.org that was a 3d game using a 2d map, that had dyncamic heights, floors and ceilings.

I''d definately suggest looking into this.

##### Share on other sites
Voxel technology is based on the concept of a 3D pixel (A voxel is a 3D pixel), being essentially what you described, 3D cubes the size of a pixel. This tech is what''s used in Novalogic''s graphics engines to create the smooth scrolling landscapes in their games (though they use standard polygon methods for rending all other objects). One of the problems this technology is plagued with is the lack of hardware acceleration for it. Games like Delta Force need to be run at lower resolutions cause the landscapes are rendered with software, with very little if any hardware acceleration. But that lack is due to it''s lack of usage in the gaming industry. I don''t know if anyone besides NovaLogic uses it today (one of those catch 22 things). It could be a great option for 3D engines if it had more hardware support.

Once you get into the concept of dynamically deformable voxel landscapes... now you''re talking SERIOUS number crunching. We''re talking totally crippling even the fastest of PCs out there today. Trying to do it using tiny 3D polygon rendered cubes isn''t gonna fly either. Each cube will need a minimum of 12 polygons (2 per side). To get decent resolution landscapes you''re going to need a serious number of cubes. Even if we say 1 cube per square inch (using real world measurements just to get a gauge, not going to concern ourselves with scaling it to game dimensions) that''s 144 cubes per square foot. 1,728 cubes per cubic foot (you want some depth to that snow, don''t you? a 10 square yard area 1 foot deep would require 1,555,200 cubes, that''s 18,662,400 untextured, unlit polygons for a 10 yard square. That''s not including the physics engine for those 1.5 million cubes. Ouch.

##### Share on other sites
You could fake it.

If the snow isn''t a particle until it leaves the ground it should be easier at least. You then need to show the actual snow moving, probably using those fluid dynamics someone mentioned earlier. For the terrain, you need something that can deform and that you can deform easily. I think I remember seeing a tutorial on deformable terrain here on gd.net but I''m not sure. I''m also not a graphics person so I don''t know what would be easiest to deform. I''m also pretty sure the next term is used really for isometric games, but maybe you wanna go isometric, but the important part is what the word sounds like, not actual meaning, height-map!

##### Share on other sites
AP: heightmaps are actually exactly what he needs.

Avator: Make a heightmap terrain, use fluid dynamics to make snow fly around, and when it settles on the ground, simply update the heightmap. Couldn''t be easier (at least the terrain deformation part). No need for voxel rendering whatsoever.

##### Share on other sites
Oh, and this part is probably pretty obvious but I forgot to mention it. You tie in the deformation according to a function relating it with sucking time.

Don''t forget level-of-detail, lod.

Anyone know if the force is going to lessen linearly or exponentially or geometrically or logarithmically?

##### Share on other sites
As far as building walls or what not have the player able to spit out different "streams" like you can use different brushes in your paint program. Have a narrow stream for walls and or a tree trunk then change to a bigger fluffier brush for the top of the tree or to cover a large area or whatever.

##### Share on other sites
This is avator2138, changed my name into Mandarijn

First of all, thank you all for your contributions!

Jindocai, happy you like the gameplay aspects, of course the terrain should be altered, that''s the most important thing, being able to throw with that snow is interesting too, but secondary to the shaping experience, shaping your terrain in-game with a simple building technic, sucking and spitting, is revolutionary (or not anyone?). It won''t be snow but clouds where the people are living in. I''m not shure yet whether shooting something, clouds then, will be possible. Look for me at the game design platform, I''ll discuss some topics on the gameplay aspects overthere. About that ''cube'' engine with transformable heights, ceilings and walls, I can''t find it on that opengl.org site. Can you find it back, or something comparable?

About the technology, Yan L. you seem to be very dynamic on that level. Your first solution is really cool, having such a dynamic pressure field would be impressive indeed. Although too complex for now such a construction has lot''s of power.

nonnus29, "streams" good idea, you will be able to widen or narrowing the opening of your ''sucky'' mouth and that way decide the thickness of your ''brush''.

Heightmaps!

Would it be possible to use this technic in really 3d, so that you not only can highten and lower the terrain but also can dig wholes or bridges.

The game is situated in the clouds. The people your playing in live in the clouds, they can walk on it and they eat crystals that grow on them (they can fall off the clouds too, jump from one cloud to the other or fly). Now it would be fantastic if they would be able to manipulate those clouds and shape all kinds of things out of it. The characristics of those clouds would be that they are sticky like snow but it''s not heavy, it doesn''t fall, it floats.

(to simplify, let''s say there is no wind, so when you blow out some clouds it stays on that place)

We could start with one big cloud. A big balloon object, a round heightmap. When you suck some cloud from the big cloud that round heightmap shrinkens a bit on that place, could be done vertical, you are standing on the cloud and suck from the ground just in front of you, but horizontal too, you are standing next to a big cloud (on the same cloud), and suck a whole into the big horizontal wall.

Is a 3d heightmap possible and is it the proper solution for the shaping cloud experience?

##### Share on other sites
The standard method for solving these kind of problems is the Finite Element Method (FEM) sometimes called Finite Element Analysis (FEA). Generally with these methods you define your problem space then you split it up into discreate volumes or areas (3d or 2d - lengths for 1d) by creating a mesh. The solution time will depend on the fineness of the mesh and the number of dimensions to consider. If you aren''t examining anything particually complex in terms of geometry you could probably get away with an extremelly course mesh & interpolating the results. If you''re serious about persuing this course I''d suggest you have a look at the books in a uni library - search for FEM, FEA & Fluid Dynamics - you may also find some useful stuff in the structural mechanics (very similar method of analysis - different eqn''s though, although similar principles to derive them). The books I''ve read that I can remember are by Bathe (The Finite Element Method ?) and "Programming the Finite Element Method" by Smith & Griffiths (pub. Wiley) [hope your FORTRAN 90''s good!]

As others have mentioned before it is slow, although accurate...I wonder if simple fluid dynamics will do the job you want (Benoulli etc.) especially if what you want is basically a sort of stream tube ? I was recently running a 2d flow sim on my 1GHz comp using a mesh of about 4000 triangles for 1200 steps which took the better part of a day to run due to some instabilities in a wake that was being generated. Look on the web for SLFEA...this might help for code ???

##### Share on other sites
NickB I''m not a coder, I just thought of some interesting feature I would like to use in a virtual world. This seems to be the approriate place since here some people know how the engines actually work, or have a simply a view on what is possble (yet) and what not.

Your explanation is quite complex to me. Do you build up the heightmap approach with those finite state theory? SLFEA, what is it exactly, kind find anything back? What do you mean by ''this kind of problem'', in the beginning of your post? The shaping feature probably, but what would your approach be and what can you realize, easily explained?

Indeed a sort of stream tube would be interesting.

##### Share on other sites
Heightmaps would have to be layered in order to achieve things like bridges and such. Tricky, but doable, at least for static environments.
I suggest instead that you have a look at www.melax.com/vox/
It describes a technique that may suit your requirements, and has a working demo too.

[edited by - plasmadog on March 24, 2002 7:41:37 PM]

##### Share on other sites
Plasmadog, thank you very much for the link, it''s fantastic!

There''s a lot of potential with this voxel&vertex combination technic. So how come there isn''it any commercial application available yet wherein you can transform, shape the 3d environment interactively?

So, has anybody here on the platform thought about such an application before?

##### Share on other sites
that melax-page won''t work for me.

##### Share on other sites
Doing my impression of a Slashdot karma whore, here''s the Google cache of the paper there:
The paper

##### Share on other sites
I have a completely different idea for handling the physics side - two, actually. The first is very complicated. The second is absurdly simple.

This first idea is for the "cloud-sculpting" game.

Have a large number of particles, which have cohesion and separation behaviors (like flocking, except they aren''t continuously moving), and are affected by viscous drag. These particles exist only for simulation purposees, and are not rendered.

Now each one of these particles contributes to an influence field, according to some function (perhaps inverse square?).

Imagine that all values below a certain threshold value are "empty" and that all above are "solid." Create a polygonal representation of this field using the marching cubes algorithm.

When the player "sucks," he basically creates a gravitational force (which acts only within a conical region) that attracts these particles. When he "spits," he expels those particles, with random velocities (a la Quake shotgun).

This probably sounds rather ambitious, and it is. But it''s no less ambitious than any of the other cloudscape ideas mentioned here!

For an easier-to-deal with environment, go with the original snowscape idea. Here''s a really simple way to deal with that: Use a heightmap. "Sucking" subtracts from the height values in front of the player; "spitting" adds. Render it as a simple grid of triangles with some depth fog and bam, you''re done. Want to add snowfall to keep things interesting? Make it random. You''ve seen plasma effects before; imagine a behind-the-scenes "plasma effect" controlling a "snowfall density map" that controls how much snow is added to each section of the heightmap in a given amount of time.

##### Share on other sites
I just read the paper Alimonster provided; it seems my idea and melax''s have a lot in common!

##### Share on other sites
About those layered (3d) heightmaps for bridges and such....
There''s an easy way to do that: break the playing field up into tiles. When someone creates something that requires a 3d map instead of the standard 2d map, simply break that part of the landscape off as a new 3d tile. That way you only do 3d calculations where you need to; most of the landscape would only need 2d maps. Anyway, this tiling would be dynamic, so a new, "clean" playing field is one, big 2d tile. When somebody makes a bridge in the middle of the field, it gets split (necessarily) into 9 tiles: 8 2d tiles around the bridge, and the 3d tile the bridge itself is on.

Also, when you think about it, aren''t all games going to use voxels eventually?
[philosophy]
And when you think about it, isn''t everything made of voxels? Photons, neutrons, protons, electrons: all are tiny particles, effictively points in space, with a 3-dimensional area of electromagnetic influence. And of course, those voxels are made of smaller voxels: quarks, which may be made of smaller voxels....what if everything in the universe can be described by recursive algorithms?[/philosophy]

##### Share on other sites

Terranfury, nice to see how you come up with something as similar as melax's solution. Did you see the demo? Should check it out, it's impressive! ( http://www.melax.com/vox/index.html )

About the heightmap approach, I can't visualize myself seeing how this technique would work in 3d? I do see how it would work when it is only possible to leverage or deepen the landscape. (You just change the heightmap values on the point you are spitting or sucking) But I can't see how the heightmap principle would work when creating interactively horizontal wholes or bridges?

With the melax technique, or what Terranfury explained, you actually have a sort of 3d heightmap. In that you only render a polygonal surface. But this surface is way more flexible and allows horizontal shapes compared to the traditional 2d heightmap approach.

ooprogrammer, how exactly would such a 3d tile work? I can't see that yet. Is it possible to manipulate in-game those shapes with this 3d tile approach?

So until now it seems that we've got3 different solutions presented here to the problem stated, creating a interactively deformable dynamic 3d environment:

- create real 3d voxel grid and render the voxels (good describtion by Yann L., 3th post)
- use heightmaps (first description by Jindocai, 4th post and further explained by plasmadog, yann l., terranfury, ooprogrammer)
- create voxel grid (not rendered), create polygonal surface, form described by voxel information, render polygonal surface.

The first approach would be the best solution to the snow landscape (with the gravity propertiestfor each voxel) though is a very process intensive solution. (jRaskelle, 5th post)

The second 'heightmap' solution is less process intensive but does not allow horizontal interactively deformation. (which is a very restricting thing) (Plasmadog, Yann L., dynamic, not static, deformable terrain with horizontal shaping, is it possible with heightmap approach?)

The third solution with the non-rendered voxel system and the rendered polygonal surface seems to be the best solution to the cloud landscape. This approach would be difficult with the snowlandscape since you need to take gravity into account when people construct all kind of things. How are you going to determine whether something has to fall down now since it's to heavy and not supported enough? A real voxel rendered system would be more appropriate when dealing with a snowlandscape. But for the cloudlandscape this approach seems to be the best one.

So when we want to create a visual attractive cloudy landscape with the round forms and no edges! using this 3th approach, how will we do it? Is it possible to have such a round shapes out of this rough edgy forms? (see pictures at: http://www.google.co.uk/search?q=cache:lxG4nEHBvQgC:www.melax.com/vox/vox.html+&hl=en )

We could highten the density of the voxel grid but this would probably ask to much computing. So maybe with some intelligent texturing effect?

[edited by - Mandarijn on March 29, 2002 7:28:05 AM]

[edited by - Mandarijn on March 29, 2002 7:59:09 AM]

##### Share on other sites
[phylosophy] Ooprogrammer, Interesting remark you make there.

Isn't the future of computer programs & virtual worlds in voxels and particles since real life is build up by little particles too?

So if you want to simulate real life you'll have to build virtual life like real life too...

I don't know, maybe the construction of movies are a better analogy for the construction of virtual worlds than the construction of Real Life. The objective of a movie is to make believe. Behind the scenes we discover that it is all fake but in front of the screen we do not and the effect of immersion works.

At the other hand, cinema of real life events are more intense than acted stuff and people seem to value movies and series more if it's real (hence the reality-tv and 'really happened' story's).

Though as a creator of virtual settings or as a creator of a movie you are interested in the effect and if the effect is better with a more non-real-life simulation like polygons instead of voxels, that solution will win. So voxels won't win over polygons because they are closer to real life structure but because they provide closer to real life simulation.

But maybe it's always like that, that when it is closer to real life structure it will probably be a better simulation of real life. So where's my point? -> That you're right about our voxel/particle future, so it seems. [/phylosophy]

About the recursive algorithm, what is the connection between that and voxels? Don't get that.

[edited by - Mandarijn on April 30, 2002 10:24:30 AM]

##### Share on other sites
I just fooled around with that voxel demo, and I''ll say that it was pretty impressive!!!

It makes for a fun game. The triumph of tunneling back to meet a previous tunnel is undescribable! (Or, maybe I just haven''t been out enough lately)
Now I''m departing a bit from the original topic to talk about deformable geometry in general.

As much as I like the voxel technique (and as applicable as it is to this thread) I''m afraid it really couldn''t be used in most game worlds.

Quake III maps, for instance, are volumetric. After compilation, they are simply a whole lot of polygons, but before they are compiled, they are a set of convex polyhedra. Thus, they are represented not be surfaces but by volumes. Now I thought of rasterizing a Quake III map three-dimensionally as a voxel field and using this algorithm to render it. One would have to ignore details like models, but I''m sure that wouldn''t be a problem.

I''ll admit right now that I really haven''t done much of any research into the marching cubes algorithm. However, AFAIK, a key limitation with it is that it creates a mesh of relatively uniform subdivision. A Quake III map, however, is far from uniformly subdivided. The marching subes algorithm would create too many faces on a flat floor and too few around a detailed object - perhaps missing the object entirely.

An alternative approach, as melax points out, is fast CSG using BSP trees. His concern with the technique, however, is very valid - over time, this results in absurd polygon counts.

Thus, what we need is some sort of system that either A - limits the polygon counts generated by CSG, or B - Adaptively tesselates a voxel surface.

Any thoughts?

##### Share on other sites
I don''t see any reason why Melax''s system can''t have a few clever optimisation techniques applied to it to cut down the number of faces generated. It shouldn''t be too difficult to detect when several adjacent cubes are all going to produce a flat floor for example, and replace all those faces with a few large polygons.

##### Share on other sites
I still prefer the pure voxel approach, where each pixel is an object. But consider...

If you had a conventional tiled heightmap of 64x64 tiles, each 64x64 pixels in measurement, you''d end up with 64 tiles x 64 pixels = 4096 pixels across x 4096 pixels down = 16 Mb of pixels, 1 deep. How deep is enough? 512 pixels would give a depth of 8 tiles, which should be good. 16 Mb of pixels, 512 deep yields 8 Gigabytes of data, one byte per pixel! If we compressed 8 pixels into a simple on/off state (1 bit) then we''d only use 16 Mb of data (4096/8 * 4096/8 * 512/8). That might work.

Let''s assume we''ll need more than 1 bit per voxel and bump it back up to 8 bits per. Now, since 8 Gb is too much let''s shrink the map size or change the resolution. Assuming 1 tile is about 5 ft square, then our 64x64 map was only 320 ft x 320 ft x 40 ft deep. If we change the resolution such that we''re only modeling every 4th pixel (16x16 pixels per tile), then we''ll only need 64x16 by 64x16 by 8x16 voxels. This comes out to 128 Mb. Still a bit hefty.

Ok, how about 8 voxels per tile (each voxel then would be a 8 inch cube, or about the size of a gallon sized snowball )? 16 Mb! Perfect. We could even do a 128x128 map (640 ft x 640 ft) with only 64 Mb. Plus, 8x8 pixel voxels are about the size of a good sized building block. Perfect for our walls and forts and tunnels.

Then there''s how do we render? First I would want 6 DOF, so forget conventional voxel rendering techniques. We''ll simply render as points of size X. We could have some kind of detail map which would determine the color of the voxels. Say for our 64x64 tile map we could have a 512x512 texture used for color. Whatever the pixel is at a given point would represent the color of all the voxels in a vertical column at that point. Heck, make just one more 512x512 texture and have it apply to the horizontal rows and mix the two colors at each point. This would produce cool strata when you began to dig.

You wouldn''t need to draw the vast majority of voxels under the topmost layer that forms the "ground", but how do you know which ones these are? Could we bit flag each voxel that''s on the "surface", then only draw those with the surface bit turned on.

Could we trace rays? Then we just draw the first voxel we hit and stop for that ray.

How about only drawing the voxels within a certain radius around the player? Have to keep some kind of smart list of voxels that way. Quad trees?

Care,
Chris Rasmus

Florida, USA
RTS Engine in Development
http://www.knology.net/~heaven
Jesus is LORD!