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

Submitted by Darshan Patil, posted on July 13, 2001

Image Description, by Darshan Patil

These are screenshots from a terrain engine I am working on.

I started with the ROAM algorithm but found the vertex popping a little irritating and discarded it.

This is a simple quadtree (ish) algorithm (no LOD whatsoever) I implemented in about 2 days.

I have used something I like to call coherent frustum culling. The lighting is precalculated and the shadowmap is ultra low-res with 1 pixel/sample.

I havent measured the fps but it feels ok on my Celeron 400 /64MB/i810.

I know the texturing is awful (its a texture tiled on the landscape). I just put it together to send my first iotd ;)

I am working on a texture synthesizer at the moment and am toying with the idea of using the ROAM algo to create static optimal meshes.

--Darshan Patil

Image of the Day Gallery


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.

July 13, 2001, 04:22 PM

I'm only posting for the purpose of being first :)

Graphics look good though.

- Lionel Brits


July 13, 2001, 04:27 PM

I love Betelgeuse because it is squidgy. Purdy Pictures.


July 13, 2001, 05:27 PM

Posting on purpose of being 2 (replies cant be considered as posts)


July 13, 2001, 05:40 PM

Anyone else see the screeming face on the right side of the gray pic?
or is it just my sleepy eyes ;)..


July 13, 2001, 05:44 PM

This terrain is really nice
but actually its not terrain, its just small piece of it, or most likely rock.
I see that view is not too distant. Do you really need quadtree for this terrain ? Also what it means OK FPS.. is it so hard to implement frame counter.
that's all folks


July 13, 2001, 05:45 PM

Of course he's screaming. He's got that big spear in his shoulder.


July 13, 2001, 05:47 PM

Hahahaha that's funny! : )


July 13, 2001, 05:48 PM

hehe.. Ooh! didnt see that one :)..


July 13, 2001, 05:49 PM

No I cant see any ghosts. Prolly u are desperate from work or something else, and your visions can say a lot about it. I suppose u need rest, or u have too much work or problems.
Dont take it personally and forget what I've said. I suppose we all are annonymous here.


July 13, 2001, 05:50 PM

alot of work.. :(..

Rectilinear Cat

July 13, 2001, 05:53 PM

Stupid question, but I'm sort of new to terrain rendering. Does the terrain lighting come as a result of the quadtree or anything, or is there some other algorithm involved. What is it?


July 13, 2001, 06:00 PM

Is anyone else annoyed by that huge sig? Count this as 1 vote for you to trim it down.


July 13, 2001, 06:03 PM

The blurred shadows make the images seem like underwater shots. Could you explain "coherent frustum culling" please.

BTW: Is there any technique which combines quadtree/octree and LoD?



July 13, 2001, 06:11 PM

Quadtree is used to do very fast culling. You devide the scene into four parts (2x2) and if the polygon count inside one of the parts exceeds a limit you divide it again (and again...). Culling gets fast because you start at the top and you check only those parts where the parent was neither a) completely visibible nor b) completely invisible. In case a you can draw that part and all the parts it consists of. In case b you simply skip it. (Just to show that I do know something :)))
Those shadows seem like generated by the height difference between vertices but it might be something else.


Mike Taylor

July 13, 2001, 06:28 PM

Well, quadtrees/octrees can be a form of LOD in and of themselves. Each node of the quadtree can have its own LOD calculated, and each node has a set of polygons in it. The higher up nodes (low LOD) have very large polygons, and are only rendered if they are very far away. As you get closer, you move down the tree to lower nodes, which have smaller, more detailed polys in them. Finally, when you hit a leaf node, you are drawing straight from the heightmap. You can augment this by biasing the split level of each node based on the number of triangles in it, or even by the curvature of the node. This is an EXTREMELY good method of handling terrains, because the LOD doesn't alter vertex positions, so it can be very hardware friendly. It can even support VIPMs (see DirtyPunk's column).

If you want more info on this, check for an article a while back on adaptive quadtrees. They explain far better than I do. After that, read up on GeoMipmapping here at Flipcode, it is kinda a neat extension to this. The only real issue I have with pure quadtrees is that they are ultimately tied to heightmaps, which I find limiting. Another beautiful property of quadtrees is that the leaf nodes can be a different structure than the rest of the tree, say, by using splines or subdiv surfaces at the leaf nodes for that last bit of super detail...

Good luck with your researching

-Mike Taylor


July 13, 2001, 07:04 PM

If most people will be annoyed I cut it off


July 13, 2001, 07:04 PM

"I am working on a texture synthesizer at the moment and am toying with the idea of using the ROAM algo to create static optimal meshes."

Paul Heckbert and Michael Garland wrote a nice survey paper on LOD technqiues which should be very helpful if you decide to investigate simplifying the landscape as a preprocessing step.



July 13, 2001, 08:30 PM

Because I have no diea what Quad trees are or what and LOD does, I can say "it looks great!" Nice work!

Peter Mackay

July 13, 2001, 09:47 PM

I'll vote too.


July 13, 2001, 11:01 PM

vote...a small quote would be nice...


July 13, 2001, 11:08 PM

I like the blured shadow effect...looks better imho. That upper left hand shot looks great, the haze reminds me of S. California :)

That is definately a face!


July 14, 2001, 05:04 AM

Ok perhaps im just mad too ... but i see it :)

Darshan Patil

July 14, 2001, 05:49 AM

Rectilinear Cat:
The lighting is precalculated. I've used a simple ray-tracing algorithm.

Well coherent frustum culling works like this --
Since when you move through terrain, divided into quads, any new quad that is visible will be a neighbour of a quad that was visible in the last frame. So instead of testing every quad for visibility, you just test the currently visible quads and their neighbours. This is useful if your terrain data is huge.

Yes, you could combine quadtrees with LOD. What you do is use quadtrees for a rough cull and render the quads using LOD techniques.

You're right. I should implement a frame-counter. I am busy with other stuff but will do that ASAP.

Brebion flavien

July 14, 2001, 07:10 AM

> Since when you move through terrain, divided into quads, any new quad that is visible will be a neighbour of a quad that was visible in the last frame.

Hum, it's not necessarily true, if you have quads that are relatively little, or if you turn the head quickly....

Hannu K.

July 14, 2001, 07:14 AM

I vote too! Better make that sig small, baxton


July 14, 2001, 08:01 AM

considering its a tiled texture its pretty damn good :]


July 14, 2001, 08:15 AM

Thanks for the info. Interesting stuff.
I don't get why quadtree should be limited to heightmaps but maybe my understanding of quadtree is simply wrong. I thought one could put any form of geometry into the leaf nodes. By doing this of course the approach in the gamasutra article ( might not work since the data could not be recursively (and dynamicaly) divided into squares. In the article a heightmap is used because one can avoid t-junctions when using the division scheme mentioned there. I'm a bit confused now (and I guess my English gets worse then as well :))) ???



July 14, 2001, 08:24 AM

Sorry Baxton! My first post had to be a vote against your post message.


July 14, 2001, 09:38 AM

Oki oki
No need to vote further ;)


July 14, 2001, 09:59 AM

i'm getting a bit tired of everyone showing off his or her landscape engine

This thread contains 44 messages.
First Previous ( To view more messages, select a page: 0 1 ... out of 1) Next Last
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.