Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 


Submitted by Aries, posted on October 27, 2000




Image Description, by Aries



This image is of an idea I had for terrain rendering using heightmaps. I'm not sure if this is used already. I would hope it is because it is so simple and works so fast. There is also limited overdraw (anything that is overdrawn wouldn't be worth culling out) and it lends itself VERY well to seamless, non popping LOD (I'll post separetly on this if anyone is interested). The image on the left shows a view of the heightmap (512x512). You start with a point (your current location #1) and then calculate points #2 and #3 based on HFOV and viewing distance. These three points form a triangle of heights on the heightmap to be rendered. Now for the easy part. Going through old programming books I came across triangle scan conversion. I thought this would apply very well to this situation. For you old school programmers, this is how you drew polygons to the screen before OpenGL and hardware rasterizers. Divide the triangle into a top and bottom triangle (green and blue - each has a perfectly horizontal side) and scan convert each triangle. Thats it, you can adjust (I use sliders) your viewing distance, HFOV, all kinds of stuff and watch it in action. It's kinda neat.

I'm positive this is commonplace as it seems so natural and easy so this likely won't impress anyone. The only downside is if you are high above the landscape and look down you can see missing polygons. I've fixed this with using a compensate factor which moves your location back and that reduces this problem.

If anyone is interested I can post another solution to this which shows off the very fast and accurate LOD, as well as a permanent solution to the above problem but it should be obvious extending what I've done here. The pics on the right are images of the rendered landscape. The polygon count is pretty high and it runs pretty well. I have a Celeron 300 and Geforce256. I can send a demo and put up a page if anyone wants to try their fps on a faster and better machine.

Again, I appologize if this idea is old and lame and no one is impressed, I've just never seen it done before. Seems to me a great way to speed up an engine and a lot quicker and more accurate than quadtrees (and the such).

You can't read it in the pictures but its about 10 fps for 181,216 triangles. I have also done zero optimizations so take that into consideration. I am wanting to increase the map size, but just scaling everything up doesn't seem to work as it looks the exact same. Any suggestions (the polygons are very small)?

Aries


[prev]
Image of the Day Gallery
www.flipcode.com

[next]

 
Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Khrob

October 27, 2000, 12:14 PM

Please post the other solution!

Fine work indeed!

 
Luke Hodorowicz

October 27, 2000, 12:18 PM

Yup, it has been done before. =)
I've done it, I saw it in a landscape demo with source when software rendering was all the rage. I think I got it off of x2ftp.oulu.fi. (that ftp site is still up!) and I have a friend who also came up with it totally seperate from me. It's a damn good idea.

The idea may be old, but certainly not lame.

Nice work. Keep it up.

-Luke

 
Erik Greenwald

October 27, 2000, 12:28 PM

The screenshots look sweet, I'd like to see the demo :) Do you have any issues with releasing source and/or linux/fbsd binaries?

For increasing map size... do you also want to increase viewing range? I don't see why simple scaling up the map size wouldn't work if you don't want viewing distance to change? Why would it look any different if you want to increase the map size and not the view size? Maybe I'm misreading something *shrug* I do that quite frequently :) I'm interested in seeing a runtime demo of your technique

-Erik [http://math.smsu.edu/~br0ke/]

 
Aries

October 27, 2000, 12:35 PM

The other algorithm is kinda neat. If this is also around someone please let me know.

Travel along the lines from points 3 - 1 and 2 - 1, heading back towards point one. Use Bresenhams algo and the lines should be the same length. On each step towards point 1, draw a line from your currect spot on the line 3-1 to the current spot on the line 2-1. Use Bresenham for this too.

The lines should all match up perfectly if you have everything set up right. You will accomplish the same as the algo I mentioned above, but with a couple advantages, and one disadvantage.

First the disadvantage: You lose the ability to draw in strips because your data won't line up in horizontal strips (triangle scan conversion converts the triangles into horiontal lines -- it made drawing to your vga card faster as you could use long word writes).

Advantages:

1) you can solve the problem of losing polygons below you when you look down. Simply break point 1 into two points and space them apart. Your viewing trianlge becomes a cone shaped quad.

2) LOD - Since you are starting with the farthest line, you kow that each subsequent line is one step closer to your viewpoint. All points on each line are the same distance away. Simple LOD allows you to join points to create triangles from the points one lines n and n + x. Then skip down x points on the 3-1 and 2-1 lines and draw the next. You can skip 5, 4, 3, 2 lines or whatever to achieve smooth LOD. I hope that wasn't too confusing and made sense.

Please let me know if this has been used as well.

Aries

 
Mahogne

October 27, 2000, 12:35 PM

You can your input map, flip vertically, horizontally, and vert-horz to up your map size to a seamless 1024x1024. Everything will be mirrored, but at least its a start.

BTW - Looks pretty good.

 
Aries

October 27, 2000, 12:37 PM

I'll post this here as well

The other algorithm is kinda neat. If this is also around someone please let me know.

Travel along the lines from points 3 - 1 and 2 - 1, heading back towards point one. Use Bresenhams algo and the lines should be the same length. On each step towards point 1, draw a line from your currect spot on the line 3-1 to the current spot on the line 2-1. Use Bresenham for this too.

The lines should all match up perfectly if you have everything set up right. You will accomplish the same as the algo I mentioned above, but with a couple advantages, and one disadvantage.

First the disadvantage: You lose the ability to draw in strips because your data won't line up in horizontal strips (triangle scan conversion converts the triangles into horiontal lines -- it made drawing to your vga card faster as you could use long word writes).

Advantages:

1) you can solve the problem of losing polygons below you when you look down. Simply break point 1 into two points and space them apart. Your viewing trianlge becomes a cone shaped quad.

2) LOD - Since you are starting with the farthest line, you kow that each subsequent line is one step closer to your viewpoint. All points on each line are the same distance away. Simple LOD allows you to join points to create triangles from the points one lines n and n + x. Then skip down x points on the 3-1 and 2-1 lines and draw the next. You can skip 5, 4, 3, 2 lines or whatever to achieve smooth LOD. I hope that wasn't too confusing and made sense.

Please let me know if this has been used as well.

Aries

 
Max

October 27, 2000, 01:04 PM

This idea is useful for other purposes as well, like if you are doing a 3D version of an old school tile based games. Say for instance the tiles (which are drawn using 3D models) are arranged on a plane and the camera hovers above the plane pointed down at it. You can find the visible tiles by computing the quadrilatel slice of the view frustum that intersects the plane and then scan converting it.

Max

 
Aries

October 27, 2000, 01:26 PM

This idea is useful for other purposes as well, like if you are doing a 3D version of an old school tile based games. Say for instance the tiles (which are drawn using 3D models) are arranged on a plane and the camera hovers above the plane pointed down at it. You can find the visible tiles by computing the quadrilatel slice of the view frustum that intersects the plane and then scan converting it.

Ya I was thinking that as well, using tiles to create a larger landscape, then renderingthe tiles with display lists. Whatever it coems down too, speed it the ultimate goal. I believe that landscapes are great for games (like flying games) but shouldn't always be the focus. The faster the terrain can be rendered, the more time to fit more objects as possible, and make the game more exciting.

Another nifty advantage to this system would be the placement of objects. Storing the heightmap as an int (or even short) would give you extra bits to store the object id of an object hovering above that piece of landscape. This allows you to render your objects (which, when located would contain the exact co-ords) with your terrain, without needing an extra step to search for visible objects.

Also all objects rendered would be visible (unless obstructed by the terrain).

Aries

 
Allen Chang

October 27, 2000, 02:59 PM

Yes, I have done this before (though my approach wasn't so elaborate, so maybe yours
doesn't exhibit any of the problems mine did); actually almost all the old-school voxel
engines were based on this. Also, what do you mean when you are
viewing down from above you see missing polygons? Perhaps a more careful scanning
algorithm for traversing the "viewing triangle's" sides would ensure that every potentially
visible triangle is rendered.

The LOD idea with Brensham's sounds very neat.

The main problem I had with this method was that it didn't work as nicely for me when
I wanted to view at a near-horizontal angle. Then, for instance, the viewing triangle
would have to clip at some arbitrary distance, which was slow and didn't look very nice;
of course, the LOD you described very likely might fix this.

Allen

 
mice

October 27, 2000, 03:27 PM


"...without needing an extra step to search for visible objects."

And combining this with my tile-engine and storing both the object id as well as the object coord offset from tile!
Could be the best tip I've heard for years!

Thanks Aries!
((mice

 
Aries

October 27, 2000, 04:05 PM

Hehe, no problem. Glad to help. Jopefully I'll see a screenshot of that soon :]

 
Garett Bass

October 27, 2000, 04:59 PM

If you calculate the triangle (or it could even be a quadrilateral) as an intersection of the frustum and the ground plane you should be include all the tris in view even if you're high above the terrain looking down.

In fact, this solution creates a more accurate inclusion region when looking down on terrain, allowing you to look straight down from above, which would create a rectangular inclusion rather than a triangle.

Scan conversion is a good technique, and tho it's probably not a bottleneck, there are many well documented optimizations.

I'd like to hear about your LOD ideas too.

Cheers.

 
Canabinol

October 27, 2000, 05:41 PM

Nice job, Aries...often the most simple approach to a problem is the best!

To get around the problem of having to render the mesh as discreet triangles (as opposed to using strips), why not divide the mesh data into 16x16 vertice "tiles", stored individually. Then display each tile in its entirety as a vertex array or series of Triangle Strips (perhaps compiled display lists would be better?) whenever any triangle in the tile is potentially visible as defined by Bresenham (admittedly may have to increase the FOV tho).

This would increase the speed of the Bresenham pvs calculation (as it would run at a lower "resolution"), and in theory is faster at render time because you can use a series of vertex array display calls, triangle strips or Display List calls for rendering instead of having to render individual GL_TRIANGLES.

The only drawback is the LOD would also work on a tile basis and perhaps result in more obvious popup if implemented at that level. I guess it's a balance between physically drawing more triangles against the render efficiency benefits of arrays, strips and lists.

Just my two cents!

Cana.

 
fluffy

October 27, 2000, 06:28 PM

Technically, you have just described a naive version of the classic mechanism of rendering a heightfield. :)

 
malkia/eastern.analog

October 28, 2000, 03:23 AM

I want demo of that!
please....

 
This thread contains 15 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.