#130819 - Mifheu - Fri Jun 08, 2007 1:55 pm
Hi there. I've just another question about how many polys/vertices can be drawn by the DS:
So, I've created al level for a strategy RPG. The stage has around 10000 to 15000 polys and is very big. It's not like a level in Final Fantasy Tactics where the level is only around one screen in size. It's more like in Fire Emblem, where a stage can be several screens in size. Mine is about 6x6 screens. But as the camera is fixed above the level in a quite near distance, there will be only around 500 or 600 polys seen on screen and the player can scroll around with the stylus.
My question is, if anybody has tried to do such a big level and if the data for such a big level can be handled by the DS in a was, that works for a game. I know a little bit about the displaylists, but as I'am no programer, I do not know, if there is a easy way to "stream" the leveldata to a displaylist, when the player scrolls through the level and if this could be done fast enough. One solution would be to cut the level in smaller chunks and load them, when the player scrolls near them. But of course it would be easier for the leveldesigners to only create the entire level without the restrictions that may come with these chunks.
So, has anybody tried to do a rather complex 3D-Level, which gets "streamed" when the player scrolls around?
I would be happy if anybody could help me with some hints, because a the design of the game depends on the bigger size of the stages. Feel free to PM me or whatever. Thanx.
_________________
Simplicity is the most complex topic.
#130829 - NeX - Fri Jun 08, 2007 4:18 pm
Split it up in whatever you are using, and optimize it as much as possible. IRRC, the DS has a limit of 6144 vertexes.
_________________
Strummer or Drummer?.
Or maybe you would rather play with sand? Sandscape is for you in that case.
#130832 - Mifheu - Fri Jun 08, 2007 4:27 pm
Yes, that's right, but as far as I understand, the 6144 vertext limit is the maximum number of vertices, that can be drawn AT ONCE on the screen. I think (or at least I hope), that it is possible to have a level that consists of much more vertices. The question is how to "stream" the data to the display, when the player scrolls to another part of the level. That's what I want to know.
_________________
Simplicity is the most complex topic.
#130833 - NeX - Fri Jun 08, 2007 4:46 pm
Yes, it is, but it involves drawing the screen multiple times;
For double vertex count, you would have a limit of 30fps.
For quadruple vertex count, you would have a limit of 15fps.
I can imagine how to stream a 2d level, but not 3d. Maybe a distance check on every polygon in the level? (WILL BE EXCEEDINGLY SLOW)
_________________
Strummer or Drummer?.
Or maybe you would rather play with sand? Sandscape is for you in that case.
#130835 - Kamu - Fri Jun 08, 2007 5:04 pm
How about just rendering a certain radius from the character?
Or perhaps I am an idiot.
#130838 - Lick - Fri Jun 08, 2007 5:15 pm
You mean with Occlusion Culling with the Viewing Frustum and an Octree/Quadtree of the 3D map?
_________________
http://licklick.wordpress.com
#130839 - Kamu - Fri Jun 08, 2007 5:26 pm
| Lick wrote: |
| You mean with Occlusion Culling with the Viewing Frustum and an Octree/Quadtree of the 3D map? |
Did a quick read up of them and it seems like it.
#130841 - Mifheu - Fri Jun 08, 2007 5:43 pm
@ Kamu: Yes, there will be only a small part of the level drawn on screen (only around 600 polys will be in the view, but the level is about 10000 to 15000 polys). But you can scroll around.
@ Lick: As the camera is quite near the level in a isometric view only what is in the view fustrum has to be drawn. Maybe an octree or quadtree would help. But as it is rather 2D (as you can not change the height or the tilt of the camera) I think it could be split up in 2D-Arrays. I'am just wondering, if I can have a big level (with several thousand polygons) in the memory and only draw a small part of it.
@ NeX: No, I do not want to draw more than 2048 polys in one frame (which would lead to a drop in the fps). I want to have a big level in memory and to be able to scroll around. There would be only 500 to 600 poly on display.
I try to add two pics:
http://www.thepong.net/Stage_Far.jpg
This is the entire stage (around 10000 to 15000 polys when it's done).
http://www.thepong.net/Stage_Near.jpg
This is, what the player will see. The camera is very near to the level and only a few polygons will be displayed of the entire level.
All I want to know, if it is possible to have such a big level in the memory of the DS and if I could still scroll around in this big level with a near camea without any problems. Or if there is not enough memory available or if there are technical limitations which will make it impossible to use such a big level in a game.
_________________
Simplicity is the most complex topic.
Last edited by Mifheu on Fri Jun 08, 2007 5:47 pm; edited 1 time in total
#130842 - dannyboy - Fri Jun 08, 2007 5:46 pm
You don't really need to do anything. You can make a level of millions of polygons if you like as long as it fits in memory. When you set things up for drawing using libnds it should only try to draw what's on the screen. If it doesn't work, then what you will have to do is look at the boxtest example.
#130843 - Lick - Fri Jun 08, 2007 5:53 pm
The artwork looks promising! ;)
I would suggest implementing a Quad Tree and render only the quadrants that are visible through the camera.
_________________
http://licklick.wordpress.com
#130844 - Mifheu - Fri Jun 08, 2007 5:53 pm
Ahhhh! Finally! I really started to think my english is to bad to descibe what I need to know. Thanx dannyboy. Is there a rough number, how much memory I can use? I have the feeling that my testlevel really starts to get too big. I'am in the planning stage of this game and I need to know, if the levels can be that detailed. Otherwiese the entire planning of the game will be based on wrong assumptions, which would lead to problems in the production.
(Hey, funny thing btw: my (real) name is danny). :)
@ LicK: Jep, that's the final solution, if anything else fails. BTW, the pics are from a early test, how the stages could be build in a short time. No textures yet. I don't wanna show too much of it, because it's in some sort of preproduction, but here are two early characters (which will not be used in their current form). They are around 1000 Polys (too much) and the textures are too big (256x256). They are for a special fight-screen, not for the normal game. :) Enjoy.
http://www.thepong.net/Pose_Screen.jpg
_________________
Simplicity is the most complex topic.
#130850 - Ant6n - Fri Jun 08, 2007 6:39 pm
Well, memory on the DS is 4 mb. if you want a huge continuous map like yours, you can split up your level into small sectors and display only the ones that are visible. Then you could also take a bunch of sectors and put them in a file each, call it region or so. Then only have a couple of regions sorrounding the player be in memory, and as you move around, you can slowly load the adjacent regions from ROM or flashcard storage.
I think San Andreas might have done something like that.
#130864 - dannyboy - Fri Jun 08, 2007 8:29 pm
There are two issues getting a bit mixed up here. I'm a bit of a hack, but here's my explanation.
Let's start by defining a polygon. Let's assume it is a triangle, so it consists of 3 vertices(corners). Each vertex consists of a position, normal and texture coordinate. Position and normal are defined with an x,y,z coordinate and texture consists of u,v. Let's be wasteful and use 4 byte integers to define the x,y,z,u,v.
A vertex thus has 8 integers, and a triangle will thus have 24 integers, or 96 bytes per polygon. 15,000 polygons will thus take 144,0000 bytes or 1.373 Megabytes out of the 4 Megabytes of VRAM available.
So let's assume you have one 15,000 polygon model for your level. You pass it to your DS to draw. There's two possibilities:
1) The DS only has enough memory to draw 2000 polygons but more than that are on screen. Basically, it won't work.
2) Only 500 polygons are actually on the screen(this is your case). In this case your DS will go through your 15,000 model and draw the 500 that should be visible, the other 14,500 it will skip. Result being it works.
However, there is a problem. You are asking your DS to go through 15,000 polygons and work out which to draw and which to skip. So although it will work, it will be very slow. So what you have to do is break your single model of the level into many parts. Say you make 150 parts of 100 polygons each. You can then check which parts are to try and draw.
So what happens is you do 150 checks yourself in software, for the parts. You end up with say 20 parts that are partly visible. You then check these parts and draw the polygons.
So what you end up with is:
150 software checks for which parts are visible.
20 * 100 = 2000 hardware checks for which polygons are visible.
Total 2150 checks. That compares with 15,000 checks in the case of a single 15,000 polygon model.
As for how much memory to use. That's up to you. You can use the entire 4 Megs for polygons if you want, but that would of course not leave space for anything else. But the thing is, you can load and delete things as you move around the level although that does that up processor time and also depends on the cartridge speed.
#130865 - Rajveer - Fri Jun 08, 2007 8:43 pm
| dannyboy wrote: |
So what you have to do is break your single model of the level into many parts. Say you make 150 parts of 100 polygons each. You can then check which parts are to try and draw.
So what happens is you do 150 checks yourself in software, for the parts. You end up with say 20 parts that are partly visible. You then check these parts and draw the polygons.
|
Why can he not keep his level as a whole model, keeping the list of all of his polygons as it is now, and then create a separate data structure (quadtree) which points to relevant polygons? The quadtree will be built during the load process and will split the relevant level and store a pointer to each relevant polygon for each node, and will work for all level models, so you can have as many polygons as you want. This way level building will be easier as the split will occur automatically during the load process, and will work for any number of polygons.
#130867 - dannyboy - Fri Jun 08, 2007 8:49 pm
What you are describing is just one of the ways to implement what I have said.
But to get more specific. There's many ways to approach this. The simplest way(from a programmers view) is for the artists to make their 3D models. After they have made their models, they can then manually go through the models and detach them into smaller parts. The artists can then give these parts along with a postion for each part to the programmer. The programmer can then implement a simple distance check for each part.
I don't really see why this approach would limit the artists in any way, it would simple ask a bit more of their time. And of course, you can experiment with the size of the chunks. If you start with 10,000 polys for the stage and just break it into 10 parts you get 1,000 polygons for each part. If you have 100 parts you get 100 polygons per part. Detaching even 100 parts wouldn't be that much work in the context of 10,000 polygons having been created.
Alternatively, if you want to leave it to the programmer, they can instead implement a octree or some other form of culling.
#130880 - Ant6n - Fri Jun 08, 2007 11:31 pm
yeah, why shouldn't the artist build structures like BSP trees himself? i mean, he's getting paid for it, better use the time to do something a computer could do in a couple of minutes.
#130882 - Lick - Fri Jun 08, 2007 11:46 pm
dannyboy, 'breaking' the 15000 polygons into smaller groups is EXACTLY what an quadtree is for. And beyond that, there is absolutely no need to even store such a ridiculously detailed resolution in the final build.
My advice: reduce the polycount to one that suits the screens resolution (more detailed will go unnoticed), then let the quadtree handle the rest.
_________________
http://licklick.wordpress.com
#130892 - dannyboy - Sat Jun 09, 2007 1:27 am
| Quote: |
| dannyboy, 'breaking' the 15000 polygons into smaller groups is EXACTLY what an quadtree is for. |
I already said that.
| Quote: |
| And beyond that, there is absolutely no need to even store such a ridiculously detailed resolution in the final build. |
What? He said 15K polys total, with around 500 viewable at a time. That's hardly ridiculous.
| Ant6n wrote: |
| yeah, why shouldn't the artist build structures like BSP trees himself? i mean, he's getting paid for it, better use the time to do something a computer could do in a couple of minutes. |
Yes, because computers can write code for themselves and then execute it.
What you fail to take into account is that coding an octree or other such structure takes time and a programmer that can do the job. Assuming he's got the programmer that can make an octree, if it takes a couple of hours to code the octree and debug it, but only takes 20 minutes for an artist to break up a level into 10 pieces say, then maybe for this particular project that would be better to let the artists handle it. Sure he doesn't have reusable code for future projects, but I'm just giving him some options.
#130895 - Rajveer - Sat Jun 09, 2007 2:17 am
| dannyboy wrote: |
| What you fail to take into account is that coding an octree or other such structure takes time and a programmer that can do the job. Assuming he's got the programmer that can make an octree, if it takes a couple of hours to code the octree and debug it, but only takes 20 minutes for an artist to break up a level into 10 pieces say, then maybe for this particular project that would be better to let the artists handle it. Sure he doesn't have reusable code for future projects, but I'm just giving him some options. |
The problem with your method is that for each and every map, each modification to maps during testing, each new map to be added e.t.c. the artist will have to break up the level into smaller pieces which may accumulate to alot of time and effort in the long run. By programming a tree structure, the process will be programmed once, debugged (if necessary), and that will be the end of it. A tree structure isn't very hard to program, and if the OP has a programmer for the project who can't even program such a structure then this isn't the biggest problem he will have.
Of course, if the OP wants to only have a few maps, say 1-3, then your method will be more beneficial to them, for any more levels I believe it's worth programming a quadtree for future maps and renditions of maps, as it will make including more levels extremely simple, just plug it in and let the DS sort it out during level loading (and it shouldn't take more than a few seconds MAX).
All in all there is no "right" way to do it and the OP should choose whichever method is best suited to them. Dannyboy's suggestion is great if you're only using a few maps as it cuts out alot of programming time. Good luck!
#130900 - Ant6n - Sat Jun 09, 2007 2:45 am
if there are no programming resources to get some quadtree working, a 2d array of sectors as suggested earlier should be pretty simple to implement, and would do the job very nicely for a top down view on landscape kinda game.
#130920 - tepples - Sat Jun 09, 2007 5:37 am
| Rajveer wrote: |
| The problem with your method is that for each and every map, each modification to maps during testing, each new map to be added e.t.c. the artist will have to break up the level into smaller pieces which may accumulate to alot of time and effort in the long run. |
If the "pieces" can have a meaning connected to the semantics, such as a piece called "courtyard", a piece called "mezzanine", etc., then splitting a level might not be so hard for an artist.
| Ant6n wrote: |
| a 2d array of sectors as suggested earlier should be pretty simple to implement, and would do the job very nicely for a top down view on landscape kinda game. |
At least it worked for Animal Crossing: Wild World.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#131112 - Jhiant - Mon Jun 11, 2007 8:50 am
Hi gang. Just joining this discussion and asking some similar questions for my own projects. I am a programmer who has a decent amount of experience with some of this stuff, so hope this is helpful.
I have two major comments. First, dannyboy has missed his calculations slightly and this is good news for us all. He's got the correct mindset though for approaching this kind of problem, so others should emulate him there. Second, regarding occlusion algorithms, the best fit for this problem is likely a simple tile approach as suggested by Ant6n and others (a 2d array of sectors.)
| dannyboy wrote: |
Let's start by defining a polygon. Let's assume it is a triangle, so it consists of 3 vertices(corners). Each vertex consists of a position, normal and texture coordinate. Position and normal are defined with an x,y,z coordinate and texture consists of u,v. Let's be wasteful and use 4 byte integers to define the x,y,z,u,v.
A vertex thus has 8 integers, and a triangle will thus have 24 integers, or 96 bytes per polygon. 15,000 polygons will thus take 144,0000 bytes or 1.373 Megabytes out of the 4 Megabytes of VRAM available. |
Ok, here is the good news. You don't have to replicate vertices three times for each triangle. This is exactly what a tristrip (GL_TRIANGLE_STRIP) is for. There is a little overhead for degenerate triangles, but essentially, the number of triangles and number of vertices is about the same.
So for the wasteful approach suggested, each vertex is 32 bytes: 3 values for position, 2 for uv's, and 3 more for normal. That is 8 values which are each 4 bytes which is 32 bytes. This can be "packed" and lots of tricks can be done here to reduce memory, but that is not necessary because first just make sure you use a tristrip.
So for 15,000 poly's (is that tri's or quads, since many modelling programs put this out as quads) at 32 bytes each, that is only 480,000 bytes. So that fits in memory fine.
For splitting it up, you probably want a 2d array of sectors, or tiles, if you're looking from the top down. In order to get the tristrips to work, these need to be broken up ahead of time. You should do this via a tool if possible. Then it is a simple process of finding a set of tiles that are near your camera position and rendering those based on what is visible.
Because your camera is top down and fixed size, you can probably tune your tile size to be about the size of one screen. Then you can load just a section of 9 tiles (the one the character is in, and the 8 surrounding tiles) and do it this way. This is much simpler than per poly occlusion.
If your world gets much bigger than the initial 15k polys, you may have to come up with a streaming solution, but that is just another level of the tile idea loading from ROM.
Again, it is going to be key that you have those tiles broken up before they are tristripped. It looks to me almost like you are modelling the world with a height map, though, since all the poly's are even. So this looks like it could be straightforward.
Good luck.
_________________
Occam's Razor: All things being equal, the simplest solution tends to be the best one.
#131118 - Mifheu - Mon Jun 11, 2007 9:38 am
Whoa! Just two days off and then there's lots and lots of interesting replies! Thanx alot guys! That's even more than I wanted to know.
I already thought about splitting up my levels to have a 2D array check, what is visible and then render only that stuff. Of course this should be done by a tool (on load) or a plug in (after the level is build). As there are about 30+ stages planned for the game it is not possible to let the artists do that. It would be a pain in the a** when the artists have to rework some parts of the level, and they would need to split the level up again and again. That would take too much time.
_________________
Simplicity is the most complex topic.
#162726 - mreaves - Thu Sep 11, 2008 6:48 am
| dannyboy wrote: |
There are two issues getting a bit mixed up here. I'm a bit of a hack, but here's my explanation.
Let's start by defining a polygon. Let's assume it is a triangle, so it consists of 3 vertices(corners). Each vertex consists of a position, normal and texture coordinate. Position and normal are defined with an x,y,z coordinate and texture consists of u,v. Let's be wasteful and use 4 byte integers to define the x,y,z,u,v.
A vertex thus has 8 integers, and a triangle will thus have 24 integers, or 96 bytes per polygon. 15,000 polygons will thus take 144,0000 bytes or 1.373 Megabytes out of the 4 Megabytes of VRAM available.
So let's assume you have one 15,000 polygon model for your level. You pass it to your DS to draw. There's two possibilities:
1) The DS only has enough memory to draw 2000 polygons but more than that are on screen. Basically, it won't work.
2) Only 500 polygons are actually on the screen(this is your case). In this case your DS will go through your 15,000 model and draw the 500 that should be visible, the other 14,500 it will skip. Result being it works.
However, there is a problem. You are asking your DS to go through 15,000 polygons and work out which to draw and which to skip. So although it will work, it will be very slow. So what you have to do is break your single model of the level into many parts. Say you make 150 parts of 100 polygons each. You can then check which parts are to try and draw.
So what happens is you do 150 checks yourself in software, for the parts. You end up with say 20 parts that are partly visible. You then check these parts and draw the polygons.
So what you end up with is:
150 software checks for which parts are visible.
20 * 100 = 2000 hardware checks for which polygons are visible.
Total 2150 checks. That compares with 15,000 checks in the case of a single 15,000 polygon model.
As for how much memory to use. That's up to you. You can use the entire 4 Megs for polygons if you want, but that would of course not leave space for anything else. But the thing is, you can load and delete things as you move around the level although that does that up processor time and also depends on the cartridge speed. |
I do think your math is a little off there RE level size in K's. You are looking at around 20 bytes per vertex, and only the polys have a normal, not each vertex, so that gets a triangle down to around 72 bytes (66 if the normal is an fx16 type). You then assume that 15,000 triangles equals 45,000 verts. With stripping that should be far, far less. Add in some quads and your level size (for geometry) is nowhere near 1.3meg.
#162731 - tepples - Thu Sep 11, 2008 1:04 pm
In fact, I've seen Quake 1 compress each normal to 1 byte by rounding it to one of about 220 points on the surface of an icosahedron. Look up "anorms.h".
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#162732 - TwentySeven - Thu Sep 11, 2008 1:06 pm
Plus the DS can stream about 4k a frame (240k a sec) off a average sort of flash cart.
So in theory, as long as you don't let the camera move too fast your level sizes could be much much larger then 4mb.
#162735 - sgeos - Thu Sep 11, 2008 3:04 pm
You could pack level size with an object oriented level design, although that would require custom encoding tools, and would not work for every kind of game.
#162741 - Miked0801 - Thu Sep 11, 2008 6:25 pm
Make your tiles slightly larger than 1 screen size and you only need to hold 4. Make them much smaller than screen size and you will save memory, but will load more often. Making the tiles exactly the screen size is probably about as wasteful a size as could be picked. :)
#162782 - Synthetic - Fri Sep 12, 2008 8:36 pm
Could you repost the screenshots? I'm interested in seeing what you have but thepong.net is down =P
#163008 - Mifheu - Thu Sep 18, 2008 2:30 pm
@ synthetic: Ah, now I know, what you meant with your message, about the site being down. Yes, thepong.net is down, but I started another site with some concepts, artworks, gamedesigns and other infos. I also reposted the sceenshots from the strategy RPG I'am doing concepts for. You can find all informations under Projects/Eternal Circle.
Under Stages you'll find the two old screenshots and a new one with the final mesh for the teststage.
I hope I will be able to do some updates, as soon as the project I'am working on in "real life" is finished.
Just visit: www.aemuse.com
_________________
Simplicity is the most complex topic.