|
Author Topic:   ROAM for use in MMORPG?
Prophylon
Member
posted June 06, 2000 03:10 AM            
Currently I am working on implenting an ROAM algoritm into my engine. I have just read the article on gamasutra by Brian T and tried to implement some of his code into my own. Just that you know, the article was great and very helpful Anyway, while implenting the code and testing it every now and then I noticed that the terrain deforms rather much... Now ofcourse as the name ROAM implies, this is the entire goal of the algo but then the landscape you see is merely an approx to the real heightmap. This is all fine and nice for single player games, but what if you have a lot of people playing it? Then you could see players who are far away actually standing higher then the ground, simply because the triangle they stand on has not been split... Does anyone have any thoughts on this?

Then there is this other thing. I believe I checked the code about 10 times during the same day but I could not find what is causing the following problem... The landscape is displayed fine, patches are clipped fine, tri meshes split but they split down to the last node it seems. So I have two or three entire patches split down and the rest is not split at all. This is causing an fps of about 9 I double checked every function (tessalate, render and reset plus all their patch and recurs counterparts) and they are all exactly the same... Anyone got an idea where I should look?

Well thanks again for writing the article, I am comparing it to other algo's today and see what you guys have to say on this

Greetings,

Joris "Prophylon" Jansen

IP:

Effin Goose
Member
posted June 06, 2000 03:57 AM            
About the multi-player bit.. What you can do is simply tesselate area's where objects are, to a higher degree than if they werent there.. I believe this is what Treadmarks does with its mulitplayer, simple tesselates to a higher degree where enemy tanks are, but dont quote me on that..

Hope that helped..

Ryan

------------------
I dont like it, and Im sorry I ever had anything to do with it
- Schrodinger

[This message has been edited by Effin Goose (edited June 06, 2000).]

IP:

Prophylon
Member
posted June 06, 2000 04:07 AM            
Do you mean I should tessalate down where other players are and render the terrain there with full detail? I thought about that, but I think it would be way to slow if there are much players or monsters on the screen at the same time... Only tessalating down and then getting the height would still not solve the problem because the monster or player might appear lower/higher then your client -renders- it...

Or am I seeing this all wrong?

Thanks for the reply btw

[on the problem]
Well it can only be this check, which for some reason is always true (as it splits down as far as he can till he is out of Tris):

if ( (fNode >= (1<<VARIANCE_DEPTH)) | | (tTriVariance > gFrameVariance))

VARIANCE_DEPTH is a #define with the value of 9. gFrameVariance does increase every renderpass because it renders the entire bin (25000 triangles). So I guess either tTriVariance is -really- high or I have some nasty bug somewhere else :-(

[This message has been edited by Prophylon (edited June 06, 2000).]

IP:

Prophylon
Member
posted June 06, 2000 09:20 AM            
It seems I have solved the problem. It was gFrameVariance. Although the variable is nicely set to 50 at the beginning, something went wrong. If I would return the gFrameVariance value every loop, it would begin at 50 and rise. This should be correct, however as soon as I replaced gFrameVariance with a normal number, the problem was solved and the algo worked perfectly... I have totally NO idea what is causing this, because when I return gFrameVariance to be printed, it prints out fine...

Then something else, what is exactly the point of (fNode >= (1 << VARIANCE_DEPTH) in the recursive tesselate function of the patch... As far as I understand (reading the comments) it splits nodes deeper then 9, because they are already split. So this would mean the area around you will be in greater detail? With the texture on I noticed little difference when I commented the line out but the speed increase was big... Is it 'just' for quality?

Thanks and greetings,

Joris "Prophylon" Jansen

IP:

Bryan T
Member
posted June 06, 2000 02:05 PM            
Prophylon,

The gFrameVariance is supposed to find the right balance of triangles over a few frames. I didn't have time to optimize this feature before the article. Not sure why you're running into the problem, it was pretty stable, though not perfect by any means.

The question of what that check is doing. Basically, the Variance Tree only goes to a certain depth, after that point what should occur?

If you choose to split the nodes past the depth of the Variance Tree (which I do), then this check forces the splitting to continue all the way to the finest possible resolution.

So the check is saying:
If the current node is below the resolution of the Variance Tree, continue splitting.
OR if the current node's variance is too high, split it.

Glad the article could help. For the MMORPG thing, Effin's idea is the way to go. Just tesselate the area around monsters or other persons. Even with 100 users onscreen, you're still saving an order of magnitude over the full number of triangles for the landscape.

--Bryan

IP:

Prophylon
Member
posted June 06, 2000 02:26 PM            
Thanks for your reply Bryan.

Well your gFrameVariance global -should- work. I have nicely declared it and its value is within limits. However it simply does not work... I have set is manually now as a temp solution.

Anyway, about the MMORPG. What you are saying is that for every object in the game I should tesselate as far down as possible... Well I think this is an accaptable solution, however since the deformation of the landscape is so sudden and so strong it would be easy to see a moving object coming from a large distance simply by watching the terrain... Although I know you touched the topic of GeoMorpihg I wonder how effective this really is?
I am beginning to doubt whether the entire ROAM solution is a good one for an MMORPG... (or for the tiny RPG I am beginning with)
Both big MMORPG's out now use static landscapes... If I remember correctly EQ uses some sort of BSP trees and AC uses a quadtree technique I believe (splitting the landscape up in different patches)... However both do not have any form of LOD. It would be a challange to do it otherwise, is it smart to? Wouldnt it be wiser to use a Quad tree because of the detail loss that would occur when rendering a lot of (moving) objects on the screen with ROAM?

Thanks!

IP:

Prophylon
Member
posted June 06, 2000 03:15 PM            
Doh I hate spamming my own thread, but I just wanted to say that I finally found out what caused me all those headaches for 2 days... It seems that for some reason I also had this in my cPatch class:

float gFrameVariance;

Being the exact name of the global that is ensuring the program works properly. Needless to say this value is never initialized and is therefore causing all the probs. Anyway, tis solved now. Thanks for reading the problem. Over to the main discussion on MMORPG.

IP:

Bryan T
Member
posted June 07, 2000 11:04 AM            
Prophylon,

Yes, you should tesselate around the objects. Geomorphing would help some, but it really depends on your triangle budget for the landscape. With a high triangle budget, the deformation around an object is much less. Also, with proper textures and other stuff going on, no one would really notice.

Regarding the current landscapes in MMORPGs: They suck, 'nuff said. If you want a nasty, blocky, spikey landscape, then you're welcome to use modeled patches. To achieve a true organic landscape with little bumps and grooves, you need something more powerful (or a lot of time in a modeling program).

EQ and AC are not praised in any review I know for their graphics engine. Some of their effects are pretty cool though.

I agree, the challenges for continuous LOD terrain are many, and it is an important decision for your project. Be sure to take all the pros and cons into account.

TRIBES uses a continuous LOD system that tesselates more around important areas. I've never seen any problems in game with this method, nor read any reviews that mentioned it. So it does work in the real world (Tread Marks uses it too, I believe).

--Bryan

IP:

Cthulhu
Member
posted June 07, 2000 02:32 PM            
Any ideas for an efficient method to split triangles under important objects in ROAM?

Or how to find out which triangle in binary tree covers specified map coordinates?

IP:

Prophylon
Member
posted June 08, 2000 04:26 AM            
Brian,

Thanks for your feedback on the subject, it is much appriciated. The problem is that I have a low triangle budget. If you look at AC or EQ you can see that they use fairly small textures to cover their HUGE triangles in the landscape. Obviously this can be quite fast, however most certainly not that pretty. I think I am going to stick with ROAM for awhile and see how it looks if I implent geomorphing. First I want to optimize the code a bit, the problem is that the Max Speed version as well as the Debug version of my program give almost the same fps. It seems like my poor little TNT is being pushed to da max.

Since I am not a great optimizer, does anyone know good references to optimizing common functions such as distance? I have searched the web but found mostly PIII or AMD specific calls.

Anyway, I have played TM once again and it is pretty hard to see the landscape change imho. I think it would be best to not use large detailed textures for ones landscape or else the popping becomes too clear.

Another interesting thing covered in some earlier threads is that of a -very- large landscape. Because how would one manage the 'heightmap' then? AC with its very low poly ground loads an entire 'sector' once you travel in a buffer zone (meaning if you change back and forward on almost the same spot the zone will not reload and load again). However this would hurt the effect of an endless landscape, since you would have to fill the void that appear by dividing the landscape in different zones. AC uses prerendered bitmaps to create the illusion of continues landscape. I believe EQ just uses BSP trees for its zones and limits the view by fog and terrain.

So I am going to see how geomorphing works and increase the size of the smallest possible triangle to allow me to cover more land with the same poly count.

About the question how to do know what triangles to tesselate, I would say pass some coordinatates to the tesselate function. However the problem is then that they hit the distance algo, which is -really- slow (I watched the function timings). Maybe one would like to change that with some far less accurate approximation so that the number of objects under which one should tesselate deeper doesnt make the engine crawl.

Anyway it is a challange and you are completely right when you say that it is possible in the real world. Too bad I do not have Tribes. As you might have noticed the quality of my English is not that high (my sincere apologies) as I am from Holland

[New]
Ow yes one other detail, I think I am going to mix the ROAM with an Octree (structures in the landscape) to get some more speed esp when the entities cover the lands lateron. Does anyone have some thoughts on this? I think that in a larger landscape it would be very well possible to have fast checks which patches are invis and which are not... And then there is collision detection. The current way of keeping the player on land is not that good (although the heightmap is high detail) so I must do some collision dectection. Traverse down the tree and point collision with the lowest end of the tree? Because box testing would be hard unless you have bigger triangles (which I think I am going to do)...
[/New]

Thanks!

Joris "Prophylon" Jansen

[This message has been edited by Prophylon (edited June 08, 2000).]

IP:

Bryan T
Member
posted June 08, 2000 10:48 AM            
Prophylon,

The distance metric I used in the article is for reference. Many games use the L1-norm. This is calculated as such:

distance = MAX( abs(x1-x2), abs(y1-y2), abs(z1-z2) );

x1,y1,z1 being the viewpoint coordinates
x2,y2,z2 being the node's coordinates

This gives distances that are longer along the diagonal, rather than circular. But it eliminates three multiplies and a square root. For games, this slight skewing is rarely noticed during play. (at least for continuous LOD terrain rendering)

The biggest optimizations to the code would be a fan-buffer and split-merge queues. The fan buffer reduces the total number of vertexes bieng sent to the card (thus more triangles per frame), the split-merge queues reduce the algorithm running time.

--Bryan

IP:

Prophylon
Member
posted June 08, 2000 02:24 PM            
Well I am using a fast sqrt function from graphic gems III now. It works pretty good although it is very difficult to notice any difference. I think my poor TNT is choking on all the different vertexes that get sent in. After I fix the GeoMorphing thing I will start with the fanning thing. Oh yes there is something else, how would one create water in a landscape using ROAM? As far as I can see it now it would involve some nasty (and much) calculations in order to remove the 'jigsaw' effect from just rendering a large quad.

Thanks again!

Joris.

Ow btw Bryan, you mentioned something about not storing your landscape in a heightmap but rather calculate each point with a noise function... Do you have any control on it then? Like roads and such will be hard, no?

IP:

Bryan T
Member
posted June 08, 2000 05:20 PM            
Prophylon,

Water is generally done by rendering a flat plane that is clipped by the surrounding landscape. Tread Marks does this, and it looks great. Don't use one quad, make it many smaller triangles (say 64x64 patches made up of two triangles, or even 32x32).

The videocard will take care of per-pixel depth calculations to keep the correct polygon displayed when the landscape intersects with the water.

What is the jigsaw effect you are referring to? (or did I answer that with the above discussion?)

Not using a heightmap is getting into the advanced territory.. combining fractal generation of a landscape with artist-generated height fields, etc. This was discussed in another thread last month, do a search for fractal, it should find that thread.

--Bryan

IP:

Prophylon
Member
posted June 09, 2000 04:35 AM            
Sorry about that, I remember reading the thread but I just did not think of it. I think I am doing a bit too much in too little time at the moment so I think I will just focus at one thing at the time. My primary concern was that if I finally had the landscape engine up to a nice level that I would find out that it is not a good solution afterall...
The JigSaw effect caused by not thinking and not reading the good posts

Thanks again!

Joris.

IP:

Oiler
Member
posted June 12, 2000 12:19 PM            
I believe the "jigsawing" is known as Z-fighting and can be removed by using a DECAL in OpenGL. DECALs take care of Z-fighting that occurs when rendering co-planar geometry.

IP:

Prophylon
Member
posted June 12, 2000 03:21 PM            
Ah thanks Oiler I shall look into that... However I first want to get this GeoMorphing running and the menu system working in a decent manner.

Btw does anyone know if there is an easy way to -read- something (a string?) from a file and then execute an function with the same name? Or do I have to use pointers for this? (to either functions or classmembers)

Thanks!

Joris.

IP:

Revolver
Member
posted June 12, 2000 05:49 PM         
You could build an array/list of function names and pointers to said functions. Read in the text, find it in the array, and call the associated function pointer. You can use STL "map"s to do this easily.

IP:

Cthulhu
Member
posted June 15, 2000 06:05 AM            
Any way to remove 'jigsaw effect' in Direct3D?

IP:

Prophylon
Member
posted June 19, 2000 02:28 PM            
Tis pretty easy, tune down your far clipping plane or/and scale down your entire world. This has something to do with the z-buffer (which is intrapolated(sp?) in 2D). You could also use a w-buffer which does the stuff in 3D. Anyway I didnt come up with this myself, credits and thanks go to John vd Burg (guy working on oxygen3d, which is a sweet engine).

IP: