svn merge -r40000:40179 https://svn.blender.org/svnroot/bf-blender/trunk/blender
authorCampbell Barton <ideasman42@gmail.com>
Tue, 13 Sep 2011 10:05:30 +0000 (10:05 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Tue, 13 Sep 2011 10:05:30 +0000 (10:05 +0000)
297 files changed:
CMakeLists.txt
build_files/cmake/Modules/FindOpenCOLLADA.cmake
build_files/cmake/Modules/FindPCRE.cmake [new file with mode: 0644]
build_files/cmake/Modules/FindXML2.cmake [new file with mode: 0644]
build_files/cmake/macros.cmake
build_files/scons/config/darwin-config.py
build_files/scons/config/linuxcross-config.py
doc/python_api/examples/bge.texture.1.py
doc/python_api/examples/bpy.types.Operator.py
doc/python_api/rst/gpu.rst [new file with mode: 0644]
doc/python_api/rst/info_best_practice.rst [new file with mode: 0644]
doc/python_api/rst/info_gotcha.rst
doc/python_api/rst/info_quickstart.rst
doc/python_api/rst/info_tips_and_tricks.rst
doc/python_api/sphinx_doc_gen.py
extern/CMakeLists.txt
extern/SConscript
extern/recastnavigation/CMakeLists.txt [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourCommon.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourNode.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourStatNavMesh.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourTileNavMesh.h [new file with mode: 0644]
extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourCommon.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourNode.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp [new file with mode: 0644]
extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp [new file with mode: 0644]
extern/recastnavigation/License.txt [new file with mode: 0644]
extern/recastnavigation/Readme.txt [new file with mode: 0644]
extern/recastnavigation/Recast/Include/Recast.h [new file with mode: 0644]
extern/recastnavigation/Recast/Include/RecastLog.h [new file with mode: 0644]
extern/recastnavigation/Recast/Include/RecastTimer.h [new file with mode: 0644]
extern/recastnavigation/Recast/Source/Recast.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastContour.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastFilter.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastLog.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastMesh.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastMeshDetail.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastRasterization.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastRegion.cpp [new file with mode: 0644]
extern/recastnavigation/Recast/Source/RecastTimer.cpp [new file with mode: 0644]
extern/recastnavigation/SConscript [new file with mode: 0644]
intern/audaspace/intern/AUD_JOSResampleReader.cpp
intern/audaspace/intern/AUD_SequencerHandle.cpp
intern/audaspace/intern/AUD_SequencerHandle.h
intern/audaspace/intern/AUD_SequencerReader.cpp
intern/elbeem/CMakeLists.txt
release/scripts/modules/bpy_types.py
release/scripts/startup/bl_operators/animsys_update.py
release/scripts/startup/bl_operators/nla.py
release/scripts/startup/bl_ui/properties_data_armature.py
release/scripts/startup/bl_ui/properties_data_modifier.py
release/scripts/startup/bl_ui/properties_data_speaker.py
release/scripts/startup/bl_ui/properties_game.py
release/scripts/startup/bl_ui/properties_physics_fluid.py
release/scripts/startup/bl_ui/space_userpref.py
release/scripts/startup/bl_ui/space_view3d_toolbar.py
source/blender/blenfont/intern/blf_font.c
source/blender/blenfont/intern/blf_glyph.c
source/blender/blenfont/intern/blf_internal.h
source/blender/blenfont/intern/blf_internal_types.h
source/blender/blenfont/intern/blf_util.c
source/blender/blenkernel/BKE_colortools.h
source/blender/blenkernel/BKE_material.h
source/blender/blenkernel/BKE_navmesh_conversion.h [new file with mode: 0644]
source/blender/blenkernel/BKE_sequencer.h
source/blender/blenkernel/CMakeLists.txt
source/blender/blenkernel/SConscript
source/blender/blenkernel/intern/DerivedMesh.c
source/blender/blenkernel/intern/boids.c
source/blender/blenkernel/intern/brush.c
source/blender/blenkernel/intern/cdderivedmesh.c
source/blender/blenkernel/intern/collision.c
source/blender/blenkernel/intern/colortools.c
source/blender/blenkernel/intern/curve.c
source/blender/blenkernel/intern/customdata.c
source/blender/blenkernel/intern/effect.c
source/blender/blenkernel/intern/material.c
source/blender/blenkernel/intern/navmesh_conversion.cpp [new file with mode: 0644]
source/blender/blenkernel/intern/node.c
source/blender/blenkernel/intern/object.c
source/blender/blenkernel/intern/particle.c
source/blender/blenkernel/intern/sca.c
source/blender/blenkernel/intern/scene.c
source/blender/blenkernel/intern/sequencer.c
source/blender/blenkernel/intern/shrinkwrap.c
source/blender/blenkernel/intern/sketch.c
source/blender/blenlib/BLI_math_inline.h
source/blender/blenlib/BLI_math_matrix.h
source/blender/blenlib/BLI_math_vector.h
source/blender/blenlib/BLI_utildefines.h
source/blender/blenlib/intern/BLI_kdopbvh.c
source/blender/blenlib/intern/graph.c
source/blender/blenlib/intern/math_matrix.c
source/blender/blenlib/intern/math_vector_inline.c
source/blender/blenloader/intern/readfile.c
source/blender/blenloader/intern/writefile.c
source/blender/collada/AnimationExporter.cpp
source/blender/collada/ArmatureExporter.cpp
source/blender/collada/ArmatureExporter.h
source/blender/collada/ArmatureImporter.cpp
source/blender/collada/CMakeLists.txt
source/blender/collada/CameraExporter.cpp
source/blender/collada/CameraExporter.h
source/blender/collada/DocumentExporter.cpp
source/blender/collada/DocumentExporter.h
source/blender/collada/EffectExporter.cpp
source/blender/collada/EffectExporter.h
source/blender/collada/ErrorHandler.cpp
source/blender/collada/ExportSettings.cpp [new file with mode: 0644]
source/blender/collada/ExportSettings.h [new file with mode: 0644]
source/blender/collada/GeometryExporter.cpp
source/blender/collada/GeometryExporter.h
source/blender/collada/ImageExporter.cpp
source/blender/collada/ImageExporter.h
source/blender/collada/LightExporter.cpp
source/blender/collada/LightExporter.h
source/blender/collada/MaterialExporter.cpp
source/blender/collada/MaterialExporter.h
source/blender/collada/SceneExporter.cpp
source/blender/collada/SceneExporter.h
source/blender/collada/collada.cpp
source/blender/editors/animation/anim_channels_defines.c
source/blender/editors/animation/keyframing.c
source/blender/editors/armature/editarmature_sketch.c
source/blender/editors/armature/meshlaplacian.c
source/blender/editors/include/ED_object.h
source/blender/editors/include/UI_interface.h
source/blender/editors/include/UI_resources.h
source/blender/editors/interface/interface_draw.c
source/blender/editors/interface/interface_layout.c
source/blender/editors/interface/interface_panel.c
source/blender/editors/interface/interface_templates.c
source/blender/editors/interface/interface_widgets.c
source/blender/editors/interface/resources.c
source/blender/editors/mesh/editmesh.c
source/blender/editors/mesh/editmesh_add.c
source/blender/editors/mesh/editmesh_lib.c
source/blender/editors/mesh/editmesh_mods.c
source/blender/editors/mesh/editmesh_tools.c
source/blender/editors/object/CMakeLists.txt
source/blender/editors/object/SConscript
source/blender/editors/object/object_intern.h
source/blender/editors/object/object_navmesh.cpp [new file with mode: 0644]
source/blender/editors/object/object_ops.c
source/blender/editors/object/object_select.c
source/blender/editors/render/render_shading.c
source/blender/editors/screen/area.c
source/blender/editors/screen/screen_ops.c
source/blender/editors/sculpt_paint/paint_stroke.c
source/blender/editors/sculpt_paint/sculpt.c
source/blender/editors/sculpt_paint/sculpt_undo.c
source/blender/editors/sound/sound_ops.c
source/blender/editors/space_file/file_draw.c
source/blender/editors/space_file/filelist.c
source/blender/editors/space_logic/logic_window.c
source/blender/editors/space_nla/nla_draw.c
source/blender/editors/space_nla/nla_select.c
source/blender/editors/space_node/drawnode.c
source/blender/editors/space_node/node_draw.c
source/blender/editors/space_node/node_edit.c
source/blender/editors/space_outliner/outliner_draw.c
source/blender/editors/space_outliner/outliner_edit.c
source/blender/editors/space_outliner/outliner_intern.h
source/blender/editors/space_outliner/outliner_select.c
source/blender/editors/space_outliner/outliner_tools.c
source/blender/editors/space_outliner/outliner_tree.c
source/blender/editors/space_sequencer/sequencer_draw.c
source/blender/editors/space_text/text_draw.c
source/blender/editors/space_view3d/drawarmature.c
source/blender/editors/space_view3d/drawobject.c
source/blender/editors/space_view3d/drawvolume.c
source/blender/editors/space_view3d/view3d_draw.c
source/blender/editors/space_view3d/view3d_edit.c
source/blender/editors/transform/transform.c
source/blender/editors/transform/transform_constraints.c
source/blender/editors/transform/transform_conversions.c
source/blender/editors/transform/transform_generics.c
source/blender/editors/transform/transform_manipulator.c
source/blender/editors/transform/transform_orientations.c
source/blender/editors/transform/transform_snap.c
source/blender/editors/util/SConscript
source/blender/gpu/GPU_extensions.h
source/blender/gpu/GPU_material.h
source/blender/gpu/intern/gpu_codegen.c
source/blender/gpu/intern/gpu_codegen.h
source/blender/gpu/intern/gpu_extensions.c
source/blender/gpu/intern/gpu_material.c
source/blender/gpu/intern/gpu_shader_material.glsl
source/blender/gpu/intern/gpu_shader_material.glsl.c
source/blender/makesdna/DNA_actuator_types.h
source/blender/makesdna/DNA_customdata_types.h
source/blender/makesdna/DNA_meshdata_types.h
source/blender/makesdna/DNA_modifier_types.h
source/blender/makesdna/DNA_object_types.h
source/blender/makesdna/DNA_outliner_types.h
source/blender/makesdna/DNA_scene_types.h
source/blender/makesdna/DNA_sequence_types.h
source/blender/makesdna/DNA_space_types.h
source/blender/makesdna/DNA_userdef_types.h
source/blender/makesrna/RNA_access.h
source/blender/makesrna/intern/rna_access.c
source/blender/makesrna/intern/rna_actuator.c
source/blender/makesrna/intern/rna_modifier.c
source/blender/makesrna/intern/rna_nodetree.c
source/blender/makesrna/intern/rna_object.c
source/blender/makesrna/intern/rna_scene.c
source/blender/makesrna/intern/rna_space.c
source/blender/makesrna/intern/rna_ui_api.c
source/blender/makesrna/intern/rna_userdef.c
source/blender/modifiers/CMakeLists.txt
source/blender/modifiers/MOD_modifiertypes.h
source/blender/modifiers/SConscript
source/blender/modifiers/intern/MOD_navmesh.cpp [new file with mode: 0644]
source/blender/modifiers/intern/MOD_util.c
source/blender/modifiers/intern/MOD_weightvg_util.c
source/blender/modifiers/intern/MOD_weightvg_util.h
source/blender/modifiers/intern/MOD_weightvgedit.c
source/blender/modifiers/intern/MOD_weightvgmix.c
source/blender/modifiers/intern/MOD_weightvgproximity.c
source/blender/nodes/composite/node_composite_tree.c
source/blender/nodes/intern/node_common.c
source/blender/nodes/shader/node_shader_tree.c
source/blender/nodes/shader/nodes/node_shader_geom.c
source/blender/nodes/shader/nodes/node_shader_material.c
source/blender/python/SConscript
source/blender/python/generic/py_capi_utils.c
source/blender/python/intern/CMakeLists.txt
source/blender/python/intern/bpy_interface.c
source/blender/python/intern/bpy_rna.c
source/blender/python/intern/gpu.c [new file with mode: 0644]
source/blender/python/intern/gpu.h [new file with mode: 0644]
source/blender/render/extern/include/RE_render_ext.h
source/blender/render/intern/include/pixelshading.h
source/blender/render/intern/include/render_types.h
source/blender/render/intern/include/rendercore.h
source/blender/render/intern/include/renderdatabase.h
source/blender/render/intern/include/shadbuf.h
source/blender/render/intern/include/shading.h
source/blender/render/intern/include/texture.h
source/blender/render/intern/include/volumetric.h
source/blender/render/intern/include/zbuf.h
source/blender/render/intern/source/convertblender.c
source/blender/render/intern/source/imagetexture.c
source/blender/render/intern/source/occlusion.c
source/blender/render/intern/source/pixelshading.c
source/blender/render/intern/source/render_texture.c
source/blender/render/intern/source/rendercore.c
source/blender/render/intern/source/renderdatabase.c
source/blender/render/intern/source/shadbuf.c
source/blender/render/intern/source/shadeinput.c
source/blender/render/intern/source/shadeoutput.c
source/blender/render/intern/source/sss.c
source/blender/render/intern/source/volume_precache.c
source/blender/render/intern/source/volumetric.c
source/blender/render/intern/source/zbuf.c
source/blender/windowmanager/intern/wm_dragdrop.c
source/blender/windowmanager/intern/wm_event_system.c
source/blender/windowmanager/intern/wm_keymap.c
source/blenderplayer/CMakeLists.txt
source/creator/CMakeLists.txt
source/creator/creator.c
source/gameengine/BlenderRoutines/BL_KetsjiEmbedStart.cpp
source/gameengine/Converter/BL_BlenderDataConversion.cpp
source/gameengine/Converter/BL_SkinDeformer.cpp
source/gameengine/Converter/CMakeLists.txt
source/gameengine/Converter/KX_ConvertActuators.cpp
source/gameengine/Converter/SConscript
source/gameengine/Expressions/IfExpr.h
source/gameengine/GameLogic/SCA_IActuator.h
source/gameengine/GamePlayer/ghost/GPG_Application.cpp
source/gameengine/GamePlayer/ghost/GPG_Application.h
source/gameengine/GamePlayer/ghost/GPG_ghost.cpp
source/gameengine/Ketsji/CMakeLists.txt
source/gameengine/Ketsji/KX_GameObject.cpp
source/gameengine/Ketsji/KX_GameObject.h
source/gameengine/Ketsji/KX_KetsjiEngine.cpp
source/gameengine/Ketsji/KX_KetsjiEngine.h
source/gameengine/Ketsji/KX_NavMeshObject.cpp [new file with mode: 0644]
source/gameengine/Ketsji/KX_NavMeshObject.h [new file with mode: 0644]
source/gameengine/Ketsji/KX_ObstacleSimulation.cpp [new file with mode: 0644]
source/gameengine/Ketsji/KX_ObstacleSimulation.h [new file with mode: 0644]
source/gameengine/Ketsji/KX_PythonInit.cpp
source/gameengine/Ketsji/KX_PythonInit.h
source/gameengine/Ketsji/KX_PythonInitTypes.cpp
source/gameengine/Ketsji/KX_Scene.cpp
source/gameengine/Ketsji/KX_Scene.h
source/gameengine/Ketsji/KX_SteeringActuator.cpp [new file with mode: 0644]
source/gameengine/Ketsji/KX_SteeringActuator.h [new file with mode: 0644]
source/gameengine/Ketsji/SConscript
source/gameengine/Rasterizer/RAS_IRasterizer.h
source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.cpp
source/gameengine/Rasterizer/RAS_OpenGLRasterizer/RAS_OpenGLRasterizer.h
source/gameengine/VideoTexture/blendVideoTex.cpp

index 8b5693f..6eb8b8c 100644 (file)
@@ -452,15 +452,8 @@ if(UNIX AND NOT APPLE)
        if(WITH_OPENCOLLADA)
                find_package(OpenCOLLADA)
                if(OPENCOLLADA_FOUND)
-                       set(PCRE /usr CACHE PATH "PCRE Directory")
-                       mark_as_advanced(PCRE)
-                       set(PCRE_LIBPATH ${PCRE}/lib)
-                       set(PCRE_LIB pcre)
-
-                       set(EXPAT /usr CACHE PATH "Expat Directory")
-                       mark_as_advanced(EXPAT)
-                       set(EXPAT_LIBPATH ${EXPAT}/lib)
-                       set(EXPAT_LIB expat)
+                       find_package(XML2)
+                       find_package(PCRE)
                else()
                        set(WITH_OPENCOLLADA OFF)
                endif()
@@ -709,7 +702,7 @@ elseif(WIN32)
                                ${LIBDIR}/opencollada/lib/ftoa.lib
                                ${LIBDIR}/opencollada/lib/UTF.lib
                        )
-                       set(PCRE_LIB
+                       set(PCRE_LIBRARIES
                                ${LIBDIR}/opencollada/lib/pcre.lib
                        )
                endif()
@@ -851,7 +844,7 @@ elseif(WIN32)
                        )
                        set(OPENCOLLADA_LIBPATH ${OPENCOLLADA}/lib ${OPENCOLLADA}/lib)
                        set(OPENCOLLADA_LIBRARIES OpenCOLLADAStreamWriter OpenCOLLADASaxFrameworkLoader OpenCOLLADAFramework OpenCOLLADABaseUtils GeneratedSaxParser UTF MathMLSolver expat pcre buffer ftoa)
-                       set(PCRE_LIB pcre)
+                       set(PCRE_LIBRARIES pcre)
                endif()
                
                if(WITH_CODEC_FFMPEG)
@@ -1073,7 +1066,7 @@ elseif(APPLE)
                #pcre is bundled with openCollada
                #set(PCRE ${LIBDIR}/pcre)
                #set(PCRE_LIBPATH ${PCRE}/lib)
-               set(PCRE_LIB pcre)
+               set(PCRE_LIBRARIES pcre)
                #libxml2 is used
                #set(EXPAT ${LIBDIR}/expat)
                #set(EXPAT_LIBPATH ${EXPAT}/lib)
index c763728..a9a1d54 100644 (file)
@@ -49,12 +49,14 @@ SET(_opencollada_FIND_COMPONENTS
   OpenCOLLADAFramework
   OpenCOLLADABaseUtils
   GeneratedSaxParser
-  UTF
   MathMLSolver
-  pcre
+)
+
+# Fedora openCOLLADA package links these statically
+SET(_opencollada_FIND_STATIC_COMPONENTS
+  UTF
   ftoa
   buffer
-  xml2
 )
 
 SET(_opencollada_SEARCH_DIRS
@@ -104,6 +106,25 @@ FOREACH(COMPONENT ${_opencollada_FIND_COMPONENTS})
   LIST(APPEND _opencollada_LIBRARIES "${OPENCOLLADA_${UPPERCOMPONENT}_LIBRARY}")
 ENDFOREACH()
 
+FOREACH(COMPONENT ${_opencollada_FIND_STATIC_COMPONENTS})
+  STRING(TOUPPER ${COMPONENT} UPPERCOMPONENT)
+
+  FIND_LIBRARY(OPENCOLLADA_${UPPERCOMPONENT}_LIBRARY
+    NAMES
+      ${COMPONENT}
+    HINTS
+      ${_opencollada_SEARCH_DIRS}
+    PATH_SUFFIXES
+      lib64 lib
+      # Ubuntu ppa needs this.
+      lib64/opencollada lib/opencollada
+    )
+  IF(OPENCOLLADA_${UPPERCOMPONENT}_LIBRARY)
+    MARK_AS_ADVANCED(OPENCOLLADA_${UPPERCOMPONENT}_LIBRARY)
+    LIST(APPEND _opencollada_LIBRARIES "${OPENCOLLADA_${UPPERCOMPONENT}_LIBRARY}")
+  ENDIF()
+ENDFOREACH()
+
 
 # handle the QUIETLY and REQUIRED arguments and set OPENCOLLADA_FOUND to TRUE if 
 # all listed variables are TRUE
diff --git a/build_files/cmake/Modules/FindPCRE.cmake b/build_files/cmake/Modules/FindPCRE.cmake
new file mode 100644 (file)
index 0000000..a093752
--- /dev/null
@@ -0,0 +1,43 @@
+# - Try to find the PCRE regular expression library
+# Once done this will define
+#
+#  PCRE_FOUND - system has the PCRE library
+#  PCRE_INCLUDE_DIR - the PCRE include directory
+#  PCRE_LIBRARIES - The libraries needed to use PCRE
+
+# Copyright (c) 2006, Alexander Neundorf, <neundorf@kde.org>
+#
+# Redistribution and use is allowed according to the terms of the BSD license.
+
+if (PCRE_INCLUDE_DIR AND PCRE_PCREPOSIX_LIBRARY AND PCRE_PCRE_LIBRARY)
+  # Already in cache, be silent
+  set(PCRE_FIND_QUIETLY TRUE)
+endif (PCRE_INCLUDE_DIR AND PCRE_PCREPOSIX_LIBRARY AND PCRE_PCRE_LIBRARY)
+       
+if (NOT WIN32)
+  # use pkg-config to get the directories and then use these values
+  # in the FIND_PATH() and FIND_LIBRARY() calls
+  find_package(PkgConfig)
+  pkg_check_modules(PC_PCRE QUIET libpcre)
+  set(PCRE_DEFINITIONS ${PC_PCRE_CFLAGS_OTHER})
+endif (NOT WIN32)
+
+find_path(PCRE_INCLUDE_DIR pcre.h
+          HINTS ${PC_PCRE_INCLUDEDIR} ${PC_PCRE_INCLUDE_DIRS}
+          PATH_SUFFIXES pcre)
+
+find_library(PCRE_PCRE_LIBRARY NAMES pcre HINTS ${PC_PCRE_LIBDIR} ${PC_PCRE_LIBRARY_DIRS})
+
+find_library(PCRE_PCREPOSIX_LIBRARY NAMES pcreposix HINTS ${PC_PCRE_LIBDIR} ${PC_PCRE_LIBRARY_DIRS})
+
+include(FindPackageHandleStandardArgs)
+
+IF(NOT WIN32)
+        find_package_handle_standard_args(PCRE DEFAULT_MSG PCRE_INCLUDE_DIR PCRE_PCRE_LIBRARY PCRE_PCREPOSIX_LIBRARY )
+        mark_as_advanced(PCRE_INCLUDE_DIR PCRE_LIBRARIES PCRE_PCREPOSIX_LIBRARY PCRE_PCRE_LIBRARY)
+        set(PCRE_LIBRARIES ${PCRE_PCRE_LIBRARY} ${PCRE_PCREPOSIX_LIBRARY})
+ELSE()
+        find_package_handle_standard_args(PCRE DEFAULT_MSG PCRE_INCLUDE_DIR PCRE_PCRE_LIBRARY  )
+        set(PCRE_LIBRARIES ${PCRE_PCRE_LIBRARY} )
+        mark_as_advanced(PCRE_INCLUDE_DIR PCRE_LIBRARIES PCRE_PCRE_LIBRARY)
+ENDIF()
diff --git a/build_files/cmake/Modules/FindXML2.cmake b/build_files/cmake/Modules/FindXML2.cmake
new file mode 100644 (file)
index 0000000..e9f9fb3
--- /dev/null
@@ -0,0 +1,88 @@
+# - Try to find XML2
+# Once done this will define
+#
+#  XML2_FOUND - system has XML2
+#  XML2_INCLUDE_DIRS - the XML2 include directory
+#  XML2_LIBRARIES - Link these to use XML2
+#  XML2_DEFINITIONS - Compiler switches required for using XML2
+#
+#  Copyright (c) 2008 Andreas Schneider <mail@cynapses.org>
+#
+#  Redistribution and use is allowed according to the terms of the New
+#  BSD license.
+#
+
+
+if (XML2_LIBRARIES AND XML2_INCLUDE_DIRS)
+  # in cache already
+  set(XML2_FOUND TRUE)
+else (XML2_LIBRARIES AND XML2_INCLUDE_DIRS)
+  # use pkg-config to get the directories and then use these values
+  # in the FIND_PATH() and FIND_LIBRARY() calls
+  if (${CMAKE_MAJOR_VERSION} EQUAL 2 AND ${CMAKE_MINOR_VERSION} EQUAL 4)
+    include(UsePkgConfig)
+    pkgconfig(libxml-2.0 _XML2_INCLUDEDIR _XML2_LIBDIR _XML2_LDFLAGS _XML2_CFLAGS)
+  else (${CMAKE_MAJOR_VERSION} EQUAL 2 AND ${CMAKE_MINOR_VERSION} EQUAL 4)
+    find_package(PkgConfig)
+    if (PKG_CONFIG_FOUND)
+      pkg_check_modules(_XML2 libxml-2.0)
+    endif (PKG_CONFIG_FOUND)
+  endif (${CMAKE_MAJOR_VERSION} EQUAL 2 AND ${CMAKE_MINOR_VERSION} EQUAL 4)
+  find_path(XML2_INCLUDE_DIR
+    NAMES
+      libxml/xpath.h
+    PATHS
+      ${_XML2_INCLUDEDIR}
+      /usr/include
+      /usr/local/include
+      /opt/local/include
+      /sw/include
+    PATH_SUFFIXES
+      libxml2
+  )
+
+  find_library(XML2_LIBRARY
+    NAMES
+      xml2
+    PATHS
+      ${_XML2_LIBDIR}
+      /usr/lib
+      /usr/local/lib
+      /opt/local/lib
+      /sw/lib
+  )
+
+  if (XML2_LIBRARY)
+    set(XML2_FOUND TRUE)
+  endif (XML2_LIBRARY)
+
+  set(XML2_INCLUDE_DIRS
+    ${XML2_INCLUDE_DIR}
+  )
+
+  if (XML2_FOUND)
+    set(XML2_LIBRARIES
+      ${XML2_LIBRARIES}
+      ${XML2_LIBRARY}
+    )
+  endif (XML2_FOUND)
+
+  if (XML2_INCLUDE_DIRS AND XML2_LIBRARIES)
+     set(XML2_FOUND TRUE)
+  endif (XML2_INCLUDE_DIRS AND XML2_LIBRARIES)
+
+  if (XML2_FOUND)
+    if (NOT XML2_FIND_QUIETLY)
+      message(STATUS "Found XML2: ${XML2_LIBRARIES}")
+    endif (NOT XML2_FIND_QUIETLY)
+  else (XML2_FOUND)
+    if (XML2_FIND_REQUIRED)
+      message(FATAL_ERROR "Could not find XML2")
+    endif (XML2_FIND_REQUIRED)
+  endif (XML2_FOUND)
+
+  # show the XML2_INCLUDE_DIRS and XML2_LIBRARIES variables only in the advanced view
+  mark_as_advanced(XML2_INCLUDE_DIRS XML2_LIBRARIES)
+
+endif (XML2_LIBRARIES AND XML2_INCLUDE_DIRS)
+
index d09215d..aec7a9f 100644 (file)
@@ -295,10 +295,10 @@ macro(setup_liblinks
                        target_link_libraries_optimized(${target} "${OPENCOLLADA_LIBRARIES}")
                        unset(OPENCOLLADA_LIBRARIES_DEBUG)
 
-                       file_list_suffix(PCRE_LIB_DEBUG "${PCRE_LIB}" "_d")
-                       target_link_libraries_debug(${target} "${PCRE_LIB_DEBUG}")
-                       target_link_libraries_optimized(${target} "${PCRE_LIB}")
-                       unset(PCRE_LIB_DEBUG)
+                       file_list_suffix(PCRE_LIBRARIES_DEBUG "${PCRE_LIBRARIES}" "_d")
+                       target_link_libraries_debug(${target} "${PCRE_LIBRARIES_DEBUG}")
+                       target_link_libraries_optimized(${target} "${PCRE_LIBRARIES}")
+                       unset(PCRE_LIBRARIES_DEBUG)
 
                        if(EXPAT_LIB)
                                file_list_suffix(EXPAT_LIB_DEBUG "${EXPAT_LIB}" "_d")
@@ -309,7 +309,8 @@ macro(setup_liblinks
                else()
                        target_link_libraries(${target}
                                        ${OPENCOLLADA_LIBRARIES}
-                                       ${PCRE_LIB}
+                                       ${PCRE_LIBRARIES}
+                                       ${XML2_LIBRARIES}
                                        ${EXPAT_LIB})
                endif()
        endif()
index 102ec73..29d2b39 100644 (file)
@@ -14,7 +14,7 @@ USE_SDK=True
 ###################     Cocoa & architecture settings      ##################
 #############################################################################
 WITH_GHOST_COCOA=True
-MACOSX_ARCHITECTURE = 'x86_64' # valid archs: ppc, i386, ppc64, x86_64
+MACOSX_ARCHITECTURE = 'i386' # valid archs: ppc, i386, ppc64, x86_64
 
 
 cmd = 'uname -p'
index 1bdf735..8057d47 100644 (file)
@@ -127,6 +127,7 @@ WITH_BF_BINRELOC = False
 WITH_BF_FFMPEG = True  # -DWITH_FFMPEG
 BF_FFMPEG = LIBDIR + '/ffmpeg'
 BF_FFMPEG_LIB = 'avformat-53 avcodec-53 avdevice-53 avutil-51 swscale-2'
+BF_FFMPEG_DLL = '${BF_FFMPEG_LIBPATH}/avformat-53.dll ${BF_FFMPEG_LIBPATH}/avcodec-53.dll ${BF_FFMPEG_LIBPATH}/avdevice-53.dll ${BF_FFMPEG_LIBPATH}/avutil-51.dll ${BF_FFMPEG_LIBPATH}/swscale-2.dll'
 BF_FFMPEG_INC = '${BF_FFMPEG}/include'
 BF_FFMPEG_LIBPATH = '${BF_FFMPEG}/lib'
 BF_FFMPEG_DLL = '${BF_FFMPEG_LIBPATH}/avformat-53.dll ${BF_FFMPEG_LIBPATH}/avcodec-53.dll ${BF_FFMPEG_LIBPATH}/avdevice-53.dll ${BF_FFMPEG_LIBPATH}/avutil-51.dll ${BF_FFMPEG_LIBPATH}/swscale-2.dll'
index faa0ae7..4be6f51 100644 (file)
@@ -14,7 +14,7 @@ def createTexture(cont):
     object = cont.owner
 
     # get the reference pointer (ID) of the internal texture
-    ID = texture.materialID(obj, 'IMoriginal.png')
+    ID = texture.materialID(object, 'IMoriginal.png')
 
     # create a texture object
     object_texture = texture.Texture(object, ID)
index 52edfa0..0981712 100644 (file)
@@ -21,7 +21,7 @@ class HelloWorldOperator(bpy.types.Operator):
         print("Hello World")
         return {'FINISHED'}
 
-bpy.utils.register_class(SimpleOperator)
+bpy.utils.register_class(HelloWorldOperator)
 
 # test call to the newly defined operator
 bpy.ops.wm.hello_world()
diff --git a/doc/python_api/rst/gpu.rst b/doc/python_api/rst/gpu.rst
new file mode 100644 (file)
index 0000000..72a5dc2
--- /dev/null
@@ -0,0 +1,531 @@
+
+GPU functions (gpu)
+===================
+
+*****
+Intro
+*****
+
+Module to provide functions concerning the GPU implementation in Blender, in particular
+the GLSL shaders that blender generates automatically to render materials in the 3D view
+and in the game engine.
+
+.. warning::
+
+    The API provided by this module should be consider unstable. The data exposed by the API 
+    are are closely related to Blender's internal GLSL code and may change if the GLSL code 
+    is modified (e.g. new uniform type). 
+
+.. module:: gpu
+
+*********
+Constants
+*********
+
+--------------
+GLSL data type
+--------------
+
+.. _data-type:
+
+Type of GLSL data.
+For shader uniforms, the data type determines which glUniform function
+variant to use to send the uniform value to the GPU.
+For vertex attributes, the data type determines which glVertexAttrib function
+variant to use to send the vertex attribute to the GPU.
+
+See export_shader_
+
+.. data:: GPU_DATA_1I
+
+   one integer
+
+   :value: 1
+
+.. data:: GPU_DATA_1F
+
+   one float
+
+   :value: 2
+
+.. data:: GPU_DATA_2F
+
+   two floats
+
+   :value: 3
+
+.. data:: GPU_DATA_3F
+
+   three floats
+   
+   :value: 4
+   
+.. data:: GPU_DATA_4F
+
+   four floats
+   
+   :value: 5
+   
+.. data:: GPU_DATA_9F
+
+   matrix 3x3 in column-major order
+
+   :value: 6
+
+.. data:: GPU_DATA_16F
+
+   matrix 4x4 in column-major order
+
+   :value: 7
+
+.. data:: GPU_DATA_4UB
+
+   four unsigned byte
+
+   :value: 8
+
+-----------------
+GLSL uniform type
+-----------------
+
+.. _uniform-type:
+
+Constants that specify the type of uniform used in a GLSL shader. 
+The uniform type determines the data type, origin and method
+of calculation used by Blender to compute the uniform value. 
+
+The calculation of some of the uniforms is based on matrices available in the scene:
+
+    .. _mat4_cam_to_world:
+    .. _mat4_world_to_cam:
+
+    *mat4_cam_to_world*
+      Model matrix of the camera. OpenGL 4x4 matrix that converts 
+      camera local coordinates to world coordinates. In blender this is obtained from the
+      'matrix_world' attribute of the camera object.
+
+      Some uniform will need the *mat4_world_to_cam*
+      matrix computed as the inverse of this matrix.
+
+    .. _mat4_object_to_world:
+    .. _mat4_world_to_object:
+
+    *mat4_object_to_world*
+      Model matrix of the object that is being rendered. OpenGL 4x4 matric that converts
+      object local coordinates to world coordinates. In blender this is obtained from the
+      'matrix_world' attribute of the object.
+  
+      Some uniform will need the *mat4_world_to_object* matrix, computed as the inverse of this matrix.
+  
+    .. _mat4_lamp_to_world:
+    .. _mat4_world_to_lamp:
+
+    *mat4_lamp_to_world*
+      Model matrix of the lamp lighting the object. OpenGL 4x4 matrix that converts lamp
+      local coordinates to world coordinates. In blender this is obtained from the
+      'matrix_world' attribute of the lamp object.
+      
+      Some uniform will need the *mat4_world_to_lamp* matrix
+      computed as the inverse of this matrix.
+
+.. data:: GPU_DYNAMIC_OBJECT_VIEWMAT
+
+    The uniform is a 4x4 GL matrix that converts world coordinates to 
+    camera coordinates (see mat4_world_to_cam_). Can be set once per frame.
+    There is at most one uniform of that type per shader.
+
+    :value: 1
+
+.. data:: GPU_DYNAMIC_OBJECT_MAT
+
+    The uniform is a 4x4 GL matrix that converts object coordinates 
+    to world coordinates (see mat4_object_to_world_). Must be set before drawing the object.
+    There is at most one uniform of that type per shader.
+
+    :value: 2
+
+.. data:: GPU_DYNAMIC_OBJECT_VIEWIMAT
+
+    The uniform is a 4x4 GL matrix that converts coordinates
+    in camera space to world coordinates (see mat4_cam_to_world_).
+    Can be set once per frame. 
+    There is at most one uniform of that type per shader.
+
+    :value: 3
+
+.. data:: GPU_DYNAMIC_OBJECT_IMAT
+
+    The uniform is a 4x4 GL matrix that converts world coodinates
+    to object coordinates (see mat4_world_to_object_).
+    Must be set before drawing the object.
+    There is at most one uniform of that type per shader.
+   
+    :value: 4
+   
+.. data:: GPU_DYNAMIC_OBJECT_COLOR
+
+    The uniform is a vector of 4 float representing a RGB color + alpha defined at object level.
+    Each values between 0.0 and 1.0. In blender it corresponds to the 'color' attribute of the object.
+    Must be set before drawing the object.
+    There is at most one uniform of that type per shader.
+   
+    :value: 5
+   
+.. data:: GPU_DYNAMIC_LAMP_DYNVEC
+
+    The uniform is a vector of 3 float representing the direction of light in camera space.
+    In Blender, this is computed by 
+
+    mat4_world_to_cam_ * (-vec3_lamp_Z_axis) 
+
+    as the lamp Z axis points to the opposite direction of light.
+    The norm of the vector should be unity. Can be set once per frame.
+    There is one uniform of that type per lamp lighting the material.
+
+    :value: 6
+   
+.. data:: GPU_DYNAMIC_LAMP_DYNCO
+
+    The uniform is a vector of 3 float representing the position of the light in camera space.
+    Computed as 
+    
+    mat4_world_to_cam_ * vec3_lamp_pos
+
+    Can be set once per frame.
+    There is one uniform of that type per lamp lighting the material.
+   
+    :value: 7
+   
+.. data:: GPU_DYNAMIC_LAMP_DYNIMAT
+
+    The uniform is a 4x4 GL matrix that converts vector in camera space to lamp space.
+    Computed as 
+
+    mat4_world_to_lamp_ * mat4_cam_to_world_
+
+    Can be set once per frame.
+    There is one uniform of that type per lamp lighting the material.
+
+    :value: 8
+
+.. data:: GPU_DYNAMIC_LAMP_DYNPERSMAT
+
+    The uniform is a 4x4 GL matrix that converts a vector in camera space to shadow buffer depth space.
+    Computed as 
+
+    mat4_perspective_to_depth_ * mat4_lamp_to_perspective_ * mat4_world_to_lamp_ * mat4_cam_to_world_.
+
+    .. _mat4_perspective_to_depth:
+
+    *mat4_perspective_to_depth* is a fixed matrix defined as follow::
+
+        0.5 0.0 0.0 0.5
+        0.0 0.5 0.0 0.5
+        0.0 0.0 0.5 0.5
+        0.0 0.0 0.0 1.0
+
+    This uniform can be set once per frame. There is one uniform of that type per lamp casting shadow in the scene.
+
+    :value: 9
+
+.. data:: GPU_DYNAMIC_LAMP_DYNENERGY
+
+    The uniform is a single float representing the lamp energy. In blender it corresponds
+    to the 'energy' attribute of the lamp data block.
+    There is one uniform of that type per lamp lighting the material.
+
+    :value: 10
+
+.. data:: GPU_DYNAMIC_LAMP_DYNCOL
+
+    The uniform is a vector of 3 float representing the lamp color. 
+    Color elements are between 0.0 and 1.0. In blender it corresponds
+    to the 'color' attribute of the lamp data block.
+    There is one uniform of that type per lamp lighting the material.
+
+    :value: 11
+
+.. data:: GPU_DYNAMIC_SAMPLER_2DBUFFER
+
+    The uniform is an integer representing an internal texture used for certain effect
+    (color band, etc). 
+       
+    :value: 12
+
+.. data:: GPU_DYNAMIC_SAMPLER_2DIMAGE
+
+    The uniform is an integer representing a texture loaded from an image file. 
+
+    :value: 13
+
+.. data:: GPU_DYNAMIC_SAMPLER_2DSHADOW
+
+    The uniform is an integer representing a shadow buffer corresponding to a lamp
+    casting shadow.
+
+    :value: 14
+
+-------------------
+GLSL attribute type
+-------------------
+
+.. _attribute-type:
+
+Type of the vertex attribute used in the GLSL shader. Determines the mesh custom data
+layer that contains the vertex attribute. 
+
+.. data:: CD_MTFACE
+
+    Vertex attribute is a UV layer. Data type is vector of 2 float.
+
+    There can be more than one attribute of that type, they are differenciated by name.
+    In blender, you can retrieve the attribute data with:
+
+    .. code-block:: python
+
+        mesh.uv_textures[attribute['name']]
+
+    :value: 5
+
+.. data:: CD_MCOL
+
+    Vertex attribute is color layer. Data type is vector 4 unsigned byte (RGBA).
+
+    There can be more than one attribute of that type, they are differenciated by name.
+    In blender you can retrieve the attribute data with:
+
+    .. code-block:: python
+
+        mesh.vertex_colors[attribute['name']]
+
+    :value: 6
+
+.. data:: CD_ORCO
+
+    Vertex attribute is original coordinates. Data type is vector 3 float.
+
+    There can be only 1 attribute of that type per shader.     
+    In blender you can retrieve the attribute data with:
+  
+    .. code-block:: python
+
+        mesh.vertices
+
+    :value: 14
+
+.. data:: CD_TANGENT
+
+    Vertex attribute is the tangent vector. Data type is vector 4 float.
+
+    There can be only 1 attribute of that type per shader.
+    There is currently no way to retrieve this attribute data via the RNA API but a standalone 
+    C function to compute the tangent layer from the other layers can be obtained from
+    blender.org.
+
+    :value: 18
+
+*********
+Functions
+*********
+
+.. _export_shader:
+
+.. function:: export_shader(scene,material)
+
+    Extracts the GLSL shader producing the visual effect of material in scene for the purpose of 
+    reusing the shader in an external engine. This function is meant to be used in material exporter 
+    so that the GLSL shader can be exported entirely. The return value is a dictionary containing the
+    shader source code and all associated data. 
+
+    :arg scene: the scene in which the material in rendered.
+    :type scene: :class:`bpy.types.Scene`
+    :arg material: the material that you want to export the GLSL shader
+    :type material: :class:`bpy.types.Material`
+    :return: the shader source code and all associated data in a dictionary
+    :rtype: dictionary
+
+    The dictionary contains the following elements:
+
+    * ['fragment'] : string
+        fragment shader source code.
+    
+    * ['vertex'] : string
+        vertex shader source code.
+
+    * ['uniforms'] : sequence
+        list of uniforms used in fragment shader, can be empty list. Each element of the
+        sequence is a dictionary with the following elements:
+
+        * ['varname'] : string
+            name of the uniform in the fragment shader. Always of the form 'unf<number>'.
+
+        * ['datatype'] : integer
+            data type of the uniform variable. Can be one of the following:
+
+            * :data:`gpu.GPU_DATA_1I` : use glUniform1i
+            * :data:`gpu.GPU_DATA_1F` : use glUniform1fv
+            * :data:`gpu.GPU_DATA_2F` : use glUniform2fv
+            * :data:`gpu.GPU_DATA_3F` : use glUniform3fv
+            * :data:`gpu.GPU_DATA_4F` : use glUniform4fv
+            * :data:`gpu.GPU_DATA_9F` : use glUniformMatrix3fv
+            * :data:`gpu.GPU_DATA_16F` : use glUniformMatrix4fv
+
+        * ['type'] : integer
+            type of uniform, determines the origin and method of calculation. See uniform-type_.
+            Depending on the type, more elements will be be present.
+
+        * ['lamp'] : :class:`bpy.types.Object`
+            Reference to the lamp object from which the uniforms value are extracted. Set for the following uniforms types:
+
+            .. hlist::
+               :columns: 3
+
+               * :data:`gpu.GPU_DYNAMIC_LAMP_DYNVEC`
+               * :data:`gpu.GPU_DYNAMIC_LAMP_DYNCO`
+               * :data:`gpu.GPU_DYNAMIC_LAMP_DYNIMAT`
+               * :data:`gpu.GPU_DYNAMIC_LAMP_DYNPERSMAT`
+               * :data:`gpu.GPU_DYNAMIC_LAMP_DYNENERGY`
+               * :data:`gpu.GPU_DYNAMIC_LAMP_DYNCOL`
+               * :data:`gpu.GPU_DYNAMIC_SAMPLER_2DSHADOW`
+
+            Notes:
+
+            * The uniforms :data:`gpu.GPU_DYNAMIC_LAMP_DYNVEC`, :data:`gpu.GPU_DYNAMIC_LAMP_DYNCO`, :data:`gpu.GPU_DYNAMIC_LAMP_DYNIMAT` and :data:`gpu.GPU_DYNAMIC_LAMP_DYNPERSMAT`
+              refer to the lamp object position and orientation, both of can be derived from the object world matrix:
+
+              .. code-block:: python
+
+                obmat = uniform['lamp'].matrix_world
+
+              where obmat is the mat4_lamp_to_world_ matrix of the lamp as a 2 dimensional array,
+              the lamp world location location is in obmat[3].
+
+            * The uniform types :data:`gpu.GPU_DYNAMIC_LAMP_DYNENERGY` and :data:`gpu.GPU_DYNAMIC_LAMP_DYNCOL` refer to the lamp data bloc that you get from:
+
+              .. code-block:: python
+
+                la = uniform['lamp'].data
+          
+              from which you get la.energy and la.color
+
+            * Lamp duplication is not supported: if you have duplicated lamps in your scene
+              (i.e. lamp that are instantiated by dupligroup, etc), this element will only 
+              give you a reference to the orignal lamp and you will not know which instance
+              of the lamp it is refering too. You can still handle that case in the exporter
+              by distributing the uniforms amongst the duplicated lamps.
+              
+        * ['image'] : :class:`bpy.types.Image`
+            Reference to the image databloc. Set for uniform type :data:`gpu.GPU_DYNAMIC_SAMPLER_2DIMAGE`. You can get the image data from:
+
+            .. code-block:: python
+
+               # full path to image file
+               uniform['image'].filepath
+               # image size as a 2-dimensional array of int
+               uniform['image'].size
+
+        * ['texnumber'] : integer
+            Channel number to which the texture is bound when drawing the object.
+            Set for uniform types :data:`gpu.GPU_DYNAMIC_SAMPLER_2DBUFFER`, :data:`gpu.GPU_DYNAMIC_SAMPLER_2DIMAGE` and :data:`gpu.GPU_DYNAMIC_SAMPLER_2DSHADOW`.
+
+            This is provided for information only: when reusing the shader outside blencer, 
+            you are free to assign the textures to the channel of your choice and to pass
+            that number channel to the GPU in the uniform.
+
+        * ['texpixels'] : byte array
+            texture data for uniform type :data:`gpu.GPU_DYNAMIC_SAMPLER_2DBUFFER`. Although
+            the corresponding uniform is a 2D sampler, the texture is always a 1D texture
+            of n x 1 pixel. The texture size n is provided in ['texsize'] element. 
+            These texture are only used for computer generated texture (colorband, etc).
+            The texture data is provided so that you can make a real image out of it in the
+            exporter.
+               
+        * ['texsize'] : integer
+            horizontal size of texture for uniform type :data:`gpu.GPU_DYNAMIC_SAMPLER_2DBUFFER`. 
+            The texture data is in ['texpixels'].
+
+    * ['attributes'] : sequence
+        list of attributes used in vertex shader, can be empty. Blender doesn't use
+        standard attributes except for vertex position and normal. All other vertex
+        attributes must be passed using the generic glVertexAttrib functions.
+        The attribute data can be found in the derived mesh custom data using RNA.
+        Each element of the sequence is a dictionary containing the following elements:
+
+        * ['varname'] : string
+            name of the uniform in the vertex shader. Always of the form 'att<number>'.
+
+        * ['datatype'] : integer
+            data type of vertex attribute, can be one of the following:
+
+            * :data:`gpu.GPU_DATA_2F` : use glVertexAttrib2fv
+            * :data:`gpu.GPU_DATA_3F` : use glVertexAttrib3fv
+            * :data:`gpu.GPU_DATA_4F` : use glVertexAttrib4fv
+            * :data:`gpu.GPU_DATA_4UB` : use glVertexAttrib4ubv
+
+        * ['number'] : integer
+            generic attribute number. This is provided for information only. Blender 
+            doesn't use glBindAttribLocation to place generic attributes at specific location,
+            it lets the shader compiler place the attributes automatically and query the 
+            placement with glGetAttribLocation. The result of this placement is returned in 
+            this element. 
+
+            When using this shader in a render engine, you should either use
+            glBindAttribLocation to force the attribute at this location or use 
+            glGetAttribLocation to get the placement chosen by the compiler of your GPU.
+
+        * ['type'] : integer
+            type of the mesh custom data from which the vertex attribute is loaded. 
+            See attribute-type_.
+
+        * ['name'] : string or integer
+            custom data layer name, used for attribute type :data:`gpu.CD_MTFACE` and :data:`gpu.CD_MCOL`.
+
+    Example:
+
+    .. code-block:: python
+
+        import gpu
+        # get GLSL shader of material Mat.001 in scene Scene.001
+        scene = bpy.data.scenes['Scene.001']
+        material = bpy.data.materials['Mat.001']
+        shader = gpu.export_shader(scene,material)
+        # scan the uniform list and find the images used in the shader
+        for uniform in shader['uniforms']:
+            if uniform['type'] == gpu.GPU_DYNAMIC_SAMPLER_2DIMAGE:
+                print("uniform {0} is using image {1}".format(uniform['varname'], uniform['image'].filepath))
+        # scan the attribute list and find the UV layer used in the shader
+        for attribute in shader['attributes']:
+            if attribute['type'] == gpu.CD_MTFACE:
+                print("attribute {0} is using UV layer {1}".format(attribute['varname'], attribute['name']))
+
+*****
+Notes
+*****
+
+.. _mat4_lamp_to_perspective:
+
+1. Calculation of the *mat4_lamp_to_perspective* matrix for a spot lamp.
+
+   The following pseudo code shows how the *mat4_lamp_to_perspective* matrix is computed 
+   in blender for uniforms of :data:`gpu.GPU_DYNAMIC_LAMP_DYNPERSMAT` type::
+
+     #Get the lamp datablock with:
+     lamp=bpy.data.objects[uniform['lamp']].data
+
+     #Compute the projection matrix:
+     #  You will need these lamp attributes:
+     #  lamp.clipsta : near clip plane in world unit
+     #  lamp.clipend : far clip plane in world unit
+     #  lamp.spotsize : angle in degree of the spot light
+
+     #The size of the projection plane is computed with the usual formula:
+     wsize = lamp.clista * tan(lamp.spotsize/2)
+
+     #And the projection matrix:
+     mat4_lamp_to_perspective = glFrustum(-wsize,wsize,-wsize,wsize,lamp.clista,lamp.clipend)
+
+2. Creation of the shadow map for a spot lamp.
+
+   The shadow map is the depth buffer of a render performed by placing the camera at the
+   spot light position. The size of the shadow map is given by the attribute lamp.bufsize : 
+   shadow map size in pixel, same size in both dimensions.
diff --git a/doc/python_api/rst/info_best_practice.rst b/doc/python_api/rst/info_best_practice.rst
new file mode 100644 (file)
index 0000000..2fbc636
--- /dev/null
@@ -0,0 +1,65 @@
+*************
+Best Practice
+*************
+
+
+TODO: Intro text
+
+
+Style Conventions
+=================
+
+For Blender 2.5 we have chosen to follow python suggested style guide to avoid mixing styles amongst our own scripts and make it easier to use python scripts from other projects.
+
+Using our style guide for your own scripts makes it easier if you eventually want to contribute them to blender.
+
+This style guide is known as pep8 and can be found `here <http://www.python.org/dev/peps/pep-0008>`_
+
+A brief listing of pep8 criteria.
+
+* camel caps for class names: MyClass
+
+* all lower case underscore separated module names: my_module
+
+* indentation of 4 spaces (no tabs)
+
+* spaces around operators. ``1 + 1``, not ``1+1``
+
+* only use explicit imports, (no importing '*')
+
+* don't use single line: ``if val: body``, separate onto 2 lines instead.
+
+
+As well as pep8 we have other conventions used for blender python scripts.
+
+* Use single quotes for enums, and double quotes for strings.
+
+  Both are of course strings but in our internal API enums are unique items from a limited set. eg.
+
+  .. code-block:: python
+
+     bpy.context.scene.render.file_format = 'PNG'
+     bpy.context.scene.render.filepath = "//render_out"
+
+* pep8 also defines that lines should not exceed 79 characters, we felt this is too restrictive so this is optional per script.
+
+Periodically we run checks for pep8 compliance on blender scripts, for scripts to be included in this check add this line as a comment at the top of the script.
+
+``# <pep8 compliant>``
+
+To enable line length checks use this instead.
+
+``# <pep8-80 compliant>``
+
+
+User Interface Layout
+=====================
+
+TODO: Thomas
+
+
+Script Efficiency
+=================
+
+TODO: Campbell
+
index c97fc3a..e7903dc 100644 (file)
@@ -1,6 +1,6 @@
-********
-Gotcha's
-********
+*******
+Gotchas
+*******
 
 This document attempts to help you work with the Blender API in areas that can be troublesome and avoid practices that are known to give instability.
 
@@ -32,12 +32,12 @@ Which raises the question as to what the correct context might be?
 
 Typically operators check for the active area type, a selection or active object they can operate on, but some operators are more picky about when they run.
 
-In most cases you can figure out what context an operator needs simply be seeing how its used in Blender and thinking about what it does.
+In most cases you can figure out what context an operator needs simply be seeing how it's used in Blender and thinking about what it does.
 
 
 Unfortunately if you're still stuck - the only way to **really** know whats going on is to read the source code for the poll function and see what its checking.
 
-For python operators its not so hard to find the source since its included with with Blender and the source file/line is included in the operator reference docs.
+For python operators it's not so hard to find the source since it's included with Blender and the source file/line is included in the operator reference docs.
 
 Downloading and searching the C code isn't so simple, especially if you're not familiar with the C language but by searching the operator name or description you should be able to find the poll function with no knowledge of C.
 
@@ -74,7 +74,7 @@ Sometimes you want to modify values from python and immediately access the updat
 
 Once changing the objects :class:`bpy.types.Object.location` you may want to access its transformation right after from :class:`bpy.types.Object.matrix_world`, but this doesn't work as you might expect.
 
-Consider the calculations that might go into working out the objects final transformation, this includes:
+Consider the calculations that might go into working out the object's final transformation, this includes:
 
 * animation function curves.
 * drivers and their pythons expressions.
@@ -106,7 +106,7 @@ Modal operators execute on user input or setup their own timers to run frequentl
 
 Transform, Painting, Fly-Mode and File-Select are example of a modal operators.
 
-Writing modal operators takes more effort then a simple ``for`` loop that happens to redraw but is more flexible and integrates better with Blenders design.
+Writing modal operators takes more effort than a simple ``for`` loop that happens to redraw but is more flexible and integrates better with Blenders design.
 
 
 **Ok, Ok! I still want to draw from python**
@@ -129,7 +129,7 @@ This is different to **numpy** which is row-major which matches what you would e
 I can't edit the mesh in edit-mode!
 ===================================
 
-Blenders EditMesh is an internal data structure (not saved and not exposed to python), this gives the main annoyance that you need to exit edit-mode to edit the mesh from python.
+Blender's EditMesh is an internal data structure (not saved and not exposed to python), this gives the main annoyance that you need to exit edit-mode to edit the mesh from python.
 
 The reason we have not made much attempt to fix this yet is because we
 will likely move to BMesh mesh API eventually, so any work on the API now will be wasted effort.
@@ -226,13 +226,13 @@ This is mainly an issue with editmode since pose data can be manipulated without
 Unicode Problems
 ================
 
-Python supports many different encpdings so there is nothing stopping you from writing a script in latin1 or iso-8859-15.
+Python supports many different encodings so there is nothing stopping you from writing a script in latin1 or iso-8859-15.
 
 See `pep-0263 <http://www.python.org/dev/peps/pep-0263/>`_
 
-However this complicates things for the python api because blend files themselves dont have an encoding.
+However this complicates things for the python api because blend files themselves don't have an encoding.
 
-To simplify the problem for python integration and script authors we have decieded all strings in blend files **must** be UTF-8 or ASCII compatible.
+To simplify the problem for python integration and script authors we have decided all strings in blend files **must** be UTF-8 or ASCII compatible.
 
 This means assigning strings with different encodings to an object names for instance will raise an error.
 
@@ -331,13 +331,13 @@ This an example of a timer which runs many times a second and moves the default
 
    my_timer()
 
-Use cases like the one above which leave the thread running once the script finishes may seem to work for a while but end up causing random crashes or errors in Blenders own drawing code.
+Use cases like the one above which leave the thread running once the script finishes may seem to work for a while but end up causing random crashes or errors in Blender's own drawing code.
 
-So far no work has gone into making Blenders python integration thread safe, so until its properly supported, best not make use of this.
+So far, no work has gone into making Blender's python integration thread safe, so until its properly supported, best not make use of this.
 
 .. note::
 
-   Pythons threads only allow co-currency and wont speed up you're scripts on multi-processor systems, the ``subprocess`` and ``multiprocess`` modules can be used with blender and make use of multiple CPU's too.
+   Pythons threads only allow co-currency and won't speed up your scripts on multi-processor systems, the ``subprocess`` and ``multiprocess`` modules can be used with blender and make use of multiple CPU's too.
 
 
 Help! My script crashes Blender
@@ -378,6 +378,41 @@ This example shows how you can tell undo changes the memory locations.
 As suggested above, simply not holding references to data when Blender is used interactively by the user is the only way to ensure the script doesn't become unstable.
 
 
+Edit Mode / Memory Access
+-------------------------
+
+Switching edit-mode ``bpy.ops.object.mode_set(mode='EDIT')`` / ``bpy.ops.object.mode_set(mode='OBJECT')`` will re-allocate objects data, any references to a meshes vertices/faces/uvs, armatures bones, curves points etc cannot be accessed after switching edit-mode.
+
+Only the reference to the data its self can be re-accessed, the following example will crash.
+
+.. code-block:: python
+
+   mesh = bpy.context.active_object.data
+   faces = mesh.faces
+   bpy.ops.object.mode_set(mode='EDIT')
+   bpy.ops.object.mode_set(mode='OBJECT')
+
+   # this will crash
+   print(faces)
+
+
+So after switching edit-mode you need to re-access any object data variables, the following example shows how to avoid the crash above.
+
+.. code-block:: python
+
+   mesh = bpy.context.active_object.data
+   faces = mesh.faces
+   bpy.ops.object.mode_set(mode='EDIT')
+   bpy.ops.object.mode_set(mode='OBJECT')
+
+   # faces have been re-allocated
+   faces = mesh.faces
+   print(faces)
+
+
+These kinds of problems can happen for any functions which re-allocate the object data but are most common when switching edit-mode.
+
+
 Array Re-Allocation
 -------------------
 
index 751e5e1..e7f2900 100644 (file)
@@ -420,49 +420,3 @@ Using Low-Level Functions:
    fcu_z.keyframe_points[0].co = 10.0, 0.0
    fcu_z.keyframe_points[1].co = 20.0, 1.0
 
-
-Style Conventions
-=================
-
-For Blender 2.5 we have chosen to follow python suggested style guide to avoid mixing styles amongst our own scripts and make it easier to use python scripts from other projects.
-
-Using our style guide for your own scripts makes it easier if you eventually want to contribute them to blender.
-
-This style guide is known as pep8 and can be found `here <http://www.python.org/dev/peps/pep-0008>`_
-
-A brief listing of pep8 criteria.
-
-* camel caps for class names: MyClass
-
-* all lower case underscore separated module names: my_module
-
-* indentation of 4 spaces (no tabs)
-
-* spaces around operators. ``1 + 1``, not ``1+1``
-
-* only use explicit imports, (no importing '*')
-
-* don't use single line: ``if val: body``, separate onto 2 lines instead.
-
-
-As well as pep8 we have other conventions used for blender python scripts.
-
-* Use single quotes for enums, and double quotes for strings.
-
-  Both are of course strings but in our internal API enums are unique items from a limited set. eg.
-
-  .. code-block:: python
-
-     bpy.context.scene.render.file_format = 'PNG'
-     bpy.context.scene.render.filepath = "//render_out"
-
-* pep8 also defines that lines should not exceed 79 characters, we felt this is too restrictive so this is optional per script.
-
-Periodically we run checks for pep8 compliance on blender scripts, for scripts to be included in this check add this line as a comment at the top of the script.
-
-``# <pep8 compliant>``
-
-To enable line length checks use this instead.
-
-``# <pep8-80 compliant>``
-
index 3ce2cfd..2bcb1e7 100644 (file)
@@ -2,56 +2,51 @@
 Tips and Tricks
 ***************
 
-Some of these are just python features that scripters may not have thaught to use with blender.
+Here are various suggestions that you might find useful when writing scripts.
+
+Some of these are just python features that scripters may not have thought to use with blender, others are blender specific.
 
 
 Use The Terminal
 ================
 
-When writing python scripts, its useful to have a terminal open, this is not the built-in python console but a terminal application which is used to start blender.
+When writing python scripts, it's useful to have a terminal open, this is not the built-in python console but a terminal application which is used to start blender.
 
 There are 3 main uses for the terminal, these are:
 
-* You can see the output of `print()` as you're script runs, which is useful to view debug info.
+* You can see the output of ``print()`` as you're script runs, which is useful to view debug info.
 
-* The error tracebacks are printed in full to the terminal which wont always generate an error popup in blenders user interface (depending on how the script is executed).
+* The error trace-back is printed in full to the terminal which won't always generate an error popup in blender's user interface (depending on how the script is executed).
 
-* If the script runs for too long or you accidentally enter an infinate loop, Ctrl+C in the terminal (Ctrl+Break on Windows) will quit the script early.
+* If the script runs for too long or you accidentally enter an infinite loop, Ctrl+C in the terminal (Ctrl+Break on Windows) will quit the script early.
 
 .. note::
    For Linux and OSX users this means starting the terminal first, then running blender from within it. On Windows the terminal can be enabled from the help menu.
 
 
-Run External Scripts
-====================
+Use an External Editor
+======================
 
-Blenders text editor is fine for edits and writing small tests but it is not a full featured editor so for larger projects you'll probably want to use an external editor.
+Blenders text editor is fine for small changes and writing tests but its not full featured, for larger projects you'll probably want to use a standalone editor or python IDE.
 
 Editing a text file externally and having the same text open in blender does work but isn't that optimal so here are 2 ways you can easily use an external file from blender.
 
+Using the following examples you'll still need textblock in blender to execute, but reference an external file rather then including it directly.
 
 Executing External Scripts
-^^^^^^^^^^^^^^^^^^^^^^^^^^
+--------------------------
 
-This is the equivilent to running the script directly, referencing a scripts path from a 2 line textblock.
+This is the equivalent to running the script directly, referencing a scripts path from a 2 line textblock.
 
-.. code-block::
+.. code-block:: python
 
    filename = "/full/path/to/myscript.py"
    exec(compile(open(filename).read(), filename, 'exec'))
 
 
-You might also want to reference the file relative to the blend file.
-
-.. code-block::
-
-   filename = "/full/path/to/script.py"
-   exec(compile(open(filename).read(), filename, 'exec'))
+You might want to reference a script relative to the blend file.
 
-
-You might want to reference a script thats at the same location as the blend file.
-
-.. code-block::
+.. code-block:: python
 
    import bpy
    import os
@@ -61,11 +56,11 @@ You might want to reference a script thats at the same location as the blend fil
 
 
 Executing Modules
-^^^^^^^^^^^^^^^^^
+-----------------
 
 This example shows loading a script in as a module and executing a module function.
 
-.. code-block::
+.. code-block:: python
 
    import myscript
    import imp
@@ -74,18 +69,18 @@ This example shows loading a script in as a module and executing a module functi
    myscript.main()
 
 
-Notice that the script is reloaded every time, this forces an update, normally the module stays cached in `sys.modules`.
+Notice that the script is reloaded every time, this forces use of the modified version, otherwise the cached one in ``sys.modules`` would be used until blender was restarted.
 
-The main difference between this and executing the script directly is it has to call a function in the module, in this case `main()` but it can be any function, an advantage with this is you can pass argumnents to the function from this small script which is often useful for testing differnt settings quickly.
+The important difference between this and executing the script directly is it has to call a function in the module, in this case ``main()`` but it can be any function, an advantage with this is you can pass arguments to the function from this small script which is often useful for testing different settings quickly.
 
 The other issue with this is the script has to be in pythons module search path.
 While this is not best practice - for testing you can extend the search path, this example adds the current blend files directory to the search path, then loads the script as a module.
 
-.. code-block::
+.. code-block:: python
 
    import sys
    import os
-   impory bpy
+   import bpy
 
    blend_dir = os.path.basename(bpy.data.filepath)
    if blend_dir not in sys.path:
@@ -100,37 +95,103 @@ While this is not best practice - for testing you can extend the search path, th
 Don't Use Blender!
 ==================
 
-While developing your own scripts blenders interface can get in the way, manually reloading, running the scripts, opening file import etc is just overhead.
+While developing your own scripts blenders interface can get in the way, manually reloading, running the scripts, opening file import etc. adds overhead.
+
+For scripts that are not interactive it can end up being more efficient not to use blenders interface at all and instead execute the script on the command line.
+
+.. code-block:: python
+
+   blender --background --python myscript.py
 
-For scripts that are not interactive it can end up being easier not to use blender at all and run blender from a terminal, without opening a window and execute the script on the command line.
 
-.. code-block::
+You might want to run this with a blend file so the script has some data to operate on.
 
-   blender --backgruond --python myscript.py
+.. code-block:: python
 
+   blender myscene.blend --background --python myscript.py
+
+
+.. note::
 
-You might want to run this with a blend file too.
+   Depending on your setup you might have to enter the full path to the blender executable.
 
-.. code-block::
 
-   blender myscene.blend --backgruond --python myscript.py
+Once the script is running properly in background mode, you'll want to check the output of the script, this depends completely on the task at hand however here are some suggestions.
 
+* render the output to an image, use an image viewer and keep writing over the same image each time.
+
+* save a new blend file, or export the file using one of blenders exporters.
+
+* if the results can be displayed as text - print them or write them to a file.
+
+
+This can take a little time to setup, but it can be well worth the effort to reduce the time it takes to test changes - you can even have blender running the script ever few seconds with a viewer updating the results, so no need to leave you're text editor to see changes.
 
 
 Use External Tools
 ==================
 
+When there are no readily available python modules to perform specific tasks it's worth keeping in mind you may be able to have python execute an external command on you're data and read the result back in.
+
+Using external programs adds an extra dependency and may limit who can use the script but to quickly setup you're own custom pipeline or writing one-off scripts this can be handy.
+
+Examples include:
+
+* Run The Gimp in batch mode to execute custom scripts for advanced image processing.
 
-Bundled Python
-==============
+* Write out 3D models to use external mesh manipulation tools and read back in the results.
 
-Blender from blender.org includes a compleate python installation on all platforms, this has the disadvantage that any extensions you have installed in you're systems python wont be found by blender.
+* Convert files into recognizable formats before reading.
+
+
+Bundled Python & Extensions
+===========================
+
+The Blender releases distributed from blender.org include a complete python installation on all platforms, this has the disadvantage that any extensions you have installed in you're systems python wont be found by blender.
 
 There are 2 ways around this:
 
-* remove blender python subdirectory, blender will then look for the systems python and use that instead **python version must match the one that blender comes with**.
+* remove blender python sub-directory, blender will then fallback on the systems python and use that instead **python version must match the one that blender comes with**.
+
+* copy the extensions into blender's python sub-directory so blender can access them, you could also copy the entire python installation into blenders sub-directory, replacing the one blender comes with. This works as long as the python versions match and the paths are created in the same relative locations. Doing this has the advantage that you can redistribute this bundle to others with blender and/or the game player, including any extensions you rely on.
+
+
+Drop Into a Python Interpreter in You're Script
+===============================================
 
-* copy the extensions into blender's python subdirectry so blender can access them, you could also copy the entire python installation into blenders subdirectory, replacing the one blender comes with. This works as long as the python versions match and the paths are created in the same location relative locations. Doing this has the advantage that you can redistribute this bundle to others with blender and/or the game player, including any extensions you rely on.
+In the middle of a script you may want to inspect some variables, run some function and generally dig about to see whats going on.
+
+.. code-block:: python
+
+   import code
+   code.interact(local=locals())
+
+
+If you want to access both global and local variables do this...
+
+.. code-block:: python
+
+   import code
+   namespace = globals().copy()
+   namespace.update(locals())
+   code.interact(local=namespace)
+
+
+The next example is an equivalent single line version of the script above which is easier to paste into you're code:
+
+.. code-block:: python
+
+   __import__('code').interact(local={k: v for ns in (globals(), locals()) for k, v in ns.items()})
+
+
+``code.interact`` can be added at any line in the script and will pause the script an launch an interactive interpreter in the terminal, when you're done you can quit the interpreter and the script will continue execution.
+
+
+Admittedly this highlights the lack of any python debugging support built into blender, but its still handy to know.
+
+.. note::
+
+   This works in the game engine as well, it can be handy to inspect the state of a running game.
 
 
 Advanced
@@ -140,10 +201,27 @@ Advanced
 Blender as a module
 -------------------
 
+From a python perspective it's nicer to have everything as an extension which lets the python script combine many components.
+
+Advantages include:
+
+* you can use external editors/IDE's with blenders python API and execute scripts within the IDE (step over code, inspect variables as the script runs).
+
+* editors/IDE's can auto complete blender modules & variables.
+
+* existing scripts can import blender API's without having to run inside blender.
+
+
+This is marked advanced because to run blender as a python module requires a special build option.
+
+For instructions on building see `Building blender as a python module <http://wiki.blender.org/index.php/User:Ideasman42/BlenderAsPyModule>`_
+
 
 Python Safety (Build Option)
 ----------------------------
 
+Since it's possible to access data which has been removed (see Gotcha's), this can be hard to track down the cause of crashes.
 
-CTypes in Blender
------------------
+To raise python exceptions on accessing freed data (rather then crashing), enable the CMake build option WITH_PYTHON_SAFETY.
+
+This enables data tracking which makes data access about 2x slower which is why the option is not enabled in release builds.
index 661d41a..ac2a498 100644 (file)
@@ -103,6 +103,8 @@ sphinx-build doc/python_api/sphinx-in doc/python_api/sphinx-out
 INFO_DOCS = (
     ("info_quickstart.rst", "Blender/Python Quickstart: new to blender/scripting and want to get you're feet wet?"),
     ("info_overview.rst", "Blender/Python API Overview: a more complete explanation of python integration"),
+    ("info_best_practice.rst", "Best Practice: Conventions to follow for writing good scripts"),
+    ("info_tips_and_tricks.rst", "Tips and Tricks: Hints to help you while writeing scripts for blender"),
     ("info_gotcha.rst", "Gotcha's: some of the problems you may come up against when writing scripts"),
     )
 
index 3990d13..0386b3d 100644 (file)
@@ -43,6 +43,10 @@ if(WITH_BUILTIN_GLEW)
        add_subdirectory(glew)
 endif()
 
+if(WITH_GAMEENGINE)
+   add_subdirectory(recastnavigation)
+endif()
+
 if(WITH_IMAGE_OPENJPEG AND (NOT UNIX OR APPLE))
        add_subdirectory(libopenjpeg)
 endif()
index 061bd1b..6bb060a 100644 (file)
@@ -4,6 +4,9 @@ Import('env')
 
 SConscript(['glew/SConscript'])
 
+if env['WITH_BF_GAMEENGINE']:
+    SConscript(['recastnavigation/SConscript'])
+
 if env['WITH_BF_ELTOPO']:
     SConscript(['eltopo/SConscript'])
 
diff --git a/extern/recastnavigation/CMakeLists.txt b/extern/recastnavigation/CMakeLists.txt
new file mode 100644 (file)
index 0000000..1af01b1
--- /dev/null
@@ -0,0 +1,66 @@
+# $Id$
+# ***** BEGIN GPL LICENSE BLOCK *****
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+#
+# The Original Code is Copyright (C) 2006, Blender Foundation
+# All rights reserved.
+#
+# The Original Code is: all of this file.
+#
+# Contributor(s): Daniel Genrich
+#
+# ***** END GPL LICENSE BLOCK *****
+
+set(INC 
+               Recast/Include 
+               Detour/Include
+)
+
+set(INC_SYS
+
+)
+
+set(SRC 
+               Detour/Source/DetourCommon.cpp
+               Detour/Source/DetourNode.cpp
+               Detour/Source/DetourStatNavMesh.cpp
+               Detour/Source/DetourStatNavMeshBuilder.cpp
+               Detour/Source/DetourTileNavMesh.cpp
+               Detour/Source/DetourTileNavMeshBuilder.cpp
+
+               Detour/Include/DetourCommon.h
+               Detour/Include/DetourNode.h
+               Detour/Include/DetourStatNavMesh.h
+               Detour/Include/DetourStatNavMeshBuilder.h
+               Detour/Include/DetourTileNavMesh.h
+               Detour/Include/DetourTileNavMeshBuilder.h
+                       
+               Recast/Source/Recast.cpp
+               Recast/Source/RecastContour.cpp
+               Recast/Source/RecastFilter.cpp
+               Recast/Source/RecastLog.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    
+)
+
+blender_add_lib(extern_recastnavigation "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/extern/recastnavigation/Detour/Include/DetourCommon.h b/extern/recastnavigation/Detour/Include/DetourCommon.h
new file mode 100644 (file)
index 0000000..d824efc
--- /dev/null
@@ -0,0 +1,167 @@
+//
+// Copyright (c) 2009 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 DETOURCOMMON_H
+#define DETOURCOMMON_H
+
+//////////////////////////////////////////////////////////////////////////////////////////
+
+template<class T> inline void swap(T& a, T& b) { T t = a; a = b; b = t; }
+template<class T> inline T min(T a, T b) { return a < b ? a : b; }
+template<class T> inline T max(T a, T b) { return a > b ? a : b; }
+template<class T> inline T abs(T a) { return a < 0 ? -a : a; }
+template<class T> inline T sqr(T a) { return a*a; }
+template<class T> inline T clamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); }
+
+inline void vcross(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]; 
+}
+
+inline float vdot(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)
+{
+       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)
+{
+       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)
+{
+       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)
+{
+       mn[0] = min(mn[0], v[0]);
+       mn[1] = min(mn[1], v[1]);
+       mn[2] = min(mn[2], v[2]);
+}
+
+inline void vmax(float* mx, const float* v)
+{
+       mx[0] = max(mx[0], v[0]);
+       mx[1] = max(mx[1], v[1]);
+       mx[2] = max(mx[2], v[2]);
+}
+
+inline void vcopy(float* dest, const float* a)
+{
+       dest[0] = a[0];
+       dest[1] = a[1];
+       dest[2] = a[2];
+}
+
+inline float vdist(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);
+}
+
+inline float vdistSqr(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 dx*dx + dy*dy + dz*dz;
+}
+
+inline void vnormalize(float* v)
+{
+       float d = 1.0f / sqrtf(sqr(v[0]) + sqr(v[1]) + sqr(v[2]));
+       v[0] *= d;
+       v[1] *= d;
+       v[2] *= d;
+}
+
+inline bool vequal(const float* p0, const float* p1)
+{
+       static const float thr = sqr(1.0f/16384.0f);
+       const float d = vdistSqr(p0, p1);
+       return d < thr;
+}
+
+inline int nextPow2(int v)
+{
+       v--;
+       v |= v >> 1;
+       v |= v >> 2;
+       v |= v >> 4;
+       v |= v >> 8;
+       v |= v >> 16;
+       v++;
+       return v;
+}
+
+inline float vdot2D(const float* u, const float* v)
+{
+       return u[0]*v[0] + u[2]*v[2];
+}
+
+inline float vperp2D(const float* u, const float* v)
+{
+       return u[2]*v[0] - u[0]*v[2];
+}
+
+inline float triArea2D(const float* a, const float* b, const float* c)
+{
+       return ((b[0]*a[2] - a[0]*b[2]) + (c[0]*b[2] - b[0]*c[2]) + (a[0]*c[2] - c[0]*a[2])) * 0.5f;
+}
+
+inline bool checkOverlapBox(const unsigned short amin[3], const unsigned short amax[3],
+                                                       const unsigned short bmin[3], const unsigned short bmax[3])
+{
+       bool overlap = true;
+       overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
+       overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
+       overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap;
+       return overlap;
+}
+
+void closestPtPointTriangle(float* closest, const float* p,
+                                                       const float* a, const float* b, const float* c);
+
+bool closestHeightPointTriangle(const float* p, const float* a, const float* b, const float* c, float& h);
+
+bool intersectSegmentPoly2D(const float* p0, const float* p1,
+                                                       const float* verts, int nverts,
+                                                       float& tmin, float& tmax,
+                                                       int& segMin, int& segMax);
+
+float distancePtSegSqr2D(const float* pt, const float* p, const float* q, float& t);
+
+void calcPolyCenter(float* tc, const unsigned short* idx, int nidx, const float* verts);
+
+#endif // DETOURCOMMON_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Include/DetourNode.h b/extern/recastnavigation/Detour/Include/DetourNode.h
new file mode 100644 (file)
index 0000000..316d5bf
--- /dev/null
@@ -0,0 +1,149 @@
+//
+// Copyright (c) 2009 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 DETOURNODE_H
+#define DETOURNODE_H
+
+enum dtNodeFlags
+{
+       DT_NODE_OPEN = 0x01,
+       DT_NODE_CLOSED = 0x02,
+};
+
+struct dtNode
+{
+       float cost;
+       float total;
+       unsigned int id;
+       unsigned int pidx : 30;
+       unsigned int flags : 2;
+};
+
+class dtNodePool
+{
+public:
+       dtNodePool(int maxNodes, int hashSize);
+       ~dtNodePool();
+       inline void operator=(const dtNodePool&) {}
+       void clear();
+       dtNode* getNode(unsigned int id);
+       const dtNode* findNode(unsigned int id) const;
+
+       inline unsigned int getNodeIdx(const dtNode* node) const
+       {
+               if (!node) return 0;
+               return (unsigned int)(node - m_nodes)+1;
+       }
+
+       inline dtNode* getNodeAtIdx(unsigned int idx)
+       {
+               if (!idx) return 0;
+               return &m_nodes[idx-1];
+       }
+       
+       inline int getMemUsed() const
+       {
+               return sizeof(*this) +
+               sizeof(dtNode)*m_maxNodes +
+               sizeof(unsigned short)*m_maxNodes +
+               sizeof(unsigned short)*m_hashSize;
+       }
+       
+private:
+       inline unsigned int hashint(unsigned int a) const
+       {
+               a += ~(a<<15);
+               a ^=  (a>>10);
+               a +=  (a<<3);
+               a ^=  (a>>6);
+               a += ~(a<<11);
+               a ^=  (a>>16);
+               return a;
+       }
+       
+       dtNode* m_nodes;
+       unsigned short* m_first;
+       unsigned short* m_next;
+       const int m_maxNodes;
+       const int m_hashSize;
+       int m_nodeCount;
+};
+
+class dtNodeQueue
+{
+public:
+       dtNodeQueue(int n);
+       ~dtNodeQueue();
+       inline void operator=(dtNodeQueue&) {}
+       
+       inline void clear()
+       {
+               m_size = 0;
+       }
+       
+       inline dtNode* top()
+       {
+               return m_heap[0];
+       }
+       
+       inline dtNode* pop()
+       {
+               dtNode* result = m_heap[0];
+               m_size--;
+               trickleDown(0, m_heap[m_size]);
+               return result;
+       }
+       
+       inline void push(dtNode* node)
+       {
+               m_size++;
+               bubbleUp(m_size-1, node);
+       }
+       
+       inline void modify(dtNode* node)
+       {
+               for (int i = 0; i < m_size; ++i)
+               {
+                       if (m_heap[i] == node)
+                       {
+                               bubbleUp(i, node);
+                               return;
+                       }
+               }
+       }
+       
+       inline bool empty() const { return m_size == 0; }
+       
+       inline int getMemUsed() const
+       {
+               return sizeof(*this) +
+               sizeof(dtNode*)*(m_capacity+1);
+       }
+       
+       
+private:
+       void bubbleUp(int i, dtNode* node);
+       void trickleDown(int i, dtNode* node);
+       
+       dtNode** m_heap;
+       const int m_capacity;
+       int m_size;
+};             
+
+
+#endif // DETOURNODE_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Include/DetourStatNavMesh.h b/extern/recastnavigation/Detour/Include/DetourStatNavMesh.h
new file mode 100644 (file)
index 0000000..5a3e04a
--- /dev/null
@@ -0,0 +1,234 @@
+//
+// Copyright (c) 2009 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 DETOURSTATNAVMESH_H
+#define DETOURSTATNAVMESH_H
+
+// Reference to navigation polygon.
+typedef unsigned short dtStatPolyRef;
+
+// Maximum number of vertices per navigation polygon.
+static const int DT_STAT_VERTS_PER_POLYGON = 6;
+
+// Structure holding the navigation polygon data.
+struct dtStatPoly
+{
+       unsigned short v[DT_STAT_VERTS_PER_POLYGON];    // Indices to vertices of the poly.
+       dtStatPolyRef n[DT_STAT_VERTS_PER_POLYGON];             // Refs to neighbours of the poly.
+       unsigned char nv;                                                               // Number of vertices.
+       unsigned char flags;                                                    // Flags (not used).
+};
+
+struct dtStatPolyDetail
+{
+       unsigned short vbase;   // Offset to detail vertex array.
+       unsigned short nverts;  // Number of vertices in the detail mesh.
+       unsigned short tbase;   // Offset to detail triangle array.
+       unsigned short ntris;   // Number of triangles.
+};
+
+const int DT_STAT_NAVMESH_MAGIC = (('N'<<24) | ('A'<<16) | ('V'<<8) | 'M');
+const int DT_STAT_NAVMESH_VERSION = 3;
+
+struct dtStatBVNode
+{
+       unsigned short bmin[3], bmax[3];
+       int i;
+};
+
+struct dtStatNavMeshHeader
+{
+       int magic;
+       int version;
+       int npolys;
+       int nverts;
+       int nnodes;
+       int ndmeshes;
+       int ndverts;
+       int ndtris;
+       float cs;
+       float bmin[3], bmax[3];
+       dtStatPoly* polys;
+       float* verts;
+       dtStatBVNode* bvtree;
+       dtStatPolyDetail* dmeshes;
+       float* dverts;
+       unsigned char* dtris;
+};
+
+class dtStatNavMesh
+{
+public:
+       
+       dtStatNavMesh();
+       ~dtStatNavMesh();
+
+       // Initializes the navmesh with data.
+       // Params:
+       //      data - (in) Pointer to navmesh data.
+       //      dataSize - (in) size of the navmesh data.
+       //      ownsData - (in) Flag indicating if the navmesh should own and delete the data.
+       bool init(unsigned char* data, int dataSize, bool ownsData);
+
+       // Finds the nearest navigation polygon around the center location.
+       // Params:
+       //      center - (in) The center of the search box.
+       //      extents - (in) The extents of the search box.
+       // Returns: Reference identifier for the polygon, or 0 if no polygons found.
+       dtStatPolyRef findNearestPoly(const float* center, const float* extents);
+
+       // Returns polygons which touch the query box.
+       // Params:
+       //      center - (in) the center of the search box.
+       //      extents - (in) the extents of the search box.
+       //      polys - (out) array holding the search result.
+       //      maxPolys - (in) The max number of polygons the polys array can hold.
+       // Returns: Number of polygons in search result array.
+       int queryPolygons(const float* center, const float* extents,
+                                         dtStatPolyRef* polys, const int maxPolys);
+       
+       // Finds path from start polygon to end polygon.
+       // If target polygon canno be reached through the navigation graph,
+       // the last node on the array is nearest node to the end polygon.
+       // Params:
+       //      startRef - (in) ref to path start polygon.
+       //      endRef - (in) ref to path end polygon.
+       //      path - (out) array holding the search result.
+       //      maxPathSize - (in) The max number of polygons the path array can hold.
+       // Returns: Number of polygons in search result array.
+       int findPath(dtStatPolyRef startRef, dtStatPolyRef endRef,
+                                const float* startPos, const float* endPos,
+                                dtStatPolyRef* path, const int maxPathSize);
+
+       // Finds a straight path from start to end locations within the corridor
+       // described by the path polygons.
+       // Start and end locations will be clamped on the corridor.
+       // Params:
+       //      startPos - (in) Path start location.
+       //      endPos - (in) Path end location.
+       //      path - (in) Array of connected polygons describing the corridor.
+       //      pathSize - (in) Number of polygons in path array.
+       //      straightPath - (out) Points describing the straight path.
+       //      maxStraightPathSize - (in) The max number of points the straight path array can hold.
+       // Returns: Number of points in the path.
+       int findStraightPath(const float* startPos, const float* endPos,
+                                                const dtStatPolyRef* path, const int pathSize,
+                                                float* straightPath, const int maxStraightPathSize);
+
+       // Finds intersection againts walls starting from start pos.
+       // Params:
+       //      startRef - (in) ref to the polygon where the start lies.
+       //      startPos - (in) start position of the query.
+       //      endPos - (in) end position of the query.
+       //      t - (out) hit parameter along the segment, 0 if no hit.
+       //      endRef - (out) ref to the last polygon which was processed.
+       // Returns: Number of polygons in path or 0 if failed.
+       int raycast(dtStatPolyRef startRef, const float* startPos, const float* endPos,
+                                float& t, dtStatPolyRef* path, const int pathSize);
+       
+       // Returns distance to nearest wall from the specified location.
+       // Params:
+       //      centerRef - (in) ref to the polygon where the center lies.
+       //      centerPos - (in) center if the query circle.
+       //      maxRadius - (in) max search radius.
+       //      hitPos - (out) location of the nearest hit.
+       //      hitNormal - (out) normal of the nearest hit.
+       // Returns: Distance to nearest wall from the test location.
+       float findDistanceToWall(dtStatPolyRef centerRef, const float* centerPos, float maxRadius,
+                                                        float* hitPos, float* hitNormal);
+       
+       // Finds polygons found along the navigation graph which touch the specified circle.
+       // Params:
+       //      centerRef - (in) ref to the polygon where the center lies.
+       //      centerPos - (in) center if the query circle
+       //      radius - (in) radius of the query circle
+       //      resultRef - (out, opt) refs to the polygons touched by the circle.
+       //      resultParent - (out, opt) parent of each result polygon.
+       //      resultCost - (out, opt) search cost at each result polygon.
+       //      maxResult - (int) maximum capacity of search results.
+       // Returns: Number of results.
+       int     findPolysAround(dtStatPolyRef centerRef, const float* centerPos, float radius,
+                                               dtStatPolyRef* resultRef, dtStatPolyRef* resultParent, float* resultCost,
+                                               const int maxResult);
+
+       // Returns closest point on navigation polygon.
+       // Params:
+       //      ref - (in) ref to the polygon.
+       //      pos - (in) the point to check.
+       //      closest - (out) closest point.
+       // Returns: true if closest point found.
+       bool closestPointToPoly(dtStatPolyRef ref, const float* pos, float* closest) const;
+
+       // Returns height of the polygon at specified location.
+       // Params:
+       //      ref - (in) ref to the polygon.
+       //      pos - (in) the point where to locate the height.
+       //      height - (out) height at the location.
+       // Returns: true if oer polygon.
+       bool getPolyHeight(dtStatPolyRef ref, const float* pos, float* height) const;
+
+       // Returns pointer to a polygon based on ref.
+       const dtStatPoly* getPolyByRef(dtStatPolyRef ref) const;
+       // Returns polygon index based on ref, or -1 if failed.
+       int getPolyIndexByRef(dtStatPolyRef ref) const;
+       // Returns number of navigation polygons.
+       inline int getPolyCount() const { return m_header ? m_header->npolys : 0; }
+       // Rerturns pointer to specified navigation polygon.
+       inline const dtStatPoly* getPoly(int i) const { return &m_header->polys[i]; }
+       // Returns number of vertices.
+       inline int getVertexCount() const { return m_header ? m_header->nverts : 0; }
+       // Returns pointer to specified vertex.
+       inline const float* getVertex(int i) const { return &m_header->verts[i*3]; }
+       // Returns number of navigation polygons details.
+       inline int getPolyDetailCount() const { return m_header ? m_header->ndmeshes : 0; }
+       // Rerturns pointer to specified navigation polygon detail.
+       const dtStatPolyDetail* getPolyDetail(int i) const { return &m_header->dmeshes[i]; }
+       // Returns pointer to specified vertex.
+       inline const float* getDetailVertex(int i) const { return &m_header->dverts[i*3]; }
+       // Returns pointer to specified vertex.
+       inline const unsigned char* getDetailTri(int i) const { return &m_header->dtris[i*4]; }
+
+       bool isInClosedList(dtStatPolyRef ref) const;
+       
+       int getMemUsed() const;
+
+       inline unsigned char* getData() const { return m_data; }
+       inline int getDataSize() const { return m_dataSize; }
+       inline const dtStatNavMeshHeader* getHeader() const { return m_header; }
+       inline const dtStatBVNode* getBvTreeNodes() const { return m_header ? m_header->bvtree : 0; }
+       inline int getBvTreeNodeCount() const { return m_header ? m_header->nnodes : 0; }
+       
+private:
+
+       // Copies the locations of vertices of a polygon to an array.
+       int getPolyVerts(dtStatPolyRef ref, float* verts) const;
+       // Returns portal points between two polygons.
+       bool getPortalPoints(dtStatPolyRef from, dtStatPolyRef to, float* left, float* right) const;
+       // Returns edge mid point between two polygons.
+       bool getEdgeMidPoint(dtStatPolyRef from, dtStatPolyRef to, float* mid) const;
+
+       unsigned char* m_data;
+       int m_dataSize;
+       
+       dtStatNavMeshHeader* m_header;
+
+       class dtNodePool* m_nodePool;
+       class dtNodeQueue* m_openList;
+};
+
+#endif // DETOURSTATNAVMESH_H
diff --git a/extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h b/extern/recastnavigation/Detour/Include/DetourStatNavMeshBuilder.h
new file mode 100644 (file)
index 0000000..03c79c4
--- /dev/null
@@ -0,0 +1,33 @@
+//
+// Copyright (c) 2009 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 DETOURSTATNAVMESHBUILDER_H
+#define DETOURSTATNAVMESHBUILDER_H
+
+bool dtCreateNavMeshData(const unsigned short* verts, const int nverts,
+                                                const unsigned short* polys, const int npolys, const int nvp,
+                                                const float* bmin, const float* bmax, float cs, float ch,
+                                                const unsigned short* dmeshes, const float* dverts, const int ndverts,
+                                                const unsigned char* dtris, const int ndtris, 
+                                                unsigned char** outData, int* outDataSize);
+
+int createBVTree(const unsigned short* verts, const int nverts,
+                                               const unsigned short* polys, const int npolys, const int nvp,
+                                               float cs, float ch, int nnodes, dtStatBVNode* nodes);
+
+#endif // DETOURSTATNAVMESHBUILDER_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Include/DetourTileNavMesh.h b/extern/recastnavigation/Detour/Include/DetourTileNavMesh.h
new file mode 100644 (file)
index 0000000..305c61e
--- /dev/null
@@ -0,0 +1,315 @@
+//
+// Copyright (c) 2009 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 DETOURTILENAVMESH_H
+#define DETOURTILENAVMESH_H
+
+// Reference to navigation polygon.
+typedef unsigned int dtTilePolyRef;
+
+// The bits used in the poly ref.
+static const int DT_TILE_REF_SALT_BITS = 12;
+static const int DT_TILE_REF_TILE_BITS = 12;
+static const int DT_TILE_REF_POLY_BITS = 8;
+static const int DT_TILE_REF_SALT_MASK = (1<<DT_TILE_REF_SALT_BITS)-1;
+static const int DT_TILE_REF_TILE_MASK = (1<<DT_TILE_REF_TILE_BITS)-1;
+static const int DT_TILE_REF_POLY_MASK = (1<<DT_TILE_REF_POLY_BITS)-1;
+
+// Maximum number of vertices per navigation polygon.
+static const int DT_TILE_VERTS_PER_POLYGON = 6;
+
+static const int DT_MAX_TILES = 1 << DT_TILE_REF_TILE_BITS;
+static const int DT_MAX_POLYGONS = 1 << DT_TILE_REF_POLY_BITS;
+
+static const int DT_TILE_NAVMESH_MAGIC = (('N'<<24) | ('A'<<16) | ('V'<<8) | 'M');
+static const int DT_TILE_NAVMESH_VERSION = 2;
+
+// Structure holding the navigation polygon data.
+struct dtTilePoly
+{
+       unsigned short v[DT_TILE_VERTS_PER_POLYGON];    // Indices to vertices of the poly.
+       unsigned short n[DT_TILE_VERTS_PER_POLYGON];    // Refs to neighbours of the poly.
+       unsigned short links;                                                   // Base index to header 'links' array. 
+       unsigned char nlinks;                                                   // Number of links for 
+       unsigned char nv;                                                               // Number of vertices.
+       unsigned char flags;                                                    // Flags (not used).
+};
+
+struct dtTilePolyDetail
+{
+       unsigned short vbase;   // Offset to detail vertex array.
+       unsigned short nverts;  // Number of vertices in the detail mesh.
+       unsigned short tbase;   // Offset to detail triangle array.
+       unsigned short ntris;   // Number of triangles.
+};
+
+// Stucture holding a link to another polygon.
+struct dtTileLink
+{
+       dtTilePolyRef ref;                      // Neighbour reference.
+       unsigned short p;                       // Index to polygon which owns this link.
+       unsigned char e;                        // Index to polygon edge which owns this link. 
+       unsigned char side;                     // If boundary link, defines on which side the link is.
+       unsigned char bmin, bmax;       // If boundary link, defines the sub edge area.
+};
+
+struct dtTileHeader
+{
+       int magic;                                      // Magic number, used to identify the data.
+       int version;                            // Data version number.
+       int npolys;                                     // Number of polygons in the tile.
+       int nverts;                                     // Number of vertices in the tile.
+       int nlinks;                                     // Number of links in the tile (will be updated when tile is added).
+       int maxlinks;                           // Number of allocated links.
+       int ndmeshes;
+       int ndverts;
+       int ndtris;
+       float bmin[3], bmax[3];         // Bounding box of the tile.
+       dtTilePoly* polys;                      // Pointer to the polygons (will be updated when tile is added).
+       float* verts;                           // Pointer to the vertices (will be updated when tile added).
+       dtTileLink* links;                      // Pointer to the links (will be updated when tile added).
+       dtTilePolyDetail* dmeshes;
+       float* dverts;
+       unsigned char* dtris;
+};
+
+struct dtTile
+{
+       int salt;                               // Counter describing modifications to the tile.
+       int x,y;                                // Grid location of the tile.
+       dtTileHeader* header;   // Pointer to tile header.
+       unsigned char* data;    // Pointer to tile data.
+       int dataSize;                   // Size of the tile data.
+       bool ownsData;                  // Flag indicating of the navmesh should release the data.
+       dtTile* next;                   // Next free tile or, next tile in spatial grid.
+};
+
+// Encodes a tile id.
+inline dtTilePolyRef dtEncodeTileId(unsigned int salt, unsigned int it, unsigned int ip)
+{
+       return (salt << (DT_TILE_REF_POLY_BITS+DT_TILE_REF_TILE_BITS)) | ((it+1) << DT_TILE_REF_POLY_BITS) | ip;
+}
+
+// Decodes a tile id.
+inline void dtDecodeTileId(dtTilePolyRef ref, unsigned int& salt, unsigned int& it, unsigned int& ip)
+{
+       salt = (ref >> (DT_TILE_REF_POLY_BITS+DT_TILE_REF_TILE_BITS)) & DT_TILE_REF_SALT_MASK;
+       it = ((ref >> DT_TILE_REF_POLY_BITS) & DT_TILE_REF_TILE_MASK) - 1;
+       ip = ref & DT_TILE_REF_POLY_MASK;
+}
+
+static const int DT_TILE_LOOKUP_SIZE = DT_MAX_TILES/4;
+
+class dtTiledNavMesh
+{
+public:
+       dtTiledNavMesh();
+       ~dtTiledNavMesh();
+
+       // Initializes the nav mesh.
+       // Params:
+       //  orig - (in) origin of the nav mesh tile space.
+       //  tileSiz - (in) size of a tile.
+       //  portalheight - (in) height of the portal region between tiles.
+       // Returns: True if succeed, else false.
+       bool init(const float* orig, float tileSize, float portalHeight);
+
+       // Adds new tile into the navmesh.
+       // The add will fail if the data is in wrong format,
+       // there is not enough tiles left, or if there is a tile already at the location.
+       // Params:
+       //  x,y - (in) Location of the new tile.
+       //  data - (in) Data of the new tile mesh.
+       //  dataSize - (in) Data size of the new tile mesh.
+       //      ownsData - (in) Flag indicating if the navmesh should own and delete the data.
+       // Returns: True if tile was added, else false. 
+       bool addTileAt(int x, int y, unsigned char* data, int dataSize, bool ownsData);
+       
+       // Removes tile at specified location.
+       // Params:
+       //  x,y - (in) Location of the tile to remove.
+       //  data - (out) Data associated with deleted tile.
+       //  dataSize - (out) Size of the data associated with deleted tile. 
+       // Returns: True if remove suceed, else false.
+       bool removeTileAt(int x, int y, unsigned char** data, int* dataSize);
+
+       // Returns pointer to tile at specified location.
+       // Params:
+       //  x,y - (in) Location of the tile to get.
+       // Returns: pointer to tile if tile exists or 0 tile does not exists.
+       dtTile* getTileAt(int x, int y);
+
+       // Returns pointer to tile in the tile array.
+       // Params:
+       //  i - (in) Index to the tile to retrieve, must be in range [0,DT_MAX_TILES[
+       // Returns: Pointer to specified tile.
+       dtTile* getTile(int i);
+       const dtTile* getTile(int i) const;
+       
+       // Finds the nearest navigation polygon around the center location.
+       // Params:
+       //      center - (in) The center of the search box.
+       //      extents - (in) The extents of the search box.
+       // Returns: Reference identifier for the polygon, or 0 if no polygons found.
+       dtTilePolyRef findNearestPoly(const float* center, const float* extents);
+       
+       // Returns polygons which touch the query box.
+       // Params:
+       //      center - (in) the center of the search box.
+       //      extents - (in) the extents of the search box.
+       //      polys - (out) array holding the search result.
+       //      maxPolys - (in) The max number of polygons the polys array can hold.
+       // Returns: Number of polygons in search result array.
+       int queryPolygons(const float* center, const float* extents,
+                                         dtTilePolyRef* polys, const int maxPolys);
+       
+       // Finds path from start polygon to end polygon.
+       // If target polygon canno be reached through the navigation graph,
+       // the last node on the array is nearest node to the end polygon.
+       // Params:
+       //      startRef - (in) ref to path start polygon.
+       //      endRef - (in) ref to path end polygon.
+       //      path - (out) array holding the search result.
+       //      maxPathSize - (in) The max number of polygons the path array can hold.
+       // Returns: Number of polygons in search result array.
+       int findPath(dtTilePolyRef startRef, dtTilePolyRef endRef,
+                                const float* startPos, const float* endPos,
+                                dtTilePolyRef* path, const int maxPathSize);
+
+       // Finds a straight path from start to end locations within the corridor
+       // described by the path polygons.
+       // Start and end locations will be clamped on the corridor.
+       // Params:
+       //      startPos - (in) Path start location.
+       //      endPos - (in) Path end location.
+       //      path - (in) Array of connected polygons describing the corridor.
+       //      pathSize - (in) Number of polygons in path array.
+       //      straightPath - (out) Points describing the straight path.
+       //      maxStraightPathSize - (in) The max number of points the straight path array can hold.
+       // Returns: Number of points in the path.
+       int findStraightPath(const float* startPos, const float* endPos,
+                                                const dtTilePolyRef* path, const int pathSize,
+                                                float* straightPath, const int maxStraightPathSize);
+
+       // Finds intersection againts walls starting from start pos.
+       // Params:
+       //      startRef - (in) ref to the polygon where the start lies.
+       //      startPos - (in) start position of the query.
+       //      endPos - (in) end position of the query.
+       //      t - (out) hit parameter along the segment, 0 if no hit.
+       //      endRef - (out) ref to the last polygon which was processed.
+       // Returns: Number of polygons in path or 0 if failed.
+       int raycast(dtTilePolyRef startRef, const float* startPos, const float* endPos,
+                               float& t, dtTilePolyRef* path, const int pathSize);
+
+       // Returns distance to nearest wall from the specified location.
+       // Params:
+       //      centerRef - (in) ref to the polygon where the center lies.
+       //      centerPos - (in) center if the query circle.
+       //      maxRadius - (in) max search radius.
+       //      hitPos - (out) location of the nearest hit.
+       //      hitNormal - (out) normal of the nearest hit.
+       // Returns: Distance to nearest wall from the test location.
+       float findDistanceToWall(dtTilePolyRef centerRef, const float* centerPos, float maxRadius,
+                                                        float* hitPos, float* hitNormal);
+
+       // Finds polygons found along the navigation graph which touch the specified circle.
+       // Params:
+       //      centerRef - (in) ref to the polygon where the center lies.
+       //      centerPos - (in) center if the query circle
+       //      radius - (in) radius of the query circle
+       //      resultRef - (out, opt) refs to the polygons touched by the circle.
+       //      resultParent - (out, opt) parent of each result polygon.
+       //      resultCost - (out, opt) search cost at each result polygon.
+       //      maxResult - (int) maximum capacity of search results.
+       // Returns: Number of results.
+       int     findPolysAround(dtTilePolyRef centerRef, const float* centerPos, float radius,
+                                               dtTilePolyRef* resultRef, dtTilePolyRef* resultParent, float* resultCost,
+                                               const int maxResult);
+       
+       // Returns closest point on navigation polygon.
+       // Params:
+       //      ref - (in) ref to the polygon.
+       //      pos - (in) the point to check.
+       //      closest - (out) closest point.
+       // Returns: true if closest point found.
+       bool closestPointToPoly(dtTilePolyRef ref, const float* pos, float* closest) const;
+
+       // Returns height of the polygon at specified location.
+       // Params:
+       //      ref - (in) ref to the polygon.
+       //      pos - (in) the point where to locate the height.
+       //      height - (out) height at the location.
+       // Returns: true if over polygon.
+       bool getPolyHeight(dtTilePolyRef ref, const float* pos, float* height) const;
+       
+       // Returns pointer to a polygon based on ref.
+       const dtTilePoly* getPolyByRef(dtTilePolyRef ref) const;
+
+       // Returns pointer to a polygon vertices based on ref.
+       const float* getPolyVertsByRef(dtTilePolyRef ref) const;
+
+       // Returns pointer to a polygon link based on ref.
+       const dtTileLink* getPolyLinksByRef(dtTilePolyRef ref) const;
+       
+private:
+
+       // Returns base id for the tile.
+       dtTilePolyRef getTileId(dtTile* tile);
+       // Returns neighbour tile based on side. 
+       dtTile* getNeighbourTileAt(int x, int y, int side);
+       // Returns all polygons in neighbour tile based on portal defined by the segment.
+       int findConnectingPolys(const float* va, const float* vb,
+                                                       dtTile* tile, int side,
+                                                       dtTilePolyRef* con, float* conarea, int maxcon);
+       // Builds internal polygons links for a tile.
+       void buildIntLinks(dtTile* tile);
+       // Builds external polygon links for a tile.
+       void buildExtLinks(dtTile* tile, dtTile* target, int side);
+       // Removes external links at specified side.
+       void removeExtLinks(dtTile* tile, int side);
+       // Queries polygons within a tile.
+       int queryTilePolygons(dtTile* tile, const float* qmin, const float* qmax,
+                                                 dtTilePolyRef* polys, const int maxPolys);
+                                                 
+       float getCost(dtTilePolyRef prev, dtTilePolyRef from, dtTilePolyRef to) const;
+       float getFirstCost(const float* pos, dtTilePolyRef from, dtTilePolyRef to) const;
+       float getLastCost(dtTilePolyRef from, dtTilePolyRef to, const float* pos) const;
+       float getHeuristic(const float* from, const float* to) const;
+       
+       // Returns portal points between two polygons.
+       bool getPortalPoints(dtTilePolyRef from, dtTilePolyRef to, float* left, float* right) const;
+       // Returns edge mid point between two polygons.
+       bool getEdgeMidPoint(dtTilePolyRef from, dtTilePolyRef to, float* mid) const;
+
+       float m_orig[3];
+       float m_tileSize;
+       float m_portalHeight;
+
+       dtTile* m_posLookup[DT_TILE_LOOKUP_SIZE];
+       dtTile* m_nextFree;
+       dtTile m_tiles[DT_MAX_TILES];
+       
+       dtTileLink* m_tmpLinks;
+       int m_ntmpLinks;
+
+       class dtNodePool* m_nodePool;
+       class dtNodeQueue* m_openList;
+};
+
+#endif // DETOURTILENAVMESH_H
diff --git a/extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h b/extern/recastnavigation/Detour/Include/DetourTileNavMeshBuilder.h
new file mode 100644 (file)
index 0000000..643dec1
--- /dev/null
@@ -0,0 +1,29 @@
+//
+// Copyright (c) 2009 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 DETOURTILEDNAVMESHBUILDER_H
+#define DETOURTILEDNAVMESHBUILDER_H
+
+bool dtCreateNavMeshTileData(const unsigned short* verts, const int nverts,
+                                                        const unsigned short* polys, const int npolys, const int nvp,
+                                                        const unsigned short* dmeshes, const float* dverts, const int ndverts,
+                                                        const unsigned char* dtris, const int ndtris, 
+                                                        const float* bmin, const float* bmax, float cs, float ch, int tileSize, int walkableClimb,
+                                                        unsigned char** outData, int* outDataSize);
+
+#endif // DETOURTILEDNAVMESHBUILDER_H
\ No newline at end of file
diff --git a/extern/recastnavigation/Detour/Source/DetourCommon.cpp b/extern/recastnavigation/Detour/Source/DetourCommon.cpp
new file mode 100644 (file)
index 0000000..e55ce5e
--- /dev/null
@@ -0,0 +1,244 @@
+//
+// Copyright (c) 2009 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 <math.h>
+#include "DetourCommon.h"
+
+void closestPtPointTriangle(float* closest, const float* p,
+                                                       const float* a, const float* b, const float* c)
+{
+       // Check if P in vertex region outside A
+       float ab[3], ac[3], ap[3];
+       vsub(ab, b, a);
+       vsub(ac, c, a);
+       vsub(ap, p, a);
+       float d1 = vdot(ab, ap);
+       float d2 = vdot(ac, ap);
+       if (d1 <= 0.0f && d2 <= 0.0f)
+       {
+               // barycentric coordinates (1,0,0)
+               vcopy(closest, a);
+               return;
+       }
+       
+       // Check if P in vertex region outside B
+       float bp[3];
+       vsub(bp, p, b);
+       float d3 = vdot(ab, bp);
+       float d4 = vdot(ac, bp);
+       if (d3 >= 0.0f && d4 <= d3)
+       {
+               // barycentric coordinates (0,1,0)
+               vcopy(closest, b);
+               return;
+       }
+       
+       // Check if P in edge region of AB, if so return projection of P onto AB
+       float vc = d1*d4 - d3*d2;
+       if (vc <= 0.0f && d1 >= 0.0f && d3 <= 0.0f)
+       {
+               // barycentric coordinates (1-v,v,0)
+               float v = d1 / (d1 - d3);
+               closest[0] = a[0] + v * ab[0];
+               closest[1] = a[1] + v * ab[1];
+               closest[2] = a[2] + v * ab[2];
+               return;
+       }
+       
+       // Check if P in vertex region outside C
+       float cp[3];
+       vsub(cp, p, c);
+       float d5 = vdot(ab, cp);
+       float d6 = vdot(ac, cp);
+       if (d6 >= 0.0f && d5 <= d6)
+       {
+               // barycentric coordinates (0,0,1)
+               vcopy(closest, c);
+               return;
+       }
+       
+       // Check if P in edge region of AC, if so return projection of P onto AC
+       float vb = d5*d2 - d1*d6;
+       if (vb <= 0.0f && d2 >= 0.0f && d6 <= 0.0f)
+       {
+               // barycentric coordinates (1-w,0,w)
+               float w = d2 / (d2 - d6);
+               closest[0] = a[0] + w * ac[0];
+               closest[1] = a[1] + w * ac[1];
+               closest[2] = a[2] + w * ac[2];
+               return;
+       }
+       
+       // Check if P in edge region of BC, if so return projection of P onto BC
+       float va = d3*d6 - d5*d4;
+       if (va <= 0.0f && (d4 - d3) >= 0.0f && (d5 - d6) >= 0.0f)
+       {
+               // barycentric coordinates (0,1-w,w)
+               float w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
+               closest[0] = b[0] + w * (c[0] - b[0]);
+               closest[1] = b[1] + w * (c[1] - b[1]);
+               closest[2] = b[2] + w * (c[2] - b[2]);
+               return;
+       }
+       
+       // P inside face region. Compute Q through its barycentric coordinates (u,v,w)
+       float denom = 1.0f / (va + vb + vc);
+       float v = vb * denom;
+       float w = vc * denom;
+       closest[0] = a[0] + ab[0] * v + ac[0] * w;
+       closest[1] = a[1] + ab[1] * v + ac[1] * w;
+       closest[2] = a[2] + ab[2] * v + ac[2] * w;
+}
+
+bool intersectSegmentPoly2D(const float* p0, const float* p1,
+                                                       const float* verts, int nverts,
+                                                       float& tmin, float& tmax,
+                                                       int& segMin, int& segMax)
+{
+       static const float EPS = 0.00000001f;
+       
+       tmin = 0;
+       tmax = 1;
+       segMin = -1;
+       segMax = -1;
+       
+       float dir[3];
+       vsub(dir, p1, p0);
+       
+       for (int i = 0, j = nverts-1; i < nverts; j=i++)
+       {
+               float edge[3], diff[3];
+               vsub(edge, &verts[i*3], &verts[j*3]);
+               vsub(diff, p0, &verts[j*3]);
+               float n = vperp2D(edge, diff);
+               float d = -vperp2D(edge, dir);
+               if (fabs(d) < EPS)
+               {
+                       // S is nearly parallel to this edge
+                       if (n < 0)
+                               return false;
+                       else
+                               continue;
+               }
+               float t = n / d;
+               if (d < 0)
+               {
+                       // segment S is entering across this edge
+                       if (t > tmin)
+                       {
+                               tmin = t;
+                               segMin = j;
+                               // S enters after leaving polygon
+                               if (tmin > tmax)
+                                       return false;
+                       }
+               }
+               else
+               {
+                       // segment S is leaving across this edge
+                       if (t < tmax)
+                       {
+                               tmax = t;
+                               segMax = j;
+                               // S leaves before entering polygon
+                               if (tmax < tmin)
+                                       return false;
+                       }
+               }
+       }
+       
+       return true;
+}
+
+float distancePtSegSqr2D(const float* pt, const float* p, const float* q, float& t)
+{
+       float pqx = q[0] - p[0];
+       float pqz = q[2] - p[2];
+       float dx = pt[0] - p[0];
+       float dz = pt[2] - p[2];
+       float d = pqx*pqx + pqz*pqz;
+       t = pqx*dx + pqz*dz;
+       if (d > 0)
+               t /= d;
+       if (t < 0)
+               t = 0;
+       else if (t > 1)
+               t = 1;
+       
+       dx = p[0] + t*pqx - pt[0];
+       dz = p[2] + t*pqz - pt[2];
+       
+       return dx*dx + dz*dz;
+}
+
+void calcPolyCenter(float* tc, const unsigned short* idx, int nidx, const float* verts)
+{
+       tc[0] = 0.0f;
+       tc[1] = 0.0f;
+       tc[2] = 0.0f;
+       for (int j = 0; j < nidx; ++j)
+       {
+               const float* v = &verts[idx[j]*3];
+               tc[0] += v[0];
+               tc[1] += v[1];
+               tc[2] += v[2];
+       }
+       const float s = 1.0f / nidx;
+       tc[0] *= s;
+       tc[1] *= s;
+       tc[2] *= s;
+}
+
+inline float vdot2(const float* a, const float* b)
+{
+       return a[0]*b[0] + a[2]*b[2];
+}
+
+#include <stdio.h>
+
+bool closestHeightPointTriangle(const float* p, const float* a, const float* b, const float* c, float& h)
+{
+       float v0[3], v1[3], v2[3];
+       vsub(v0, c,a);
+       vsub(v1, b,a);
+       vsub(v2, p,a);
+       
+       const float dot00 = vdot2(v0, v0);
+       const float dot01 = vdot2(v0, v1);
+       const float dot02 = vdot2(v0, v2);
+       const float dot11 = vdot2(v1, v1);
+       const float dot12 = vdot2(v1, v2);
+       
+       // Compute barycentric coordinates
+       float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
+       float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
+       float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
+
+       // The (sloppy) epsilon is needed to allow to get height of points which
+       // are interpolated along the edges of the triangles.
+       static const float EPS = 1e-4f;
+       
+       // If point lies inside the triangle, return interpolated ycoord.
+       if (u >= -EPS && v >= -EPS && (u+v) <= 1+EPS)
+       {
+               h = a[1] + v0[1]*u + v1[1]*v;
+               return true;
+       }
+       
+       return false;
+}
diff --git a/extern/recastnavigation/Detour/Source/DetourNode.cpp b/extern/recastnavigation/Detour/Source/DetourNode.cpp
new file mode 100644 (file)
index 0000000..1a2305f
--- /dev/null
@@ -0,0 +1,140 @@
+//
+// Copyright (c) 2009 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 "DetourNode.h"
+#include <string.h>
+
+//////////////////////////////////////////////////////////////////////////////////////////
+dtNodePool::dtNodePool(int maxNodes, int hashSize) :
+
+       m_nodes(0),
+       m_first(0),
+       m_next(0),
+       m_maxNodes(maxNodes),
+       m_hashSize(hashSize),
+       m_nodeCount(0)
+{
+       m_nodes = new dtNode[m_maxNodes];
+       m_next = new unsigned short[m_maxNodes];
+       m_first = new unsigned short[hashSize];
+       memset(m_first, 0xff, sizeof(unsigned short)*m_hashSize);
+       memset(m_next, 0xff, sizeof(unsigned short)*m_maxNodes);
+}
+
+dtNodePool::~dtNodePool()
+{
+       delete [] m_nodes;
+       delete [] m_next;
+       delete [] m_first;
+}
+
+void dtNodePool::clear()
+{
+       memset(m_first, 0xff, sizeof(unsigned short)*m_hashSize);
+       m_nodeCount = 0;
+}
+
+const dtNode* dtNodePool::findNode(unsigned int id) const
+{
+       unsigned int bucket = hashint(id) & (m_hashSize-1);
+       unsigned short i = m_first[bucket];
+       while (i != 0xffff)
+       {
+               if (m_nodes[i].id == id)
+                       return &m_nodes[i];
+               i = m_next[i];
+       }
+       return 0;
+}
+
+dtNode* dtNodePool::getNode(unsigned int id)
+{
+       unsigned int bucket = hashint(id) & (m_hashSize-1);
+       unsigned short i = m_first[bucket];
+       dtNode* node = 0;
+       while (i != 0xffff)
+       {
+               if (m_nodes[i].id == id)
+                       return &m_nodes[i];
+               i = m_next[i];
+       }
+       
+       if (m_nodeCount >= m_maxNodes)
+               return 0;
+       
+       i = (unsigned short)m_nodeCount;
+       m_nodeCount++;
+       
+       // Init node
+       node = &m_nodes[i];
+       node->pidx = 0;
+       node->cost = 0;
+       node->total = 0;
+       node->id = id;
+       node->flags = 0;
+       
+       m_next[i] = m_first[bucket];
+       m_first[bucket] = i;
+       
+       return node;
+}
+
+
+//////////////////////////////////////////////////////////////////////////////////////////
+dtNodeQueue::dtNodeQueue(int n) :
+       m_heap(0),
+       m_capacity(n),
+       m_size(0)
+{
+       m_heap = new dtNode*[m_capacity+1];
+}
+
+dtNodeQueue::~dtNodeQueue()
+{
+       delete [] m_heap;
+}
+
+void dtNodeQueue::bubbleUp(int i, dtNode* node)
+{
+       int parent = (i-1)/2;
+       // note: (index > 0) means there is a parent
+       while ((i > 0) && (m_heap[parent]->total > node->total))
+       {
+               m_heap[i] = m_heap[parent];
+               i = parent;
+               parent = (i-1)/2;
+       }
+       m_heap[i] = node;
+}
+
+void dtNodeQueue::trickleDown(int i, dtNode* node)
+{
+       int child = (i*2)+1;
+       while (child < m_size)
+       {
+               if (((child+1) < m_size) && 
+                       (m_heap[child]->total > m_heap[child+1]->total))
+               {
+                       child++;
+               }
+               m_heap[i] = m_heap[child];
+               i = child;
+               child = (i*2)+1;
+       }
+       bubbleUp(i, node);
+}
diff --git a/extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp b/extern/recastnavigation/Detour/Source/DetourStatNavMesh.cpp
new file mode 100644 (file)
index 0000000..bf59cd8
--- /dev/null
@@ -0,0 +1,876 @@
+//
+// Copyright (c) 2009 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 <math.h>
+#include <float.h>
+#include <string.h>
+#include <stdio.h>
+#include "DetourStatNavMesh.h"
+#include "DetourNode.h"
+#include "DetourCommon.h"
+
+
+//////////////////////////////////////////////////////////////////////////////////////////
+dtStatNavMesh::dtStatNavMesh() :
+       m_data(0),
+       m_dataSize(0),
+       m_header(0),
+       m_nodePool(0),
+       m_openList(0)
+{
+}
+
+dtStatNavMesh::~dtStatNavMesh()
+{
+       delete m_nodePool;
+       delete m_openList;
+       if (m_data)
+               delete [] m_data;
+}
+
+bool dtStatNavMesh::init(unsigned char* data, int dataSize, bool ownsData)
+{
+       dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)data;
+       
+       if (header->magic != DT_STAT_NAVMESH_MAGIC)
+               return false;
+       if (header->version != DT_STAT_NAVMESH_VERSION)
+               return false;
+
+       const int headerSize = sizeof(dtStatNavMeshHeader);
+       const int vertsSize = sizeof(float)*3*header->nverts;
+       const int polysSize = sizeof(dtStatPoly)*header->npolys;
+       const int nodesSize = sizeof(dtStatBVNode)*header->npolys*2;
+       const int detailMeshesSize = sizeof(dtStatPolyDetail)*header->ndmeshes;
+       const int detailVertsSize = sizeof(float)*3*header->ndverts;
+       const int detailTrisSize = sizeof(unsigned char)*4*header->ndtris;
+       
+
+       unsigned char* d = data + headerSize;
+       header->verts = (float*)d; d += vertsSize;
+       header->polys = (dtStatPoly*)d; d += polysSize;
+       header->bvtree = (dtStatBVNode*)d; d += nodesSize;
+       header->dmeshes = (dtStatPolyDetail*)d; d += detailMeshesSize;
+       header->dverts = (float*)d; d += detailVertsSize;
+       header->dtris = (unsigned char*)d; d += detailTrisSize;
+       
+       m_nodePool = new dtNodePool(2048, 256);
+       if (!m_nodePool)
+               return false;
+               
+       m_openList = new dtNodeQueue(2048);
+       if (!m_openList)
+               return false;
+       
+       if (ownsData)
+       {
+               m_data = data;
+               m_dataSize = dataSize;
+       }
+
+       m_header = header;
+
+       return true;
+}
+
+const dtStatPoly* dtStatNavMesh::getPolyByRef(dtStatPolyRef ref) const
+{
+       if (!m_header || ref == 0 || (int)ref > m_header->npolys) return 0;
+       return &m_header->polys[ref-1];
+}
+
+int dtStatNavMesh::getPolyIndexByRef(dtStatPolyRef ref) const
+{
+       if (!m_header || ref == 0 || (int)ref > m_header->npolys) return -1;
+       return (int)ref-1;
+}
+
+int dtStatNavMesh::findPath(dtStatPolyRef startRef, dtStatPolyRef endRef,
+                                                       const float* startPos, const float* endPos,
+                                                       dtStatPolyRef* path, const int maxPathSize)
+{
+       if (!m_header) return 0;
+       
+       if (!startRef || !endRef)
+               return 0;
+
+       if (!maxPathSize)
+               return 0;
+
+       if (startRef == endRef)
+       {
+               path[0] = startRef;
+               return 1;
+       }
+
+       m_nodePool->clear();
+       m_openList->clear();
+
+       static const float H_SCALE = 1.1f;      // Heuristic scale.
+       
+       dtNode* startNode = m_nodePool->getNode(startRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = vdist(startPos, endPos) * H_SCALE;
+       startNode->id = startRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+
+       dtNode* lastBestNode = startNode;
+       float lastBestNodeCost = startNode->total;
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+       
+               if (bestNode->id == endRef)
+               {
+                       lastBestNode = bestNode;
+                       break;
+               }
+
+               const dtStatPoly* poly = getPoly(bestNode->id-1);
+               for (int i = 0; i < (int)poly->nv; ++i)
+               {
+                       dtStatPolyRef neighbour = poly->n[i];
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               // Calculate cost.
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, startPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.cost = parent->cost + vdist(p0,p1);
+                               // Special case for last node.
+                               if (newNode.id == endRef)
+                                       newNode.cost += vdist(p1, endPos);
+                               
+                               // Heuristic
+                               const float h = vdist(p1,endPos)*H_SCALE;
+                               newNode.total = newNode.cost + h;
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+                                               
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= ~DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->cost = newNode.cost;
+                                       actualNode->total = newNode.total;
+
+                                       if (h < lastBestNodeCost)
+                                       {
+                                               lastBestNodeCost = h;
+                                               lastBestNode = actualNode;
+                                       }
+
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               actualNode->flags |= DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+               bestNode->flags |= DT_NODE_CLOSED;
+       }
+
+       // Reverse the path.
+       dtNode* prev = 0;
+       dtNode* node = lastBestNode;
+       do
+       {
+               dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
+               node->pidx = m_nodePool->getNodeIdx(prev);
+               prev = node;
+               node = next;
+       }
+       while (node);
+       
+       // Store path
+       node = prev;
+       int n = 0;
+       do
+       {
+               path[n++] = node->id;
+               node = m_nodePool->getNodeAtIdx(node->pidx);
+       }
+       while (node && n < maxPathSize);
+
+       return n;
+}
+
+bool dtStatNavMesh::closestPointToPoly(dtStatPolyRef ref, const float* pos, float* closest) const
+{
+       int idx = getPolyIndexByRef(ref);
+       if (idx == -1)
+               return false;
+
+       float closestDistSqr = FLT_MAX;
+       const dtStatPoly* p = getPoly(idx);
+       const dtStatPolyDetail* pd = getPolyDetail(idx);
+
+       for (int j = 0; j < pd->ntris; ++j)
+       {
+               const unsigned char* t = getDetailTri(pd->tbase+j);
+               const float* v[3];
+               for (int k = 0; k < 3; ++k)
+               {
+                       if (t[k] < p->nv)
+                               v[k] = getVertex(p->v[t[k]]);
+                       else
+                               v[k] = getDetailVertex(pd->vbase+(t[k]-p->nv));
+               }
+               float pt[3];
+               closestPtPointTriangle(pt, pos, v[0], v[1], v[2]);
+               float d = vdistSqr(pos, pt);
+               if (d < closestDistSqr)
+               {
+                       vcopy(closest, pt);
+                       closestDistSqr = d;
+               }
+       }
+       
+       return true;
+}
+
+bool dtStatNavMesh::getPolyHeight(dtStatPolyRef ref, const float* pos, float* height) const
+{
+       int idx = getPolyIndexByRef(ref);
+       if (idx == -1)
+               return false;
+       
+       const dtStatPoly* p = getPoly(idx);
+       const dtStatPolyDetail* pd = getPolyDetail(idx);
+
+       for (int i = 0; i < pd->ntris; ++i)
+       {
+               const unsigned char* t = getDetailTri(pd->tbase+i);
+               const float* v[3];
+               for (int j = 0; j < 3; ++j)
+               {
+                       if (t[j] < p->nv)
+                               v[j] = getVertex(p->v[t[j]]);
+                       else
+                               v[j] = getDetailVertex(pd->vbase+(t[j]-p->nv));
+               }
+               float h;
+               if (closestHeightPointTriangle(pos, v[0], v[1], v[2], h))
+               {
+                       if (height)
+                               *height = h;
+                       return true;
+               }
+       }
+       
+       return false;
+}
+
+int dtStatNavMesh::findStraightPath(const float* startPos, const float* endPos,
+                                                                       const dtStatPolyRef* path, const int pathSize,
+                                                                       float* straightPath, const int maxStraightPathSize)
+{
+       if (!m_header) return 0;
+       
+       if (!maxStraightPathSize)
+               return 0;
+
+       if (!path[0])
+               return 0;
+
+       int straightPathSize = 0;
+       
+       float closestStartPos[3];
+       if (!closestPointToPoly(path[0], startPos, closestStartPos))
+               return 0;
+
+       // Add start point.
+       vcopy(&straightPath[straightPathSize*3], closestStartPos);
+       straightPathSize++;
+       if (straightPathSize >= maxStraightPathSize)
+               return straightPathSize;
+
+       float closestEndPos[3];
+       if (!closestPointToPoly(path[pathSize-1], endPos, closestEndPos))
+               return 0;
+
+       float portalApex[3], portalLeft[3], portalRight[3];
+
+       if (pathSize > 1)
+       {
+               vcopy(portalApex, closestStartPos);
+               vcopy(portalLeft, portalApex);
+               vcopy(portalRight, portalApex);
+               int apexIndex = 0;
+               int leftIndex = 0;
+               int rightIndex = 0;
+
+               for (int i = 0; i < pathSize; ++i)
+               {
+                       float left[3], right[3];
+                       if (i < pathSize-1)
+                       {
+                               // Next portal.
+                               getPortalPoints(path[i], path[i+1], left, right);
+                       }
+                       else
+                       {
+                               // End of the path.
+                               vcopy(left, closestEndPos);
+                               vcopy(right, closestEndPos);
+                       }
+
+                       // Right vertex.
+                       if (vequal(portalApex, portalRight))
+                       {
+                               vcopy(portalRight, right);
+                               rightIndex = i;
+                       }
+                       else
+                       {
+                               if (triArea2D(portalApex, portalRight, right) <= 0.0f)
+                               {
+                                       if (triArea2D(portalApex, portalLeft, right) > 0.0f)
+                                       {
+                                               vcopy(portalRight, right);
+                                               rightIndex = i;
+                                       }
+                                       else
+                                       {
+                                               vcopy(portalApex, portalLeft);
+                                               apexIndex = leftIndex;
+
+                                               if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex))
+                                               {
+                                                       vcopy(&straightPath[straightPathSize*3], portalApex);
+                                                       straightPathSize++;
+                                                       if (straightPathSize >= maxStraightPathSize)
+                                                               return straightPathSize;
+                                               }
+
+                                               vcopy(portalLeft, portalApex);
+                                               vcopy(portalRight, portalApex);
+                                               leftIndex = apexIndex;
+                                               rightIndex = apexIndex;
+
+                                               // Restart
+                                               i = apexIndex;
+
+                                               continue;
+                                       }
+                               }
+                       }
+
+                       // Left vertex.
+                       if (vequal(portalApex, portalLeft))
+                       {
+                               vcopy(portalLeft, left);
+                               leftIndex = i;
+                       }
+                       else
+                       {
+                               if (triArea2D(portalApex, portalLeft, left) >= 0.0f)
+                               {
+                                       if (triArea2D(portalApex, portalRight, left) < 0.0f)
+                                       {
+                                               vcopy(portalLeft, left);
+                                               leftIndex = i;
+                                       }
+                                       else
+                                       {
+                                               vcopy(portalApex, portalRight);
+                                               apexIndex = rightIndex;
+
+                                               if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex))
+                                               {
+                                                       vcopy(&straightPath[straightPathSize*3], portalApex);
+                                                       straightPathSize++;
+                                                       if (straightPathSize >= maxStraightPathSize)
+                                                               return straightPathSize;
+                                               }
+
+                                               vcopy(portalLeft, portalApex);
+                                               vcopy(portalRight, portalApex);
+                                               leftIndex = apexIndex;
+                                               rightIndex = apexIndex;
+
+                                               // Restart
+                                               i = apexIndex;
+
+                                               continue;
+                                       }
+                               }
+                       }
+               }
+       }
+
+       // Add end point.
+       vcopy(&straightPath[straightPathSize*3], closestEndPos);
+       straightPathSize++;
+       
+       return straightPathSize;
+}
+
+int dtStatNavMesh::getPolyVerts(dtStatPolyRef ref, float* verts) const
+{
+       if (!m_header) return 0;
+       const dtStatPoly* poly = getPolyByRef(ref);
+       if (!poly) return 0;
+       float* v = verts;
+       for (int i = 0; i < (int)poly->nv; ++i)
+       {
+               const float* cv = &m_header->verts[poly->v[i]*3];
+               *v++ = cv[0];
+               *v++ = cv[1];
+               *v++ = cv[2];
+       }
+       return (int)poly->nv;
+}
+
+int dtStatNavMesh::raycast(dtStatPolyRef centerRef, const float* startPos, const float* endPos,
+                                         float& t, dtStatPolyRef* path, const int pathSize)
+{
+       if (!m_header) return 0;
+       if (!centerRef) return 0;
+       
+       dtStatPolyRef prevRef = centerRef;
+       dtStatPolyRef curRef = centerRef;
+       t = 0;
+
+       float verts[DT_STAT_VERTS_PER_POLYGON*3];
+       int n = 0;
+
+       while (curRef)
+       {
+               // Cast ray against current polygon.
+               int nv = getPolyVerts(curRef, verts);
+               if (nv < 3)
+               {
+                       // Hit bad polygon, report hit.
+                       return n;
+               }
+               
+               float tmin, tmax;
+               int segMin, segMax;
+               if (!intersectSegmentPoly2D(startPos, endPos, verts, nv, tmin, tmax, segMin, segMax))
+               {
+                       // Could not a polygon, keep the old t and report hit.
+                       return n;
+               }
+               // Keep track of furthest t so far.
+               if (tmax > t)
+                       t = tmax;
+
+               if (n < pathSize)
+                       path[n++] = curRef;
+
+               // Check the neighbour of this polygon.
+               const dtStatPoly* poly = getPolyByRef(curRef);
+               dtStatPolyRef nextRef = poly->n[segMax];
+               if (!nextRef)
+               {
+                       // No neighbour, we hit a wall.
+                       return n;
+               }
+               
+               // No hit, advance to neighbour polygon.
+               prevRef = curRef;
+               curRef = nextRef;
+       }
+       
+       return n;
+}
+
+
+float dtStatNavMesh::findDistanceToWall(dtStatPolyRef centerRef, const float* centerPos, float maxRadius,
+                                                                 float* hitPos, float* hitNormal)
+{
+       if (!m_header) return 0;
+       if (!centerRef) return 0;
+       
+       m_nodePool->clear();
+       m_openList->clear();
+       
+       dtNode* startNode = m_nodePool->getNode(centerRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = 0;
+       startNode->id = centerRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+       
+       float radiusSqr = sqr(maxRadius);
+       
+       hitNormal[0] = 1;
+       hitNormal[1] = 0;
+       hitNormal[2] = 0;
+       
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+               const dtStatPoly* poly = getPoly(bestNode->id-1);
+               
+               // Hit test walls.
+               for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++)
+               {
+                       // Skip non-solid edges.
+                       if (poly->n[j]) continue;
+                       
+                       // Calc distance to the edge.
+                       const float* vj = getVertex(poly->v[j]);
+                       const float* vi = getVertex(poly->v[i]);
+                       float tseg;
+                       float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg);
+
+                       // Edge is too far, skip.
+                       if (distSqr > radiusSqr)
+                               continue;
+                               
+                       // Hit wall, update radius.
+                       radiusSqr = distSqr;
+                       // Calculate hit pos.
+                       hitPos[0] = vj[0] + (vi[0] - vj[0])*tseg;
+                       hitPos[1] = vj[1] + (vi[1] - vj[1])*tseg;
+                       hitPos[2] = vj[2] + (vi[2] - vj[2])*tseg;
+               }
+
+               // Check to see if teh circle expands to one of the neighbours and expand.
+               for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++)
+               {
+                       // Skip solid edges.
+                       if (!poly->n[j]) continue;
+                       
+                       // Expand to neighbour if not visited yet.
+                       dtStatPolyRef neighbour = poly->n[j];
+                       
+                       // Skip parent node.
+                       if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                               continue;
+                       
+                       // Calc distance to the edge.
+                       const float* vj = getVertex(poly->v[j]);
+                       const float* vi = getVertex(poly->v[i]);
+                       float tseg;
+                       float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg);
+                       
+                       // Edge is too far, skip.
+                       if (distSqr > radiusSqr)
+                               continue;
+                       
+                       dtNode* parent = bestNode;
+                       dtNode newNode;
+                       newNode.pidx = m_nodePool->getNodeIdx(parent);
+                       newNode.id = neighbour;
+                       
+                       // Cost
+                       float p0[3], p1[3];
+                       if (!parent->pidx)
+                               vcopy(p0, centerPos);
+                       else
+                               getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                       getEdgeMidPoint(parent->id, newNode.id, p1);
+                       newNode.total = parent->total + vdist(p0,p1);
+                       
+                       dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                       if (!actualNode)
+                               continue;
+
+                       if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                               !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                       {
+                               actualNode->flags &= ~DT_NODE_CLOSED;
+                               actualNode->pidx = newNode.pidx;
+                               actualNode->total = newNode.total;
+                               
+                               if (actualNode->flags & DT_NODE_OPEN)
+                               {
+                                       m_openList->modify(actualNode);
+                               }
+                               else
+                               {
+                                       actualNode->flags |= DT_NODE_OPEN;
+                                       m_openList->push(actualNode);
+                               }
+                       }
+               }
+               bestNode->flags |= DT_NODE_CLOSED;
+       }
+
+       // Calc hit normal.
+       vsub(hitNormal, centerPos, hitPos);
+       vnormalize(hitNormal);
+       
+       return sqrtf(radiusSqr);
+}
+
+int dtStatNavMesh::findPolysAround(dtStatPolyRef centerRef, const float* centerPos, float radius,
+                                                                  dtStatPolyRef* resultRef, dtStatPolyRef* resultParent, float* resultCost,
+                                                                  const int maxResult)
+{
+       if (!m_header) return 0;
+       if (!centerRef) return 0;
+
+       m_nodePool->clear();
+       m_openList->clear();
+
+       dtNode* startNode = m_nodePool->getNode(centerRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = 0;
+       startNode->id = centerRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+
+       int n = 0;
+       if (n < maxResult)
+       {
+               if (resultRef)
+                       resultRef[n] = startNode->id;
+               if (resultParent)
+                       resultParent[n] = 0;
+               if (resultCost)
+                       resultCost[n] = 0;
+               ++n;
+       }
+
+       const float radiusSqr = sqr(radius);
+
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+               const dtStatPoly* poly = getPoly(bestNode->id-1);
+               for (unsigned i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j=i++)
+               {
+                       dtStatPolyRef neighbour = poly->n[j];
+
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+                                       
+                               // Calc distance to the edge.
+                               const float* vj = getVertex(poly->v[j]);
+                               const float* vi = getVertex(poly->v[i]);
+                               float tseg;
+                               float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg);
+                               
+                               // If the circle is not touching the next polygon, skip it.
+                               if (distSqr > radiusSqr)
+                                       continue;
+                               
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               // Cost
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, centerPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.total = parent->total + vdist(p0,p1);
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= ~DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->total = newNode.total;
+
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               if (n < maxResult)
+                                               {
+                                                       if (resultRef)
+                                                               resultRef[n] = actualNode->id;
+                                                       if (resultParent)
+                                                               resultParent[n] = m_nodePool->getNodeAtIdx(actualNode->pidx)->id;
+                                                       if (resultCost)
+                                                               resultCost[n] = actualNode->total;
+                                                       ++n;
+                                               }
+                                               actualNode->flags |= DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+               bestNode->flags |= DT_NODE_CLOSED;
+               
+       }
+
+       return n;
+}
+
+// Returns polygons which are withing certain radius from the query location.
+int dtStatNavMesh::queryPolygons(const float* center, const float* extents,
+                                                                dtStatPolyRef* polys, const int maxIds)
+{
+       if (!m_header) return 0;
+       
+       const dtStatBVNode* node = &m_header->bvtree[0];
+       const dtStatBVNode* end = &m_header->bvtree[m_header->nnodes];
+
+       // Calculate quantized box
+       const float ics = 1.0f / m_header->cs;
+       unsigned short bmin[3], bmax[3];
+       // Clamp query box to world box.
+       float minx = clamp(center[0] - extents[0], m_header->bmin[0], m_header->bmax[0]) - m_header->bmin[0];
+       float miny = clamp(center[1] - extents[1], m_header->bmin[1], m_header->bmax[1]) - m_header->bmin[1];
+       float minz = clamp(center[2] - extents[2], m_header->bmin[2], m_header->bmax[2]) - m_header->bmin[2];
+       float maxx = clamp(center[0] + extents[0], m_header->bmin[0], m_header->bmax[0]) - m_header->bmin[0];
+       float maxy = clamp(center[1] + extents[1], m_header->bmin[1], m_header->bmax[1]) - m_header->bmin[1];
+       float maxz = clamp(center[2] + extents[2], m_header->bmin[2], m_header->bmax[2]) - m_header->bmin[2];
+       // Quantize
+       bmin[0] = (unsigned short)(ics * minx) & 0xfffe;
+       bmin[1] = (unsigned short)(ics * miny) & 0xfffe;
+       bmin[2] = (unsigned short)(ics * minz) & 0xfffe;
+       bmax[0] = (unsigned short)(ics * maxx + 1) | 1;
+       bmax[1] = (unsigned short)(ics * maxy + 1) | 1;
+       bmax[2] = (unsigned short)(ics * maxz + 1) | 1;
+       
+       // Traverse tree
+       int n = 0;
+       while (node < end)
+       {
+               bool overlap = checkOverlapBox(bmin, bmax, node->bmin, node->bmax);
+               bool isLeafNode = node->i >= 0;
+               
+               if (isLeafNode && overlap)
+               {
+                       if (n < maxIds)
+                       {
+                               polys[n] = (dtStatPolyRef)node->i;
+                               n++;
+                       }
+               }
+               
+               if (overlap || isLeafNode)
+                       node++;
+               else
+               {
+                       const int escapeIndex = -node->i;
+                       node += escapeIndex;
+               }
+       }
+       
+       return n;
+}
+
+dtStatPolyRef dtStatNavMesh::findNearestPoly(const float* center, const float* extents)
+{
+       if (!m_header) return 0;
+       
+       // Get nearby polygons from proximity grid.
+       dtStatPolyRef polys[128];
+       int npolys = queryPolygons(center, extents, polys, 128);
+
+       // Find nearest polygon amongst the nearby polygons.
+       dtStatPolyRef nearest = 0;
+       float nearestDistanceSqr = FLT_MAX;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtStatPolyRef ref = polys[i];
+               float closest[3];
+               if (!closestPointToPoly(ref, center, closest))
+                       continue;
+               float d = vdistSqr(center, closest);
+               if (d < nearestDistanceSqr)
+               {
+                       nearestDistanceSqr = d;
+                       nearest = ref;
+               }
+       }
+
+       return nearest;
+}
+
+bool dtStatNavMesh::getPortalPoints(dtStatPolyRef from, dtStatPolyRef to, float* left, float* right) const
+{
+       const dtStatPoly* fromPoly = getPolyByRef(from);
+       if (!fromPoly)
+               return false;
+
+       // Find common edge between the polygons and returns the segment end points.
+       for (unsigned i = 0, j = (int)fromPoly->nv - 1; i < (int)fromPoly->nv; j = i++)
+       {
+               unsigned short neighbour = fromPoly->n[j];
+               if (neighbour == to)
+               {
+                       vcopy(left, getVertex(fromPoly->v[j]));
+                       vcopy(right, getVertex(fromPoly->v[i]));
+                       return true;
+               }
+       }
+
+       return false;
+}
+
+bool dtStatNavMesh::getEdgeMidPoint(dtStatPolyRef from, dtStatPolyRef to, float* mid) const
+{
+       float left[3], right[3];
+       if (!getPortalPoints(from, to, left,right)) return false;
+       mid[0] = (left[0]+right[0])*0.5f;
+       mid[1] = (left[1]+right[1])*0.5f;
+       mid[2] = (left[2]+right[2])*0.5f;
+       return true;
+}
+
+bool dtStatNavMesh::isInClosedList(dtStatPolyRef ref) const
+{
+       if (!m_nodePool) return false;
+       const dtNode* node = m_nodePool->findNode(ref);
+       return node && node->flags & DT_NODE_CLOSED;
+}
+
+int dtStatNavMesh::getMemUsed() const
+{
+       if (!m_nodePool || ! m_openList)
+               return 0;
+       return sizeof(*this) + m_dataSize +
+                       m_nodePool->getMemUsed() +
+                       m_openList->getMemUsed();
+}      
diff --git a/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp b/extern/recastnavigation/Detour/Source/DetourStatNavMeshBuilder.cpp
new file mode 100644 (file)
index 0000000..2ca455f
--- /dev/null
@@ -0,0 +1,346 @@
+//
+// Copyright (c) 2009 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 <math.h>
+#include <stdlib.h>
+#include <string.h>
+#include "DetourStatNavMesh.h"
+
+struct BVItem
+{
+       unsigned short bmin[3];
+       unsigned short bmax[3];
+       int i;
+};
+
+static int compareItemX(const void* va, const void* vb)
+{
+       const BVItem* a = (const BVItem*)va;
+       const BVItem* b = (const BVItem*)vb;
+       if (a->bmin[0] < b->bmin[0])
+               return -1;
+       if (a->bmin[0] > b->bmin[0])
+               return 1;
+       return 0;
+}
+
+static int compareItemY(const void* va, const void* vb)
+{
+       const BVItem* a = (const BVItem*)va;
+       const BVItem* b = (const BVItem*)vb;
+       if (a->bmin[1] < b->bmin[1])
+               return -1;
+       if (a->bmin[1] > b->bmin[1])
+               return 1;
+       return 0;
+}
+
+static int compareItemZ(const void* va, const void* vb)
+{
+       const BVItem* a = (const BVItem*)va;
+       const BVItem* b = (const BVItem*)vb;
+       if (a->bmin[2] < b->bmin[2])
+               return -1;
+       if (a->bmin[2] > b->bmin[2])
+               return 1;
+       return 0;
+}
+
+static void calcExtends(BVItem* items, int nitems, int imin, int imax,
+                                               unsigned short* bmin, unsigned short* bmax)
+{
+       bmin[0] = items[imin].bmin[0];
+       bmin[1] = items[imin].bmin[1];
+       bmin[2] = items[imin].bmin[2];
+       
+       bmax[0] = items[imin].bmax[0];
+       bmax[1] = items[imin].bmax[1];
+       bmax[2] = items[imin].bmax[2];
+       
+       for (int i = imin+1; i < imax; ++i)
+       {
+               const BVItem& it = items[i];
+               if (it.bmin[0] < bmin[0]) bmin[0] = it.bmin[0];
+               if (it.bmin[1] < bmin[1]) bmin[1] = it.bmin[1];
+               if (it.bmin[2] < bmin[2]) bmin[2] = it.bmin[2];
+               
+               if (it.bmax[0] > bmax[0]) bmax[0] = it.bmax[0];
+               if (it.bmax[1] > bmax[1]) bmax[1] = it.bmax[1];
+               if (it.bmax[2] > bmax[2]) bmax[2] = it.bmax[2];
+       }
+}
+
+inline int longestAxis(unsigned short x, unsigned short y, unsigned short z)
+{
+       int     axis = 0;
+       unsigned short maxVal = x;
+       if (y > maxVal)
+       {
+               axis = 1;
+               maxVal = y;
+       }
+       if (z > maxVal)
+       {
+               axis = 2;
+               maxVal = z;
+       }
+       return axis;
+}
+
+static void subdivide(BVItem* items, int nitems, int imin, int imax, int& curNode, dtStatBVNode* nodes)
+{
+       int inum = imax - imin;
+       int icur = curNode;
+       
+       dtStatBVNode& node = nodes[curNode++];
+       
+       if (inum == 1)
+       {
+               // Leaf
+               node.bmin[0] = items[imin].bmin[0];
+               node.bmin[1] = items[imin].bmin[1];
+               node.bmin[2] = items[imin].bmin[2];
+               
+               node.bmax[0] = items[imin].bmax[0];
+               node.bmax[1] = items[imin].bmax[1];
+               node.bmax[2] = items[imin].bmax[2];
+               
+               node.i = items[imin].i;
+       }
+       else
+       {
+               // Split
+               calcExtends(items, nitems, imin, imax, node.bmin, node.bmax);
+               
+               int     axis = longestAxis(node.bmax[0] - node.bmin[0],
+                                                          node.bmax[1] - node.bmin[1],
+                                                          node.bmax[2] - node.bmin[2]);
+               
+               if (axis == 0)
+               {
+                       // Sort along x-axis
+                       qsort(items+imin, inum, sizeof(BVItem), compareItemX);
+               }
+               else if (axis == 1)
+               {
+                       // Sort along y-axis
+                       qsort(items+imin, inum, sizeof(BVItem), compareItemY);
+               }
+               else
+               {
+                       // Sort along z-axis
+                       qsort(items+imin, inum, sizeof(BVItem), compareItemZ);
+               }
+               
+               int isplit = imin+inum/2;
+               
+               // Left
+               subdivide(items, nitems, imin, isplit, curNode, nodes);
+               // Right
+               subdivide(items, nitems, isplit, imax, curNode, nodes);
+               
+               int iescape = curNode - icur;
+               // Negative index means escape.
+               node.i = -iescape;
+       }
+}
+
+/*static*/ int createBVTree(const unsigned short* verts, const int nverts,
+                                               const unsigned short* polys, const int npolys, const int nvp,
+                                               float cs, float ch,
+                                               int nnodes, dtStatBVNode* nodes)
+{
+       // Build tree
+       BVItem* items = new BVItem[npolys];
+       for (int i = 0; i < npolys; i++)
+       {
+               BVItem& it = items[i];
+               it.i = i+1;
+               // Calc polygon bounds.
+               const unsigned short* p = &polys[i*nvp*2];
+               it.bmin[0] = it.bmax[0] = verts[p[0]*3+0];
+               it.bmin[1] = it.bmax[1] = verts[p[0]*3+1];
+               it.bmin[2] = it.bmax[2] = verts[p[0]*3+2];
+               
+               for (int j = 1; j < nvp; ++j)
+               {
+                       if (p[j] == 0xffff) break;
+                       unsigned short x = verts[p[j]*3+0];
+                       unsigned short y = verts[p[j]*3+1];
+                       unsigned short z = verts[p[j]*3+2];
+                       
+                       if (x < it.bmin[0]) it.bmin[0] = x;
+                       if (y < it.bmin[1]) it.bmin[1] = y;
+                       if (z < it.bmin[2]) it.bmin[2] = z;
+                       
+                       if (x > it.bmax[0]) it.bmax[0] = x;
+                       if (y > it.bmax[1]) it.bmax[1] = y;
+                       if (z > it.bmax[2]) it.bmax[2] = z;
+               }
+               // Remap y
+               it.bmin[1] = (unsigned short)floorf((float)it.bmin[1]*ch/cs);
+               it.bmax[1] = (unsigned short)ceilf((float)it.bmax[1]*ch/cs);
+       }
+       
+       int curNode = 0;
+       subdivide(items, npolys, 0, npolys, curNode, nodes);
+       
+       delete [] items;
+       
+       return curNode;
+}
+
+
+bool dtCreateNavMeshData(const unsigned short* verts, const int nverts,
+                                                const unsigned short* polys, const int npolys, const int nvp,
+                                                const float* bmin, const float* bmax, float cs, float ch,
+                                                const unsigned short* dmeshes, const float* dverts, const int ndverts,
+                                                const unsigned char* dtris, const int ndtris, 
+                                                unsigned char** outData, int* outDataSize)
+{
+       if (nvp > DT_STAT_VERTS_PER_POLYGON)
+               return false;
+       if (nverts >= 0xffff)
+               return false;
+               
+       if (!nverts)
+               return false;
+       if (!npolys)
+               return false;
+       if (!dmeshes || !dverts || ! dtris)
+               return false;
+       
+       // Find unique detail vertices.
+       int uniqueDetailVerts = 0;
+       if (dmeshes)
+       {
+               for (int i = 0; i < npolys; ++i)
+               {
+                       const unsigned short* p = &polys[i*nvp*2];
+                       int ndv = dmeshes[i*4+1];
+                       int nv = 0;
+                       for (int j = 0; j < nvp; ++j)
+                       {
+                               if (p[j] == 0xffff) break;
+                               nv++;
+                       }
+                       ndv -= nv;
+                       uniqueDetailVerts += ndv;
+               }
+       }
+       
+       // Calculate data size
+       const int headerSize = sizeof(dtStatNavMeshHeader);
+       const int vertsSize = sizeof(float)*3*nverts;
+       const int polysSize = sizeof(dtStatPoly)*npolys;
+       const int nodesSize = sizeof(dtStatBVNode)*npolys*2;
+       const int detailMeshesSize = sizeof(dtStatPolyDetail)*npolys;
+       const int detailVertsSize = sizeof(float)*3*uniqueDetailVerts;
+       const int detailTrisSize = sizeof(unsigned char)*4*ndtris;
+       
+       const int dataSize = headerSize + vertsSize + polysSize + nodesSize +
+                                                detailMeshesSize + detailVertsSize + detailTrisSize;
+       unsigned char* data = new unsigned char[dataSize];
+       if (!data)
+               return false;
+       memset(data, 0, dataSize);
+
+       unsigned char* d = data;
+       dtStatNavMeshHeader* header = (dtStatNavMeshHeader*)d; d += headerSize;
+       float* navVerts = (float*)d; d += vertsSize;
+       dtStatPoly* navPolys = (dtStatPoly*)d; d += polysSize;
+       dtStatBVNode* navNodes = (dtStatBVNode*)d; d += nodesSize;
+       dtStatPolyDetail* navDMeshes = (dtStatPolyDetail*)d; d += detailMeshesSize;
+       float* navDVerts = (float*)d; d += detailVertsSize;
+       unsigned char* navDTris = (unsigned char*)d; d += detailTrisSize;
+       
+       // Store header
+       header->magic = DT_STAT_NAVMESH_MAGIC;
+       header->version = DT_STAT_NAVMESH_VERSION;
+       header->npolys = npolys;
+       header->nverts = nverts;
+       header->cs = cs;
+       header->bmin[0] = bmin[0];
+       header->bmin[1] = bmin[1];
+       header->bmin[2] = bmin[2];
+       header->bmax[0] = bmax[0];
+       header->bmax[1] = bmax[1];
+       header->bmax[2] = bmax[2];
+       header->ndmeshes = dmeshes ? npolys : 0;
+       header->ndverts = dmeshes ? uniqueDetailVerts : 0;
+       header->ndtris = dmeshes ? ndtris : 0;
+       
+       // Store vertices
+       for (int i = 0; i < nverts; ++i)
+       {
+               const unsigned short* iv = &verts[i*3];
+               float* v = &navVerts[i*3];
+               v[0] = bmin[0] + iv[0] * cs;
+               v[1] = bmin[1] + iv[1] * ch;
+               v[2] = bmin[2] + iv[2] * cs;
+       }
+       
+       // Store polygons
+       const unsigned short* src = polys;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtStatPoly* p = &navPolys[i];
+               p->nv = 0;
+               for (int j = 0; j < nvp; ++j)
+               {
+                       if (src[j] == 0xffff) break;
+                       p->v[j] = src[j];
+                       p->n[j] = src[nvp+j]+1;
+                       p->nv++;
+               }
+               src += nvp*2;
+       }
+       
+       header->nnodes = createBVTree(verts, nverts, polys, npolys, nvp,
+                                        cs, ch, npolys*2, navNodes);
+       
+
+       // Store detail meshes and vertices.
+       // The nav polygon vertices are stored as the first vertices on each mesh.
+       // We compress the mesh data by skipping them and using the navmesh coordinates.
+       unsigned short vbase = 0;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtStatPolyDetail& dtl = navDMeshes[i];
+               const int vb = dmeshes[i*4+0];
+               const int ndv = dmeshes[i*4+1];
+               const int nv = navPolys[i].nv;
+               dtl.vbase = vbase;
+               dtl.nverts = ndv-nv;
+               dtl.tbase = dmeshes[i*4+2];
+               dtl.ntris = dmeshes[i*4+3];
+               // Copy vertices except the first 'nv' verts which are equal to nav poly verts.
+               if (ndv-nv)
+               {
+                       memcpy(&navDVerts[vbase*3], &dverts[(vb+nv)*3], sizeof(float)*3*(ndv-nv));
+                       vbase += ndv-nv;
+               }
+       }
+       // Store triangles.
+       memcpy(navDTris, dtris, sizeof(unsigned char)*4*ndtris);
+       
+       *outData = data;
+       *outDataSize = dataSize;
+       
+       return true;
+}
diff --git a/extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp b/extern/recastnavigation/Detour/Source/DetourTileNavMesh.cpp
new file mode 100644 (file)
index 0000000..0813c77
--- /dev/null
@@ -0,0 +1,1428 @@
+//
+// Copyright (c) 2009 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 <math.h>
+#include <float.h>
+#include <string.h>
+#include <stdio.h>
+#include "DetourTileNavMesh.h"
+#include "DetourNode.h"
+#include "DetourCommon.h"
+
+
+inline int opposite(int side) { return (side+2) & 0x3; }
+
+inline bool overlapBoxes(const float* amin, const float* amax,
+                                                const float* bmin, const float* bmax)
+{
+       bool overlap = true;
+       overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
+       overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
+       overlap = (amin[2] > bmax[2] || amax[2] < bmin[2]) ? false : overlap;
+       return overlap;
+}
+
+inline bool overlapRects(const float* amin, const float* amax,
+                                                const float* bmin, const float* bmax)
+{
+       bool overlap = true;
+       overlap = (amin[0] > bmax[0] || amax[0] < bmin[0]) ? false : overlap;
+       overlap = (amin[1] > bmax[1] || amax[1] < bmin[1]) ? false : overlap;
+       return overlap;
+}
+
+static void calcRect(const float* va, const float* vb,
+                                        float* bmin, float* bmax,
+                                        int side, float padx, float pady)
+{
+       if ((side&1) == 0)
+       {
+               bmin[0] = min(va[2],vb[2]) + padx;
+               bmin[1] = min(va[1],vb[1]) - pady;
+               bmax[0] = max(va[2],vb[2]) - padx;
+               bmax[1] = max(va[1],vb[1]) + pady;
+       }
+       else
+       {
+               bmin[0] = min(va[0],vb[0]) + padx;
+               bmin[1] = min(va[1],vb[1]) - pady;
+               bmax[0] = max(va[0],vb[0]) - padx;
+               bmax[1] = max(va[1],vb[1]) + pady;
+       }
+}
+
+inline int computeTileHash(int x, int y)
+{
+       const unsigned int h1 = 0x8da6b343; // Large multiplicative constants;
+       const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes
+       unsigned int n = h1 * x + h2 * y;
+       return (int)(n & (DT_TILE_LOOKUP_SIZE-1));
+}
+
+//////////////////////////////////////////////////////////////////////////////////////////
+dtTiledNavMesh::dtTiledNavMesh() :
+       m_tileSize(0),
+       m_portalHeight(0),
+       m_nextFree(0),
+       m_tmpLinks(0),
+       m_ntmpLinks(0),
+       m_nodePool(0),
+       m_openList(0)
+{
+}
+
+dtTiledNavMesh::~dtTiledNavMesh()
+{
+       for (int i = 0; i < DT_MAX_TILES; ++i)
+       {
+               if (m_tiles[i].data && m_tiles[i].dataSize < 0)
+               {
+                       delete [] m_tiles[i].data;
+                       m_tiles[i].data = 0;
+                       m_tiles[i].dataSize = 0;
+               }
+       }
+       delete [] m_tmpLinks;
+       delete m_nodePool;
+       delete m_openList;
+}
+               
+bool dtTiledNavMesh::init(const float* orig, float tileSize, float portalHeight)
+{
+       vcopy(m_orig, orig);
+       m_tileSize = tileSize;
+       m_portalHeight = portalHeight;
+       
+       // Init tiles
+       memset(m_tiles, 0, sizeof(dtTile)*DT_MAX_TILES);
+       memset(m_posLookup, 0, sizeof(dtTile*)*DT_TILE_LOOKUP_SIZE);
+       m_nextFree = 0;
+       for (int i = DT_MAX_TILES-1; i >= 0; --i)
+       {
+               m_tiles[i].next = m_nextFree;
+               m_nextFree = &m_tiles[i];
+       }
+
+       if (!m_nodePool)
+       {
+               m_nodePool = new dtNodePool(2048, 256);
+               if (!m_nodePool)
+                       return false;
+       }
+       
+       if (!m_openList)
+       {
+               m_openList = new dtNodeQueue(2048);
+               if (!m_openList)
+                       return false;
+       }
+       
+       return true;
+}
+
+//////////////////////////////////////////////////////////////////////////////////////////
+int dtTiledNavMesh::findConnectingPolys(const float* va, const float* vb,
+                                                                               dtTile* tile, int side,
+                                                                               dtTilePolyRef* con, float* conarea, int maxcon)
+{
+       if (!tile) return 0;
+       dtTileHeader* h = tile->header;
+       
+       float amin[2], amax[2];
+       calcRect(va,vb, amin,amax, side, 0.01f, m_portalHeight);
+
+       // Remove links pointing to 'side' and compact the links array. 
+       float bmin[2], bmax[2];
+       unsigned short m = 0x8000 | (unsigned short)side;
+       int n = 0;
+       
+       dtTilePolyRef base = getTileId(tile);
+       
+       for (int i = 0; i < h->npolys; ++i)
+       {
+               dtTilePoly* poly = &h->polys[i];
+               for (int j = 0; j < poly->nv; ++j)
+               {
+                       // Skip edges which do not point to the right side.
+                       if (poly->n[j] != m) continue;
+                       // Check if the segments touch.
+                       const float* vc = &h->verts[poly->v[j]*3];
+                       const float* vd = &h->verts[poly->v[(j+1) % (int)poly->nv]*3];
+                       calcRect(vc,vd, bmin,bmax, side, 0.01f, m_portalHeight);
+                       if (!overlapRects(amin,amax, bmin,bmax)) continue;
+                       // Add return value.
+                       if (n < maxcon)
+                       {
+                               conarea[n*2+0] = max(amin[0], bmin[0]);
+                               conarea[n*2+1] = min(amax[0], bmax[0]);
+                               con[n] = base | (unsigned int)i;
+                               n++;
+                       }
+                       break;
+               }
+       }
+       return n;
+}
+
+void dtTiledNavMesh::removeExtLinks(dtTile* tile, int side)
+{
+       if (!tile) return;
+       dtTileHeader* h = tile->header;
+       
+       // Remove links pointing to 'side' and compact the links array. 
+       dtTileLink* pool = m_tmpLinks;
+       int nlinks = 0;
+       for (int i = 0; i < h->npolys; ++i)
+       {
+               dtTilePoly* poly = &h->polys[i];
+               int plinks = nlinks;
+               int nplinks = 0;                
+               for (int j = 0; j < poly->nlinks; ++j)
+               {
+                       dtTileLink* link = &h->links[poly->links+j];
+                       if ((int)link->side != side)
+                       {
+                               if (nlinks < h->maxlinks)
+                               {
+                                       dtTileLink* dst = &pool[nlinks++];
+                                       memcpy(dst, link, sizeof(dtTileLink));
+                                       nplinks++;
+                               }
+                       }
+               }
+               poly->links = plinks;
+               poly->nlinks = nplinks;
+       }
+       h->nlinks = nlinks;
+       if (h->nlinks)
+               memcpy(h->links, m_tmpLinks, sizeof(dtTileLink)*nlinks);
+}
+
+void dtTiledNavMesh::buildExtLinks(dtTile* tile, dtTile* target, int side)
+{
+       if (!tile) return;
+       dtTileHeader* h = tile->header;
+       
+       // Remove links pointing to 'side' and compact the links array. 
+       dtTileLink* pool = m_tmpLinks;
+       int nlinks = 0;
+       for (int i = 0; i < h->npolys; ++i)
+       {
+               dtTilePoly* poly = &h->polys[i];
+               int plinks = nlinks;
+               int nplinks = 0;
+               // Copy internal and other external links.
+               for (int j = 0; j < poly->nlinks; ++j)
+               {
+                       dtTileLink* link = &h->links[poly->links+j];
+                       if ((int)link->side != side)
+                       {
+                               if (nlinks < h->maxlinks)
+                               {
+                                       dtTileLink* dst = &pool[nlinks++];
+                                       memcpy(dst, link, sizeof(dtTileLink));
+                                       nplinks++;
+                               }
+                       }
+               }
+               // Create new links.
+               unsigned short m = 0x8000 | (unsigned short)side;
+               for (int j = 0; j < poly->nv; ++j)
+               {
+                       // Skip edges which do not point to the right side.
+                       if (poly->n[j] != m) continue;
+                       
+                       // Create new links
+                       const float* va = &h->verts[poly->v[j]*3];
+                       const float* vb = &h->verts[poly->v[(j+1)%(int)poly->nv]*3];
+                       dtTilePolyRef nei[4];
+                       float neia[4*2];
+                       int nnei = findConnectingPolys(va,vb, target, opposite(side), nei,neia,4);
+                       for (int k = 0; k < nnei; ++k)
+                       {
+                               if (nlinks < h->maxlinks)
+                               {
+                                       dtTileLink* link = &pool[nlinks++];
+                                       link->ref = nei[k];
+                                       link->p = (unsigned short)i;
+                                       link->e = (unsigned char)j;
+                                       link->side = (unsigned char)side;
+
+                                       // Compress portal limits to a byte value.
+                                       if (side == 0 || side == 2)
+                                       {
+                                               const float lmin = min(va[2], vb[2]);
+                                               const float lmax = max(va[2], vb[2]);
+                                               link->bmin = (unsigned char)(clamp((neia[k*2+0]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f);
+                                               link->bmax = (unsigned char)(clamp((neia[k*2+1]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f);
+                                       }
+                                       else
+                                       {
+                                               const float lmin = min(va[0], vb[0]);
+                                               const float lmax = max(va[0], vb[0]);
+                                               link->bmin = (unsigned char)(clamp((neia[k*2+0]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f);
+                                               link->bmax = (unsigned char)(clamp((neia[k*2+1]-lmin)/(lmax-lmin), 0.0f, 1.0f)*255.0f);
+                                       }                                       
+                                       nplinks++;
+                               }
+                       }
+               }
+               
+               poly->links = plinks;
+               poly->nlinks = nplinks;
+       }
+       h->nlinks = nlinks;
+       if (h->nlinks)
+               memcpy(h->links, m_tmpLinks, sizeof(dtTileLink)*nlinks);
+}
+
+void dtTiledNavMesh::buildIntLinks(dtTile* tile)
+{
+       if (!tile) return;
+       dtTileHeader* h = tile->header;
+
+       dtTilePolyRef base = getTileId(tile);
+       dtTileLink* pool = h->links;
+       int nlinks = 0;
+       for (int i = 0; i < h->npolys; ++i)
+       {
+               dtTilePoly* poly = &h->polys[i];
+               poly->links = nlinks;
+               poly->nlinks = 0;
+               for (int j = 0; j < poly->nv; ++j)
+               {
+                       // Skip hard and non-internal edges.
+                       if (poly->n[j] == 0 || (poly->n[j] & 0x8000)) continue;
+                       
+                       if (nlinks < h->maxlinks)
+                       {
+                               dtTileLink* link = &pool[nlinks++];
+                               link->ref = base | (unsigned int)(poly->n[j]-1);
+                               link->p = (unsigned short)i;
+                               link->e = (unsigned char)j;
+                               link->side = 0xff;
+                               link->bmin = link->bmax = 0;
+                               poly->nlinks++;
+                       }
+               }
+       }
+       h->nlinks = nlinks;
+}
+
+bool dtTiledNavMesh::addTileAt(int x, int y, unsigned char* data, int dataSize, bool ownsData)
+{
+       if (getTileAt(x,y))
+               return false;
+       // Make sure there is enough space for new tile.
+       if (!m_nextFree)
+               return false;
+       // Make sure the data is in right format.
+       dtTileHeader* header = (dtTileHeader*)data;
+       if (header->magic != DT_TILE_NAVMESH_MAGIC)
+               return false;
+       if (header->version != DT_TILE_NAVMESH_VERSION)
+               return false;
+       
+       // Make sure the tmp link array is large enough.
+       if (header->maxlinks > m_ntmpLinks)
+       {
+               m_ntmpLinks = header->maxlinks;
+               delete [] m_tmpLinks;
+               m_tmpLinks = 0;
+               m_tmpLinks = new dtTileLink[m_ntmpLinks];
+       }
+       if (!m_tmpLinks)
+               return false;
+       
+       // Allocate a tile.
+       dtTile* tile = m_nextFree;
+       m_nextFree = tile->next;
+       tile->next = 0;
+
+       // Insert tile into the position lut.
+       int h = computeTileHash(x,y);
+       tile->next = m_posLookup[h];
+       m_posLookup[h] = tile;
+       
+       // Patch header pointers.
+       const int headerSize = sizeof(dtTileHeader);
+       const int vertsSize = sizeof(float)*3*header->nverts;
+       const int polysSize = sizeof(dtTilePoly)*header->npolys;
+       const int linksSize = sizeof(dtTileLink)*(header->maxlinks);
+       const int detailMeshesSize = sizeof(dtTilePolyDetail)*header->ndmeshes;
+       const int detailVertsSize = sizeof(float)*3*header->ndverts;
+       const int detailTrisSize = sizeof(unsigned char)*4*header->ndtris;
+       
+       unsigned char* d = data + headerSize;
+       header->verts = (float*)d; d += vertsSize;
+       header->polys = (dtTilePoly*)d; d += polysSize;
+       header->links = (dtTileLink*)d; d += linksSize;
+       header->dmeshes = (dtTilePolyDetail*)d; d += detailMeshesSize;
+       header->dverts = (float*)d; d += detailVertsSize;
+       header->dtris = (unsigned char*)d; d += detailTrisSize;
+
+       // Init tile.
+       tile->header = header;
+       tile->x = x;
+       tile->y = y;
+       tile->data = data;
+       tile->dataSize = dataSize;
+       tile->ownsData = ownsData;
+
+       buildIntLinks(tile);
+
+       // Create connections connections.
+       for (int i = 0; i < 4; ++i)
+       {
+               dtTile* nei = getNeighbourTileAt(x,y,i);
+               if (nei)
+               {
+                       buildExtLinks(tile, nei, i);
+                       buildExtLinks(nei, tile, opposite(i));
+               }
+       }
+       
+       return true;
+}
+
+dtTile* dtTiledNavMesh::getTileAt(int x, int y)
+{
+       // Find tile based on hash.
+       int h = computeTileHash(x,y);
+       dtTile* tile = m_posLookup[h];
+       while (tile)
+       {
+               if (tile->x == x && tile->y == y)
+                       return tile;
+               tile = tile->next;
+       }
+       return 0;
+}
+
+dtTile* dtTiledNavMesh::getTile(int i)
+{
+       return &m_tiles[i];
+}
+
+const dtTile* dtTiledNavMesh::getTile(int i) const
+{
+       return &m_tiles[i];
+}
+
+dtTile* dtTiledNavMesh::getNeighbourTileAt(int x, int y, int side)
+{
+       switch (side)
+       {
+       case 0: x++; break;
+       case 1: y++; break;
+       case 2: x--; break;
+       case 3: y--; break;
+       };
+       return getTileAt(x,y);
+}
+
+bool dtTiledNavMesh::removeTileAt(int x, int y, unsigned char** data, int* dataSize)
+{
+       // Remove tile from hash lookup.
+       int h = computeTileHash(x,y);
+       dtTile* prev = 0;
+       dtTile* tile = m_posLookup[h];
+       while (tile)
+       {
+               if (tile->x == x && tile->y == y)
+               {
+                       if (prev)
+                               prev->next = tile->next;
+                       else
+                               m_posLookup[h] = tile->next;
+                       break;
+               }
+               prev = tile;
+               tile = tile->next;
+       }
+       if (!tile)
+               return false;
+       
+       // Remove connections to neighbour tiles.
+       for (int i = 0; i < 4; ++i)
+       {
+               dtTile* nei = getNeighbourTileAt(x,y,i);
+               if (!nei) continue;
+               removeExtLinks(nei, opposite(i));
+       }
+       
+       
+       // Reset tile.
+       if (tile->ownsData)
+       {
+               // Owns data
+               delete [] tile->data;
+               tile->data = 0;
+               tile->dataSize = 0;
+               if (data) *data = 0;
+               if (dataSize) *dataSize = 0;
+       }
+       else
+       {
+               if (data) *data = tile->data;
+               if (dataSize) *dataSize = tile->dataSize;
+       }
+       tile->header = 0;
+       tile->x = tile->y = 0;
+       tile->salt++;
+
+       // Add to free list.
+       tile->next = m_nextFree;
+       m_nextFree = tile;
+
+       return true;
+}
+
+
+
+bool dtTiledNavMesh::closestPointToPoly(dtTilePolyRef ref, const float* pos, float* closest) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return false;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false;
+       const dtTileHeader* header = m_tiles[it].header;
+
+       if (ip >= (unsigned int)header->npolys) return false;
+       const dtTilePoly* poly = &header->polys[ip];
+       
+       float closestDistSqr = FLT_MAX;
+       const dtTilePolyDetail* pd = &header->dmeshes[ip];
+       
+       for (int j = 0; j < pd->ntris; ++j)
+       {
+               const unsigned char* t = &header->dtris[(pd->tbase+j)*4];
+               const float* v[3];
+               for (int k = 0; k < 3; ++k)
+               {
+                       if (t[k] < poly->nv)
+                               v[k] = &header->verts[poly->v[t[k]]*3];
+                       else
+                               v[k] = &header->dverts[(pd->vbase+(t[k]-poly->nv))*3];
+               }
+               float pt[3];
+               closestPtPointTriangle(pt, pos, v[0], v[1], v[2]);
+               float d = vdistSqr(pos, pt);
+               if (d < closestDistSqr)
+               {
+                       vcopy(closest, pt);
+                       closestDistSqr = d;
+               }
+       }
+       
+       return true;
+}
+
+bool dtTiledNavMesh::getPolyHeight(dtTilePolyRef ref, const float* pos, float* height) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return false;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false;
+       const dtTileHeader* header = m_tiles[it].header;
+       
+       if (ip >= (unsigned int)header->npolys) return false;
+       const dtTilePoly* poly = &header->polys[ip];
+       
+       const dtTilePolyDetail* pd = &header->dmeshes[ip];
+       for (int j = 0; j < pd->ntris; ++j)
+       {
+               const unsigned char* t = &header->dtris[(pd->tbase+j)*4];
+               const float* v[3];
+               for (int k = 0; k < 3; ++k)
+               {
+                       if (t[k] < poly->nv)
+                               v[k] = &header->verts[poly->v[t[k]]*3];
+                       else
+                               v[k] = &header->dverts[(pd->vbase+(t[k]-poly->nv))*3];
+               }
+               float h;
+               if (closestHeightPointTriangle(pos, v[0], v[1], v[2], h))
+               {
+                       if (height)
+                               *height = h;
+                       return true;
+               }
+       }
+       
+       return false;
+}
+
+
+dtTilePolyRef dtTiledNavMesh::findNearestPoly(const float* center, const float* extents)
+{
+       // Get nearby polygons from proximity grid.
+       dtTilePolyRef polys[128];
+       int npolys = queryPolygons(center, extents, polys, 128);
+       
+       // Find nearest polygon amongst the nearby polygons.
+       dtTilePolyRef nearest = 0;
+       float nearestDistanceSqr = FLT_MAX;
+       for (int i = 0; i < npolys; ++i)
+       {
+               dtTilePolyRef ref = polys[i];
+               float closest[3];
+               if (!closestPointToPoly(ref, center, closest))
+                       continue;
+               float d = vdistSqr(center, closest);
+               if (d < nearestDistanceSqr)
+               {
+                       nearestDistanceSqr = d;
+                       nearest = ref;
+               }
+       }
+       
+       return nearest;
+}
+
+dtTilePolyRef dtTiledNavMesh::getTileId(dtTile* tile)
+{
+       if (!tile) return 0;
+       const unsigned int it = tile - m_tiles;
+       return dtEncodeTileId(tile->salt, it, 0);
+}
+
+int dtTiledNavMesh::queryTilePolygons(dtTile* tile,
+                                                                         const float* qmin, const float* qmax,
+                                                                         dtTilePolyRef* polys, const int maxPolys)
+{
+       float bmin[3], bmax[3];
+       const dtTileHeader* header = tile->header;
+       int n = 0;
+       dtTilePolyRef base = getTileId(tile);
+       for (int i = 0; i < header->npolys; ++i)
+       {
+               // Calc polygon bounds.
+               dtTilePoly* p = &header->polys[i];
+               const float* v = &header->verts[p->v[0]*3];
+               vcopy(bmin, v);
+               vcopy(bmax, v);
+               for (int j = 1; j < p->nv; ++j)
+               {
+                       v = &header->verts[p->v[j]*3];
+                       vmin(bmin, v);
+                       vmax(bmax, v);
+               }
+               if (overlapBoxes(qmin,qmax, bmin,bmax))
+               {
+                       if (n < maxPolys)
+                               polys[n++] = base | (dtTilePolyRef)i;
+               }
+       }
+       return n;
+}
+
+int dtTiledNavMesh::queryPolygons(const float* center, const float* extents,
+                                                                 dtTilePolyRef* polys, const int maxPolys)
+{
+       float bmin[3], bmax[3];
+       bmin[0] = center[0] - extents[0];
+       bmin[1] = center[1] - extents[1];
+       bmin[2] = center[2] - extents[2];
+       
+       bmax[0] = center[0] + extents[0];
+       bmax[1] = center[1] + extents[1];
+       bmax[2] = center[2] + extents[2];
+       
+       // Find tiles the query touches.
+       const int minx = (int)floorf((bmin[0]-m_orig[0]) / m_tileSize);
+       const int maxx = (int)ceilf((bmax[0]-m_orig[0]) / m_tileSize);
+
+       const int miny = (int)floorf((bmin[2]-m_orig[2]) / m_tileSize);
+       const int maxy = (int)ceilf((bmax[2]-m_orig[2]) / m_tileSize);
+
+       int n = 0;
+       for (int y = miny; y < maxy; ++y)
+       {
+               for (int x = minx; x < maxx; ++x)
+               {
+                       dtTile* tile = getTileAt(x,y);
+                       if (!tile) continue;
+                       n += queryTilePolygons(tile, bmin, bmax, polys+n, maxPolys-n);
+                       if (n >= maxPolys) return n;
+               }
+       }
+
+       return n;
+}
+
+int dtTiledNavMesh::findPath(dtTilePolyRef startRef, dtTilePolyRef endRef,
+                                                        const float* startPos, const float* endPos,
+                                                        dtTilePolyRef* path, const int maxPathSize)
+{
+       if (!startRef || !endRef)
+               return 0;
+       
+       if (!maxPathSize)
+               return 0;
+       
+       if (!getPolyByRef(startRef) || !getPolyByRef(endRef))
+               return 0;
+       
+       if (startRef == endRef)
+       {
+               path[0] = startRef;
+               return 1;
+       }
+       
+       if (!m_nodePool || !m_openList)
+               return 0;
+               
+       m_nodePool->clear();
+       m_openList->clear();
+       
+       static const float H_SCALE = 1.1f;      // Heuristic scale.
+       
+       dtNode* startNode = m_nodePool->getNode(startRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = vdist(startPos, endPos) * H_SCALE;
+       startNode->id = startRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+       
+       dtNode* lastBestNode = startNode;
+       float lastBestNodeCost = startNode->total;
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+               
+               if (bestNode->id == endRef)
+               {
+                       lastBestNode = bestNode;
+                       break;
+               }
+
+               // Get poly and tile.
+               unsigned int salt, it, ip;
+               dtDecodeTileId(bestNode->id, salt, it, ip);
+               // The API input has been cheked already, skip checking internal data.
+               const dtTileHeader* header = m_tiles[it].header;
+               const dtTilePoly* poly = &header->polys[ip];
+               
+               for (int i = 0; i < poly->nlinks; ++i)
+               {
+                       dtTilePolyRef neighbour = header->links[poly->links+i].ref;
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               // Calculate cost.
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, startPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.cost = parent->cost + vdist(p0,p1);
+                               // Special case for last node.
+                               if (newNode.id == endRef)
+                                       newNode.cost += vdist(p1, endPos);
+
+                               // Heuristic
+                               const float h = vdist(p1,endPos)*H_SCALE;
+                               newNode.total = newNode.cost + h;
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+                               
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->cost = newNode.cost;
+                                       actualNode->total = newNode.total;
+                                       
+                                       if (h < lastBestNodeCost)
+                                       {
+                                               lastBestNodeCost = h;
+                                               lastBestNode = actualNode;
+                                       }
+                                       
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               actualNode->flags |= DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+               bestNode->flags |= DT_NODE_CLOSED;
+       }
+       
+       // Reverse the path.
+       dtNode* prev = 0;
+       dtNode* node = lastBestNode;
+       do
+       {
+               dtNode* next = m_nodePool->getNodeAtIdx(node->pidx);
+               node->pidx = m_nodePool->getNodeIdx(prev);
+               prev = node;
+               node = next;
+       }
+       while (node);
+       
+       // Store path
+       node = prev;
+       int n = 0;
+       do
+       {
+               path[n++] = node->id;
+               node = m_nodePool->getNodeAtIdx(node->pidx);
+       }
+       while (node && n < maxPathSize);
+       
+       return n;
+}
+
+int dtTiledNavMesh::findStraightPath(const float* startPos, const float* endPos,
+                                                                        const dtTilePolyRef* path, const int pathSize,
+                                                                        float* straightPath, const int maxStraightPathSize)
+{
+       if (!maxStraightPathSize)
+               return 0;
+       
+       if (!path[0])
+               return 0;
+       
+       int straightPathSize = 0;
+       
+       float closestStartPos[3];
+       if (!closestPointToPoly(path[0], startPos, closestStartPos))
+               return 0;
+       
+       // Add start point.
+       vcopy(&straightPath[straightPathSize*3], closestStartPos);
+       straightPathSize++;
+       if (straightPathSize >= maxStraightPathSize)
+               return straightPathSize;
+       
+       float closestEndPos[3];
+       if (!closestPointToPoly(path[pathSize-1], endPos, closestEndPos))
+               return 0;
+       
+       float portalApex[3], portalLeft[3], portalRight[3];
+       
+       if (pathSize > 1)
+       {
+               vcopy(portalApex, closestStartPos);
+               vcopy(portalLeft, portalApex);
+               vcopy(portalRight, portalApex);
+               int apexIndex = 0;
+               int leftIndex = 0;
+               int rightIndex = 0;
+               
+               for (int i = 0; i < pathSize; ++i)
+               {
+                       float left[3], right[3];
+                       if (i < pathSize-1)
+                       {
+                               // Next portal.
+                               if (!getPortalPoints(path[i], path[i+1], left, right))
+                               {
+                                       if (!closestPointToPoly(path[i], endPos, closestEndPos))
+                                               return 0;
+                                       vcopy(&straightPath[straightPathSize*3], closestEndPos);
+                                       straightPathSize++;
+                                       return straightPathSize;
+                               }
+                       }
+                       else
+                       {
+                               // End of the path.
+                               vcopy(left, closestEndPos);
+                               vcopy(right, closestEndPos);
+                       }
+                       
+                       // Right vertex.
+                       if (vequal(portalApex, portalRight))
+                       {
+                               vcopy(portalRight, right);
+                               rightIndex = i;
+                       }
+                       else
+                       {
+                               if (triArea2D(portalApex, portalRight, right) <= 0.0f)
+                               {
+                                       if (triArea2D(portalApex, portalLeft, right) > 0.0f)
+                                       {
+                                               vcopy(portalRight, right);
+                                               rightIndex = i;
+                                       }
+                                       else
+                                       {
+                                               vcopy(portalApex, portalLeft);
+                                               apexIndex = leftIndex;
+                                               
+                                               if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex))
+                                               {
+                                                       vcopy(&straightPath[straightPathSize*3], portalApex);
+                                                       straightPathSize++;
+                                                       if (straightPathSize >= maxStraightPathSize)
+                                                               return straightPathSize;
+                                               }
+                                               
+                                               vcopy(portalLeft, portalApex);
+                                               vcopy(portalRight, portalApex);
+                                               leftIndex = apexIndex;
+                                               rightIndex = apexIndex;
+                                               
+                                               // Restart
+                                               i = apexIndex;
+                                               
+                                               continue;
+                                       }
+                               }
+                       }
+                       
+                       // Left vertex.
+                       if (vequal(portalApex, portalLeft))
+                       {
+                               vcopy(portalLeft, left);
+                               leftIndex = i;
+                       }
+                       else
+                       {
+                               if (triArea2D(portalApex, portalLeft, left) >= 0.0f)
+                               {
+                                       if (triArea2D(portalApex, portalRight, left) < 0.0f)
+                                       {
+                                               vcopy(portalLeft, left);
+                                               leftIndex = i;
+                                       }
+                                       else
+                                       {
+                                               vcopy(portalApex, portalRight);
+                                               apexIndex = rightIndex;
+                                               
+                                               if (!vequal(&straightPath[(straightPathSize-1)*3], portalApex))
+                                               {
+                                                       vcopy(&straightPath[straightPathSize*3], portalApex);
+                                                       straightPathSize++;
+                                                       if (straightPathSize >= maxStraightPathSize)
+                                                               return straightPathSize;
+                                               }
+                                               
+                                               vcopy(portalLeft, portalApex);
+                                               vcopy(portalRight, portalApex);
+                                               leftIndex = apexIndex;
+                                               rightIndex = apexIndex;
+                                               
+                                               // Restart
+                                               i = apexIndex;
+                                               
+                                               continue;
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       // Add end point.
+       vcopy(&straightPath[straightPathSize*3], closestEndPos);
+       straightPathSize++;
+       
+       return straightPathSize;
+}
+
+// Returns portal points between two polygons.
+bool dtTiledNavMesh::getPortalPoints(dtTilePolyRef from, dtTilePolyRef to, float* left, float* right) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(from, salt, it, ip);
+       if (it >= DT_MAX_TILES) return false;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return false;
+       if (ip >= (unsigned int)m_tiles[it].header->npolys) return false;
+       const dtTileHeader* fromHeader = m_tiles[it].header;
+       const dtTilePoly* fromPoly = &fromHeader->polys[ip];
+
+       for (int i = 0; i < fromPoly->nlinks; ++i)
+       {
+               const dtTileLink* link = &fromHeader->links[fromPoly->links+i];
+               if (link->ref == to)
+               {
+                       // Find portal vertices.
+                       const int v0 = fromPoly->v[link->e];
+                       const int v1 = fromPoly->v[(link->e+1) % fromPoly->nv];
+                       vcopy(left, &fromHeader->verts[v0*3]);
+                       vcopy(right, &fromHeader->verts[v1*3]);
+                       // If the link is at tile boundary, clamp the vertices to
+                       // the link width.
+                       if (link->side == 0 || link->side == 2)
+                       {
+                               // Unpack portal limits.
+                               const float smin = min(left[2],right[2]);
+                               const float smax = max(left[2],right[2]);
+                               const float s = (smax-smin) / 255.0f;
+                               const float lmin = smin + link->bmin*s;
+                               const float lmax = smin + link->bmax*s;
+                               left[2] = max(left[2],lmin);
+                               left[2] = min(left[2],lmax);
+                               right[2] = max(right[2],lmin);
+                               right[2] = min(right[2],lmax);
+                       }
+                       else if (link->side == 1 || link->side == 3)
+                       {
+                               // Unpack portal limits.
+                               const float smin = min(left[0],right[0]);
+                               const float smax = max(left[0],right[0]);
+                               const float s = (smax-smin) / 255.0f;
+                               const float lmin = smin + link->bmin*s;
+                               const float lmax = smin + link->bmax*s;
+                               left[0] = max(left[0],lmin);
+                               left[0] = min(left[0],lmax);
+                               right[0] = max(right[0],lmin);
+                               right[0] = min(right[0],lmax);
+                       }
+                       return true;
+               }
+       }
+       return false;
+}
+
+// Returns edge mid point between two polygons.
+bool dtTiledNavMesh::getEdgeMidPoint(dtTilePolyRef from, dtTilePolyRef to, float* mid) const
+{
+       float left[3], right[3];
+       if (!getPortalPoints(from, to, left,right)) return false;
+       mid[0] = (left[0]+right[0])*0.5f;
+       mid[1] = (left[1]+right[1])*0.5f;
+       mid[2] = (left[2]+right[2])*0.5f;
+       return true;
+}
+
+int dtTiledNavMesh::raycast(dtTilePolyRef centerRef, const float* startPos, const float* endPos,
+                                                       float& t, dtTilePolyRef* path, const int pathSize)
+{
+       t = 0;
+       
+       if (!centerRef || !getPolyByRef(centerRef))
+               return 0;
+       
+       dtTilePolyRef curRef = centerRef;
+       float verts[DT_TILE_VERTS_PER_POLYGON*3];       
+       int n = 0;
+       
+       while (curRef)
+       {
+               // Cast ray against current polygon.
+               
+               // The API input has been cheked already, skip checking internal data.
+               unsigned int salt, it, ip;
+               dtDecodeTileId(curRef, salt, it, ip);
+               const dtTileHeader* header = m_tiles[it].header;
+               const dtTilePoly* poly = &header->polys[ip];
+
+               // Collect vertices.
+               int nv = 0;
+               for (int i = 0; i < (int)poly->nv; ++i)
+               {
+                       vcopy(&verts[nv*3], &header->verts[poly->v[i]*3]);
+                       nv++;
+               }               
+               if (nv < 3)
+               {
+                       // Hit bad polygon, report hit.
+                       return n;
+               }
+               
+               float tmin, tmax;
+               int segMin, segMax;
+               if (!intersectSegmentPoly2D(startPos, endPos, verts, nv, tmin, tmax, segMin, segMax))
+               {
+                       // Could not hit the polygon, keep the old t and report hit.
+                       return n;
+               }
+               // Keep track of furthest t so far.
+               if (tmax > t)
+                       t = tmax;
+
+               if (n < pathSize)
+                       path[n++] = curRef;
+               
+               // Follow neighbours.
+               dtTilePolyRef nextRef = 0;
+               for (int i = 0; i < poly->nlinks; ++i)
+               {
+                       const dtTileLink* link = &header->links[poly->links+i];
+                       if ((int)link->e == segMax)
+                       {
+                               // If the link is internal, just return the ref.
+                               if (link->side == 0xff)
+                               {
+                                       nextRef = link->ref;
+                                       break;
+                               }
+                               
+                               // If the link is at tile boundary,
+                               const int v0 = poly->v[link->e];
+                               const int v1 = poly->v[(link->e+1) % poly->nv];
+                               const float* left = &header->verts[v0*3];
+                               const float* right = &header->verts[v1*3];
+                               
+                               // Check that the intersection lies inside the link portal.
+                               if (link->side == 0 || link->side == 2)
+                               {
+                                       // Calculate link size.
+                                       const float smin = min(left[2],right[2]);
+                                       const float smax = max(left[2],right[2]);
+                                       const float s = (smax-smin) / 255.0f;
+                                       const float lmin = smin + link->bmin*s;
+                                       const float lmax = smin + link->bmax*s;
+                                       // Find Z intersection.
+                                       float z = startPos[2] + (endPos[2]-startPos[2])*tmax;
+                                       if (z >= lmin && z <= lmax)
+                                       {
+                                               nextRef = link->ref;
+                                               break;
+                                       }
+                               }
+                               else if (link->side == 1 || link->side == 3)
+                               {
+                                       // Calculate link size.
+                                       const float smin = min(left[0],right[0]);
+                                       const float smax = max(left[0],right[0]);
+                                       const float s = (smax-smin) / 255.0f;
+                                       const float lmin = smin + link->bmin*s;
+                                       const float lmax = smin + link->bmax*s;
+                                       // Find X intersection.
+                                       float x = startPos[0] + (endPos[0]-startPos[0])*tmax;
+                                       if (x >= lmin && x <= lmax)
+                                       {
+                                               nextRef = link->ref;
+                                               break;
+                                       }
+                               }
+                       }
+               }
+               
+               if (!nextRef)
+               {
+                       // No neighbour, we hit a wall.
+                       return n;
+               }
+               
+               // No hit, advance to neighbour polygon.
+               curRef = nextRef;
+       }
+       
+       return n;
+}
+
+int dtTiledNavMesh::findPolysAround(dtTilePolyRef centerRef, const float* centerPos, float radius,
+                                                                       dtTilePolyRef* resultRef, dtTilePolyRef* resultParent, float* resultCost,
+                                                                       const int maxResult)
+{
+       if (!centerRef) return 0;
+       if (!getPolyByRef(centerRef)) return 0;
+       if (!m_nodePool || !m_openList) return 0;
+       
+       m_nodePool->clear();
+       m_openList->clear();
+       
+       dtNode* startNode = m_nodePool->getNode(centerRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = 0;
+       startNode->id = centerRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+       
+       int n = 0;
+       if (n < maxResult)
+       {
+               if (resultRef)
+                       resultRef[n] = startNode->id;
+               if (resultParent)
+                       resultParent[n] = 0;
+               if (resultCost)
+                       resultCost[n] = 0;
+               ++n;
+       }
+       
+       const float radiusSqr = sqr(radius);
+       
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+
+               // Get poly and tile.
+               unsigned int salt, it, ip;
+               dtDecodeTileId(bestNode->id, salt, it, ip);
+               // The API input has been cheked already, skip checking internal data.
+               const dtTileHeader* header = m_tiles[it].header;
+               const dtTilePoly* poly = &header->polys[ip];
+               
+               for (int i = 0; i < poly->nlinks; ++i)
+               {
+                       const dtTileLink* link = &header->links[poly->links+i];
+                       dtTilePolyRef neighbour = link->ref;
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+                               
+                               // Calc distance to the edge.
+                               const float* va = &header->verts[poly->v[link->e]*3];
+                               const float* vb = &header->verts[poly->v[(link->e+1)%poly->nv]*3];
+                               float tseg;
+                               float distSqr = distancePtSegSqr2D(centerPos, va, vb, tseg);
+                               
+                               // If the circle is not touching the next polygon, skip it.
+                               if (distSqr > radiusSqr)
+                                       continue;
+                               
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               // Cost
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, centerPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.total = parent->total + vdist(p0,p1);
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+                               
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= ~DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->total = newNode.total;
+                                       
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               if (n < maxResult)
+                                               {
+                                                       if (resultRef)
+                                                               resultRef[n] = actualNode->id;
+                                                       if (resultParent)
+                                                               resultParent[n] = m_nodePool->getNodeAtIdx(actualNode->pidx)->id;
+                                                       if (resultCost)
+                                                               resultCost[n] = actualNode->total;
+                                                       ++n;
+                                               }
+                                               actualNode->flags = DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       return n;
+}
+
+float dtTiledNavMesh::findDistanceToWall(dtTilePolyRef centerRef, const float* centerPos, float maxRadius,
+                                                float* hitPos, float* hitNormal)
+{
+       if (!centerRef) return 0;
+       if (!getPolyByRef(centerRef)) return 0;
+       if (!m_nodePool || !m_openList) return 0;
+       
+       m_nodePool->clear();
+       m_openList->clear();
+       
+       dtNode* startNode = m_nodePool->getNode(centerRef);
+       startNode->pidx = 0;
+       startNode->cost = 0;
+       startNode->total = 0;
+       startNode->id = centerRef;
+       startNode->flags = DT_NODE_OPEN;
+       m_openList->push(startNode);
+       
+       float radiusSqr = sqr(maxRadius);
+       
+       while (!m_openList->empty())
+       {
+               dtNode* bestNode = m_openList->pop();
+               
+               // Get poly and tile.
+               unsigned int salt, it, ip;
+               dtDecodeTileId(bestNode->id, salt, it, ip);
+               // The API input has been cheked already, skip checking internal data.
+               const dtTileHeader* header = m_tiles[it].header;
+               const dtTilePoly* poly = &header->polys[ip];
+               
+               // Hit test walls.
+               for (int i = 0, j = (int)poly->nv-1; i < (int)poly->nv; j = i++)
+               {
+                       // Skip non-solid edges.
+                       if (poly->n[j] & 0x8000)
+                       {
+                               // Tile border.
+                               bool solid = true;
+                               for (int i = 0; i < poly->nlinks; ++i)
+                               {
+                                       const dtTileLink* link = &header->links[poly->links+i];
+                                       if (link->e == j && link->ref != 0)
+                                       {
+                                               solid = false;
+                                               break;
+                                       }
+                               }
+                               if (!solid) continue;
+                       }
+                       else if (poly->n[j])
+                       {
+                               // Internal edge
+                               continue;
+                       }
+                       
+                       // Calc distance to the edge.
+                       const float* vj = &header->verts[poly->v[j]*3];
+                       const float* vi = &header->verts[poly->v[i]*3];
+                       float tseg;
+                       float distSqr = distancePtSegSqr2D(centerPos, vj, vi, tseg);
+                       
+                       // Edge is too far, skip.
+                       if (distSqr > radiusSqr)
+                               continue;
+                       
+                       // Hit wall, update radius.
+                       radiusSqr = distSqr;
+                       // Calculate hit pos.
+                       hitPos[0] = vj[0] + (vi[0] - vj[0])*tseg;
+                       hitPos[1] = vj[1] + (vi[1] - vj[1])*tseg;
+                       hitPos[2] = vj[2] + (vi[2] - vj[2])*tseg;
+               }
+               
+               for (int i = 0; i < poly->nlinks; ++i)
+               {
+                       const dtTileLink* link = &header->links[poly->links+i];
+                       dtTilePolyRef neighbour = link->ref;
+                       if (neighbour)
+                       {
+                               // Skip parent node.
+                               if (bestNode->pidx && m_nodePool->getNodeAtIdx(bestNode->pidx)->id == neighbour)
+                                       continue;
+                               
+                               // Calc distance to the edge.
+                               const float* va = &header->verts[poly->v[link->e]*3];
+                               const float* vb = &header->verts[poly->v[(link->e+1)%poly->nv]*3];
+                               float tseg;
+                               float distSqr = distancePtSegSqr2D(centerPos, va, vb, tseg);
+                               
+                               // If the circle is not touching the next polygon, skip it.
+                               if (distSqr > radiusSqr)
+                                       continue;
+                               
+                               dtNode* parent = bestNode;
+                               dtNode newNode;
+                               newNode.pidx = m_nodePool->getNodeIdx(parent);
+                               newNode.id = neighbour;
+
+                               float p0[3], p1[3];
+                               if (!parent->pidx)
+                                       vcopy(p0, centerPos);
+                               else
+                                       getEdgeMidPoint(m_nodePool->getNodeAtIdx(parent->pidx)->id, parent->id, p0);
+                               getEdgeMidPoint(parent->id, newNode.id, p1);
+                               newNode.total = parent->total + vdist(p0,p1);
+                               
+                               dtNode* actualNode = m_nodePool->getNode(newNode.id);
+                               if (!actualNode)
+                                       continue;
+                               
+                               if (!((actualNode->flags & DT_NODE_OPEN) && newNode.total > actualNode->total) &&
+                                       !((actualNode->flags & DT_NODE_CLOSED) && newNode.total > actualNode->total))
+                               {
+                                       actualNode->flags &= ~DT_NODE_CLOSED;
+                                       actualNode->pidx = newNode.pidx;
+                                       actualNode->total = newNode.total;
+                                       
+                                       if (actualNode->flags & DT_NODE_OPEN)
+                                       {
+                                               m_openList->modify(actualNode);
+                                       }
+                                       else
+                                       {
+                                               actualNode->flags = DT_NODE_OPEN;
+                                               m_openList->push(actualNode);
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       // Calc hit normal.
+       vsub(hitNormal, centerPos, hitPos);
+       vnormalize(hitNormal);
+       
+       return sqrtf(radiusSqr);
+}
+
+const dtTilePoly* dtTiledNavMesh::getPolyByRef(dtTilePolyRef ref) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return 0;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0;
+       if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0;
+       return &m_tiles[it].header->polys[ip];
+}
+
+const float* dtTiledNavMesh::getPolyVertsByRef(dtTilePolyRef ref) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return 0;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0;
+       if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0;
+       return m_tiles[it].header->verts;
+}
+
+const dtTileLink* dtTiledNavMesh::getPolyLinksByRef(dtTilePolyRef ref) const
+{
+       unsigned int salt, it, ip;
+       dtDecodeTileId(ref, salt, it, ip);
+       if (it >= DT_MAX_TILES) return 0;
+       if (m_tiles[it].salt != salt || m_tiles[it].header == 0) return 0;
+       if (ip >= (unsigned int)m_tiles[it].header->npolys) return 0;
+       return m_tiles[it].header->links;
+}
diff --git a/extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp b/extern/recastnavigation/Detour/Source/DetourTileNavMeshBuilder.cpp
new file mode 100644 (file)
index 0000000..95dd34b
--- /dev/null
@@ -0,0 +1,213 @@
+//
+// Copyright (c) 2009 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