From c7b53c03ae7f7feb45a6023ee5cf764025ebb5e1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?R=C3=A9mi=20Verschelde?= Date: Thu, 17 Dec 2020 16:01:36 +0100 Subject: SCons: Add explicit dependencies on thirdparty code in cloned env Since we clone the environments to build thirdparty code, we don't get an explicit dependency on the build objects produced by that environment. So when we update thirdparty code, Godot code using it is not necessarily rebuilt (I think it is for changed headers, but not for changed .c/.cpp files), which can lead to an invalid compilation output (linking old Godot .o files with a newer, potentially ABI breaking version of thirdparty code). This was only seen as really problematic with bullet updates (leading to crashes when rebuilding Godot after a bullet update without cleaning .o files), but it's safer to fix it everywhere, even if it's a LOT of hacky boilerplate. --- core/SCsub | 20 +- core/crypto/SCsub | 15 +- drivers/png/SCsub | 19 +- drivers/spirv-reflect/SCsub | 8 +- drivers/vulkan/SCsub | 29 ++- modules/assimp/SCsub | 30 ++- modules/basis_universal/SCsub | 17 +- modules/bullet/SCsub | 14 +- modules/cvtt/SCsub | 15 +- modules/denoise/SCsub | 17 +- modules/enet/SCsub | 16 +- modules/etc/SCsub | 15 +- modules/freetype/SCsub | 14 +- modules/gdnavigation/SCsub | 31 ++- modules/glslang/SCsub | 18 +- modules/jpg/SCsub | 17 +- modules/mbedtls/SCsub | 23 ++- modules/meshoptimizer/SCsub | 17 +- modules/ogg/SCsub | 16 +- modules/opensimplex/SCsub | 17 +- modules/opus/SCsub | 19 +- modules/pvr/SCsub | 15 +- modules/regex/SCsub | 18 +- modules/squish/SCsub | 16 +- modules/stb_vorbis/SCsub | 17 +- modules/svg/SCsub | 17 +- modules/text_server_adv/SCsub | 62 +++--- modules/text_server_fb/SCsub | 1 + modules/theora/SCsub | 16 +- modules/tinyexr/SCsub | 17 +- modules/upnp/SCsub | 15 +- modules/vhacd/SCsub | 17 +- modules/vorbis/SCsub | 20 +- modules/webm/SCsub | 15 +- modules/webp/SCsub | 16 +- modules/webrtc/SCsub | 2 - modules/websocket/SCsub | 32 ++- modules/xatlas_unwrap/SCsub | 16 +- platform/android/SCsub | 6 +- scene/SCsub | 18 +- scene/animation/SCsub | 21 +- scene/resources/SCsub | 21 +- servers/camera/SCsub | 2 - thirdparty/rvo2/API.h | 45 ++++ thirdparty/rvo2/Agent.cpp | 425 ++++++++++++++++++++++++++++++++++++++ thirdparty/rvo2/Agent.h | 121 +++++++++++ thirdparty/rvo2/Definitions.h | 55 +++++ thirdparty/rvo2/KdTree.cpp | 152 ++++++++++++++ thirdparty/rvo2/KdTree.h | 124 +++++++++++ thirdparty/rvo2/Vector3.h | 335 ++++++++++++++++++++++++++++++ thirdparty/rvo2/src/API.h | 45 ---- thirdparty/rvo2/src/Agent.cpp | 425 -------------------------------------- thirdparty/rvo2/src/Agent.h | 121 ----------- thirdparty/rvo2/src/Definitions.h | 55 ----- thirdparty/rvo2/src/KdTree.cpp | 152 -------------- thirdparty/rvo2/src/KdTree.h | 124 ----------- thirdparty/rvo2/src/Vector3.h | 335 ------------------------------ 57 files changed, 1859 insertions(+), 1422 deletions(-) create mode 100644 thirdparty/rvo2/API.h create mode 100644 thirdparty/rvo2/Agent.cpp create mode 100644 thirdparty/rvo2/Agent.h create mode 100644 thirdparty/rvo2/Definitions.h create mode 100644 thirdparty/rvo2/KdTree.cpp create mode 100644 thirdparty/rvo2/KdTree.h create mode 100644 thirdparty/rvo2/Vector3.h delete mode 100644 thirdparty/rvo2/src/API.h delete mode 100644 thirdparty/rvo2/src/Agent.cpp delete mode 100644 thirdparty/rvo2/src/Agent.h delete mode 100644 thirdparty/rvo2/src/Definitions.h delete mode 100644 thirdparty/rvo2/src/KdTree.cpp delete mode 100644 thirdparty/rvo2/src/KdTree.h delete mode 100644 thirdparty/rvo2/src/Vector3.h diff --git a/core/SCsub b/core/SCsub index 45918fb520..c9f84a9a00 100644 --- a/core/SCsub +++ b/core/SCsub @@ -38,6 +38,9 @@ with open("script_encryption_key.gen.cpp", "w") as f: # Add required thirdparty code. + +thirdparty_obj = [] + env_thirdparty = env.Clone() env_thirdparty.disable_warnings() @@ -55,7 +58,7 @@ thirdparty_misc_sources = [ "clipper.cpp", ] thirdparty_misc_sources = [thirdparty_misc_dir + file for file in thirdparty_misc_sources] -env_thirdparty.add_source_files(env.core_sources, thirdparty_misc_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_misc_sources) # Zlib library, can be unbundled if env["builtin_zlib"]: @@ -81,14 +84,14 @@ if env["builtin_zlib"]: if env["target"] == "debug": env_thirdparty.Append(CPPDEFINES=["ZLIB_DEBUG"]) - env_thirdparty.add_source_files(env.core_sources, thirdparty_zlib_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_zlib_sources) # Minizip library, could be unbundled in theory # However, our version has some custom modifications, so it won't compile with the system one thirdparty_minizip_dir = "#thirdparty/minizip/" thirdparty_minizip_sources = ["ioapi.c", "unzip.c", "zip.c"] thirdparty_minizip_sources = [thirdparty_minizip_dir + file for file in thirdparty_minizip_sources] -env_thirdparty.add_source_files(env.core_sources, thirdparty_minizip_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_minizip_sources) # Zstd library, can be unbundled in theory # though we currently use some private symbols @@ -130,10 +133,14 @@ if env["builtin_zstd"]: # Also needed in main env includes will trigger warnings env.Append(CPPDEFINES=["ZSTD_STATIC_LINKING_ONLY"]) - env_thirdparty.add_source_files(env.core_sources, thirdparty_zstd_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_zstd_sources) + +env.core_sources += thirdparty_obj + + +# Godot source files -# Godot's own sources env.add_source_files(env.core_sources, "*.cpp") # Certificates @@ -185,3 +192,6 @@ SConscript("error/SCsub") # Build it all as a library lib = env.add_library("core", env.core_sources) env.Prepend(LIBS=[lib]) + +# Needed to force rebuilding the core files when the thirdparty code is updated. +env.Depends(lib, thirdparty_obj) diff --git a/core/crypto/SCsub b/core/crypto/SCsub index da4a9c9381..4f3104d84b 100644 --- a/core/crypto/SCsub +++ b/core/crypto/SCsub @@ -6,6 +6,7 @@ env_crypto = env.Clone() is_builtin = env["builtin_mbedtls"] has_module = env["module_mbedtls_enabled"] +thirdparty_obj = [] if is_builtin or not has_module: # Use our headers for builtin or if the module is not going to be compiled. @@ -35,6 +36,16 @@ if not has_module: "godot_core_mbedtls_platform.c", ] thirdparty_mbedtls_sources = [thirdparty_mbedtls_dir + file for file in thirdparty_mbedtls_sources] - env_thirdparty.add_source_files(env.core_sources, thirdparty_mbedtls_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_mbedtls_sources) + env.core_sources += thirdparty_obj -env_crypto.add_source_files(env.core_sources, "*.cpp") + +# Godot source files + +core_obj = [] + +env_crypto.add_source_files(core_obj, "*.cpp") +env.core_sources += core_obj + +# Needed to force rebuilding the core files when the thirdparty library is updated. +env.Depends(core_obj, thirdparty_obj) diff --git a/drivers/png/SCsub b/drivers/png/SCsub index db08be0c47..26508dc612 100644 --- a/drivers/png/SCsub +++ b/drivers/png/SCsub @@ -5,6 +5,9 @@ Import("env") env_png = env.Clone() # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_libpng"]: thirdparty_dir = "#thirdparty/libpng/" thirdparty_sources = [ @@ -41,7 +44,7 @@ if env["builtin_libpng"]: env_thirdparty = env_png.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.drivers_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) if use_neon: env_neon = env_thirdparty.Clone() @@ -52,9 +55,17 @@ if env["builtin_libpng"]: neon_sources.append(env_neon.Object(thirdparty_dir + "/arm/filter_neon_intrinsics.c")) neon_sources.append(env_neon.Object(thirdparty_dir + "/arm/filter_neon.S")) neon_sources.append(env_neon.Object(thirdparty_dir + "/arm/palette_neon_intrinsics.c")) - env.drivers_sources += neon_sources + thirdparty_obj += neon_sources + + env.drivers_sources += thirdparty_obj + # Godot source files -env_png.add_source_files(env.drivers_sources, "*.cpp") -Export("env") +driver_obj = [] + +env_png.add_source_files(driver_obj, "*.cpp") +env.drivers_sources += driver_obj + +# Needed to force rebuilding the driver files when the thirdparty library is updated. +env.Depends(driver_obj, thirdparty_obj) diff --git a/drivers/spirv-reflect/SCsub b/drivers/spirv-reflect/SCsub index d0ffaf068d..1e7b3de0e6 100644 --- a/drivers/spirv-reflect/SCsub +++ b/drivers/spirv-reflect/SCsub @@ -2,8 +2,7 @@ Import("env") -env_spirv_reflect = env.Clone() -env_spirv_reflect.disable_warnings() +# Thirdparty source files thirdparty_dir = "#thirdparty/spirv-reflect/" thirdparty_sources = [ @@ -12,6 +11,7 @@ thirdparty_sources = [ thirdparty_sources = [thirdparty_dir + file for file in thirdparty_sources] -env_spirv_reflect.add_source_files(env.drivers_sources, thirdparty_sources) +env_thirdparty = env.Clone() +env_thirdparty.disable_warnings() -Export("env") +env_thirdparty.add_source_files(env.drivers_sources, thirdparty_sources) diff --git a/drivers/vulkan/SCsub b/drivers/vulkan/SCsub index 13fcaf16d2..14b9d63204 100644 --- a/drivers/vulkan/SCsub +++ b/drivers/vulkan/SCsub @@ -2,7 +2,7 @@ Import("env") -env.add_source_files(env.drivers_sources, "*.cpp") +thirdparty_obj = [] # FIXME: Refactor all this to reduce code duplication. if env["platform"] == "android": @@ -22,7 +22,8 @@ if env["platform"] == "android": thirdparty_dir = "#thirdparty/vulkan" vma_sources = [thirdparty_dir + "/android/vk_mem_alloc.cpp"] - env_thirdparty.add_source_files(env.drivers_sources, vma_sources) + env_thirdparty.add_source_files(thirdparty_obj, vma_sources) + elif env["platform"] == "iphone": # Use bundled Vulkan headers thirdparty_dir = "#thirdparty/vulkan" @@ -33,7 +34,8 @@ elif env["platform"] == "iphone": env_thirdparty.disable_warnings() vma_sources = [thirdparty_dir + "/vk_mem_alloc.cpp"] - env_thirdparty.add_source_files(env.drivers_sources, vma_sources) + env_thirdparty.add_source_files(thirdparty_obj, vma_sources) + elif env["builtin_vulkan"]: # Use bundled Vulkan headers thirdparty_dir = "#thirdparty/vulkan" @@ -98,8 +100,9 @@ elif env["builtin_vulkan"]: env_thirdparty.AppendUnique(CPPDEFINES=["HAVE_SECURE_GETENV"]) loader_sources = [thirdparty_dir + "/loader/" + file for file in loader_sources] - env_thirdparty.add_source_files(env.drivers_sources, loader_sources) - env_thirdparty.add_source_files(env.drivers_sources, vma_sources) + env_thirdparty.add_source_files(thirdparty_obj, loader_sources) + env_thirdparty.add_source_files(thirdparty_obj, vma_sources) + else: # Always build VMA. thirdparty_dir = "#thirdparty/vulkan" env.Prepend(CPPPATH=[thirdparty_dir]) @@ -109,4 +112,18 @@ else: # Always build VMA. env_thirdparty.disable_warnings() vma_sources = [thirdparty_dir + "/vk_mem_alloc.cpp"] - env_thirdparty.add_source_files(env.drivers_sources, vma_sources) + env_thirdparty.add_source_files(thirdparty_obj, vma_sources) + + +env.drivers_sources += thirdparty_obj + + +# Godot source files + +driver_obj = [] + +env.add_source_files(driver_obj, "*.cpp") +env.drivers_sources += driver_obj + +# Needed to force rebuilding the driver files when the thirdparty code is updated. +env.Depends(driver_obj, thirdparty_obj) diff --git a/modules/assimp/SCsub b/modules/assimp/SCsub index f1d0c742b4..7213efb74d 100644 --- a/modules/assimp/SCsub +++ b/modules/assimp/SCsub @@ -5,8 +5,13 @@ Import("env_modules") env_assimp = env_modules.Clone() +# Thirdparty source files + +thirdparty_obj = [] + # Force bundled version for now, there's no released version of Assimp with # support for ArmaturePopulate which we use from their master branch. + if True: # env['builtin_assimp']: thirdparty_dir = "#thirdparty/assimp" @@ -84,11 +89,20 @@ if True: # env['builtin_assimp']: env_thirdparty = env_assimp.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, Glob("#thirdparty/assimp/code/CApi/*.cpp")) - env_thirdparty.add_source_files(env.modules_sources, Glob("#thirdparty/assimp/code/Common/*.cpp")) - env_thirdparty.add_source_files(env.modules_sources, Glob("#thirdparty/assimp/code/PostProcessing/*.cpp")) - env_thirdparty.add_source_files(env.modules_sources, Glob("#thirdparty/assimp/code/Material/*.cpp")) - env_thirdparty.add_source_files(env.modules_sources, Glob("#thirdparty/assimp/code/FBX/*.cpp")) - -# Godot's own source files -env_assimp.add_source_files(env.modules_sources, "*.cpp") + env_thirdparty.add_source_files(thirdparty_obj, Glob("#thirdparty/assimp/code/CApi/*.cpp")) + env_thirdparty.add_source_files(thirdparty_obj, Glob("#thirdparty/assimp/code/Common/*.cpp")) + env_thirdparty.add_source_files(thirdparty_obj, Glob("#thirdparty/assimp/code/PostProcessing/*.cpp")) + env_thirdparty.add_source_files(thirdparty_obj, Glob("#thirdparty/assimp/code/Material/*.cpp")) + env_thirdparty.add_source_files(thirdparty_obj, Glob("#thirdparty/assimp/code/FBX/*.cpp")) + env.modules_sources += thirdparty_obj + + +# Godot source files + +module_obj = [] + +env_assimp.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/basis_universal/SCsub b/modules/basis_universal/SCsub index dc7b176d24..351628a0e3 100644 --- a/modules/basis_universal/SCsub +++ b/modules/basis_universal/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_basisu = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + # Not unbundled so far since not widespread as shared library thirdparty_dir = "#thirdparty/basis_universal/" tool_sources = [ @@ -41,8 +44,16 @@ if env["target"] == "debug": env_thirdparty = env_basisu.Clone() env_thirdparty.disable_warnings() if env["tools"]: - env_thirdparty.add_source_files(env.modules_sources, tool_sources) -env_thirdparty.add_source_files(env.modules_sources, transcoder_sources) + env_thirdparty.add_source_files(thirdparty_obj, tool_sources) +env_thirdparty.add_source_files(thirdparty_obj, transcoder_sources) +env.modules_sources += thirdparty_obj # Godot source files -env_basisu.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_basisu.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/bullet/SCsub b/modules/bullet/SCsub index 21bdcca18e..bfac0df5b0 100644 --- a/modules/bullet/SCsub +++ b/modules/bullet/SCsub @@ -7,6 +7,8 @@ env_bullet = env_modules.Clone() # Thirdparty source files +thirdparty_obj = [] + if env["builtin_bullet"]: # Build only version 2 for now (as of 2.89) # Sync file list with relevant upstream CMakeLists.txt for each folder. @@ -208,8 +210,16 @@ if env["builtin_bullet"]: env_thirdparty = env_bullet.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj # Godot source files -env_bullet.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_bullet.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/cvtt/SCsub b/modules/cvtt/SCsub index 5438f7ebac..e56177d6e9 100644 --- a/modules/cvtt/SCsub +++ b/modules/cvtt/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_cvtt = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + thirdparty_dir = "#thirdparty/cvtt/" thirdparty_sources = [ "ConvectionKernels.cpp", @@ -17,7 +20,15 @@ env_cvtt.Prepend(CPPPATH=[thirdparty_dir]) env_thirdparty = env_cvtt.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj # Godot source files -env_cvtt.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_cvtt.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/denoise/SCsub b/modules/denoise/SCsub index bf3bd7d073..97feea2b44 100644 --- a/modules/denoise/SCsub +++ b/modules/denoise/SCsub @@ -8,6 +8,9 @@ Import("env_modules") env_oidn = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + thirdparty_dir = "#thirdparty/oidn/" thirdparty_sources = [ "core/api.cpp", @@ -106,7 +109,8 @@ env_oidn.Append( env_thirdparty = env_oidn.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj weights_in_path = thirdparty_dir + "weights/rtlightmap_hdr.tza" weights_out_path = thirdparty_dir + "weights/rtlightmap_hdr.gen.cpp" @@ -114,5 +118,12 @@ weights_out_path = thirdparty_dir + "weights/rtlightmap_hdr.gen.cpp" env_thirdparty.Depends(weights_out_path, weights_in_path) env_thirdparty.CommandNoCache(weights_out_path, weights_in_path, resource_to_cpp.tza_to_cpp) -env_oidn.add_source_files(env.modules_sources, "denoise_wrapper.cpp") -env_modules.add_source_files(env.modules_sources, ["register_types.cpp", "lightmap_denoiser.cpp"]) +# Godot source files + +module_obj = [] + +env_oidn.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/enet/SCsub b/modules/enet/SCsub index c8f4b3885e..580e5a3eb0 100644 --- a/modules/enet/SCsub +++ b/modules/enet/SCsub @@ -7,6 +7,8 @@ env_enet = env_modules.Clone() # Thirdparty source files +thirdparty_obj = [] + if env["builtin_enet"]: thirdparty_dir = "#thirdparty/enet/" thirdparty_sources = [ @@ -26,6 +28,16 @@ if env["builtin_enet"]: env_thirdparty = env_enet.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + + +# Godot source files + +module_obj = [] + +env_enet.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -env_enet.add_source_files(env.modules_sources, "*.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/etc/SCsub b/modules/etc/SCsub index 383bbf83c3..9b46f17916 100644 --- a/modules/etc/SCsub +++ b/modules/etc/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_etc = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + # Not unbundled so far since not widespread as shared library thirdparty_dir = "#thirdparty/etc2comp/" thirdparty_sources = [ @@ -31,7 +34,15 @@ env_etc.Prepend(CPPPATH=[thirdparty_dir]) env_thirdparty = env_etc.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj # Godot source files -env_etc.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_etc.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/freetype/SCsub b/modules/freetype/SCsub index bfc1658bb4..fc2535a6ca 100644 --- a/modules/freetype/SCsub +++ b/modules/freetype/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_freetype = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_freetype"]: thirdparty_dir = "#thirdparty/freetype/" thirdparty_sources = [ @@ -84,6 +87,7 @@ if env["builtin_freetype"]: env_thirdparty = env_freetype.Clone() env_thirdparty.disable_warnings() lib = env_thirdparty.add_library("freetype_builtin", thirdparty_sources) + thirdparty_obj += lib # Needs to be appended to arrive after libscene in the linker call, # but we don't want it to arrive *after* system libs, so manual hack @@ -98,5 +102,13 @@ if env["builtin_freetype"]: if not inserted: env.Append(LIBS=[lib]) + # Godot source files -env_freetype.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_freetype.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/gdnavigation/SCsub b/modules/gdnavigation/SCsub index 877d601c6a..22b5509b32 100644 --- a/modules/gdnavigation/SCsub +++ b/modules/gdnavigation/SCsub @@ -5,6 +5,10 @@ Import("env_modules") env_navigation = env_modules.Clone() +# Thirdparty source files + +thirdparty_obj = [] + # Recast Thirdparty source files if env["builtin_recast"]: thirdparty_dir = "#thirdparty/recastnavigation/Recast/" @@ -23,28 +27,37 @@ if env["builtin_recast"]: ] thirdparty_sources = [thirdparty_dir + file for file in thirdparty_sources] - env_navigation.Prepend(CPPPATH=[thirdparty_dir + "/Include"]) + env_navigation.Prepend(CPPPATH=[thirdparty_dir + "Include"]) env_thirdparty = env_navigation.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) - + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) # RVO Thirdparty source files if env["builtin_rvo2"]: - thirdparty_dir = "#thirdparty/rvo2" + thirdparty_dir = "#thirdparty/rvo2/" thirdparty_sources = [ - "/src/Agent.cpp", - "/src/KdTree.cpp", + "Agent.cpp", + "KdTree.cpp", ] thirdparty_sources = [thirdparty_dir + file for file in thirdparty_sources] - env_navigation.Prepend(CPPPATH=[thirdparty_dir + "/src"]) + env_navigation.Prepend(CPPPATH=[thirdparty_dir]) env_thirdparty = env_navigation.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + + +env.modules_sources += thirdparty_obj # Godot source files -env_navigation.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_navigation.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/glslang/SCsub b/modules/glslang/SCsub index 58c033c75d..182272ffc7 100644 --- a/modules/glslang/SCsub +++ b/modules/glslang/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_glslang = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_glslang"]: thirdparty_dir = "#thirdparty/glslang/" thirdparty_sources = [ @@ -70,7 +73,16 @@ if env["builtin_glslang"]: env_thirdparty = env_glslang.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + + +# Godot source files + +module_obj = [] + +env_glslang.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -# Godot's own source files -env_glslang.add_source_files(env.modules_sources, "*.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/jpg/SCsub b/modules/jpg/SCsub index 8ee8e6dd6e..7c6ceeea29 100644 --- a/modules/jpg/SCsub +++ b/modules/jpg/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_jpg = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + # Not unbundled for now as they are not commonly available as shared library thirdparty_dir = "#thirdparty/jpeg-compressor/" thirdparty_sources = [ @@ -17,7 +20,15 @@ env_jpg.Prepend(CPPPATH=[thirdparty_dir]) env_thirdparty = env_jpg.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj + +# Godot source files + +module_obj = [] + +env_jpg.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -# Godot's own source files -env_jpg.add_source_files(env.modules_sources, "*.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/mbedtls/SCsub b/modules/mbedtls/SCsub index 3b1739c6ee..4fcbe8fb43 100755 --- a/modules/mbedtls/SCsub +++ b/modules/mbedtls/SCsub @@ -5,8 +5,11 @@ Import("env_modules") env_mbed_tls = env_modules.Clone() +# Thirdparty source files + +thirdparty_obj = [] + if env["builtin_mbedtls"]: - # Thirdparty source files thirdparty_sources = [ "aes.c", "aesni.c", @@ -96,11 +99,21 @@ if env["builtin_mbedtls"]: env_thirdparty = env_mbed_tls.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + + +# Godot source files -# Module sources -env_mbed_tls.add_source_files(env.modules_sources, "*.cpp") +module_obj = [] + +env_mbed_tls.add_source_files(module_obj, "*.cpp") if env["tests"]: env_mbed_tls.Append(CPPDEFINES=["TESTS_ENABLED"]) - env_mbed_tls.add_source_files(env.modules_sources, "./tests/*.cpp") + env_mbed_tls.add_source_files(module_obj, "./tests/*.cpp") + +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/meshoptimizer/SCsub b/modules/meshoptimizer/SCsub index 3b1a5f917e..3f86bb4f00 100644 --- a/modules/meshoptimizer/SCsub +++ b/modules/meshoptimizer/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_meshoptimizer = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + thirdparty_dir = "#thirdparty/meshoptimizer/" thirdparty_sources = [ "allocator.cpp", @@ -26,9 +29,17 @@ thirdparty_sources = [ ] thirdparty_sources = [thirdparty_dir + file for file in thirdparty_sources] - env_thirdparty = env_meshoptimizer.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj + +# Godot source files + +module_obj = [] + +env_meshoptimizer.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -env_modules.add_source_files(env.modules_sources, ["register_types.cpp"]) +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/ogg/SCsub b/modules/ogg/SCsub index e768fb4ae8..e415d92498 100644 --- a/modules/ogg/SCsub +++ b/modules/ogg/SCsub @@ -9,6 +9,9 @@ Import("env_modules") env_ogg = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_libogg"]: thirdparty_dir = "#thirdparty/libogg/" thirdparty_sources = [ @@ -21,7 +24,16 @@ if env["builtin_libogg"]: env_thirdparty = env_ogg.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + # Godot source files -env_ogg.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_ogg.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/opensimplex/SCsub b/modules/opensimplex/SCsub index 52d8b145ef..86d77c3dfb 100644 --- a/modules/opensimplex/SCsub +++ b/modules/opensimplex/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_opensimplex = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + thirdparty_dir = "#thirdparty/misc/" thirdparty_sources = [ "open-simplex-noise.c", @@ -16,7 +19,15 @@ env_opensimplex.Prepend(CPPPATH=[thirdparty_dir]) env_thirdparty = env_opensimplex.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj + +# Godot source files + +module_obj = [] + +env_opensimplex.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -# Godot's own source files -env_opensimplex.add_source_files(env.modules_sources, "*.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/opus/SCsub b/modules/opus/SCsub index 52c61fa708..1437cd86df 100644 --- a/modules/opus/SCsub +++ b/modules/opus/SCsub @@ -9,6 +9,10 @@ Import("env_modules") env_opus = env_modules.Clone() +# Thirdparty source files + +thirdparty_obj = [] + # Thirdparty source files if env["builtin_opus"]: thirdparty_dir = "#thirdparty/opus/" @@ -233,7 +237,16 @@ if env["builtin_opus"]: env_thirdparty = env_opus.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + + +# Godot source files + +module_obj = [] + +env_opus.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -# Module files -env_opus.add_source_files(env.modules_sources, "register_types.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/pvr/SCsub b/modules/pvr/SCsub index e0baf851f1..36052cffed 100644 --- a/modules/pvr/SCsub +++ b/modules/pvr/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_pvr = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + # Not unbundled so far since not widespread as shared library thirdparty_dir = "#thirdparty/pvrtccompressor/" thirdparty_sources = [ @@ -21,7 +24,15 @@ env_pvr.Prepend(CPPPATH=[thirdparty_dir]) env_thirdparty = env_pvr.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj # Godot source files -env_pvr.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_pvr.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/regex/SCsub b/modules/regex/SCsub index 2afacc1d9c..deb9db7591 100644 --- a/modules/regex/SCsub +++ b/modules/regex/SCsub @@ -5,6 +5,10 @@ Import("env_modules") env_regex = env_modules.Clone() +# Thirdparty source files + +thirdparty_obj = [] + if env["builtin_pcre2"]: thirdparty_dir = "#thirdparty/pcre2/src/" thirdparty_flags = ["PCRE2_STATIC", "HAVE_CONFIG_H", "SUPPORT_UNICODE"] @@ -52,11 +56,21 @@ if env["builtin_pcre2"]: env_pcre2 = env_regex.Clone() env_pcre2.disable_warnings() env_pcre2["OBJSUFFIX"] = "_" + width + env_pcre2["OBJSUFFIX"] - env_pcre2.add_source_files(env.modules_sources, thirdparty_sources) env_pcre2.Append(CPPDEFINES=[("PCRE2_CODE_UNIT_WIDTH", width)]) + env_pcre2.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj pcre2_builtin("16") pcre2_builtin("32") + +# Godot source files + +module_obj = [] + env_regex.Append(CPPDEFINES=[("PCRE2_CODE_UNIT_WIDTH", 0)]) -env_regex.add_source_files(env.modules_sources, "*.cpp") +env_regex.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/squish/SCsub b/modules/squish/SCsub index b31032403f..c9e29911d8 100644 --- a/modules/squish/SCsub +++ b/modules/squish/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_squish = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_squish"]: thirdparty_dir = "#thirdparty/squish/" thirdparty_sources = [ @@ -26,7 +29,16 @@ if env["builtin_squish"]: env_thirdparty = env_squish.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + # Godot source files -env_squish.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_squish.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/stb_vorbis/SCsub b/modules/stb_vorbis/SCsub index 266c87c802..8fddb23dc8 100644 --- a/modules/stb_vorbis/SCsub +++ b/modules/stb_vorbis/SCsub @@ -6,11 +6,22 @@ Import("env_modules") env_stb_vorbis = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + thirdparty_sources = ["#thirdparty/misc/stb_vorbis.c"] env_thirdparty = env_stb_vorbis.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj + +# Godot source files + +module_obj = [] + +env_stb_vorbis.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -# Godot's own source files -env_stb_vorbis.add_source_files(env.modules_sources, "*.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/svg/SCsub b/modules/svg/SCsub index 0bfba34fe5..c7228a8d0b 100644 --- a/modules/svg/SCsub +++ b/modules/svg/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_svg = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + thirdparty_dir = "#thirdparty/nanosvg/" thirdparty_sources = [ "nanosvg.cc", @@ -16,7 +19,15 @@ env_svg.Prepend(CPPPATH=[thirdparty_dir]) env_thirdparty = env_svg.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj + +# Godot source files + +module_obj = [] + +env_svg.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -# Godot's own source files -env_svg.add_source_files(env.modules_sources, "*.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/text_server_adv/SCsub b/modules/text_server_adv/SCsub index 7403b01a4c..3589c8546d 100644 --- a/modules/text_server_adv/SCsub +++ b/modules/text_server_adv/SCsub @@ -35,10 +35,14 @@ def make_icu_data(target, source, env): g.write("#endif") +# Thirdparty source files + +thirdparty_obj = [] + if env["builtin_harfbuzz"]: env_harfbuzz = env_modules.Clone() + env_harfbuzz.disable_warnings() - # Thirdparty source files thirdparty_dir = "#thirdparty/harfbuzz/" thirdparty_sources = [ "src/hb-aat-layout.cc", @@ -107,6 +111,15 @@ if env["builtin_harfbuzz"]: ] thirdparty_sources = [thirdparty_dir + file for file in thirdparty_sources] + env_harfbuzz.Append( + CPPPATH=[ + "#thirdparty/harfbuzz/src", + "#thirdparty/freetype/include", + "#thirdparty/graphite/include", + "#thirdparty/icu4c/common/", + ] + ) + if env["platform"] == "android" or env["platform"] == "linuxbsd" or env["platform"] == "server": env_harfbuzz.Append(CCFLAGS=["-DHAVE_PTHREAD"]) @@ -116,14 +129,6 @@ if env["builtin_harfbuzz"]: else: env_harfbuzz.Append(CCFLAGS=["-DHB_NO_MT"]) - env_harfbuzz.Append( - CPPPATH=[ - "#thirdparty/harfbuzz/src", - "#thirdparty/freetype/include", - "#thirdparty/graphite/include", - "#thirdparty/icu4c/common/", - ] - ) env_harfbuzz.Append( CCFLAGS=[ "-DHAVE_ICU_BUILTIN", @@ -133,10 +138,9 @@ if env["builtin_harfbuzz"]: "-DGRAPHITE2_STATIC", ] ) - env_harfbuzz.disable_warnings() - env_thirdparty = env_harfbuzz.Clone() - env_thirdparty.disable_warnings() - lib = env_thirdparty.add_library("harfbuzz_builtin", thirdparty_sources) + + lib = env_harfbuzz.add_library("harfbuzz_builtin", thirdparty_sources) + thirdparty_obj += lib # Needs to be appended to arrive after libscene in the linker call, # but we don't want it to arrive *after* system libs, so manual hack @@ -151,10 +155,11 @@ if env["builtin_harfbuzz"]: if not inserted: env.Append(LIBS=[lib]) + if env["builtin_graphite"]: env_graphite = env_modules.Clone() + env_graphite.disable_warnings() - # Thirdparty source files thirdparty_dir = "#thirdparty/graphite/" thirdparty_sources = [ "src/gr_char_info.cpp", @@ -203,10 +208,9 @@ if env["builtin_graphite"]: "-DGRAPHITE2_NFILEFACE", ] ) - env_graphite.disable_warnings() - env_thirdparty = env_graphite.Clone() - env_thirdparty.disable_warnings() - lib = env_thirdparty.add_library("graphite_builtin", thirdparty_sources) + + lib = env_graphite.add_library("graphite_builtin", thirdparty_sources) + thirdparty_obj += lib # Needs to be appended to arrive after libscene in the linker call, # but we don't want it to arrive *after* system libs, so manual hack @@ -221,12 +225,12 @@ if env["builtin_graphite"]: if not inserted: env.Append(LIBS=[lib]) + if env["builtin_icu"]: env_icu = env_modules.Clone() + env_icu.disable_warnings() - # Thirdparty source files thirdparty_dir = "#thirdparty/icu4c/" - # Thirdparty source files thirdparty_sources = [ "common/appendable.cpp", "common/bmpset.cpp", @@ -457,10 +461,8 @@ if env["builtin_icu"]: ] ) - env_icu.disable_warnings() - env_thirdparty = env_icu.Clone() - env_thirdparty.disable_warnings() - lib = env_thirdparty.add_library("icu_builtin", thirdparty_sources) + lib = env_icu.add_library("icu_builtin", thirdparty_sources) + thirdparty_obj += lib # Needs to be appended to arrive after libscene in the linker call, # but we don't want it to arrive *after* system libs, so manual hack @@ -475,6 +477,11 @@ if env["builtin_icu"]: if not inserted: env.Append(LIBS=[lib]) + +# Godot source files + +module_obj = [] + if env_text_server_adv["tools"]: env_text_server_adv.Append(CXXFLAGS=["-DICU_STATIC_DATA"]) @@ -486,4 +493,9 @@ env_text_server_adv.Append( "#thirdparty/icu4c/common/", ] ) -env_text_server_adv.add_source_files(env.modules_sources, "*.cpp") + +env_text_server_adv.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/text_server_fb/SCsub b/modules/text_server_fb/SCsub index 7650e27063..03eccbe7bd 100644 --- a/modules/text_server_fb/SCsub +++ b/modules/text_server_fb/SCsub @@ -9,4 +9,5 @@ env_text_server_fb.Append( "#thirdparty/freetype/include", ] ) + env_text_server_fb.add_source_files(env.modules_sources, "*.cpp") diff --git a/modules/theora/SCsub b/modules/theora/SCsub index a01e65b4b0..6038ea086a 100644 --- a/modules/theora/SCsub +++ b/modules/theora/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_theora = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_libtheora"]: thirdparty_dir = "#thirdparty/libtheora/" thirdparty_sources = [ @@ -80,7 +83,16 @@ if env["builtin_libtheora"]: env_thirdparty = env_theora.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + # Godot source files -env_theora.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_theora.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/tinyexr/SCsub b/modules/tinyexr/SCsub index 84b3b4015b..30bde96fb4 100644 --- a/modules/tinyexr/SCsub +++ b/modules/tinyexr/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_tinyexr = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + # Not unbundled for now as they are not commonly available as shared library thirdparty_dir = "#thirdparty/tinyexr/" thirdparty_sources = [ @@ -20,7 +23,15 @@ env_tinyexr.Append(CPPDEFINES=["TINYEXR_USE_THREAD"]) env_thirdparty = env_tinyexr.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj + +# Godot source files + +module_obj = [] + +env_tinyexr.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -# Godot's own source files -env_tinyexr.add_source_files(env.modules_sources, "*.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/upnp/SCsub b/modules/upnp/SCsub index 2e129e15ca..bc0b215be3 100644 --- a/modules/upnp/SCsub +++ b/modules/upnp/SCsub @@ -7,6 +7,8 @@ env_upnp = env_modules.Clone() # Thirdparty source files +thirdparty_obj = [] + if env["builtin_miniupnpc"]: thirdparty_dir = "#thirdparty/miniupnpc/" thirdparty_sources = [ @@ -31,7 +33,16 @@ if env["builtin_miniupnpc"]: env_thirdparty = env_upnp.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + # Godot source files -env_upnp.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_upnp.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/vhacd/SCsub b/modules/vhacd/SCsub index ecd432b275..1ff4122114 100644 --- a/modules/vhacd/SCsub +++ b/modules/vhacd/SCsub @@ -7,6 +7,8 @@ env_vhacd = env_modules.Clone() # Thirdparty source files +thirdparty_obj = [] + thirdparty_dir = "#thirdparty/vhacd/" thirdparty_sources = [ @@ -24,10 +26,19 @@ thirdparty_sources = [ thirdparty_sources = [thirdparty_dir + file for file in thirdparty_sources] -env_vhacd.Prepend(CPPPATH=[thirdparty_dir + "/inc"]) +env_vhacd.Prepend(CPPPATH=[thirdparty_dir + "inc"]) env_thirdparty = env_vhacd.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj + +# Godot source files + +module_obj = [] + +env_vhacd.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -env_vhacd.add_source_files(env.modules_sources, "*.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/vorbis/SCsub b/modules/vorbis/SCsub index 05d46757d3..bc31fff066 100644 --- a/modules/vorbis/SCsub +++ b/modules/vorbis/SCsub @@ -8,9 +8,10 @@ Import("env_modules") env_vorbis = env_modules.Clone() -stub = True - # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_libvorbis"]: thirdparty_dir = "#thirdparty/libvorbis/" thirdparty_sources = [ @@ -51,7 +52,16 @@ if env["builtin_libvorbis"]: env_thirdparty = env_vorbis.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + + +# Godot source files + +module_obj = [] + +env_vorbis.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj -# Module files -env_vorbis.add_source_files(env.modules_sources, "register_types.cpp") +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/webm/SCsub b/modules/webm/SCsub index 247b4ead37..44e80e2870 100644 --- a/modules/webm/SCsub +++ b/modules/webm/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_webm = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + thirdparty_dir = "#thirdparty/libsimplewebm/" thirdparty_sources = [ "libwebm/mkvparser/mkvparser.cc", @@ -31,7 +34,15 @@ if env["builtin_libvpx"]: env_thirdparty = env_webm.Clone() env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.modules_sources += thirdparty_obj # Godot source files -env_webm.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_webm.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/webp/SCsub b/modules/webp/SCsub index 58f2bb35e6..4c0c2f7893 100644 --- a/modules/webp/SCsub +++ b/modules/webp/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_webp = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_libwebp"]: thirdparty_dir = "#thirdparty/libwebp/" thirdparty_sources = [ @@ -130,7 +133,16 @@ if env["builtin_libwebp"]: env_thirdparty = env_webp.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + # Godot source files -env_webp.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_webp.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/webrtc/SCsub b/modules/webrtc/SCsub index 4f870ddb2f..31b8a73bf2 100644 --- a/modules/webrtc/SCsub +++ b/modules/webrtc/SCsub @@ -3,8 +3,6 @@ Import("env") Import("env_modules") -# Thirdparty source files - env_webrtc = env_modules.Clone() use_gdnative = env_webrtc["module_gdnative_enabled"] diff --git a/modules/websocket/SCsub b/modules/websocket/SCsub index 13e51a39c0..4c022c43cf 100644 --- a/modules/websocket/SCsub +++ b/modules/websocket/SCsub @@ -5,28 +5,44 @@ Import("env_modules") env_ws = env_modules.Clone() +thirdparty_obj = [] + if env["platform"] == "javascript": # Our JavaScript/C++ interface. env.AddJSLibraries(["library_godot_websocket.js"]) + elif env["builtin_wslay"]: # Thirdparty source files - wslay_dir = "#thirdparty/wslay/" - wslay_sources = [ + thirdparty_dir = "#thirdparty/wslay/" + thirdparty_sources = [ "wslay_net.c", "wslay_event.c", "wslay_queue.c", "wslay_stack.c", "wslay_frame.c", ] - wslay_sources = [wslay_dir + s for s in wslay_sources] - env_ws.Prepend(CPPPATH=[wslay_dir + "includes/"]) + thirdparty_sources = [thirdparty_dir + s for s in thirdparty_sources] + + env_ws.Prepend(CPPPATH=[thirdparty_dir + "includes/"]) env_ws.Append(CPPDEFINES=["HAVE_CONFIG_H"]) + if env["platform"] == "windows" or env["platform"] == "uwp": env_ws.Append(CPPDEFINES=["HAVE_WINSOCK2_H"]) else: env_ws.Append(CPPDEFINES=["HAVE_NETINET_IN_H"]) - env_wslay = env_ws.Clone() - env_wslay.disable_warnings() - env_wslay.add_source_files(env.modules_sources, wslay_sources) -env_ws.add_source_files(env.modules_sources, "*.cpp") + env_thirdparty = env_ws.Clone() + env_thirdparty.disable_warnings() + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + + +# Godot source files + +module_obj = [] + +env_ws.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/modules/xatlas_unwrap/SCsub b/modules/xatlas_unwrap/SCsub index c659349d05..aa6bdaea33 100644 --- a/modules/xatlas_unwrap/SCsub +++ b/modules/xatlas_unwrap/SCsub @@ -6,6 +6,9 @@ Import("env_modules") env_xatlas_unwrap = env_modules.Clone() # Thirdparty source files + +thirdparty_obj = [] + if env["builtin_xatlas"]: thirdparty_dir = "#thirdparty/xatlas/" thirdparty_sources = [ @@ -17,7 +20,16 @@ if env["builtin_xatlas"]: env_thirdparty = env_xatlas_unwrap.Clone() env_thirdparty.disable_warnings() - env_thirdparty.add_source_files(env.modules_sources, thirdparty_sources) + env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) + env.modules_sources += thirdparty_obj + # Godot source files -env_xatlas_unwrap.add_source_files(env.modules_sources, "*.cpp") + +module_obj = [] + +env_xatlas_unwrap.add_source_files(module_obj, "*.cpp") +env.modules_sources += module_obj + +# Needed to force rebuilding the module files when the thirdparty library is updated. +env.Depends(module_obj, thirdparty_obj) diff --git a/platform/android/SCsub b/platform/android/SCsub index d8013b0baf..7e9dac926c 100644 --- a/platform/android/SCsub +++ b/platform/android/SCsub @@ -29,10 +29,14 @@ for x in android_files: env_thirdparty = env_android.Clone() env_thirdparty.disable_warnings() -android_objects.append(env_thirdparty.SharedObject("#thirdparty/misc/ifaddrs-android.cc")) +thirdparty_obj = env_thirdparty.SharedObject("#thirdparty/misc/ifaddrs-android.cc") +android_objects.append(thirdparty_obj) lib = env_android.add_shared_library("#bin/libgodot", [android_objects], SHLIBSUFFIX=env["SHLIBSUFFIX"]) +# Needed to force rebuilding the platform files when the thirdparty code is updated. +env.Depends(lib, thirdparty_obj) + lib_arch_dir = "" if env["android_arch"] == "armv7": lib_arch_dir = "armeabi-v7a" diff --git a/scene/SCsub b/scene/SCsub index f9fc00f3f2..ccd2bab8ff 100644 --- a/scene/SCsub +++ b/scene/SCsub @@ -4,24 +4,9 @@ Import("env") env.scene_sources = [] -# Thirdparty code -thirdparty_dir = "#thirdparty/misc/" -thirdparty_sources = [ - # C++ sources - "easing_equations.cpp", - # C sources - "mikktspace.c", -] -thirdparty_sources = [thirdparty_dir + file for file in thirdparty_sources] - -env_thirdparty = env.Clone() -env_thirdparty.disable_warnings() -env_thirdparty.add_source_files(env.scene_sources, thirdparty_sources) - -# Godot's own sources +# Godot source files env.add_source_files(env.scene_sources, "*.cpp") - # Chain load SCsubs SConscript("main/SCsub") SConscript("gui/SCsub") @@ -32,7 +17,6 @@ SConscript("audio/SCsub") SConscript("resources/SCsub") SConscript("debugger/SCsub") - # Build it all as a library lib = env.add_library("scene", env.scene_sources) env.Prepend(LIBS=[lib]) diff --git a/scene/animation/SCsub b/scene/animation/SCsub index fc61250247..cc33a5af84 100644 --- a/scene/animation/SCsub +++ b/scene/animation/SCsub @@ -2,4 +2,23 @@ Import("env") -env.add_source_files(env.scene_sources, "*.cpp") +# Thirdparty code + +thirdparty_obj = [] + +thirdparty_sources = "#thirdparty/misc/easing_equations.cpp" + +env_thirdparty = env.Clone() +env_thirdparty.disable_warnings() +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.scene_sources += thirdparty_obj + +# Godot source files + +scene_obj = [] + +env.add_source_files(scene_obj, "*.cpp") +env.scene_sources += scene_obj + +# Needed to force rebuilding the scene files when the thirdparty code is updated. +env.Depends(scene_obj, thirdparty_obj) diff --git a/scene/resources/SCsub b/scene/resources/SCsub index 3a86b22835..f4dc7a46fb 100644 --- a/scene/resources/SCsub +++ b/scene/resources/SCsub @@ -2,6 +2,25 @@ Import("env") -env.add_source_files(env.scene_sources, "*.cpp") +# Thirdparty code + +thirdparty_obj = [] + +thirdparty_sources = "#thirdparty/misc/mikktspace.c" + +env_thirdparty = env.Clone() +env_thirdparty.disable_warnings() +env_thirdparty.add_source_files(thirdparty_obj, thirdparty_sources) +env.scene_sources += thirdparty_obj + +# Godot source files + +scene_obj = [] + +env.add_source_files(scene_obj, "*.cpp") +env.scene_sources += scene_obj + +# Needed to force rebuilding the scene files when the thirdparty code is updated. +env.Depends(scene_obj, thirdparty_obj) SConscript("default_theme/SCsub") diff --git a/servers/camera/SCsub b/servers/camera/SCsub index c949f3bb25..86681f9c74 100644 --- a/servers/camera/SCsub +++ b/servers/camera/SCsub @@ -3,5 +3,3 @@ Import("env") env.add_source_files(env.servers_sources, "*.cpp") - -Export("env") diff --git a/thirdparty/rvo2/API.h b/thirdparty/rvo2/API.h new file mode 100644 index 0000000000..c64efb452c --- /dev/null +++ b/thirdparty/rvo2/API.h @@ -0,0 +1,45 @@ +/* + * API.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to . + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * + */ + +/** + * \file API.h + * \brief Contains definitions related to Microsoft Windows. + */ + +#ifndef RVO_API_H_ +#define RVO_API_H_ + +// -- GODOT start -- +#define RVO_API +// -- GODOT end -- + +#endif /* RVO_API_H_ */ diff --git a/thirdparty/rvo2/Agent.cpp b/thirdparty/rvo2/Agent.cpp new file mode 100644 index 0000000000..851d780758 --- /dev/null +++ b/thirdparty/rvo2/Agent.cpp @@ -0,0 +1,425 @@ +/* + * Agent.cpp + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to . + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * + */ + +#include "Agent.h" + +#include +#include + +#include "Definitions.h" +#include "KdTree.h" + +namespace RVO { +/** + * \brief A sufficiently small positive number. + */ +const float RVO_EPSILON = 0.00001f; + +/** + * \brief Defines a directed line. + */ +class Line { +public: + /** + * \brief The direction of the directed line. + */ + Vector3 direction; + + /** + * \brief A point on the directed line. + */ + Vector3 point; +}; + +/** + * \brief Solves a one-dimensional linear program on a specified line subject to linear constraints defined by planes and a spherical constraint. + * \param planes Planes defining the linear constraints. + * \param planeNo The plane on which the line lies. + * \param line The line on which the 1-d linear program is solved + * \param radius The radius of the spherical constraint. + * \param optVelocity The optimization velocity. + * \param directionOpt True if the direction should be optimized. + * \param result A reference to the result of the linear program. + * \return True if successful. + */ +bool linearProgram1(const std::vector &planes, size_t planeNo, const Line &line, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); + +/** + * \brief Solves a two-dimensional linear program on a specified plane subject to linear constraints defined by planes and a spherical constraint. + * \param planes Planes defining the linear constraints. + * \param planeNo The plane on which the 2-d linear program is solved + * \param radius The radius of the spherical constraint. + * \param optVelocity The optimization velocity. + * \param directionOpt True if the direction should be optimized. + * \param result A reference to the result of the linear program. + * \return True if successful. + */ +bool linearProgram2(const std::vector &planes, size_t planeNo, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); + +/** + * \brief Solves a three-dimensional linear program subject to linear constraints defined by planes and a spherical constraint. + * \param planes Planes defining the linear constraints. + * \param radius The radius of the spherical constraint. + * \param optVelocity The optimization velocity. + * \param directionOpt True if the direction should be optimized. + * \param result A reference to the result of the linear program. + * \return The number of the plane it fails on, and the number of planes if successful. + */ +size_t linearProgram3(const std::vector &planes, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); + +/** + * \brief Solves a four-dimensional linear program subject to linear constraints defined by planes and a spherical constraint. + * \param planes Planes defining the linear constraints. + * \param beginPlane The plane on which the 3-d linear program failed. + * \param radius The radius of the spherical constraint. + * \param result A reference to the result of the linear program. + */ +void linearProgram4(const std::vector &planes, size_t beginPlane, float radius, Vector3 &result); + +Agent::Agent() : + id_(0), maxNeighbors_(0), maxSpeed_(0.0f), neighborDist_(0.0f), radius_(0.0f), timeHorizon_(0.0f), ignore_y_(false) {} + +void Agent::computeNeighbors(KdTree *kdTree_) { + agentNeighbors_.clear(); + if (maxNeighbors_ > 0) { + kdTree_->computeAgentNeighbors(this, neighborDist_ * neighborDist_); + } +} + +#define ABS(m_v) (((m_v) < 0) ? (-(m_v)) : (m_v)) +void Agent::computeNewVelocity(float timeStep) { + orcaPlanes_.clear(); + const float invTimeHorizon = 1.0f / timeHorizon_; + + /* Create agent ORCA planes. */ + for (size_t i = 0; i < agentNeighbors_.size(); ++i) { + const Agent *const other = agentNeighbors_[i].second; + + Vector3 relativePosition = other->position_ - position_; + Vector3 relativeVelocity = velocity_ - other->velocity_; + const float combinedRadius = radius_ + other->radius_; + + // This is a Godot feature that allow the agents to avoid the collision + // by moving only on the horizontal plane relative to the player velocity. + if (ignore_y_) { + // Skip if these are in two different heights + if (ABS(relativePosition[1]) > combinedRadius * 2) { + continue; + } + relativePosition[1] = 0; + relativeVelocity[1] = 0; + } + + const float distSq = absSq(relativePosition); + const float combinedRadiusSq = sqr(combinedRadius); + + Plane plane; + Vector3 u; + + if (distSq > combinedRadiusSq) { + /* No collision. */ + const Vector3 w = relativeVelocity - invTimeHorizon * relativePosition; + /* Vector from cutoff center to relative velocity. */ + const float wLengthSq = absSq(w); + + const float dotProduct = w * relativePosition; + + if (dotProduct < 0.0f && sqr(dotProduct) > combinedRadiusSq * wLengthSq) { + /* Project on cut-off circle. */ + const float wLength = std::sqrt(wLengthSq); + const Vector3 unitW = w / wLength; + + plane.normal = unitW; + u = (combinedRadius * invTimeHorizon - wLength) * unitW; + } else { + /* Project on cone. */ + const float a = distSq; + const float b = relativePosition * relativeVelocity; + const float c = absSq(relativeVelocity) - absSq(cross(relativePosition, relativeVelocity)) / (distSq - combinedRadiusSq); + const float t = (b + std::sqrt(sqr(b) - a * c)) / a; + const Vector3 w = relativeVelocity - t * relativePosition; + const float wLength = abs(w); + const Vector3 unitW = w / wLength; + + plane.normal = unitW; + u = (combinedRadius * t - wLength) * unitW; + } + } else { + /* Collision. */ + const float invTimeStep = 1.0f / timeStep; + const Vector3 w = relativeVelocity - invTimeStep * relativePosition; + const float wLength = abs(w); + const Vector3 unitW = w / wLength; + + plane.normal = unitW; + u = (combinedRadius * invTimeStep - wLength) * unitW; + } + + plane.point = velocity_ + 0.5f * u; + orcaPlanes_.push_back(plane); + } + + const size_t planeFail = linearProgram3(orcaPlanes_, maxSpeed_, prefVelocity_, false, newVelocity_); + + if (planeFail < orcaPlanes_.size()) { + linearProgram4(orcaPlanes_, planeFail, maxSpeed_, newVelocity_); + } + + if (ignore_y_) { + // Not 100% necessary, but better to have. + newVelocity_[1] = prefVelocity_[1]; + } +} + +void Agent::insertAgentNeighbor(const Agent *agent, float &rangeSq) { + if (this != agent) { + const float distSq = absSq(position_ - agent->position_); + + if (distSq < rangeSq) { + if (agentNeighbors_.size() < maxNeighbors_) { + agentNeighbors_.push_back(std::make_pair(distSq, agent)); + } + + size_t i = agentNeighbors_.size() - 1; + + while (i != 0 && distSq < agentNeighbors_[i - 1].first) { + agentNeighbors_[i] = agentNeighbors_[i - 1]; + --i; + } + + agentNeighbors_[i] = std::make_pair(distSq, agent); + + if (agentNeighbors_.size() == maxNeighbors_) { + rangeSq = agentNeighbors_.back().first; + } + } + } +} + +bool linearProgram1(const std::vector &planes, size_t planeNo, const Line &line, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { + const float dotProduct = line.point * line.direction; + const float discriminant = sqr(dotProduct) + sqr(radius) - absSq(line.point); + + if (discriminant < 0.0f) { + /* Max speed sphere fully invalidates line. */ + return false; + } + + const float sqrtDiscriminant = std::sqrt(discriminant); + float tLeft = -dotProduct - sqrtDiscriminant; + float tRight = -dotProduct + sqrtDiscriminant; + + for (size_t i = 0; i < planeNo; ++i) { + const float numerator = (planes[i].point - line.point) * planes[i].normal; + const float denominator = line.direction * planes[i].normal; + + if (sqr(denominator) <= RVO_EPSILON) { + /* Lines line is (almost) parallel to plane i. */ + if (numerator > 0.0f) { + return false; + } else { + continue; + } + } + + const float t = numerator / denominator; + + if (denominator >= 0.0f) { + /* Plane i bounds line on the left. */ + tLeft = std::max(tLeft, t); + } else { + /* Plane i bounds line on the right. */ + tRight = std::min(tRight, t); + } + + if (tLeft > tRight) { + return false; + } + } + + if (directionOpt) { + /* Optimize direction. */ + if (optVelocity * line.direction > 0.0f) { + /* Take right extreme. */ + result = line.point + tRight * line.direction; + } else { + /* Take left extreme. */ + result = line.point + tLeft * line.direction; + } + } else { + /* Optimize closest point. */ + const float t = line.direction * (optVelocity - line.point); + + if (t < tLeft) { + result = line.point + tLeft * line.direction; + } else if (t > tRight) { + result = line.point + tRight * line.direction; + } else { + result = line.point + t * line.direction; + } + } + + return true; +} + +bool linearProgram2(const std::vector &planes, size_t planeNo, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { + const float planeDist = planes[planeNo].point * planes[planeNo].normal; + const float planeDistSq = sqr(planeDist); + const float radiusSq = sqr(radius); + + if (planeDistSq > radiusSq) { + /* Max speed sphere fully invalidates plane planeNo. */ + return false; + } + + const float planeRadiusSq = radiusSq - planeDistSq; + + const Vector3 planeCenter = planeDist * planes[planeNo].normal; + + if (directionOpt) { + /* Project direction optVelocity on plane planeNo. */ + const Vector3 planeOptVelocity = optVelocity - (optVelocity * planes[planeNo].normal) * planes[planeNo].normal; + const float planeOptVelocityLengthSq = absSq(planeOptVelocity); + + if (planeOptVelocityLengthSq <= RVO_EPSILON) { + result = planeCenter; + } else { + result = planeCenter + std::sqrt(planeRadiusSq / planeOptVelocityLengthSq) * planeOptVelocity; + } + } else { + /* Project point optVelocity on plane planeNo. */ + result = optVelocity + ((planes[planeNo].point - optVelocity) * planes[planeNo].normal) * planes[planeNo].normal; + + /* If outside planeCircle, project on planeCircle. */ + if (absSq(result) > radiusSq) { + const Vector3 planeResult = result - planeCenter; + const float planeResultLengthSq = absSq(planeResult); + result = planeCenter + std::sqrt(planeRadiusSq / planeResultLengthSq) * planeResult; + } + } + + for (size_t i = 0; i < planeNo; ++i) { + if (planes[i].normal * (planes[i].point - result) > 0.0f) { + /* Result does not satisfy constraint i. Compute new optimal result. */ + /* Compute intersection line of plane i and plane planeNo. */ + Vector3 crossProduct = cross(planes[i].normal, planes[planeNo].normal); + + if (absSq(crossProduct) <= RVO_EPSILON) { + /* Planes planeNo and i are (almost) parallel, and plane i fully invalidates plane planeNo. */ + return false; + } + + Line line; + line.direction = normalize(crossProduct); + const Vector3 lineNormal = cross(line.direction, planes[planeNo].normal); + line.point = planes[planeNo].point + (((planes[i].point - planes[planeNo].point) * planes[i].normal) / (lineNormal * planes[i].normal)) * lineNormal; + + if (!linearProgram1(planes, i, line, radius, optVelocity, directionOpt, result)) { + return false; + } + } + } + + return true; +} + +size_t linearProgram3(const std::vector &planes, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { + if (directionOpt) { + /* Optimize direction. Note that the optimization velocity is of unit length in this case. */ + result = optVelocity * radius; + } else if (absSq(optVelocity) > sqr(radius)) { + /* Optimize closest point and outside circle. */ + result = normalize(optVelocity) * radius; + } else { + /* Optimize closest point and inside circle. */ + result = optVelocity; + } + + for (size_t i = 0; i < planes.size(); ++i) { + if (planes[i].normal * (planes[i].point - result) > 0.0f) { + /* Result does not satisfy constraint i. Compute new optimal result. */ + const Vector3 tempResult = result; + + if (!linearProgram2(planes, i, radius, optVelocity, directionOpt, result)) { + result = tempResult; + return i; + } + } + } + + return planes.size(); +} + +void linearProgram4(const std::vector &planes, size_t beginPlane, float radius, Vector3 &result) { + float distance = 0.0f; + + for (size_t i = beginPlane; i < planes.size(); ++i) { + if (planes[i].normal * (planes[i].point - result) > distance) { + /* Result does not satisfy constraint of plane i. */ + std::vector projPlanes; + + for (size_t j = 0; j < i; ++j) { + Plane plane; + + const Vector3 crossProduct = cross(planes[j].normal, planes[i].normal); + + if (absSq(crossProduct) <= RVO_EPSILON) { + /* Plane i and plane j are (almost) parallel. */ + if (planes[i].normal * planes[j].normal > 0.0f) { + /* Plane i and plane j point in the same direction. */ + continue; + } else { + /* Plane i and plane j point in opposite direction. */ + plane.point = 0.5f * (planes[i].point + planes[j].point); + } + } else { + /* Plane.point is point on line of intersection between plane i and plane j. */ + const Vector3 lineNormal = cross(crossProduct, planes[i].normal); + plane.point = planes[i].point + (((planes[j].point - planes[i].point) * planes[j].normal) / (lineNormal * planes[j].normal)) * lineNormal; + } + + plane.normal = normalize(planes[j].normal - planes[i].normal); + projPlanes.push_back(plane); + } + + const Vector3 tempResult = result; + + if (linearProgram3(projPlanes, radius, planes[i].normal, true, result) < projPlanes.size()) { + /* This should in principle not happen. The result is by definition already in the feasible region of this linear program. If it fails, it is due to small floating point error, and the current result is kept. */ + result = tempResult; + } + + distance = planes[i].normal * (planes[i].point - result); + } + } +} +} // namespace RVO diff --git a/thirdparty/rvo2/Agent.h b/thirdparty/rvo2/Agent.h new file mode 100644 index 0000000000..16f75a08f6 --- /dev/null +++ b/thirdparty/rvo2/Agent.h @@ -0,0 +1,121 @@ +/* + * Agent.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to . + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * + */ + +/** + * \file Agent.h + * \brief Contains the Agent class. + */ +#ifndef RVO_AGENT_H_ +#define RVO_AGENT_H_ + +#include "API.h" + +#include +#include +#include + +#include "Vector3.h" + +// Note: Slightly modified to work better in Godot. +// - The agent can be created by anyone. +// - The simulator pointer is removed. +// - The update function is removed. +// - The compute velocity function now need the timeStep. +// - Moved the `Plane` class here. +// - Added a new parameter `ignore_y_` in the `Agent`. This parameter is used to control a godot feature that allows to avoid collisions by moving on the horizontal plane. +namespace RVO { +/** + * \brief Defines a plane. + */ +class Plane { +public: + /** + * \brief A point on the plane. + */ + Vector3 point; + + /** + * \brief The normal to the plane. + */ + Vector3 normal; +}; + +/** + * \brief Defines an agent in the simulation. + */ +class Agent { + +public: + /** + * \brief Constructs an agent instance. + * \param sim The simulator instance. + */ + explicit Agent(); + + /** + * \brief Computes the neighbors of this agent. + */ + void computeNeighbors(class KdTree *kdTree_); + + /** + * \brief Computes the new velocity of this agent. + */ + void computeNewVelocity(float timeStep); + + /** + * \brief Inserts an agent neighbor into the set of neighbors of this agent. + * \param agent A pointer to the agent to be inserted. + * \param rangeSq The squared range around this agent. + */ + void insertAgentNeighbor(const Agent *agent, float &rangeSq); + + Vector3 newVelocity_; + Vector3 position_; + Vector3 prefVelocity_; + Vector3 velocity_; + size_t id_; + size_t maxNeighbors_; + float maxSpeed_; + float neighborDist_; + float radius_; + float timeHorizon_; + std::vector > agentNeighbors_; + std::vector orcaPlanes_; + /// This is a godot feature that allows the Agent to avoid collision by mooving + /// on the horizontal plane. + bool ignore_y_; + + friend class KdTree; +}; +} // namespace RVO + +#endif /* RVO_AGENT_H_ */ diff --git a/thirdparty/rvo2/Definitions.h b/thirdparty/rvo2/Definitions.h new file mode 100644 index 0000000000..a73aca9908 --- /dev/null +++ b/thirdparty/rvo2/Definitions.h @@ -0,0 +1,55 @@ +/* + * Definitions.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to . + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * + */ + +/** + * \file Definitions.h + * \brief Contains functions and constants used in multiple classes. + */ + +#ifndef RVO_DEFINITIONS_H_ +#define RVO_DEFINITIONS_H_ + +#include "API.h" + +namespace RVO { + /** + * \brief Computes the square of a float. + * \param scalar The float to be squared. + * \return The square of the float. + */ + inline float sqr(float scalar) + { + return scalar * scalar; + } +} + +#endif /* RVO_DEFINITIONS_H_ */ diff --git a/thirdparty/rvo2/KdTree.cpp b/thirdparty/rvo2/KdTree.cpp new file mode 100644 index 0000000000..bc224614f0 --- /dev/null +++ b/thirdparty/rvo2/KdTree.cpp @@ -0,0 +1,152 @@ +/* + * KdTree.cpp + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to . + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * + */ + +#include "KdTree.h" + +#include + +#include "Agent.h" +#include "Definitions.h" + +namespace RVO { +const size_t RVO_MAX_LEAF_SIZE = 10; + +KdTree::KdTree() {} + +void KdTree::buildAgentTree(std::vector agents) { + agents_.swap(agents); + + if (!agents_.empty()) { + agentTree_.resize(2 * agents_.size() - 1); + buildAgentTreeRecursive(0, agents_.size(), 0); + } +} + +void KdTree::buildAgentTreeRecursive(size_t begin, size_t end, size_t node) { + agentTree_[node].begin = begin; + agentTree_[node].end = end; + agentTree_[node].minCoord = agents_[begin]->position_; + agentTree_[node].maxCoord = agents_[begin]->position_; + + for (size_t i = begin + 1; i < end; ++i) { + agentTree_[node].maxCoord[0] = std::max(agentTree_[node].maxCoord[0], agents_[i]->position_.x()); + agentTree_[node].minCoord[0] = std::min(agentTree_[node].minCoord[0], agents_[i]->position_.x()); + agentTree_[node].maxCoord[1] = std::max(agentTree_[node].maxCoord[1], agents_[i]->position_.y()); + agentTree_[node].minCoord[1] = std::min(agentTree_[node].minCoord[1], agents_[i]->position_.y()); + agentTree_[node].maxCoord[2] = std::max(agentTree_[node].maxCoord[2], agents_[i]->position_.z()); + agentTree_[node].minCoord[2] = std::min(agentTree_[node].minCoord[2], agents_[i]->position_.z()); + } + + if (end - begin > RVO_MAX_LEAF_SIZE) { + /* No leaf node. */ + size_t coord; + + if (agentTree_[node].maxCoord[0] - agentTree_[node].minCoord[0] > agentTree_[node].maxCoord[1] - agentTree_[node].minCoord[1] && agentTree_[node].maxCoord[0] - agentTree_[node].minCoord[0] > agentTree_[node].maxCoord[2] - agentTree_[node].minCoord[2]) { + coord = 0; + } else if (agentTree_[node].maxCoord[1] - agentTree_[node].minCoord[1] > agentTree_[node].maxCoord[2] - agentTree_[node].minCoord[2]) { + coord = 1; + } else { + coord = 2; + } + + const float splitValue = 0.5f * (agentTree_[node].maxCoord[coord] + agentTree_[node].minCoord[coord]); + + size_t left = begin; + + size_t right = end; + + while (left < right) { + while (left < right && agents_[left]->position_[coord] < splitValue) { + ++left; + } + + while (right > left && agents_[right - 1]->position_[coord] >= splitValue) { + --right; + } + + if (left < right) { + std::swap(agents_[left], agents_[right - 1]); + ++left; + --right; + } + } + + size_t leftSize = left - begin; + + if (leftSize == 0) { + ++leftSize; + ++left; + ++right; + } + + agentTree_[node].left = node + 1; + agentTree_[node].right = node + 2 * leftSize; + + buildAgentTreeRecursive(begin, left, agentTree_[node].left); + buildAgentTreeRecursive(left, end, agentTree_[node].right); + } +} + +void KdTree::computeAgentNeighbors(Agent *agent, float rangeSq) const { + queryAgentTreeRecursive(agent, rangeSq, 0); +} + +void KdTree::queryAgentTreeRecursive(Agent *agent, float &rangeSq, size_t node) const { + if (agentTree_[node].end - agentTree_[node].begin <= RVO_MAX_LEAF_SIZE) { + for (size_t i = agentTree_[node].begin; i < agentTree_[node].end; ++i) { + agent->insertAgentNeighbor(agents_[i], rangeSq); + } + } else { + const float distSqLeft = sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[0] - agent->position_.x())) + sqr(std::max(0.0f, agent->position_.x() - agentTree_[agentTree_[node].left].maxCoord[0])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[1] - agent->position_.y())) + sqr(std::max(0.0f, agent->position_.y() - agentTree_[agentTree_[node].left].maxCoord[1])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[2] - agent->position_.z())) + sqr(std::max(0.0f, agent->position_.z() - agentTree_[agentTree_[node].left].maxCoord[2])); + + const float distSqRight = sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[0] - agent->position_.x())) + sqr(std::max(0.0f, agent->position_.x() - agentTree_[agentTree_[node].right].maxCoord[0])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[1] - agent->position_.y())) + sqr(std::max(0.0f, agent->position_.y() - agentTree_[agentTree_[node].right].maxCoord[1])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[2] - agent->position_.z())) + sqr(std::max(0.0f, agent->position_.z() - agentTree_[agentTree_[node].right].maxCoord[2])); + + if (distSqLeft < distSqRight) { + if (distSqLeft < rangeSq) { + queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].left); + + if (distSqRight < rangeSq) { + queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].right); + } + } + } else { + if (distSqRight < rangeSq) { + queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].right); + + if (distSqLeft < rangeSq) { + queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].left); + } + } + } + } +} +} // namespace RVO diff --git a/thirdparty/rvo2/KdTree.h b/thirdparty/rvo2/KdTree.h new file mode 100644 index 0000000000..1dbad00ea4 --- /dev/null +++ b/thirdparty/rvo2/KdTree.h @@ -0,0 +1,124 @@ +/* + * KdTree.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to . + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * + */ +/** + * \file KdTree.h + * \brief Contains the KdTree class. + */ +#ifndef RVO_KD_TREE_H_ +#define RVO_KD_TREE_H_ + +#include "API.h" + +#include +#include + +#include "Vector3.h" + +// Note: Slightly modified to work better with Godot. +// - Removed `sim_`. +// - KdTree things are public +namespace RVO { +class Agent; +class RVOSimulator; + +/** + * \brief Defines kd-trees for agents in the simulation. + */ +class KdTree { +public: + /** + * \brief Defines an agent kd-tree node. + */ + class AgentTreeNode { + public: + /** + * \brief The beginning node number. + */ + size_t begin; + + /** + * \brief The ending node number. + */ + size_t end; + + /** + * \brief The left node number. + */ + size_t left; + + /** + * \brief The right node number. + */ + size_t right; + + /** + * \brief The maximum coordinates. + */ + Vector3 maxCoord; + + /** + * \brief The minimum coordinates. + */ + Vector3 minCoord; + }; + + /** + * \brief Constructs a kd-tree instance. + * \param sim The simulator instance. + */ + explicit KdTree(); + + /** + * \brief Builds an agent kd-tree. + */ + void buildAgentTree(std::vector agents); + + void buildAgentTreeRecursive(size_t begin, size_t end, size_t node); + + /** + * \brief Computes the agent neighbors of the specified agent. + * \param agent A pointer to the agent for which agent neighbors are to be computed. + * \param rangeSq The squared range around the agent. + */ + void computeAgentNeighbors(Agent *agent, float rangeSq) const; + + void queryAgentTreeRecursive(Agent *agent, float &rangeSq, size_t node) const; + + std::vector agents_; + std::vector agentTree_; + + friend class Agent; + friend class RVOSimulator; +}; +} // namespace RVO + +#endif /* RVO_KD_TREE_H_ */ diff --git a/thirdparty/rvo2/Vector3.h b/thirdparty/rvo2/Vector3.h new file mode 100644 index 0000000000..8c8835c865 --- /dev/null +++ b/thirdparty/rvo2/Vector3.h @@ -0,0 +1,335 @@ +/* + * Vector3.h + * RVO2-3D Library + * + * Copyright 2008 University of North Carolina at Chapel Hill + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * Please send all bug reports to . + * + * The authors may be contacted via: + * + * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha + * Dept. of Computer Science + * 201 S. Columbia St. + * Frederick P. Brooks, Jr. Computer Science Bldg. + * Chapel Hill, N.C. 27599-3175 + * United States of America + * + * + */ + +/** + * \file Vector3.h + * \brief Contains the Vector3 class. + */ +#ifndef RVO_VECTOR3_H_ +#define RVO_VECTOR3_H_ + +#include "API.h" + +#include +#include +#include + +namespace RVO { + /** + * \brief Defines a three-dimensional vector. + */ + class Vector3 { + public: + /** + * \brief Constructs and initializes a three-dimensional vector instance to zero. + */ + RVO_API inline Vector3() + { + val_[0] = 0.0f; + val_[1] = 0.0f; + val_[2] = 0.0f; + } + + /** + * \brief Constructs and initializes a three-dimensional vector from the specified three-element array. + * \param val The three-element array containing the xyz-coordinates. + */ + RVO_API inline explicit Vector3(const float val[3]) + { + val_[0] = val[0]; + val_[1] = val[1]; + val_[2] = val[2]; + } + + /** + * \brief Constructs and initializes a three-dimensional vector from the specified xyz-coordinates. + * \param x The x-coordinate of the three-dimensional vector. + * \param y The y-coordinate of the three-dimensional vector. + * \param z The z-coordinate of the three-dimensional vector. + */ + RVO_API inline Vector3(float x, float y, float z) + { + val_[0] = x; + val_[1] = y; + val_[2] = z; + } + + /** + * \brief Returns the x-coordinate of this three-dimensional vector. + * \return The x-coordinate of the three-dimensional vector. + */ + RVO_API inline float x() const { return val_[0]; } + + /** + * \brief Returns the y-coordinate of this three-dimensional vector. + * \return The y-coordinate of the three-dimensional vector. + */ + RVO_API inline float y() const { return val_[1]; } + + /** + * \brief Returns the z-coordinate of this three-dimensional vector. + * \return The z-coordinate of the three-dimensional vector. + */ + RVO_API inline float z() const { return val_[2]; } + + /** + * \brief Returns the specified coordinate of this three-dimensional vector. + * \param i The coordinate that should be returned (0 <= i < 3). + * \return The specified coordinate of the three-dimensional vector. + */ + RVO_API inline float operator[](size_t i) const { return val_[i]; } + + /** + * \brief Returns a reference to the specified coordinate of this three-dimensional vector. + * \param i The coordinate to which a reference should be returned (0 <= i < 3). + * \return A reference to the specified coordinate of the three-dimensional vector. + */ + RVO_API inline float &operator[](size_t i) { return val_[i]; } + + /** + * \brief Computes the negation of this three-dimensional vector. + * \return The negation of this three-dimensional vector. + */ + RVO_API inline Vector3 operator-() const + { + return Vector3(-val_[0], -val_[1], -val_[2]); + } + + /** + * \brief Computes the dot product of this three-dimensional vector with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the dot product should be computed. + * \return The dot product of this three-dimensional vector with a specified three-dimensional vector. + */ + RVO_API inline float operator*(const Vector3 &vector) const + { + return val_[0] * vector[0] + val_[1] * vector[1] + val_[2] * vector[2]; + } + + /** + * \brief Computes the scalar multiplication of this three-dimensional vector with the specified scalar value. + * \param scalar The scalar value with which the scalar multiplication should be computed. + * \return The scalar multiplication of this three-dimensional vector with a specified scalar value. + */ + RVO_API inline Vector3 operator*(float scalar) const + { + return Vector3(val_[0] * scalar, val_[1] * scalar, val_[2] * scalar); + } + + /** + * \brief Computes the scalar division of this three-dimensional vector with the specified scalar value. + * \param scalar The scalar value with which the scalar division should be computed. + * \return The scalar division of this three-dimensional vector with a specified scalar value. + */ + RVO_API inline Vector3 operator/(float scalar) const + { + const float invScalar = 1.0f / scalar; + + return Vector3(val_[0] * invScalar, val_[1] * invScalar, val_[2] * invScalar); + } + + /** + * \brief Computes the vector sum of this three-dimensional vector with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the vector sum should be computed. + * \return The vector sum of this three-dimensional vector with a specified three-dimensional vector. + */ + RVO_API inline Vector3 operator+(const Vector3 &vector) const + { + return Vector3(val_[0] + vector[0], val_[1] + vector[1], val_[2] + vector[2]); + } + + /** + * \brief Computes the vector difference of this three-dimensional vector with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the vector difference should be computed. + * \return The vector difference of this three-dimensional vector with a specified three-dimensional vector. + */ + RVO_API inline Vector3 operator-(const Vector3 &vector) const + { + return Vector3(val_[0] - vector[0], val_[1] - vector[1], val_[2] - vector[2]); + } + + /** + * \brief Tests this three-dimensional vector for equality with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which to test for equality. + * \return True if the three-dimensional vectors are equal. + */ + RVO_API inline bool operator==(const Vector3 &vector) const + { + return val_[0] == vector[0] && val_[1] == vector[1] && val_[2] == vector[2]; + } + + /** + * \brief Tests this three-dimensional vector for inequality with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which to test for inequality. + * \return True if the three-dimensional vectors are not equal. + */ + RVO_API inline bool operator!=(const Vector3 &vector) const + { + return val_[0] != vector[0] || val_[1] != vector[1] || val_[2] != vector[2]; + } + + /** + * \brief Sets the value of this three-dimensional vector to the scalar multiplication of itself with the specified scalar value. + * \param scalar The scalar value with which the scalar multiplication should be computed. + * \return A reference to this three-dimensional vector. + */ + RVO_API inline Vector3 &operator*=(float scalar) + { + val_[0] *= scalar; + val_[1] *= scalar; + val_[2] *= scalar; + + return *this; + } + + /** + * \brief Sets the value of this three-dimensional vector to the scalar division of itself with the specified scalar value. + * \param scalar The scalar value with which the scalar division should be computed. + * \return A reference to this three-dimensional vector. + */ + RVO_API inline Vector3 &operator/=(float scalar) + { + const float invScalar = 1.0f / scalar; + + val_[0] *= invScalar; + val_[1] *= invScalar; + val_[2] *= invScalar; + + return *this; + } + + /** + * \brief Sets the value of this three-dimensional vector to the vector + * sum of itself with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the vector sum should be computed. + * \return A reference to this three-dimensional vector. + */ + RVO_API inline Vector3 &operator+=(const Vector3 &vector) + { + val_[0] += vector[0]; + val_[1] += vector[1]; + val_[2] += vector[2]; + + return *this; + } + + /** + * \brief Sets the value of this three-dimensional vector to the vector difference of itself with the specified three-dimensional vector. + * \param vector The three-dimensional vector with which the vector difference should be computed. + * \return A reference to this three-dimensional vector. + */ + RVO_API inline Vector3 &operator-=(const Vector3 &vector) + { + val_[0] -= vector[0]; + val_[1] -= vector[1]; + val_[2] -= vector[2]; + + return *this; + } + + private: + float val_[3]; + }; + + + /** + * \relates Vector3 + * \brief Computes the scalar multiplication of the specified three-dimensional vector with the specified scalar value. + * \param scalar The scalar value with which the scalar multiplication should be computed. + * \param vector The three-dimensional vector with which the scalar multiplication should be computed. + * \return The scalar multiplication of the three-dimensional vector with the scalar value. + */ + inline Vector3 operator*(float scalar, const Vector3 &vector) + { + return Vector3(scalar * vector[0], scalar * vector[1], scalar * vector[2]); + } + + /** + * \relates Vector3 + * \brief Computes the cross product of the specified three-dimensional vectors. + * \param vector1 The first vector with which the cross product should be computed. + * \param vector2 The second vector with which the cross product should be computed. + * \return The cross product of the two specified vectors. + */ + inline Vector3 cross(const Vector3 &vector1, const Vector3 &vector2) + { + return Vector3(vector1[1] * vector2[2] - vector1[2] * vector2[1], vector1[2] * vector2[0] - vector1[0] * vector2[2], vector1[0] * vector2[1] - vector1[1] * vector2[0]); + } + + /** + * \relates Vector3 + * \brief Inserts the specified three-dimensional vector into the specified output stream. + * \param os The output stream into which the three-dimensional vector should be inserted. + * \param vector The three-dimensional vector which to insert into the output stream. + * \return A reference to the output stream. + */ + inline std::ostream &operator<<(std::ostream &os, const Vector3 &vector) + { + os << "(" << vector[0] << "," << vector[1] << "," << vector[2] << ")"; + + return os; + } + + /** + * \relates Vector3 + * \brief Computes the length of a specified three-dimensional vector. + * \param vector The three-dimensional vector whose length is to be computed. + * \return The length of the three-dimensional vector. + */ + inline float abs(const Vector3 &vector) + { + return std::sqrt(vector * vector); + } + + /** + * \relates Vector3 + * \brief Computes the squared length of a specified three-dimensional vector. + * \param vector The three-dimensional vector whose squared length is to be computed. + * \return The squared length of the three-dimensional vector. + */ + inline float absSq(const Vector3 &vector) + { + return vector * vector; + } + + /** + * \relates Vector3 + * \brief Computes the normalization of the specified three-dimensional vector. + * \param vector The three-dimensional vector whose normalization is to be computed. + * \return The normalization of the three-dimensional vector. + */ + inline Vector3 normalize(const Vector3 &vector) + { + return vector / abs(vector); + } +} + +#endif diff --git a/thirdparty/rvo2/src/API.h b/thirdparty/rvo2/src/API.h deleted file mode 100644 index c64efb452c..0000000000 --- a/thirdparty/rvo2/src/API.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - * API.h - * RVO2-3D Library - * - * Copyright 2008 University of North Carolina at Chapel Hill - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Please send all bug reports to . - * - * The authors may be contacted via: - * - * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha - * Dept. of Computer Science - * 201 S. Columbia St. - * Frederick P. Brooks, Jr. Computer Science Bldg. - * Chapel Hill, N.C. 27599-3175 - * United States of America - * - * - */ - -/** - * \file API.h - * \brief Contains definitions related to Microsoft Windows. - */ - -#ifndef RVO_API_H_ -#define RVO_API_H_ - -// -- GODOT start -- -#define RVO_API -// -- GODOT end -- - -#endif /* RVO_API_H_ */ diff --git a/thirdparty/rvo2/src/Agent.cpp b/thirdparty/rvo2/src/Agent.cpp deleted file mode 100644 index 851d780758..0000000000 --- a/thirdparty/rvo2/src/Agent.cpp +++ /dev/null @@ -1,425 +0,0 @@ -/* - * Agent.cpp - * RVO2-3D Library - * - * Copyright 2008 University of North Carolina at Chapel Hill - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Please send all bug reports to . - * - * The authors may be contacted via: - * - * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha - * Dept. of Computer Science - * 201 S. Columbia St. - * Frederick P. Brooks, Jr. Computer Science Bldg. - * Chapel Hill, N.C. 27599-3175 - * United States of America - * - * - */ - -#include "Agent.h" - -#include -#include - -#include "Definitions.h" -#include "KdTree.h" - -namespace RVO { -/** - * \brief A sufficiently small positive number. - */ -const float RVO_EPSILON = 0.00001f; - -/** - * \brief Defines a directed line. - */ -class Line { -public: - /** - * \brief The direction of the directed line. - */ - Vector3 direction; - - /** - * \brief A point on the directed line. - */ - Vector3 point; -}; - -/** - * \brief Solves a one-dimensional linear program on a specified line subject to linear constraints defined by planes and a spherical constraint. - * \param planes Planes defining the linear constraints. - * \param planeNo The plane on which the line lies. - * \param line The line on which the 1-d linear program is solved - * \param radius The radius of the spherical constraint. - * \param optVelocity The optimization velocity. - * \param directionOpt True if the direction should be optimized. - * \param result A reference to the result of the linear program. - * \return True if successful. - */ -bool linearProgram1(const std::vector &planes, size_t planeNo, const Line &line, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); - -/** - * \brief Solves a two-dimensional linear program on a specified plane subject to linear constraints defined by planes and a spherical constraint. - * \param planes Planes defining the linear constraints. - * \param planeNo The plane on which the 2-d linear program is solved - * \param radius The radius of the spherical constraint. - * \param optVelocity The optimization velocity. - * \param directionOpt True if the direction should be optimized. - * \param result A reference to the result of the linear program. - * \return True if successful. - */ -bool linearProgram2(const std::vector &planes, size_t planeNo, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); - -/** - * \brief Solves a three-dimensional linear program subject to linear constraints defined by planes and a spherical constraint. - * \param planes Planes defining the linear constraints. - * \param radius The radius of the spherical constraint. - * \param optVelocity The optimization velocity. - * \param directionOpt True if the direction should be optimized. - * \param result A reference to the result of the linear program. - * \return The number of the plane it fails on, and the number of planes if successful. - */ -size_t linearProgram3(const std::vector &planes, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result); - -/** - * \brief Solves a four-dimensional linear program subject to linear constraints defined by planes and a spherical constraint. - * \param planes Planes defining the linear constraints. - * \param beginPlane The plane on which the 3-d linear program failed. - * \param radius The radius of the spherical constraint. - * \param result A reference to the result of the linear program. - */ -void linearProgram4(const std::vector &planes, size_t beginPlane, float radius, Vector3 &result); - -Agent::Agent() : - id_(0), maxNeighbors_(0), maxSpeed_(0.0f), neighborDist_(0.0f), radius_(0.0f), timeHorizon_(0.0f), ignore_y_(false) {} - -void Agent::computeNeighbors(KdTree *kdTree_) { - agentNeighbors_.clear(); - if (maxNeighbors_ > 0) { - kdTree_->computeAgentNeighbors(this, neighborDist_ * neighborDist_); - } -} - -#define ABS(m_v) (((m_v) < 0) ? (-(m_v)) : (m_v)) -void Agent::computeNewVelocity(float timeStep) { - orcaPlanes_.clear(); - const float invTimeHorizon = 1.0f / timeHorizon_; - - /* Create agent ORCA planes. */ - for (size_t i = 0; i < agentNeighbors_.size(); ++i) { - const Agent *const other = agentNeighbors_[i].second; - - Vector3 relativePosition = other->position_ - position_; - Vector3 relativeVelocity = velocity_ - other->velocity_; - const float combinedRadius = radius_ + other->radius_; - - // This is a Godot feature that allow the agents to avoid the collision - // by moving only on the horizontal plane relative to the player velocity. - if (ignore_y_) { - // Skip if these are in two different heights - if (ABS(relativePosition[1]) > combinedRadius * 2) { - continue; - } - relativePosition[1] = 0; - relativeVelocity[1] = 0; - } - - const float distSq = absSq(relativePosition); - const float combinedRadiusSq = sqr(combinedRadius); - - Plane plane; - Vector3 u; - - if (distSq > combinedRadiusSq) { - /* No collision. */ - const Vector3 w = relativeVelocity - invTimeHorizon * relativePosition; - /* Vector from cutoff center to relative velocity. */ - const float wLengthSq = absSq(w); - - const float dotProduct = w * relativePosition; - - if (dotProduct < 0.0f && sqr(dotProduct) > combinedRadiusSq * wLengthSq) { - /* Project on cut-off circle. */ - const float wLength = std::sqrt(wLengthSq); - const Vector3 unitW = w / wLength; - - plane.normal = unitW; - u = (combinedRadius * invTimeHorizon - wLength) * unitW; - } else { - /* Project on cone. */ - const float a = distSq; - const float b = relativePosition * relativeVelocity; - const float c = absSq(relativeVelocity) - absSq(cross(relativePosition, relativeVelocity)) / (distSq - combinedRadiusSq); - const float t = (b + std::sqrt(sqr(b) - a * c)) / a; - const Vector3 w = relativeVelocity - t * relativePosition; - const float wLength = abs(w); - const Vector3 unitW = w / wLength; - - plane.normal = unitW; - u = (combinedRadius * t - wLength) * unitW; - } - } else { - /* Collision. */ - const float invTimeStep = 1.0f / timeStep; - const Vector3 w = relativeVelocity - invTimeStep * relativePosition; - const float wLength = abs(w); - const Vector3 unitW = w / wLength; - - plane.normal = unitW; - u = (combinedRadius * invTimeStep - wLength) * unitW; - } - - plane.point = velocity_ + 0.5f * u; - orcaPlanes_.push_back(plane); - } - - const size_t planeFail = linearProgram3(orcaPlanes_, maxSpeed_, prefVelocity_, false, newVelocity_); - - if (planeFail < orcaPlanes_.size()) { - linearProgram4(orcaPlanes_, planeFail, maxSpeed_, newVelocity_); - } - - if (ignore_y_) { - // Not 100% necessary, but better to have. - newVelocity_[1] = prefVelocity_[1]; - } -} - -void Agent::insertAgentNeighbor(const Agent *agent, float &rangeSq) { - if (this != agent) { - const float distSq = absSq(position_ - agent->position_); - - if (distSq < rangeSq) { - if (agentNeighbors_.size() < maxNeighbors_) { - agentNeighbors_.push_back(std::make_pair(distSq, agent)); - } - - size_t i = agentNeighbors_.size() - 1; - - while (i != 0 && distSq < agentNeighbors_[i - 1].first) { - agentNeighbors_[i] = agentNeighbors_[i - 1]; - --i; - } - - agentNeighbors_[i] = std::make_pair(distSq, agent); - - if (agentNeighbors_.size() == maxNeighbors_) { - rangeSq = agentNeighbors_.back().first; - } - } - } -} - -bool linearProgram1(const std::vector &planes, size_t planeNo, const Line &line, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { - const float dotProduct = line.point * line.direction; - const float discriminant = sqr(dotProduct) + sqr(radius) - absSq(line.point); - - if (discriminant < 0.0f) { - /* Max speed sphere fully invalidates line. */ - return false; - } - - const float sqrtDiscriminant = std::sqrt(discriminant); - float tLeft = -dotProduct - sqrtDiscriminant; - float tRight = -dotProduct + sqrtDiscriminant; - - for (size_t i = 0; i < planeNo; ++i) { - const float numerator = (planes[i].point - line.point) * planes[i].normal; - const float denominator = line.direction * planes[i].normal; - - if (sqr(denominator) <= RVO_EPSILON) { - /* Lines line is (almost) parallel to plane i. */ - if (numerator > 0.0f) { - return false; - } else { - continue; - } - } - - const float t = numerator / denominator; - - if (denominator >= 0.0f) { - /* Plane i bounds line on the left. */ - tLeft = std::max(tLeft, t); - } else { - /* Plane i bounds line on the right. */ - tRight = std::min(tRight, t); - } - - if (tLeft > tRight) { - return false; - } - } - - if (directionOpt) { - /* Optimize direction. */ - if (optVelocity * line.direction > 0.0f) { - /* Take right extreme. */ - result = line.point + tRight * line.direction; - } else { - /* Take left extreme. */ - result = line.point + tLeft * line.direction; - } - } else { - /* Optimize closest point. */ - const float t = line.direction * (optVelocity - line.point); - - if (t < tLeft) { - result = line.point + tLeft * line.direction; - } else if (t > tRight) { - result = line.point + tRight * line.direction; - } else { - result = line.point + t * line.direction; - } - } - - return true; -} - -bool linearProgram2(const std::vector &planes, size_t planeNo, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { - const float planeDist = planes[planeNo].point * planes[planeNo].normal; - const float planeDistSq = sqr(planeDist); - const float radiusSq = sqr(radius); - - if (planeDistSq > radiusSq) { - /* Max speed sphere fully invalidates plane planeNo. */ - return false; - } - - const float planeRadiusSq = radiusSq - planeDistSq; - - const Vector3 planeCenter = planeDist * planes[planeNo].normal; - - if (directionOpt) { - /* Project direction optVelocity on plane planeNo. */ - const Vector3 planeOptVelocity = optVelocity - (optVelocity * planes[planeNo].normal) * planes[planeNo].normal; - const float planeOptVelocityLengthSq = absSq(planeOptVelocity); - - if (planeOptVelocityLengthSq <= RVO_EPSILON) { - result = planeCenter; - } else { - result = planeCenter + std::sqrt(planeRadiusSq / planeOptVelocityLengthSq) * planeOptVelocity; - } - } else { - /* Project point optVelocity on plane planeNo. */ - result = optVelocity + ((planes[planeNo].point - optVelocity) * planes[planeNo].normal) * planes[planeNo].normal; - - /* If outside planeCircle, project on planeCircle. */ - if (absSq(result) > radiusSq) { - const Vector3 planeResult = result - planeCenter; - const float planeResultLengthSq = absSq(planeResult); - result = planeCenter + std::sqrt(planeRadiusSq / planeResultLengthSq) * planeResult; - } - } - - for (size_t i = 0; i < planeNo; ++i) { - if (planes[i].normal * (planes[i].point - result) > 0.0f) { - /* Result does not satisfy constraint i. Compute new optimal result. */ - /* Compute intersection line of plane i and plane planeNo. */ - Vector3 crossProduct = cross(planes[i].normal, planes[planeNo].normal); - - if (absSq(crossProduct) <= RVO_EPSILON) { - /* Planes planeNo and i are (almost) parallel, and plane i fully invalidates plane planeNo. */ - return false; - } - - Line line; - line.direction = normalize(crossProduct); - const Vector3 lineNormal = cross(line.direction, planes[planeNo].normal); - line.point = planes[planeNo].point + (((planes[i].point - planes[planeNo].point) * planes[i].normal) / (lineNormal * planes[i].normal)) * lineNormal; - - if (!linearProgram1(planes, i, line, radius, optVelocity, directionOpt, result)) { - return false; - } - } - } - - return true; -} - -size_t linearProgram3(const std::vector &planes, float radius, const Vector3 &optVelocity, bool directionOpt, Vector3 &result) { - if (directionOpt) { - /* Optimize direction. Note that the optimization velocity is of unit length in this case. */ - result = optVelocity * radius; - } else if (absSq(optVelocity) > sqr(radius)) { - /* Optimize closest point and outside circle. */ - result = normalize(optVelocity) * radius; - } else { - /* Optimize closest point and inside circle. */ - result = optVelocity; - } - - for (size_t i = 0; i < planes.size(); ++i) { - if (planes[i].normal * (planes[i].point - result) > 0.0f) { - /* Result does not satisfy constraint i. Compute new optimal result. */ - const Vector3 tempResult = result; - - if (!linearProgram2(planes, i, radius, optVelocity, directionOpt, result)) { - result = tempResult; - return i; - } - } - } - - return planes.size(); -} - -void linearProgram4(const std::vector &planes, size_t beginPlane, float radius, Vector3 &result) { - float distance = 0.0f; - - for (size_t i = beginPlane; i < planes.size(); ++i) { - if (planes[i].normal * (planes[i].point - result) > distance) { - /* Result does not satisfy constraint of plane i. */ - std::vector projPlanes; - - for (size_t j = 0; j < i; ++j) { - Plane plane; - - const Vector3 crossProduct = cross(planes[j].normal, planes[i].normal); - - if (absSq(crossProduct) <= RVO_EPSILON) { - /* Plane i and plane j are (almost) parallel. */ - if (planes[i].normal * planes[j].normal > 0.0f) { - /* Plane i and plane j point in the same direction. */ - continue; - } else { - /* Plane i and plane j point in opposite direction. */ - plane.point = 0.5f * (planes[i].point + planes[j].point); - } - } else { - /* Plane.point is point on line of intersection between plane i and plane j. */ - const Vector3 lineNormal = cross(crossProduct, planes[i].normal); - plane.point = planes[i].point + (((planes[j].point - planes[i].point) * planes[j].normal) / (lineNormal * planes[j].normal)) * lineNormal; - } - - plane.normal = normalize(planes[j].normal - planes[i].normal); - projPlanes.push_back(plane); - } - - const Vector3 tempResult = result; - - if (linearProgram3(projPlanes, radius, planes[i].normal, true, result) < projPlanes.size()) { - /* This should in principle not happen. The result is by definition already in the feasible region of this linear program. If it fails, it is due to small floating point error, and the current result is kept. */ - result = tempResult; - } - - distance = planes[i].normal * (planes[i].point - result); - } - } -} -} // namespace RVO diff --git a/thirdparty/rvo2/src/Agent.h b/thirdparty/rvo2/src/Agent.h deleted file mode 100644 index 16f75a08f6..0000000000 --- a/thirdparty/rvo2/src/Agent.h +++ /dev/null @@ -1,121 +0,0 @@ -/* - * Agent.h - * RVO2-3D Library - * - * Copyright 2008 University of North Carolina at Chapel Hill - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Please send all bug reports to . - * - * The authors may be contacted via: - * - * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha - * Dept. of Computer Science - * 201 S. Columbia St. - * Frederick P. Brooks, Jr. Computer Science Bldg. - * Chapel Hill, N.C. 27599-3175 - * United States of America - * - * - */ - -/** - * \file Agent.h - * \brief Contains the Agent class. - */ -#ifndef RVO_AGENT_H_ -#define RVO_AGENT_H_ - -#include "API.h" - -#include -#include -#include - -#include "Vector3.h" - -// Note: Slightly modified to work better in Godot. -// - The agent can be created by anyone. -// - The simulator pointer is removed. -// - The update function is removed. -// - The compute velocity function now need the timeStep. -// - Moved the `Plane` class here. -// - Added a new parameter `ignore_y_` in the `Agent`. This parameter is used to control a godot feature that allows to avoid collisions by moving on the horizontal plane. -namespace RVO { -/** - * \brief Defines a plane. - */ -class Plane { -public: - /** - * \brief A point on the plane. - */ - Vector3 point; - - /** - * \brief The normal to the plane. - */ - Vector3 normal; -}; - -/** - * \brief Defines an agent in the simulation. - */ -class Agent { - -public: - /** - * \brief Constructs an agent instance. - * \param sim The simulator instance. - */ - explicit Agent(); - - /** - * \brief Computes the neighbors of this agent. - */ - void computeNeighbors(class KdTree *kdTree_); - - /** - * \brief Computes the new velocity of this agent. - */ - void computeNewVelocity(float timeStep); - - /** - * \brief Inserts an agent neighbor into the set of neighbors of this agent. - * \param agent A pointer to the agent to be inserted. - * \param rangeSq The squared range around this agent. - */ - void insertAgentNeighbor(const Agent *agent, float &rangeSq); - - Vector3 newVelocity_; - Vector3 position_; - Vector3 prefVelocity_; - Vector3 velocity_; - size_t id_; - size_t maxNeighbors_; - float maxSpeed_; - float neighborDist_; - float radius_; - float timeHorizon_; - std::vector > agentNeighbors_; - std::vector orcaPlanes_; - /// This is a godot feature that allows the Agent to avoid collision by mooving - /// on the horizontal plane. - bool ignore_y_; - - friend class KdTree; -}; -} // namespace RVO - -#endif /* RVO_AGENT_H_ */ diff --git a/thirdparty/rvo2/src/Definitions.h b/thirdparty/rvo2/src/Definitions.h deleted file mode 100644 index a73aca9908..0000000000 --- a/thirdparty/rvo2/src/Definitions.h +++ /dev/null @@ -1,55 +0,0 @@ -/* - * Definitions.h - * RVO2-3D Library - * - * Copyright 2008 University of North Carolina at Chapel Hill - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Please send all bug reports to . - * - * The authors may be contacted via: - * - * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha - * Dept. of Computer Science - * 201 S. Columbia St. - * Frederick P. Brooks, Jr. Computer Science Bldg. - * Chapel Hill, N.C. 27599-3175 - * United States of America - * - * - */ - -/** - * \file Definitions.h - * \brief Contains functions and constants used in multiple classes. - */ - -#ifndef RVO_DEFINITIONS_H_ -#define RVO_DEFINITIONS_H_ - -#include "API.h" - -namespace RVO { - /** - * \brief Computes the square of a float. - * \param scalar The float to be squared. - * \return The square of the float. - */ - inline float sqr(float scalar) - { - return scalar * scalar; - } -} - -#endif /* RVO_DEFINITIONS_H_ */ diff --git a/thirdparty/rvo2/src/KdTree.cpp b/thirdparty/rvo2/src/KdTree.cpp deleted file mode 100644 index bc224614f0..0000000000 --- a/thirdparty/rvo2/src/KdTree.cpp +++ /dev/null @@ -1,152 +0,0 @@ -/* - * KdTree.cpp - * RVO2-3D Library - * - * Copyright 2008 University of North Carolina at Chapel Hill - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Please send all bug reports to . - * - * The authors may be contacted via: - * - * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha - * Dept. of Computer Science - * 201 S. Columbia St. - * Frederick P. Brooks, Jr. Computer Science Bldg. - * Chapel Hill, N.C. 27599-3175 - * United States of America - * - * - */ - -#include "KdTree.h" - -#include - -#include "Agent.h" -#include "Definitions.h" - -namespace RVO { -const size_t RVO_MAX_LEAF_SIZE = 10; - -KdTree::KdTree() {} - -void KdTree::buildAgentTree(std::vector agents) { - agents_.swap(agents); - - if (!agents_.empty()) { - agentTree_.resize(2 * agents_.size() - 1); - buildAgentTreeRecursive(0, agents_.size(), 0); - } -} - -void KdTree::buildAgentTreeRecursive(size_t begin, size_t end, size_t node) { - agentTree_[node].begin = begin; - agentTree_[node].end = end; - agentTree_[node].minCoord = agents_[begin]->position_; - agentTree_[node].maxCoord = agents_[begin]->position_; - - for (size_t i = begin + 1; i < end; ++i) { - agentTree_[node].maxCoord[0] = std::max(agentTree_[node].maxCoord[0], agents_[i]->position_.x()); - agentTree_[node].minCoord[0] = std::min(agentTree_[node].minCoord[0], agents_[i]->position_.x()); - agentTree_[node].maxCoord[1] = std::max(agentTree_[node].maxCoord[1], agents_[i]->position_.y()); - agentTree_[node].minCoord[1] = std::min(agentTree_[node].minCoord[1], agents_[i]->position_.y()); - agentTree_[node].maxCoord[2] = std::max(agentTree_[node].maxCoord[2], agents_[i]->position_.z()); - agentTree_[node].minCoord[2] = std::min(agentTree_[node].minCoord[2], agents_[i]->position_.z()); - } - - if (end - begin > RVO_MAX_LEAF_SIZE) { - /* No leaf node. */ - size_t coord; - - if (agentTree_[node].maxCoord[0] - agentTree_[node].minCoord[0] > agentTree_[node].maxCoord[1] - agentTree_[node].minCoord[1] && agentTree_[node].maxCoord[0] - agentTree_[node].minCoord[0] > agentTree_[node].maxCoord[2] - agentTree_[node].minCoord[2]) { - coord = 0; - } else if (agentTree_[node].maxCoord[1] - agentTree_[node].minCoord[1] > agentTree_[node].maxCoord[2] - agentTree_[node].minCoord[2]) { - coord = 1; - } else { - coord = 2; - } - - const float splitValue = 0.5f * (agentTree_[node].maxCoord[coord] + agentTree_[node].minCoord[coord]); - - size_t left = begin; - - size_t right = end; - - while (left < right) { - while (left < right && agents_[left]->position_[coord] < splitValue) { - ++left; - } - - while (right > left && agents_[right - 1]->position_[coord] >= splitValue) { - --right; - } - - if (left < right) { - std::swap(agents_[left], agents_[right - 1]); - ++left; - --right; - } - } - - size_t leftSize = left - begin; - - if (leftSize == 0) { - ++leftSize; - ++left; - ++right; - } - - agentTree_[node].left = node + 1; - agentTree_[node].right = node + 2 * leftSize; - - buildAgentTreeRecursive(begin, left, agentTree_[node].left); - buildAgentTreeRecursive(left, end, agentTree_[node].right); - } -} - -void KdTree::computeAgentNeighbors(Agent *agent, float rangeSq) const { - queryAgentTreeRecursive(agent, rangeSq, 0); -} - -void KdTree::queryAgentTreeRecursive(Agent *agent, float &rangeSq, size_t node) const { - if (agentTree_[node].end - agentTree_[node].begin <= RVO_MAX_LEAF_SIZE) { - for (size_t i = agentTree_[node].begin; i < agentTree_[node].end; ++i) { - agent->insertAgentNeighbor(agents_[i], rangeSq); - } - } else { - const float distSqLeft = sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[0] - agent->position_.x())) + sqr(std::max(0.0f, agent->position_.x() - agentTree_[agentTree_[node].left].maxCoord[0])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[1] - agent->position_.y())) + sqr(std::max(0.0f, agent->position_.y() - agentTree_[agentTree_[node].left].maxCoord[1])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minCoord[2] - agent->position_.z())) + sqr(std::max(0.0f, agent->position_.z() - agentTree_[agentTree_[node].left].maxCoord[2])); - - const float distSqRight = sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[0] - agent->position_.x())) + sqr(std::max(0.0f, agent->position_.x() - agentTree_[agentTree_[node].right].maxCoord[0])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[1] - agent->position_.y())) + sqr(std::max(0.0f, agent->position_.y() - agentTree_[agentTree_[node].right].maxCoord[1])) + sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minCoord[2] - agent->position_.z())) + sqr(std::max(0.0f, agent->position_.z() - agentTree_[agentTree_[node].right].maxCoord[2])); - - if (distSqLeft < distSqRight) { - if (distSqLeft < rangeSq) { - queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].left); - - if (distSqRight < rangeSq) { - queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].right); - } - } - } else { - if (distSqRight < rangeSq) { - queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].right); - - if (distSqLeft < rangeSq) { - queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].left); - } - } - } - } -} -} // namespace RVO diff --git a/thirdparty/rvo2/src/KdTree.h b/thirdparty/rvo2/src/KdTree.h deleted file mode 100644 index 1dbad00ea4..0000000000 --- a/thirdparty/rvo2/src/KdTree.h +++ /dev/null @@ -1,124 +0,0 @@ -/* - * KdTree.h - * RVO2-3D Library - * - * Copyright 2008 University of North Carolina at Chapel Hill - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Please send all bug reports to . - * - * The authors may be contacted via: - * - * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha - * Dept. of Computer Science - * 201 S. Columbia St. - * Frederick P. Brooks, Jr. Computer Science Bldg. - * Chapel Hill, N.C. 27599-3175 - * United States of America - * - * - */ -/** - * \file KdTree.h - * \brief Contains the KdTree class. - */ -#ifndef RVO_KD_TREE_H_ -#define RVO_KD_TREE_H_ - -#include "API.h" - -#include -#include - -#include "Vector3.h" - -// Note: Slightly modified to work better with Godot. -// - Removed `sim_`. -// - KdTree things are public -namespace RVO { -class Agent; -class RVOSimulator; - -/** - * \brief Defines kd-trees for agents in the simulation. - */ -class KdTree { -public: - /** - * \brief Defines an agent kd-tree node. - */ - class AgentTreeNode { - public: - /** - * \brief The beginning node number. - */ - size_t begin; - - /** - * \brief The ending node number. - */ - size_t end; - - /** - * \brief The left node number. - */ - size_t left; - - /** - * \brief The right node number. - */ - size_t right; - - /** - * \brief The maximum coordinates. - */ - Vector3 maxCoord; - - /** - * \brief The minimum coordinates. - */ - Vector3 minCoord; - }; - - /** - * \brief Constructs a kd-tree instance. - * \param sim The simulator instance. - */ - explicit KdTree(); - - /** - * \brief Builds an agent kd-tree. - */ - void buildAgentTree(std::vector agents); - - void buildAgentTreeRecursive(size_t begin, size_t end, size_t node); - - /** - * \brief Computes the agent neighbors of the specified agent. - * \param agent A pointer to the agent for which agent neighbors are to be computed. - * \param rangeSq The squared range around the agent. - */ - void computeAgentNeighbors(Agent *agent, float rangeSq) const; - - void queryAgentTreeRecursive(Agent *agent, float &rangeSq, size_t node) const; - - std::vector agents_; - std::vector agentTree_; - - friend class Agent; - friend class RVOSimulator; -}; -} // namespace RVO - -#endif /* RVO_KD_TREE_H_ */ diff --git a/thirdparty/rvo2/src/Vector3.h b/thirdparty/rvo2/src/Vector3.h deleted file mode 100644 index 8c8835c865..0000000000 --- a/thirdparty/rvo2/src/Vector3.h +++ /dev/null @@ -1,335 +0,0 @@ -/* - * Vector3.h - * RVO2-3D Library - * - * Copyright 2008 University of North Carolina at Chapel Hill - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * - * Please send all bug reports to . - * - * The authors may be contacted via: - * - * Jur van den Berg, Stephen J. Guy, Jamie Snape, Ming C. Lin, Dinesh Manocha - * Dept. of Computer Science - * 201 S. Columbia St. - * Frederick P. Brooks, Jr. Computer Science Bldg. - * Chapel Hill, N.C. 27599-3175 - * United States of America - * - * - */ - -/** - * \file Vector3.h - * \brief Contains the Vector3 class. - */ -#ifndef RVO_VECTOR3_H_ -#define RVO_VECTOR3_H_ - -#include "API.h" - -#include -#include -#include - -namespace RVO { - /** - * \brief Defines a three-dimensional vector. - */ - class Vector3 { - public: - /** - * \brief Constructs and initializes a three-dimensional vector instance to zero. - */ - RVO_API inline Vector3() - { - val_[0] = 0.0f; - val_[1] = 0.0f; - val_[2] = 0.0f; - } - - /** - * \brief Constructs and initializes a three-dimensional vector from the specified three-element array. - * \param val The three-element array containing the xyz-coordinates. - */ - RVO_API inline explicit Vector3(const float val[3]) - { - val_[0] = val[0]; - val_[1] = val[1]; - val_[2] = val[2]; - } - - /** - * \brief Constructs and initializes a three-dimensional vector from the specified xyz-coordinates. - * \param x The x-coordinate of the three-dimensional vector. - * \param y The y-coordinate of the three-dimensional vector. - * \param z The z-coordinate of the three-dimensional vector. - */ - RVO_API inline Vector3(float x, float y, float z) - { - val_[0] = x; - val_[1] = y; - val_[2] = z; - } - - /** - * \brief Returns the x-coordinate of this three-dimensional vector. - * \return The x-coordinate of the three-dimensional vector. - */ - RVO_API inline float x() const { return val_[0]; } - - /** - * \brief Returns the y-coordinate of this three-dimensional vector. - * \return The y-coordinate of the three-dimensional vector. - */ - RVO_API inline float y() const { return val_[1]; } - - /** - * \brief Returns the z-coordinate of this three-dimensional vector. - * \return The z-coordinate of the three-dimensional vector. - */ - RVO_API inline float z() const { return val_[2]; } - - /** - * \brief Returns the specified coordinate of this three-dimensional vector. - * \param i The coordinate that should be returned (0 <= i < 3). - * \return The specified coordinate of the three-dimensional vector. - */ - RVO_API inline float operator[](size_t i) const { return val_[i]; } - - /** - * \brief Returns a reference to the specified coordinate of this three-dimensional vector. - * \param i The coordinate to which a reference should be returned (0 <= i < 3). - * \return A reference to the specified coordinate of the three-dimensional vector. - */ - RVO_API inline float &operator[](size_t i) { return val_[i]; } - - /** - * \brief Computes the negation of this three-dimensional vector. - * \return The negation of this three-dimensional vector. - */ - RVO_API inline Vector3 operator-() const - { - return Vector3(-val_[0], -val_[1], -val_[2]); - } - - /** - * \brief Computes the dot product of this three-dimensional vector with the specified three-dimensional vector. - * \param vector The three-dimensional vector with which the dot product should be computed. - * \return The dot product of this three-dimensional vector with a specified three-dimensional vector. - */ - RVO_API inline float operator*(const Vector3 &vector) const - { - return val_[0] * vector[0] + val_[1] * vector[1] + val_[2] * vector[2]; - } - - /** - * \brief Computes the scalar multiplication of this three-dimensional vector with the specified scalar value. - * \param scalar The scalar value with which the scalar multiplication should be computed. - * \return The scalar multiplication of this three-dimensional vector with a specified scalar value. - */ - RVO_API inline Vector3 operator*(float scalar) const - { - return Vector3(val_[0] * scalar, val_[1] * scalar, val_[2] * scalar); - } - - /** - * \brief Computes the scalar division of this three-dimensional vector with the specified scalar value. - * \param scalar The scalar value with which the scalar division should be computed. - * \return The scalar division of this three-dimensional vector with a specified scalar value. - */ - RVO_API inline Vector3 operator/(float scalar) const - { - const float invScalar = 1.0f / scalar; - - return Vector3(val_[0] * invScalar, val_[1] * invScalar, val_[2] * invScalar); - } - - /** - * \brief Computes the vector sum of this three-dimensional vector with the specified three-dimensional vector. - * \param vector The three-dimensional vector with which the vector sum should be computed. - * \return The vector sum of this three-dimensional vector with a specified three-dimensional vector. - */ - RVO_API inline Vector3 operator+(const Vector3 &vector) const - { - return Vector3(val_[0] + vector[0], val_[1] + vector[1], val_[2] + vector[2]); - } - - /** - * \brief Computes the vector difference of this three-dimensional vector with the specified three-dimensional vector. - * \param vector The three-dimensional vector with which the vector difference should be computed. - * \return The vector difference of this three-dimensional vector with a specified three-dimensional vector. - */ - RVO_API inline Vector3 operator-(const Vector3 &vector) const - { - return Vector3(val_[0] - vector[0], val_[1] - vector[1], val_[2] - vector[2]); - } - - /** - * \brief Tests this three-dimensional vector for equality with the specified three-dimensional vector. - * \param vector The three-dimensional vector with which to test for equality. - * \return True if the three-dimensional vectors are equal. - */ - RVO_API inline bool operator==(const Vector3 &vector) const - { - return val_[0] == vector[0] && val_[1] == vector[1] && val_[2] == vector[2]; - } - - /** - * \brief Tests this three-dimensional vector for inequality with the specified three-dimensional vector. - * \param vector The three-dimensional vector with which to test for inequality. - * \return True if the three-dimensional vectors are not equal. - */ - RVO_API inline bool operator!=(const Vector3 &vector) const - { - return val_[0] != vector[0] || val_[1] != vector[1] || val_[2] != vector[2]; - } - - /** - * \brief Sets the value of this three-dimensional vector to the scalar multiplication of itself with the specified scalar value. - * \param scalar The scalar value with which the scalar multiplication should be computed. - * \return A reference to this three-dimensional vector. - */ - RVO_API inline Vector3 &operator*=(float scalar) - { - val_[0] *= scalar; - val_[1] *= scalar; - val_[2] *= scalar; - - return *this; - } - - /** - * \brief Sets the value of this three-dimensional vector to the scalar division of itself with the specified scalar value. - * \param scalar The scalar value with which the scalar division should be computed. - * \return A reference to this three-dimensional vector. - */ - RVO_API inline Vector3 &operator/=(float scalar) - { - const float invScalar = 1.0f / scalar; - - val_[0] *= invScalar; - val_[1] *= invScalar; - val_[2] *= invScalar; - - return *this; - } - - /** - * \brief Sets the value of this three-dimensional vector to the vector - * sum of itself with the specified three-dimensional vector. - * \param vector The three-dimensional vector with which the vector sum should be computed. - * \return A reference to this three-dimensional vector. - */ - RVO_API inline Vector3 &operator+=(const Vector3 &vector) - { - val_[0] += vector[0]; - val_[1] += vector[1]; - val_[2] += vector[2]; - - return *this; - } - - /** - * \brief Sets the value of this three-dimensional vector to the vector difference of itself with the specified three-dimensional vector. - * \param vector The three-dimensional vector with which the vector difference should be computed. - * \return A reference to this three-dimensional vector. - */ - RVO_API inline Vector3 &operator-=(const Vector3 &vector) - { - val_[0] -= vector[0]; - val_[1] -= vector[1]; - val_[2] -= vector[2]; - - return *this; - } - - private: - float val_[3]; - }; - - - /** - * \relates Vector3 - * \brief Computes the scalar multiplication of the specified three-dimensional vector with the specified scalar value. - * \param scalar The scalar value with which the scalar multiplication should be computed. - * \param vector The three-dimensional vector with which the scalar multiplication should be computed. - * \return The scalar multiplication of the three-dimensional vector with the scalar value. - */ - inline Vector3 operator*(float scalar, const Vector3 &vector) - { - return Vector3(scalar * vector[0], scalar * vector[1], scalar * vector[2]); - } - - /** - * \relates Vector3 - * \brief Computes the cross product of the specified three-dimensional vectors. - * \param vector1 The first vector with which the cross product should be computed. - * \param vector2 The second vector with which the cross product should be computed. - * \return The cross product of the two specified vectors. - */ - inline Vector3 cross(const Vector3 &vector1, const Vector3 &vector2) - { - return Vector3(vector1[1] * vector2[2] - vector1[2] * vector2[1], vector1[2] * vector2[0] - vector1[0] * vector2[2], vector1[0] * vector2[1] - vector1[1] * vector2[0]); - } - - /** - * \relates Vector3 - * \brief Inserts the specified three-dimensional vector into the specified output stream. - * \param os The output stream into which the three-dimensional vector should be inserted. - * \param vector The three-dimensional vector which to insert into the output stream. - * \return A reference to the output stream. - */ - inline std::ostream &operator<<(std::ostream &os, const Vector3 &vector) - { - os << "(" << vector[0] << "," << vector[1] << "," << vector[2] << ")"; - - return os; - } - - /** - * \relates Vector3 - * \brief Computes the length of a specified three-dimensional vector. - * \param vector The three-dimensional vector whose length is to be computed. - * \return The length of the three-dimensional vector. - */ - inline float abs(const Vector3 &vector) - { - return std::sqrt(vector * vector); - } - - /** - * \relates Vector3 - * \brief Computes the squared length of a specified three-dimensional vector. - * \param vector The three-dimensional vector whose squared length is to be computed. - * \return The squared length of the three-dimensional vector. - */ - inline float absSq(const Vector3 &vector) - { - return vector * vector; - } - - /** - * \relates Vector3 - * \brief Computes the normalization of the specified three-dimensional vector. - * \param vector The three-dimensional vector whose normalization is to be computed. - * \return The normalization of the three-dimensional vector. - */ - inline Vector3 normalize(const Vector3 &vector) - { - return vector / abs(vector); - } -} - -#endif -- cgit v1.2.3