 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| The Second Life of Brute Force Terrain Mapping |
|
 |
edotorpedo Member since: 8/16/2000 From: Delft, Netherlands |
|||
 Posted - 6/21/2002 9:33:40 AM |
||||
Hi, The method I'm using now is a mix between ROAM and brute-force, it goes like this: 1. divide terrain into patches(8*8 for example) 2. calculate mesh for each patch using ROAM, but independant from viewpoint (so it's only using recursive variance values) 3. render each patch into a display list 4. you're done. This way you do have a level of detail (flat terrain only have non-split patches), and you also have brute-force precalculated terrain. This method works perfectly fine for me, and is pretty fast (I also use frustrum culling for patches) because of the display lists. Any thoughts on this method? Has anyone tried this before? |
||||
|
||||
|
ZealousElixir Member since: 6/20/2001 From: Huntsville, USA |
|||
 Posted - 6/21/2002 3:23:10 PM |
||||
| How can you have negative FPS? I would think your FPS would simply approach 0; e.g. If I can only render a frame every 30 seconds, that's 1/30 FPS, not -something FPS. //email me.//zealouselixir software.//msdn.//n00biez.// miscellaneous links |
||||
|
||||
|
Palidine Member since: 12/13/2001 From: Los Angeles, CA, United States |
|||
|
Posted - 6/21/2002 3:53:54 PM |
||||
quote: erm. he just extended the line from known data points. you can extend lines into negative regions if you want. technically he should just cut the line when it hits zero and extend it out at zero FPS for continued levels of detail. but the framerates are particular to the system he used. the lines show trends and that's what is important about the graph, not the fact that they will both go into negative framerates. whatever, not a big deal. -me [edited by - Palidine on June 21, 2002 3:55:01 PM] |
||||
|
||||
|
ZealousElixir Member since: 6/20/2001 From: Huntsville, USA |
|||
 Posted - 6/21/2002 3:56:36 PM |
||||
quote: Not if it results in erroneous data; it eliminates the purpose of the comparison. Anyway, we all know that I'm right, so no big deal. Later, ZE. //email me.//zealouselixir software.//msdn.//n00biez.// miscellaneous links |
||||
|
||||
|
Ithyl_Chantresonge Member since: 2/16/2002 |
|||
 Posted - 6/21/2002 7:53:26 PM |
||||
| Just a few comments on possible improvements for the article. First, the graph ... The fact that extending lines leads to negative fps shows that the relation is not linear. It should be a curve that tends toward zero. That needs to be corrected if you want the crossing point to be of any meaning. Also, that may be a personnal choice but the units of the graph seems a little strange. The horizontal axis reducing toward zero make the reading confusing. I would suggest to change the definition of detail level to something along the lines of "detail level = 1 / 2^(size of quad)" instead of "detail level = size of quad". That would make the graph easier to read. It would make more sense to say that the higher the level of detail is, the more precise it gets. Second, references ... In the article, we find references to Willem de Boer and Bryan Turner's work. I think that changing the links to their actual papers instead of their email address would serve the reader better. I would prefer to read their article before contacting them about it. Third, the goal of the article ... After reading the introduction, I was expecting to find a description of the different methods to do terrain mapping with a long analysis of their pros and cons. Instead, the article turned out to be a to the point illustration of the fact that Brute force can be a good approach in many case. Both ideas are equally interesting IMO, but clarifying it would be nice. Enough critics ... On a positive note, the terrain mapping I was planning to use for my engine is something along the lines of "GeoMipMapping". This article allowed me to put a name on it. Hoping those comments are of some use, Ithyl |
||||
|
||||
|
Mage Member since: 10/7/2000 From: Kayl, Luxembourg |
|||
|
Posted - 6/21/2002 8:53:53 PM |
||||
| Hi there! I just wanted to tell my opinion on this subject: - You shouldn't compare brute-force with a ROAM algorithm on today's hardware. ROAM is particularly bad on newer hardware because of cache issues and the such. There are other algorithms out there which are specifically designed to run on modern T&L hardware, which perform much better (don't ask me names of algorithms, I have a particularly bad memory, but I do remember that several variations have been discussed in detail on GDAlgorithms-list). - Brute-Force is never optimal. You may be satisfied with the performance you get, but my personal goal is always to achieve optimal (or, let's rather say almost-optimal) results. 130 fps is not a bad number as such, but remember that a game needs more than just a simple terrain. And if your terrain eats up that much performance on its own, then don't try to let much happen on your landscape! Don't take this ill at all! You have shared your experience with us, which is a good thing, so I just wanted to do same! Cheers! [edited by - Mage on June 24, 2002 10:14:40 AM] |
||||
|
||||
|
Ardor Member since: 6/2/2002 |
|||
|
Posted - 6/24/2002 3:56:48 AM |
||||
quote: Not at all. GeoMipMap LOD can be done using an IB with several LOD versions of the same indexlist stored, so nothing has to be precompiled (except of the IB of course). So, even dynamic terrain is possible. [edited by - ardor on June 24, 2002 3:57:16 AM] |
||||
|
||||
 |
Sander Moderator - Web Development Member since: 4/19/2002 From: Den Bosch, Netherlands |
|||
|
Posted - 6/24/2002 4:57:28 AM |
||||
| Hey guys. Thanx for all the comments on my article (both the positive as well as the negative). It's my very first article ever so I can really ise all the comments I get to improve it. quote: This is the Geomipmap principle mentioned in the article. I find that it works really well until the terrain gets huge. If a BF patch takes up x memory, Geomipmaps take up approx. 1,5x with 2 detail levels and will approach 2x when the number of detail levels increases (anyone know how to write this in the 'big-O' notation?). quote: True... almost. You're correct that I should remove the negative values is the graph. They make no sense. MS-Excels interpolation did this. I'll correct it in the next revision of the article. If you take another look at the graph you'll see that the x-axis has a logarithmic scale. This means that the 2 lines really are curves if you would draw them on regular graph paper. You'd also need a lot of paper because it would get very wide. Hence the logarithmic scale and the seemingly straight lines. Maybe some vertical reference lines on the graph to show the log scale would improve it? quote: Simply true  I already added a reference section to the article on my site which links the pdf's on flipcode.com.quote: The methods I compared are all extensively discussed in many other articles (which I sould have added to the reference as well BTW) so I won't go over that. Same is true for the pro's and cons. You have pointed out exacly the core of the article here. Showing BF can be an alternative and should not be labeled as 'old, slow and redundant'. I guess I must have done something right quote: I will test it when I buy new hardware. One thing was mentioned a few times by e-mail to me. I didn't know this was possible when I wrote the article (but it will be in the next revision). The memory problems I mentioned with GeoMipMaps can be overcome by using an indexed vertex list on the highest detail level. For the lower detail levels, simply adjust the indexing of the list. No need to precompile all detail levels anymore. Thanx for all you're imput and happy coding! [edit] fixed spelling and added geomipmap vertex list Sander Maréchal [Lone Wolves Production][Articles][E-mail] [edited by - smarechal on June 24, 2002 5:01:12 AM] |
||||
|
||||
|
PrettyBoyTim Member since: 2/5/2002 From: London, United Kingdom |
|||
|
Posted - 6/24/2002 6:27:55 PM |
||||
| Re: Geomipmapping... Geomipmapping need not be as expensive as you make out, as you can generate your tiles on the fly. This does have a slight performance overhead, but you could spread it out over several frames, and if you use a tile cache you could reduce the overhead to be only when you really need it. A good URL describing geomipmapping is a talk by Glen Corpes: http://www.cix.co.uk/~glennc/gdcetalk_files/frame.htm I based a landscape renderer on his system, with a slight difference - instead of having sixteen combinations of edge divisions, I simply have two versions (high & low) of each of the four edge strips, and a single interior section. This is a substantial improvement in memory when the detail starts getting higher, at (I suspect) the cost of a slight drop in efficiency. (I assume - I've never actually measured it...) |
||||
|
||||
|
Symphonic Member since: 9/8/2001 From: Boston, MA, United States |
|||
|
Posted - 7/5/2002 4:05:40 AM |
||||
| Improving brute force. Typically you can render a heightmapped terrain using Triangle, Triangle-Fans or Triangle-Strips. From former to latter these are increasingly efficient methods because they reduce the number of Vertices you have to send to the hardware. I'm using the TriStrip method, and my little trick is to determine the lowest height on the map (stored at initialization), and calculate exactly how many strips of what lengths will fill the view-frustrum, if all the heights were that minimum value (and since they are all greater than that value I'm in good hands). It is an elegant solution, being just a set of intersections with the frustrum, and the list you generate each frame is considerably smaller than that produced with ROAM (and much faster). The results are stored in a contiguous array in pairs and then I just iterate through the array and render those strips. For comparatively small maps (32x32) there's no respectable difference in FPS (avg. 50.2 vs 49.8), but when maps get up to 256x256 squares (my viewfrustrum depth is equiv. to 100 square edges) the culling method retains good numbers while the brute force falls off fast (1.6 vs 31.4). Mind you, I'm using a pleasantly aged P3-866/GF3 so these are good framerates by my standards  George D. FiliotisAre you in support of the ban of Dihydrogen Monoxide? You should be! |
||||
|
||||
|
alexjascott Member since: 8/20/2002 |
|||
|
Posted - 8/20/2002 11:38:59 AM |
||||
quote: This is exactly what I am doing. The problem will be matching up the patches so that gaps dont show - so I have a 'edge' square all around each patch with has an additional triangle in it so that it will 'fit' with either lod+1 or lod-1. However this means you cannot move from 1 lod level to a lod level MORE than 1 higher - but this shouldnt ever really be desirable anyway. I remember seeing an article my someone from Lost Toys (an ex-bullfrog programmer) the other day that is doing EXACTLY this with his new engine. |
||||
|
||||
|
alexjascott Member since: 8/20/2002 |
|||
|
Posted - 8/20/2002 11:56:12 AM |
||||
| Ah found it. Just to stress I didnt COPY this, but thought of it, have partially implemented it, and then found it whilst searching on the net; http://www.cix.co.uk/~glennc/gdcetalk_files/frame.htm#slide0001.htm |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
