NavMesh Generation

This article is incomplete. You can help by filling in any blank descriptions. Further information might be found in a section of the discussion page. Please remove this message when no longer necessary.

General Info

Automatic Navmesh Generation is unsupported in GECK v1.0 This development tool was designed for rapid generation of basic navmesh for area. The nature of archived art files removes the data this tool used to approximate navmesh. This documentation is left as an educational tool, and may prove useful to some modders, particularly those using entirely new art assets.

Navmesh Generation is group of tools that are responsible for creating NavMeshes from a cell’s havok data. These tools are also useful for optimizing existing NavMeshes. There are two dialog boxes for NavMesh generation. Standard NavMesh Generation is mainly used as a one click solution to create a full working NavMesh for a cell. Advanced NavMesh Generation is a group of tools that can be run one pass at a time in order to optimize and fix problems with an existing NavMesh. A cell should generally have fewer than 500 triangles in all of its NavMeshes to insure a small memory footprint and fast pathing.

NavMesh Auto-Generation Dialog

This dialog box is the one click solution to create starting navmeshes for a cell. Open it by clicking Generate NavMesh from the main NavMesh drop down menu. It allows you to set the options wanted with check boxes, and set the variable values. Once set click Ok, the application imports the data specified in the Import Options, runs the selected passes, and finalizes the NavMesh (if checked). This should generate a good starting point for most cells.

Import Options

Only the object types selected are imported. All imported data is wielded within the distance set in the Wield Vertex Distance.

Import Land

Import Havok

Import Current

Passes

Check the boxes next to the passes that should be performed.

Simplify Mesh

Remove Overlapping

Remove Islands

Connect Stairs

Intersection

Finalize NavMesh

• Not a pass but an option to choose if the finalizing passes at the end should be preformed or not (on by default).
• With this option unchecked the generation will finish much faster as it will not finding cover edges, linking cell edges, or create portals for doors. These things slow the generation process down and generally you are going to need to modify a few things before you want those passes done anyway. This is useful in speeding things up when you want to quickly get to manually editing, or you want to try testing different generation values. This also helps with further advanced generation passes as many optimizations and removal passes won't remove cover triangles.
• Note Remember if you are going to not use Finalize NavMesh you will need to manually run (all located in the NavMesh drop down menu) Find Cover Edges if you want cover, Link Doors if there are doors in your cell, and Link Cell Edges if it is an exterior cell, before you finish the NavMesh.

Parameters

Set these parameter values to modify the generation. The default values should work well as a starting point.

Wield Vertex Distance

Longest Edge Length

Shortest Edge Length

Simplification Level

Corner Simplify: ???

Overlap Distance

Min Island Area

Step Height

Max Walkable Angle

Other Info

• There is no undo with this dialog box running this will clear the current undo buffer.
• Since this dialog runs Link Doors, Link Cell Edges it will most likely try to check out NavMeshes that are in cells linked to the working cell.

What to expect from One Click Generation

• This process can take a good amount of time. On a cell with a large amount of collision polygons and intersection between objects it can take 5 minutes on a fast machine. There is a status bar update in the editor to show some relative progress.
• The navmesh generation uses the havok collision geometry so the more optimized this geometry is the better the navmesh generation will be, and the less time it will take to generate.
• You will rarely get a finished navmesh from one click generation, some cleanup work will need to be done. On some interiors you will get something very close to useable but there is almost always a few holes or an unconnected edge or two.
• One of the common problems with the one click generation is the stair connect pass being aggressive. It will try to combine edges that don't exactly match up. In the general case this will save time by connecting long edges such as sidewalk edges. However it can make mistakes and you will see areas with some triangles snapped up that don't make much sense. The idea is that it should be easier to delete the bad triangles than to spend time fusing edges together.
• Another common problem is the aggressive removal process. It will attempt to remove any triangle underneath another (within the given range) and also remove triangles that are found to be inside of something, a pole or a pillar. This works very well in making clean cuts around walls and other vertical hard edges. To determine if something should be removed the process checks against other geometry and their normals. The problem is that some triangles will erroneously be removed. This will mostly happen in areas where there is single sided collision geometry as the removal test assumes all geometry is double sided and has proper normals. In practice it will improve the generation by cutting and removing most unused triangles. Cleanup becomes filling in the triangles that were removed by error instead of manually cutting and removing large amounts of triangles.

Advanced NavMesh Generation Dialog

Similar to Generate NavMesh Dialog as it only works on the current cell. Most all of the same functions are used, this dialog is set up to run one pass at a time instead of all at once. This allows for more fine grain manipulation and optimization of the navmesh. Unlimited undo is also supported with this mode, note however that once the dialog is closed the undo data is lost.

Passes

Each pass is a button, click it to run that pass. Undo Last will restore the cells navmesh to the previous pass state.

Generate Objects

Generate Land

Cut Selected Obj

Finalize

Find Cover

Remove Unwalkable

Simplify Edge Collapse

Simplify Edge Swap

Remove Overlapping

Intersect

Remove Islands

Collapse Short Edges

Connect Stairs

Undo Last

Parameters

Set these parameter values to modify the generation. The default values should work well as a starting point.

Wield Vertex Distance

Max Angle

Simplification Level

Longest Edge Length

Corner Simplify Threshold

Edge Swap Max Angle

Overlap Distance

Minimum Intersection Length

Min Island Area

Shortest Edge Length

Step Height

Max XY Threshold

WorldSpace NavMesh auto generation

This allows a user to generate navmeshes for a region or worldspace. This generation mode creates navmeshes using a height map based approach on all the geometry in the cell (except for trees which are later cut out of the meshes). It should give useful navmeshes for exterior "wilderness cells" (cells generally filled with only landscape type features, land, rocks, trees). It will not handle overlapping objects like buildings or bridges well, these cells will generally need to be fixed by hand or generated using the single cell NavMesh Standard Generation

• To generate for a region:
  • Open up the region dialog, from main menu World->Region
  • Click on a region
  • Click “Auto Generate Navmesh for this Region”
  • This will open the Auto Generation dialog

• To generate for a worldspace:
  • Load a cell for the desired worldspace to generate navmesh for
  • From main menu Navmesh->Auto Generate Worldspace
  • This will open the Auto Generation dialog

The Auto Generation dialog will give information on how many cells it has found in the region or worldspace to work on. It will ignore cells that already contain hand made/fixed navmeshes in them. By default it will ignore cells that have existing auto generated navmeshes in them, you can click the Regenerate Existing Auto Generated Cells option to redo those cells.

• With default values auto generation should take about 30-40 seconds per cell to generate (not including cell loading time).
• For a very fast, draft quality navmesh try using a Height Map Resolution of 128 and setting the Faster Generation (No Thin Area Removal) check box. This should only take about 1-3 seconds per cell. This fast mode can work well as a final solution for navmeshing a "test worldspace" with flat land and few objects.
• You can limit the number of cells that the auto generation will process by setting the Cell Count Limit value.

---

Parameters

Set these parameter values to modify the auto generation.

Height Map Resolution

Simplification Level

Min Island Area

Max Walkable Angle

Longest Edge Length

Other Info

• Information for the auto generation will be written to the warnings file, this will give cell names, load times, generation times, and navmesh triangle counts. This should also be helpful in tracking down issues.
• The system will save after every 25 cells to make sure data is not lost, this also means you can kill it if needed and retain most of the work done.
• You can clear auto generated cells in a region by clicking the Remove Auto Navmesh for this Region button on the region dialog.

Passes

Passes that are used in NavMesh Generation, both the standard and advanced dialogs use these passes. Be aware that details that state certain passes should be run after a pass only apply to advanced navmesh generation mode. Standard generation is set up to make sure all the need passes are run in the proper order.

Import Land

• Imports land data to the navmesh. Note that land data is 2048 triangles before simplification, can be a little slow until a Simplify Edge Collapse pass is run. Incoming vertices are wielded with Wield Vertex Distance.

Import Havok

• Imports all havok data in a cell. Only objects whose root is located in the current cell will be imported.
• When run as a single pass all triangles are imported (down facing and vertical), and won't be very useable until a Remove Unwalkable pass is run. Incoming vertices are wielded with Wield Vertex Distance.

Import Current

• (Standard only) Always happens implicitly for Advanced Passes.
• Imports the current NavMeshes in a cell.
• When used in standard generation mode it is useful for cleaning and relinking of a mesh, generally when doing this though one would only have the Remove Unwalkable and Simplify Mesh passes checked.
• Note for Standard Generation if this is set and another import option is also set both/all will be imported.

Generate Objects

• (Advanced only)
• Select objects by holding down the ALT key. Then run this pass.
• Will import the havok geometry for the selected objects and run that standard generation pass on them.
• This pass will not effect the current navmeshes in the cell.
• Useful for quickly adding navmeshes to a new area in a cell that already has finished navmeshes.

Generate Land

• (Advanced only)
• Same as Generate Objects, but the Land is the only object that is generated for.
• Useful for quickly putting in a navmesh for a sparse exterior cell.

Cut Selected Obj

• (Advanced only)
• Imports currently selected (with regular GECK selection) objects, currently must turn off NavMesh Editing (Main NavMesh icon from GECK, will stop drawing of NavMesh), select an object or objects, then open the advance dialog and run this pass, then turn the NavMesh Editing back on.
• Will import the havok data for the selected object or objects. Incoming vertices are wielded with Wield Vertex Distance.
• Very useful for fixing a changed part of a cell without recreating the entire mesh.
• Also useful to create masks that can be used to remove large areas using Remove Overlapping.

Finalize

• (Advanced only, happen implicitly with standard generation)
• Short cut pass, that allows undo. Same as running Finalize Cell NavMeshes from the main drop-down menu

Find Cover

• (Advanced only, happen implicitly with standard generation)
• Short cut pass, that allows undo. Same as running Find Cover Edges from the main drop-down menu

Remove Unwalkable

• Removes triangles with normal vectors that form an angle with the positive Z axis less than a threshold set by Max Angle (default 45, range 0 - 90). Smaller numbers leave fewer triangles (0 only leaves flat triangles).
• Should be done after manual creation with a value of no more than 45 to make sure the NavMesh created is going to be walkable by NPCs.
• This pass will also remove vertices that have no triangles.
• May create holes in areas not expected, watch for yellow edges that are not on the outside of the mesh.

Simplify Edge Collapse

• Called Simplify Mesh in Standard Generation.
• Main simplification pass. This pass will remove vertices and triangles while trying to preserve as much of the original shape as possible.
• Uses Simplification Level (0.0 min) this value specifies a relative amount of change allowable for an edge collapse. A value of 0.0 will only allow edge collapses to happen between triangles that are coplanar. The standard value of 1.0 will allow a good amount of change between triangles, larger values such as 4, or 5 can be useful in exteriors.
• Large values will greatly simplify the mesh, but could cause problems with many parts of the mesh being underneath or over the geometry it is trying to approximate. This isn't horrible as the animation system will use the havok data to actually walk.
• Uses parameter Longest Edge Length, this will prevent collapses that would create an edge longer than this value. It is good to keep this around 512 interior or 1024 exterior to prevent very large triangles, triangles that are very large are not always best for pathing.
• Uses parameter Corner Simplify Threshold (0.85 - 0.9999) this specifies how much angular difference can exist between an outside edge before it can be simplified. A value of 1.0 would only allow a collapse between two connected outside edges when the line they are on is completely straight. A lower value will allow slightly bent outside edges to be simplified.

Simplify Edge Swap

• (Advanced only) runs implicitly during standard generation.
• Secondary simplification pass. This pass does not remove any triangles or vertices. It only switches the order of where the edges are in a mesh and to try and create healthier triangles; large triangles with larger angles. Tries to fix problems such as fans of many edges coming from one vertex, and thin triangles. Thin triangles are bad for pathfinding.
• Uses the parameter Edge Swap Max Angle, (default 3.5) this value should stay low, as it limits the amount of change between two triangles where a swap will happen. With large values the mesh can be significantly distorted as valleys between two connected triangles will become hills and visa-versa.
• Also uses Longest Edge Length, this value will prevent edge swaps that would create an edge longer than this value. It is good to keep this around 512 interior or 1024 exterior to prevent very large triangles, triangles that are very large are not always best for pathing.

Remove Overlapping

• This pass will project triangles down Overlap Distance and then cut out and remove triangles that are underneath these projected triangles.
• This pass is very useful to make clean cuts and corners around world geometry such as buildings, beds, etc.
• This pass can be slow in an extremely complex area, and can create thousands of triangles. If this happens it can generally be fixed by running a Simplify Edge Collapse pass after.
• Another option is to handle complex areas is to import a few objects at a time using Cut Selected Obj and then after Remove Unwalkable triangles. Then you should have a good mask, select all of the triangles with flood fill F, and then move the triangles down by holding the Z key. Get it into position within Overlap Distance then run the pass, this will allow clean removal of buildings and other objects that are too tall to use the standard overlapping pass.
• A useful trick to get rid of narrow pathways is to use existing small meshes, such as bed tops, to clean up small spaces between the bed and a wall. Do this by manually stretching the bed top mesh to move outside of the wall. Then when the overlapping pass is run it will clean and remove the small area between the bed and the wall.
• The removal will sometimes leave behind very thin triangles (may look like yellow lines). These can generally be fixed by vertex merging (link/reference needed here) or by running a Collapse Short Edges pass.

Intersection

• Intersection of the mesh with itself. This will not remove anything however.
• To quickly remove unwanted area after intersection it is best to manually delete vertices.
• This pass has the potential to be slow in a very complex area.
• Can create many vertices and small triangles. After deleting what isn't wanted make sure to run a Simplify Edge Collapse pass after.
• Uses parameter Minimum Intersection Length it will prevent intersections smaller than this value. Default 0.10 should be used most times, however increasing this value can limit problems where too many intersections are created.
• When used in advanced mode will also clip triangles that fall outside of an exterior cell boundry. Useful after manually adding an object.

Remove Islands

• This pass will flood fill all areas of the navmesh and delete triangle groups with an area less than Min Island Area.
• This pass is useful in remove small mesh such as stair steps, chair and bed tops, and small unconnected areas in the mesh.

Collapse Short Edges

• (Advanced Only) runs implicitly during standard generation
• This pass will collapse any edge smaller than Shortest Edge Length (default value 1.0).
• Very useful in cleaning up very thin triangles.
• Once the basic navmesh and it's passes have been run running this pass with a larger value such as 10.0 will help to remove problems in the mesh that might not be obvious.

Connect Stairs

• This pass will attempt to connect edges that are close to parallel with each other and within a Step Height.
• This will merge things other than stairs, useful things like merging sidewalks to lower ground, but it can also merge things unwanted that will need to be cleaned up later.

Undo Last

• (Advanced Only)
• Clicking this will restore the navmeshes from before the last pass.
• Note, when the dialog box is closed or the cell is changed the undo data is flushed.

Issues

• None of the passes respect cover edges, or portal edges; if you run any passes in advanced mode, all of that data will be lost (Should be fixed in the future). However doing a standard auto-generate will run all the linking and cover finding passes at the end. For now make sure the navmesh is in the state you want it in, then run the linking and cover passes, then it should be ready to save and check in. You can also run a standard auto-generation with everything turned off except for Import Current as this will run all the needed passes at the end.

Parameters

Parameters that can be set for use in NavMesh Generation, both the standard and advanced dialog use these parameters. Input error checking is done and values are clamped to prevent unsafe data being used, new values are stored across both dialog boxes, but lost and set back to default on editor exit.

Wield Vertex Distance

• This parameter sets the minimum distance between two vertices before they will be merged. All importing and passes respect this.
• (default 0.1, range 0.0 - 2.5)
• Setting this value to a larger number can be useful in fixing problems with duplicate/very close vertices, generally good to use with a Collapse Short Edges pass.
• Note Large values when Intersection or Remove Overlapping is selected/being run can cause bad results.

Max Angle

• This parameter is only used with Remove Unwalkable.
• (default 45, range 0 - 90)
• Smaller numbers leave fewer triangles (0 only leaves flat triangles).

Simplification Level

• This parameter is only used with the Simplify Edge Collapse pass.
• (default 1.0, range 0.0 - 10.0)
• Larger values produce few triangles but larger distortion from the original havok data.

Longest Edge Length

• This parameter is used by Simplify Edge Collapse and Simplify Edge Swap.
• (default 512.0, range > 0.0)
• This value limits creation of edges longer than this.
• Note this does not split edges that are longer than this value right now. If a longer edge is imported it is left as is.

Corner Simplify Threshold

• (Advanced Generation Only)
• This parameter is only used by Simplify Edge Collapse.
• (default 0.9999, range 0.85 - 0.9999)
• This value limits the how much simplification can be done to the outside edges of a mesh.
• A value close to 1.0 will only allow completely straight outside edges to be simplified.
• Smaller values will allow slightly bend outside edges to be simplified.

Edge Swap Max Angle

• (Advanced Generation Only)
• This parameter is only used by Simplify Edge Swap.
• (default 3.5, range 0.1 - 44.5)
• Large values will cause significant mesh distortion as valleys between steeply angled triangles will become inversely steep hills and visa-versa.

Overlap Distance

• This parameter is only used by Remove Overlapping.
• (default 128.0, range >= 0.0)
• Sets how far objects should be projected down for intersection and removal of triangles that are underneath one another.

Minimum Intersection Length

• (Advanced Generation Only)
• This parameter is used by Intersection and Remove Overlapping.
• (default 0.1, range >= 0.1)
• This value is clamped to be at least as large as Wield Vertex Distance.
• This value prevents small intersections. This prevents the intersection code from producing too many triangles.

Min Island Area

• This parameter is only used by Remove Islands.
• (default 100.0, range >= 0)
• When the Remove Islands pass is run triangle groups that are unconnected and have less area than this are thrown away.
• The default value throws away most chairs, benches, and stair steps. Does not throw away bed tops, as they are useful in fixing narrow pathways see Remove Islands.
• A value of 150.0 will get rid of bed tops.

Shortest Edge Length

• This parameter is used with Collapse Short Edges (which is implicitly called during Standard Generation)
• (default 1.00 range 0.0 - 50.0)
• Edges less than this will be removed. Useful for removing very thin triangles.

Step Height

• This parameter is used with Connect Stairs
• (default 25.00)
• The height difference between two almost parallel edges that will be allowed for a stair connect.

Max XY Threshold

• This parameter is used with Connect Stairs (default vaule is used with Standard Generation)
• (default 8.0)
• This value sets the distance and max error that a valid pair of edges can be away from each other for a stair connect.

Verifying a NavMesh Is Complete

• Make sure stair cases are connected, generation doesn't take care of that. It is easy to do though, just select the two top vertices and one bottom vertex, hit A to add the triangle, then repeat for the other edge.

• Select a triangle and hit F to flood fill the navmesh and make sure that things are all connected as you expect.

• Hover over something without navmesh and look at the text bar in GECK, make sure the number of NavMeshes in this cell is what you are expecting (if more there could some unconnected triangles hiding). Note until you save (which splits unconnected large islands into their own meshes) you might only have one navmesh.

• Hover over the navmesh and see how many triangles it has, anything more than 500 and you should probably simplify it more, try an Simplify Edge Collapse pass with a higher Simplification Level value. (MegatonInteriorPlaza is about 450 triangles)

• Make sure that cell edges have the thick green borders (portals) to adjacent meshes.

• Make sure that doors to other cells also have the thick portal borders. In edge selection mode you can hover over the edge to see where the connection is to.