svn merge ^/trunk/blender -r40644:40720
authorCampbell Barton <ideasman42@gmail.com>
Thu, 6 Oct 2011 16:59:58 +0000 (16:59 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Thu, 6 Oct 2011 16:59:58 +0000 (16:59 +0000)
112 files changed:
CMakeLists.txt
GNUmakefile
SConstruct
build_files/cmake/macros.cmake
build_files/scons/config/darwin-config.py
doc/python_api/sphinx_doc_gen.py
extern/recastnavigation/CMakeLists.txt
extern/recastnavigation/Recast/Include/Recast.h
extern/recastnavigation/Recast/Include/RecastAlloc.h [new file with mode: 0644]
extern/recastnavigation/Recast/Include/RecastAssert.h [new file with mode: 0644]
extern/recastnavigation/Recast/Source/Recast.cpp
extern/recastnavigation/Recast/Source/RecastAlloc.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastArea.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastContour.cpp
extern/recastnavigation/Recast/Source/RecastFilter.cpp
extern/recastnavigation/Recast/Source/RecastLayers.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastMesh.cpp
extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp
extern/recastnavigation/Recast/Source/RecastRasterization.cpp
extern/recastnavigation/Recast/Source/RecastRegion.cpp
extern/recastnavigation/recast-capi.cpp
extern/recastnavigation/recast-capi.h
intern/audaspace/intern/AUD_SequencerReader.cpp
intern/elbeem/intern/ntl_world.cpp
intern/ghost/SConscript
po/POTFILES.in
po/README.txt [new file with mode: 0644]
po/check_po.py [new file with mode: 0755]
po/clean_po.py [new file with mode: 0755]
po/merge_po.py [new file with mode: 0755]
po/messages.txt [deleted file]
po/update_mo.py
po/update_msg.py
po/update_po.py
po/update_pot.py
release/bin/.blender/fonts/droidsans.ttf.gz
release/scripts/startup/bl_operators/screen_play_rendered_anim.py
release/scripts/startup/bl_ui/space_sequencer.py
source/blender/blenkernel/BKE_blender.h
source/blender/blenkernel/BKE_fcurve.h
source/blender/blenkernel/BKE_object.h
source/blender/blenkernel/intern/cloth.c
source/blender/blenkernel/intern/collision.c
source/blender/blenkernel/intern/colortools.c
source/blender/blenkernel/intern/curve.c
source/blender/blenkernel/intern/fcurve.c
source/blender/blenkernel/intern/implicit.c
source/blender/blenkernel/intern/multires.c
source/blender/blenkernel/intern/navmesh_conversion.c
source/blender/blenkernel/intern/object.c
source/blender/blenkernel/intern/scene.c
source/blender/blenkernel/intern/softbody.c
source/blender/blenkernel/intern/texture.c
source/blender/blenloader/intern/readfile.c
source/blender/editors/animation/anim_filter.c
source/blender/editors/animation/keyframes_edit.c
source/blender/editors/include/UI_interface.h
source/blender/editors/interface/interface.c
source/blender/editors/interface/interface_draw.c
source/blender/editors/interface/interface_handlers.c
source/blender/editors/interface/interface_icons.c
source/blender/editors/interface/interface_ops.c
source/blender/editors/interface/interface_templates.c
source/blender/editors/mesh/mesh_navmesh.c
source/blender/editors/physics/physics_fluid.c
source/blender/editors/space_action/action_edit.c
source/blender/editors/space_graph/graph_buttons.c
source/blender/editors/space_outliner/space_outliner.c
source/blender/editors/space_sequencer/sequencer_intern.h
source/blender/editors/space_sequencer/sequencer_ops.c
source/blender/editors/space_sequencer/sequencer_select.c
source/blender/editors/space_view3d/drawobject.c
source/blender/editors/space_view3d/view3d_buttons.c
source/blender/editors/transform/transform_conversions.c
source/blender/gpu/intern/gpu_material.c
source/blender/imbuf/intern/anim_movie.c
source/blender/makesdna/DNA_ID.h
source/blender/makesdna/DNA_texture_types.h
source/blender/makesdna/DNA_windowmanager_types.h
source/blender/makesrna/intern/CMakeLists.txt
source/blender/makesrna/intern/makesrna.c
source/blender/makesrna/intern/rna_armature.c
source/blender/makesrna/intern/rna_boid.c
source/blender/makesrna/intern/rna_camera.c
source/blender/makesrna/intern/rna_camera_api.c [new file with mode: 0644]
source/blender/makesrna/intern/rna_internal.h
source/blender/makesrna/intern/rna_main_api.c
source/blender/makesrna/intern/rna_object_force.c
source/blender/makesrna/intern/rna_particle.c
source/blender/makesrna/intern/rna_scene.c
source/blender/makesrna/intern/rna_screen.c
source/blender/makesrna/intern/rna_sequencer.c
source/blender/makesrna/intern/rna_smoke.c
source/blender/makesrna/intern/rna_space.c
source/blender/makesrna/intern/rna_texture.c
source/blender/makesrna/intern/rna_ui.c
source/blender/makesrna/intern/rna_userdef.c
source/blender/modifiers/intern/MOD_explode.c
source/blender/python/intern/bpy_props.c
source/blender/python/intern/bpy_rna.c
source/blender/python/intern/bpy_rna.h
source/blender/quicktime/SConscript
source/blender/render/intern/include/render_types.h
source/blender/render/intern/source/render_texture.c
source/blender/render/intern/source/volume_precache.c
source/blender/windowmanager/intern/wm.c
source/blender/windowmanager/intern/wm_event_system.c
source/blender/windowmanager/intern/wm_files.c
source/blender/windowmanager/intern/wm_init_exit.c
source/blender/windowmanager/intern/wm_operators.c
source/gameengine/Ketsji/KX_NavMeshObject.cpp
source/gameengine/Ketsji/KX_SteeringActuator.cpp

index b23959e566135a22c80f7f234dae2fc8cdab2a76..dddf06431e62f4a784ee65eab47147a104cda360 100644 (file)
@@ -488,17 +488,17 @@ if(UNIX AND NOT APPLE)
                find_path(X11_XF86keysym_INCLUDE_PATH X11/XF86keysym.h ${X11_INC_SEARCH_PATH})
                mark_as_advanced(X11_XF86keysym_INCLUDE_PATH)
 
-               list(APPEND PLATFORM_LINKLIBS ${X11_X11_LIB})
+               set(PLATFORM_LINKLIBS "${PLATFORM_LINKLIBS} ${X11_X11_LIB}")
 
                if(WITH_X11_XINPUT)
-                       list(APPEND PLATFORM_LINKLIBS ${X11_Xinput_LIB})
+                       set(PLATFORM_LINKLIBS "${PLATFORM_LINKLIBS} ${X11_Xinput_LIB}")
                endif()
        endif()
 
        if(CMAKE_SYSTEM_NAME MATCHES "Linux")
                if(NOT WITH_PYTHON_MODULE)
                        # BSD's dont use libdl.so
-                       list(APPEND PLATFORM_LINKLIBS -ldl)
+               set(PLATFORM_LINKLIBS "${PLATFORM_LINKLIBS} -ldl")
                        # binreloc is linux only
                        set(BINRELOC_INCLUDE_DIRS ${CMAKE_SOURCE_DIR}/extern/binreloc/include)
                        set(WITH_BINRELOC ON)
index 9915406e52cb2f63a2ad01b1acaac4ca8be06d82..aad3c58938c304f415b0ee90fe9664f855cb82a9 100644 (file)
@@ -164,7 +164,7 @@ package_archive:
 # Other Targets
 #
 translations:
-       $(BUILD_DIR)/bin/blender --background --python po/update_msg.py
+       $(BUILD_DIR)/bin/blender --background --factory-startup --python po/update_msg.py
        python3 po/update_pot.py
        python3 po/update_po.py
        python3 po/update_mo.py
index 42ee3342031edfad7f497609ed4a27b395ff62c2..6de11d8fe4e11aad7081861f908539b7b2efa175 100644 (file)
@@ -277,7 +277,7 @@ if env['OURPLATFORM']=='darwin':
             print "3D_CONNEXION_CLIENT_LIBRARY not found, disabling WITH_BF_3DMOUSE" # avoid build errors !
             env['WITH_BF_3DMOUSE'] = 0
         else:
-            env.Append(LINKFLAGS=['-weak_framework','3DconnexionClient'])
+            env.Append(LINKFLAGS=['-Xlinker','-weak_framework','-Xlinker','3DconnexionClient'])
 
 if env['WITH_BF_OPENMP'] == 1:
         if env['OURPLATFORM'] in ('win32-vc', 'win64-vc'):
index ef4edca1b220982ecaa6288d1032f5c1e26b581e..8a665405e72fdd05d1a1f60638724a0d77c22b75 100644 (file)
@@ -213,6 +213,7 @@ macro(setup_liblinks
                        ${JPEG_LIBRARIES}
                        ${PNG_LIBRARIES}
                        ${ZLIB_LIBRARIES}
+                       ${FREETYPE_LIBRARY}
                        ${PLATFORM_LINKLIBS})
 
        # since we are using the local libs for python when compiling msvc projects, we need to add _d when compiling debug versions
@@ -233,13 +234,6 @@ macro(setup_liblinks
                target_link_libraries(${target} ${GLEW_LIBRARY})
        endif()
 
-       target_link_libraries(${target}
-                       ${OPENGL_glu_LIBRARY}
-                       ${JPEG_LIBRARIES}
-                       ${PNG_LIBRARIES}
-                       ${ZLIB_LIBRARIES}
-                       ${FREETYPE_LIBRARY})
-
        if(WITH_INTERNATIONAL)
                target_link_libraries(${target} ${GETTEXT_LIB})
 
index 29d2b39323ec117a9e83f2530ccab99ea0f470fc..935827e7237da0ceed13c4115f096f90409e3a68 100644 (file)
@@ -90,9 +90,10 @@ LIBDIR = '${LCGDIR}'
 ###################          Dependency settings           ##################
 #############################################################################
 
-#Defaults openMP to true if compiler handles it
-if CC == 'gcc-4.2' or CC == 'llvm-gcc-4.2':
-    WITH_BF_OPENMP = True  # multithreading for fluids, cloth and smoke
+#Defaults openMP to true if compiler handles it ( only gcc 4.6.1 and newer )
+# if your compiler does not have accurate suffix you may have to enable it by hand !
+if CC.endswith('4.6.1'):
+    WITH_BF_OPENMP = True  # multithreading for fluids, cloth, sculpt and smoke
 else:
     WITH_BF_OPENMP = False
 
index ca37030074afa7e3622fd1c08cefa445337e5514..c1bed089b5a1b0ac673fde21ecf2183afe439bfd 100644 (file)
@@ -161,7 +161,7 @@ def range_str(val):
 
 
 def example_extract_docstring(filepath):
-    file = open(filepath, 'r')
+    file = open(filepath, "r", encoding="utf-8")
     line = file.readline()
     line_no = 0
     text = []
@@ -360,7 +360,7 @@ def pymodule2sphinx(BASEPATH, module_name, module, title):
     if module_all:
         module_dir = module_all
 
-    file = open(filepath, "w")
+    file = open(filepath, "w", encoding="utf-8")
 
     fw = file.write
 
@@ -510,7 +510,7 @@ def pycontext2sphinx(BASEPATH):
     # Only use once. very irregular
 
     filepath = os.path.join(BASEPATH, "bpy.context.rst")
-    file = open(filepath, "w")
+    file = open(filepath, "w", encoding="utf-8")
     fw = file.write
     fw("Context Access (bpy.context)\n")
     fw("============================\n\n")
@@ -698,7 +698,7 @@ def pyrna2sphinx(BASEPATH):
         #    return
 
         filepath = os.path.join(BASEPATH, "bpy.types.%s.rst" % struct.identifier)
-        file = open(filepath, "w")
+        file = open(filepath, "w", encoding="utf-8")
         fw = file.write
 
         base_id = getattr(struct.base, "identifier", "")
@@ -912,7 +912,7 @@ def pyrna2sphinx(BASEPATH):
 
         def fake_bpy_type(class_value, class_name, descr_str, use_subclasses=True):
             filepath = os.path.join(BASEPATH, "bpy.types.%s.rst" % class_name)
-            file = open(filepath, "w")
+            file = open(filepath, "w", encoding="utf-8")
             fw = file.write
 
             write_title(fw, class_name, "=")
@@ -963,7 +963,7 @@ def pyrna2sphinx(BASEPATH):
 
         for op_module_name, ops_mod in op_modules.items():
             filepath = os.path.join(BASEPATH, "bpy.ops.%s.rst" % op_module_name)
-            file = open(filepath, "w")
+            file = open(filepath, "w", encoding="utf-8")
             fw = file.write
 
             title = "%s Operators" % op_module_name.replace("_", " ").title()
@@ -1017,7 +1017,7 @@ def rna2sphinx(BASEPATH):
 
     # conf.py - empty for now
     filepath = os.path.join(BASEPATH, "conf.py")
-    file = open(filepath, "w")
+    file = open(filepath, "w", encoding="utf-8")
     fw = file.write
 
     version_string = ".".join(str(v) for v in bpy.app.version)
@@ -1053,7 +1053,7 @@ def rna2sphinx(BASEPATH):
 
     # main page needed for sphinx (index.html)
     filepath = os.path.join(BASEPATH, "contents.rst")
-    file = open(filepath, "w")
+    file = open(filepath, "w", encoding="utf-8")
     fw = file.write
 
     fw("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n")
@@ -1169,7 +1169,7 @@ def rna2sphinx(BASEPATH):
     # internal modules
     if "bpy.ops" not in EXCLUDE_MODULES:
         filepath = os.path.join(BASEPATH, "bpy.ops.rst")
-        file = open(filepath, "w")
+        file = open(filepath, "w", encoding="utf-8")
         fw = file.write
         fw("Operators (bpy.ops)\n")
         fw("===================\n\n")
@@ -1181,7 +1181,7 @@ def rna2sphinx(BASEPATH):
 
     if "bpy.types" not in EXCLUDE_MODULES:
         filepath = os.path.join(BASEPATH, "bpy.types.rst")
-        file = open(filepath, "w")
+        file = open(filepath, "w", encoding="utf-8")
         fw = file.write
         fw("Types (bpy.types)\n")
         fw("=================\n\n")
@@ -1194,7 +1194,7 @@ def rna2sphinx(BASEPATH):
         # not actually a module, only write this file so we
         # can reference in the TOC
         filepath = os.path.join(BASEPATH, "bpy.data.rst")
-        file = open(filepath, "w")
+        file = open(filepath, "w", encoding="utf-8")
         fw = file.write
         fw("Data Access (bpy.data)\n")
         fw("======================\n\n")
@@ -1284,7 +1284,7 @@ def rna2sphinx(BASEPATH):
 
     if 0:
         filepath = os.path.join(BASEPATH, "bpy.rst")
-        file = open(filepath, "w")
+        file = open(filepath, "w", encoding="utf-8")
         fw = file.write
 
         fw("\n")
index 660b881dd078ab63c7b9985086b05069cf6eb643..3d8b7ab151394661898f644b0d02eea51378c8f1 100644 (file)
@@ -53,18 +53,19 @@ set(SRC
                Detour/Include/DetourTileNavMeshBuilder.h
 
                Recast/Source/Recast.cpp
+               Recast/Source/RecastAlloc.cpp
+               Recast/Source/RecastArea.cpp
                Recast/Source/RecastContour.cpp
                Recast/Source/RecastFilter.cpp
-               Recast/Source/RecastLog.cpp
+               Recast/Source/RecastLayers.cpp
                Recast/Source/RecastMesh.cpp
                Recast/Source/RecastMeshDetail.cpp
                Recast/Source/RecastRasterization.cpp
                Recast/Source/RecastRegion.cpp
-               Recast/Source/RecastTimer.cpp
 
                Recast/Include/Recast.h
-               Recast/Include/RecastLog.h
-               Recast/Include/RecastTimer.h
+               Recast/Include/RecastAlloc.h
+               Recast/Include/RecastAssert.h
 )
 
 blender_add_lib(extern_recastnavigation "${SRC}" "${INC}" "${INC_SYS}")
index f25ab47f8fadc388d479f397e12b6516b61f76ae..4e20b0f0fff8c28a35eacfa3bd76c7f4f80458d5 100644 (file)
@@ -1,5 +1,5 @@
 //
-// Copyright (c) 2009 Mikko Mononen memon@inside.org
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
 //
 // This software is provided 'as-is', without any express or implied
 // warranty.  In no event will the authors be held liable for any damages
 #ifndef RECAST_H
 #define RECAST_H
 
-// The units of the parameters are specified in parenthesis as follows:
-// (vx) voxels, (wu) world units
-struct rcConfig
+/// The value of PI used by Recast.
+static const float RC_PI = 3.14159265f;
+
+/// Recast log categories.
+/// @see rcContext
+enum rcLogCategory
 {
-       int width, height;                              // Dimensions of the rasterized heighfield (vx)
-       int tileSize;                                   // Width and Height of a tile (vx)
-       int borderSize;                                 // Non-navigable Border around the heightfield (vx)
-       float cs, ch;                                   // Grid cell size and height (wu)
-       float bmin[3], bmax[3];                 // Grid bounds (wu)
-       float walkableSlopeAngle;               // Maximum walkble slope angle in degrees.
-       int walkableHeight;                             // Minimum height where the agent can still walk (vx)
-       int walkableClimb;                              // Maximum height between grid cells the agent can climb (vx)
-       int walkableRadius;                             // Radius of the agent in cells (vx)
-       int maxEdgeLen;                                 // Maximum contour edge length (vx)
-       float maxSimplificationError;   // Maximum distance error from contour to cells (vx)
-       int minRegionSize;                              // Minimum regions size. Smaller regions will be deleted (vx)
-       int mergeRegionSize;                    // Minimum regions size. Smaller regions will be merged (vx)
-       int maxVertsPerPoly;                    // Max number of vertices per polygon
-       float detailSampleDist;                 // Detail mesh sample spacing.
-       float detailSampleMaxError;             // Detail mesh simplification max sample error.
+       RC_LOG_PROGRESS = 1,    ///< A progress log entry.
+       RC_LOG_WARNING,             ///< A warning log entry.
+       RC_LOG_ERROR,               ///< An error log entry.
 };
 
-// Heightfield span.
-struct rcSpan
+/// Recast performance timer categories.
+/// @see rcContext
+enum rcTimerLabel
+{
+       /// The user defined total time of the build.
+       RC_TIMER_TOTAL,
+       /// A user defined build time.
+       RC_TIMER_TEMP,
+       /// The time to rasterize the triangles. (See: #rcRasterizeTriangle)
+       RC_TIMER_RASTERIZE_TRIANGLES,
+       /// The time to build the compact heightfield. (See: #rcBuildCompactHeightfield)
+       RC_TIMER_BUILD_COMPACTHEIGHTFIELD,
+       /// The total time to build the contours. (See: #rcBuildContours)
+       RC_TIMER_BUILD_CONTOURS,
+       /// The time to trace the boundaries of the contours. (See: #rcBuildContours)
+       RC_TIMER_BUILD_CONTOURS_TRACE,
+       /// The time to simplify the contours. (See: #rcBuildContours)
+       RC_TIMER_BUILD_CONTOURS_SIMPLIFY,
+       /// The time to filter ledge spans. (See: #rcFilterLedgeSpans)
+       RC_TIMER_FILTER_BORDER,
+       /// The time to filter low height spans. (See: #rcFilterWalkableLowHeightSpans)
+       RC_TIMER_FILTER_WALKABLE,
+       /// The time to apply the median filter. (See: #rcMedianFilterWalkableArea)
+       RC_TIMER_MEDIAN_AREA,
+       /// The time to filter low obstacles. (See: #rcFilterLowHangingWalkableObstacles)
+       RC_TIMER_FILTER_LOW_OBSTACLES,
+       /// The time to build the polygon mesh. (See: #rcBuildPolyMesh)
+       RC_TIMER_BUILD_POLYMESH,
+       /// The time to merge polygon meshes. (See: #rcMergePolyMeshes)
+       RC_TIMER_MERGE_POLYMESH,
+       /// The time to erode the walkable area. (See: #rcErodeWalkableArea)
+       RC_TIMER_ERODE_AREA,
+       /// The time to mark a box area. (See: #rcMarkBoxArea)
+       RC_TIMER_MARK_BOX_AREA,
+       /// The time to mark a cylinder area. (See: #rcMarkCylinderArea)
+       RC_TIMER_MARK_CYLINDER_AREA,
+       /// The time to mark a convex polygon area. (See: #rcMarkConvexPolyArea)
+       RC_TIMER_MARK_CONVEXPOLY_AREA,
+       /// The total time to build the distance field. (See: #rcBuildDistanceField)
+       RC_TIMER_BUILD_DISTANCEFIELD,
+       /// The time to build the distances of the distance field. (See: #rcBuildDistanceField)
+       RC_TIMER_BUILD_DISTANCEFIELD_DIST,
+       /// The time to blur the distance field. (See: #rcBuildDistanceField)
+       RC_TIMER_BUILD_DISTANCEFIELD_BLUR,
+       /// The total time to build the regions. (See: #rcBuildRegions, #rcBuildRegionsMonotone)
+       RC_TIMER_BUILD_REGIONS,
+       /// The total time to apply the watershed algorithm. (See: #rcBuildRegions)
+       RC_TIMER_BUILD_REGIONS_WATERSHED,
+       /// The time to expand regions while applying the watershed algorithm. (See: #rcBuildRegions)
+       RC_TIMER_BUILD_REGIONS_EXPAND,
+       /// The time to flood regions while applying the watershed algorithm. (See: #rcBuildRegions)
+       RC_TIMER_BUILD_REGIONS_FLOOD,
+       /// The time to filter out small regions. (See: #rcBuildRegions, #rcBuildRegionsMonotone)
+       RC_TIMER_BUILD_REGIONS_FILTER,
+       /// The time to build heightfield layers. (See: #rcBuildHeightfieldLayers)
+       RC_TIMER_BUILD_LAYERS, 
+       /// The time to build the polygon mesh detail. (See: #rcBuildPolyMeshDetail)
+       RC_TIMER_BUILD_POLYMESHDETAIL,
+       /// The time to merge polygon mesh details. (See: #rcMergePolyMeshDetails)
+       RC_TIMER_MERGE_POLYMESHDETAIL,
+       /// The maximum number of timers.  (Used for iterating timers.)
+       RC_MAX_TIMERS
+};
+
+/// Provides an interface for optional logging and performance tracking of the Recast 
+/// build process.
+/// @ingroup recast
+class rcContext
+{
+public:
+
+       /// Contructor.
+       ///  @param[in] state  TRUE if the logging and performance timers should be enabled.  [Default: true]
+       inline rcContext(bool state = true) : m_logEnabled(state), m_timerEnabled(state) {}
+       virtual ~rcContext() {}
+
+       /// Enables or disables logging.
+       ///  @param[in] state TRUE if logging should be enabled.
+       inline void enableLog(bool state) { m_logEnabled = state; }
+
+       /// Clears all log entries.
+       inline void resetLog() { if (m_logEnabled) doResetLog(); }
+
+       /// Logs a message.
+       ///  @param[in] category The category of the message.
+       ///  @param[in] format The message.
+       void log(const rcLogCategory category, const char* format, ...);
+
+       /// Enables or disables the performance timers.
+       ///  @param[in] state  TRUE if timers should be enabled.
+       inline void enableTimer(bool state) { m_timerEnabled = state; }
+
+       /// Clears all peformance timers. (Resets all to unused.)
+       inline void resetTimers() { if (m_timerEnabled) doResetTimers(); }
+
+       /// Starts the specified performance timer.
+       ///  @param label  The category of timer.
+       inline void startTimer(const rcTimerLabel label) { if (m_timerEnabled) doStartTimer(label); }
+
+       /// Stops the specified performance timer.
+       ///  @param label  The category of the timer.
+       inline void stopTimer(const rcTimerLabel label) { if (m_timerEnabled) doStopTimer(label); }
+
+       /// Returns the total accumulated time of the specified performance timer.
+       ///  @param label  The category of the timer.
+       ///  @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started.
+       inline int getAccumulatedTime(const rcTimerLabel label) const { return m_timerEnabled ? doGetAccumulatedTime(label) : -1; }
+
+protected:
+
+       /// Clears all log entries.
+       virtual void doResetLog() {}
+
+       /// Logs a message.
+       ///  @param[in] category The category of the message.
+       ///  @param[in] msg The formatted message.
+       ///  @param[in] len The length of the formatted message.
+       virtual void doLog(const rcLogCategory /*category*/, const char* /*msg*/, const int /*len*/) {}
+
+       /// Clears all timers. (Resets all to unused.)
+       virtual void doResetTimers() {}
+
+       /// Starts the specified performance timer.
+       ///  @param[in] label  The category of timer.
+       virtual void doStartTimer(const rcTimerLabel /*label*/) {}
+
+       /// Stops the specified performance timer.
+       ///  @param[in] label  The category of the timer.
+       virtual void doStopTimer(const rcTimerLabel /*label*/) {}
+
+       /// Returns the total accumulated time of the specified performance timer.
+       ///  @param[in] label  The category of the timer.
+       ///  @return The accumulated time of the timer, or -1 if timers are disabled or the timer has never been started.
+       virtual int doGetAccumulatedTime(const rcTimerLabel /*label*/) const { return -1; }
+       
+       /// True if logging is enabled.
+       bool m_logEnabled;
+
+       /// True if the performance timers are enabled.
+       bool m_timerEnabled;
+};
+
+/// Specifies a configuration to use when performing Recast builds.
+/// @ingroup recast
+struct rcConfig
 {
-       unsigned int smin : 15;                 // Span min height.
-       unsigned int smax : 15;                 // Span max height.
-       unsigned int flags : 2;                 // Span flags.
-       rcSpan* next;                                   // Next span in column.
+       /// The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
+       int width;
+
+       /// The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
+       int height;     
+       
+       /// The width/height size of tile's on the xz-plane. [Limit: >= 0] [Units: vx]
+       int tileSize;   
+       
+       /// The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
+       int borderSize;
+
+       /// The xz-plane cell size to use for fields. [Limit: > 0] [Units: wu] 
+       float cs;
+
+       /// The y-axis cell size to use for fields. [Limit: > 0] [Units: wu]
+       float ch;
+
+       /// The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
+       float bmin[3]; 
+
+       /// The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
+       float bmax[3];
+
+       /// The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees] 
+       float walkableSlopeAngle;
+
+       /// Minimum floor to 'ceiling' height that will still allow the floor area to 
+       /// be considered walkable. [Limit: >= 3] [Units: vx] 
+       int walkableHeight;                             
+       
+       /// Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx] 
+       int walkableClimb;                              
+       
+       /// The distance to erode/shrink the walkable area of the heightfield away from 
+       /// obstructions.  [Limit: >=0] [Units: vx] 
+       int walkableRadius;                             
+       
+       /// The maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx] 
+       int maxEdgeLen;                                 
+       
+       /// The maximum distance a simplfied contour's border edges should deviate 
+       /// the original raw contour. [Limit: >=0] [Units: wu]
+       float maxSimplificationError;   
+       
+       /// The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx] 
+       int minRegionArea;                              
+       
+       /// Any regions with a span count smaller than this value will, if possible, 
+       /// be merged with larger regions. [Limit: >=0] [Units: vx] 
+       int mergeRegionArea;                    
+       
+       /// The maximum number of vertices allowed for polygons generated during the 
+       /// contour to polygon conversion process. [Limit: >= 3] 
+       int maxVertsPerPoly;
+       
+       /// Sets the sampling distance to use when generating the detail mesh.
+       /// (For height detail only.) [Limits: 0 or >= 0.9] [Units: wu] 
+       float detailSampleDist;
+       
+       /// The maximum distance the detail mesh surface should deviate from heightfield
+       /// data. (For height detail only.) [Limit: >=0] [Units: wu] 
+       float detailSampleMaxError;
 };
 
+/// Defines the number of bits allocated to rcSpan::smin and rcSpan::smax.
+static const int RC_SPAN_HEIGHT_BITS = 13;
+/// Defines the maximum value for rcSpan::smin and rcSpan::smax.
+static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1;
+
+/// The number of spans allocated per span spool.
+/// @see rcSpanPool
 static const int RC_SPANS_PER_POOL = 2048;
 
-// Memory pool used for quick span allocation.
+/// Represents a span in a heightfield.
+/// @see rcHeightfield
+struct rcSpan
+{
+    unsigned int smin : 13;                    ///< The lower limit of the span. [Limit: < #smax]
+    unsigned int smax : 13;                    ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]
+       unsigned int area : 6;                  ///< The area id assigned to the span.
+       rcSpan* next;                                   ///< The next span higher up in column.
+};
+
+/// A memory pool used for quick allocation of spans within a heightfield.
+/// @see rcHeightfield
 struct rcSpanPool
 {
-       rcSpanPool* next;       // Pointer to next pool.
-       rcSpan items[1];        // Array of spans (size RC_SPANS_PER_POOL).
+       rcSpanPool* next;                                       ///< The next span pool.
+       rcSpan items[RC_SPANS_PER_POOL];        ///< Array of spans in the pool.
 };
 
-// Dynamic span-heightfield.
+/// A dynamic heightfield representing obstructed space.
+/// @ingroup recast
 struct rcHeightfield
 {
-       inline rcHeightfield() : width(0), height(0), spans(0), pools(0), freelist(0) {}
-       inline ~rcHeightfield()
-       {
-               // Delete span array.
-               delete [] spans;
-               // Delete span pools.
-               while (pools)
-               {
-                       rcSpanPool* next = pools->next;
-                       delete [] reinterpret_cast<unsigned char*>(pools);
-                       pools = next;
-               }
-       }
-       int width, height;                      // Dimension of the heightfield.
-       float bmin[3], bmax[3];         // Bounding box of the heightfield
-       float cs, ch;                           // Cell size and height.
-       rcSpan** spans;                         // Heightfield of spans (width*height).
-       rcSpanPool* pools;                      // Linked list of span pools.
-       rcSpan* freelist;                       // Pointer to next free span.
+       int width;                  ///< The width of the heightfield. (Along the x-axis in cell units.)
+       int height;                     ///< The height of the heightfield. (Along the z-axis in cell units.)
+       float bmin[3];          ///< The minimum bounds in world space. [(x, y, z)]
+       float bmax[3];          ///< The maximum bounds in world space. [(x, y, z)]
+       float cs;                   ///< The size of each cell. (On the xz-plane.)
+       float ch;                       ///< The height of each cell. (The minimum increment along the y-axis.)
+       rcSpan** spans;         ///< Heightfield of spans (width*height).
+       rcSpanPool* pools;      ///< Linked list of span pools.
+       rcSpan* freelist;       ///< The next free span.
 };
 
+/// Provides information on the content of a cell column in a compact heightfield. 
 struct rcCompactCell
 {
-       unsigned int index : 24;        // Index to first span in column.
-       unsigned int count : 8;         // Number of spans in this column.
+       unsigned int index : 24;        ///< Index to the first span in the column.
+       unsigned int count : 8;         ///< Number of spans in the column.
 };
 
+/// Represents a span of unobstructed space within a compact heightfield.
 struct rcCompactSpan
 {
-       unsigned short y;                       // Bottom coordinate of the span.
-       unsigned short reg;                     // Region ID
-       unsigned short dist;            // Distance to border
-       unsigned short con;                     // Connections to neighbour cells.
-       unsigned char h;                        // Height of the span.
-       unsigned char flags;            // Flags.
+       unsigned short y;                       ///< The lower extent of the span. (Measured from the heightfield's base.)
+       unsigned short reg;                 ///< The id of the region the span belongs to. (Or zero if not in a region.)
+       unsigned int con : 24;          ///< Packed neighbor connection data.
+       unsigned int h : 8;                     ///< The height of the span.  (Measured from #y.)
 };
 
-// Compact static heightfield. 
+/// A compact, static heightfield representing unobstructed space.
+/// @ingroup recast
 struct rcCompactHeightfield
 {
-       inline rcCompactHeightfield() : maxDistance(0), maxRegions(0), cells(0), spans(0) {}
-       inline ~rcCompactHeightfield() { delete [] cells; delete [] spans; }
-       int width, height;                                      // Width and height of the heighfield.
-       int spanCount;                                          // Number of spans in the heightfield.
-       int walkableHeight, walkableClimb;      // Agent properties.
-       unsigned short maxDistance;                     // Maximum distance value stored in heightfield.
-       unsigned short maxRegions;                      // Maximum Region Id stored in heightfield.
-       float bmin[3], bmax[3];                         // Bounding box of the heightfield.
-       float cs, ch;                                           // Cell size and height.
-       rcCompactCell* cells;                           // Pointer to width*height cells.
-       rcCompactSpan* spans;                           // Pointer to spans.
+       int width;                                  ///< The width of the heightfield. (Along the x-axis in cell units.)
+       int height;                                     ///< The height of the heightfield. (Along the z-axis in cell units.)
+       int spanCount;                          ///< The number of spans in the heightfield.
+       int walkableHeight;                 ///< The walkable height used during the build of the field.  (See: rcConfig::walkableHeight)
+       int walkableClimb;                      ///< The walkable climb used during the build of the field. (See: rcConfig::walkableClimb)
+       int borderSize;                         ///< The AABB border size used during the build of the field. (See: rcConfig::borderSize)
+       unsigned short maxDistance;     ///< The maximum distance value of any span within the field. 
+       unsigned short maxRegions;      ///< The maximum region id of any span within the field. 
+       float bmin[3];                      ///< The minimum bounds in world space. [(x, y, z)]
+       float bmax[3];                          ///< The maximum bounds in world space. [(x, y, z)]
+       float cs;                                   ///< The size of each cell. (On the xz-plane.)
+       float ch;                                       ///< The height of each cell. (The minimum increment along the y-axis.)
+       rcCompactCell* cells;           ///< Array of cells. [Size: #width*#height]
+       rcCompactSpan* spans;           ///< Array of spans. [Size: #spanCount]
+       unsigned short* dist;           ///< Array containing border distance data. [Size: #spanCount]
+       unsigned char* areas;           ///< Array containing area id data. [Size: #spanCount]
+};
+
+/// Represents a heightfield layer within a layer set.
+/// @see rcHeightfieldLayerSet
+struct rcHeightfieldLayer
+{
+       float bmin[3];                      ///< The minimum bounds in world space. [(x, y, z)]
+       float bmax[3];                          ///< The maximum bounds in world space. [(x, y, z)]
+       float cs;                                   ///< The size of each cell. (On the xz-plane.)
+       float ch;                                       ///< The height of each cell. (The minimum increment along the y-axis.)
+       int width;                                  ///< The width of the heightfield. (Along the x-axis in cell units.)
+       int height;                                     ///< The height of the heightfield. (Along the z-axis in cell units.)
+       int minx;                                   ///< The minimum x-bounds of usable data.
+       int maxx;                                   ///< The maximum x-bounds of usable data.
+       int miny;                                   ///< The minimum y-bounds of usable data. (Along the z-axis.)
+       int maxy;                                       ///< The maximum y-bounds of usable data. (Along the z-axis.)
+       int hmin;                                   ///< The minimum height bounds of usable data. (Along the y-axis.)
+       int hmax;                                       ///< The maximum height bounds of usable data. (Along the y-axis.)
+       unsigned char* heights;         ///< The heightfield. [Size: (width - borderSize*2) * (h - borderSize*2)]
+       unsigned char* areas;           ///< Area ids. [Size: Same as #heights]
+       unsigned char* cons;            ///< Packed neighbor connection information. [Size: Same as #heights]
+};
+
+/// Represents a set of heightfield layers.
+/// @ingroup recast
+/// @see rcAllocHeightfieldLayerSet, rcFreeHeightfieldLayerSet 
+struct rcHeightfieldLayerSet
+{
+       rcHeightfieldLayer* layers;                     ///< The layers in the set. [Size: #nlayers]
+       int nlayers;                                            ///< The number of layers in the set.
 };
 
+/// Represents a simple, non-overlapping contour in field space.
 struct rcContour
 {
-       inline rcContour() : verts(0), nverts(0), rverts(0), nrverts(0) { }
-       inline ~rcContour() { delete [] verts; delete [] rverts; }
-       int* verts;                     // Vertex coordinates, each vertex contains 4 components.
-       int nverts;                     // Number of vertices.
-       int* rverts;            // Raw vertex coordinates, each vertex contains 4 components.
-       int nrverts;            // Number of raw vertices.
-       unsigned short reg;     // Region ID of the contour.
+       int* verts;                     ///< Simplified contour vertex and connection data. [Size: 4 * #nverts]
+       int nverts;                     ///< The number of vertices in the simplified contour. 
+       int* rverts;            ///< Raw contour vertex and connection data. [Size: 4 * #nrverts]
+       int nrverts;            ///< The number of vertices in the raw contour. 
+       unsigned short reg;     ///< The region id of the contour.
+       unsigned char area;     ///< The area id of the contour.
 };
 
+/// Represents a group of related contours.
+/// @ingroup recast
 struct rcContourSet
 {
-       inline rcContourSet() : conts(0), nconts(0) {}
-       inline ~rcContourSet() { delete [] conts; }
-       rcContour* conts;               // Pointer to all contours.
-       int nconts;                             // Number of contours.
-       float bmin[3], bmax[3]; // Bounding box of the heightfield.
-       float cs, ch;                   // Cell size and height.
+       rcContour* conts;       ///< An array of the contours in the set. [Size: #nconts]
+       int nconts;                     ///< The number of contours in the set.
+       float bmin[3];          ///< The minimum bounds in world space. [(x, y, z)]
+       float bmax[3];          ///< The maximum bounds in world space. [(x, y, z)]
+       float cs;                   ///< The size of each cell. (On the xz-plane.)
+       float ch;                       ///< The height of each cell. (The minimum increment along the y-axis.)
+       int width;                  ///< The width of the set. (Along the x-axis in cell units.) 
+       int height;                 ///< The height of the set. (Along the z-axis in cell units.) 
+       int borderSize;         ///< The AABB border size used to generate the source data from which the contours were derived.
 };
 
-// Polymesh store a connected mesh of polygons.
-// The polygons are store in an array where each polygons takes
-// 'nvp*2' elements. The first 'nvp' elements are indices to vertices
-// and the second 'nvp' elements are indices to neighbour polygons.
-// If a polygona has less than 'bvp' vertices, the remaining indices
-// are set os 0xffff. If an polygon edge does not have a neighbour
-// the neighbour index is set to 0xffff.
-// Vertices can be transformed into world space as follows:
-//   x = bmin[0] + verts[i*3+0]*cs;
-//   y = bmin[1] + verts[i*3+1]*ch;
-//   z = bmin[2] + verts[i*3+2]*cs;
+/// Represents a polygon mesh suitable for use in building a navigation mesh. 
+/// @ingroup recast
 struct rcPolyMesh
-{
-       inline rcPolyMesh() : verts(0), polys(0), regs(0), nverts(0), npolys(0), nvp(3) {}
-       inline ~rcPolyMesh() { delete [] verts; delete [] polys; delete [] regs; }
-       unsigned short* verts;  // Vertices of the mesh, 3 elements per vertex.
-       unsigned short* polys;  // Polygons of the mesh, nvp*2 elements per polygon.
-       unsigned short* regs;   // Regions of the polygons.
-       int nverts;                             // Number of vertices.
-       int npolys;                             // Number of polygons.
-       int nvp;                                // Max number of vertices per polygon.
-       float bmin[3], bmax[3]; // Bounding box of the mesh.
-       float cs, ch;                   // Cell size and height.
+{      
+       unsigned short* verts;  ///< The mesh vertices. [Form: (x, y, z) * #nverts]
+       unsigned short* polys;  ///< Polygon and neighbor data. [Length: #maxpolys * 2 * #nvp]
+       unsigned short* regs;   ///< The region id assigned to each polygon. [Length: #maxpolys]
+       unsigned short* flags;  ///< The user defined flags for each polygon. [Length: #maxpolys]
+       unsigned char* areas;   ///< The area id assigned to each polygon. [Length: #maxpolys]
+       int nverts;                             ///< The number of vertices.
+       int npolys;                             ///< The number of polygons.
+       int maxpolys;                   ///< The number of allocated polygons.
+       int nvp;                                ///< The maximum number of vertices per polygon.
+       float bmin[3];              ///< The minimum bounds in world space. [(x, y, z)]
+       float bmax[3];              ///< The maximum bounds in world space. [(x, y, z)]
+       float cs;                           ///< The size of each cell. (On the xz-plane.)
+       float ch;                               ///< The height of each cell. (The minimum increment along the y-axis.)
+       int borderSize;                 ///< The AABB border size used to generate the source data from which the mesh was derived.
 };
 
-// Detail mesh generated from a rcPolyMesh.
-// Each submesh represents a polygon in the polymesh and they are stored in
-// excatly same order. Each submesh is described as 4 values:
-// base vertex, vertex count, base triangle, triangle count. That is,
-//   const unsigned char* t = &dtl.tris[(tbase+i)*3]; and
-//   const float* v = &dtl.verts[(vbase+t[j])*3];
-// If the input polygon has 'n' vertices, those vertices are first in the
-// submesh vertex list. This allows to compres the mesh by not storing the
-// first vertices and using the polymesh vertices instead.
-
+/// Contains triangle meshes that represent detailed height data associated 
+/// with the polygons in its associated polygon mesh object.
+/// @ingroup recast
 struct rcPolyMeshDetail
 {
-       inline rcPolyMeshDetail() :
-               meshes(0), verts(0), tris(0),
-               nmeshes(0), nverts(0), ntris(0) {}
-       inline ~rcPolyMeshDetail()
-       {
-               delete [] meshes; delete [] verts; delete [] tris;
-       }
-       
-       unsigned short* meshes; // Pointer to all mesh data.
-       float* verts;                   // Pointer to all vertex data.
-       unsigned char* tris;    // Pointer to all triangle data.
-       int nmeshes;                    // Number of meshes.
-       int nverts;                             // Number of total vertices.
-       int ntris;                              // Number of triangles.
+    unsigned int* meshes;      ///< The sub-mesh data. [Size: 4*#nmeshes] 
+    float* verts;                      ///< The mesh vertices. [Size: 3*#nverts] 
+    unsigned char* tris;       ///< The mesh triangles. [Size: 4*#ntris] 
+    int nmeshes;                       ///< The number of sub-meshes defined by #meshes.
+    int nverts;                                ///< The number of vertices in #verts.
+    int ntris;                         ///< The number of triangles in #tris.
 };
 
+/// @name Allocation Functions
+/// Functions used to allocate and de-allocate Recast objects.
+/// @see rcAllocSetCustom
+/// @{
 
-// Simple dynamic array ints.
-class rcIntArray
-{
-       int* m_data;
-       int m_size, m_cap;
-public:
-       inline rcIntArray() : m_data(0), m_size(0), m_cap(0) {}
-       inline rcIntArray(int n) : m_data(0), m_size(0), m_cap(n) { m_data = new int[n]; }
-       inline ~rcIntArray() { delete [] m_data; }
-       void resize(int n);
-       inline void push(int item) { resize(m_size+1); m_data[m_size-1] = item; }
-       inline int pop() { if (m_size > 0) m_size--; return m_data[m_size]; }
-       inline const int& operator[](int i) const { return m_data[i]; }
-       inline int& operator[](int i) { return m_data[i]; }
-       inline int size() const { return m_size; }
-};
+/// Allocates a heightfield object using the Recast allocator.
+///  @return A heightfield that is ready for initialization, or null on failure.
+///  @ingroup recast
+///  @see rcCreateHeightfield, rcFreeHeightField
+rcHeightfield* rcAllocHeightfield();
 
-enum rcSpanFlags
-{
-       RC_WALKABLE = 0x01,
-       RC_REACHABLE = 0x02,
-};
+/// Frees the specified heightfield object using the Recast allocator.
+///  @param[in] hf  A heightfield allocated using #rcAllocHeightfield
+///  @ingroup recast
+///  @see rcAllocHeightfield
+void rcFreeHeightField(rcHeightfield* hf);
+
+/// Allocates a compact heightfield object using the Recast allocator.
+///  @return A compact heightfield that is ready for initialization, or null on failure.
+///  @ingroup recast
+///  @see rcBuildCompactHeightfield, rcFreeCompactHeightfield
+rcCompactHeightfield* rcAllocCompactHeightfield();
+
+/// Frees the specified compact heightfield object using the Recast allocator.
+///  @param[in] chf  A compact heightfield allocated using #rcAllocCompactHeightfield
+///  @ingroup recast
+///  @see rcAllocCompactHeightfield
+void rcFreeCompactHeightfield(rcCompactHeightfield* chf);
+
+/// Allocates a heightfield layer set using the Recast allocator.
+///  @return A heightfield layer set that is ready for initialization, or null on failure.
+///  @ingroup recast
+///  @see rcBuildHeightfieldLayers, rcFreeHeightfieldLayerSet
+rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet();
+
+/// Frees the specified heightfield layer set using the Recast allocator.
+///  @param[in] lset  A heightfield layer set allocated using #rcAllocHeightfieldLayerSet
+///  @ingroup recast
+///  @see rcAllocHeightfieldLayerSet
+void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset);
+
+/// Allocates a contour set object using the Recast allocator.
+///  @return A contour set that is ready for initialization, or null on failure.
+///  @ingroup recast
+///  @see rcBuildContours, rcFreeContourSet
+rcContourSet* rcAllocContourSet();
+
+/// Frees the specified contour set using the Recast allocator.
+///  @param[in] cset  A contour set allocated using #rcAllocContourSet
+///  @ingroup recast
+///  @see rcAllocContourSet
+void rcFreeContourSet(rcContourSet* cset);
+
+/// Allocates a polygon mesh object using the Recast allocator.
+///  @return A polygon mesh that is ready for initialization, or null on failure.
+///  @ingroup recast
+///  @see rcBuildPolyMesh, rcFreePolyMesh
+rcPolyMesh* rcAllocPolyMesh();
+
+/// Frees the specified polygon mesh using the Recast allocator.
+///  @param[in] pmesh  A polygon mesh allocated using #rcAllocPolyMesh
+///  @ingroup recast
+///  @see rcAllocPolyMesh
+void rcFreePolyMesh(rcPolyMesh* pmesh);
+
+/// Allocates a detail mesh object using the Recast allocator.
+///  @return A detail mesh that is ready for initialization, or null on failure.
+///  @ingroup recast
+///  @see rcBuildPolyMeshDetail, rcFreePolyMeshDetail
+rcPolyMeshDetail* rcAllocPolyMeshDetail();
+
+/// Frees the specified detail mesh using the Recast allocator.
+///  @param[in] dmesh  A detail mesh allocated using #rcAllocPolyMeshDetail
+///  @ingroup recast
+///  @see rcAllocPolyMeshDetail
+void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh);
 
-// If heightfield region ID has the following bit set, the region is on border area
-// and excluded from many calculations.
+/// @}
+
+/// Heighfield border flag.
+/// If a heightfield region ID has this bit set, then the region is a border 
+/// region and its spans are considered unwalkable.
+/// (Used during the region and contour build process.)
+/// @see rcCompactSpan::reg
 static const unsigned short RC_BORDER_REG = 0x8000;
 
-// If contour region ID has the following bit set, the vertex will be later
-// removed in order to match the segments and vertices at tile boundaries.
+/// Border vertex flag.
+/// If a region ID has this bit set, then the associated element lies on
+/// a tile border. If a contour vertex's region ID has this bit set, the 
+/// vertex will later be removed in order to match the segments and vertices 
+/// at tile boundaries.
+/// (Used during the build process.)
+/// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts
 static const int RC_BORDER_VERTEX = 0x10000;
 
-// Compact span neighbour helpers.
-inline int rcGetCon(const rcCompactSpan& s, int dir)
-{
-       return (s.con >> (dir*4)) & 0xf;
-}
+/// Area border flag.
+/// If a region ID has this bit set, then the associated element lies on
+/// the border of an area.
+/// (Used during the region and contour build process.)
+/// @see rcCompactSpan::reg, #rcContour::verts, #rcContour::rverts
+static const int RC_AREA_BORDER = 0x20000;
 
-inline int rcGetDirOffsetX(int dir)
+/// Contour build flags.
+/// @see rcBuildContours
+enum rcBuildContoursFlags
 {
-       const int offset[4] = { -1, 0, 1, 0, };
-       return offset[dir&0x03];
-}
+       RC_CONTOUR_TESS_WALL_EDGES = 0x01,      ///< Tessellate solid (impassable) edges during contour simplification.
+       RC_CONTOUR_TESS_AREA_EDGES = 0x02,      ///< Tessellate edges between areas during contour simplification.
+};
 
-inline int rcGetDirOffsetY(int dir)
-{
-       const int offset[4] = { 0, 1, 0, -1 };
-       return offset[dir&0x03];
-}
+/// Applied to the region id field of contour vertices in order to extract the region id.
+/// The region id field of a vertex may have several flags applied to it.  So the
+/// fields value can't be used directly.
+/// @see rcContour::verts, rcContour::rverts
+static const int RC_CONTOUR_REG_MASK = 0xffff;
+
+/// An value which indicates an invalid index within a mesh.
+/// @note This does not necessarily indicate an error.
+/// @see rcPolyMesh::polys
+static const unsigned short RC_MESH_NULL_IDX = 0xffff;
+
+/// Represents the null area.
+/// When a data element is given this value it is considered to no longer be 
+/// assigned to a usable area.  (E.g. It is unwalkable.)
+static const unsigned char RC_NULL_AREA = 0;
+
+/// The default area id used to indicate a walkable polygon. 
+/// This is also the maximum allowed area id, and the only non-null area id 
+/// recognized by some steps in the build process. 
+static const unsigned char RC_WALKABLE_AREA = 63;
+
+/// The value returned by #rcGetCon if the specified direction is not connected
+/// to another span. (Has no neighbor.)
+static const int RC_NOT_CONNECTED = 0x3f;
+
+/// @name General helper functions
+/// @{
 
-// Common helper functions
+/// Swaps the values of the two parameters.
+///  @param[in,out] a  Value A
+///  @param[in,out] b  Value B
 template<class T> inline void rcSwap(T& a, T& b) { T t = a; a = b; b = t; }
+
+/// Returns the minimum of two values.
+///  @param[in] a  Value A
+///  @param[in] b  Value B
+///  @return The minimum of the two values.
 template<class T> inline T rcMin(T a, T b) { return a < b ? a : b; }
+
+/// Returns the maximum of two values.
+///  @param[in] a  Value A
+///  @param[in] b  Value B
+///  @return The maximum of the two values.
 template<class T> inline T rcMax(T a, T b) { return a > b ? a : b; }
+
+/// Returns the absolute value.
+///  @param[in] a  The value.
+///  @return The absolute value of the specified value.
 template<class T> inline T rcAbs(T a) { return a < 0 ? -a : a; }
+
+/// Return the square of a value.
+///  @param[in] a  The value.
+///  @return The square of the value.
 template<class T> inline T rcSqr(T a) { return a*a; }
+
+/// Clamps the value to the specified range.
+///  @param[in] v   The value to clamp.
+///  @param[in] mn  The minimum permitted return value.
+///  @param[in] mx  The maximum permitted return value.
+///  @return The value, clamped to the specified range.
 template<class T> inline T rcClamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); }
 
-// Common vector helper functions.
-inline void vcross(float* dest, const float* v1, const float* v2)
+/// Returns the square root of the value.
+///  @param[in] x  The value.
+///  @return The square root of the vlaue.
+float rcSqrt(float x);
+
+/// Not documented.  Internal use only.
+///  @param[in] x  Not documented.
+///  @return Not documented.
+inline int rcAlign4(int x) { return (x+3) & ~3; }
+
+/// @}
+/// @name Vector helper functions.
+/// @{
+
+/// Derives the cross product of two vectors. (v1 x v2)
+///   @param[out] dest  The cross product. [(x, y, z)]
+///   @param[in]  v1    A Vector [(x, y, z)]
+///   @param[in]  v2    A vector [(x, y, z)]
+inline void rcVcross(float* dest, const float* v1, const float* v2)
 {
        dest[0] = v1[1]*v2[2] - v1[2]*v2[1];
        dest[1] = v1[2]*v2[0] - v1[0]*v2[2];
-       dest[2] = v1[0]*v2[1] - v1[1]*v2[0]; 
+       dest[2] = v1[0]*v2[1] - v1[1]*v2[0];
 }
 
-inline float vdot(const float* v1, const float* v2)
+/// Derives the dot product of two vectors. (v1 . v2)
+///   @param[in]  v1    A Vector [(x, y, z)]
+///   @param[in]  v2    A vector [(x, y, z)]
+///   @return The dot product.
+inline float rcVdot(const float* v1, const float* v2)
 {
        return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
 }
 
-inline void vmad(float* dest, const float* v1, const float* v2, const float s)
+/// Performs a scaled vector addition. (v1 + (v2 * s))
+///   @param[out] dest  The result vector. [(x, y, z)]
+///   @param[in]  v1    The base vector [(x, y, z)]
+///   @param[in]  v2    The vector to scale and add to @p v1. [(x, y, z)]
+///   @param[in]  s     The amount to scale @p v2 by before adding to @p v1.
+inline void rcVmad(float* dest, const float* v1, const float* v2, const float s)
 {
        dest[0] = v1[0]+v2[0]*s;
        dest[1] = v1[1]+v2[1]*s;
        dest[2] = v1[2]+v2[2]*s;
 }
 
-inline void vadd(float* dest, const float* v1, const float* v2)
+/// Performs a vector addition. (@p v1 + @p v2)
+///   @param[out] dest  The result vector. [(x, y, z)]
+///   @param[in]  v1    The base vector [(x, y, z)]
+///   @param[in]  v2    The vector to add to @p v1. [(x, y, z)]
+inline void rcVadd(float* dest, const float* v1, const float* v2)
 {
        dest[0] = v1[0]+v2[0];
        dest[1] = v1[1]+v2[1];
        dest[2] = v1[2]+v2[2];
 }
 
-inline void vsub(float* dest, const float* v1, const float* v2)
+/// Performs a vector subtraction. (@p v1 - @p v2)
+///   @param[out] dest  The result vector. [(x, y, z)]
+///   @param[in]  v1    The base vector [(x, y, z)]
+///   @param[in]  v2    The vector to subtract from @p v1. [(x, y, z)]
+inline void rcVsub(float* dest, const float* v1, const float* v2)
 {
        dest[0] = v1[0]-v2[0];
        dest[1] = v1[1]-v2[1];
        dest[2] = v1[2]-v2[2];
 }
 
-inline void vmin(float* mn, const float* v)
+/// Selects the minimum value of each element from the specified vectors.
+///  @param[in, out] mn  A vector.  (Will be updated with the result.) [(x, y, z)]
+///  @param[in]      v   A vector. [(x, y, z)]
+inline void rcVmin(float* mn, const float* v)
 {
        mn[0] = rcMin(mn[0], v[0]);
        mn[1] = rcMin(mn[1], v[1]);
        mn[2] = rcMin(mn[2], v[2]);
 }
 
-inline void vmax(float* mx, const float* v)
+/// Selects the maximum value of each element from the specified vectors.
+///  @param[in, out] mx  A vector.  (Will be updated with the result.) [(x, y, z)]
+///  @param[in]      v   A vector. [(x, y, z)]
+inline void rcVmax(float* mx, const float* v)
 {
        mx[0] = rcMax(mx[0], v[0]);
        mx[1] = rcMax(mx[1], v[1]);
        mx[2] = rcMax(mx[2], v[2]);
 }
 
-inline void vcopy(float* dest, const float* v)
+/// Performs a vector copy.
+///  @param[out] dest  The result. [(x, y, z)]
+///  @param[in]  v     The vector to copy [(x, y, z)]
+inline void rcVcopy(float* dest, const float* v)
 {
        dest[0] = v[0];
        dest[1] = v[1];
        dest[2] = v[2];
 }
 
-inline float vdist(const float* v1, const float* v2)
+/// Returns the distance between two points.
+///   @param[in] v1  A point. [(x, y, z)]
+///   @param[in] v2  A point. [(x, y, z)]
+///   @return The distance between the two points.
+inline float rcVdist(const float* v1, const float* v2)
 {
        float dx = v2[0] - v1[0];
        float dy = v2[1] - v1[1];
        float dz = v2[2] - v1[2];
-       return sqrtf(dx*dx + dy*dy + dz*dz);
+       return rcSqrt(dx*dx + dy*dy + dz*dz);
 }
 
-inline float vdistSqr(const float* v1, const float* v2)
+/// Returns the square of the distance between two points.
+///   @param[in] v1  A point. [(x, y, z)]
+///   @param[in] v2  A point. [(x, y, z)]
+///   @return The square of the distance between the two points.
+inline float rcVdistSqr(const float* v1, const float* v2)
 {
        float dx = v2[0] - v1[0];
        float dy = v2[1] - v1[1];
@@ -318,184 +705,424 @@ inline float vdistSqr(const float* v1, const float* v2)
        return dx*dx + dy*dy + dz*dz;
 }
 
-inline void vnormalize(float* v)
+/// Normalizes the vector.
+///  @param[in,out] v  The vector to normalize. [(x, y, z)]
+inline void rcVnormalize(float* v)
 {
-       float d = 1.0f / sqrtf(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2]));
+       float d = 1.0f / rcSqrt(rcSqr(v[0]) + rcSqr(v[1]) + rcSqr(v[2]));
        v[0] *= d;
        v[1] *= d;
        v[2] *= d;
 }
 
-inline bool vequal(const float* p0, const float* p1)
+/// Not documented.  Internal use only.
+///  @param[in] p0  Not documented.
+///  @param[in] p1  Not documented.
+///  @return Not documented.
+inline bool rcVequal(const float* p0, const float* p1)
 {
        static const float thr = rcSqr(1.0f/16384.0f);
-       const float d = vdistSqr(p0, p1);
+       const float d = rcVdistSqr(p0, p1);
        return d < thr;
 }
 
+/// @}
+/// @name Heightfield Functions
+/// @see rcHeightfield
+/// @{
 
-// Calculated bounding box of array of vertices.
-// Params:
-//     verts - (in) array of vertices
-//     nv - (in) vertex count
-//     bmin, bmax - (out) bounding box
+/// Calculates the bounding box of an array of vertices.
+///  @ingroup recast
+///  @param[in]  verts  An array of vertices. [(x, y, z) * @p nv]
+///  @param[in]  nv     The number of vertices in the @p verts array.
+///  @param[out] bmin   The minimum bounds of the AABB. [(x, y, z)] [Units: wu]
+///  @param[out] bmax   The maximum bounds of the AABB. [(x, y, z)] [Units: wu]
 void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax);
 
-// Calculates grid size based on bounding box and grid cell size.
-// Params:
-//     bmin, bmax - (in) bounding box
-//     cs - (in) grid cell size
-//     w - (out) grid width
-//     h - (out) grid height
+/// Calculates the grid size based on the bounding box and grid cell size.
+///  @ingroup recast
+///  @param[in]  bmin  The minimum bounds of the AABB. [(x, y, z)] [Units: wu]
+///  @param[in]  bmax  The maximum bounds of the AABB. [(x, y, z)] [Units: wu]
+///  @param[in]  cs    The xz-plane cell size. [Limit: > 0] [Units: wu]
+///  @param[out] w     The width along the x-axis. [Limit: >= 0] [Units: vx]
+///  @param[out] h     The height along the z-axis. [Limit: >= 0] [Units: vx]
 void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h);
 
-// Creates and initializes new heightfield.
-// Params:
-//     hf - (in/out) heightfield to initialize.
-//     width - (in) width of the heightfield.
-//     height - (in) height of the heightfield.
-//     bmin, bmax - (in) bounding box of the heightfield
-//     cs - (in) grid cell size
-//     ch - (in) grid cell height
-bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
+/// Initializes a new heightfield.
+///  @ingroup recast
+///  @param[in,out] ctx     The build context to use during the operation.
+///  @param[in,out] hf      The allocated heightfield to initialize.
+///  @param[in]     width   The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
+///  @param[in]     height  The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
+///  @param[in]     bmin    The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
+///  @param[in]     bmax    The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
+///  @param[in]     cs      The xz-plane cell size to use for the field. [Limit: > 0] [Units: wu]
+///  @param[in]     ch      The y-axis cell size to use for field. [Limit: > 0] [Units: wu]
+bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height,
                                                 const float* bmin, const float* bmax,
                                                 float cs, float ch);
 
-// Sets the WALKABLE flag for every triangle whose slope is below
-// the maximun walkable slope angle.
-// Params:
-//     walkableSlopeAngle - (in) maximun slope angle in degrees.
-//     verts - (in) array of vertices
-//     nv - (in) vertex count
-//     tris - (in) array of triangle vertex indices
-//     nt - (in) triangle count
-//     flags - (out) array of triangle flags
-void rcMarkWalkableTriangles(const float walkableSlopeAngle,
-                                                        const float* verts, int nv,
-                                                        const int* tris, int nt,
-                                                        unsigned char* flags); 
-
-// Rasterizes a triangle into heightfield spans.
-// Params:
-//     v0,v1,v2 - (in) the vertices of the triangle.
-//     flags - (in) triangle flags (uses WALKABLE)
-//     solid - (in) heighfield where the triangle is rasterized
-void rcRasterizeTriangle(const float* v0, const float* v1, const float* v2,
-                                                unsigned char flags, rcHeightfield& solid);
-
-// Rasterizes the triangles into heightfield spans.
-// Params:
-//     verts - (in) array of vertices
-//     nv - (in) vertex count
-//     tris - (in) array of triangle vertex indices
-//     norms - (in) array of triangle normals
-//     flags - (in) array of triangle flags (uses WALKABLE)
-//     nt - (in) triangle count
-//     solid - (in) heighfield where the triangles are rasterized
-void rcRasterizeTriangles(const float* verts, int nv,
-                                                 const int* tris, const unsigned char* flags, int nt,
-                                                 rcHeightfield& solid);
-
-// Removes WALKABLE flag from all spans that are at ledges. This filtering
-// removes possible overestimation of the conservative voxelization so that
-// the resulting mesh will not have regions hanging in air over ledges.
-// Params:
-//     walkableHeight - (in) minimum height where the agent can still walk
-//     walkableClimb - (in) maximum height between grid cells the agent can climb
-//     solid - (in/out) heightfield describing the solid space
-void rcFilterLedgeSpans(const int walkableHeight,
-                                               const int walkableClimb,
-                                               rcHeightfield& solid);
-
-// Removes WALKABLE flag from all spans which have smaller than
-// 'walkableHeight' clearane above them.
-// Params:
-//     walkableHeight - (in) minimum height where the agent can still walk
-//     solid - (in/out) heightfield describing the solid space
-void rcFilterWalkableLowHeightSpans(int walkableHeight,
-                                                                       rcHeightfield& solid);
-
-// Marks spans which are reachable from any of the topmost spans.
-// Params:
-//     walkableHeight - (in) minimum height where the agent can still walk
-//     walkableClimb - (in) maximum height between grid cells the agent can climb
-//     solid - (in/out) heightfield describing the solid space
-// Returns false if operation ran out of memory.
-bool rcMarkReachableSpans(const int walkableHeight,
-                                                 const int walkableClimb,
-                                                 rcHeightfield& solid);
-
-// Builds compact representation of the heightfield.
-// Params:
-//     walkableHeight - (in) minimum height where the agent can still walk
-//     walkableClimb - (in) maximum height between grid cells the agent can climb
-//     hf - (in) heightfield to be compacted
-//     chf - (out) compact heightfield representing the open space.
-// Returns false if operation ran out of memory.
-bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb,
-                                                          unsigned char flags,
-                                                          rcHeightfield& hf,
-                                                          rcCompactHeightfield& chf);
-
-// Builds distance field and stores it into the combat heightfield.
-// Params:
-//     chf - (in/out) compact heightfield representing the open space.
-// Returns false if operation ran out of memory.
-bool rcBuildDistanceField(rcCompactHeightfield& chf);
-
-// Divides the walkable heighfied into simple regions.
-// Each region has only one contour and no overlaps.
-// The regions are stored in the compact heightfield 'reg' field.
-// The regions will be shrinked by the radius of the agent.
-// The process sometimes creates small regions. The parameter
-// 'minRegionSize' specifies the smallest allowed regions size.
-// If the area of a regions is smaller than allowed, the regions is
-// removed or merged to neighbour region. 
-// Params:
-//     chf - (in/out) compact heightfield representing the open space.
-//     walkableRadius - (in) the radius of the agent.
-//     minRegionSize - (in) the smallest allowed regions size.
-//     maxMergeRegionSize - (in) the largest allowed regions size which can be merged.
-// Returns false if operation ran out of memory.
-bool rcBuildRegions(rcCompactHeightfield& chf,
-                                       int walkableRadius, int borderSize,
-                                       int minRegionSize, int mergeRegionSize);
-
-// Builds simplified contours from the regions outlines.
-// Params:
-//     chf - (in) compact heightfield which has regions set.
-//     maxError - (in) maximum allowed distance between simplified countour and cells.
-//     maxEdgeLen - (in) maximum allowed contour edge length in cells.
-//     cset - (out) Resulting contour set.
-// Returns false if operation ran out of memory.
-bool rcBuildContours(rcCompactHeightfield& chf,
+/// Sets the area id of all triangles with a slope below the specified value
+/// to #RC_WALKABLE_AREA.
+///  @ingroup recast
+///  @param[in,out] ctx                 The build context to use during the operation.
+///  @param[in]     walkableSlopeAngle  The maximum slope that is considered walkable. [Limits: 0 <= value < 90] 
+///                                     [Units: Degrees]
+///  @param[in]     verts               The vertices. [(x, y, z) * @p nv]
+///  @param[in]     nv                  The number of vertices.
+///  @param[in]     tris                The triangle vertex indices. [(vertA, vertB, vertC) * @p nt]
+///  @param[in]     nt                  The number of triangles.
+///  @param[out]    areas               The triangle area ids. [Length: >= @p nt]
+void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv,
+                                                        const int* tris, int nt, unsigned char* areas); 
+
+/// Sets the area id of all triangles with a slope greater than or equal to the specified value to #RC_NULL_AREA.
+///  @ingroup recast
+///  @param[in,out] ctx                 The build context to use during the operation.
+///  @param[in]     walkableSlopeAngle  The maximum slope that is considered walkable. [Limits: 0 <= value < 90] 
+///                                     [Units: Degrees]
+///  @param[in]     verts               The vertices. [(x, y, z) * @p nv]
+///  @param[in]     nv                  The number of vertices.
+///  @param[in]     tris                The triangle vertex indices. [(vertA, vertB, vertC) * @p nt]
+///  @param[in]     nt                  The number of triangles.
+///  @param[out]    areas               The triangle area ids. [Length: >= @p nt]
+void rcClearUnwalkableTriangles(rcContext* ctx, const float walkableSlopeAngle, const float* verts, int nv,
+                                                               const int* tris, int nt, unsigned char* areas); 
+
+/// Adds a span to the specified heightfield.
+///  @ingroup recast
+///  @param[in,out] ctx           The build context to use during the operation.
+///  @param[in,out] hf            An initialized heightfield.      
+///  @param[in]     x             The width index where the span is to be added. 
+///                               [Limits: 0 <= value < rcHeightfield::width]
+///  @param[in]     y             The height index where the span is to be added. 
+///                               [Limits: 0 <= value < rcHeightfield::height]
+///  @param[in]     smin          The minimum height of the span. [Limit: < @p smax] [Units: vx]
+///  @param[in]     smax          The maximum height of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT] [Units: vx]
+///  @param[in]     area          The area id of the span. [Limit: <= #RC_WALKABLE_AREA)
+///  @param[in]     flagMergeThr  The merge theshold. [Limit: >= 0] [Units: vx]
+void rcAddSpan(rcContext* ctx, rcHeightfield& hf, const int x, const int y,
+                          const unsigned short smin, const unsigned short smax,
+                          const unsigned char area, const int flagMergeThr);
+
+/// Rasterizes a triangle into the specified heightfield.
+///  @ingroup recast
+///  @param[in,out]  ctx           The build context to use during the operation.
+///  @param[in]      v0            Triangle vertex 0 [(x, y, z)]
+///  @param[in]      v1            Triangle vertex 1 [(x, y, z)]
+///  @param[in]      v2            Triangle vertex 2 [(x, y, z)]
+///  @param[in]      area          The area id of the triangle. [Limit: <= #RC_WALKABLE_AREA]
+///  @param[in, out] solid         An initialized heightfield.
+///  @param[in]      flagMergeThr  The distance where the walkable flag is favored over the non-walkable flag. 
+///                                [Limit: >= 0] [Units: vx]
+void rcRasterizeTriangle(rcContext* ctx, const float* v0, const float* v1, const float* v2,
+                                                const unsigned char area, rcHeightfield& solid,
+                                                const int flagMergeThr = 1);
+
+/// Rasterizes an indexed triangle mesh into the specified heightfield.
+///  @ingroup recast
+///  @param[in,out]  ctx           The build context to use during the operation.
+///  @param[in]      verts         The vertices. [(x, y, z) * @p nv]
+///  @param[in]      nv            The number of vertices.
+///  @param[in]      tris          The triangle indices. [(vertA, vertB, vertC) * @p nt]
+///  @param[in]      areas         The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
+///  @param[in]      nt            The number of triangles.
+///  @param[in, out] solid         An initialized heightfield.
+///  @param[in]      flagMergeThr  The distance where the walkable flag is favored over the non-walkable flag. 
+///                                [Limit: >= 0] [Units: vx]
+void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv,
+                                                 const int* tris, const unsigned char* areas, const int nt,
+                                                 rcHeightfield& solid, const int flagMergeThr = 1);
+
+/// Rasterizes an indexed triangle mesh into the specified heightfield.
+///  @ingroup recast
+///  @param[in,out]  ctx           The build context to use during the operation.
+///  @param[in]      verts         The vertices. [(x, y, z) * @p nv]
+///  @param[in]      nv            The number of vertices.
+///  @param[in]      tris          The triangle indices. [(vertA, vertB, vertC) * @p nt]
+///  @param[in]      areas         The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
+///  @param[in]      nt            The number of triangles.
+///  @param[in, out] solid         An initialized heightfield.
+///  @param[in]      flagMergeThr  The distance where the walkable flag is favored over the non-walkable flag. 
+///                                [Limit: >= 0] [Units: vx]
+void rcRasterizeTriangles(rcContext* ctx, const float* verts, const int nv,
+                                                 const unsigned short* tris, const unsigned char* areas, const int nt,
+                                                 rcHeightfield& solid, const int flagMergeThr = 1);
+
+/// Rasterizes triangles into the specified heightfield.
+///  @ingroup recast
+///  @param[in,out]  ctx           The build context to use during the operation.
+///  @param[in]      verts         The triangle vertices. [(ax, ay, az, bx, by, bz, cx, by, cx) * @p nt]
+///  @param[in]      areas         The area id's of the triangles. [Limit: <= #RC_WALKABLE_AREA] [Size: @p nt]
+///  @param[in]      nt            The number of triangles.
+///  @param[in, out] solid         An initialized heightfield.
+///  @param[in]      flagMergeThr  The distance where the walkable flag is favored over the non-walkable flag. 
+///                                [Limit: >= 0] [Units: vx]
+void rcRasterizeTriangles(rcContext* ctx, const float* verts, const unsigned char* areas, const int nt,
+                                                 rcHeightfield& solid, const int flagMergeThr = 1);
+
+/// Marks non-walkable spans as walkable if their maximum is within @p walkableClimp of a walkable neihbor. 
+///  @ingroup recast
+///  @param[in,out] ctx            The build context to use during the operation.
+///  @param[in]     walkableClimb  Maximum ledge height that is considered to still be traversable. 
+///                                [Limit: >=0] [Units: vx]
+///  @param[in,out] solid          A fully built heightfield.  (All spans have been added.)
+void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid);
+
+/// Marks spans that are ledges as not-walkable. 
+///  @ingroup recast
+///  @param[in,out] ctx             The build context to use during the operation.
+///  @param[in]     walkableHeight  Minimum floor to 'ceiling' height that will still allow the floor area to 
+///                                 be considered walkable. [Limit: >= 3] [Units: vx]
+///  @param[in]     walkableClimb   Maximum ledge height that is considered to still be traversable. 
+///                                 [Limit: >=0] [Units: vx]
+///  @param[in,out] solid          A fully built heightfield.  (All spans have been added.)
+void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight,
+                                               const int walkableClimb, rcHeightfield& solid);
+
+/// Marks walkable spans as not walkable if the clearence above the span is less than the specified height. 
+///  @ingroup recast
+///  @param[in,out] ctx             The build context to use during the operation.
+///  @param[in]     walkableHeight  Minimum floor to 'ceiling' height that will still allow the floor area to 
+///                                 be considered walkable. [Limit: >= 3] [Units: vx]
+///  @param[in,out] solid           A fully built heightfield.  (All spans have been added.)
+void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid);
+
+/// Returns the number of spans contained in the specified heightfield.
+///  @ingroup recast
+///  @param[in,out] ctx  The build context to use during the operation.
+///  @param[in]     hf   An initialized heightfield.
+///  @returns The number of spans in the heightfield.
+int rcGetHeightFieldSpanCount(rcContext* ctx, rcHeightfield& hf);
+
+/// @}
+/// @name Compact Heightfield Functions
+/// @see rcCompactHeightfield
+/// @{
+
+/// Builds a compact heightfield representing open space, from a heightfield representing solid space.
+///  @ingroup recast
+///  @param[in,out] ctx             The build context to use during the operation.
+///  @param[in]     walkableHeight  Minimum floor to 'ceiling' height that will still allow the floor area 
+///                                 to be considered walkable. [Limit: >= 3] [Units: vx]
+///  @param[in]     walkableClimb   Maximum ledge height that is considered to still be traversable. 
+///                                 [Limit: >=0] [Units: vx]
+///  @param[in]     hf              The heightfield to be compacted.
+///  @param[out]    chf             The resulting compact heightfield. (Must be pre-allocated.)
+///  @returns True if the operation completed successfully.
+bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,
+                                                          rcHeightfield& hf, rcCompactHeightfield& chf);
+
+/// Erodes the walkable area within the heightfield by the specified radius. 
+///  @ingroup recast
+///  @param[in,out] ctx     The build context to use during the operation.
+///  @param[in]     radius  The radius of erosion. [Limits: 0 < value < 255] [Units: vx]
+///  @param[in,out] chf     The populated compact heightfield to erode.
+///  @returns True if the operation completed successfully.
+bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf);
+
+/// Applies a median filter to walkable area types (based on area id), removing noise.
+///  @ingroup recast
+///  @param[in,out] ctx  The build context to use during the operation.
+///  @param[in,out] chf  A populated compact heightfield.
+///  @returns True if the operation completed successfully.
+bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf);
+
+/// Applies an area id to all spans within the specified bounding box. (AABB) 
+///  @ingroup recast
+///  @param[in,out] ctx     The build context to use during the operation.
+///  @param[in]     bmin    The minimum of the bounding box. [(x, y, z)]
+///  @param[in]     bmax    The maximum of the bounding box. [(x, y, z)]
+///  @param[in]     areaId  The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
+///  @param[in,out] chf     A populated compact heightfield.
+void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId,
+                                  rcCompactHeightfield& chf);
+
+/// Applies the area id to the all spans within the specified convex polygon. 
+///  @ingroup recast
+///  @param[in,out] ctx     The build context to use during the operation.
+///  @param[in]     verts   The vertices of the polygon [Fomr: (x, y, z) * @p nverts]
+///  @param[in]     nverts  The number of vertices in the polygon.
+///  @param[in]     hmin    The height of the base of the polygon.
+///  @param[in]     hmax    The height of the top of the polygon.
+///  @param[in]     areaId  The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
+///  @param[in,out] chf     A populated compact heightfield.
+void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts,
+                                                 const float hmin, const float hmax, unsigned char areaId,
+                                                 rcCompactHeightfield& chf);
+
+/// Applies the area id to all spans within the specified cylinder.
+///  @ingroup recast
+///  @param[in,out] ctx     The build context to use during the operation.
+///  @param[in]     pos     The center of the base of the cylinder. [Form: (x, y, z)] 
+///  @param[in]     r       The radius of the cylinder.
+///  @param[in]     h       The height of the cylinder.
+///  @param[in]     areaId  The area id to apply. [Limit: <= #RC_WALKABLE_AREA]
+///  @param[in,out] chf     A populated compact heightfield.
+void rcMarkCylinderArea(rcContext* ctx, const float* pos,
+                                               const float r, const float h, unsigned char areaId,
+                                               rcCompactHeightfield& chf);
+
+/// Builds the distance field for the specified compact heightfield. 
+///  @ingroup recast
+///  @param[in,out] ctx  The build context to use during the operation.
+///  @param[in,out] chf  A populated compact heightfield.
+///  @returns True if the operation completed successfully.
+bool rcBuildDistanceField(rcContext* ctx, rcCompactHeightfield& chf);
+
+/// Builds region data for the heightfield using watershed partitioning. 
+///  @ingroup recast
+///  @param[in,out] ctx          The build context to use during the operation.
+///  @param[in,out] chf          A populated compact heightfield.
+///  @param[in] borderSize       The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
+///  @param[in] minRegionArea    The minimum number of cells allowed to form isolated island areas. [Limit: >=0] 
+///                              [Units: vx].
+///  @param[in] mergeRegionArea  Any regions with a span count smaller than this value will, if possible, 
+///                              be merged with larger regions. [Limit: >=0] [Units: vx] 
+///  @returns True if the operation completed successfully.
+bool rcBuildRegions(rcContext* ctx, rcCompactHeightfield& chf,
+                                       const int borderSize, const int minRegionArea, const int mergeRegionArea);
+
+/// Builds region data for the heightfield using simple monotone partitioning.
+///  @ingroup recast 
+///  @param[in,out] ctx          The build context to use during the operation.
+///  @param[in,out] chf          A populated compact heightfield.
+///  @param[in] borderSize       The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
+///  @param[in] minRegionArea    The minimum number of cells allowed to form isolated island areas. [Limit: >=0] 
+///                              [Units: vx].
+///  @param[in] mergeRegionArea  Any regions with a span count smaller than this value will, if possible, 
+///                              be merged with larger regions. [Limit: >=0] [Units: vx] 
+///  @returns True if the operation completed successfully.
+bool rcBuildRegionsMonotone(rcContext* ctx, rcCompactHeightfield& chf,
+                                                       const int borderSize, const int minRegionArea, const int mergeRegionArea);
+
+
+/// Sets the neighbor connection data for the specified direction.
+///  @param[in] s    The span to update.
+///  @param[in] dir  The direction to set. [Limits: 0 <= value < 4]
+///  @param[in] i    The index of the neighbor span.
+inline void rcSetCon(rcCompactSpan& s, int dir, int i)
+{
+       const unsigned int shift = (unsigned int)dir*6;
+       unsigned int con = s.con;
+       s.con = (con & ~(0x3f << shift)) | (((unsigned int)i & 0x3f) << shift);
+}
+
+/// Gets neighbor connection data for the specified direction.
+///  @param[in] s    The span to check.
+///  @param[in] dir  The direction to check. [Limits: 0 <= value < 4]
+///  @return The neighbor connection data for the specified direction,
+///          or #RC_NOT_CONNECTED if there is no connection.
+inline int rcGetCon(const rcCompactSpan& s, int dir)
+{
+       const unsigned int shift = (unsigned int)dir*6;
+       return (s.con >> shift) & 0x3f;
+}
+
+/// Gets the standard width (x-axis) offset for the specified direction.
+///  @param[in] dir  The direction. [Limits: 0 <= value < 4]
+///  @return The width offset to apply to the current cell position to move
+///          in the direction.
+inline int rcGetDirOffsetX(int dir)
+{
+       const int offset[4] = { -1, 0, 1, 0, };
+       return offset[dir&0x03];
+}
+
+/// Gets the standard height (z-axis) offset for the specified direction.
+///  @param[in] dir  The direction. [Limits: 0 <= value < 4]
+///  @return The height offset to apply to the current cell position to move
+///          in the direction.
+inline int rcGetDirOffsetY(int dir)
+{
+       const int offset[4] = { 0, 1, 0, -1 };
+       return offset[dir&0x03];
+}
+
+/// @}
+/// @name Layer, Contour, Polymesh, and Detail Mesh Functions
+/// @see rcHeightfieldLayer, rcContourSet, rcPolyMesh, rcPolyMeshDetail
+/// @{
+
+/// Builds a layer set from the specified compact heightfield.
+///  @ingroup recast
+///  @param[in,out] ctx             The build context to use during the operation.
+///  @param[in]     chf             A fully built compact heightfield.
+///  @param[in]     borderSize      The size of the non-navigable border around the heightfield. [Limit: >=0] 
+///                                 [Units: vx]
+///  @param[in]     walkableHeight  Minimum floor to 'ceiling' height that will still allow the floor area 
+///                                 to be considered walkable. [Limit: >= 3] [Units: vx]
+///  @param[out]    lset            The resulting layer set. (Must be pre-allocated.)
+///  @returns True if the operation completed successfully.
+bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf, 
+                                                         const int borderSize, const int walkableHeight,
+                                                         rcHeightfieldLayerSet& lset);
+
+/// Builds a contour set from the region outlines in the provided compact heightfield.
+///  @ingroup recast
+///  @param[in,out] ctx      The build context to use during the operation.
+///  @param[in] chf          A fully built compact heightfield.
+///  @param[in] maxError     The maximum distance a simplfied contour's border edges should deviate 
+///                          the original raw contour. [Limit: >=0] [Units: wu]
+///  @param[in] maxEdgeLen   The maximum allowed length for contour edges along the border of the mesh. 
+///                          [Limit: >=0] [Units: vx]
+///  @param[out] cset        The resulting contour set. (Must be pre-allocated.)
+///  @param[in]  buildFlags  The build flags. (See: #rcBuildContoursFlags)
+///  @returns True if the operation completed successfully.
+bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
                                         const float maxError, const int maxEdgeLen,
-                                        rcContourSet& cset);
-
-// Builds connected convex polygon mesh from contour polygons.
-// Params:
-//     cset - (in) contour set.
-//     nvp - (in) maximum number of vertices per polygon.
-//     mesh - (out) poly mesh.
-// Returns false if operation ran out of memory.
-bool rcBuildPolyMesh(rcContourSet& cset, int nvp, rcPolyMesh& mesh);
-
-bool rcMergePolyMeshes(rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh);
-
-// Builds detail triangle mesh for each polygon in the poly mesh.
-// Params:
-//     mesh - (in) poly mesh to detail.
-//     chf - (in) compacy height field, used to query height for new vertices.
-//  sampleDist - (in) spacing between height samples used to generate more detail into mesh.
-//  sampleMaxError - (in) maximum allowed distance between simplified detail mesh and height sample.
-//     pmdtl - (out) detail mesh.
-// Returns false if operation ran out of memory.
-bool rcBuildPolyMeshDetail(const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
+                                        rcContourSet& cset, const int flags = RC_CONTOUR_TESS_WALL_EDGES);
+
+/// Builds a polygon mesh from the provided contours.
+///  @ingroup recast
+///  @param[in,out] ctx     The build context to use during the operation.
+///  @param[in]     cset    A fully built contour set.
+///  @param[in]     nvp     The maximum number of vertices allowed for polygons generated during the 
+///                         contour to polygon conversion process. [Limit: >= 3] 
+///  @param[out]    mesh    The resulting polygon mesh. (Must be re-allocated.)
+///  @returns True if the operation completed successfully.
+bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh);
+
+/// Merges multiple polygon meshes into a single mesh.
+///  @ingroup recast
+///  @param[in,out] ctx      The build context to use during the operation.
+///  @param[in]     meshes   An array of polygon meshes to merge. [Size: @p nmeshes]
+///  @param[in]     nmeshes  The number of polygon meshes in the meshes array.
+///  @param[in]     mesh     The resulting polygon mesh. (Must be pre-allocated.)
+///  @returns True if the operation completed successfully.
+bool rcMergePolyMeshes(rcContext* ctx, rcPolyMesh** meshes, const int nmeshes, rcPolyMesh& mesh);
+
+/// Builds a detail mesh from the provided polygon mesh.
+///  @ingroup recast
+///  @param[in,out] ctx             The build context to use during the operation.
+///  @param[in]     mesh            A fully built polygon mesh.
+///  @param[in]     chf             The compact heightfield used to build the polygon mesh.
+///  @param[in]     sampleDist      Sets the distance to use when samping the heightfield. [Limit: >=0] [Units: wu]
+///  @param[in]     sampleMaxError  The maximum distance the detail mesh surface should deviate from 
+///                                 heightfield data. [Limit: >=0] [Units: wu]
+///  @param[out]    dmesh           The resulting detail mesh.  (Must be pre-allocated.)
+///  @returns True if the operation completed successfully.
+bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
                                                   const float sampleDist, const float sampleMaxError,
                                                   rcPolyMeshDetail& dmesh);
 
-bool rcMergePolyMeshDetails(rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh);
+/// Merges multiple detail meshes into a single detail mesh.
+///  @ingroup recast
+///  @param[in,out] ctx      The build context to use during the operation.
+///  @param[in]     meshes   An array of detail meshes to merge. [Size: @p nmeshes]
+///  @param[in]     nmeshes  The number of detail meshes in the meshes array.
+///  @param[out]    mesh     The resulting detail mesh. (Must be pre-allocated.)
+///  @returns True if the operation completed successfully.
+bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh);
 
 bool buildMeshAdjacency(unsigned short* polys, const int npolys, const int nverts, const int vertsPerPoly);
 
+/// @}
+
 #endif // RECAST_H
+
+///////////////////////////////////////////////////////////////////////////
+
+// Due to the large amount of detail documentation for this file, 
+// the content normally located at the end of the header file has been separated
+// out to a file in /Docs/Extern.
diff --git a/extern/recastnavigation/Recast/Include/RecastAlloc.h b/extern/recastnavigation/Recast/Include/RecastAlloc.h
new file mode 100644 (file)
index 0000000..0038c1a
--- /dev/null
@@ -0,0 +1,122 @@
+//
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
+//
+// This software is provided 'as-is', without any express or implied
+// warranty.  In no event will the authors be held liable for any damages
+// arising from the use of this software.
+// Permission is granted to anyone to use this software for any purpose,
+// including commercial applications, and to alter it and redistribute it
+// freely, subject to the following restrictions:
+// 1. The origin of this software must not be misrepresented; you must not
+//    claim that you wrote the original software. If you use this software
+//    in a product, an acknowledgment in the product documentation would be
+//    appreciated but is not required.
+// 2. Altered source versions must be plainly marked as such, and must not be
+//    misrepresented as being the original software.
+// 3. This notice may not be removed or altered from any source distribution.
+//
+
+#ifndef RECASTALLOC_H
+#define RECASTALLOC_H
+
+/// Provides hint values to the memory allocator on how long the
+/// memory is expected to be used.
+enum rcAllocHint
+{
+       RC_ALLOC_PERM,          ///< Memory will persist after a function call.
+       RC_ALLOC_TEMP           ///< Memory used temporarily within a function.
+};
+
+/// A memory allocation function.
+//  @param[in] size         The size, in bytes of memory, to allocate.
+//  @param[in] rcAllocHint  A hint to the allocator on how long the memory is expected to be in use.
+//  @return A pointer to the beginning of the allocated memory block, or null if the allocation failed.
+///  @see rcAllocSetCustom
+typedef void* (rcAllocFunc)(int size, rcAllocHint hint);
+
+/// A memory deallocation function.
+/// @see rcAllocSetCustom
+//  @param[in] ptr 
+typedef void (rcFreeFunc)(void* ptr);
+
+/// Sets the base custom allocation functions to be used by Recast.
+///  @param[in] allocFunc  The memory allocation function to be used by #rcAlloc
+///  @param[in] freeFunc   The memory de-allocation function to be used by #rcFree
+void rcAllocSetCustom(rcAllocFunc *allocFunc, rcFreeFunc *freeFunc);
+
+/// Allocates a memory block.
+///  @param[in] size  The size, in bytes of memory, to allocate.
+///  @param[in] hint  A hint to the allocator on how long the memory is expected to be in use.
+///  @return A pointer to the beginning of the allocated memory block, or null if the allocation failed.
+void* rcAlloc(int size, rcAllocHint hint);
+
+/// Deallocates a memory block.
+///  @param[in] ptr A pointer to a memory block previously allocated using #rcAlloc.
+void rcFree(void* ptr);
+
+
+/// A simple dynamic array of integers.
+class rcIntArray
+{
+       int* m_data;
+       int m_size, m_cap;
+       inline rcIntArray(const rcIntArray&);
+       inline rcIntArray& operator=(const rcIntArray&);
+public:
+
+       /// Constructs an instance with an initial array size of zero.
+       inline rcIntArray() : m_data(0), m_size(0), m_cap(0) {}
+
+       /// Constructs an instance initialized to the specified size.
+       ///  @param[in] n The initial size of the integer array.
+       inline rcIntArray(int n) : m_data(0), m_size(0), m_cap(0) { resize(n); }
+       inline ~rcIntArray() { rcFree(m_data); }
+
+       /// Specifies the new size of the integer array.
+       ///  @param[in] n  The new size of the integer array.
+       void resize(int n);
+
+       /// Push the specified integer onto the end of the array and increases the size by one.
+       ///  @param[in] item  The new value.
+       inline void push(int item) { resize(m_size+1); m_data[m_size-1] = item; }
+
+       /// Returns the value at the end of the array and reduces the size by one.
+       ///  @return The value at the end of the array.
+       inline int pop() { if (m_size > 0) m_size--; return m_data[m_size]; }
+
+       /// The value at the specified array index.
+       /// @warning Does not provide overflow protection.
+       ///  @param[in] i  The index of the value.
+       inline const int& operator[](int i) const { return m_data[i]; }
+
+       /// The value at the specified array index.
+       /// @warning Does not provide overflow protection.
+       ///  @param[in] i  The index of the value.
+       inline int& operator[](int i) { return m_data[i]; }
+
+       /// The current size of the integer array.
+       inline int size() const { return m_size; }
+};
+
+/// A simple helper class used to delete an array when it goes out of scope.
+/// @note This class is rarely if ever used by the end user.
+template<class T> class rcScopedDelete
+{
+       T* ptr;
+       inline T* operator=(T* p);
+public:
+
+       /// Constructs an instance with a null pointer.
+       inline rcScopedDelete() : ptr(0) {}
+
+       /// Constructs an instance with the specified pointer.
+       ///  @param[in] p  An pointer to an allocated array.
+       inline rcScopedDelete(T* p) : ptr(p) {}
+       inline ~rcScopedDelete() { rcFree(ptr); }
+
+       /// The root array pointer.
+       ///  @return The root array pointer.
+       inline operator T*() { return ptr; }
+};
+
+#endif
diff --git a/extern/recastnavigation/Recast/Include/RecastAssert.h b/extern/recastnavigation/Recast/Include/RecastAssert.h
new file mode 100644 (file)
index 0000000..b58b8fc
--- /dev/null
@@ -0,0 +1,33 @@
+//
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
+//
+// This software is provided 'as-is', without any express or implied
+// warranty.  In no event will the authors be held liable for any damages
+// arising from the use of this software.
+// Permission is granted to anyone to use this software for any purpose,
+// including commercial applications, and to alter it and redistribute it
+// freely, subject to the following restrictions:
+// 1. The origin of this software must not be misrepresented; you must not
+//    claim that you wrote the original software. If you use this software
+//    in a product, an acknowledgment in the product documentation would be
+//    appreciated but is not required.
+// 2. Altered source versions must be plainly marked as such, and must not be
+//    misrepresented as being the original software.
+// 3. This notice may not be removed or altered from any source distribution.
+//
+
+#ifndef RECASTASSERT_H
+#define RECASTASSERT_H
+
+// Note: This header file's only purpose is to include define assert.
+// Feel free to change the file and include your own implementation instead.
+
+#ifdef NDEBUG
+// From http://cnicholson.net/2009/02/stupid-c-tricks-adventures-in-assert/
+#      define rcAssert(x) do { (void)sizeof(x); } while(__LINE__==-1,false)  
+#else
+#      include <assert.h> 
+#      define rcAssert assert
+#endif
+
+#endif // RECASTASSERT_H
index 0db26c2c1cd77000ec0313f642893e6d08fa70f8..283cf0c128b19651e1f49a42058d51ed81fa3a92 100644 (file)
@@ -1,5 +1,5 @@
 //
-// Copyright (c) 2009 Mikko Mononen memon@inside.org
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
 //
 // This software is provided 'as-is', without any express or implied
 // warranty.  In no event will the authors be held liable for any damages
 #include <string.h>
 #include <stdlib.h>
 #include <stdio.h>
+#include <stdarg.h>
 #include "Recast.h"
-#include "RecastLog.h"
-#include "RecastTimer.h"
+#include "RecastAlloc.h"
+#include "RecastAssert.h"
 
+float rcSqrt(float x)
+{
+       return sqrtf(x);
+}
+
+/// @class rcContext
+/// @par
+///
+/// This class does not provide logging or timer functionality on its 
+/// own.  Both must be provided by a concrete implementation 
+/// by overriding the protected member functions.  Also, this class does not 
+/// provide an interface for extracting log messages. (Only adding them.) 
+/// So concrete implementations must provide one.
+///
+/// If no logging or timers are required, just pass an instance of this 
+/// class through the Recast build process.
+///
 
-void rcIntArray::resize(int n)
+/// @par
+///
+/// Example:
+/// @code
+/// // Where ctx is an instance of rcContext and filepath is a char array.
+/// ctx->log(RC_LOG_ERROR, "buildTiledNavigation: Could not load '%s'", filepath);
+/// @endcode
+void rcContext::log(const rcLogCategory category, const char* format, ...)
 {
-       if (n > m_cap)
+       if (!m_logEnabled)
+               return;
+       static const int MSG_SIZE = 512;
+       char msg[MSG_SIZE];
+       va_list ap;
+       va_start(ap, format);
+       int len = vsnprintf(msg, MSG_SIZE, format, ap);
+       if (len >= MSG_SIZE)
        {
-               if (!m_cap) m_cap = 8;
-               while (m_cap < n) m_cap *= 2;
-               int* newData = new int[m_cap];
-               if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int));
-               delete [] m_data;
-               m_data = newData;
+               len = MSG_SIZE-1;
+               msg[MSG_SIZE-1] = '\0';
        }
-       m_size = n;
+       va_end(ap);
+       doLog(category, msg, len);
+}
+
+rcHeightfield* rcAllocHeightfield()
+{
+       rcHeightfield* hf = (rcHeightfield*)rcAlloc(sizeof(rcHeightfield), RC_ALLOC_PERM);
+       memset(hf, 0, sizeof(rcHeightfield));
+       return hf;
+}
+
+void rcFreeHeightField(rcHeightfield* hf)
+{
+       if (!hf) return;
+       // Delete span array.
+       rcFree(hf->spans);
+       // Delete span pools.
+       while (hf->pools)
+       {
+               rcSpanPool* next = hf->pools->next;
+               rcFree(hf->pools);
+               hf->pools = next;
+       }
+       rcFree(hf);
+}
+
+rcCompactHeightfield* rcAllocCompactHeightfield()
+{
+       rcCompactHeightfield* chf = (rcCompactHeightfield*)rcAlloc(sizeof(rcCompactHeightfield), RC_ALLOC_PERM);
+       memset(chf, 0, sizeof(rcCompactHeightfield));
+       return chf;
+}
+
+void rcFreeCompactHeightfield(rcCompactHeightfield* chf)
+{
+       if (!chf) return;
+       rcFree(chf->cells);
+       rcFree(chf->spans);
+       rcFree(chf->dist);
+       rcFree(chf->areas);
+       rcFree(chf);
+}
+
+
+rcHeightfieldLayerSet* rcAllocHeightfieldLayerSet()
+{
+       rcHeightfieldLayerSet* lset = (rcHeightfieldLayerSet*)rcAlloc(sizeof(rcHeightfieldLayerSet), RC_ALLOC_PERM);
+       memset(lset, 0, sizeof(rcHeightfieldLayerSet));
+       return lset;
+}
+
+void rcFreeHeightfieldLayerSet(rcHeightfieldLayerSet* lset)
+{
+       if (!lset) return;
+       for (int i = 0; i < lset->nlayers; ++i)
+       {
+               rcFree(lset->layers[i].heights);
+               rcFree(lset->layers[i].areas);
+               rcFree(lset->layers[i].cons);
+       }
+       rcFree(lset->layers);
+       rcFree(lset);
+}
+
+
+rcContourSet* rcAllocContourSet()
+{
+       rcContourSet* cset = (rcContourSet*)rcAlloc(sizeof(rcContourSet), RC_ALLOC_PERM);
+       memset(cset, 0, sizeof(rcContourSet));
+       return cset;
+}
+
+void rcFreeContourSet(rcContourSet* cset)
+{
+       if (!cset) return;
+       for (int i = 0; i < cset->nconts; ++i)
+       {
+               rcFree(cset->conts[i].verts);
+               rcFree(cset->conts[i].rverts);
+       }
+       rcFree(cset->conts);
+       rcFree(cset);
+}
+
+rcPolyMesh* rcAllocPolyMesh()
+{
+       rcPolyMesh* pmesh = (rcPolyMesh*)rcAlloc(sizeof(rcPolyMesh), RC_ALLOC_PERM);
+       memset(pmesh, 0, sizeof(rcPolyMesh));
+       return pmesh;
+}
+
+void rcFreePolyMesh(rcPolyMesh* pmesh)
+{
+       if (!pmesh) return;
+       rcFree(pmesh->verts);
+       rcFree(pmesh->polys);
+       rcFree(pmesh->regs);
+       rcFree(pmesh->flags);
+       rcFree(pmesh->areas);
+       rcFree(pmesh);
+}
+
+rcPolyMeshDetail* rcAllocPolyMeshDetail()
+{
+       rcPolyMeshDetail* dmesh = (rcPolyMeshDetail*)rcAlloc(sizeof(rcPolyMeshDetail), RC_ALLOC_PERM);
+       memset(dmesh, 0, sizeof(rcPolyMeshDetail));
+       return dmesh;
+}
+
+void rcFreePolyMeshDetail(rcPolyMeshDetail* dmesh)
+{
+       if (!dmesh) return;
+       rcFree(dmesh->meshes);
+       rcFree(dmesh->verts);
+       rcFree(dmesh->tris);
+       rcFree(dmesh);
 }
 
 void rcCalcBounds(const float* verts, int nv, float* bmin, float* bmax)
 {
        // Calculate bounding box.
-       vcopy(bmin, verts);
-       vcopy(bmax, verts);
+       rcVcopy(bmin, verts);
+       rcVcopy(bmax, verts);
        for (int i = 1; i < nv; ++i)
        {
                const float* v = &verts[i*3];
-               vmin(bmin, v);
-               vmax(bmax, v);
+               rcVmin(bmin, v);
+               rcVmax(bmax, v);
        }
 }
 
@@ -60,17 +203,25 @@ void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int*
        *h = (int)((bmax[2] - bmin[2])/cs+0.5f);
 }
 
-bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
+/// @par
+///
+/// See the #rcConfig documentation for more information on the configuration parameters.
+/// 
+/// @see rcAllocHeightfield, rcHeightfield 
+bool rcCreateHeightfield(rcContext* /*ctx*/, rcHeightfield& hf, int width, int height,
                                                 const float* bmin, const float* bmax,
                                                 float cs, float ch)
 {
+       // TODO: VC complains about unref formal variable, figure out a way to handle this better.
+//     rcAssert(ctx);
+       
        hf.width = width;
        hf.height = height;
-       hf.spans = new rcSpan*[hf.width*hf.height];
-       vcopy(hf.bmin, bmin);
-       vcopy(hf.bmax, bmax);
+       rcVcopy(hf.bmin, bmin);
+       rcVcopy(hf.bmax, bmax);
        hf.cs = cs;
        hf.ch = ch;
+       hf.spans = (rcSpan**)rcAlloc(sizeof(rcSpan*)*hf.width*hf.height, RC_ALLOC_PERM);
        if (!hf.spans)
                return false;
        memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height);
@@ -80,18 +231,29 @@ bool rcCreateHeightfield(rcHeightfield& hf, int width, int height,
 static void calcTriNormal(const float* v0, const float* v1, const float* v2, float* norm)
 {
        float e0[3], e1[3];
-       vsub(e0, v1, v0);
-       vsub(e1, v2, v0);
-       vcross(norm, e0, e1);
-       vnormalize(norm);
+       rcVsub(e0, v1, v0);
+       rcVsub(e1, v2, v0);
+       rcVcross(norm, e0, e1);
+       rcVnormalize(norm);
 }
 
-void rcMarkWalkableTriangles(const float walkableSlopeAngle,
-                                                        const float* verts, int nv,
+/// @par
+///
+/// Only sets the aread id's for the walkable triangles.  Does not alter the
+/// area id's for unwalkable triangles.
+/// 
+/// See the #rcConfig documentation for more information on the configuration parameters.
+/// 
+/// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
+void rcMarkWalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle,
+                                                        const float* verts, int /*nv*/,
                                                         const int* tris, int nt,
-                                                        unsigned char* flags)
+                                                        unsigned char* areas)
 {
-       const float walkableThr = cosf(walkableSlopeAngle/180.0f*(float)M_PI);
+       // TODO: VC complains about unref formal variable, figure out a way to handle this better.
+//     rcAssert(ctx);
+       
+       const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
 
        float norm[3];
        
@@ -101,12 +263,45 @@ void rcMarkWalkableTriangles(const float walkableSlopeAngle,
                calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
                // Check if the face is walkable.
                if (norm[1] > walkableThr)
-                       flags[i] |= RC_WALKABLE;
+                       areas[i] = RC_WALKABLE_AREA;
+       }
+}
+
+/// @par
+///
+/// Only sets the aread id's for the unwalkable triangles.  Does not alter the
+/// area id's for walkable triangles.
+/// 
+/// See the #rcConfig documentation for more information on the configuration parameters.
+/// 
+/// @see rcHeightfield, rcClearUnwalkableTriangles, rcRasterizeTriangles
+void rcClearUnwalkableTriangles(rcContext* /*ctx*/, const float walkableSlopeAngle,
+                                                               const float* verts, int /*nv*/,
+                                                               const int* tris, int nt,
+                                                               unsigned char* areas)
+{
+       // TODO: VC complains about unref formal variable, figure out a way to handle this better.
+//     rcAssert(ctx);
+       
+       const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
+       
+       float norm[3];
+       
+       for (int i = 0; i < nt; ++i)
+       {
+               const int* tri = &tris[i*3];
+               calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
+               // Check if the face is walkable.
+               if (norm[1] <= walkableThr)
+                       areas[i] = RC_NULL_AREA;
        }
 }
 
-static int getSpanCount(unsigned char flags, rcHeightfield& hf)
+int rcGetHeightFieldSpanCount(rcContext* /*ctx*/, rcHeightfield& hf)
 {
+       // TODO: VC complains about unref formal variable, figure out a way to handle this better.
+//     rcAssert(ctx);
+       
        const int w = hf.width;
        const int h = hf.height;
        int spanCount = 0;
@@ -116,7 +311,7 @@ static int getSpanCount(unsigned char flags, rcHeightfield& hf)
                {
                        for (rcSpan* s = hf.spans[x + y*w]; s; s = s->next)
                        {
-                               if (s->flags == flags)
+                               if (s->area != RC_NULL_AREA)
                                        spanCount++;
                        }
                }
@@ -124,21 +319,25 @@ static int getSpanCount(unsigned char flags, rcHeightfield& hf)
        return spanCount;
 }
 
-inline void setCon(rcCompactSpan& s, int dir, int i)
-{
-       s.con &= ~(0xf << (dir*4));
-       s.con |= (i&0xf) << (dir*4);
-}
-
-bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb,
-                                                          unsigned char flags, rcHeightfield& hf,
-                                                          rcCompactHeightfield& chf)
+/// @par
+///
+/// This is just the beginning of the process of fully building a compact heightfield.
+/// Various filters may be applied applied, then the distance field and regions built.
+/// E.g: #rcBuildDistanceField and #rcBuildRegions
+///
+/// See the #rcConfig documentation for more information on the configuration parameters.
+///
+/// @see rcAllocCompactHeightfield, rcHeightfield, rcCompactHeightfield, rcConfig
+bool rcBuildCompactHeightfield(rcContext* ctx, const int walkableHeight, const int walkableClimb,
+                                                          rcHeightfield& hf, rcCompactHeightfield& chf)
 {
-       rcTimeVal startTime = rcGetPerformanceTimer();
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD);
        
        const int w = hf.width;
        const int h = hf.height;
-       const int spanCount = getSpanCount(flags, hf);
+       const int spanCount = rcGetHeightFieldSpanCount(ctx, hf);
 
        // Fill in header.
        chf.width = w;
@@ -147,27 +346,32 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
        chf.walkableHeight = walkableHeight;
        chf.walkableClimb = walkableClimb;
        chf.maxRegions = 0;
-       vcopy(chf.bmin, hf.bmin);
-       vcopy(chf.bmax, hf.bmax);
+       rcVcopy(chf.bmin, hf.bmin);
+       rcVcopy(chf.bmax, hf.bmax);
        chf.bmax[1] += walkableHeight*hf.ch;
        chf.cs = hf.cs;
        chf.ch = hf.ch;
-       chf.cells = new rcCompactCell[w*h];
+       chf.cells = (rcCompactCell*)rcAlloc(sizeof(rcCompactCell)*w*h, RC_ALLOC_PERM);
        if (!chf.cells)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
+               ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.cells' (%d)", w*h);
                return false;
        }
        memset(chf.cells, 0, sizeof(rcCompactCell)*w*h);
-       chf.spans = new rcCompactSpan[spanCount];
+       chf.spans = (rcCompactSpan*)rcAlloc(sizeof(rcCompactSpan)*spanCount, RC_ALLOC_PERM);
        if (!chf.spans)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
+               ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.spans' (%d)", spanCount);
                return false;
        }
        memset(chf.spans, 0, sizeof(rcCompactSpan)*spanCount);
+       chf.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*spanCount, RC_ALLOC_PERM);
+       if (!chf.areas)
+       {
+               ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Out of memory 'chf.areas' (%d)", spanCount);
+               return false;
+       }
+       memset(chf.areas, RC_NULL_AREA, sizeof(unsigned char)*spanCount);
        
        const int MAX_HEIGHT = 0xffff;
        
@@ -185,12 +389,13 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
                        c.count = 0;
                        while (s)
                        {
-                               if (s->flags == flags)
+                               if (s->area != RC_NULL_AREA)
                                {
                                        const int bot = (int)s->smax;
                                        const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
                                        chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
                                        chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
+                                       chf.areas[idx] = s->area;
                                        idx++;
                                        c.count++;
                                }
@@ -200,6 +405,8 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
        }
 
        // Find neighbour connections.
+       const int MAX_LAYERS = RC_NOT_CONNECTED-1;
+       int tooHighNeighbour = 0;
        for (int y = 0; y < h; ++y)
        {
                for (int x = 0; x < w; ++x)
@@ -208,14 +415,16 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
                        for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
                        {
                                rcCompactSpan& s = chf.spans[i];
+                               
                                for (int dir = 0; dir < 4; ++dir)
                                {
-                                       setCon(s, dir, 0xf);
+                                       rcSetCon(s, dir, RC_NOT_CONNECTED);
                                        const int nx = x + rcGetDirOffsetX(dir);
                                        const int ny = y + rcGetDirOffsetY(dir);
                                        // First check that the neighbour cell is in bounds.
                                        if (nx < 0 || ny < 0 || nx >= w || ny >= h)
                                                continue;
+                                               
                                        // Iterate over all neighbour spans and check if any of the is
                                        // accessible from current cell.
                                        const rcCompactCell& nc = chf.cells[nx+ny*w];
@@ -230,23 +439,34 @@ bool rcBuildCompactHeightfield(const int walkableHeight, const int walkableClimb
                                                if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb)
                                                {
                                                        // Mark direction as walkable.
-                                                       setCon(s, dir, k - (int)nc.index);
+                                                       const int idx = k - (int)nc.index;
+                                                       if (idx < 0 || idx > MAX_LAYERS)
+                                                       {
+                                                               tooHighNeighbour = rcMax(tooHighNeighbour, idx);
+                                                               continue;
+                                                       }
+                                                       rcSetCon(s, dir, idx);
                                                        break;
                                                }
                                        }
+                                       
                                }
                        }
                }
        }
        
-       rcTimeVal endTime = rcGetPerformanceTimer();
-       
-       if (rcGetBuildTimes())
-               rcGetBuildTimes()->buildCompact += rcGetDeltaTimeUsec(startTime, endTime);
+       if (tooHighNeighbour > MAX_LAYERS)
+       {
+               ctx->log(RC_LOG_ERROR, "rcBuildCompactHeightfield: Heightfield has too many layers %d (max: %d)",
+                                tooHighNeighbour, MAX_LAYERS);
+       }
+               
+       ctx->stopTimer(RC_TIMER_BUILD_COMPACTHEIGHTFIELD);
        
        return true;
 }
 
+/*
 static int getHeightfieldMemoryUsage(const rcHeightfield& hf)
 {
        int size = 0;
@@ -270,3 +490,4 @@ static int getCompactHeightFieldMemoryusage(const rcCompactHeightfield& chf)
        size += sizeof(rcCompactCell) * chf.width * chf.height;
        return size;
 }
+*/
\ No newline at end of file
diff --git a/extern/recastnavigation/Recast/Source/RecastAlloc.cpp b/extern/recastnavigation/Recast/Source/RecastAlloc.cpp
new file mode 100644 (file)
index 0000000..b5ec151
--- /dev/null
@@ -0,0 +1,88 @@
+//
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
+//
+// This software is provided 'as-is', without any express or implied
+// warranty.  In no event will the authors be held liable for any damages
+// arising from the use of this software.
+// Permission is granted to anyone to use this software for any purpose,
+// including commercial applications, and to alter it and redistribute it
+// freely, subject to the following restrictions:
+// 1. The origin of this software must not be misrepresented; you must not
+//    claim that you wrote the original software. If you use this software
+//    in a product, an acknowledgment in the product documentation would be
+//    appreciated but is not required.
+// 2. Altered source versions must be plainly marked as such, and must not be
+//    misrepresented as being the original software.
+// 3. This notice may not be removed or altered from any source distribution.
+//
+
+#include <stdlib.h>
+#include <string.h>
+#include "RecastAlloc.h"
+
+static void *rcAllocDefault(int size, rcAllocHint)
+{
+       return malloc(size);
+}
+
+static void rcFreeDefault(void *ptr)
+{
+       free(ptr);
+}
+
+static rcAllocFunc* sRecastAllocFunc = rcAllocDefault;
+static rcFreeFunc* sRecastFreeFunc = rcFreeDefault;
+
+/// @see rcAlloc, rcFree
+void rcAllocSetCustom(rcAllocFunc *allocFunc, rcFreeFunc *freeFunc)
+{
+       sRecastAllocFunc = allocFunc ? allocFunc : rcAllocDefault;
+       sRecastFreeFunc = freeFunc ? freeFunc : rcFreeDefault;
+}
+
+/// @see rcAllocSetCustom
+void* rcAlloc(int size, rcAllocHint hint)
+{
+       return sRecastAllocFunc(size, hint);
+}
+
+/// @par
+///
+/// @warning This function leaves the value of @p ptr unchanged.  So it still
+/// points to the same (now invalid) location, and not to null.
+/// 
+/// @see rcAllocSetCustom
+void rcFree(void* ptr)
+{
+       if (ptr)
+               sRecastFreeFunc(ptr);
+}
+
+/// @class rcIntArray
+///
+/// While it is possible to pre-allocate a specific array size during 
+/// construction or by using the #resize method, certain methods will 
+/// automatically resize the array as needed.
+///
+/// @warning The array memory is not initialized to zero when the size is 
+/// manually set during construction or when using #resize.
+
+/// @par
+///
+/// Using this method ensures the array is at least large enough to hold
+/// the specified number of elements.  This can improve performance by
+/// avoiding auto-resizing during use.
+void rcIntArray::resize(int n)
+{
+       if (n > m_cap)
+       {
+               if (!m_cap) m_cap = n;
+               while (m_cap < n) m_cap *= 2;
+               int* newData = (int*)rcAlloc(m_cap*sizeof(int), RC_ALLOC_TEMP);
+               if (m_size && newData) memcpy(newData, m_data, m_size*sizeof(int));
+               rcFree(m_data);
+               m_data = newData;
+       }
+       m_size = n;
+}
+
diff --git a/extern/recastnavigation/Recast/Source/RecastArea.cpp b/extern/recastnavigation/Recast/Source/RecastArea.cpp
new file mode 100644 (file)
index 0000000..a59acc5
--- /dev/null
@@ -0,0 +1,524 @@
+//
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
+//
+// This software is provided 'as-is', without any express or implied
+// warranty.  In no event will the authors be held liable for any damages
+// arising from the use of this software.
+// Permission is granted to anyone to use this software for any purpose,
+// including commercial applications, and to alter it and redistribute it
+// freely, subject to the following restrictions:
+// 1. The origin of this software must not be misrepresented; you must not
+//    claim that you wrote the original software. If you use this software
+//    in a product, an acknowledgment in the product documentation would be
+//    appreciated but is not required.
+// 2. Altered source versions must be plainly marked as such, and must not be
+//    misrepresented as being the original software.
+// 3. This notice may not be removed or altered from any source distribution.
+//
+
+#include <float.h>
+#define _USE_MATH_DEFINES
+#include <math.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "Recast.h"
+#include "RecastAlloc.h"
+#include "RecastAssert.h"
+
+/// @par 
+/// 
+/// Basically, any spans that are closer to a boundary or obstruction than the specified radius 
+/// are marked as unwalkable.
+///
+/// This method is usually called immediately after the heightfield has been built.
+///
+/// @see rcCompactHeightfield, rcBuildCompactHeightfield, rcConfig::walkableRadius
+bool rcErodeWalkableArea(rcContext* ctx, int radius, rcCompactHeightfield& chf)
+{
+       rcAssert(ctx);
+       
+       const int w = chf.width;
+       const int h = chf.height;
+       
+       ctx->startTimer(RC_TIMER_ERODE_AREA);
+       
+       unsigned char* dist = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
+       if (!dist)
+       {
+               ctx->log(RC_LOG_ERROR, "erodeWalkableArea: Out of memory 'dist' (%d).", chf.spanCount);
+               return false;
+       }
+       
+       // Init distance.
+       memset(dist, 0xff, sizeof(unsigned char)*chf.spanCount);
+       
+       // Mark boundary cells.
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               if (chf.areas[i] == RC_NULL_AREA)
+                               {
+                                       dist[i] = 0;
+                               }
+                               else
+                               {
+                                       const rcCompactSpan& s = chf.spans[i];
+                                       int nc = 0;
+                                       for (int dir = 0; dir < 4; ++dir)
+                                       {
+                                               if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
+                                               {
+                                                       const int nx = x + rcGetDirOffsetX(dir);
+                                                       const int ny = y + rcGetDirOffsetY(dir);
+                                                       const int ni = (int)chf.cells[nx+ny*w].index + rcGetCon(s, dir);
+                                                       if (chf.areas[ni] != RC_NULL_AREA)
+                                                       {
+                                                               nc++;
+                                                       }
+                                               }
+                                       }
+                                       // At least one missing neighbour.
+                                       if (nc != 4)
+                                               dist[i] = 0;
+                               }
+                       }
+               }
+       }
+       
+       unsigned char nd;
+       
+       // Pass 1
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               const rcCompactSpan& s = chf.spans[i];
+                               
+                               if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
+                               {
+                                       // (-1,0)
+                                       const int ax = x + rcGetDirOffsetX(0);
+                                       const int ay = y + rcGetDirOffsetY(0);
+                                       const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
+                                       const rcCompactSpan& as = chf.spans[ai];
+                                       nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
+                                       if (nd < dist[i])
+                                               dist[i] = nd;
+                                       
+                                       // (-1,-1)
+                                       if (rcGetCon(as, 3) != RC_NOT_CONNECTED)
+                                       {
+                                               const int aax = ax + rcGetDirOffsetX(3);
+                                               const int aay = ay + rcGetDirOffsetY(3);
+                                               const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 3);
+                                               nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
+                                               if (nd < dist[i])
+                                                       dist[i] = nd;
+                                       }
+                               }
+                               if (rcGetCon(s, 3) != RC_NOT_CONNECTED)
+                               {
+                                       // (0,-1)
+                                       const int ax = x + rcGetDirOffsetX(3);
+                                       const int ay = y + rcGetDirOffsetY(3);
+                                       const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
+                                       const rcCompactSpan& as = chf.spans[ai];
+                                       nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
+                                       if (nd < dist[i])
+                                               dist[i] = nd;
+                                       
+                                       // (1,-1)
+                                       if (rcGetCon(as, 2) != RC_NOT_CONNECTED)
+                                       {
+                                               const int aax = ax + rcGetDirOffsetX(2);
+                                               const int aay = ay + rcGetDirOffsetY(2);
+                                               const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 2);
+                                               nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
+                                               if (nd < dist[i])
+                                                       dist[i] = nd;
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       // Pass 2
+       for (int y = h-1; y >= 0; --y)
+       {
+               for (int x = w-1; x >= 0; --x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               const rcCompactSpan& s = chf.spans[i];
+                               
+                               if (rcGetCon(s, 2) != RC_NOT_CONNECTED)
+                               {
+                                       // (1,0)
+                                       const int ax = x + rcGetDirOffsetX(2);
+                                       const int ay = y + rcGetDirOffsetY(2);
+                                       const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 2);
+                                       const rcCompactSpan& as = chf.spans[ai];
+                                       nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
+                                       if (nd < dist[i])
+                                               dist[i] = nd;
+                                       
+                                       // (1,1)
+                                       if (rcGetCon(as, 1) != RC_NOT_CONNECTED)
+                                       {
+                                               const int aax = ax + rcGetDirOffsetX(1);
+                                               const int aay = ay + rcGetDirOffsetY(1);
+                                               const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 1);
+                                               nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
+                                               if (nd < dist[i])
+                                                       dist[i] = nd;
+                                       }
+                               }
+                               if (rcGetCon(s, 1) != RC_NOT_CONNECTED)
+                               {
+                                       // (0,1)
+                                       const int ax = x + rcGetDirOffsetX(1);
+                                       const int ay = y + rcGetDirOffsetY(1);
+                                       const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 1);
+                                       const rcCompactSpan& as = chf.spans[ai];
+                                       nd = (unsigned char)rcMin((int)dist[ai]+2, 255);
+                                       if (nd < dist[i])
+                                               dist[i] = nd;
+                                       
+                                       // (-1,1)
+                                       if (rcGetCon(as, 0) != RC_NOT_CONNECTED)
+                                       {
+                                               const int aax = ax + rcGetDirOffsetX(0);
+                                               const int aay = ay + rcGetDirOffsetY(0);
+                                               const int aai = (int)chf.cells[aax+aay*w].index + rcGetCon(as, 0);
+                                               nd = (unsigned char)rcMin((int)dist[aai]+3, 255);
+                                               if (nd < dist[i])
+                                                       dist[i] = nd;
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       const unsigned char thr = (unsigned char)(radius*2);
+       for (int i = 0; i < chf.spanCount; ++i)
+               if (dist[i] < thr)
+                       chf.areas[i] = RC_NULL_AREA;
+       
+       rcFree(dist);
+       
+       ctx->stopTimer(RC_TIMER_ERODE_AREA);
+       
+       return true;
+}
+
+static void insertSort(unsigned char* a, const int n)
+{
+       int i, j;
+       for (i = 1; i < n; i++)
+       {
+               const unsigned char value = a[i];
+               for (j = i - 1; j >= 0 && a[j] > value; j--)
+                       a[j+1] = a[j];
+               a[j+1] = value;
+       }
+}
+
+/// @par
+///
+/// This filter is usually applied after applying area id's using functions
+/// such as #rcMarkBoxArea, #rcMarkConvexPolyArea, and #rcMarkCylinderArea.
+/// 
+/// @see rcCompactHeightfield
+bool rcMedianFilterWalkableArea(rcContext* ctx, rcCompactHeightfield& chf)
+{
+       rcAssert(ctx);
+       
+       const int w = chf.width;
+       const int h = chf.height;
+       
+       ctx->startTimer(RC_TIMER_MEDIAN_AREA);
+       
+       unsigned char* areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
+       if (!areas)
+       {
+               ctx->log(RC_LOG_ERROR, "medianFilterWalkableArea: Out of memory 'areas' (%d).", chf.spanCount);
+               return false;
+       }
+       
+       // Init distance.
+       memset(areas, 0xff, sizeof(unsigned char)*chf.spanCount);
+       
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               const rcCompactSpan& s = chf.spans[i];
+                               if (chf.areas[i] == RC_NULL_AREA)
+                               {
+                                       areas[i] = chf.areas[i];
+                                       continue;
+                               }
+                               
+                               unsigned char nei[9];
+                               for (int j = 0; j < 9; ++j)
+                                       nei[j] = chf.areas[i];
+                               
+                               for (int dir = 0; dir < 4; ++dir)
+                               {
+                                       if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
+                                       {
+                                               const int ax = x + rcGetDirOffsetX(dir);
+                                               const int ay = y + rcGetDirOffsetY(dir);
+                                               const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
+                                               if (chf.areas[ai] != RC_NULL_AREA)
+                                                       nei[dir*2+0] = chf.areas[ai];
+                                               
+                                               const rcCompactSpan& as = chf.spans[ai];
+                                               const int dir2 = (dir+1) & 0x3;
+                                               if (rcGetCon(as, dir2) != RC_NOT_CONNECTED)
+                                               {
+                                                       const int ax2 = ax + rcGetDirOffsetX(dir2);
+                                                       const int ay2 = ay + rcGetDirOffsetY(dir2);
+                                                       const int ai2 = (int)chf.cells[ax2+ay2*w].index + rcGetCon(as, dir2);
+                                                       if (chf.areas[ai2] != RC_NULL_AREA)
+                                                               nei[dir*2+1] = chf.areas[ai2];
+                                               }
+                                       }
+                               }
+                               insertSort(nei, 9);
+                               areas[i] = nei[4];
+                       }
+               }
+       }
+       
+       memcpy(chf.areas, areas, sizeof(unsigned char)*chf.spanCount);
+       
+       rcFree(areas);
+
+       ctx->stopTimer(RC_TIMER_MEDIAN_AREA);
+       
+       return true;
+}
+
+/// @par
+///
+/// The value of spacial parameters are in world units.
+/// 
+/// @see rcCompactHeightfield, rcMedianFilterWalkableArea
+void rcMarkBoxArea(rcContext* ctx, const float* bmin, const float* bmax, unsigned char areaId,
+                                  rcCompactHeightfield& chf)
+{
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_MARK_BOX_AREA);
+
+       int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs);
+       int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch);
+       int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs);
+       int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs);
+       int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch);
+       int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs);
+       
+       if (maxx < 0) return;
+       if (minx >= chf.width) return;
+       if (maxz < 0) return;
+       if (minz >= chf.height) return;
+
+       if (minx < 0) minx = 0;
+       if (maxx >= chf.width) maxx = chf.width-1;
+       if (minz < 0) minz = 0;
+       if (maxz >= chf.height) maxz = chf.height-1;    
+       
+       for (int z = minz; z <= maxz; ++z)
+       {
+               for (int x = minx; x <= maxx; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+z*chf.width];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               rcCompactSpan& s = chf.spans[i];
+                               if ((int)s.y >= miny && (int)s.y <= maxy)
+                               {
+                                       if (chf.areas[i] != RC_NULL_AREA)
+                                               chf.areas[i] = areaId;
+                               }
+                       }
+               }
+       }
+
+       ctx->stopTimer(RC_TIMER_MARK_BOX_AREA);
+
+}
+
+
+static int pointInPoly(int nvert, const float* verts, const float* p)
+{
+       int i, j, c = 0;
+       for (i = 0, j = nvert-1; i < nvert; j = i++)
+       {
+               const float* vi = &verts[i*3];
+               const float* vj = &verts[j*3];
+               if (((vi[2] > p[2]) != (vj[2] > p[2])) &&
+                       (p[0] < (vj[0]-vi[0]) * (p[2]-vi[2]) / (vj[2]-vi[2]) + vi[0]) )
+                       c = !c;
+       }
+       return c;
+}
+
+/// @par
+///
+/// The value of spacial parameters are in world units.
+/// 
+/// The y-values of the polygon vertices are ignored. So the polygon is effectively 
+/// projected onto the xz-plane at @p hmin, then extruded to @p hmax.
+/// 
+/// @see rcCompactHeightfield, rcMedianFilterWalkableArea
+void rcMarkConvexPolyArea(rcContext* ctx, const float* verts, const int nverts,
+                                                 const float hmin, const float hmax, unsigned char areaId,
+                                                 rcCompactHeightfield& chf)
+{
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_MARK_CONVEXPOLY_AREA);
+
+       float bmin[3], bmax[3];
+       rcVcopy(bmin, verts);
+       rcVcopy(bmax, verts);
+       for (int i = 1; i < nverts; ++i)
+       {
+               rcVmin(bmin, &verts[i*3]);
+               rcVmax(bmax, &verts[i*3]);
+       }
+       bmin[1] = hmin;
+       bmax[1] = hmax;
+
+       int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs);
+       int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch);
+       int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs);
+       int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs);
+       int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch);
+       int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs);
+       
+       if (maxx < 0) return;
+       if (minx >= chf.width) return;
+       if (maxz < 0) return;
+       if (minz >= chf.height) return;
+       
+       if (minx < 0) minx = 0;
+       if (maxx >= chf.width) maxx = chf.width-1;
+       if (minz < 0) minz = 0;
+       if (maxz >= chf.height) maxz = chf.height-1;    
+       
+       
+       // TODO: Optimize.
+       for (int z = minz; z <= maxz; ++z)
+       {
+               for (int x = minx; x <= maxx; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+z*chf.width];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               rcCompactSpan& s = chf.spans[i];
+                               if (chf.areas[i] == RC_NULL_AREA)
+                                       continue;
+                               if ((int)s.y >= miny && (int)s.y <= maxy)
+                               {
+                                       float p[3];
+                                       p[0] = chf.bmin[0] + (x+0.5f)*chf.cs; 
+                                       p[1] = 0;
+                                       p[2] = chf.bmin[2] + (z+0.5f)*chf.cs; 
+
+                                       if (pointInPoly(nverts, verts, p))
+                                       {
+                                               chf.areas[i] = areaId;
+                                       }
+                               }
+                       }
+               }
+       }
+
+       ctx->stopTimer(RC_TIMER_MARK_CONVEXPOLY_AREA);
+}
+
+/// @par
+///
+/// The value of spacial parameters are in world units.
+/// 
+/// @see rcCompactHeightfield, rcMedianFilterWalkableArea
+void rcMarkCylinderArea(rcContext* ctx, const float* pos,
+                                               const float r, const float h, unsigned char areaId,
+                                               rcCompactHeightfield& chf)
+{
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_MARK_CYLINDER_AREA);
+       
+       float bmin[3], bmax[3];
+       bmin[0] = pos[0] - r;
+       bmin[1] = pos[1];
+       bmin[2] = pos[2] - r;
+       bmax[0] = pos[0] + r;
+       bmax[1] = pos[1] + h;
+       bmax[2] = pos[2] + r;
+       const float r2 = r*r;
+       
+       int minx = (int)((bmin[0]-chf.bmin[0])/chf.cs);
+       int miny = (int)((bmin[1]-chf.bmin[1])/chf.ch);
+       int minz = (int)((bmin[2]-chf.bmin[2])/chf.cs);
+       int maxx = (int)((bmax[0]-chf.bmin[0])/chf.cs);
+       int maxy = (int)((bmax[1]-chf.bmin[1])/chf.ch);
+       int maxz = (int)((bmax[2]-chf.bmin[2])/chf.cs);
+       
+       if (maxx < 0) return;
+       if (minx >= chf.width) return;
+       if (maxz < 0) return;
+       if (minz >= chf.height) return;
+       
+       if (minx < 0) minx = 0;
+       if (maxx >= chf.width) maxx = chf.width-1;
+       if (minz < 0) minz = 0;
+       if (maxz >= chf.height) maxz = chf.height-1;    
+       
+       
+       for (int z = minz; z <= maxz; ++z)
+       {
+               for (int x = minx; x <= maxx; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+z*chf.width];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               rcCompactSpan& s = chf.spans[i];
+                               
+                               if (chf.areas[i] == RC_NULL_AREA)
+                                       continue;
+                               
+                               if ((int)s.y >= miny && (int)s.y <= maxy)
+                               {
+                                       const float sx = chf.bmin[0] + (x+0.5f)*chf.cs; 
+                                       const float sz = chf.bmin[2] + (z+0.5f)*chf.cs; 
+                                       const float dx = sx - pos[0];
+                                       const float dz = sz - pos[2];
+                                       
+                                       if (dx*dx + dz*dz < r2)
+                                       {
+                                               chf.areas[i] = areaId;
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       ctx->stopTimer(RC_TIMER_MARK_CYLINDER_AREA);
+}
index 96f763a18f34d12444830df064f3bc0ae88564bb..078c464e5f4d067ed2ed80c469cbf76044a09b56 100644 (file)
@@ -1,5 +1,5 @@
 //
-// Copyright (c) 2009 Mikko Mononen memon@inside.org
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
 //
 // This software is provided 'as-is', without any express or implied
 // warranty.  In no event will the authors be held liable for any damages
@@ -21,8 +21,8 @@
 #include <string.h>
 #include <stdio.h>
 #include "Recast.h"
-#include "RecastLog.h"
-#include "RecastTimer.h"
+#include "RecastAlloc.h"
+#include "RecastAssert.h"
 
 
 static int getCornerHeight(int x, int y, int i, int dir,
@@ -33,44 +33,46 @@ static int getCornerHeight(int x, int y, int i, int dir,
        int ch = (int)s.y;
        int dirp = (dir+1) & 0x3;
        
-       unsigned short regs[4] = {0,0,0,0};
+       unsigned int regs[4] = {0,0,0,0};
        
-       regs[0] = s.reg;
+       // Combine region and area codes in order to prevent
+       // border vertices which are in between two areas to be removed. 
+       regs[0] = chf.spans[i].reg | (chf.areas[i] << 16);
        
-       if (rcGetCon(s, dir) != 0xf)
+       if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
        {
                const int ax = x + rcGetDirOffsetX(dir);
                const int ay = y + rcGetDirOffsetY(dir);
                const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
                const rcCompactSpan& as = chf.spans[ai];
                ch = rcMax(ch, (int)as.y);
-               regs[1] = as.reg;
-               if (rcGetCon(as, dirp) != 0xf)
+               regs[1] = chf.spans[ai].reg | (chf.areas[ai] << 16);
+               if (rcGetCon(as, dirp) != RC_NOT_CONNECTED)
                {
                        const int ax2 = ax + rcGetDirOffsetX(dirp);
                        const int ay2 = ay + rcGetDirOffsetY(dirp);
                        const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dirp);
                        const rcCompactSpan& as2 = chf.spans[ai2];
                        ch = rcMax(ch, (int)as2.y);
-                       regs[2] = as2.reg;
+                       regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16);
                }
        }
-       if (rcGetCon(s, dirp) != 0xf)
+       if (rcGetCon(s, dirp) != RC_NOT_CONNECTED)
        {
                const int ax = x + rcGetDirOffsetX(dirp);
                const int ay = y + rcGetDirOffsetY(dirp);
                const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dirp);
                const rcCompactSpan& as = chf.spans[ai];
                ch = rcMax(ch, (int)as.y);
-               regs[3] = as.reg;
-               if (rcGetCon(as, dir) != 0xf)
+               regs[3] = chf.spans[ai].reg | (chf.areas[ai] << 16);
+               if (rcGetCon(as, dir) != RC_NOT_CONNECTED)
                {
                        const int ax2 = ax + rcGetDirOffsetX(dir);
                        const int ay2 = ay + rcGetDirOffsetY(dir);
                        const int ai2 = (int)chf.cells[ax2+ay2*chf.width].index + rcGetCon(as, dir);
                        const rcCompactSpan& as2 = chf.spans[ai2];
                        ch = rcMax(ch, (int)as2.y);
-                       regs[2] = as2.reg;
+                       regs[2] = chf.spans[ai2].reg | (chf.areas[ai2] << 16);
                }
        }
 
@@ -86,8 +88,9 @@ static int getCornerHeight(int x, int y, int i, int dir,
                // followed by two interior cells and none of the regions are out of bounds.
                const bool twoSameExts = (regs[a] & regs[b] & RC_BORDER_REG) != 0 && regs[a] == regs[b];
                const bool twoInts = ((regs[c] | regs[d]) & RC_BORDER_REG) == 0;
+               const bool intsSameArea = (regs[c]>>16) == (regs[d]>>16);
                const bool noZeros = regs[a] != 0 && regs[b] != 0 && regs[c] != 0 && regs[d] != 0;
-               if (twoSameExts && twoInts && noZeros)
+               if (twoSameExts && twoInts && intsSameArea && noZeros)
                {
                        isBorderVertex = true;
                        break;
@@ -109,6 +112,8 @@ static void walkContour(int x, int y, int i,
        unsigned char startDir = dir;
        int starti = i;
        
+       const unsigned char area = chf.areas[i];
+       
        int iter = 0;
        while (++iter < 40000)
        {
@@ -116,6 +121,7 @@ static void walkContour(int x, int y, int i,
                {
                        // Choose the edge corner
                        bool isBorderVertex = false;
+                       bool isAreaBorder = false;
                        int px = x;
                        int py = getCornerHeight(x, y, i, dir, chf, isBorderVertex);
                        int pz = y;
@@ -127,16 +133,19 @@ static void walkContour(int x, int y, int i,
                        }
                        int r = 0;
                        const rcCompactSpan& s = chf.spans[i];
-                       if (rcGetCon(s, dir) != 0xf)
+                       if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
                        {
                                const int ax = x + rcGetDirOffsetX(dir);
                                const int ay = y + rcGetDirOffsetY(dir);
                                const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
-                               const rcCompactSpan& as = chf.spans[ai];
-                               r = (int)as.reg;
+                               r = (int)chf.spans[ai].reg;
+                               if (area != chf.areas[ai])
+                                       isAreaBorder = true;
                        }
                        if (isBorderVertex)
                                r |= RC_BORDER_VERTEX;
+                       if (isAreaBorder)
+                               r |= RC_AREA_BORDER;
                        points.push(px);
                        points.push(py);
                        points.push(pz);
@@ -151,7 +160,7 @@ static void walkContour(int x, int y, int i,
                        const int nx = x + rcGetDirOffsetX(dir);
                        const int ny = y + rcGetDirOffsetY(dir);
                        const rcCompactSpan& s = chf.spans[i];
-                       if (rcGetCon(s, dir) != 0xf)
+                       if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
                        {
                                const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
                                ni = (int)nc.index + rcGetCon(s, dir);
@@ -174,9 +183,9 @@ static void walkContour(int x, int y, int i,
        }
 }
 
-static float distancePtSeg(int x, int y, int z,
-                                                  int px, int py, int pz,
-                                                  int qx, int qy, int qz)
+static float distancePtSeg(const int x, const int z,
+                                                  const int px, const int pz,
+                                                  const int qx, const int qz)
 {
 /*     float pqx = (float)(qx - px);
        float pqy = (float)(qy - py);
@@ -218,20 +227,40 @@ static float distancePtSeg(int x, int y, int z,
        return dx*dx + dz*dz;
 }
 
-static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float maxError, int maxEdgeLen)
+static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
+                                                       const float maxError, const int maxEdgeLen, const int buildFlags)
 {
        // Add initial points.
-       bool noConnections = true;
+       bool hasConnections = false;
        for (int i = 0; i < points.size(); i += 4)
        {
-               if ((points[i+3] & 0xffff) != 0)
+               if ((points[i+3] & RC_CONTOUR_REG_MASK) != 0)
                {
-                       noConnections = false;
+                       hasConnections = true;
                        break;
                }
        }
        
-       if (noConnections)
+       if (hasConnections)
+       {
+               // The contour has some portals to other regions.
+               // Add a new point to every location where the region changes.
+               for (int i = 0, ni = points.size()/4; i < ni; ++i)
+               {
+                       int ii = (i+1) % ni;
+                       const bool differentRegs = (points[i*4+3] & RC_CONTOUR_REG_MASK) != (points[ii*4+3] & RC_CONTOUR_REG_MASK);
+                       const bool areaBorders = (points[i*4+3] & RC_AREA_BORDER) != (points[ii*4+3] & RC_AREA_BORDER);
+                       if (differentRegs || areaBorders)
+                       {
+                               simplified.push(points[i*4+0]);
+                               simplified.push(points[i*4+1]);
+                               simplified.push(points[i*4+2]);
+                               simplified.push(i);
+                       }
+               }       
+       }
+       
+       if (simplified.size() == 0)
        {
                // If there is no connections at all,
                // create some initial points for the simplification process. 
@@ -256,7 +285,7 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float ma
                                llz = z;
                                lli = i/4;
                        }
-                       if (x >= urx || (x == urx && z > urz))
+                       if (x > urx || (x == urx && z > urz))
                        {
                                urx = x;
                                ury = y;
@@ -274,22 +303,6 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float ma
                simplified.push(urz);
                simplified.push(uri);
        }
-       else
-       {
-               // The contour has some portals to other regions.
-               // Add a new point to every location where the region changes.
-               for (int i = 0, ni = points.size()/4; i < ni; ++i)
-               {
-                       int ii = (i+1) % ni;
-                       if ((points[i*4+3] & 0xffff) != (points[ii*4+3] & 0xffff))
-                       {
-                               simplified.push(points[i*4+0]);
-                               simplified.push(points[i*4+1]);
-                               simplified.push(points[i*4+2]);
-                               simplified.push(i);
-                       }
-               }       
-       }
        
        // Add points until all raw points are within
        // error tolerance to the simplified shape.
@@ -298,34 +311,48 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float ma
        {
                int ii = (i+1) % (simplified.size()/4);
                
-               int ax = simplified[i*4+0];
-               int ay = simplified[i*4+1];
-               int az = simplified[i*4+2];
-               int ai = simplified[i*4+3];
-               
-               int bx = simplified[ii*4+0];
-               int by = simplified[ii*4+1];
-               int bz = simplified[ii*4+2];
-               int bi = simplified[ii*4+3];
+               const int ax = simplified[i*4+0];
+               const int az = simplified[i*4+2];
+               const int ai = simplified[i*4+3];
                
+               const int bx = simplified[ii*4+0];
+               const int bz = simplified[ii*4+2];
+               const int bi = simplified[ii*4+3];
+
                // Find maximum deviation from the segment.
                float maxd = 0;
                int maxi = -1;
-               int ci = (ai+1) % pn;
+               int ci, cinc, endi;
                
-               // Tesselate only outer edges.
-               if ((points[ci*4+3] & 0xffff) == 0)
+               // Traverse the segment in lexilogical order so that the
+               // max deviation is calculated similarly when traversing
+               // opposite segments.
+               if (bx > ax || (bx == ax && bz > az))
                {
-                       while (ci != bi)
+                       cinc = 1;
+                       ci = (ai+cinc) % pn;
+                       endi = bi;
+               }
+               else
+               {
+                       cinc = pn-1;
+                       ci = (bi+cinc) % pn;
+                       endi = ai;
+               }
+               
+               // Tessellate only outer edges or edges between areas.
+               if ((points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0 ||
+                       (points[ci*4+3] & RC_AREA_BORDER))
+               {
+                       while (ci != endi)
                        {
-                               float d = distancePtSeg(points[ci*4+0], points[ci*4+1]/4, points[ci*4+2],
-                                                                               ax, ay/4, az, bx, by/4, bz);
+                               float d = distancePtSeg(points[ci*4+0], points[ci*4+2], ax, az, bx, bz);
                                if (d > maxd)
                                {
                                        maxd = d;
                                        maxi = ci;
                                }
-                               ci = (ci+1) % pn;
+                               ci = (ci+cinc) % pn;
                        }
                }
                
@@ -336,7 +363,7 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float ma
                {
                        // Add space for the new point.
                        simplified.resize(simplified.size()+4);
-                       int n = simplified.size()/4;
+                       const int n = simplified.size()/4;
                        for (int j = n-1; j > i; --j)
                        {
                                simplified[j*4+0] = simplified[(j-1)*4+0];
@@ -357,33 +384,52 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float ma
        }
        
        // Split too long edges.
-       if (maxEdgeLen > 0)
+       if (maxEdgeLen > 0 && (buildFlags & (RC_CONTOUR_TESS_WALL_EDGES|RC_CONTOUR_TESS_AREA_EDGES)) != 0)
        {
                for (int i = 0; i < simplified.size()/4; )
                {
-                       int ii = (i+1) % (simplified.size()/4);
-                       
-                       int ax = simplified[i*4+0];
-                       int az = simplified[i*4+2];
-                       int ai = simplified[i*4+3];
+                       const int ii = (i+1) % (simplified.size()/4);
                        
-                       int bx = simplified[ii*4+0];
-                       int bz = simplified[ii*4+2];
-                       int bi = simplified[ii*4+3];
+                       const int ax = simplified[i*4+0];
+                       const int az = simplified[i*4+2];
+                       const int ai = simplified[i*4+3];
                        
+                       const int bx = simplified[ii*4+0];
+                       const int bz = simplified[ii*4+2];
+                       const int bi = simplified[ii*4+3];
+
                        // Find maximum deviation from the segment.
                        int maxi = -1;
                        int ci = (ai+1) % pn;
+
+                       // Tessellate only outer edges or edges between areas.
+                       bool tess = false;
+                       // Wall edges.
+                       if ((buildFlags & RC_CONTOUR_TESS_WALL_EDGES) && (points[ci*4+3] & RC_CONTOUR_REG_MASK) == 0)
+                               tess = true;
+                       // Edges between areas.
+                       if ((buildFlags & RC_CONTOUR_TESS_AREA_EDGES) && (points[ci*4+3] & RC_AREA_BORDER))
+                               tess = true;
                        
-                       // Tesselate only outer edges.
-                       if ((points[ci*4+3] & 0xffff) == 0)
+                       if (tess)
                        {
                                int dx = bx - ax;
                                int dz = bz - az;
                                if (dx*dx + dz*dz > maxEdgeLen*maxEdgeLen)
                                {
-                                       int n = bi < ai ? (bi+pn - ai) : (bi - ai);
-                                       maxi = (ai + n/2) % pn;
+                                       // Round based on the segments in lexilogical order so that the
+                                       // max tesselation is consistent regardles in which direction
+                                       // segments are traversed.
+                                       if (bx > ax || (bx == ax && bz > az))
+                                       {
+                                               const int n = bi < ai ? (bi+pn - ai) : (bi - ai);
+                                               maxi = (ai + n/2) % pn;
+                                       }
+                                       else
+                                       {
+                                               const int n = bi < ai ? (bi+pn - ai) : (bi - ai);
+                                               maxi = (ai + (n+1)/2) % pn;
+                                       }
                                }
                        }
                        
@@ -393,7 +439,7 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float ma
                        {
                                // Add space for the new point.
                                simplified.resize(simplified.size()+4);
-                               int n = simplified.size()/4;
+                               const int n = simplified.size()/4;
                                for (int j = n-1; j > i; --j)
                                {
                                        simplified[j*4+0] = simplified[(j-1)*4+0];
@@ -420,7 +466,7 @@ static void simplifyContour(rcIntArray& points, rcIntArray& simplified, float ma
                // and the neighbour region is take from the next raw point.
                const int ai = (simplified[i*4+3]+1) % pn;
                const int bi = simplified[i*4+3];
-               simplified[i*4+3] = (points[ai*4+3] & 0xffff) | (points[bi*4+3] & RC_BORDER_VERTEX);
+               simplified[i*4+3] = (points[ai*4+3] & RC_CONTOUR_REG_MASK) | (points[bi*4+3] & RC_BORDER_VERTEX);
        }
        
 }
@@ -446,7 +492,7 @@ static void removeDegenerateSegments(rcIntArray& simplified)
                                simplified[j*4+2] = simplified[(j+1)*4+2];
                                simplified[j*4+3] = simplified[(j+1)*4+3];
                        }
-                       simplified.pop();
+                       simplified.resize(simplified.size()-4);
                }
        }
 }
@@ -463,25 +509,40 @@ static int calcAreaOfPolygon2D(const int* verts, const int nverts)
        return (area+1) / 2;
 }
 
+inline bool ileft(const int* a, const int* b, const int* c)
+{
+       return (b[0] - a[0]) * (c[2] - a[2]) - (c[0] - a[0]) * (b[2] - a[2]) <= 0;
+}
+
 static void getClosestIndices(const int* vertsa, const int nvertsa,
                                                          const int* vertsb, const int nvertsb,
                                                          int& ia, int& ib)
 {
        int closestDist = 0xfffffff;
+       ia = -1, ib = -1;
        for (int i = 0; i < nvertsa; ++i)
        {
+               const int in = (i+1) % nvertsa;
+               const int ip = (i+nvertsa-1) % nvertsa;
                const int* va = &vertsa[i*4];
+               const int* van = &vertsa[in*4];
+               const int* vap = &vertsa[ip*4];
+               
                for (int j = 0; j < nvertsb; ++j)
                {
                        const int* vb = &vertsb[j*4];
-                       const int dx = vb[0] - va[0];
-                       const int dz = vb[2] - va[2];
-                       const int d = dx*dx + dz*dz;
-                       if (d < closestDist)
+                       // vb must be "infront" of va.
+                       if (ileft(vap,va,vb) && ileft(va,van,vb))
                        {
-                               ia = i;
-                               ib = j;
-                               closestDist = d;
+                               const int dx = vb[0] - va[0];
+                               const int dz = vb[2] - va[2];
+                               const int d = dx*dx + dz*dz;
+                               if (d < closestDist)
+                               {
+                                       ia = i;
+                                       ib = j;
+                                       closestDist = d;
+                               }
                        }
                }
        }
@@ -490,7 +551,7 @@ static void getClosestIndices(const int* vertsa, const int nvertsa,
 static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
 {
        const int maxVerts = ca.nverts + cb.nverts + 2;
-       int* verts = new int[maxVerts*4];
+       int* verts = (int*)rcAlloc(sizeof(int)*maxVerts*4, RC_ALLOC_PERM);
        if (!verts)
                return false;
 
@@ -520,47 +581,73 @@ static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
                nv++;
        }
        
-       delete [] ca.verts;
+       rcFree(ca.verts);
        ca.verts = verts;
        ca.nverts = nv;
 
-       delete [] cb.verts;
+       rcFree(cb.verts);
        cb.verts = 0;
        cb.nverts = 0;
        
        return true;
 }
 
-bool rcBuildContours(rcCompactHeightfield& chf,
+/// @par
+///
+/// The raw contours will match the region outlines exactly. The @p maxError and @p maxEdgeLen
+/// parameters control how closely the simplified contours will match the raw contours.
+///
+/// Simplified contours are generated such that the vertices for portals between areas match up. 
+/// (They are considered mandatory vertices.)
+///
+/// Setting @p maxEdgeLength to zero will disabled the edge length feature.
+/// 
+/// See the #rcConfig documentation for more information on the configuration parameters.
+/// 
+/// @see rcAllocContourSet, rcCompactHeightfield, rcContourSet, rcConfig
+bool rcBuildContours(rcContext* ctx, rcCompactHeightfield& chf,
                                         const float maxError, const int maxEdgeLen,
-                                        rcContourSet& cset)
+                                        rcContourSet& cset, const int buildFlags)
 {
+       rcAssert(ctx);
+       
        const int w = chf.width;
        const int h = chf.height;
+       const int borderSize = chf.borderSize;
        
-       rcTimeVal startTime = rcGetPerformanceTimer();
+       ctx->startTimer(RC_TIMER_BUILD_CONTOURS);
        
-       vcopy(cset.bmin, chf.bmin);
-       vcopy(cset.bmax, chf.bmax);
+       rcVcopy(cset.bmin, chf.bmin);
+       rcVcopy(cset.bmax, chf.bmax);
+       if (borderSize > 0)
+       {
+               // If the heightfield was build with bordersize, remove the offset.
+               const float pad = borderSize*chf.cs;
+               cset.bmin[0] += pad;
+               cset.bmin[2] += pad;
+               cset.bmax[0] -= pad;
+               cset.bmax[2] -= pad;
+       }
        cset.cs = chf.cs;
        cset.ch = chf.ch;
+       cset.width = chf.width - chf.borderSize*2;
+       cset.height = chf.height - chf.borderSize*2;
+       cset.borderSize = chf.borderSize;
        
-       const int maxContours = chf.maxRegions*2;
-       cset.conts = new rcContour[maxContours];
+       int maxContours = rcMax((int)chf.maxRegions, 8);
+       cset.conts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
        if (!cset.conts)
                return false;
        cset.nconts = 0;
        
-       unsigned char* flags = new unsigned char[chf.spanCount];
+       rcScopedDelete<unsigned char> flags = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
        if (!flags)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags'.");
+               ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'flags' (%d).", chf.spanCount);
                return false;
        }
        
-       rcTimeVal traceStartTime = rcGetPerformanceTimer();
-                                       
+       ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
        
        // Mark boundaries.
        for (int y = 0; y < h; ++y)
@@ -572,7 +659,7 @@ bool rcBuildContours(rcCompactHeightfield& chf,
                        {
                                unsigned char res = 0;
                                const rcCompactSpan& s = chf.spans[i];
-                               if (!s.reg || (s.reg & RC_BORDER_REG))
+                               if (!chf.spans[i].reg || (chf.spans[i].reg & RC_BORDER_REG))
                                {
                                        flags[i] = 0;
                                        continue;
@@ -580,15 +667,14 @@ bool rcBuildContours(rcCompactHeightfield& chf,
                                for (int dir = 0; dir < 4; ++dir)
                                {
                                        unsigned short r = 0;
-                                       if (rcGetCon(s, dir) != 0xf)
+                                       if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
                                        {
                                                const int ax = x + rcGetDirOffsetX(dir);
                                                const int ay = y + rcGetDirOffsetY(dir);
                                                const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
-                                               const rcCompactSpan& as = chf.spans[ai];
-                                               r = as.reg;
+                                               r = chf.spans[ai].reg;
                                        }
-                                       if (r == s.reg)
+                                       if (r == chf.spans[i].reg)
                                                res |= (1 << dir);
                                }
                                flags[i] = res ^ 0xf; // Inverse, mark non connected edges.
@@ -596,9 +682,7 @@ bool rcBuildContours(rcCompactHeightfield& chf,
                }
        }
        
-       rcTimeVal traceEndTime = rcGetPerformanceTimer();
-       
-       rcTimeVal simplifyStartTime = rcGetPerformanceTimer();
+       ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
        
        rcIntArray verts(256);
        rcIntArray simplified(64);
@@ -615,36 +699,87 @@ bool rcBuildContours(rcCompactHeightfield& chf,
                                        flags[i] = 0;
                                        continue;
                                }
-                               unsigned short reg = chf.spans[i].reg;
+                               const unsigned short reg = chf.spans[i].reg;
                                if (!reg || (reg & RC_BORDER_REG))
                                        continue;
+                               const unsigned char area = chf.areas[i];
                                
                                verts.resize(0);
                                simplified.resize(0);
+
+                               ctx->startTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
                                walkContour(x, y, i, chf, flags, verts);
-                               simplifyContour(verts, simplified, maxError, maxEdgeLen);
+                               ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_TRACE);
+
+                               ctx->startTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
+                               simplifyContour(verts, simplified, maxError, maxEdgeLen, buildFlags);
                                removeDegenerateSegments(simplified);
+                               ctx->stopTimer(RC_TIMER_BUILD_CONTOURS_SIMPLIFY);
                                
+
                                // Store region->contour remap info.
                                // Create contour.
                                if (simplified.size()/4 >= 3)
                                {
                                        if (cset.nconts >= maxContours)
                                        {
-                                               if (rcGetLog())
-                                                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildContours: Too many contours %d, max %d.", cset.nconts, maxContours);
-                                               return false;
+                                               // Allocate more contours.
+                                               // This can happen when there are tiny holes in the heightfield.
+                                               const int oldMax = maxContours;
+                                               maxContours *= 2;
+                                               rcContour* newConts = (rcContour*)rcAlloc(sizeof(rcContour)*maxContours, RC_ALLOC_PERM);
+                                               for (int j = 0; j < cset.nconts; ++j)
+                                               {
+                                                       newConts[j] = cset.conts[j];
+                                                       // Reset source pointers to prevent data deletion.
+                                                       cset.conts[j].verts = 0;
+                                                       cset.conts[j].rverts = 0;
+                                               }
+                                               rcFree(cset.conts);
+                                               cset.conts = newConts;
+                                       
+                                               ctx->log(RC_LOG_WARNING, "rcBuildContours: Expanding max contours from %d to %d.", oldMax, maxContours);
                                        }
                                                
                                        rcContour* cont = &cset.conts[cset.nconts++];
                                        
                                        cont->nverts = simplified.size()/4;
-                                       cont->verts = new int[cont->nverts*4];
+                                       cont->verts = (int*)rcAlloc(sizeof(int)*cont->nverts*4, RC_ALLOC_PERM);
+                                       if (!cont->verts)
+                                       {
+                                               ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'verts' (%d).", cont->nverts);
+                                               return false;
+                                       }
                                        memcpy(cont->verts, &simplified[0], sizeof(int)*cont->nverts*4);
+                                       if (borderSize > 0)
+                                       {
+                                               // If the heightfield was build with bordersize, remove the offset.
+                                               for (int i = 0; i < cont->nverts; ++i)
+                                               {
+                                                       int* v = &cont->verts[i*4];
+                                                       v[0] -= borderSize;
+                                                       v[2] -= borderSize;
+                                               }
+                                       }
                                        
                                        cont->nrverts = verts.size()/4;
-                                       cont->rverts = new int[cont->nrverts*4];
+                                       cont->rverts = (int*)rcAlloc(sizeof(int)*cont->nrverts*4, RC_ALLOC_PERM);
+                                       if (!cont->rverts)
+                                       {
+                                               ctx->log(RC_LOG_ERROR, "rcBuildContours: Out of memory 'rverts' (%d).", cont->nrverts);
+                                               return false;
+                                       }
                                        memcpy(cont->rverts, &verts[0], sizeof(int)*cont->nrverts*4);
+                                       if (borderSize > 0)
+                                       {
+                                               // If the heightfield was build with bordersize, remove the offset.
+                                               for (int i = 0; i < cont->nrverts; ++i)
+                                               {
+                                                       int* v = &cont->rverts[i*4];
+                                                       v[0] -= borderSize;
+                                                       v[2] -= borderSize;
+                                               }
+                                       }
                                        
 /*                                     cont->cx = cont->cy = cont->cz = 0;
                                        for (int i = 0; i < cont->nverts; ++i)
@@ -658,13 +793,14 @@ bool rcBuildContours(rcCompactHeightfield& chf,
                                        cont->cz /= cont->nverts;*/
                                        
                                        cont->reg = reg;
+                                       cont->area = area;
                                }
                        }
                }
        }
        
        // Check and merge droppings.
-       // Sometimes the previous algorithms can fail and create several countours
+       // Sometimes the previous algorithms can fail and create several contours
        // per area. This pass will try to merge the holes into the main region.
        for (int i = 0; i < cset.nconts; ++i)
        {
@@ -689,44 +825,29 @@ bool rcBuildContours(rcCompactHeightfield& chf,
                        }
                        if (mergeIdx == -1)
                        {
-                               if (rcGetLog())
-                                       rcGetLog()->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i);
+                               ctx->log(RC_LOG_WARNING, "rcBuildContours: Could not find merge target for bad contour %d.", i);
                        }
                        else
                        {
                                rcContour& mcont = cset.conts[mergeIdx];
                                // Merge by closest points.
-                               int ia, ib;
+                               int ia = 0, ib = 0;
                                getClosestIndices(mcont.verts, mcont.nverts, cont.verts, cont.nverts, ia, ib);
+                               if (ia == -1 || ib == -1)
+                               {
+                                       ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to find merge points for %d and %d.", i, mergeIdx);
+                                       continue;
+                               }
                                if (!mergeContours(mcont, cont, ia, ib))
                                {
-                                       if (rcGetLog())
-                                               rcGetLog()->log(RC_LOG_WARNING, "rcBuildContours: Failed to merge contours %d and %d.", i, mergeIdx);
+                                       ctx->log(RC_LOG_WARNING, "rcBuildContours: Failed to merge contours %d and %d.", i, mergeIdx);
+                                       continue;
                                }
                        }
                }
        }
        
-               
-       delete [] flags;
-       
-       rcTimeVal simplifyEndTime = rcGetPerformanceTimer();
-       
-       rcTimeVal endTime = rcGetPerformanceTimer();
-       
-//     if (rcGetLog())
-//     {
-//             rcGetLog()->log(RC_LOG_PROGRESS, "Create contours: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
-//             rcGetLog()->log(RC_LOG_PROGRESS, " - boundary: %.3f ms", rcGetDeltaTimeUsec(boundaryStartTime, boundaryEndTime)/1000.0f);
-//             rcGetLog()->log(RC_LOG_PROGRESS, " - contour: %.3f ms", rcGetDeltaTimeUsec(contourStartTime, contourEndTime)/1000.0f);
-//     }
-
-       if (rcGetBuildTimes())
-       {
-               rcGetBuildTimes()->buildContours += rcGetDeltaTimeUsec(startTime, endTime);
-               rcGetBuildTimes()->buildContoursTrace += rcGetDeltaTimeUsec(traceStartTime, traceEndTime);
-               rcGetBuildTimes()->buildContoursSimplify += rcGetDeltaTimeUsec(simplifyStartTime, simplifyEndTime);
-       }
+       ctx->stopTimer(RC_TIMER_BUILD_CONTOURS);
        
        return true;
 }
index ebe60714a18ff285a5e54d0d7a9099587cd6d2ef..bf985c362c91ab2ce173fa2fdd6786335fad9fc4 100644 (file)
@@ -1,5 +1,5 @@
 //
-// Copyright (c) 2009 Mikko Mononen memon@inside.org
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
 //
 // This software is provided 'as-is', without any express or implied
 // warranty.  In no event will the authors be held liable for any damages
 #include <math.h>
 #include <stdio.h>
 #include "Recast.h"
-#include "RecastLog.h"
-#include "RecastTimer.h"
+#include "RecastAssert.h"
 
+/// @par
+///
+/// Allows the formation of walkable regions that will flow over low lying 
+/// objects such as curbs, and up structures such as stairways. 
+/// 
+/// Two neighboring spans are walkable if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) < waklableClimb</tt>
+/// 
+/// @warning Will override the effect of #rcFilterLedgeSpans.  So if both filters are used, call
+/// #rcFilterLedgeSpans after calling this filter. 
+///
+/// @see rcHeightfield, rcConfig
+void rcFilterLowHangingWalkableObstacles(rcContext* ctx, const int walkableClimb, rcHeightfield& solid)
+{
+       rcAssert(ctx);
+
+       ctx->startTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
+       
+       const int w = solid.width;
+       const int h = solid.height;
+       
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       rcSpan* ps = 0;
+                       bool previousWalkable = false;
+                       unsigned char previousArea = RC_NULL_AREA;
+                       
+                       for (rcSpan* s = solid.spans[x + y*w]; s; ps = s, s = s->next)
+                       {
+                               const bool walkable = s->area != RC_NULL_AREA;
+                               // If current span is not walkable, but there is walkable
+                               // span just below it, mark the span above it walkable too.
+                               if (!walkable && previousWalkable)
+                               {
+                                       if (rcAbs((int)s->smax - (int)ps->smax) <= walkableClimb)
+                                               s->area = previousArea;
+                               }
+                               // Copy walkable flag so that it cannot propagate
+                               // past multiple non-walkable objects.
+                               previousWalkable = walkable;
+                               previousArea = s->area;
+                       }
+               }
+       }
+
+       ctx->stopTimer(RC_TIMER_FILTER_LOW_OBSTACLES);
+}
 
-void rcFilterLedgeSpans(const int walkableHeight,
-                                               const int walkableClimb,
+/// @par
+///
+/// A ledge is a span with one or more neighbors whose maximum is further away than @p walkableClimb
+/// from the current span's maximum.
+/// This method removes the impact of the overestimation of conservative voxelization 
+/// so the resulting mesh will not have regions hanging in the air over ledges.
+/// 
+/// A span is a ledge if: <tt>rcAbs(currentSpan.smax - neighborSpan.smax) > walkableClimb</tt>
+/// 
+/// @see rcHeightfield, rcConfig
+void rcFilterLedgeSpans(rcContext* ctx, const int walkableHeight, const int walkableClimb,
                                                rcHeightfield& solid)
 {
-       rcTimeVal startTime = rcGetPerformanceTimer();
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_FILTER_BORDER);
 
        const int w = solid.width;
        const int h = solid.height;
@@ -42,15 +100,19 @@ void rcFilterLedgeSpans(const int walkableHeight,
                        for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
                        {
                                // Skip non walkable spans.
-                               if ((s->flags & RC_WALKABLE) == 0)
+                               if (s->area == RC_NULL_AREA)
                                        continue;
                                
-                               const int bot = (int)s->smax;
-                               const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
+                               const int bot = (int)(s->smax);
+                               const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
                                
                                // Find neighbours minimum height.
                                int minh = MAX_HEIGHT;
 
+                               // Min and max height of accessible neighbours.
+                               int asmin = s->smax;
+                               int asmax = s->smax;
+
                                for (int dir = 0; dir < 4; ++dir)
                                {
                                        int dx = x + rcGetDirOffsetX(dir);
@@ -77,30 +139,49 @@ void rcFilterLedgeSpans(const int walkableHeight,
                                                ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
                                                // Skip neightbour if the gap between the spans is too small.
                                                if (rcMin(top,ntop) - rcMax(bot,nbot) > walkableHeight)
+                                               {
                                                        minh = rcMin(minh, nbot - bot);
+                                               
+                                                       // Find min/max accessible neighbour height. 
+                                                       if (rcAbs(nbot - bot) <= walkableClimb)
+                                                       {
+                                                               if (nbot < asmin) asmin = nbot;
+                                                               if (nbot > asmax) asmax = nbot;
+                                                       }
+                                                       
+                                               }
                                        }
                                }
                                
                                // The current span is close to a ledge if the drop to any
                                // neighbour span is less than the walkableClimb.
                                if (minh < -walkableClimb)
-                                       s->flags &= ~RC_WALKABLE;
-                               
+                                       s->area = RC_NULL_AREA;
+                                       
+                               // If the difference between all neighbours is too large,
+                               // we are at steep slope, mark the span as ledge.
+                               if ((asmax - asmin) > walkableClimb)
+                               {
+                                       s->area = RC_NULL_AREA;
+                               }
                        }
                }
        }
        
-       rcTimeVal endTime = rcGetPerformanceTimer();
-//     if (rcGetLog())
-//             rcGetLog()->log(RC_LOG_PROGRESS, "Filter border: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
-       if (rcGetBuildTimes())
-               rcGetBuildTimes()->filterBorder += rcGetDeltaTimeUsec(startTime, endTime);
+       ctx->stopTimer(RC_TIMER_FILTER_BORDER);
 }      
 
-void rcFilterWalkableLowHeightSpans(int walkableHeight,
-                                                                       rcHeightfield& solid)
+/// @par
+///
+/// For this filter, the clearance above the span is the distance from the span's 
+/// maximum to the next higher span's minimum. (Same grid column.)
+/// 
+/// @see rcHeightfield, rcConfig
+void rcFilterWalkableLowHeightSpans(rcContext* ctx, int walkableHeight, rcHeightfield& solid)
 {
-       rcTimeVal startTime = rcGetPerformanceTimer();
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_FILTER_WALKABLE);
        
        const int w = solid.width;
        const int h = solid.height;
@@ -114,136 +195,13 @@ void rcFilterWalkableLowHeightSpans(int walkableHeight,
                {
                        for (rcSpan* s = solid.spans[x + y*w]; s; s = s->next)
                        {
-                               const int bot = (int)s->smax;
-                               const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;
+                               const int bot = (int)(s->smax);
+                               const int top = s->next ? (int)(s->next->smin) : MAX_HEIGHT;
                                if ((top - bot) <= walkableHeight)
-                                       s->flags &= ~RC_WALKABLE;
+                                       s->area = RC_NULL_AREA;
                        }
                }
        }
        
-       rcTimeVal endTime = rcGetPerformanceTimer();
-
-//     if (rcGetLog())
-//             rcGetLog()->log(RC_LOG_PROGRESS, "Filter walkable: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
-       if (rcGetBuildTimes())
-               rcGetBuildTimes()->filterWalkable += rcGetDeltaTimeUsec(startTime, endTime);
-}
-
-
-struct rcReachableSeed
-{
-       inline void set(int ix, int iy, rcSpan* is)
-       {
-               x = (unsigned short)ix;
-               y = (unsigned short)iy;
-               s = is;
-       }
-       unsigned short x, y;
-       rcSpan* s;
-};
-
-bool rcMarkReachableSpans(const int walkableHeight,
-                                                 const int walkableClimb,
-                                                 rcHeightfield& solid)
-{
-       const int w = solid.width;
-       const int h = solid.height;
-       const int MAX_HEIGHT = 0xffff;
-       
-       rcTimeVal startTime = rcGetPerformanceTimer();
-       
-       // Build navigable space.
-       const int MAX_SEEDS = w*h;
-       rcReachableSeed* stack = new rcReachableSeed[MAX_SEEDS];
-       if (!stack)
-       {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcMarkReachableSpans: Out of memory 'stack' (%d).", MAX_SEEDS);
-               return false;
-       }
-       int stackSize = 0;
-       
-       for (int y = 0; y < h; ++y)
-       {
-               for (int x = 0; x < w; ++x)
-               {
-                       rcSpan* topSpan = solid.spans[x + y*w];
-                       if (!topSpan)
-                               continue;
-                       while (topSpan->next)
-                               topSpan = topSpan->next;
-                       
-                       // If the span is not walkable, skip it.
-                       if ((topSpan->flags & RC_WALKABLE) == 0)
-                               continue;
-                       // If the span has been visited already, skip it.
-                       if (topSpan->flags & RC_REACHABLE)
-                               continue;
-                       
-                       // Start flood fill.
-                       topSpan->flags |= RC_REACHABLE;
-                       stackSize = 0;
-                       stack[stackSize].set(x, y, topSpan);
-                       stackSize++;
-                       
-                       while (stackSize)
-                       {
-                               // Pop a seed from the stack.
-                               stackSize--;
-                               rcReachableSeed cur = stack[stackSize];
-                               
-                               const int bot = (int)cur.s->smax;
-                               const int top = cur.s->next ? (int)cur.s->next->smin : MAX_HEIGHT;
-                               
-                               // Visit neighbours in all 4 directions.
-                               for (int dir = 0; dir < 4; ++dir)
-                               {
-                                       int dx = (int)cur.x + rcGetDirOffsetX(dir);
-                                       int dy = (int)cur.y + rcGetDirOffsetY(dir);
-                                       // Skip neighbour which are out of bounds.
-                                       if (dx < 0 || dy < 0 || dx >= w || dy >= h)
-                                               continue;
-                                       for (rcSpan* ns = solid.spans[dx + dy*w]; ns; ns = ns->next)
-                                       {
-                                               // Skip neighbour if it is not walkable.
-                                               if ((ns->flags & RC_WALKABLE) == 0)
-                                                       continue;
-                                               // Skip the neighbour if it has been visited already.
-                                               if (ns->flags & RC_REACHABLE)
-                                                       continue;
-                                               
-                                               const int nbot = (int)ns->smax;
-                                               const int ntop = ns->next ? (int)ns->next->smin : MAX_HEIGHT;
-                                               // Skip neightbour if the gap between the spans is too small.
-                                               if (rcMin(top,ntop) - rcMax(bot,nbot) < walkableHeight)
-                                                       continue;
-                                               // Skip neightbour if the climb height to the neighbour is too high.
-                                               if (rcAbs(nbot - bot) >= walkableClimb)
-                                                       continue;
-                                               
-                                               // This neighbour has not been visited yet.
-                                               // Mark it as reachable and add it to the seed stack.
-                                               ns->flags |= RC_REACHABLE;
-                                               if (stackSize < MAX_SEEDS)
-                                               {
-                                                       stack[stackSize].set(dx, dy, ns);
-                                                       stackSize++;
-                                               }
-                                       }
-                               }
-                       }
-               }
-       }
-       
-       delete [] stack;        
-       
-       rcTimeVal endTime = rcGetPerformanceTimer();
-       
-//     if (rcGetLog())
-//             rcGetLog()->log(RC_LOG_PROGRESS, "Mark reachable: %.3f ms", rcGetDeltaTimeUsec(startTime, endTime)/1000.0f);
-       if (rcGetBuildTimes())
-               rcGetBuildTimes()->filterMarkReachable += rcGetDeltaTimeUsec(startTime, endTime);
-       
-       return true;
+       ctx->stopTimer(RC_TIMER_FILTER_WALKABLE);
 }
diff --git a/extern/recastnavigation/Recast/Source/RecastLayers.cpp b/extern/recastnavigation/Recast/Source/RecastLayers.cpp
new file mode 100644 (file)
index 0000000..617cf45
--- /dev/null
@@ -0,0 +1,620 @@
+//
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
+//
+// This software is provided 'as-is', without any express or implied
+// warranty.  In no event will the authors be held liable for any damages
+// arising from the use of this software.
+// Permission is granted to anyone to use this software for any purpose,
+// including commercial applications, and to alter it and redistribute it
+// freely, subject to the following restrictions:
+// 1. The origin of this software must not be misrepresented; you must not
+//    claim that you wrote the original software. If you use this software
+//    in a product, an acknowledgment in the product documentation would be
+//    appreciated but is not required.
+// 2. Altered source versions must be plainly marked as such, and must not be
+//    misrepresented as being the original software.
+// 3. This notice may not be removed or altered from any source distribution.
+//
+
+#include <float.h>
+#define _USE_MATH_DEFINES
+#include <math.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "Recast.h"
+#include "RecastAlloc.h"
+#include "RecastAssert.h"
+
+
+static const int RC_MAX_LAYERS = RC_NOT_CONNECTED;
+static const int RC_MAX_NEIS = 16;
+
+struct rcLayerRegion
+{
+       unsigned char layers[RC_MAX_LAYERS];
+       unsigned char neis[RC_MAX_NEIS];
+       unsigned short ymin, ymax;
+       unsigned char layerId;          // Layer ID
+       unsigned char nlayers;          // Layer count
+       unsigned char nneis;            // Neighbour count
+       unsigned char base;                     // Flag indicating if the region is hte base of merged regions.
+};
+
+
+static void addUnique(unsigned char* a, unsigned char& an, unsigned char v)
+{
+       const int n = (int)an;
+       for (int i = 0; i < n; ++i)
+               if (a[i] == v)
+                       return;
+       a[an] = v;
+       an++;
+}
+
+static bool contains(const unsigned char* a, const unsigned char an, const unsigned char v)
+{
+       const int n = (int)an;
+       for (int i = 0; i < n; ++i)
+               if (a[i] == v)
+                       return true;
+       return false;
+}
+
+inline bool overlapRange(const unsigned short amin, const unsigned short amax,
+                                                const unsigned short bmin, const unsigned short bmax)
+{
+       return (amin > bmax || amax < bmin) ? false : true;
+}
+
+
+
+struct rcLayerSweepSpan
+{
+       unsigned short ns;      // number samples
+       unsigned char id;       // region id
+       unsigned char nei;      // neighbour id
+};
+
+/// @par
+/// 
+/// See the #rcConfig documentation for more information on the configuration parameters.
+/// 
+/// @see rcAllocHeightfieldLayerSet, rcCompactHeightfield, rcHeightfieldLayerSet, rcConfig
+bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
+                                                         const int borderSize, const int walkableHeight,
+                                                         rcHeightfieldLayerSet& lset)
+{
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_BUILD_LAYERS);
+       
+       const int w = chf.width;
+       const int h = chf.height;
+       
+       rcScopedDelete<unsigned char> srcReg = (unsigned char*)rcAlloc(sizeof(unsigned char)*chf.spanCount, RC_ALLOC_TEMP);
+       if (!srcReg)
+       {
+               ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'srcReg' (%d).", chf.spanCount);
+               return false;
+       }
+       memset(srcReg,0xff,sizeof(unsigned char)*chf.spanCount);
+       
+       const int nsweeps = chf.width;
+       rcScopedDelete<rcLayerSweepSpan> sweeps = (rcLayerSweepSpan*)rcAlloc(sizeof(rcLayerSweepSpan)*nsweeps, RC_ALLOC_TEMP);
+       if (!sweeps)
+       {
+               ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'sweeps' (%d).", nsweeps);
+               return false;
+       }
+       
+       
+       // Partition walkable area into monotone regions.
+       int prevCount[256];
+       unsigned char regId = 0;
+
+       for (int y = borderSize; y < h-borderSize; ++y)
+       {
+               memset(prevCount,0,sizeof(int)*regId);
+               unsigned char sweepId = 0;
+               
+               for (int x = borderSize; x < w-borderSize; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               const rcCompactSpan& s = chf.spans[i];
+                               if (chf.areas[i] == RC_NULL_AREA) continue;
+
+                               unsigned char sid = 0xff;
+
+                               // -x
+                               if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
+                               {
+                                       const int ax = x + rcGetDirOffsetX(0);
+                                       const int ay = y + rcGetDirOffsetY(0);
+                                       const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 0);
+                                       if (chf.areas[ai] != RC_NULL_AREA && srcReg[ai] != 0xff)
+                                               sid = srcReg[ai];
+                               }
+                               
+                               if (sid == 0xff)
+                               {
+                                       sid = sweepId++;
+                                       sweeps[sid].nei = 0xff;
+                                       sweeps[sid].ns = 0;
+                               }
+                               
+                               // -y
+                               if (rcGetCon(s,3) != RC_NOT_CONNECTED)
+                               {
+                                       const int ax = x + rcGetDirOffsetX(3);
+                                       const int ay = y + rcGetDirOffsetY(3);
+                                       const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, 3);
+                                       const unsigned char nr = srcReg[ai];
+                                       if (nr != 0xff)
+                                       {
+                                               // Set neighbour when first valid neighbour is encoutered.
+                                               if (sweeps[sid].ns == 0)
+                                                       sweeps[sid].nei = nr;
+                                               
+                                               if (sweeps[sid].nei == nr)
+                                               {
+                                                       // Update existing neighbour
+                                                       sweeps[sid].ns++;
+                                                       prevCount[nr]++;
+                                               }
+                                               else
+                                               {
+                                                       // This is hit if there is nore than one neighbour.
+                                                       // Invalidate the neighbour.
+                                                       sweeps[sid].nei = 0xff;
+                                               }
+                                       }
+                               }
+                               
+                               srcReg[i] = sid;
+                       }
+               }
+               
+               // Create unique ID.
+               for (int i = 0; i < sweepId; ++i)
+               {
+                       // If the neighbour is set and there is only one continuous connection to it,
+                       // the sweep will be merged with the previous one, else new region is created.
+                       if (sweeps[i].nei != 0xff && prevCount[sweeps[i].nei] == (int)sweeps[i].ns)
+                       {
+                               sweeps[i].id = sweeps[i].nei;
+                       }
+                       else
+                       {
+                               if (regId == 255)
+                               {
+                                       ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Region ID overflow.");
+                                       return false;
+                               }
+                               sweeps[i].id = regId++;
+                       }
+               }
+               
+               // Remap local sweep ids to region ids.
+               for (int x = borderSize; x < w-borderSize; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               if (srcReg[i] != 0xff)
+                                       srcReg[i] = sweeps[srcReg[i]].id;
+                       }
+               }
+       }
+
+       // Allocate and init layer regions.
+       const int nregs = (int)regId;
+       rcScopedDelete<rcLayerRegion> regs = (rcLayerRegion*)rcAlloc(sizeof(rcLayerRegion)*nregs, RC_ALLOC_TEMP);
+       if (!regs)
+       {
+               ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'regs' (%d).", nregs);
+               return false;
+       }
+       memset(regs, 0, sizeof(rcLayerRegion)*nregs);
+       for (int i = 0; i < nregs; ++i)
+       {
+               regs[i].layerId = 0xff;
+               regs[i].ymin = 0xffff;
+               regs[i].ymax = 0;
+       }
+       
+       // Find region neighbours and overlapping regions.
+       for (int y = 0; y < h; ++y)
+       {
+               for (int x = 0; x < w; ++x)
+               {
+                       const rcCompactCell& c = chf.cells[x+y*w];
+                       
+                       unsigned char lregs[RC_MAX_LAYERS];
+                       int nlregs = 0;
+                       
+                       for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                       {
+                               const rcCompactSpan& s = chf.spans[i];
+                               const unsigned char ri = srcReg[i];
+                               if (ri == 0xff) continue;
+                               
+                               regs[ri].ymin = rcMin(regs[ri].ymin, s.y);
+                               regs[ri].ymax = rcMax(regs[ri].ymax, s.y);
+                               
+                               // Collect all region layers.
+                               if (nlregs < RC_MAX_LAYERS)
+                                       lregs[nlregs++] = ri;
+                               
+                               // Update neighbours
+                               for (int dir = 0; dir < 4; ++dir)
+                               {
+                                       if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
+                                       {
+                                               const int ax = x + rcGetDirOffsetX(dir);
+                                               const int ay = y + rcGetDirOffsetY(dir);
+                                               const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
+                                               const unsigned char rai = srcReg[ai];
+                                               if (rai != 0xff && rai != ri)
+                                                       addUnique(regs[ri].neis, regs[ri].nneis, rai);
+                                       }
+                               }
+                               
+                       }
+                       
+                       // Update overlapping regions.
+                       for (int i = 0; i < nlregs-1; ++i)
+                       {
+                               for (int j = i+1; j < nlregs; ++j)
+                               {
+                                       if (lregs[i] != lregs[j])
+                                       {
+                                               rcLayerRegion& ri = regs[lregs[i]];
+                                               rcLayerRegion& rj = regs[lregs[j]];
+                                               addUnique(ri.layers, ri.nlayers, lregs[j]);
+                                               addUnique(rj.layers, rj.nlayers, lregs[i]);
+                                       }
+                               }
+                       }
+                       
+               }
+       }
+       
+       // Create 2D layers from regions.
+       unsigned char layerId = 0;
+       
+       static const int MAX_STACK = 64;
+       unsigned char stack[MAX_STACK];
+       int nstack = 0;
+       
+       for (int i = 0; i < nregs; ++i)
+       {
+               rcLayerRegion& root = regs[i];
+               // Skip alreadu visited.
+               if (root.layerId != 0xff)
+                       continue;
+
+               // Start search.
+               root.layerId = layerId;
+               root.base = 1;
+               
+               nstack = 0;
+               stack[nstack++] = (unsigned char)i;
+               
+               while (nstack)
+               {
+                       // Pop front
+                       rcLayerRegion& reg = regs[stack[0]];
+                       nstack--;
+                       for (int j = 0; j < nstack; ++j)
+                               stack[j] = stack[j+1];
+                       
+                       const int nneis = (int)reg.nneis;
+                       for (int j = 0; j < nneis; ++j)
+                       {
+                               const unsigned char nei = reg.neis[j];
+                               rcLayerRegion& regn = regs[nei];
+                               // Skip already visited.
+                               if (regn.layerId != 0xff)
+                                       continue;
+                               // Skip if the neighbour is overlapping root region.
+                               if (contains(root.layers, root.nlayers, nei))
+                                       continue;
+                               // Skip if the height range would become too large.
+                               const int ymin = rcMin(root.ymin, regn.ymin);
+                               const int ymax = rcMin(root.ymax, regn.ymax);
+                               if ((ymax - ymin) >= 255)
+                                        continue;
+
+                               if (nstack < MAX_STACK)
+                               {
+                                       // Deepen
+                                       stack[nstack++] = (unsigned char)nei;
+                                       
+                                       // Mark layer id
+                                       regn.layerId = layerId;
+                                       // Merge current layers to root.
+                                       for (int k = 0; k < regn.nlayers; ++k)
+                                               addUnique(root.layers, root.nlayers, regn.layers[k]);
+                                       root.ymin = rcMin(root.ymin, regn.ymin);
+                                       root.ymax = rcMax(root.ymax, regn.ymax);
+                               }
+                       }
+               }
+               
+               layerId++;
+       }
+       
+       // Merge non-overlapping regions that are close in height.
+       const unsigned short mergeHeight = (unsigned short)walkableHeight * 4;
+       
+       for (int i = 0; i < nregs; ++i)
+       {
+               rcLayerRegion& ri = regs[i];
+               if (!ri.base) continue;
+               
+               unsigned char newId = ri.layerId;
+               
+               for (;;)
+               {
+                       unsigned char oldId = 0xff;
+                       
+                       for (int j = 0; j < nregs; ++j)
+                       {
+                               if (i == j) continue;
+                               rcLayerRegion& rj = regs[j];
+                               if (!rj.base) continue;
+                               
+                               // Skip if teh regions are not close to each other.
+                               if (!overlapRange(ri.ymin,ri.ymax+mergeHeight, rj.ymin,rj.ymax+mergeHeight))
+                                       continue;
+                               // Skip if the height range would become too large.
+                               const int ymin = rcMin(ri.ymin, rj.ymin);
+                               const int ymax = rcMin(ri.ymax, rj.ymax);
+                               if ((ymax - ymin) >= 255)
+                                 continue;
+                                                 
+                               // Make sure that there is no overlap when mergin 'ri' and 'rj'.
+                               bool overlap = false;
+                               // Iterate over all regions which have the same layerId as 'rj'
+                               for (int k = 0; k < nregs; ++k)
+                               {
+                                       if (regs[k].layerId != rj.layerId)
+                                               continue;
+                                       // Check if region 'k' is overlapping region 'ri'
+                                       // Index to 'regs' is the same as region id.
+                                       if (contains(ri.layers,ri.nlayers, (unsigned char)k))
+                                       {
+                                               overlap = true;
+                                               break;
+                                       }
+                               }
+                               // Cannot merge of regions overlap.
+                               if (overlap)
+                                       continue;
+                               
+                               // Can merge i and j.
+                               oldId = rj.layerId;
+                               break;
+                       }
+                       
+                       // Could not find anything to merge with, stop.
+                       if (oldId == 0xff)
+                               break;
+                       
+                       // Merge
+                       for (int j = 0; j < nregs; ++j)
+                       {
+                               rcLayerRegion& rj = regs[j];
+                               if (rj.layerId == oldId)
+                               {
+                                       rj.base = 0;
+                                       // Remap layerIds.
+                                       rj.layerId = newId;
+                                       // Add overlaid layers from 'rj' to 'ri'.
+                                       for (int k = 0; k < rj.nlayers; ++k)
+                                               addUnique(ri.layers, ri.nlayers, rj.layers[k]);
+                                       // Update heigh bounds.
+                                       ri.ymin = rcMin(ri.ymin, rj.ymin);
+                                       ri.ymax = rcMax(ri.ymax, rj.ymax);
+                               }
+                       }
+               }
+       }
+       
+       // Compact layerIds
+       unsigned char remap[256];
+       memset(remap, 0, 256);
+
+       // Find number of unique layers.
+       layerId = 0;
+       for (int i = 0; i < nregs; ++i)
+               remap[regs[i].layerId] = 1;
+       for (int i = 0; i < 256; ++i)
+       {
+               if (remap[i])
+                       remap[i] = layerId++;
+               else
+                       remap[i] = 0xff;
+       }
+       // Remap ids.
+       for (int i = 0; i < nregs; ++i)
+               regs[i].layerId = remap[regs[i].layerId];
+       
+       // No layers, return empty.
+       if (layerId == 0)
+       {
+               ctx->stopTimer(RC_TIMER_BUILD_LAYERS);
+               return true;
+       }
+       
+       // Create layers.
+       rcAssert(lset.layers == 0);
+       
+       const int lw = w - borderSize*2;
+       const int lh = h - borderSize*2;
+
+       // Build contracted bbox for layers.
+       float bmin[3], bmax[3];
+       rcVcopy(bmin, chf.bmin);
+       rcVcopy(bmax, chf.bmax);
+       bmin[0] += borderSize*chf.cs;
+       bmin[2] += borderSize*chf.cs;
+       bmax[0] -= borderSize*chf.cs;
+       bmax[2] -= borderSize*chf.cs;
+       
+       lset.nlayers = (int)layerId;
+       
+       lset.layers = (rcHeightfieldLayer*)rcAlloc(sizeof(rcHeightfieldLayer)*lset.nlayers, RC_ALLOC_PERM);
+       if (!lset.layers)
+       {
+               ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'layers' (%d).", lset.nlayers);
+               return false;
+       }
+       memset(lset.layers, 0, sizeof(rcHeightfieldLayer)*lset.nlayers);
+
+       
+       // Store layers.
+       for (int i = 0; i < lset.nlayers; ++i)
+       {
+               unsigned char curId = (unsigned char)i;
+               
+               // Allocate memory for the current layer.
+               rcHeightfieldLayer* layer = &lset.layers[i];
+               memset(layer, 0, sizeof(rcHeightfieldLayer));
+
+               const int gridSize = sizeof(unsigned char)*lw*lh;
+
+               layer->heights = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
+               if (!layer->heights)
+               {
+                       ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'heights' (%d).", gridSize);
+                       return false;
+               }
+               memset(layer->heights, 0xff, gridSize);
+
+               layer->areas = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
+               if (!layer->areas)
+               {
+                       ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'areas' (%d).", gridSize);
+                       return false;
+               }
+               memset(layer->areas, 0, gridSize);
+
+               layer->cons = (unsigned char*)rcAlloc(gridSize, RC_ALLOC_PERM);
+               if (!layer->cons)
+               {
+                       ctx->log(RC_LOG_ERROR, "rcBuildHeightfieldLayers: Out of memory 'cons' (%d).", gridSize);
+                       return false;
+               }
+               memset(layer->cons, 0, gridSize);
+               
+               // Find layer height bounds.
+               int hmin = 0, hmax = 0;
+               for (int j = 0; j < nregs; ++j)
+               {
+                       if (regs[j].base && regs[j].layerId == curId)
+                       {
+                               hmin = (int)regs[j].ymin;
+                               hmax = (int)regs[j].ymax;
+                       }
+               }
+
+               layer->width = lw;
+               layer->height = lh;
+               layer->cs = chf.cs;
+               layer->ch = chf.ch;
+               
+               // Adjust the bbox to fit the heighfield.
+               rcVcopy(layer->bmin, bmin);
+               rcVcopy(layer->bmax, bmax);
+               layer->bmin[1] = bmin[1] + hmin*chf.ch;
+               layer->bmax[1] = bmin[1] + hmax*chf.ch;
+               layer->hmin = hmin;
+               layer->hmax = hmax;
+
+               // Update usable data region.
+               layer->minx = layer->width;
+               layer->maxx = 0;
+               layer->miny = layer->height;
+               layer->maxy = 0;
+               
+               // Copy height and area from compact heighfield. 
+               for (int y = 0; y < lh; ++y)
+               {
+                       for (int x = 0; x < lw; ++x)
+                       {
+                               const int cx = borderSize+x;
+                               const int cy = borderSize+y;
+                               const rcCompactCell& c = chf.cells[cx+cy*w];
+                               for (int i = (int)c.index, ni = (int)(c.index+c.count); i < ni; ++i)
+                               {
+                                       const rcCompactSpan& s = chf.spans[i];
+                                       // Skip unassigned regions.
+                                       if (srcReg[i] == 0xff)
+                                               continue;
+                                       // Skip of does nto belong to current layer.
+                                       unsigned char lid = regs[srcReg[i]].layerId;
+                                       if (lid != curId)
+                                               continue;
+                                       
+                                       // Update data bounds.
+                                       layer->minx = rcMin(layer->minx, x);
+                                       layer->maxx = rcMax(layer->maxx, x);
+                                       layer->miny = rcMin(layer->miny, y);
+                                       layer->maxy = rcMax(layer->maxy, y);
+                                       
+                                       // Store height and area type.
+                                       const int idx = x+y*lw;
+                                       layer->heights[idx] = (unsigned char)(s.y - hmin);
+                                       layer->areas[idx] = chf.areas[i];
+                                       
+                                       // Check connection.
+                                       unsigned char portal = 0;
+                                       unsigned char con = 0;
+                                       for (int dir = 0; dir < 4; ++dir)
+                                       {
+                                               if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
+                                               {
+                                                       const int ax = cx + rcGetDirOffsetX(dir);
+                                                       const int ay = cy + rcGetDirOffsetY(dir);
+                                                       const int ai = (int)chf.cells[ax+ay*w].index + rcGetCon(s, dir);
+                                                       unsigned char alid = srcReg[ai] != 0xff ? regs[srcReg[ai]].layerId : 0xff;
+                                                       // Portal mask
+                                                       if (chf.areas[ai] != RC_NULL_AREA && lid != alid)
+                                                       {
+                                                               portal |= (unsigned char)(1<<dir);
+                                                               // Update height so that it matches on both sides of the portal.
+                                                               const rcCompactSpan& as = chf.spans[ai];
+                                                               if (as.y > hmin)
+                                                                       layer->heights[idx] = rcMax(layer->heights[idx], (unsigned char)(as.y - hmin));
+                                                       }
+                                                       // Valid connection mask
+                                                       if (chf.areas[ai] != RC_NULL_AREA && lid == alid)
+                                                       {
+                                                               const int nx = ax - borderSize;
+                                                               const int ny = ay - borderSize;
+                                                               if (nx >= 0 && ny >= 0 && nx < lw && ny < lh)
+                                                                       con |= (unsigned char)(1<<dir);
+                                                       }
+                                               }
+                                       }
+                                       
+                                       layer->cons[idx] = (portal << 4) | con;
+                               }
+                       }
+               }
+               
+               if (layer->minx > layer->maxx)
+                       layer->minx = layer->maxx = 0;
+               if (layer->miny > layer->maxy)
+                       layer->miny = layer->maxy = 0;
+       }
+       
+       ctx->stopTimer(RC_TIMER_BUILD_LAYERS);
+       
+       return true;
+}
index 38d629042130b9378814d848c25482a634a61b97..ef37d569a175f9161e53367b1e01bb0a2e27b14e 100644 (file)
@@ -1,5 +1,5 @@
 //
-// Copyright (c) 2009 Mikko Mononen memon@inside.org
+// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
 //
 // This software is provided 'as-is', without any express or implied
 // warranty.  In no event will the authors be held liable for any damages
@@ -21,9 +21,8 @@
 #include <string.h>
 #include <stdio.h>
 #include "Recast.h"
-#include "RecastLog.h"
-#include "RecastTimer.h"
-
+#include "RecastAlloc.h"
+#include "RecastAssert.h"
 
 struct rcEdge
 {
@@ -32,36 +31,37 @@ struct rcEdge
        unsigned short poly[2];
 };
 
-/*static */bool buildMeshAdjacency(unsigned short* polys, const int npolys,
+/*static*/ bool buildMeshAdjacency(unsigned short* polys, const int npolys,
                                                           const int nverts, const int vertsPerPoly)
 {
        // Based on code by Eric Lengyel from:
        // http://www.terathon.com/code/edges.php
        
        int maxEdgeCount = npolys*vertsPerPoly;
-       unsigned short* firstEdge = new unsigned short[nverts + maxEdgeCount];
+       unsigned short* firstEdge = (unsigned short*)rcAlloc(sizeof(unsigned short)*(nverts + maxEdgeCount), RC_ALLOC_TEMP);
        if (!firstEdge)
                return false;
        unsigned short* nextEdge = firstEdge + nverts;
        int edgeCount = 0;
        
-       rcEdge* edges = new rcEdge[maxEdgeCount];
+       rcEdge* edges = (rcEdge*)rcAlloc(sizeof(rcEdge)*maxEdgeCount, RC_ALLOC_TEMP);
        if (!edges)
+       {
+               rcFree(firstEdge);
                return false;
+       }
        
        for (int i = 0; i < nverts; i++)
-               firstEdge[i] = 0xffff;
-       
-       // Invalida indices are marked as 0xffff, the following code
-       // handles them just fine.
+               firstEdge[i] = RC_MESH_NULL_IDX;
        
        for (int i = 0; i < npolys; ++i)
        {
                unsigned short* t = &polys[i*vertsPerPoly*2];
                for (int j = 0; j < vertsPerPoly; ++j)
                {
+                       if (t[j] == RC_MESH_NULL_IDX) break;
                        unsigned short v0 = t[j];
-                       unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == 0xffff) ? t[0] : t[j+1];
+                       unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
                        if (v0 < v1)
                        {
                                rcEdge& edge = edges[edgeCount];
@@ -73,7 +73,7 @@ struct rcEdge
                                edge.polyEdge[1] = 0;
                                // Insert edge
                                nextEdge[edgeCount] = firstEdge[v0];
-                               firstEdge[v0] = edgeCount;
+                               firstEdge[v0] = (unsigned short)edgeCount;
                                edgeCount++;
                        }
                }
@@ -84,11 +84,12 @@ struct rcEdge
                unsigned short* t = &polys[i*vertsPerPoly*2];
                for (int j = 0; j < vertsPerPoly; ++j)
                {
+                       if (t[j] == RC_MESH_NULL_IDX) break;
                        unsigned short v0 = t[j];
-                       unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == 0xffff) ? t[0] : t[j+1];
+                       unsigned short v1 = (j+1 >= vertsPerPoly || t[j+1] == RC_MESH_NULL_IDX) ? t[0] : t[j+1];
                        if (v0 > v1)
                        {
-                               for (unsigned short e = firstEdge[v1]; e != 0xffff; e = nextEdge[e])
+                               for (unsigned short e = firstEdge[v1]; e != RC_MESH_NULL_IDX; e = nextEdge[e])
                                {
                                        rcEdge& edge = edges[e];
                                        if (edge.vert[1] == v0 && edge.poly[0] == edge.poly[1])
@@ -115,8 +116,8 @@ struct rcEdge
                }
        }
        
-       delete [] firstEdge;
-       delete [] edges;
+       rcFree(firstEdge);
+       rcFree(edges);
        
        return true;
 }
@@ -133,8 +134,8 @@ inline int computeVertexHash(int x, int y, int z)
        return (int)(n & (VERTEX_BUCKET_COUNT-1));
 }
 
-static int addVertex(unsigned short x, unsigned short y, unsigned short z,
-                                        unsigned short* verts, int* firstVert, int* nextVert, int& nv)
+static unsigned short addVertex(unsigned short x, unsigned short y, unsigned short z,
+                                                               unsigned short* verts, int* firstVert, int* nextVert, int& nv)
 {
        int bucket = computeVertexHash(x, 0, z);
        int i = firstVert[bucket];
@@ -143,7 +144,7 @@ static int addVertex(unsigned short x, unsigned short y, unsigned short z,
        {
                const unsigned short* v = &verts[i*3];
                if (v[0] == x && (rcAbs(v[1] - y) <= 2) && v[2] == z)
-                       return i;
+                       return (unsigned short)i;
                i = nextVert[i]; // next
        }
        
@@ -156,7 +157,7 @@ static int addVertex(unsigned short x, unsigned short y, unsigned short z,
        nextVert[i] = firstVert[bucket];
        firstVert[bucket] = i;
        
-       return i;
+       return (unsigned short)i;
 }
 
 inline int prev(int i, int n) { return i-1 >= 0 ? i-1 : n-1; }
@@ -196,7 +197,7 @@ inline bool collinear(const int* a, const int* b, const int* c)
 //     Returns true iff ab properly intersects cd: they share
 //     a point interior to both segments.  The properness of the
 //     intersection is ensured by using strict leftness.
-bool intersectProp(const int* a, const int* b, const int* c, const int* d)
+static bool intersectProp(const int* a, const int* b, const int* c, const int* d)
 {
        // Eliminate improper cases.
        if (collinear(a,b,c) || collinear(a,b,d) ||
@@ -287,7 +288,7 @@ static bool diagonal(int i, int j, int n, const int* verts, int* indices)
        return inCone(i, j, n, verts, indices) && diagonalie(i, j, n, verts, indices);
 }
 
-int triangulate(int n, const int* verts, int* indices, int* tris)
+static int triangulate(int n, const int* verts, int* indices, int* tris)
 {
        int ntris = 0;
        int* dst = tris;
@@ -328,8 +329,6 @@ int triangulate(int n, const int* verts, int* indices, int* tris)
                if (mini == -1)
                {
                        // Should not happen.
-                       if (rcGetLog())
-                               rcGetLog()->log(RC_LOG_WARNING, "triangulate: Failed to triangulate polygon.");
 /*                     printf("mini == -1 ntris=%d n=%d\n", ntris, n);
                        for (int i = 0; i < n; i++)
                        {
@@ -379,7 +378,7 @@ int triangulate(int n, const int* verts, int* indices, int* tris)
 static int countPolyVerts(const unsigned short* p, const int nvp)
 {
        for (int i = 0; i < nvp; ++i)
-               if (p[i] == 0xffff)
+               if (p[i] == RC_MESH_NULL_IDX)
                        return i;
        return nvp;
 }
@@ -454,8 +453,7 @@ static int getPolyMergeValue(unsigned short* pa, unsigned short* pb,
        return dx*dx + dy*dy;
 }
 
-static void mergePolys(unsigned short* pa, unsigned short* pb,
-                                          const unsigned short* verts, int ea, int eb,
+static void mergePolys(unsigned short* pa, unsigned short* pb, int ea, int eb,
                                           unsigned short* tmp, const int nvp)
 {
        const int na = countPolyVerts(pa, nvp);
@@ -474,6 +472,7 @@ static void mergePolys(unsigned short* pa, unsigned short* pb,
        memcpy(pa, tmp, sizeof(unsigned short)*nvp);
 }
 
+
 static void pushFront(int v, int* arr, int& an)
 {
        an++;
@@ -487,59 +486,157 @@ static void pushBack(int v, int* arr, int& an)
        an++;
 }
 
-static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int maxTris)
+static bool canRemoveVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem)
 {
-       unsigned short* tmpPoly;
-       int ntris;
+       const int nvp = mesh.nvp;
+       
+       // Count number of polygons to remove.
+       int numRemovedVerts = 0;
+       int numTouchedVerts = 0;
+       int numRemainingEdges = 0;
+       for (int i = 0; i < mesh.npolys; ++i)
+       {
+               unsigned short* p = &mesh.polys[i*nvp*2];
+               const int nv = countPolyVerts(p, nvp);
+               int numRemoved = 0;
+               int numVerts = 0;
+               for (int j = 0; j < nv; ++j)
+               {
+                       if (p[j] == rem)
+                       {
+                               numTouchedVerts++;
+                               numRemoved++;
+                       }
+                       numVerts++;
+               }
+               if (numRemoved)
+               {
+                       numRemovedVerts += numRemoved;
+                       numRemainingEdges += numVerts-(numRemoved+1);
+               }
+       }
+       
+       // There would be too few edges remaining to create a polygon.
+       // This can happen for example when a tip of a triangle is marked
+       // as deletion, but there are no other polys that share the vertex.
+       // In this case, the vertex should not be removed.
+       if (numRemainingEdges <= 2)
+               return false;
+       
+       // Find edges which share the removed vertex.
+       const int maxEdges = numTouchedVerts*2;
+       int nedges = 0;
+       rcScopedDelete<int> edges = (int*)rcAlloc(sizeof(int)*maxEdges*3, RC_ALLOC_TEMP);
+       if (!edges)
+       {
+               ctx->log(RC_LOG_WARNING, "canRemoveVertex: Out of memory 'edges' (%d).", maxEdges*3);
+               return false;
+       }
+               
+       for (int i = 0; i < mesh.npolys; ++i)
+       {
+               unsigned short* p = &mesh.polys[i*nvp*2];
+               const int nv = countPolyVerts(p, nvp);
+
+               // Collect edges which touches the removed vertex.
+               for (int j = 0, k = nv-1; j < nv; k = j++)
+               {
+                       if (p[j] == rem || p[k] == rem)
+                       {
+                               // Arrange edge so that a=rem.
+                               int a = p[j], b = p[k];
+                               if (b == rem)
+                                       rcSwap(a,b);
+                                       
+                               // Check if the edge exists
+                               bool exists = false;
+                               for (int k = 0; k < nedges; ++k)
+                               {
+                                       int* e = &edges[k*3];
+                                       if (e[1] == b)
+                                       {
+                                               // Exists, increment vertex share count.
+                                               e[2]++;
+                                               exists = true;
+                                       }
+                               }
+                               // Add new edge.
+                               if (!exists)
+                               {
+                                       int* e = &edges[nedges*3];
+                                       e[0] = a;
+                                       e[1] = b;
+                                       e[2] = 1;
+                                       nedges++;
+                               }
+                       }
+               }
+       }
 
-       static const int nvp = mesh.nvp;
+       // There should be no more than 2 open edges.
+       // This catches the case that two non-adjacent polygons
+       // share the removed vertex. In that case, do not remove the vertex.
+       int numOpenEdges = 0;
+       for (int i = 0; i < nedges; ++i)
+       {
+               if (edges[i*3+2] < 2)
+                       numOpenEdges++;
+       }
+       if (numOpenEdges > 2)
+               return false;
+       
+       return true;
+}
 
-       int* edges = 0;
-       int nedges = 0;
-       int* hole = 0;
-       int nhole = 0;
-       int* hreg = 0;
-       int nhreg = 0;
-       int* tris = 0;
-       int* tverts = 0;
-       int* thole = 0;
-       unsigned short* polys = 0;
-       unsigned short* pregs = 0;
-       int npolys = 0;
+static bool removeVertex(rcContext* ctx, rcPolyMesh& mesh, const unsigned short rem, const int maxTris)
+{
+       const int nvp = mesh.nvp;
 
        // Count number of polygons to remove.
-       int nrem = 0;
+       int numRemovedVerts = 0;
        for (int i = 0; i < mesh.npolys; ++i)
        {
                unsigned short* p = &mesh.polys[i*nvp*2];
-               for (int j = 0; j < nvp; ++j)
-                       if (p[j] == rem) { nrem++; break; }
+               const int nv = countPolyVerts(p, nvp);
+               for (int j = 0; j < nv; ++j)
+               {
+                       if (p[j] == rem)
+                               numRemovedVerts++;
+               }
        }
-
-       edges = new int[nrem*nvp*3];
+       
+       int nedges = 0;
+       rcScopedDelete<int> edges = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp*4, RC_ALLOC_TEMP);
        if (!edges)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_WARNING, "removeVertex: Out of memory 'edges' (%d).", nrem*nvp*3);
-               goto failure;
+               ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'edges' (%d).", numRemovedVerts*nvp*4);
+               return false;
        }
 
-       hole = new int[nrem*nvp];
+       int nhole = 0;
+       rcScopedDelete<int> hole = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP);
        if (!hole)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hole' (%d).", nrem*nvp);
-               goto failure;
+               ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hole' (%d).", numRemovedVerts*nvp);
+               return false;
        }
-       hreg = new int[nrem*nvp];
+       
+       int nhreg = 0;
+       rcScopedDelete<int> hreg = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP);
        if (!hreg)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hreg' (%d).", nrem*nvp);
-               goto failure;
+               ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'hreg' (%d).", numRemovedVerts*nvp);
+               return false;
+       }
+
+       int nharea = 0;
+       rcScopedDelete<int> harea = (int*)rcAlloc(sizeof(int)*numRemovedVerts*nvp, RC_ALLOC_TEMP);
+       if (!harea)
+       {
+               ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'harea' (%d).", numRemovedVerts*nvp);
+               return false;
        }
        
-               
        for (int i = 0; i < mesh.npolys; ++i)
        {
                unsigned short* p = &mesh.polys[i*nvp*2];
@@ -554,17 +651,20 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
                        {
                                if (p[j] != rem && p[k] != rem)
                                {
-                                       int* e = &edges[nedges*3];
+                                       int* e = &edges[nedges*4];
                                        e[0] = p[k];
                                        e[1] = p[j];
                                        e[2] = mesh.regs[i];
+                                       e[3] = mesh.areas[i];
                                        nedges++;
                                }
                        }
                        // Remove the polygon.
                        unsigned short* p2 = &mesh.polys[(mesh.npolys-1)*nvp*2];
                        memcpy(p,p2,sizeof(unsigned short)*nvp);
+                       memset(p+nvp,0xff,sizeof(unsigned short)*nvp);
                        mesh.regs[i] = mesh.regs[mesh.npolys-1];
+                       mesh.areas[i] = mesh.areas[mesh.npolys-1];
                        mesh.npolys--;
                        --i;
                }
@@ -589,16 +689,18 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
        }
        for (int i = 0; i < nedges; ++i)
        {
-               if (edges[i*3+0] > rem) edges[i*3+0]--;
-               if (edges[i*3+1] > rem) edges[i*3+1]--;
+               if (edges[i*4+0] > rem) edges[i*4+0]--;
+               if (edges[i*4+1] > rem) edges[i*4+1]--;
        }
 
        if (nedges == 0)
                return true;
 
-       hole[nhole] = edges[0];
-       hreg[nhole] = edges[2];
-       nhole++;
+       // Start with one vertex, keep appending connected
+       // segments to the start and end of the hole.
+       pushBack(edges[0], hole, nhole);
+       pushBack(edges[2], hreg, nhreg);
+       pushBack(edges[3], harea, nharea);
        
        while (nedges)
        {
@@ -606,28 +708,34 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
                
                for (int i = 0; i < nedges; ++i)
                {
-                       const int ea = edges[i*3+0];
-                       const int eb = edges[i*3+1];
-                       const int r = edges[i*3+2];
+                       const int ea = edges[i*4+0];
+                       const int eb = edges[i*4+1];
+                       const int r = edges[i*4+2];
+                       const int a = edges[i*4+3];
                        bool add = false;
                        if (hole[0] == eb)
                        {
+                               // The segment matches the beginning of the hole boundary.
                                pushFront(ea, hole, nhole);
                                pushFront(r, hreg, nhreg);
+                               pushFront(a, harea, nharea);
                                add = true;
                        }
                        else if (hole[nhole-1] == ea)
                        {
+                               // The segment matches the end of the hole boundary.
                                pushBack(eb, hole, nhole);
                                pushBack(r, hreg, nhreg);
+                               pushBack(a, harea, nharea);
                                add = true;
                        }
                        if (add)
                        {
-                               // Remove edge.
-                               edges[i*3+0] = edges[(nedges-1)*3+0];
-                               edges[i*3+1] = edges[(nedges-1)*3+1];
-                               edges[i*3+2] = edges[(nedges-1)*3+2];
+                               // The edge segment was added, remove it.
+                               edges[i*4+0] = edges[(nedges-1)*4+0];
+                               edges[i*4+1] = edges[(nedges-1)*4+1];
+                               edges[i*4+2] = edges[(nedges-1)*4+2];
+                               edges[i*4+3] = edges[(nedges-1)*4+3];
                                --nedges;
                                match = true;
                                --i;
@@ -638,28 +746,25 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
                        break;
        }
 
-       tris = new int[nhole*3];
+       rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*nhole*3, RC_ALLOC_TEMP);
        if (!tris)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tris' (%d).", nhole*3);
-               goto failure;
+               ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tris' (%d).", nhole*3);
+               return false;
        }
 
-       tverts = new int[nhole*4];
+       rcScopedDelete<int> tverts = (int*)rcAlloc(sizeof(int)*nhole*4, RC_ALLOC_TEMP);
        if (!tverts)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tverts' (%d).", nhole*4);
-               goto failure;
+               ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'tverts' (%d).", nhole*4);
+               return false;
        }
 
-       thole = new int[nhole];
+       rcScopedDelete<int> thole = (int*)rcAlloc(sizeof(int)*nhole, RC_ALLOC_TEMP);
        if (!tverts)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_WARNING, "removeVertex: Out of memory 'thole' (%d).", nhole);
-               goto failure;
+               ctx->log(RC_LOG_WARNING, "removeVertex: Out of memory 'thole' (%d).", nhole);
+               return false;
        }
 
        // Generate temp vertex array for triangulation.
@@ -674,27 +779,37 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
        }
 
        // Triangulate the hole.
-       ntris = triangulate(nhole, &tverts[0], &thole[0], tris);
-
+       int ntris = triangulate(nhole, &tverts[0], &thole[0], tris);
+       if (ntris < 0)
+       {
+               ntris = -ntris;
+               ctx->log(RC_LOG_WARNING, "removeVertex: triangulate() returned bad results.");
+       }
+       
        // Merge the hole triangles back to polygons.
-       polys = new unsigned short[(ntris+1)*nvp];
+       rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(ntris+1)*nvp, RC_ALLOC_TEMP);
        if (!polys)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_WARNING, "removeVertex: Out of memory 'polys' (%d).", (ntris+1)*nvp);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'polys' (%d).", (ntris+1)*nvp);
+               return false;
        }
-       pregs = new unsigned short[ntris];
+       rcScopedDelete<unsigned short> pregs = (unsigned short*)rcAlloc(sizeof(unsigned short)*ntris, RC_ALLOC_TEMP);
        if (!pregs)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_WARNING, "removeVertex: Out of memory 'pregs' (%d).", ntris);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pregs' (%d).", ntris);
+               return false;
+       }
+       rcScopedDelete<unsigned char> pareas = (unsigned char*)rcAlloc(sizeof(unsigned char)*ntris, RC_ALLOC_TEMP);
+       if (!pregs)
+       {
+               ctx->log(RC_LOG_ERROR, "removeVertex: Out of memory 'pareas' (%d).", ntris);
+               return false;
        }
        
-       tmpPoly = &polys[ntris*nvp];
+       unsigned short* tmpPoly = &polys[ntris*nvp];
                        
        // Build initial polygons.
+       int npolys = 0;
        memset(polys, 0xff, ntris*nvp*sizeof(unsigned short));
        for (int j = 0; j < ntris; ++j)
        {
@@ -704,7 +819,8 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
                        polys[npolys*nvp+0] = (unsigned short)hole[t[0]];
                        polys[npolys*nvp+1] = (unsigned short)hole[t[1]];
                        polys[npolys*nvp+2] = (unsigned short)hole[t[2]];
-                       pregs[npolys] = hreg[t[0]];
+                       pregs[npolys] = (unsigned short)hreg[t[0]];
+                       pareas[npolys] = (unsigned char)harea[t[0]];
                        npolys++;
                }
        }
@@ -714,11 +830,11 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
        // Merge polygons.
        if (nvp > 3)
        {
-               while (true)
+               for (;;)
                {
                        // Find best polygons to merge.
                        int bestMergeVal = 0;
-                       int bestPa, bestPb, bestEa, bestEb;
+                       int bestPa = 0, bestPb = 0, bestEa = 0, bestEb = 0;
                        
                        for (int j = 0; j < npolys-1; ++j)
                        {
@@ -744,9 +860,10 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
                                // Found best, merge.
                                unsigned short* pa = &polys[bestPa*nvp];
                                unsigned short* pb = &polys[bestPb*nvp];
-                               mergePolys(pa, pb, mesh.verts, bestEa, bestEb, tmpPoly, nvp);
+                               mergePolys(pa, pb, bestEa, bestEb, tmpPoly, nvp);
                                memcpy(pb, &polys[(npolys-1)*nvp], sizeof(unsigned short)*nvp);
                                pregs[bestPb] = pregs[npolys-1];
+                               pareas[bestPb] = pareas[npolys-1];
                                npolys--;
                        }
                        else
@@ -766,50 +883,43 @@ static bool removeVertex(rcPolyMesh& mesh, const unsigned short rem, const int m
                for (int j = 0; j < nvp; ++j)
                        p[j] = polys[i*nvp+j];
                mesh.regs[mesh.npolys] = pregs[i];
+               mesh.areas[mesh.npolys] = pareas[i];
                mesh.npolys++;
+               if (mesh.npolys > maxTris)
+               {
+                       ctx->log(RC_LOG_ERROR, "removeVertex: Too many polygons %d (max:%d).", mesh.npolys, maxTris);
+                       return false;
+               }
        }
        
-       delete [] edges;
-       delete [] hole;
-       delete [] hreg;
-       delete [] tris;
-       delete [] thole;
-       delete [] tverts;
-       delete [] polys;
-       delete [] pregs;
-       
        return true;
-
-failure:
-       delete [] edges;
-       delete [] hole;
-       delete [] hreg;
-       delete [] tris;
-       delete [] thole;
-       delete [] tverts;
-       delete [] polys;
-       delete [] pregs;
-       
-       return false;
 }
 
-
-bool rcBuildPolyMesh(rcContourSet& cset, int nvp, rcPolyMesh& mesh)
+/// @par
+///
+/// @note If the mesh data is to be used to construct a Detour navigation mesh, then the upper 
+/// limit must be retricted to <= #DT_VERTS_PER_POLYGON.
+///
+/// @see rcAllocPolyMesh, rcContourSet, rcPolyMesh, rcConfig
+bool rcBuildPolyMesh(rcContext* ctx, rcContourSet& cset, const int nvp, rcPolyMesh& mesh)
 {
-       unsigned short* tmpPoly;
-       rcTimeVal startTime = rcGetPerformanceTimer();
-       rcTimeVal endTime;
+       rcAssert(ctx);
+       
+       ctx->startTimer(RC_TIMER_BUILD_POLYMESH);
 
-       vcopy(mesh.bmin, cset.bmin);
-       vcopy(mesh.bmax, cset.bmax);
+       rcVcopy(mesh.bmin, cset.bmin);
+       rcVcopy(mesh.bmax, cset.bmax);
        mesh.cs = cset.cs;
        mesh.ch = cset.ch;
+       mesh.borderSize = cset.borderSize;
        
        int maxVertices = 0;
        int maxTris = 0;
        int maxVertsPerCont = 0;
        for (int i = 0; i < cset.nconts; ++i)
        {
+               // Skip null contours.
+               if (cset.conts[i].nverts < 3) continue;
                maxVertices += cset.conts[i].nverts;
                maxTris += cset.conts[i].nverts - 2;
                maxVertsPerCont = rcMax(maxVertsPerCont, cset.conts[i].nverts);
@@ -817,103 +927,95 @@ bool rcBuildPolyMesh(rcContourSet& cset, int nvp, rcPolyMesh& mesh)
        
        if (maxVertices >= 0xfffe)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many vertices %d.", maxVertices);
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Too many vertices %d.", maxVertices);
                return false;
        }
-       
-       unsigned char* vflags = 0;
-       int* nextVert = 0;
-       int* firstVert = 0;
-       int* indices = 0;
-       int* tris = 0;
-       unsigned short* polys = 0;
-       
-       vflags = new unsigned char[maxVertices];
+               
+       rcScopedDelete<unsigned char> vflags = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxVertices, RC_ALLOC_TEMP);
        if (!vflags)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
+               return false;
        }
        memset(vflags, 0, maxVertices);
        
-       mesh.verts = new unsigned short[maxVertices*3];
+       mesh.verts = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxVertices*3, RC_ALLOC_PERM);
        if (!mesh.verts)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.verts' (%d).", maxVertices);
+               return false;
        }
-       mesh.polys = new unsigned short[maxTris*nvp*2];
+       mesh.polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris*nvp*2, RC_ALLOC_PERM);
        if (!mesh.polys)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.polys' (%d).", maxTris*nvp*2);
+               return false;
        }
-       mesh.regs = new unsigned short[maxTris];
+       mesh.regs = (unsigned short*)rcAlloc(sizeof(unsigned short)*maxTris, RC_ALLOC_PERM);
        if (!mesh.regs)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.regs' (%d).", maxTris);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.regs' (%d).", maxTris);
+               return false;
+       }
+       mesh.areas = (unsigned char*)rcAlloc(sizeof(unsigned char)*maxTris, RC_ALLOC_PERM);
+       if (!mesh.areas)
+       {
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'mesh.areas' (%d).", maxTris);
+               return false;
        }
+       
        mesh.nverts = 0;
        mesh.npolys = 0;
        mesh.nvp = nvp;
+       mesh.maxpolys = maxTris;
        
        memset(mesh.verts, 0, sizeof(unsigned short)*maxVertices*3);
        memset(mesh.polys, 0xff, sizeof(unsigned short)*maxTris*nvp*2);
        memset(mesh.regs, 0, sizeof(unsigned short)*maxTris);
+       memset(mesh.areas, 0, sizeof(unsigned char)*maxTris);
        
-       nextVert = new int[maxVertices];
+       rcScopedDelete<int> nextVert = (int*)rcAlloc(sizeof(int)*maxVertices, RC_ALLOC_TEMP);
        if (!nextVert)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'nextVert' (%d).", maxVertices);
+               return false;
        }
        memset(nextVert, 0, sizeof(int)*maxVertices);
        
-       firstVert = new int[VERTEX_BUCKET_COUNT];
+       rcScopedDelete<int> firstVert = (int*)rcAlloc(sizeof(int)*VERTEX_BUCKET_COUNT, RC_ALLOC_TEMP);
        if (!firstVert)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'firstVert' (%d).", VERTEX_BUCKET_COUNT);
+               return false;
        }
        for (int i = 0; i < VERTEX_BUCKET_COUNT; ++i)
                firstVert[i] = -1;
        
-       indices = new int[maxVertsPerCont];
+       rcScopedDelete<int> indices = (int*)rcAlloc(sizeof(int)*maxVertsPerCont, RC_ALLOC_TEMP);
        if (!indices)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'indices' (%d).", maxVertsPerCont);
+               return false;
        }
-       tris = new int[maxVertsPerCont*3];
+       rcScopedDelete<int> tris = (int*)rcAlloc(sizeof(int)*maxVertsPerCont*3, RC_ALLOC_TEMP);
        if (!tris)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'tris' (%d).", maxVertsPerCont*3);
+               return false;
        }
-       polys = new unsigned short[(maxVertsPerCont+1)*nvp];
+       rcScopedDelete<unsigned short> polys = (unsigned short*)rcAlloc(sizeof(unsigned short)*(maxVertsPerCont+1)*nvp, RC_ALLOC_TEMP);
        if (!polys)
        {
-               if (rcGetLog())
-                       rcGetLog()->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp);
-               goto failure;
+               ctx->log(RC_LOG_ERROR, "rcBuildPolyMesh: Out of memory 'polys' (%d).", maxVertsPerCont*nvp);
+               return false;
        }
-       tmpPoly = &polys[maxVertsPerCont*nvp];
+       unsigned short* tmpPoly = &polys[maxVertsPerCont*nvp];
 
        for (int i = 0; i < cset.nconts; ++i)
        {
                rcContour& cont = cset.conts[i];
                
-               // Skip empty contours.
+               // Skip null contours.
                if (cont.nverts < 3)
                        continue;
                
@@ -925,20 +1027,20 @@ bool rcBuildPolyMesh(rcContourSet& cset, int nvp, rcPolyMesh& mesh)
                if (ntris <= 0)
                {
                        // Bad triangulation, should not happen.
-/*                     for (int k = 0; k < cont.nverts; ++k)
+/*                     printf("\tconst float bmin[3] = {%ff,%ff,%ff};\n", cset.bmin[0], cset.bmin[1], cset.bmin[2]);
+                       printf("\tconst float cs = %ff;\n", cset.cs);
+                       printf("\tconst float ch = %ff;\n", cset.ch);