Good example for extracting Heightfield vertices/triangles?

[KungFooMasta]

My question isn't recast specific, but I'm sure a lot of recast users
have solved this problem. I'm using Ogre as my rendering library, and
the Terrain add on has an API that gives me the height data of the
terrain:

/** Get a pointer to all the height data for this terrain.
@remarks
The height data is in world coordinates, relative to the position
of the terrain.
@par
This pointer is not const, so you can update the height data if you
wish. However, changes will not be propagated until you call
Terrain::dirty or Terrain::dirtyRect.
*/
float* getHeightData() const;

/// Get the size of the terrain in vertices along one side
uint16 getSize() const;

/// Get the size of the terrain in world units
Real getWorldSize() const;

(note that the terrain is always square, so a world size of 500 means
its 500 ogre units width by 500 ogre units depth)

Using the APIs listed (and knowing the center of the Terrain in 3d
space) I should be able to get all of the vertices of the Terrain.

However I'm not very familiar with triangle data, or how to obtain
triangle data. Would anybody be kind enough to outline how to iterate
through the vertex data and compute the triangle data? I read the
demo code and its basically reading all of this data in from a .obj
file, however it does compute normals.

I'm basically not sure how to retrieve triangle, face, and normal data.

[Mikko Mononen]

You might get faster response from the ogre forums, since that
question is very ogre specific. Does the ogre sources offer any
indication how the HF data is converted to triangles?

--mikko

[KungFooMasta]

I asked Sinbad if he would be kind enough to make an API giving access
to the triangle data, but found out that there is no central location
that stores all this data, and his suggestion was to derive this data
manually using the 'getHeightAt' API.

Still, in order for me to ask the right questions, I need to
understand what the triangle data really is. I'm looking through the
MeshLoaderObj class to try and figure it out, it looks like the
triangle data is an array of ints?

while (src < srcEnd)
{
// Parse one row
row[0] = '\0';
src = parseRow(src, srcEnd, row, sizeof(row)/sizeof(char));
// Skip comments
if (row[0] == '#') continue;
if (row[0] == 'v' && row[1] != 'n' && row[1] != 't')
{
// Vertex pos
sscanf(row+1, "%f %f %f", &x, &y, &z);
addVertex(x, y, z, vcap);
}
if (row[0] == 'f')
{
// Faces
nv = parseFace(row+1, face, 32, m_vertCount);
for (int i = 2; i < nv; ++i)
addTriangle(face[0], face[i-1], face[i], tcap);
}
}

So in here we add vertices and faces depending on what is read in from
the .obj file. The triangle data looks to be retrieved from the face
data:

void rcMeshLoaderObj::addTriangle(int a, int b, int c, int& cap)
{
if (m_triCount+1 > cap)
{
cap = !cap ? 8 : cap*2;
int* nv = new int[cap*3];
if (m_triCount)
memcpy(nv, m_tris, m_triCount*3*sizeof(int));
delete [] m_tris;
m_tris = nv;
}
int* dst = &m_tris[m_triCount*3];
*dst++ = a;
*dst++ = b;
*dst++ = c;
m_triCount++;
}

As you can tell this process for getting data is nothing similar to
how I would get it from an a mesh or heightfield object. (No parsing
of files)

In this situation, what does a face represent, how is it different
from a triangle? How does an int represent a triangle, maybe each
triangle is a few ints within the array? (are they ints in the array
grouped together to form some meaningful data?)

Thanks for the help. (really looking forward to using recast but I'm
not used to the lower level side of graphics programming.. :( )

Ben

> > I'm basically not sure how to retrieve triangle, face, and normal data.- Hide quoted text -
>
> - Show quoted text -

[Mikko Mononen]

It is indexed triangles data, layid out as simply as it gets. That is
the int array has triangleCount*3 indices, one index per each corner
of each triangle. These indices point to the associated vertex array.
The vertex array is simply list of floats, were 3 consecutive floats
defines a vertex.

There are 3 ways to voxelize the triangles in Recast, you can mix and
match these methods and call them as many times as you need. The
examples just call it once, since the whole model comes from one file.

The simplest function is rcRasterizeTriangle(), which takes 3 verts
and a flag (walkable or not) and just rasterizes it. Then there are
two versions of rcRasterizeTriangles(). One is very much like
glDrawArrays(), that is, takes just list of vertices and treats 3
consecutive vertices as triangle. The second version of
rcRasterizeTriangles(), which is used by all the examples, takes index
list and vertex list and each 3 consecutive indices create a triangle,
and it is very much like glDrawElements().

In pseudo code, rendering heighfield data usually looks something like this:

for (int y = 0; y < height; ++y)
for (int x = 0; x < width; ++x)
verts[x+y*width].set(x*units, getHeight[x+y*width], y*units);

for (int y = 0; y < height-1; ++y)
{
for (int x = 0; x < width-1; ++x)
{
in va = x+y*width;
in vb = (x+1)+y*width;
in vc = (x+1)+(y+1)*width;
in vd = x+(y+1)*width;
drawtri(verts[va],verts[vb],verts[vc]);
drawtri(verts[va],verts[vc],verts[vd]);
}
}

As you can see, it is pretty much indexed triangle model too. For the
actual code, you need to consult to ogre dudes again.


--mikko

[KungFooMasta]

Thanks mikko, this is very helpful! I think I'll have to go the index
route, since in my design I have multiple meshes that register
themselves to be used for pathing.

That being said, do you know of any links or information about
indices?

For example say I have a 2d quad on the screen, which is made of 2
triangles:

0---1
| / |
| / |
2---3

0,1,2, and 3 represent the 4 vertices that are used to make up the
quad. The vertex array (floats) would store [0.x,0.y,0.z,1.x,1.y,1.z,
2.x,2.y,2.z,3.x,3.y,3.z]

What does the index buffer look like? [1,2,3,3,4,2] ?

I'm somewhat familiar with winding, clockwise and counter clockwise,
which determines which way the face is pointing. But I just need a
real example of the kinds of ints I would find in an index array.

Ben

> >> - Show quoted text -- Hide quoted text -

[Mikko Mononen]

This came first via google:
http://alt.pluralsight.com/wiki/default.aspx/Craig.DirectX/IndexBufferTutorial.html

Don't think it too hard, index is just an offset :) Just like you
would access an array, but here you do it indirectly. In the example
below, the data is otherwise right, but the first vertex index is 0,
second 1, etc. Another way to think about it is that the index is an
offset to the array.

Here' how creating an index buffer for the example below might work
(not tested code):

int* indices = new int[(width-1)*(height-1)*2*3]; // 2 tris per cell

for (int y = 0; y < height-1; ++y)
{
for (int x = 0; x < width-1; ++x)
{

int va = x+y*width;
int vb = (x+1)+y*width;
int vc = (x+1)+(y+1)*width;
int vd = x+(y+1)*width;
int base = (x+y*(width-1))*2*3; // offset to current 2 triangles in
the index array.

indices[base+0] = va;
indices[base+1] = vb;
indices[base+2] = vc;

indices[base+3] = va;
indices[base+4] = vc;
indices[base+5] = vd;
}
}

You can call the recast rasterization methods (rcRasterizeTriangles)
as many times as you need, before you call the filter functions and
turn the height field into compact heightfield.


--mikko