NavMesh generation issues

[Joey]

Terrain grid size: 100
http://postimage.org/image/9pwzq8s67/
http://postimage.org/image/qeyfm5orj/

The generated NavMesh:
http://postimage.org/image/y8z17jwkf/

configuration parameters:
http://postimage.org/image/jr1tzk59b/

I adjusted all the parameters, but it doesn't work.

[Mikko Mononen]

The config is not right, take a look at this blog on how to derive the settings:
http://digestingduck.blogspot.fi/2009/08/recast-settings-uncovered.html

The cell size should be at least twice as small as agent radius, I
also suggest to keep cell height smaller than cell size. For example
in your case I might try cellsize 2.5, cellheight 0.5.


--mikko

[Joey]

Thanks Mikko! We are using centimeter as units. so the terrain grid
size = 100 x 100.
I tweaked the parameters:
Agent Radius = 40;
Agent Radius = 200;
Cell Size = 20;
Cell Height = 10;
http://postimage.org/image/npz1idtwf/

Got this
http://postimage.org/image/5lw0xqw7z/

Is there any mistake?

[Mikko Mononen]

Params look better now. It is a bit hard to see what is going on in
those locations where the navmesh does not get build. Can you show it
from another angle? Maybe debug draw of compact heightfields too.

--mikko

[Joey]

I'll go to office and snapshot another picture on Monday. Thanks!

[Joey]

Hi, Mikko, I snapshot another picture here, please take a look,
http://postimage.org/image/vut7h31cv/
http://postimage.org/image/5ns0l4j33/

On 8月3日, 下午6时26分, Mikko Mononen <memono...@gmail.com> wrote:

[Joey]

http://postimage.org/image/nf88dbnvj/

On 8月3日, 下午6时26分, Mikko Mononen <memono...@gmail.com> wrote:

[Mikko Mononen]

Looks like some of your input triangles are maybe marked as nonnavigable.

How do you feed in the triangles? Can you draw their area type (i.e.
are they walkable or not based on the slope)?

Can you draw the compact heightfield regions too (that is,
duDebugDrawCompactHeightfieldRegions(&dd, *m_chf))?


--mikko

[Joey]

I found a error, there are many zero area triangles, Because our
terrain using Triangle_Strip,
there will be zero area triangle between each row, now i filtered the
zero area triangles when
converting the terrain data into Triangle_List.
This region is correct:
http://postimage.org/image/pt4esxndr/

But other regions still wrong:
http://postimage.org/image/7rl9v4tcv/
http://postimage.org/image/an2yfqmqn/

the compact heightfield
http://postimage.org/image/wnjawd5en/
http://postimage.org/image/ux09uvnvj/

[Joey]

Thanks, Mikko, problem solved! There is a error in converting terrain
and cliff data. Now it work well.
http://postimage.org/image/44a42tajj/

[Mikko Mononen]

Yay! :)

--mikko

[Joey]

Another question, how to mark non-walkable triangle in
rcChunkyTriMesh?
I used ChunkyTriMesh to handle tile mesh generation, and i have two
kind of input geometry data,
terrain for walkable, other model for non-walkable.

[Mikko Mononen]

I think there's no way to do that. Do you really need chunky trimesh?
If you only have one tile, then there is no need for chunky trimes at
all.

--mikko

[Joey]

I need DetourTileCache to handle dynamic obstacle. My terrain has 256
x 256 tiles, 1 tile = 16 x 16 cells.

[Joey]

I will mark the non-walkable model as ConvexVolume, the terrain data
still use ChunkyTriMesh.

On 8月8日, 下午5时05分, Mikko Mononen <memono...@gmail.com> wrote:

[Mikko Mononen]

You can use triangle flag too, but I think the chunky trimesh does not
support flags, so you would need to extend that. Generally I encourage
folks to use their engines own spatial query and not to use the chunky
trimehs at all. It was mostly created to allow the demo to handle
large meshes.

--mikko

[Joey]

Hi, Mikko, I use my own spatial query(terrain tile), but i got this
http://postimage.org/image/egstuxdlr/
Is there parameter wrong?

[Mikko Mononen]

Hi,

Tile has two bounding boxes, one which describes the exact tile
extents and another one which is used building the heighfield. The
expanded bbox is needed so that the algorithm that dilates the borders
by agent radius works correctly across tiles.

You can see how the expanded bbox is calculated here:
https://code.google.com/p/recastnavigation/source/browse/trunk/RecastDemo/Source/Sample_TileMesh.cpp#928

If your game world is build using tiles too and a navmesh tile is
exactly the size of your tile, then this means that you will need to
pass in the neighbour tiles too.


--mikko

[Joey]

Yes, I use the sample_tilemesh code, and replace the chunkymesh, the
navmesh tile is match my terrain tile, 16 x 16 tiles.
cfg.tileSize = (int)m_params.tileSize;
cfg.borderSize = cfg.walkableRadius + 3; // Reserve enough padding.
cfg.width = cfg.tileSize + cfg.borderSize*2;
cfg.height = cfg.tileSize + cfg.borderSize*2;
rcVcopy(cfg.bmin, tileBmin);
rcVcopy(cfg.bmax, tileBmax);
cfg.bmin[0] -= cfg.borderSize * cfg.cs;
cfg.bmin[2] -= cfg.borderSize * cfg.cs;
cfg.bmax[0] += cfg.borderSize * cfg.cs;
cfg.bmax[2] += cfg.borderSize * cfg.cs;

you mean, if i build tile[i][j], i need pass (i-1, j-1), (i, j), (i
+1, j+1)....9 tiles in it?

On 8月15日, 下午4时01分, Mikko Mononen <memono...@gmail.com> wrote:
> Hi,
>
> Tile has two bounding boxes, one which describes the exact tile
> extents and another one which is used building the heighfield. The
> expanded bbox is needed so that the algorithm that dilates the borders
> by agent radius works correctly across tiles.
>

> You can see how the expanded bbox is calculated here:https://code.google.com/p/recastnavigation/source/browse/trunk/Recast...

[Joey]

I use neighbors to build a tile, the tile partition is ok. But the
nonwalkable region is wrong.
http://postimage.org/image/hyd9gv673/

I mark the terrain triangles as walkable area, and mark the bounding
box of tree as nonwalkable area,
unsigned char* buildTileMesh(int tx, int ty, const float* bmin, const
float* bmax, int& dataSize)
{
......
if (!rcCreateHeightfield(m_ctx, *solid, cfg.width, cfg.height,
cfg.bmin, cfg.bmax, cfg.cs, cfg.ch))
{
m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not create solid
heightfield.");
return 0;
}

for (int j = -1; j <= 1; ++j)
{
for (int i = -1; i <= 1; ++i)
{
if (ty+j >= 0 && ty+j < 16 && tx+i >= 0 && tx+i < 16)
{
const TriangleList& walkable = m_Walkable[ty+j][tx+i];
const TriangleList&nonWalkable = m_NonWalkable[ty+j][tx+i];
if (walkable.ntris > 0)
{
unsigned char* triareas = new unsigned char[walkable.ntris];
memset(triareas, 0, walkable.ntris*sizeof(unsigned char));
rcMarkWalkableTriangles(m_ctx, cfg.walkableSlopeAngle,
walkable.verts, walkable.nverts, walkable.tris, walkable.ntris,
triareas);

rcRasterizeTriangles(m_ctx, walkable.verts, walkable.nverts,
walkable.tris, triareas, walkable.ntris, *solid, cfg.walkableClimb);

delete [] triareas;
}

if (nonWalkable.ntris > 0)
{
unsigned char* triareas = new unsigned char[nonWalkable.ntris];
memset(triareas, 0, nonWalkable.ntris*sizeof(unsigned char));
rcRasterizeTriangles(m_ctx, nonWalkable.verts,
nonWalkable.nverts, nonWalkable.tris, triareas, nonWalkable.ntris,
*solid, cfg.walkableClimb);

delete [] triareas;
}
}
}
}

// Once all geometry is rasterized, we do initial pass of filtering
to
// remove unwanted overhangs caused by the conservative rasterization
// as well as filter spans where the character cannot possibly stand.
rcFilterLowHangingWalkableObstacles(m_ctx, cfg.walkableClimb,
*solid);
......
}

[Joey]

The red region is wrong, the tree bounding box is marked as
nonwalkable.
http://postimage.org/image/g0ckiqhwf/

On 8月15日, 下午4时01分, Mikko Mononen <memono...@gmail.com> wrote:

> Hi,
>
> Tile has two bounding boxes, one which describes the exact tile
> extents and another one which is used building the heighfield. The
> expanded bbox is needed so that the algorithm that dilates the borders
> by agent radius works correctly across tiles.
>

> You can see how the expanded bbox is calculated here:https://code.google.com/p/recastnavigation/source/browse/trunk/Recast...

[Mikko Mononen]

How does the compact heightfield look for that location?

--mikko

[Joey]

the compact heightfield:
http://postimage.org/image/ezcbtm0wv/
http://postimage.org/image/q07gymt5r/

[Mikko Mononen]

Looks like the missing trees are not just rendered. Can you double
check your bbox code?

--mikko

[Joey]

I rechecked the index of tree bounding box, it has a wrong offset. I
fixed it.
But the edge of two tiles still has wrong polygon, take a look at red
circle:
http://postimage.org/image/iy9jcfpjz/

I hided the trees, and draw the tree bounding box as white box.

[Mikko Mononen]

It behaves as designed.

In your case Recast has detected that there is small walkable area
inside the tree bounding box, but it does not get pruned away because
it is at tile boundary. The areas at tile boundary are not pruned
because there is not enough information to detect if the area is just
a small area or if it is actually crucial small part of some walkable
region.

If you want more volumetric method to punch holes, you can use
rcMarkBoxArea() or rcMarkConvexPolyArea() with RC_NULL_AREA as areaId.
Box area takes world axis aligned bounding box to mark an area, and
convex poly area will take polygon boundary and extrude it vertically
to mark an area. If the bounding box depicts nonwalkable area, you
should expand the bbox bottom down by agent height.


--mikko

[Joey]

This is the top view of the area:
http://postimage.org/image/7eihpmknz/

Apparently, there is no walkable area at the tile cross line.
I'll take your advice to use rcMarkboxArea. Thanks Mikko.

[Mikko Mononen]

If you change cfg.minRegionArea = 0, you'll see the other pruned inner
areas too inside the bboxes.

--mikko