# Vertices, Triangles, Height-map and an Octree Question

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

## 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 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 on other sites

[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 arrayunsigned 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 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 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 on other sites
Quote:
 Original post by Deebo1. 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 edges4. 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 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 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 valuevertex2 = m_pHeightmap[(i * m_iWidth) + (j + 1)]; // one to the rightvertex3 = m_pHeightmap[((i + 1) * m_iWidth) + j]; // one belowvertex4 = m_pHeightmap[((i + 1) * m_iWidth) + (j + 1)]; // the diagonal one// make triangles from verticies here}}

##### 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		}	}

Fixed diagram in the source[/Edit]

1. 1
Rutin
37
2. 2
3. 3
4. 4
5. 5

• 11
• 10
• 13
• 104
• 11
• ### Forum Statistics

• Total Topics
632978
• Total Posts
3009681
• ### Who's Online (See full list)

There are no registered users currently online

×