🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Data Structures + Octrees
Author
I''ve written a program that reads a heightmap and a texture and displays it as a simple texture-mapped 3d terrain.
Right now, I am just drawing everything(as GL_TRIANGLES or GL_TRIANGLE_STRIPs, either one). I have a 2d array that holds the height values, ie vertices[x][y]. When drawing I just have a for loop, containing another for loop. The loops give me the X and Z vertex values, and I use these also to access the Y values from the height array.
This works fine, except it''s painfully slow.
So I''ve decided to use Octrees for visibility determination(plus other stuff later on).
However, I am at a loss as to how I should store my vertex values for the terrain and also in the future I would like to have other objects as well(trees, buildings, etc).
So can anyone suggest a good structure to store my world data(I still want to load terrain from a heightmap, I mean after it''s loaded), that could be easily used in an octree algorithm.
Thanks,
Jonathan
Hi,
For your terrain-engine, make use of Quad-Patch or ROAM. The Quad-Patch algo. is the something as Octree except is for a plane (2d).
So, what you need to do is pretty simple.
My algo make use of recursion ...
You can probably use Iterative function too, but i dont see the necessity, due to to the fact that a maximum recursion of 7,9 do something really Cool.
Here a pseudo-code:
So, using this, you just compute what you need to.
I've already impletent this in my 3d Engine. I get over 60FPS with a 30-35K polygons landscape , on a PIII 500MHz.
Two thing, a Landscape cannot make use of Octree, Octree are very efficent for indoor environment only.
You're better using Gray-Scaled Bitmap for your heightmap, use 8bit, maybe 16bit for it. Then use some sort of Textures IDs, using normal 256x256x24bits Texture, to map your LandScape.
Happy Coding,
LowRad
Edited by - LowRad on July 31, 2000 1:25:49 PM
For your terrain-engine, make use of Quad-Patch or ROAM. The Quad-Patch algo. is the something as Octree except is for a plane (2d).
So, what you need to do is pretty simple.
My algo make use of recursion ...
You can probably use Iterative function too, but i dont see the necessity, due to to the fact that a maximum recursion of 7,9 do something really Cool.
Here a pseudo-code:
CreatePatch (CVecteur2d *View, float x1, float y1, float x2, float y2){ if (this patch is visible) // if your in it or if it's in your fov { if (this patch need more precision) // LOD (Level of Detail) { call Create Patch 4x time, to divide your current patch into 4 smaller one } else { Split your square into 2 triangle, and draw them } }} So, using this, you just compute what you need to.
I've already impletent this in my 3d Engine. I get over 60FPS with a 30-35K polygons landscape , on a PIII 500MHz.
Two thing, a Landscape cannot make use of Octree, Octree are very efficent for indoor environment only.
You're better using Gray-Scaled Bitmap for your heightmap, use 8bit, maybe 16bit for it. Then use some sort of Textures IDs, using normal 256x256x24bits Texture, to map your LandScape.
Happy Coding,
LowRad
Edited by - LowRad on July 31, 2000 1:25:49 PM
Author
The engine is not going to be an outdoor terrain-only engine. There will be many buildings with indoor areas.
Therefore, Octrees are the ideal solution.
I am sorry if I was not clear on this before.
Therefore, Octrees are the ideal solution.
I am sorry if I was not clear on this before.
Hi Dinotrack,
I dont say : "Dont use OCTREES" ...
I mean : Use Quad-Patch for your landscape, and use Octree for the buildings on it, the indoor part (caverns, inside building, ...)
More then that, what i''ve do is : I use quad-patch for my landscape, and i use Octree with Portals for anything else which is static.
And i treat moving object, (players, monsters, items) in a different list.
LowRad
I dont say : "Dont use OCTREES" ...
I mean : Use Quad-Patch for your landscape, and use Octree for the buildings on it, the indoor part (caverns, inside building, ...)
More then that, what i''ve do is : I use quad-patch for my landscape, and i use Octree with Portals for anything else which is static.
And i treat moving object, (players, monsters, items) in a different list.
LowRad
hmmmm, 60 fps with 35k triangles?
I did a test, I draw 4000 untextured and unlit triangles (using a vertex array), no model or nothing, just 4000 small triangles.
I got 8 fps with a celeron 550 with a matrox G400... what''s wrong? don''t tell me it''s a software fallback cause it isn''t. And quake3 works fine with 100 fps. What''s wrong? Any ideas?
I did a test, I draw 4000 untextured and unlit triangles (using a vertex array), no model or nothing, just 4000 small triangles.
I got 8 fps with a celeron 550 with a matrox G400... what''s wrong? don''t tell me it''s a software fallback cause it isn''t. And quake3 works fine with 100 fps. What''s wrong? Any ideas?
im sure he means 35000 polys in the lanscape , not 35000 drawn on the screen at once.
though 4000 tris @ 8 fps aint great
i do about 10000 textured + lit tris @ 20 fps 1024x768x16 on a celeron433 with a vanta
Edited by - zedzeek on July 31, 2000 7:20:34 PM
though 4000 tris @ 8 fps aint great
i do about 10000 textured + lit tris @ 20 fps 1024x768x16 on a celeron433 with a vanta
Edited by - zedzeek on July 31, 2000 7:20:34 PM
Author
Okay, I think I phrased my original question wrong.
So I''ll give it another go.
First of all, forget about Octrees, those are not important at the moment.
I''m not at the computer with the code right now, so I''ll just sorta summarize the basic drawing routine.
As you can see, I calculate the x and z coords as I''m rendering basically. And heightmap[x][z] is just an array of heights obviously.
I know this is very inefficient.
However, I don''t really care about efficiency at the moment.
The problem though, I don''t know how I could store the data(as triangles) before that main drawing loop.
I tried all sorts of structures, but that didn''t seem to work.
I would like it to be able to be easily drawn, possibly as a vertex array? I don''t want to use a display list, because I need the vertex/triangle data available for other functions.
So I''ll give it another go.
First of all, forget about Octrees, those are not important at the moment.
I''m not at the computer with the code right now, so I''ll just sorta summarize the basic drawing routine.
glBegin(GL_TRIANGLES);for(x=0;x<WIDTH;x++){ for(z=0;z<HEIGHT;z++) { . .//I actually calculate tex coords here glTexCoords2f(u,v); glVertex3f(x, heightmap[x][z], z); glTexCoords2f(u,v); glVertex3f(x, heightmap[x][z+1], z+1); ...etc //the rest of the gl vertex and texture calls }}glEnd(); As you can see, I calculate the x and z coords as I''m rendering basically. And heightmap[x][z] is just an array of heights obviously.
I know this is very inefficient.
However, I don''t really care about efficiency at the moment.
The problem though, I don''t know how I could store the data(as triangles) before that main drawing loop.
I tried all sorts of structures, but that didn''t seem to work.
I would like it to be able to be easily drawn, possibly as a vertex array? I don''t want to use a display list, because I need the vertex/triangle data available for other functions.
if youre doing it so use gl_triangle_strip it should render ±25% quicker
for(x=0;x<WIDTH;x++){ glBegin(GL_TRIANGLE_STRIP); for(z=0;z<HEIGHT;z++) { glTexCoords2f(u,v); glVertex3f(x, heightmap[x][z], z); glTexCoords2f(u,v); glVertex3f(x, heightmap[x][z+1]; } glEnd();}
Author
Why is everyone missing the point of my question?
I know how to render it as a gl_triangle_strip, and it is a bit faster. However, I want to store the triangle data so other functions can use it.
Basically I would like to know how I could put the triangles into an array.
I can''t figure out how, since I''m already in a double for loop, I don''t know how I can increment a triangle array for each of the vertices.
I know how to render it as a gl_triangle_strip, and it is a bit faster. However, I want to store the triangle data so other functions can use it.
Basically I would like to know how I could put the triangles into an array.
I can''t figure out how, since I''m already in a double for loop, I don''t know how I can increment a triangle array for each of the vertices.
sorry mate didnt read your whole question
u want someit like this perhaps
this is a struct i use which contains 4 quads / 8 triangles of the landscape
Terrain world[worldwidth][worldheight];
u want someit like this perhaps
struct Terrain { UINT32 texture; bool has_shadow; UINT32 shadowTexture; VECTOR v1,v2,v3,v4,v5,v6,v7,v8,v9; // the nine vertices of the terrain VECTOR n1,n2,n3,n4,n5,n6,n7,n8,n9; // normals Vec2 t1,t2,t3,t4,t5,t6,t7,t8,t9; // texture coords int res; // 0 nodraw others are 1,2,3,4 void draw(void);}; this is a struct i use which contains 4 quads / 8 triangles of the landscape
Terrain world[worldwidth][worldheight];
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
