Jump to content
  • Advertisement


  • Content count

  • Joined

  • Last visited

Community Reputation

292 Neutral

About NickUdell

  • Rank
  1. NickUdell

    Title Screenshot Rendered

    It looks nice, but I'd definitely recommend using a GUISkin to change those buttons
  2. NickUdell

    Quick Update - Texturing Sucks

    Just a quick update to reassure you all that work is still progressing. Unfortunately I'm working on a lot of things at once right now which means very little in the way of screenshotable material has come out in the last week or two. I'm also working on a massive deadline for my PhD, so I've had less free time than usual. What have I been working on? Octree space representation and working around floating point inaccuracy Brightness-based culling method Combining deferred rendering with procedural textures in a (hopefully) efficient way Parametric Planet Texture Generation. But yeah, none of this is at a displayable stage, but expect a load of in-depth and wonderfully graphic dev journals over the next couple of months.
  3. Non-position based octrees
  4. NickUdell

    Octrees are a dev's best friend

    I've been using an octree system for space partitioning for a long time now, and a couple of the reasons I'm using one are: It can adapt well to any number of items in them It only really falls down as structures get very close together (and I'm dealing with celestial objects - which have a tendency to explode or absorb each other as they get too close) It can be built and rebuilt fairly quickly It's essential for Bayes-Hut Now there's more than one way to skin a cat, apparently, and there's also more than one way to build an octree. Traditionally you build the hierarchy based on position, splitting a node into 8 smaller nodes as the number of items near each other reaches a pre-set threshold. This is how you should have it for Bayes-Hut to work as intended. Alternatively however, (and useful for level of detailing in a space sim), you can build your octree hierarchy based on size, visibility, temperature or any other characterization. Taking size as an example, let's say we want to render far away stars only if they're very large (why waste rendering calls on a star that's barely larger than a couple of pixels?). Normally we LOD to distance, but in this case a very, very large star or a very, very bright star can be seen from quite a distance compared to an asteroid. So we build an octree, with size, brightness, temperature, magnitude, etc as the function for calculating heirarchy. The giant items make up the first level of the tree, with maybe four or five of them in any one galaxy. Then, as the size gets smaller, we put them in finer and finer-grained octree nodes. This lets us operate by octree level, setting different view distances per size. Does this also work with Bayes-Hut? No. Let's take a look at the Newtonian formula for pair-wise gravitational interactions: F = (G*m1*m2 / r^2) Here F is the force, G is the gravitational constant, m1 is the mass of the first body, m2 is the mass of the second body and r^2 is the distance between the two bodies squared. You see, there are two important variables in the gravity calculation: mass and distance, but it's clearly seen that as distance increases, the force is reduced exponentially, so distance is more important in the long term. If you think about it, you'd want a planet that's orbiting a star to directly gravitate against that star instead of with every other planet in the galaxy. It just doesn't make sense otherwise. So how do we cull the bodies that are far away and small, but keep the really big ones? Well we build a formula for it. There's a very complicated formula for what size an object will appear on the screen in pixels, but we don't actually need that and it makes me queasy just thinking about it. Astrophysics has our back. The visibility of a celestial object is described using its apparent magnitude.
  5. NickUdell

    Size does matter - and precision too.

    Not really, the problem of precision still remains. If I store an item's position as being 1000.023 kilometres away as opposed to 1000023 metres away I still come up against the precision cap of floats. In this case 1000.0235 will be rounded to 1000.024 just like 1000023.5 would be rounded to 1000024, meaning the same loss of precision (+-0.5m), no matter what units you use.
  6. Floating point precision
  7. NickUdell

    Size does matter - and precision too.

    With Pigment, I hope to (for the computers that can handle it) offer an entire galaxy to explore. Most of the area will go unexplored, as the vast distance between stars alone is enough to make the heart jump, but I want the far away stars and black holes to still have their effect felt in across the galaxy. This brings a problem of precision. According to Wolfram Alpha, the rough width of our galaxy is approximately 9.5x10^20 meters. This is quite a lot, as you can imagine. Luckily, a double-precision floating point is more than capable of storing that number. What it cannot do, unfortunately, is store many numbers around that number. The double precision floating point format has an 11 bit exponent and a 53-bit significand. The significand is essentially the number of bits of precision any number can use. This is approximately 15 decimal places. Any number that requires more than 15 significant digits will suffer from rounding errors. At the edge of the galaxy you would need a 70 bit significand (log2(9.5*10^20) = ~69.68) to represent a position at 1 meter accuracy. Ideally I would like centimeter accuracy to better deal with movement that takes place close to the camera and for that kind of accuracy I would need a 79 bit significand. With a double, the position would be rounded to the nearest 130,000 meters. That might be ok for large celestial bodies like the sun, but a 300x200 meter ship will have some considerable problems moving about. So what can we do? There are a couple of options: [font=arial,helvetica,sans-serif]Use a Quad[/font] A Quadruple precision floating point value is simply a turbo-charged double. It has a significand of 113 bits, which will give us a precision of around 114 femtometres at the edge of the universe. This seems like a bit of an overkill really. Each position value will take up 48 bytes with a quad. So a galaxy full of stars will be approximately 14.4GB of positions alone. On top of that, I would have to write my own implementation, as to my knowledge C# does not include its own native version, nor does HLSL - so I would have to add additional functions to my shaders for working with the larger data type, and I'm not even sure if it'll even accept a world coordinate that large. Additionally all of my code currently uses the SlimDX Vector3 class for position, as it's a handy tool for vector maths. I'm not adverse to writing my own implementation of those functions, but I'd rather not waste the time when there's a better solution. [font=arial,helvetica,sans-serif]Use a combination of Single and Double precision.[/font] This is very similar to the Quad method, except instead of using a combination of 64bit and 32bit floating point values to give us a significand of 53 + 23 = 76 bits. An accuracy of 1.5cm at the edge of the galaxy. With this representation, a galaxy full of stars will have cut down to 10.8GB, which is not something to sneeze at, but I'll have to handle the math related to the compound values and I'm wasting the exponent bits in my single precision item. Use Integers An odd decision for a system which wants decimal accuracy, but if I've decided the minimum acceptable positional change is 1cm then that can be represented as my minimum integral unit. I'd need an 80-bit integer (represented by a combination of a 64 bit integer and a 16-bit integer), which is still an ugly datatype, but it's precise and the accuracy is guaranteed to not change. Unfortunately I'd have to physically stop the player from exiting this range, and I thought we were passed the days of invisible barriers. I would need to pad data sent to the GPU to 128bits, but with this datatype the math will be slightly faster, and the overall size of a universe of stars would be 9GB. Shorten the maximum galaxy size A double precision floating point will support a 1cm resolution up to a distance of 9x10^13, or approximately 1/10,000,000th of our galaxy. Our galaxy has approximately 300,000,000 stars. 30 stars would fit in this restricted size, which isn't much for a space exploration game. So what about integers? Using the same number of bits, an integer can represent 1.8x10^16 meters. This gives us 1/10,000th of a galaxy, and roughly 30,000 stars. This is much better for space exploration, and we can be fairly sure that a galaxy any larger has a very low chance of being explored. 30,000 stars with 64-bit integer positions would take up 720kb of memory. But then there's still the problem of invisible barriers. It's very feasible that the player might hit 1.8x10^16 meters, which is only 1.9 lightyears, particularly since they'll start in the center. Offset from the player's location If the precision of a floating point number reduces as the number increases, why not make that number the distance from the player? As the object is further and further from the player, its accuracy becomes less important, leaving an area of extremely high accuracy centred around the player, with lower accuracy reserved for the larger objects still being rendered, which are so far away that a 130km jump in position looks negligeable. With this system you'd only really need the precision of a float, which would work wonderfully as I'm already using them. Fortunately the maximum size of a single-precision float is 3.4x10^38, due to the size of its exponent, which gives us plenty of room to play with. The accuracy at the edge of the galaxy (4.25x10^20) from the origin is 42,500,000,000,000m. This is a huge number, but remember we won't be rendering objects that far from the player, that's the maximum distance an item can be (roughly) from the player. Realistically, the most stars we would probably want to be rendering near the player would be ~2 (I intend to turn distant but bright celestial objects into a dynamically textured skybox). The 2nd closest star to the sun is Sirius, which is 8x10^16 metres away. At this distance, the accuracy will be ~800,000,000m, which is less than its radius (and at that distance I doubt that length would be much larger than one or two pixels). The biggest downside from this system comes from the fact that you would periodically need to recalculate every celestial body's position from the player's by summing the difference between the player's current position and the position the player was at the last time the positions were recalculated, but that would only really need doing once a minute or so, depending on player speed. That's not too bad really, compared to 15GB galaxies or invisible walls or low-precision close to the player. I haven't yet implemented it though, so it's still all pending. I want to re-evaluate how I use octrees so that instead of a spatial measure, they use the visibility of the celestial object to organise the objects (so using various "tiers" depending on visibility, allowing only a certain number of items in certain tiers), and this would be the perfect time to implement that.
  8. NickUdell

    A Description Engine

    Hi, thanks for your input! I've actually been working on a synonym class for this, but I think you're on to something with extending it to cover phrasing too. I like the idea of randomly altering the way the data is delivered too. It'd be a blow to extensibility, but if I made a generic enough version of the algorithm it should solve most of those problems. Have you ever seen Dwarf Fortress' descriptions? Impressive stuff, but even they feel a little bit contrived after a while. An example description: [img]http://manvshorse.files.wordpress.com/2008/06/dwarf-fortress-2.jpg[/img]
  9. NickUdell

    A Description Engine

    Ok, so it's not the octree-based gravitation I promised you, but I came up with a very last-minute massive overhaul idea for aesthetics which has slightly broken the octree code. No biggie, but it's gonna take a bit longer to fix. On the plus side I am very excited indeed for the new look of the thing, which I'll show you at a later date. So this time I'm going to talk to you about descriptions. Each one of my celestial bodies is based on a class which extends from a class, which in turn extends from more classes. In fact, if you want a look at the class tree at the moment for in-game objects, it's something like this: So, as we can see, that's a lot of inheritence. I know you can't read the names properly here because it's so small, but the bottom-right block is where the stars, black holes and planets are. They inherit from things like mineable, dynamic, moving, massive, etc abstract classes. All designed to very easily encapsulate their own little pieces of functionality which has made crafting this game a hell of a lot easier. An important part of Pigment will be exploration. I want it to be more meaningful than just zipping about, seeing what we can see. To start with I want to reward the player for finding new areas and I want the player to have to actively compete with other characters to be labelled the discoverer of that object (and be given the honour of naming it, of course). As such these things had better be a little more unique than "brown star", "dwarf planet", "moon". I need them to feel like they're individual, beautiful entities, born from the swirling fires of the galactic core and battered by the chaos around them. I took a big leaf from Dwarf Fortress here, which is probably the best case of procedurally generating attributes and descriptions there has ever been. So how do I do it? Well, from every class, even right at the top, there is an overidden function Describe() which returns a string. The string it returns constitutes the current state of the description. So right at the top it will return "This object is a blue, supermassive star." and towards the end you might be getting a bit more detail. Each implementation of the function returns the parent class' string result combined with their own descriptive contribution in order to call the Describe() function on every class that is relevant. So what does the code look like? Well here's the implementation for the Discoverable abstract class: public virtual string Describe() { if (Discovered) { return "It was discovered by " + Discoverer.Name + " in " + DiscoveryDate + base.Describe(); } return "It has not yet been discovered." + base.Describe(); } So here are a couple of descriptions that have been generated so far This star has no name. It is unstable, with a temperature of 3574600C. It will likely collapse in 8000 million years. It can best be described as Yellow in colour. It is approximately 128 billion years old and it has a radius of 191AU. It has not yet been discovered. This star has no name. It is unstable, with a temperature of 143400C. It will likely collapse in 1000 million years. It can best be described as Blue in colour. It is approximately 90 billion years old and it has a radius of 309AU. It has not yet been discovered. This star has no name. It is unstable, with a temperature of 123130C. It will likely collapse in 1000 years. It can best be described as Dark Red in colour. It is approximately 100 billion years old and it has a radius of 252AU. It has not yet been discovered. These are mostly randomized data in there, a lot of it just doesn't have the proper code to calculate things like size and colour so they're randomized, but later on this will give some highly scientific readings, and I hope to include orbit information and major events too. In the future I hope to hook this description system up to some sort of text-to-speech engine and actually have the ship's computer read out data about it as you fly along. Space games always break with immersion as soon as you have to bring up a menu while you're flying along, because when that happens you're powerless to control your ship, so I want to have minimal reading and menu clicking where-ever possible.
  10. New aesthetics ideas and the Goons show
  11. NickUdell

    So I created a universe with 10,000,000 stars today...

    That's a very good point on both issues. I've been working on calculating the correct luminance of a star / body based on its size and temperature recently, so until now I've only really had position as a framework for it. I think the issue here isn't going to be brightness though - as I intend to swap stars with billboards and eventually a single backdrop as they physically start to take up fewer pixels on screen. This then becomes more of a relation of how big the object is combined with how far away it is, as opposed to how much it flares up (which is actually done post-process, so even a single pixel on a backdrop can flare massively). I'm still working on this, so I might write a journal entry on it at some point when I believe I've found a satisfactory answer. I hope to allow the player to actually fly at some impressively high speeds. Not only will I allow them to approach light-speed, I will also be implementing a slightly exaggerated time dilation feature so that as they speed up, the passage of time speeds up too. I'm aware that's not strictly speaking how time dilation works, but it should serve to simulate it fairly well, and be a boon to interstellar travellers. As for positions, I think a relative position would work best. I already have the positional gridpoints stored as the centres of my octree nodes, so simply changing position to be an offset from there will save me a hell of a lot of precision, and since I don't move octree nodes (I only recalculate them occasionally), they're free to be fairly low precision. I could probably store their positions in 3 floats. This does, however, impose a limit of using distance as my octree metric.
  12. NickUdell

    So I created a universe with 10,000,000 stars today...

    That's a good idea, the only struggle will be correctly applying gravity to the offloaded chunks so they don't whizz off in weird directions. Although if I apply gravity currently using Bayes-Hut, then I can reverse the process and apply gravity to an entire OctreeNode and then when I load chunks from inside that node, I apply the total gravity to it. It won't be exact, but it should be fairly close, and will drastically increase the potential universe size. Now all I need to do is work out some way to make a skybox out of the major celestial bodies from the off-loaded chunks. And make it quickly too... EDIT: The more I think about this, the more I think it might be perfect for Pigment. I previously wrote a simple Managed DirectX Minecraft clone (just infinite procedural block terrain using 3D perlin noise - nothing too special) that offloaded and reloaded chunks, so a lot of that code can be borrowed.
  13. NickUdell

    And a video

    Your problem with no galaxies or stable orbits forming might have been due to a lack of rotation? I'm not sure my engine will be able to handle adding in some of the more complicated physics associated with rotations and the like. Another reason could be because newtonian gravitation doesn't really work well in the long term, which is why the use of spacetime curves to simulate gravity are considered the gold standard. Unfortunately, spacetime is a little harder to simulate when you have to deliver it at a constant time. I haven't gotten around to particle effects yet. I have a place for them in the framework and will eventually use them, but currently they're an unwritten placeholder.
  14. Surprisingly it actually kept running interactively without stuttering for about five minutes before crashing. According to google our galaxy contains about 300,000,000,000 stars which is only 30,000 times more than what I've got! Not bad, if I do say so myself. Of course, really this is a limit on objects in general, as my universe won't just be made of stars. There'll be planets, asteroids, rings, nebulae, supernovae, etc. Looking at the stats it took up approximately 12 gigabytes of RAM. I can probably optimize that later a little bit. Not to mention the fact that probably only 1/100,000 of that was on screen at any one time (draw distance was set to about 10,000km), so some sort of off-loading to disk would be best too. Maybe I'll work on that next, I've never done compression before - could be interesting. Anybody out there know any good articles on compression techniques? Might publish a proper journal entry tomorrow about the gravitation system and the octree, if I have time. I'm also meant to be going to a ball with my girlfriend.
  15. NickUdell

    And a video

    Yeah the collisions are still happening in this (well, what's currently happening is the bodies are entering each other and then, when their centres are essentially 0 from each other the gravity pulls them at a ridiculous speed so they fling off in mad directions). I have collision testing on all objects already written, but there's a bug or two still in the way I deal with the collisions currently. The joy of this is that it actually scales really well. Because of the incredibly slow motion in general I can get away with running this update maybe once every 30 seconds or so. If I've given it its own thread, then that gives me up to 30 seconds to process all of the objects. Combine that with the octree implementation and I could theoretically have millions of stars in here (and I hope to, once I've sorted out LODing and efficient octree-based frustum culling) EDIT: The other thing to bear in mind is that every now and then you'll have to rebuild the entire octree from scratch. This is because as each item in the tree moves, the culling / calculations become less and less accurate (essentially the chance of an item moving into the space "owned" by another octree node increases the more they move). But if you only have to update their positions / gravity every 30 seconds you probably won't need to update the tree anything less than every half hour or so. And updating the tree is actually a really quick operation, amazingly. I've added 100,000 items to the tree and it's taken less than a second on my hardware (I've never gotten around to actually timing it because it's been so fast so far, and from the start I've separated the universe updates from the rendering loop). When it comes to optimizing later, I'll look into it a bit more, but right now it's really not crucial.
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!