Sign in to follow this  

Vertices, Triangles, Height-map and an Octree Question

This topic is 4840 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

1: How should I store my world? as Vector3D vertices? as Triangles( 3 Vector3D points )with a texture Id, etc ? 2: What free leveleditors are out there? ( A tutorial link how to load the map, please - not a bsp map, I am using an octree) 3: How can I calculate the Triangles from a heightmap? (.raw) This is our height-map: 20 20 20 20 20 20 20 95 200 200 95 20 20 95 255 255 95 20 20 95 255 255 95 20 20 95 200 200 95 20 20 20 20 20 20 20 What now? How can I "connect" the triangles to each other?

 Vector3D vertices = new Vector3D[ (m_Size*m_Size)*3 ];
 for( int z = 0; z < m_Size; ++z )
 {
    for( int x = 0; x < m_Size; ++x )
    {
       const int index = ( z*m_Size+x );
       // what now? :3
    }
 }


4: What should I store in the endnodes of an octree? Vector3D* vertices ? Triangles* tris? Thanks in advance for any replies!

Share this post


Link to post
Share on other sites
1. Store your stuff in anyway that will make loading it more convienient. I store my maps in an XML file that has a vertex list, and a triangle list that indexes the vertex list.
2. I personally use 3ds max. I would recommend gmax, worldcraft (a.k.a hammer), or blender (I tried it but didn't like it, but that doesn't mean you won't)
3. Firstly, your code will quite simply crash horribly. Take a closer look at it and see if you can figure it out. Your algorithm should look something like this:

for(every height value)
{
vertex 1 = current height value;
vertex 2 = height value below it;
vertex 3 = height value to the right;
vertex 4 = height value below vertex 3;
triangle1 = new triangle(vertex1, vertex2, vertex3);
triangle2 = new triangle(vertex2, vertex3, vertex4);
}


just dont forget to "skip" values at edges
4. You can store verticies, triangles, meshes, entities, collision data, and so on and so on. Octrees are used for spatial sorting of any data. Simply store what YOU need to use. (In your case I would say triangles.) For heightmaps, I recommend that you use quadtrees, then move to octrees when you are more comfortable with the concept.

Share this post


Link to post
Share on other sites
Oh, thank you for your answers!




[qoute]
I personally use 3ds max. I would recommend gmax, worldcraft (a.k.a hammer), or blender (I tried it but didn't like it, but that doesn't mean you won't)
[/qoute]
But they are not free? (worldcraft is?) Do you know tutorials that explain how I can load the maps?





How can I get the data one up/down? And is this one right: ? :|

// 1D array
unsigned short* height_data = getDataFromRaw( filename, height_map_size );

std::vector<Triangle> tris;

for( int z = 0; z < height_map_size; ++z )
{
for( int x = 0; x < height_map_size; ++x )
{
const int index = ( z*height_map_size + x );

const float vertex1 = data[index];
const float vertex2 = data[index]; // what here? hmm?

float vertex3;
if( index + 1 >= height_map_size )
vertex3 = data[index];
else
vertex3 = data[index+1];

const float vertex4 = data[index]; // what here? hmm?

tris.push_back( triangle( vertex1, vertex2, vertex3 ));
tris.push_back( triangle( vertex2, vertex3, vertex4 ));
}
}







raw load function:

// Raw Loader ( 8-bit RAW Files Only )
unsigned short* LoadRaw( const char* filename, int &Size)
{
// load RAW file
FILE* pFile;
pFile = fopen( filename, "rb" );
if(!pFile) return 0;

// calculate dimensions of heightmap
fseek (pFile , 0 , SEEK_END);
Size = (int)sqrt(ftell(pFile)/2);
rewind(pFile);

// allocate memory
unsigned short *data = new unsigned short[Size*Size];
if(!data) return 0;

// read in data
fread(data, 2, Size*Size, pFile);

if(Size%2 != 0) return data;


unsigned short *data2 = new unsigned short[(Size+1)*(Size+1)];
memset(data2, 0, (Size+1)*(Size+1));


int i(0), j(0);
for( i = 0; i < Size; ++i)
{
for( j = 0; j < Size; ++j)
{
data2[i*(Size+1)+j] = data[i*Size+j];
}
}

delete [] data;
Size++;

// close file
fclose(pFile);

// return data
return data2;
}



Thank you again! :)

[Edited by - rakoon2 on September 12, 2004 2:10:24 PM]

Share this post


Link to post
Share on other sites
I have a question:
what are the x and Z values for:
vertex 1 = current height value;
vertex 2 = height value below it;
vertex 3 = height value to the right;
vertex 4 = height value below vertex 3;
? =3

Thank you! :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Deebo
1. Store your stuff in anyway that will make loading it more convienient. I store my maps in an XML file that has a vertex list, and a triangle list that indexes the vertex list.
2. I personally use 3ds max. I would recommend gmax, worldcraft (a.k.a hammer), or blender (I tried it but didn't like it, but that doesn't mean you won't)
3. Firstly, your code will quite simply crash horribly. Take a closer look at it and see if you can figure it out. Your algorithm should look something like this:
*** Source Snippet Removed ***
just dont forget to "skip" values at edges
4. You can store verticies, triangles, meshes, entities, collision data, and so on and so on. Octrees are used for spatial sorting of any data. Simply store what YOU need to use. (In your case I would say triangles.) For heightmaps, I recommend that you use quadtrees, then move to octrees when you are more comfortable with the concept.


i just want to node something about the quadtree/octree thing

in my engine i give the mapper the possibility to choose one of these culling methods,
why?
octrees are not very suitable for vast outdoor maps
you can compare them with 3d textures the iterations to check each node might consume more performance than they win

e.g. if i divide my map into a quadtree i get around 1300 nodes approximately with a octree i get around 32000 nodes

so octrees should only be your choice when have cubic like maps with several detailed floors
otherwise id suggest you use quadtrees

Share this post


Link to post
Share on other sites
OH, yes i see.. My scene with 50000 vertices gives me 15 fps...!
(athlon 1600 XP+, geforce ti 4200 ) :-/ DO you know a quad tree tutorial? I'll try to make it on my own.. but let's see :)

One more question how much Subdivisions should I let the tree make? And what about "maxTrianglesInNode"?


::edit:: Just tested it: It's faster if I not use the octree!( on single node with all vertices ) ..... !! :( :( :( ): ): ): !!
But maybe it's because that my height map isn't right! ( it isn't.. )





I need help with my highmap loader! :3 Please take a look:
http://members.chello.at/ennemoser/damn_height_map.jpg

The triangles are too big! And the right side is buggy too! ( ok.. ) It doesn't look like the terrain I made. :[


// I know most is wrong, so please help me! :|

unsigned short* data = LoadRaw( filename, m_Size );
if(!data)
{
LOG << "Couldn't load map " << filename << ENDL;
return false;
}
std::vector< Triangle > tris;
const float high_manipulator( (255.0f/(1<<16)) );
const float cell_size = 10;


int index(0);

for( int z = 0; z < m_Size; ++z )
{
for( int x = 0; x < m_Size; ++x )
{

/* START V.*/
index = (z*m_Size + x);
Vector3D vec1( x, data[ index ] * high_manipulator, z );


/* ONE DOWN*/
if( (z*m_Size + x + m_Size) > m_Size*m_Size )
{
// not correct:
index = z*m_Size + x + ((z*m_Size + x + m_Size) - m_Size*m_Size);
}
else
index = (z*m_Size + x + m_Size);

Vector3D vec2( x, data[ index ] * high_manipulator, z + cell_size );



/* ONE RIGHT*/ // not correct?
if( ( z*m_Size + x + 1 ) > m_Size )
{
index = (m_Size-1);
}
else
index = (z*m_Size + x + 1);

Vector3D vec3( x + cell_size, data[ index ] * high_manipulator, z );


/* ONE DOWN "FROM THE RIGHT" */ // not correct:
if( ( z*m_Size + x + m_Size + 1 ) >= m_Size + 1 )
index = (m_Size-1)*(m_Size-1);
else
index = ( z*m_Size + x + m_Size + 1 );

Vector3D vec4( x + cell_size, data[ index ] * high_manipulator, z + cell_size );




tris.push_back( Triangle( vec1, vec2, vec3 ) );
tris.push_back( Triangle( vec2, vec3, vec4 ) );

}
}


Share this post


Link to post
Share on other sites
rakoon2, gmax is the free version of 3ds max (at least the last I heard). The height map value is your y-axis, and the heightmap coordinates should be your x and z axis.

for(int i = 0; i < (m_iHeight - 1); i++)
{
for(int j = 0; j < (m_iWidth - 1); j++)
{
vertex1 = m_pHeightmap[(i * m_iWidth) + j]; // current value
vertex2 = m_pHeightmap[(i * m_iWidth) + (j + 1)]; // one to the right
vertex3 = m_pHeightmap[((i + 1) * m_iWidth) + j]; // one below
vertex4 = m_pHeightmap[((i + 1) * m_iWidth) + (j + 1)]; // the diagonal one
// make triangles from verticies here
}
}

Share this post


Link to post
Share on other sites
When doing spatial partitioning of a heightmap, make sure that you use a heightmap with a n^2+1 by n^2+1 resolution. For example, 257x257, 513x513, 1025x1025. Now, if you split the quadtree/octree node in the middle, there will be an equal amount of vertices on both sides.

The errors in the image you posted are due to invalid vertex indices. You're trying to access vertices that aren't there.

Here's some source code for how you would fill the index buffer:

// Fill the index buffer:
// Create a triangle like this:
//
// v1 __ v3 __
// | /| /| /|
// |/_|/_|/_|
// v2 v4

numIndex = (Size - 1) * (Size - 1) * 6;
Index = new unsigned int[numIndex];

Counter = 0;
for (int x = 0; x < (Size - 1); ++x) {
for (int y = 0; y < (Size - 1); ++y) {
Index[Counter++] = x + y * Size; // v1
Index[Counter++] = x + (y + 1) * Size; // v2
Index[Counter++] = (x + 1) + y * Size; // v3

Index[Counter++] = (x + 1) + y * Size; // v3
Index[Counter++] = x + (y + 1) * Size; // v2
Index[Counter++] = (x + 1) + (y + 1) * Size; // v4
}
}





[Edit]Fixed diagram in the source[/Edit]

Share this post


Link to post
Share on other sites

This topic is 4840 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this