Joe Rambles

Table of disContents:

10 June 2001 : (Joe) Canoe World

My basic thought is to create an adventure 'engine' which allows users to share outdoor experiences like canoeing, mountain climbing, sailing, etc with each other on-line. The main idea is to make it look and feel as real as possible which includes making the water and the forests and the humans so realistic that they cannot be distinguished from the real thing. Well, for now, let's say they cannot be distinguished from a video of the real thing.

Why is this different from what Half-Life and Quake III and the rest of the game industry is doing? These guys are the pioneers who created the cash flow that drives the development of graphics and hardware. I love them. Without them we'd be nowhere today. But, they only have enthusiasm for shoot-em up games. That's where the big money is. The computer game industry makes far more money than all of Hollywood's movie production (you probably already knew that) so why would they give that up to do anything else?

But, outside of the mainstream game industry, there are people who are working on vr. Just to give you an idea of how many people, here's a url for a german web site (in english) that keeps a detailed list of graphics engines and their features (there are hundreds of engines) .

http://cg.cs.tu-berlin.de/~ki/engines.html

It's overwhelming to see so much being done. There is also a nice web page at

http://washedashore.com

He has a couple of interesting links, One is:

http://vterrain.org/

You might want to take a look at some of this stuff.

Here's a short list of things I've been thinking about.

1. a nature engine. that can create realistic outdoors scenes as an environment for the players on-line. What has not been done in real time is waves and rapids and trees that look real (3-D)as you get close to them. Halo is working toward that but I have only seen fuzzy video clips so far that suggest a lot of bump mapping and perhaps mpeg projections. Notice that the outdoor games stay away from forests, with the exception of Everquest which does not make much effort to create realistic anything. I call it the plywood look.

2. a repository of natural terrain models based on real places. I like the boreal forest. I have not seen anyone doing this yet. I am bored with deserts and places that lack character between the rolling hills and the textured grass. I think forests are necessary. I have some ideas about how to make forests but it's the one thing I have not experimented with yet. There was no use experimenting because I didn't have any ideas. now I have at least one that might work. I did write some program last year that took usgs elevation data and combined it with satellite pictures to produce a fair mountain scene. I'm going to attach an image from that experiment to this e-mail.

3. develop real looking avatars so people can get into the characters. this is very important and although I have developed a technique and a couple of demo programs, I have not had the energy to do all the work here. The whole character has a skeleton with inverse kinematics, muscles and skin. The face and hair and hands and feet need special treatment. There's a lot of work to do here.

4. add communications and write the code so it can adapt to new technology eg. these glasses: http://www.isense.com/products/pro/index.htm

We can't produce a holodeck but I don't think that is necessary in order to get people emotionally into the scene. Games have already proven that. But I'd like to get enough immersion so that the " suspension of disbelief " would be maximized. The plan is to replace the intensity of the shootem-up game with the awe of nature. Transform all that hormonal cpu time into an outdoor adventure in classy surroundings. The wind, the waves, the rapids and the peaks are as formidable adversaries as Doom's Cyberdemon.

All this is easier to say than to do. The things I have done are piecemeal and cannot lead to anything without some kind of coordinated structure. Also, they need more work beyond the proof-of-concept programs I've already written. It seems like a big job, but I think it can be done if we take things one problem at a time and keep in mind that everything has to fit together into one engine. One of the things that I realized early on is that the developers of these engines need tools of their own making beyond the off-the-shelf stuff like photoshop. For example if we wanted to make a river using the same wave generating method I use in the canoe program we would need a way to tell the water where its boundaries are and be able to put rapids and waves where we wanted them. There is no canned method for doing this now. So we actually need a world-making tool... something like a level maker I imagine.

well, this is getting long and I think we should talk in person or on the phone about how to get started. Let me know what your schedule is these days

joe dart

25 June 2001 : (Joe) Virtual

I have not gotten the terrain patch for you yet. I am wondering if it makes sense for me to put it into RAW format since we would be using USGS and similar formats for our terrain. So maybe I could just send you the read routine I use for the USGS DEM's (DEM=their file format which is an easy text format) and a DEM file sample. Of course a small map doesn't make sense since the idea is to not depend on the view frustrum clip planes to reduce the drawing.. Before we render any terrain shouldn't we determine the range of locations that will appear in the frustrum. so, even before we ask the bsp or whatever to sort out the order of what is visible, we need to limit what the bsp has to be concerned with. Does this make sense to you? If the viewer only looked in one of the cardinal directions that would be easy.. but unfortunately the viewer may look in any direction which eliminates a simple x range and y range. Then there is the problem of perspective which make the frustrum an odd shape. But that odd shape can be determined from a formula.(it's in the opengl red book near the back)

I have been reading this web article about ROAM and its offspring. ROAM is one of the popular terrain mapping algorithms that is used in outdoors programs like the flight simulators. apparently it has some problems with cracks that appear but there are several methods developed to clean these up. One of the things I learned when I worked with hierarchical splines is that an algorithm that deals with LOD (level of detail) can be efficient, but the subsequent cleanup to make the edges between adjacent polygons snug can burn up whatever time savings you gain. These cracks have tarnished the basic ROAM idea because fixing them involves screwing around with (altering) adjacent polygons and this is not an easy task after the affected neighbors have been submitted to a queue for drawing.

In any case, it is my impression that these problems have been beaten and now there are fast algorithms available for terrain. We just have to settle on the best one. Our problems may be different than those in a game since we are still concerned with maintaining "realism" as things get further away.

By the way, here are three things that come to mind when I think of LOD:

1. How many polygons should be used for characters as they recede from the camera. This involves not only the shapes' details but the textures as well. Opengl uses mip mapping to deal with the texture issue. More than one version of the textures are created. Then as the object moves away, the number of texels used is reduced by swapping a cruder texture map. I am not sure if we should worry about the numbers of polygons in the characters since there would be very few characters involved. Again, we don't have to deal with this stuff up front. As long as we keep the program organized so that we can make subtle changes later without completely re-writing everything we will be safe. So it doesn't hurt to anticipate a possible need even if we are not going to address it right now. so this problem can be back burner'd.

2. But more important is is the question of how many polygons to use for terrain features. Terrain has various levels of detail. If you use the same number of vertices necessary to draw the details of some localized bump over a large map that is otherwise featureless, you burn up a lot of cpu time unnecessarily. The trick is to make the engine work only when there is something to draw but not force it to see all terrain as equally detailed. This is the essence of the LOD concept. So a little knot of hills further away from the viewer may require more cpu to render than less detailed terrain that is right in front of the camera. This has to be a central ingredient whatever technique we use. This is what I believe is the real problem we face right from the beginning... thus the need for LOD thought.

3. Finally, there is the question of aliasing. If you draw a checkerboard and view it as a plane moving off into the distance, the flattened checker squares on the horizon start to glitter because the proximity of the images creates an aliasing problem. My graphics card has a built in antialiasing feature of opengl. It is my opinion that we should not dwell on this problem but let the new hardware deal with it. Anti aliasing slows things down a lot. That would reduce realism too. Something we may come up against but does not affect us getting started. Back burner.

So here is my simplistic take on all this. We should get an understanding of the LOD techniques that are now being used in terrain maps and use the one best suited to our (realism) needs. The Watt book (which you Pat have has some useful discussion).. by the way, the two new Watt books are on the way.. I also ordered the book that you (John) mentioned.. "Game Programming Gems" hoping that it may have something useful.

Got any other ideas about any this stuff?

joe

25 June 2001 : (John) Reply

Couple random thoughts...

First, I'm thinking that we are missing something when we talk about terrain mapping. Maybe I'm crazy...but I just need to get this straight in my head...

It seems to me that "terrain" could involve two separate approaches.

1. the "ground" - what the players walk on

2. the landscaping - what the players walk through (forests, water, bushes, corn fields)

Perhaps my nomenclature is misleading, but what I mean to say is... There are certain aspects of the world that become "blankets on the horizon." For example, a distant forest can perhaps be viewed as a texture, but at "mid range" becomes quite a different thing. On the other hand, a grassy field would look almost identical at all distances.

I guess the old phrase "loosing site of the forest for the trees" applies on a number of different levels.

The thing is, when I think of terrain from a distance, I picture the forest. But when I think of the local terrain, I picture the ground.

I'm thinking that making these elements separate is a positive thing.

Okay, I think I got side tracked.

John

25 June 2001 : (Joe) Response

Interesting problem you bring up. Well first let's get the skybox out of this definition of terrain since the horizon can never be reached by the player no matter if it is forest mountain or sky. So the images on the skybox are only affected during rotation of the player. There is no "where" in the terrain for the skybox images. This is the easy problem.

The harder problem is the other intermediate stuff you brought up. Initially I was thinking about the terrain as hills and valleys.. not really thinking about the trees etc.as part of that.. like they were just stuck in the terrain. But now I see that is too simplistic. since they constitute the great part of the obfuscation, they must be part of the bsp tree and follow the visibility rules of the bsp (or whatever method we use).

Here is one difficulty. If the trees are part of the fixed terrain, suppose the user wants to chop a tree down. what happens then? The tree, which was part of the fixed terrain has suddenly become a dynamic object in the terrain. This is an interesting problem because walt disney had the same problem with regular animations a long time ago. He would have a forest background painted and the characters would be painted on plastic panels layed over that background. To animate he would put a sequence of character panels on the background one at a time and take a picture of each. But what if a character wanted to pick up a rock that was painted on the background? To do this, the rock had to be repainted on yet another plastic sheet and then erased from the original background before the character could pick it up. This is parallel to our problem. Since the sorting algorithm that lays out the bsp or quad tree has already determined that tree is a permanent fixture (background), how can it be removed from the scene (chopped down)?

Off the top of my head, I would suggest that as the player approaches background (fixed) ground items that they become 3-d items. The original image (that this 3d image replaces) can be made transparent. So now what we have is a tree whose position still conforms to the map position. But now suppose the player chops the tree down. This means the tree goes from being a terrain object to a 3-d object dissociated from the terrain. We could then treat the tree in its newest incarnation.. (like disney) as a regular object not connected to the terrain. The original tree was in a node in the bsp and if the tree is removed from its original terrain position, I am guessing that the node has to be cut out of the bsp tree. (similar to disney's painting over the rock in the background painting) Also, the original tree position would have to lose its collision detection response so characters would not be bumping into objects that were no longer there.

This gets complicated. But you are right in your question. the terrain is more than the surface of the ground. So here is what the terrain could look like logically (just a possibility) . It could have coordinates and objects could occupy those coordinates. (trees etc) These objects could be detachable from the bsp (or whatever) should they be "chopped down.". Then the original image would be made transparent , lose its collision detection and be excised from the bsp tree. BUT the new slain tree would have to be treated as an independent object that has to be fit into the action in the same way that any other non-terrain object must be fit in.

This is another reason why those vast outdoor scenes in games are wastelands and why you can't knock the walls down in quake.

good observation. Now what do we have to do to make it work?

joe

26 June 2001 : (John) Seeing the forest for the trees

Here's more food for thought...

What is a forest?

Is a forest a collection of randomly placed trees?

From a distance, a forest of mostly spruce trees looks quite different from a forest of mostly birch... is that a consideration?

If a forest is just a "region", then perhaps it could be a region with a population number as well. When trees are cut down the population shinks. The look of a forest from a distance could be partially determined by the "tree density" of that forest.

What do you guys think...or is it too early to worry about these things?

John

26 June 2001 : (Joe) Seeing the forest for the trees

These are good questions.

What is a forest?

Is a forest a collection of randomly placed trees?

Here I think we can have our cake and eat it too. If we seed the random number generators in both machines with the same seed, they will produce the same series of random trees. So, even though the trees have been placed "randomly" they will appear the same to all players. It seems like trees can be treated like particles in that they have an on and off switch. ON tells us that they are standing, what type, they are visible, they are in the bsp tree, and they have collision detection.. While OFF means they are no longer there. Since we are moving around in the scene it will be necessary to keep track of the trees' positions in the same way that quake keeps track of the walls of the rooms. This means we need to generate them at bsp tree design time (long before the game starts) and store them in a data file and load that file at the beginning of the "level." I don't see a problem with this since no matter what the terrain holds(even if it is empty) we will have to ask the bsp to tell us what is visible..For us, the forest is the freater part of the "walls". I mean something will always be visible. So we are not paying anything more by keeping track of the trees (which are simply polygon structures) than we are already paying by keeping track of any other structures within sight of the camera.

Looking back over this last paragraph it seems like the positions of the trees would have to be generated at bsp creation time. This means that the random number generator along with some basic rules would position them in the scene. Then the bsp generator would make the bsp tree (I am saying bsp but I mean whatever method we use) using the positions of the trees as if they were walls. Then after the bsp tree is completed we need to store that in a data file. But it may not be necessary to store the actual locations of the trees in the data file because when the level is launched, we can use the same seed and the same trees as are in the bsp tree will be re-generated.

when it comes to generating trees, there is a method called the L method that is a sort of fractal technique. Personally I think trees made by it are not very realistic. Realistic trees can be made by combining a few parts (branches) in a variety of colors, combinations and sizes. I was looking at the spruce trees today and realized that most of them are indistinguishable from each other except for a few snag types.

These two (above) situations would prove disastrous.

- A chopped down tree will magically "re-grow" when player returns. Or is a forest a collection of predefined tree co-ordinates?

I think there is no other way. To make the trees come and go whimsically would cause discontinuities that would be very inconsistent with a real experience. (except in some parts of the amazon jungle)

Do we include other "attributes" when storing a trees co-ordinates... such as height, diameter, age (number of branch layers)?

My thought is yes.

From a distance, a forest of mostly spruce trees looks quite different from a forest of mostly birch... is that a consideration?

Yes, I think so. This tree design information can be incorporated into the struct. That's why I think trees should be treated like particles. The random number generator creates the trees but that creation is subject to some rules about what kinds of trees should be created in a given location. Birch, spruce, aspen, alder, mixed, old growth, shrub etc. It would not be sensible to make a birch forest up above the timber line.

If a forest is just a "region", then perhaps it could be a region with a population number as well. When trees are cut down the population shinks. The look of a forest from a distance could be partially determined by the "tree density" of that forest.

It seems like this is a matter of keeping track of what we have..

What do you guys think...or is it too early to worry about these things?

These are good thoughts John. We need to nail it down. Brainstorm now and we avoid intractable problems later.

Pat. Are you there?

joe dart

whoops.

I think my assumption that all rand() implementations would produce the same sequence of random numbers if seeded with the same value is wrong.

erase that.

joe

5 July 2001 : (Joe) Meet

As I mentioned last time, I've invited the Maya graphics guys to this meeting so we can decide if they can be helpful. I didn't notify them until today so I hope they can make it on short notice. One of the things that I know we will need is someone to create tiles from various textures. By tiles I mean texture patches that can be placed side by side with no seam showing. I did my own tiling in the canoe program's water and it is a pain in the butt. We should let these artistic guys work on this kind of thing so we can focus on programming. I have seen their work and they are very competent... in fact I'll bring a disk with their final maya project from two years ago to show you how good they were then.

Very large textures are not very efficient when they are sent to the video cards for obvious reasons. But some textures cannot be reduced to tiles because the image is not repeated. In order to leave room for these, we should tile whatever we can. I don't know what experience you have had using textures, but if an excellent texture is stretched too much or scrunched too much or stretched more in one direction than the other, it can look pretty crappy. So we should start off with good textures in optimal sizes and use opengl's texture mapping so we can take advantage of the graphics board's efficiency and the little tricks that opengl provides like multiple textures and tiling. I don't even want to bring up the problem of shadows right now. It is something we can put off for awhile since the shadow routines are squeezed in at rendering time. We will need shadows and we could use a pre-written opengl library written by kilgard (the guy who wrote glut) or do it ourselves. The trouble with kilgard is that he is so technical (and a show-off in his code) that it is hard to figure out what is essential to the routines he writes and what is programming showboating. I once spent a day trying to figure out how he was doing some routine in a caustics program and finally gave up. I commented out the routine and the program worked fine. I never did know what it was supposed to do.

One other thing. By now you must realize that our work ends in laying out the triangles. At this point opengl takes over, filling those triangles with correct lighting, colors, textures etc. So we do not have direct access to pixels (without going to the various buffers and interrogating them.. time consuming) But we can deal with texels and this is a good second best since almost everything we draw will have textures. Additionally, textures gives us alpha to work with so we can make the edges of the textures irregular (as with billboarding trees)

I don't know if it is possible to have the Maya guys create 3-d objects for us since maya does use a lot of space. However, I do think they have control over the number of points in an object so it is possible that they could create objects we can use. In any case we should talk to them to see what they can do and make sure they understand the real-time constraints we are working under. We also need to be sure they can put their output into files we can use... including any necessary textures.

Speaking of which, I wrote/stole an opengl routine which will allow us to print out the frame rate of any scene we are showing while it runs. It will be handy for finding out how much the frame rate is reduced as we add functions to the program. In the end we will need to determine how much time is being spent doing each task.. easy in unix and possibly in visual c. Maybe you have seen something like this?

Anyway, let me know if there is any problem with meeting tomorrow. Otherwise I'll see you there.

joe dart

7 July 2001 : (Joe) Yet another BSP explanation

Here's a web page I found a couple of years ago. It has a very good explanation of bsp and some code. There are a lot of dumb pages out there which are more confusing than helpful, but this one makes sense.

http://www.cs.wpi.edu/~matt/courses/cs563/talks/bsp/document.html

joe

8 July 2001 : (Joe) Jackpot

ok you guys I think I've found the way to go. Here's a method called ROAM (Realtime Optimally Adapting Meshes) which is universally acclaimed by the whiz-geeks as the best outdoor partition technique to date. I found a web page with an excellent description of the technique and a demo (with source and executable) in cpp and opengl. One of the big advantages of this method (aside from speed) is that it works very well with DEM data which is the USGS format for storing elevations.

http://www.gamasutra.com/features/20000403/turner_01.htm

I also have a printout that has an innovation in the ROAM technique that speeds it up even more. (I don't know where I got it from the web but I have it in hard copy) If you get a chance to look at the above article (and try out the accompanying demo) before friday I think we can get this phase out of the way pretty soon. I'll bring some copies of the fast algorithm paper.

Let me know if you have any thoughts about it.

joe

10 July 2001 : (Joe) Game Gems

I've been going through the web pages trying to get to the "frontier" of all this terrain stuff. I sent a note to Turner (the guy that wrote the Gamasutra article) to see what's new in terrain algorithms. He wrote right back and he mentioned an algorithm called CLOD.

Here is his reply to my question which asked him to clarify the relationship between LOD and BSP/Quadtrees etc. This problem is getting more interesting all the time.

anyway here's his letter:

His last comment "To answer your..." throws me off a little. Above it seems like he is saying we need to deal with both problems separately but in this last line he suggests that ROAM does both. What do you make of it?

joe

10 July 2001 : (Joe) The Dawn

ok

I have been staring into the abyss of this ROAM/CLOD stuff and now have a grasp of how it works.

Initially I was only paying attention to the fact that a point is calculated in the middle of the hypotenuse, and then this point's height position is compared to the actual coordinates of the same data point on the surface. When these two values are too different, the triangle is subdivided along the line that connects its original right angle vertex and the new point, and the map's height coordinate becomes the height for the new point. This may require the adjacent triangles to be split in order to adjust the nearby points.

OK, so far so good. But what I was not paying attention to was how they were determining when the calculated midpoint of the hypotenuse was too big to ignore. This is done by knowing how far this point is away from the viewer. When the point is close to the viewer even a little variance requires the triangle to split.. because it is close and easy to see. But when the point is far from the viewer it takes a greater height difference to initiate a triangle split. This is because at a distance the actual large height difference is diminished by perspective.

It all makes sense. His demo program is CLOD. It also explains why when you run his program some of the patches bounce around as you turn the viewpoint. Apparently the arithmetic variations are causing this to happen as the viewpoint changes.

are you with me?

joe

12 July 2001 : (Joe) Terrain

I have been remiss in my duties in getting the terrain section together because I've been learning about Binary Triangle Trees. Why only last week I couldn't even spell CLOD. Now I am one.

Yes, we need to have a piece of terrain that we can work on so I'll do it later tonight or tomorrow at the latest. Here's what I will get together for you:

1. the USGS file (I'll tell you where to download it from and which one)

2. I'll send you the source code for my routine which reads this file into an array. The format is only complicated because it has a file header and record headers that have numbers relating to longitudes and latitudes and record lengths/counts, most of which I currently bypass but which may be useful to us later. Mostly the file contains a bunch of elevations in rows and columns.

Patrick is under the gun this summer, so we'll have to go it alone for awhile. It is good that he can be there on Fridays because he can keep up with what we are doing.

My thought is this Friday we should clarify the terrain method we will use in the beginning and design the data structure(s) we'll be using, and the names/ arguments for the functions. we might want to think of the cleanest names so anyone can read the code because should we add programmers later we don't want to scare them with MKv3-19->BQS type variable names. They should (knowing how to program of course) be able to sit down and read the source code like a book.

joe

12 July 2001 : (John) Variable Names

That all sounds good to me.

I agree with your concerns about variable names in the code. I used to add a lot of comments to my code, but I read a really interesting article a while back( http://www.gamasutra.com/features/20010119/warden_pfv.htm ) that convinced me to change my coding style.

The article suggests that adding adding detailed comments is a good idea in theory, but when you code is changing during development, those comments are often overlooked and can often be quite misleading by the end of the development. The author suggested a better method is to use very descriptive variables.

Well, anyway... sorry to hear that Pat isn't going to be able to work on this, but I completely understand his reasons.

John

12 July 2001 : (Joe) Variable Names

that was a good article. since Pat won't be available until the end of the summer, I've invited another programmer to sit in tomorrow. He's got a good head. Micah Caldwell is his name. He currently works for DC&C on their database (one of your boys) but has also spent a summer programming for GVEA a couple of years ago. I did manage to meet one of the guys from the Maya group who didn't show up last Friday and discovered why they didn't come. Apparently they have a class at exactly the same time as we met. Apparently their schedules are opposite to yours. They either work of take classes after 5 pm and are free before that. But we don't need them right away anyway.

Still looking at the code for binary triangle trees. I like the way he writes with comments. But I agree with you about comments. You have to be really careful to make sure that the code matches the comments. The only time I put in comments is to explain what a function does to myself. If the code evolves away from that then I am in trouble. But the best way to code is to make the code itself readable (as in the gamasutra article you mentioned below).

joe

16 July 2001 : (Joe) Terrain Again

Gentlemen:

Well it looks like I am headed for a c version of the binary triangle tree instead of CPP. (at least for now) Since I already have all that c code (for splines and fps timers and tcp/ip etc) I am not inclined to work in cpp. It is an efficiency question.

As I get into his code I can see that he has cut some good corners.. saved memory and written a very clean program. I can find all the functions and the material related to the binary subdivisions is nice. However, I think he has a tendency to multiply and divide too much. (for example he does a bunch of sines and cosines where he actually does the pi/180 divide in every calculation rather than defining the TO_RADS number. When he subdivides the triangles he ends up drawing each triangle because he loses the ability to draw using any of the opengl goodies like triangle strips or fans. I don't see any way around this right now but it seems wasteful. Also, He zeros out his variables when he reconstructs the trees and does some other arithmetic stuff that I would not like to maintain. These may seem trivial but this program runs very slowly when you come down to it. If we use his code without speeding it up, I doubt it will serve us very well.

I won't even mention the opengl problems because he fessed up to his inexperience in that early on. But it needs serious revision. No problem there. Of course a lot of his code is not relevant to us since its objective is demonstrate. It is not industrial code. But I believe we can make this concept or a variant of it run a lot faster. The problem I have is that I do not know what causes cpp to slow down and what is elegant so I am kind of reluctant to tackle it when I am trying to make the code more efficient. By the way, I thoroughly understand this cpp code. The cpp here is not complicated. (He seems like he is really a c programmer) I just don't want to get bogged down writing poetry in a foreign language.

John. I think from our discussion that you might have some misgivings about this. Let me know. The only other comment I should make is that this program is a trip into unexplored ideas. CPP seems too anal to accommodate this kind of exploratory programming. We can't predict what we may invent and have no way to know how it will all fit together beforehand. John scared me with his discussion of memory leaks.

I have also knocked out the windows.h include and all that MS crap(replaced it with glut). But that will not speed anything up. It will only make it less microsoft dependent. with a few ifdefs we can compile it on any machine. Speaking of which Micah.. can you get a Macintosh to compile opengl programs?

So I'd like to hear all your opinions on c versus cpp. In the meantime I am going to try to get my rendition of this code running by Friday. I have already figured out how to replace his map with a general usgs map. no problem there. It still looks like a month of work to do it right but at least I may get a basic ROAM terrain operational this week.

joe

19 July 2001 : (Joe) Reminder Friday Meeting in Chapman

so I've spent the better part of a week screwing with this program. I put the C version on the back burner because it would take me another week to finish it. So I decided to take the short cut and alter his original program to accept USGS data files and texture files. His program uses a height map file that contains unsigned characters (0 to 255). this is more restricted range than the USGS height values so I spent today trying to alter his program to accept the USGS files or at least the kind of data they offer. I changed his file input from "unsigned char) to (int) and went through the program cleaning up all the errors that came up as a result. I finally got the file to read the data into the program but somewhere later on in the code it does not like the integers.

At this point I've made a few other adjustments to his code. I dumped the windows stuff and added some include files which are more universal and also got GLUT to do its thing correctly. His openGL is pretty hacked up and is strewn all over the place. Hard to get a grip on how to unravel it. He has integrated the variables he uses for FOV with openGL's frustum setup. This makes sense but it complicates what would otherwise be relatively easy. So I have to be careful when I rearrange stuff.

Tonight I'll try to figure out why it doesn't like the integers. If I can't figure it out right away, I'll go on to the problem of getting the program to read texture files. These do not seem like such formidable obstacles. Hopefully I'll have something for tomorrow's meeting.

see you there.

joe

21 July 2001 : (Joe) Bryan on Roam

23 July 2001 : Uh oh

I just discovered a peculiarity in Bryan's program. If you get into the nitty gritty you realize that he is not using the conventional order xyz in assigning the x,y,z value for the point where the viewer is standing. He gives glViewPosition[]={0,5,0} as the viewer's position.

However, this order is not {x,y,z} but rather {x,z,y} So the 5 is actually the z value and NOT the y value as it is conventionally. I don't know why he did this because the order in his normal routine is the conventional xyz. Probably some artifact of his fixing things up after the fact. I'm going to change this to conform to the conventional xyz order just so we are not scratching our heads next year wondering why we are confused.

joe

24 July 2001 : On Water

A little distraction from my current map program but I found this picture and am hypnotized by the desire to make it happen in real time. That flushing water would be a great challenge.

It looks like there are three components. 1. the surface needs to have a spline control like my canoe program so the standing waves can squirm around, 2. The surface has to be a dynamic blend where one of the textures is fixed ( the blue sky reflecting on the dark blue/black surface) while the other texture with some foam specks is sliding over it, 3. the flushing has to dance around and reshape.. possibly some variant of a particle system combined with spline/texture. It wouldn't be easy and that's what makes it interesting. I've stood on ledge below water like that in the springtime. It is thunderous and terrifying. The mind conjures up images of a frustrated, ferocious and pitiless dark churning beast straining against its tether to sweep you away. Oh I'm ok heh heh.

joe

26 July 2001 : Terrain Revisited

Patrick: I know the English course on top of the unfinished 481 is creating a dilemma for you. I wouldn't want you to get your dangling participial adjectives in the pluperfect subjunctive case, mixed up with your inverse Fourier tensor space transformation eigenvector mappings. You will be sorely missed Friday. Don't get overwhelmed.

Anyway, all I am hoping to accomplish by Friday is to get the ROAM program operational with the USGS map and our texture, and you already know the problems we have with that.

Assuming we have it solved by Friday, what we might do then is make some decision about how to connect up the right textures with the right patches and how to get this into the cpp idiom. For example, suppose the surface scene texture is some rocky ground surrounded by lichens. We will need to project the correct pieces of that scene onto the right patches. So each patch struct must have a pointer to its own texture map. This would simplify things. However, in the current cpp program with the two classes (landscape and patch,) the patches are not created by the landscape class until run time. This leaves us with the question of how can we assign textures to the patches in advance, before they are even created? Since the height map file tells us how big the landscape is going to be, we already know how many patches will be in it, so we can make the assignments in advance, then we can notify the the patch->texture_map pointers at patch creation time what texture is theirs.

This is a lot easier to do than to say i suspect. Let me try to write it in order:

1. Texture guy determines how tall and wide the landscape is in patches. He knows this from landscape size and height point density.
2. He lines up the textures to be read in the same order as the patches. (we need a special landscape texture patch read)
3. As the patch is created by the landscape, the texture map address is assigned to its texture pointer.
4. When the surface is displayed, each patch calls for its own texture map.

Maybe there are some other alternatives. John? Pat? Micah? Got any ideas?

John. Pretty soon we will need to answer your original questions about how to treat objects like forests etc on the surface of the landscape. Do you think we could do the intermediate/distant forests with layers of transparent rectangles of forest texture images billboarded onto them? That's my first thought, and I'm only proposing it without having thought it through. When I drive around these days I look at the tips of the trees on the horizon trying to get an idea of what I can actually distinguish about the silhouettes of the tree tops at a distance. We can probably get away with a lot when things are a hundred yards or more away. We will be left with the question of what to do close up.. but that to me will be the final frontier and should be most of the fun for us when this gets rolling.

I am still hoping that the concept of projecting 3-d trees onto these billboards which only return to 3-d life when they get a certain close distance from the viewer will be a useful plan.

You know as I keep thinking about this. Our situation with its layers of forest presents a different set of problems than the landscape LOD solves. The ROAM method assumes that the terrain is always visible. For us, the distant ground itself will not be visible to the viewer except in the great vista shot across a river/lake or from a mountain top. Most of the time he will be surrounded by closer up forests, cliffs, water, etc. Are we making a bad turn here? Should we be thinking about some other way to describe our layers of forests than ROAM? This might bring us back to square one but better now than later. Of course we would still need terrain because the trees are standing on hills and valleys, but do we need to LOD that terrain itself? Since it is not even visible? Maybe we need a refinement to our thinking.

Comment about the movie of the game I put on the orange cd last friday. That game has a terrific real-time advantage over us in that the camera only looks downward at an angle. It has no horizon. Thus it never has to deal with the problem we have with the terrain LOD. But the player is always removed from the scene, being in the god-like third person position. One thing they do which is interesting (although not realistic) is to dissolve the foreground trees and objects in order to allow the player to see the characters and action.

anyway I better get back to programming.

joe

26 July 2001 : Texture is Working

ok. we can now put our file textures onto the patches. I have 256 bill the cats projected onto the surface. It's a frightening scene. Next is to get the program to read the USGS files so we can make our own contours. If I can pull this off tomorrow (actually today) we will be in fat city.

By the way, it didn't seem to slow anything down. he was creating 512 by 512 textures but only using 256 by 256 on his patches. I boosted it up to 512 X 512 to see what would happen. No problemo.

joe

27 July 2001 : Done

at 4am I finally got this thing running right. Now the ROAM program can read texture maps from files and the USGS heightmaps.

There's a couple of little glitches in the code I have not looked at yet. They were also in his original program. First, there's a line that leaves the final corner of the surface and goes off into space. I'm pretty sure it is because he overshoots at the end of the surface. I found several tests he was using to limit drawing that were going out of bounds because the tests were not written correctly. This errant line is probably the same kind of thing. Second, little bumps keep shifting around as the program runs. This is a bad problem (also in his original program) since it detracts from the potential realism. But these are both solvable. he even mentions the latter problem in his gamasutra article.

One observation. This terrain is a very large area that covers part of Maine and northern New Hampshire. It is not ideal as an example because instead of using a smaller area with more dense height points, I used this big map. It looks ok on the ground in the drive through but is not as refined as the maps we will be using. This map is 1024 by 1024. My machine is too fast for the drive through so I slowed it down and now looks pretty good. We may have to speed it up again for slower machines. We will have to clean up this program quite a bit to make it do what we need, and one of the things we will need to do is make its action-speed cpu independent.

Anyway, now that this program is running I have more questions than answers. It runs very fast (that's what we were hoping) but does it do what we need doing? We should spend some serious brainstorming time with this question.

I'll be there tomorrow with my usual disks (which will have this program on it) and I'll also bring the "3-d graphics file formats" book John.

in any case I'll have it on a disk at 5pm chapman. I'll see whoever shows up.

joe

29 July 2001 : Shading

This ROAM program never had real shading because he simply glued dark texels to the texture. He said using lighting was too slow. That's nonsense. Now I am trying to get the lighting to work correctly and suddenly realized that his technique for shading with light (even though he never used it) cannot be made smooth because he simply finds the normal of a triangle and submits that to the renderer rather than finding the normals for the three vertices and rendering them separately. This means that he can only make the triangle one shade and thus the gl_smooth cannot do its job. The answer is for me to add a function that makes the correct normal for each point when the file is read and then to submit these normals to the glvertex commands for each point as it is drawn. To make things even worse, he made the height map a 1 dimensional array which means a lot of arithmetic to find a point's neighbors. groan, I think, since this is only done once, I will transfer the points to a 2-D array and then plug that into a function i have already written to do the job.. and then put the calculated normals back into a 1-d array so they can be associated with their corresponding height points. But it is still worth it. I even think that when we get through fixing the opengl this program may even be faster.

A second thing is that weird line that sticks up at the end of the surface. I have located the function that causes it but am still trying to see how to fix it without disturbing anything else.

So that's what I'll be doing this week. I hate to say it but the more I look at this program the more I see that it must be changed before we use it as the core of our terrain generator. Not being able to find the x,y of any height point will make it very hard to place trees and rocks and keep track of people/objects on the terrain. I guess we have two choices. 1. is to have converter functions that will convert a height point from the 1-D array to x,y (and visa versa) or 2, rewrite his functions to use 2-D terrain coordinates. We are talking about weeks of programming and debugging with this latter approach.

But as I keep repeating, the essential ideas in ROAM are very valuable and worth some effort to use. I knew we could not just plug it into a serious engine since he told us up front that it was a demo-only program.

Anyway I'll tackle the shade/light problem.

joe

30 July 2001 : 2d to 3d

Today I got the program to calculate the normals and they are now (theoretically) in an array of normals waiting to be called into service at rendering time.

What I'm trying to figure out now is which normal goes with which point at rendering time. Once I have that I can simply turn off his fake shadowing and invoke the normals. By tonight I should have it.

Last night Micah and I talked about the overall problems entailed with cludging this ROAM program to fit our needs. This may give us serious problems in the future. Here are the things that would get in our way unless we do a major overhaul

1. Everything is designed for a simple character or integer calculation. We need doubles. Changing all these variables and any special treatment they get, for example, shifts << and mallocs (size) and memcpy(), is a lot of work because they are so integrated(and cute).

2. The opengl is all over the place with switches here and there that are unnecessary and cumbersome. We need to consolidate the opengl activities. Also, it is possible/likely that the opengl is running inefficiently. His wireframe which is not a wireframe at all is an example.

3. His notion of saving memory by not maintaining the coordinates of the height points (which could also have been accomplished by storing them in a 2-d array instead af a 1-d) is an untenable situation for us for such things as collision detection and assigning objects to locations on the map. We need to explicitly know where everything is.

4. Imbedded deep in the code is the intermittant reversal of the conventional x,y,z order to x,z,y. An arduous task to fix.

If we could disentangle the useful ideas from these above mentioned drawbacks we would be much better off. After traipsing through the code for a couple of weeks now, I think it would take me the month of August to make it right. Quite honestly there are parts of his central ROAM code that still elude my comprehension. What I have done to this point is glue together a program that looks ok but which is really not expandable. I have pretty much worked within the constraints of his code. The upside of this delay is that we will know by tonight if we can maintain the speed while using real lighting and normals. So far I have added textures and a USGS map with no obvious deleterious affect on the rendering speed. So we might think of these two weeks as a time of experimentation to see if his ROAM version can work with the kind of data we will be using. So far I'm impressed.

That's the situation as I see it. Despite this slight delay, I don't see this as a disaster. After all, he handed a tested idea to us that would have taken a lot longer to have written from scratch. My proposal is to look at this code to see what we can salvage and begin a rewrite soon. Any other thoughts? Look at the code yourself and you will see that part of its beauty lies in its constraints.

Let me know what conclusions you come to.

joe

31 July 2001 : Shading Revisited

attached is a screen shot of the bill the cat mountain range with shading. The trouble is that when I travel through the landscape, just as the little lumps keep appearing and disappearing, so do little patches of shadows. This is distracting. Additionally, even with smooth shading you can see from the screen shot that the triangles are apparent in places. The patterns of the triangle patches underneath come through as shadows.

This may have something to do with my revisions, but it may also be an artifact of the roam code. Perhaps he realized this and that is why he chose not to use the normals for calculating the shading. In any case I will try to determine the cause. I'm going to experiment with changing the depth of levels to see if that has any affect.

I sent this attached screen shot to Patrick but wasn't sure if you all got it so I'm sending it again. I'm still not sure if my additions are causing the appearance of patterns of triangles showing through the texture.. which is very hard to see when I use this landsat satellite texture.. but I am now pretty well convinced that the disconcerting flashing on and off of shadows is the result of what happens when the roam technique changes its mind about how many triangles to break a patch into (as we walk along). So, when roam says redo a patch with a different constellation of triangles, bumps either grow or diminish. Naturally his leads to a change in the shading. Thus the shading gives emphasis to the fluctuations on the surface.

The only way to prevent this from happening is either to keep the bumps from fluctuating (which defeats the whole idea of ROAM) or to map the shading on the surface permanently (as he did in his demo). But this latter method will not allow us to move the sun at run time.

Even a re-write of ROAM for our specific purposes will not prevent this from happening.

John: Your machine must have a lot of memory (as mine has) but I was using far too much. I created ten megs or so that I never used by creating some huge arrays. I got rid of them tonight. Also, I can change one of the temporary arrays to a malloc which I can free up when the program starts.. it is a work area for the creation of the normals. That will give us more space. Maybe Pat's machine was overwhelmed with the amount of memory it needed and was using the cache. But that should be better now. I have not done the above mentioned malloc yet but it may not be necessary.

This texture is immense. It is 512 by 512 per patch so the total amount is big big or big^2

On the good news front (seeing as you think it looks good) I re-read the original paper that Turner wrote and I discovered how he thought this "popping" of terrain could be handled. He says he just drags out the pop over more frames.. He says it is called Geomorphing but I can see it is the same process we use everywhere in graphics, the old partition of one technique. He averages the point height in an unsplit triangle with the actual point height. It might work. I'll do some experiments with it. This would drag out the change from one shade to the next over a period of a few frames so it would not be so noticeable. Let me try it tonight to see what we get into.

Patrick. I am uploading a newer version of the program with all the extra memory removed to see if your machine can run it at a reasonable speed.

I just ran the program (the cleaned one) on my 32 meg mamory machine and the cache was working and it slowed down too much. I'll get rid of as much memory as I can to see if I can get it down to run on 32 megs. next message will have new version name to download.

sorry

joe

1 August 2001 : Details

I have been thinking about these little bumps appearing and disappearing. ROAM disease.

You have probably noticed that this program keeps popping the bumps up and down even if you don't move. This is much more distracting than when it happens as you move around. What I have done for similar situations in the past is set up a switch in the input function case statements so when the user moves or turns, a switch is set. Then in the idle function, test this switch to see if the user has moved. If he has, recalculate the surface, otherwise go directly to display. Not such a big deal right now. However, in the future when we have all kinds of things happening outside of the terrain generation we may need a series of these tests for various components of the model.

Looking ahead a little. Suppose we have someone walking along on this surface. Now we have to make some kind of calculation as to where his feet are so he won't be walking on air or a foot underground. Usually this calculation is straightforward, just put his weighted foot on the surface. But with this roam technique, the current surface beneath his feet would change depending on how far he gets away from the viewer and how much the viewer moves. Question. Will the walking person end up bouncing unnaturally? The theory is that the only time a surface is not subdivided is when the difference between the calculated and actual elevation is imperceptible to the viewer. I wonder if his corresponding vertical movements will share that imperceptibility or if his solitary profile will create a vibrating or bouncing image so he ends up walking with the gait of mister natural in a silent movie. If it came down to making a choice between having him (at a distance) vibrating up and down.. or having his feet slightly under ground I would choose the latter because it seems like it would be less noticeable. But this may be a non problem. We should probably wait and see what develops.

joe

2 August 2001 : USGS Maps

I have been using the 1 degree maps from USGS but there are some 15 minute and even 7.5 minute elevations available for alaska and the rest of the country. Here is the url for the 15 minute alaska elevation maps:

http://agdc.usgs.gov/data/usgs/geodata/dem/63K/demlist_M.html

and here is the main url for the alaska data site(this is different from the usgs site which maintains 1 degree DEMs:

http://agdc.usgs.gov/data/usgs/to_geo.html

these will give us much more "local" elevations which would make sense. The 1 degree maps are good for flyovers where you are moving fast over the terrain but we need more detailed local terrain. If I am doing my arithmetic right, 7.5 minute elevations are 8 times more precise than 1 degree elevations. which means we will get 8 elevation points to describe what is now described in a single point. That should smooth things out a lot.

If you download any of these elevation DEMs (that's what they call them Digital Elevation Maps) you may have a problem unzipping the gz file, if you use netscape. I was able to do it with Explorer. My version of netscape does not do it correctly and I cannot get rid of the gz even after it is "unzipped" but explorer leaves them in a proper zipped format that winzip can handle.

The reason why I am suggesting you take a look at these is because they are big text databases with lots of header data that we may find useful. On the 1 degree maps I know what most of the header information is.These smaller maps are similar.. numbers of elevation points in both directions and starting/ending lat/long, distance between elevation points. This is the kind of stuff. I am sure the people up in the usgs office on campus know what these numbers are if we can't figure it out. We will need these numbers when we attach the correct landsat or aerial photos to the elevations in order to line things up.

The current map size I have been using is 1024 by 1024 but we can use any of the 2^n by 2^n sizes as long as we make sure the number of triangle levels doesn't go too deep. We may have to bring in four of these smaller maps at a time and fit them together to get a good sized area.

Other data bases are available but I have not located them yet. For example the forest types overlays. These are gis and we could use them to determine where to put what kinds of trees/shrubs on the terrain.

eventually we would be better off pre-processing this geo data and using our own file formats to feed the main vr program. The overhead of working through their elevations and forest maps takes a lot of time (right now for example I calculate the normals before the run which takes time and makes the program more cumbersome.) If we just read these data in at run time it would be easier. We could provide the conversion programs to everyone so they could use standard usgs maps (I wonder what the canadian data looks like.)

Anyway, take a peek at the data files if you get any spare time.

joe

3 August 2001 : Yipes! I spaced the Friday get together.

After I worked all last night, a friend of mine called me and asked me to get some medical information for her from the web. So I stayed up until noon and then hit the sack, setting the alarm for 3pm which apparently did not occur on my clock today.. it just skipped over 3 o'clock.. maybe an Einsteinian space-time discontinuum event. Now there's an excuse even one of my miscreant students wouldn't stoop to using. However, a couple of years ago I did have a guy who told me he missed the mid term exam and half of the semester because he had "sympathetic pregnancy" for his girl friend who was with child. Unfortunately his ill fate was compounded by an "unsympathetic teacher." I aborted him from the class, thus preventing his new to-be-born sympathetic baby from having a CS101 flunky for a dad.

Texture musings. We are lucky that opengl allows us to change the dimensions of texture images to fit their 2^n by 2^m texture size requirements because I suspect that the elevation data and the satellite data are going to require some work to match. The elevation data comes in regular lat/long rectangles. The satellite data does not come the same way. It is based on what is under the satellite as it passes overhead, together with its field of view. Then there is the distortion caused by the spherical earth and the satellite's parallax. Perhaps if we choose pieces of land in smaller areas we will not have so much problem with the distortion. I have heard that there are GIS tools that will "fix" images so they lay flat. If we don't want to spend all our time making/using GIS tools to reconcile the images we better get pre-fixed images. I have a good friend who has an extensive GIS background and as soon as he gets back in town I will ask him what is possible. I believe that we can get overlays and all that in TIF format. These overlays will tell us things like forest type (so we can plant trees) and where the water is (so we can place lakes and streams)

So John, should we get together this week end? Do you want to connect up before Friday or just meet at the usual time next week. The only reason why I am not addressing everyone in the group is because Patrick I know you are out of it until you at least finish the 481 project, and Micah is mercurial. (this is a euphemism for a lazy, game playing, self-control lacking, sleep deprived, easily led, pizza eating, keyboard stomping, computer geek who was inadvertently placed on a planet with only 24 hours in a day for gaming.)

Let me know. The only 'urgent' business is to determine how much revision we need to do on this ROAM program and how much we can live with. In its present form I can work around things but that could be a false success. Another possibility is for all of us to take the basic program and do things to it in order to get familiar with its parts. Then, when we all feel confident about its anatomy, perhaps it would be easier to revise it. In an industrial setting this does not make so much sense, but at this stage for us I think it is more an educational/experience problem than an industrial one. The more we play around with this the more comfortable we will be making global changes. (no pun intended)

Just to get a benchmark I'll put the current (rudimentary) roam program on cd's for you with the essential ingredients:

1. Turner's ROAM
2. USGS input
3. texture input
4. non_windows openGL API

joe

5 August 2001 : Why the program keeps calculating

I have been studying the program to figure out the puzzling problem of why we keep getting these popping bumps even when we are still. Here is what I found out.

There are four variables involved in the "variance" process; gDesiredTris, gFrameVariance and TriVariance. The fourth variable that tells how many triangles we have created for the frame comes from GetNextTrinode() which simply keeps track of how many triangles have been used from a pool of triangles.

At the start of the program a goal of 10000 "desired" triangles per frame is set (gDesiredTris). The idea is to keep the program at a constant frame rate by fixing the number of triangles per frame. It also sets an "estimated" value of 50 for a variable called the gFrameVariance. This value will change during the operation of the program. gFrameVariance is the threshold value that the variance (TriVariance) of an elevation point is compared with to determine if a subdivision is necessary. So, in each frame, for every elevation point, a calculation is done where the variance (=difference between that elevation point and closest triangle midpoint) divided by the distance from the viewer produces a value called TriVariance. TriVariance is then compared with the gFrameVariance to determine if the triangle should be subdivided at this point. If the TriVariance is larger than gFrameVariance, subdivide. Otherwise do not subdivide.

While all this is going on, the program counts the number of triangles it uses per frame. At the end of the frame rendering it does the following.

Compares the actual triangle count GetNextTrinode() to the desired count (gDesiredTris). If they are not equal, the following calculation is performed:

gFrameVariance + = (GetNextTrinode() - gDesiredTris) / gDesiredTris;

The plan is to keep adjusting the original gFrameVariance estimate until GetNextTrinode() produces the 10000 triangles goal.

So we have a feed back loop. gFrameVariance controls the number of triangles and the number of triangles controls the gFrameVariance. This is why even when the viewer stops moving, the program continues to pop little bumps in and out of the surface. It is constantly trying to adjust the gFrameVariance to produce the desired 10000 triangles. After awhile the action slows to a stop because the number of triangles is 10000. But when you move or look around it has different patches to look at so it has to go through the adjustment again.

I don't know if this description makes easy reading or not. Sometimes it is better to just trace through code to see how it works than to have someone read it for you and try to describe it in english.

I may have mentioned this before, but the reason why the bumps are more obvious in my version of the program than his is because I am using real shading instead of shading that is incorporated into the texture map. So when my version pops a bump, that bump comes with shading.

So there it is. I can probably do a better job describing it in person than in email.

joe

9 August 2001 : New Roam Version online

I uploaded the most recent version with its changes and cludges and threw in all the opengl dll's etc for luck (you will probably have to dump the dll's if you want it to run on your machines but I put them there in case anyone else downloads it and doesn't have the dlls.

I made the program do some preliminary calculations of the terrain before it starts to display so it doesn't have a whole bunch of topography to do the first frame. Also, I told it not to do any bumps if the viewer is not moving or looking around. Slowly I am disentangling the maze of code.

I'm also going to put it onto a cd (complete) and also put the very original version from Turner there too in case you want to refer back to it.

What I've been thinking about lately is how to put the "geomorphing" that Turner mentions into the code. He says that this will reduce the bumps' intrusiveness. I think his theory is right. Maybe we can get the variations down to nearly imperceptible.

Let me know if you can't get this version to run. It is over three megs zipped by the way because I put everything I could think of into it.

This program runs on my 200 mhrtz 64 meg memory computer at home but it is not smooth and it takes a very very long time to do the preliminary normal calculations etc before anything comes onto the screen. It ran ok on that machine (and the one at work) only after I replaced my permanent work arrays with mallocs so I could free the memory before display time.

joe