summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--core/image.cpp151
-rw-r--r--core/image.h1
-rw-r--r--core/math/math_funcs.h6
-rw-r--r--doc/classes/Image.xml2
-rwxr-xr-xdoc/tools/makerst.py15
-rw-r--r--editor/editor_node.cpp4
-rw-r--r--editor/editor_settings.cpp2
-rw-r--r--editor/editor_themes.cpp2
-rw-r--r--modules/bullet/rigid_body_bullet.cpp10
-rw-r--r--modules/bullet/shape_bullet.cpp8
-rw-r--r--scene/gui/line_edit.cpp2
-rw-r--r--scene/gui/text_edit.cpp5
-rw-r--r--thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp19
-rw-r--r--thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp420
-rw-r--r--thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h21
15 files changed, 645 insertions, 23 deletions
diff --git a/core/image.cpp b/core/image.cpp
index 99d5eab864..30af724de9 100644
--- a/core/image.cpp
+++ b/core/image.cpp
@@ -725,6 +725,131 @@ static void _scale_nearest(const uint8_t *__restrict p_src, uint8_t *__restrict
}
}
+#define LANCZOS_TYPE 3
+
+static float _lanczos(float p_x) {
+ return Math::abs(p_x) >= LANCZOS_TYPE ? 0 : Math::sincn(p_x) * Math::sincn(p_x / LANCZOS_TYPE);
+}
+
+template <int CC, class T>
+static void _scale_lanczos(const uint8_t *__restrict p_src, uint8_t *__restrict p_dst, uint32_t p_src_width, uint32_t p_src_height, uint32_t p_dst_width, uint32_t p_dst_height) {
+
+ int32_t src_width = p_src_width;
+ int32_t src_height = p_src_height;
+ int32_t dst_height = p_dst_height;
+ int32_t dst_width = p_dst_width;
+
+ uint32_t buffer_size = src_height * dst_width * CC;
+ float *buffer = memnew_arr(float, buffer_size); // Store the first pass in a buffer
+
+ { // FIRST PASS (horizontal)
+
+ float x_scale = float(src_width) / float(dst_width);
+
+ float scale_factor = MAX(x_scale, 1); // A larger kernel is required only when downscaling
+ int32_t half_kernel = LANCZOS_TYPE * scale_factor;
+
+ float *kernel = memnew_arr(float, half_kernel * 2 - 1);
+
+ for (int32_t buffer_x = 0; buffer_x < dst_width; buffer_x++) {
+
+ float src_real_x = buffer_x * x_scale;
+ int32_t src_x = src_real_x;
+
+ int32_t start_x = MAX(0, src_x - half_kernel + 1);
+ int32_t end_x = MIN(src_width - 1, src_x + half_kernel);
+
+ // Create the kernel used by all the pixels of the column
+ for (int32_t target_x = start_x; target_x <= end_x; target_x++)
+ kernel[target_x - start_x] = _lanczos((src_real_x - target_x) / scale_factor);
+
+ for (int32_t buffer_y = 0; buffer_y < src_height; buffer_y++) {
+
+ float pixel[CC] = { 0 };
+ float weight = 0;
+
+ for (int32_t target_x = start_x; target_x <= end_x; target_x++) {
+
+ float lanczos_val = kernel[target_x - start_x];
+ weight += lanczos_val;
+
+ const T *__restrict src_data = ((const T *)p_src) + (buffer_y * src_width + target_x) * CC;
+
+ for (uint32_t i = 0; i < CC; i++) {
+ if (sizeof(T) == 2) //half float
+ pixel[i] += Math::half_to_float(src_data[i]) * lanczos_val;
+ else
+ pixel[i] += src_data[i] * lanczos_val;
+ }
+ }
+
+ float *dst_data = ((float *)buffer) + (buffer_y * dst_width + buffer_x) * CC;
+
+ for (uint32_t i = 0; i < CC; i++)
+ dst_data[i] = pixel[i] / weight; // Normalize the sum of all the samples
+ }
+ }
+
+ memdelete_arr(kernel);
+ } // End of first pass
+
+ { // SECOND PASS (vertical + result)
+
+ float y_scale = float(src_height) / float(dst_height);
+
+ float scale_factor = MAX(y_scale, 1);
+ int32_t half_kernel = LANCZOS_TYPE * scale_factor;
+
+ float *kernel = memnew_arr(float, half_kernel * 2 - 1);
+
+ for (int32_t dst_y = 0; dst_y < dst_height; dst_y++) {
+
+ float buffer_real_y = dst_y * y_scale;
+ int32_t buffer_y = buffer_real_y;
+
+ int32_t start_y = MAX(0, buffer_y - half_kernel + 1);
+ int32_t end_y = MIN(src_height - 1, buffer_y + half_kernel);
+
+ for (int32_t target_y = start_y; target_y <= end_y; target_y++)
+ kernel[target_y - start_y] = _lanczos((buffer_real_y - target_y) / scale_factor);
+
+ for (int32_t dst_x = 0; dst_x < dst_width; dst_x++) {
+
+ float pixel[CC] = { 0 };
+ float weight = 0;
+
+ for (int32_t target_y = start_y; target_y <= end_y; target_y++) {
+
+ float lanczos_val = kernel[target_y - start_y];
+ weight += lanczos_val;
+
+ float *buffer_data = ((float *)buffer) + (target_y * dst_width + dst_x) * CC;
+
+ for (uint32_t i = 0; i < CC; i++)
+ pixel[i] += buffer_data[i] * lanczos_val;
+ }
+
+ T *dst_data = ((T *)p_dst) + (dst_y * dst_width + dst_x) * CC;
+
+ for (uint32_t i = 0; i < CC; i++) {
+ pixel[i] /= weight;
+
+ if (sizeof(T) == 1) //byte
+ dst_data[i] = CLAMP(Math::fast_ftoi(pixel[i]), 0, 255);
+ else if (sizeof(T) == 2) //half float
+ dst_data[i] = Math::make_half_float(pixel[i]);
+ else // float
+ dst_data[i] = pixel[i];
+ }
+ }
+ }
+
+ memdelete_arr(kernel);
+ } // End of second pass
+
+ memdelete_arr(buffer);
+}
+
static void _overlay(const uint8_t *__restrict p_src, uint8_t *__restrict p_dst, float p_alpha, uint32_t p_width, uint32_t p_height, uint32_t p_pixel_size) {
uint16_t alpha = CLAMP((uint16_t)(p_alpha * 256.0f), 0, 256);
@@ -939,6 +1064,31 @@ void Image::resize(int p_width, int p_height, Interpolation p_interpolation) {
}
}
} break;
+ case INTERPOLATE_LANCZOS: {
+
+ if (format >= FORMAT_L8 && format <= FORMAT_RGBA8) {
+ switch (get_format_pixel_size(format)) {
+ case 1: _scale_lanczos<1, uint8_t>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 2: _scale_lanczos<2, uint8_t>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 3: _scale_lanczos<3, uint8_t>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 4: _scale_lanczos<4, uint8_t>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ }
+ } else if (format >= FORMAT_RF && format <= FORMAT_RGBAF) {
+ switch (get_format_pixel_size(format)) {
+ case 4: _scale_lanczos<1, float>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 8: _scale_lanczos<2, float>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 12: _scale_lanczos<3, float>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 16: _scale_lanczos<4, float>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ }
+ } else if (format >= FORMAT_RH && format <= FORMAT_RGBAH) {
+ switch (get_format_pixel_size(format)) {
+ case 2: _scale_lanczos<1, uint16_t>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 4: _scale_lanczos<2, uint16_t>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 6: _scale_lanczos<3, uint16_t>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ case 8: _scale_lanczos<4, uint16_t>(r_ptr, w_ptr, width, height, p_width, p_height); break;
+ }
+ }
+ } break;
}
r = PoolVector<uint8_t>::Read();
@@ -2685,6 +2835,7 @@ void Image::_bind_methods() {
BIND_ENUM_CONSTANT(INTERPOLATE_BILINEAR);
BIND_ENUM_CONSTANT(INTERPOLATE_CUBIC);
BIND_ENUM_CONSTANT(INTERPOLATE_TRILINEAR);
+ BIND_ENUM_CONSTANT(INTERPOLATE_LANCZOS);
BIND_ENUM_CONSTANT(ALPHA_NONE);
BIND_ENUM_CONSTANT(ALPHA_BIT);
diff --git a/core/image.h b/core/image.h
index 69a42f169a..752ef20208 100644
--- a/core/image.h
+++ b/core/image.h
@@ -109,6 +109,7 @@ public:
INTERPOLATE_BILINEAR,
INTERPOLATE_CUBIC,
INTERPOLATE_TRILINEAR,
+ INTERPOLATE_LANCZOS,
/* INTERPOLATE_TRICUBIC, */
/* INTERPOLATE GAUSS */
};
diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h
index a75f2fb4ab..82b5b56c01 100644
--- a/core/math/math_funcs.h
+++ b/core/math/math_funcs.h
@@ -61,6 +61,12 @@ public:
static _ALWAYS_INLINE_ double sinh(double p_x) { return ::sinh(p_x); }
static _ALWAYS_INLINE_ float sinh(float p_x) { return ::sinhf(p_x); }
+ static _ALWAYS_INLINE_ float sinc(float p_x) { return p_x == 0 ? 1 : ::sin(p_x) / p_x; }
+ static _ALWAYS_INLINE_ double sinc(double p_x) { return p_x == 0 ? 1 : ::sin(p_x) / p_x; }
+
+ static _ALWAYS_INLINE_ float sincn(float p_x) { return sinc(Math_PI * p_x); }
+ static _ALWAYS_INLINE_ double sincn(double p_x) { return sinc(Math_PI * p_x); }
+
static _ALWAYS_INLINE_ double cosh(double p_x) { return ::cosh(p_x); }
static _ALWAYS_INLINE_ float cosh(float p_x) { return ::coshf(p_x); }
diff --git a/doc/classes/Image.xml b/doc/classes/Image.xml
index 641bd64599..8dfabdd884 100644
--- a/doc/classes/Image.xml
+++ b/doc/classes/Image.xml
@@ -603,6 +603,8 @@
If the image does not have mipmaps, they will be generated and used internally, but no mipmaps will be generated on the resulting image. (Note that if you intend to scale multiple copies of the original image, it's better to call [code]generate_mipmaps[/code] on it in advance, to avoid wasting processing power in generating them again and again.)
On the other hand, if the image already has mipmaps, they will be used, and a new set will be generated for the resulting image.
</constant>
+ <constant name="INTERPOLATE_LANCZOS" value="4" enum="Interpolation">
+ </constant>
<constant name="ALPHA_NONE" value="0" enum="AlphaMode">
</constant>
<constant name="ALPHA_BIT" value="1" enum="AlphaMode">
diff --git a/doc/tools/makerst.py b/doc/tools/makerst.py
index e81b4db13e..c3e15b2f9a 100755
--- a/doc/tools/makerst.py
+++ b/doc/tools/makerst.py
@@ -683,10 +683,16 @@ def rstize_text(text, state): # type: (str, State) -> str
# Handle [tags]
inside_code = False
+ inside_url = False
+ url_has_name = False
+ url_link = ""
pos = 0
tag_depth = 0
+ previous_pos = 0
while True:
pos = text.find('[', pos)
+ if inside_url and (pos > previous_pos):
+ url_has_name = True
if pos == -1:
break
@@ -795,12 +801,16 @@ def rstize_text(text, state): # type: (str, State) -> str
elif cmd.find('image=') == 0:
tag_text = "" # '![](' + cmd[6:] + ')'
elif cmd.find('url=') == 0:
- tag_text = ':ref:`' + cmd[4:] + '<' + cmd[4:] + ">`"
+ url_link = cmd[4:]
+ tag_text = ':ref:`'
tag_depth += 1
+ url_has_name = False
+ inside_url = True
elif cmd == '/url':
- tag_text = ''
+ tag_text = ('' if url_has_name else url_link) + '<' + url_link + ">`"
tag_depth -= 1
escape_post = True
+ inside_url = False
elif cmd == 'center':
tag_depth += 1
tag_text = ''
@@ -871,6 +881,7 @@ def rstize_text(text, state): # type: (str, State) -> str
text = pre_text + tag_text + post_text
pos = len(pre_text) + len(tag_text)
+ previous_pos = pos
if tag_depth > 0:
print_error("Tag depth mismatch: too many/little open/close tags, file: {}".format(state.current_class), state)
diff --git a/editor/editor_node.cpp b/editor/editor_node.cpp
index fed1f6b4fa..40e05940a7 100644
--- a/editor/editor_node.cpp
+++ b/editor/editor_node.cpp
@@ -1015,8 +1015,7 @@ void EditorNode::_save_scene_with_preview(String p_file, int p_idx) {
y = (img->get_height() - size) / 2;
img->crop_from_point(x, y, size, size);
- // We could get better pictures with better filters
- img->resize(preview_size, preview_size, Image::INTERPOLATE_CUBIC);
+ img->resize(preview_size, preview_size, Image::INTERPOLATE_LANCZOS);
}
img->convert(Image::FORMAT_RGB8);
@@ -5997,7 +5996,6 @@ EditorNode::EditorNode() {
node_dock = memnew(NodeDock);
filesystem_dock = memnew(FileSystemDock(this));
- filesystem_dock->connect("open", this, "open_request");
filesystem_dock->connect("inherit", this, "_inherit_request");
filesystem_dock->connect("instance", this, "_instance_request");
filesystem_dock->connect("display_mode_changed", this, "_save_docks");
diff --git a/editor/editor_settings.cpp b/editor/editor_settings.cpp
index c32dcb0ace..8f26663f81 100644
--- a/editor/editor_settings.cpp
+++ b/editor/editor_settings.cpp
@@ -651,7 +651,7 @@ void EditorSettings::_load_default_text_editor_theme() {
_initial_set("text_editor/highlighting/executing_line_color", Color(0.2, 0.8, 0.2, 0.4));
_initial_set("text_editor/highlighting/code_folding_color", Color(0.8, 0.8, 0.8, 0.8));
_initial_set("text_editor/highlighting/search_result_color", Color(0.05, 0.25, 0.05, 1));
- _initial_set("text_editor/highlighting/search_result_border_color", Color(0.1, 0.45, 0.1, 1));
+ _initial_set("text_editor/highlighting/search_result_border_color", Color(0.41, 0.61, 0.91, 0.38));
}
bool EditorSettings::_save_text_editor_theme(String p_file) {
diff --git a/editor/editor_themes.cpp b/editor/editor_themes.cpp
index f74e913208..e1addaa532 100644
--- a/editor/editor_themes.cpp
+++ b/editor/editor_themes.cpp
@@ -1121,7 +1121,7 @@ Ref<Theme> create_editor_theme(const Ref<Theme> p_theme) {
const Color executing_line_color = Color(0.2, 0.8, 0.2, 0.4);
const Color code_folding_color = alpha3;
const Color search_result_color = alpha1;
- const Color search_result_border_color = alpha3;
+ const Color search_result_border_color = Color(0.41, 0.61, 0.91, 0.38);
EditorSettings *setting = EditorSettings::get_singleton();
String text_editor_color_theme = setting->get("text_editor/theme/color_theme");
diff --git a/modules/bullet/rigid_body_bullet.cpp b/modules/bullet/rigid_body_bullet.cpp
index e5f70a0b34..733a900396 100644
--- a/modules/bullet/rigid_body_bullet.cpp
+++ b/modules/bullet/rigid_body_bullet.cpp
@@ -741,22 +741,20 @@ void RigidBodyBullet::set_continuous_collision_detection(bool p_enable) {
if (p_enable) {
// This threshold enable CCD if the object moves more than
// 1 meter in one simulation frame
- btBody->setCcdMotionThreshold(0.1);
+ btBody->setCcdMotionThreshold(1e-7);
/// Calculate using the rule writte below the CCD swept sphere radius
/// CCD works on an embedded sphere of radius, make sure this radius
/// is embedded inside the convex objects, preferably smaller:
/// for an object of dimensions 1 meter, try 0.2
- btScalar radius;
+ btScalar radius(1.0);
if (btBody->getCollisionShape()) {
btVector3 center;
btBody->getCollisionShape()->getBoundingSphere(center, radius);
- } else {
- radius = 0;
}
btBody->setCcdSweptSphereRadius(radius * 0.2);
} else {
- btBody->setCcdMotionThreshold(0.);
+ btBody->setCcdMotionThreshold(10000.0);
btBody->setCcdSweptSphereRadius(0.);
}
}
@@ -834,7 +832,7 @@ void RigidBodyBullet::reload_shapes() {
btBody->updateInertiaTensor();
reload_kinematic_shapes();
-
+ set_continuous_collision_detection(btBody->getCcdMotionThreshold() < 9998.0);
reload_body();
}
diff --git a/modules/bullet/shape_bullet.cpp b/modules/bullet/shape_bullet.cpp
index b590d63167..f15bcec914 100644
--- a/modules/bullet/shape_bullet.cpp
+++ b/modules/bullet/shape_bullet.cpp
@@ -148,7 +148,13 @@ btHeightfieldTerrainShape *ShapeBullet::create_shape_height_field(PoolVector<rea
const bool flipQuadEdges = false;
const void *heightsPtr = p_heights.read().ptr();
- return bulletnew(btHeightfieldTerrainShape(p_width, p_depth, heightsPtr, ignoredHeightScale, p_min_height, p_max_height, YAxis, PHY_FLOAT, flipQuadEdges));
+ btHeightfieldTerrainShape *heightfield = bulletnew(btHeightfieldTerrainShape(p_width, p_depth, heightsPtr, ignoredHeightScale, p_min_height, p_max_height, YAxis, PHY_FLOAT, flipQuadEdges));
+
+ // The shape can be created without params when you do PhysicsServer.shape_create(PhysicsServer.SHAPE_HEIGHTMAP)
+ if (heightsPtr)
+ heightfield->buildAccelerator(16);
+
+ return heightfield;
}
btRayShape *ShapeBullet::create_shape_ray(real_t p_length, bool p_slips_on_slope) {
diff --git a/scene/gui/line_edit.cpp b/scene/gui/line_edit.cpp
index b10ddfaf70..2d18a80833 100644
--- a/scene/gui/line_edit.cpp
+++ b/scene/gui/line_edit.cpp
@@ -613,7 +613,7 @@ void LineEdit::_notification(int p_what) {
#endif
case NOTIFICATION_RESIZED: {
- window_pos = 0; //force scroll back since it's expanding to text length
+ window_pos = 0;
set_cursor_position(get_cursor_position());
} break;
diff --git a/scene/gui/text_edit.cpp b/scene/gui/text_edit.cpp
index 10bd9e2a8b..86b99b3c6d 100644
--- a/scene/gui/text_edit.cpp
+++ b/scene/gui/text_edit.cpp
@@ -1072,10 +1072,7 @@ void TextEdit::_notification(int p_what) {
}
if ((char_ofs + char_margin + char_w) >= xmargin_end) {
- if (syntax_coloring)
- continue;
- else
- break;
+ break;
}
bool in_search_result = false;
diff --git a/thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp b/thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp
index 782e9efaf1..b30ce03164 100644
--- a/thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp
+++ b/thirdparty/bullet/BulletCollision/CollisionDispatch/btCollisionWorld.cpp
@@ -19,9 +19,10 @@ subject to the following restrictions:
#include "BulletCollision/CollisionShapes/btCollisionShape.h"
#include "BulletCollision/CollisionShapes/btConvexShape.h"
#include "BulletCollision/NarrowPhaseCollision/btGjkEpaPenetrationDepthSolver.h"
-#include "BulletCollision/CollisionShapes/btSphereShape.h" //for raycasting
-#include "BulletCollision/CollisionShapes/btBvhTriangleMeshShape.h" //for raycasting
-#include "BulletCollision/CollisionShapes/btScaledBvhTriangleMeshShape.h" //for raycasting
+#include "BulletCollision/CollisionShapes/btSphereShape.h" //for raycasting
+#include "BulletCollision/CollisionShapes/btBvhTriangleMeshShape.h" //for raycasting
+#include "BulletCollision/CollisionShapes/btScaledBvhTriangleMeshShape.h" //for raycasting
+#include "BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h" //for raycasting
#include "BulletCollision/NarrowPhaseCollision/btRaycastCallback.h"
#include "BulletCollision/CollisionShapes/btCompoundShape.h"
#include "BulletCollision/NarrowPhaseCollision/btSubSimplexConvexCast.h"
@@ -413,6 +414,18 @@ void btCollisionWorld::rayTestSingleInternal(const btTransform& rayFromTrans, co
rcb.m_hitFraction = resultCallback.m_closestHitFraction;
triangleMesh->performRaycast(&rcb, rayFromLocalScaled, rayToLocalScaled);
}
+ else if (collisionShape->getShapeType()==TERRAIN_SHAPE_PROXYTYPE)
+ {
+ ///optimized version for btHeightfieldTerrainShape
+ btHeightfieldTerrainShape* heightField = (btHeightfieldTerrainShape*)collisionShape;
+ btTransform worldTocollisionObject = colObjWorldTransform.inverse();
+ btVector3 rayFromLocal = worldTocollisionObject * rayFromTrans.getOrigin();
+ btVector3 rayToLocal = worldTocollisionObject * rayToTrans.getOrigin();
+
+ BridgeTriangleRaycastCallback rcb(rayFromLocal,rayToLocal,&resultCallback,collisionObjectWrap->getCollisionObject(),heightField,colObjWorldTransform);
+ rcb.m_hitFraction = resultCallback.m_closestHitFraction;
+ heightField->performRaycast(&rcb, rayFromLocal, rayToLocal);
+ }
else
{
//generic (slower) case
diff --git a/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp b/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp
index c85ce2498e..4adf27e6bb 100644
--- a/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp
+++ b/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp
@@ -73,6 +73,10 @@ void btHeightfieldTerrainShape::initialize(
m_useZigzagSubdivision = false;
m_upAxis = upAxis;
m_localScaling.setValue(btScalar(1.), btScalar(1.), btScalar(1.));
+ m_vboundsGrid = NULL;
+ m_vboundsChunkSize = 0;
+ m_vboundsGridWidth = 0;
+ m_vboundsGridLength = 0;
// determine min/max axis-aligned bounding box (aabb) values
switch (m_upAxis)
@@ -108,6 +112,7 @@ void btHeightfieldTerrainShape::initialize(
btHeightfieldTerrainShape::~btHeightfieldTerrainShape()
{
+ clearAccelerator();
}
void btHeightfieldTerrainShape::getAabb(const btTransform& t, btVector3& aabbMin, btVector3& aabbMax) const
@@ -323,6 +328,8 @@ void btHeightfieldTerrainShape::processAllTriangles(btTriangleCallback* callback
}
}
+ // TODO If m_vboundsGrid is available, use it to determine if we really need to process this area
+
for (int j = startJ; j < endJ; j++)
{
for (int x = startX; x < endX; x++)
@@ -373,3 +380,416 @@ const btVector3& btHeightfieldTerrainShape::getLocalScaling() const
{
return m_localScaling;
}
+
+
+
+struct GridRaycastState
+{
+ int x; // Next quad coords
+ int z;
+ int prev_x; // Previous quad coords
+ int prev_z;
+ btScalar param; // Exit param for previous quad
+ btScalar prevParam; // Enter param for previous quad
+ btScalar maxDistanceFlat;
+ btScalar maxDistance3d;
+};
+
+
+// TODO Does it really need to take 3D vectors?
+/// Iterates through a virtual 2D grid of unit-sized square cells,
+/// and executes an action on each cell intersecting the given segment, ordered from begin to end.
+/// Initially inspired by http://www.cse.yorku.ca/~amana/research/grid.pdf
+template <typename Action_T>
+void gridRaycast(Action_T &quadAction, const btVector3 &beginPos, const btVector3 &endPos)
+{
+ GridRaycastState rs;
+ rs.maxDistance3d = beginPos.distance(endPos);
+ if (rs.maxDistance3d < 0.0001)
+ // Consider the ray is too small to hit anything
+ return;
+
+ btScalar rayDirectionFlatX = endPos[0] - beginPos[0];
+ btScalar rayDirectionFlatZ = endPos[2] - beginPos[2];
+ rs.maxDistanceFlat = btSqrt(rayDirectionFlatX * rayDirectionFlatX + rayDirectionFlatZ * rayDirectionFlatZ);
+
+ if(rs.maxDistanceFlat < 0.0001)
+ {
+ // Consider the ray vertical
+ rayDirectionFlatX = 0;
+ rayDirectionFlatZ = 0;
+ }
+ else
+ {
+ rayDirectionFlatX /= rs.maxDistanceFlat;
+ rayDirectionFlatZ /= rs.maxDistanceFlat;
+ }
+
+ const int xiStep = rayDirectionFlatX > 0 ? 1 : rayDirectionFlatX < 0 ? -1 : 0;
+ const int ziStep = rayDirectionFlatZ > 0 ? 1 : rayDirectionFlatZ < 0 ? -1 : 0;
+
+ const float infinite = 9999999;
+ const btScalar paramDeltaX = xiStep != 0 ? 1.f / btFabs(rayDirectionFlatX) : infinite;
+ const btScalar paramDeltaZ = ziStep != 0 ? 1.f / btFabs(rayDirectionFlatZ) : infinite;
+
+ // pos = param * dir
+ btScalar paramCrossX; // At which value of `param` we will cross a x-axis lane?
+ btScalar paramCrossZ; // At which value of `param` we will cross a z-axis lane?
+
+ // paramCrossX and paramCrossZ are initialized as being the first cross
+ // X initialization
+ if (xiStep != 0)
+ {
+ if (xiStep == 1)
+ paramCrossX = (ceil(beginPos[0]) - beginPos[0]) * paramDeltaX;
+ else
+ paramCrossX = (beginPos[0] - floor(beginPos[0])) * paramDeltaX;
+ }
+ else
+ paramCrossX = infinite; // Will never cross on X
+
+ // Z initialization
+ if (ziStep != 0)
+ {
+ if (ziStep == 1)
+ paramCrossZ = (ceil(beginPos[2]) - beginPos[2]) * paramDeltaZ;
+ else
+ paramCrossZ = (beginPos[2] - floor(beginPos[2])) * paramDeltaZ;
+ }
+ else
+ paramCrossZ = infinite; // Will never cross on Z
+
+ rs.x = static_cast<int>(floor(beginPos[0]));
+ rs.z = static_cast<int>(floor(beginPos[2]));
+
+ // Workaround cases where the ray starts at an integer position
+ if (paramCrossX == 0.0)
+ {
+ paramCrossX += paramDeltaX;
+ // If going backwards, we should ignore the position we would get by the above flooring,
+ // because the ray is not heading in that direction
+ if (xiStep == -1)
+ rs.x -= 1;
+ }
+
+ if (paramCrossZ == 0.0)
+ {
+ paramCrossZ += paramDeltaZ;
+ if (ziStep == -1)
+ rs.z -= 1;
+ }
+
+ rs.prev_x = rs.x;
+ rs.prev_z = rs.z;
+ rs.param = 0;
+
+ while (true)
+ {
+ rs.prev_x = rs.x;
+ rs.prev_z = rs.z;
+ rs.prevParam = rs.param;
+
+ if (paramCrossX < paramCrossZ)
+ {
+ // X lane
+ rs.x += xiStep;
+ // Assign before advancing the param,
+ // to be in sync with the initialization step
+ rs.param = paramCrossX;
+ paramCrossX += paramDeltaX;
+ }
+ else
+ {
+ // Z lane
+ rs.z += ziStep;
+ rs.param = paramCrossZ;
+ paramCrossZ += paramDeltaZ;
+ }
+
+ if (rs.param > rs.maxDistanceFlat)
+ {
+ rs.param = rs.maxDistanceFlat;
+ quadAction(rs);
+ break;
+ }
+ else
+ quadAction(rs);
+ }
+}
+
+
+struct ProcessTrianglesAction
+{
+ const btHeightfieldTerrainShape *shape;
+ bool flipQuadEdges;
+ bool useDiamondSubdivision;
+ int width;
+ int length;
+ btTriangleCallback* callback;
+
+ void exec(int x, int z) const
+ {
+ if(x < 0 || z < 0 || x >= width || z >= length)
+ return;
+
+ btVector3 vertices[3];
+
+ // Check quad
+ if (flipQuadEdges || (useDiamondSubdivision && (((z + x) & 1) > 0)))
+ {
+ // First triangle
+ shape->getVertex(x, z, vertices[0]);
+ shape->getVertex(x + 1, z, vertices[1]);
+ shape->getVertex(x + 1, z + 1, vertices[2]);
+ callback->processTriangle(vertices, x, z);
+
+ // Second triangle
+ shape->getVertex(x, z, vertices[0]);
+ shape->getVertex(x + 1, z + 1, vertices[1]);
+ shape->getVertex(x, z + 1, vertices[2]);
+ callback->processTriangle(vertices, x, z);
+ }
+ else
+ {
+ // First triangle
+ shape->getVertex(x, z, vertices[0]);
+ shape->getVertex(x, z + 1, vertices[1]);
+ shape->getVertex(x + 1, z, vertices[2]);
+ callback->processTriangle(vertices, x, z);
+
+ // Second triangle
+ shape->getVertex(x + 1, z, vertices[0]);
+ shape->getVertex(x, z + 1, vertices[1]);
+ shape->getVertex(x + 1, z + 1, vertices[2]);
+ callback->processTriangle(vertices, x, z);
+ }
+ }
+
+ void operator ()(const GridRaycastState &bs) const
+ {
+ exec(bs.prev_x, bs.prev_z);
+ }
+};
+
+
+struct ProcessVBoundsAction
+{
+ const btHeightfieldTerrainShape::Range *vbounds;
+ int width;
+ int length;
+ int chunkSize;
+
+ btVector3 rayBegin;
+ btVector3 rayEnd;
+ btVector3 rayDir;
+
+ ProcessTrianglesAction processTriangles;
+
+ void operator ()(const GridRaycastState &rs) const
+ {
+ int x = rs.prev_x;
+ int z = rs.prev_z;
+
+ if(x < 0 || z < 0 || x >= width || z >= length)
+ return;
+
+ const btHeightfieldTerrainShape::Range chunk = vbounds[x + z * width];
+
+ btVector3 enterPos;
+ btVector3 exitPos;
+
+ if (rs.maxDistanceFlat > 0.0001)
+ {
+ btScalar flatTo3d = chunkSize * rs.maxDistance3d / rs.maxDistanceFlat;
+ btScalar enterParam3d = rs.prevParam * flatTo3d;
+ btScalar exitParam3d = rs.param * flatTo3d;
+ enterPos = rayBegin + rayDir * enterParam3d;
+ exitPos = rayBegin + rayDir * exitParam3d;
+
+ // We did enter the flat projection of the AABB,
+ // but we have to check if we intersect it on the vertical axis
+ if (enterPos[1] > chunk.max && exitPos[1] > chunk.max)
+ return;
+ if (enterPos[1] < chunk.min && exitPos[1] < chunk.min)
+ return;
+ }
+ else
+ {
+ // Consider the ray vertical
+ // (though we shouldn't reach this often because there is an early check up-front)
+ enterPos = rayBegin;
+ exitPos = rayEnd;
+ }
+
+ gridRaycast(processTriangles, enterPos, exitPos);
+ // Note: it could be possible to have more than one grid at different levels,
+ // to do this there would be a branch using a pointer to another ProcessVBoundsAction
+ }
+};
+
+
+// TODO How do I interrupt the ray when there is a hit? `callback` does not return any result
+/// Performs a raycast using a hierarchical Bresenham algorithm.
+/// Does not allocate any memory by itself.
+void btHeightfieldTerrainShape::performRaycast(btTriangleCallback* callback, const btVector3& raySource, const btVector3& rayTarget) const
+{
+ // Transform to cell-local
+ btVector3 beginPos = raySource / m_localScaling;
+ btVector3 endPos = rayTarget / m_localScaling;
+ beginPos += m_localOrigin;
+ endPos += m_localOrigin;
+
+ ProcessTrianglesAction processTriangles;
+ processTriangles.shape = this;
+ processTriangles.flipQuadEdges = m_flipQuadEdges;
+ processTriangles.useDiamondSubdivision = m_useDiamondSubdivision;
+ processTriangles.callback = callback;
+ processTriangles.width = m_heightStickWidth - 1;
+ processTriangles.length = m_heightStickLength - 1;
+
+ // TODO Transform vectors to account for m_upAxis
+ int iBeginX = static_cast<int>(floor(beginPos[0]));
+ int iBeginZ = static_cast<int>(floor(beginPos[2]));
+ int iEndX = static_cast<int>(floor(endPos[0]));
+ int iEndZ = static_cast<int>(floor(endPos[2]));
+
+ if (iBeginX == iEndX && iBeginZ == iEndZ)
+ {
+ // The ray will never cross quads within the plane,
+ // so directly process triangles within one quad
+ // (typically, vertical rays should end up here)
+ processTriangles.exec(iBeginX, iEndZ);
+ return;
+ }
+
+ if (m_vboundsGrid == NULL)
+ {
+ // Process all quads intersecting the flat projection of the ray
+ gridRaycast(processTriangles, beginPos, endPos);
+ }
+ else
+ {
+ btVector3 rayDiff = endPos - beginPos;
+ btScalar flatDistance2 = rayDiff[0] * rayDiff[0] + rayDiff[2] * rayDiff[2];
+ if (flatDistance2 < m_vboundsChunkSize * m_vboundsChunkSize)
+ {
+ // Don't use chunks, the ray is too short in the plane
+ gridRaycast(processTriangles, beginPos, endPos);
+ }
+
+ ProcessVBoundsAction processVBounds;
+ processVBounds.width = m_vboundsGridWidth;
+ processVBounds.length = m_vboundsGridLength;
+ processVBounds.vbounds = m_vboundsGrid;
+ processVBounds.rayBegin = beginPos;
+ processVBounds.rayEnd = endPos;
+ processVBounds.rayDir = rayDiff.normalized();
+ processVBounds.processTriangles = processTriangles;
+ processVBounds.chunkSize = m_vboundsChunkSize;
+ // The ray is long, run raycast on a higher-level grid
+ gridRaycast(processVBounds, beginPos / m_vboundsChunkSize, endPos / m_vboundsChunkSize);
+ }
+}
+
+
+/// Builds a grid data structure storing the min and max heights of the terrain in chunks.
+/// if chunkSize is zero, that accelerator is removed.
+/// If you modify the heights, you need to rebuild this accelerator.
+void btHeightfieldTerrainShape::buildAccelerator(int chunkSize)
+{
+ if (chunkSize <= 0)
+ {
+ clearAccelerator();
+ return;
+ }
+
+ m_vboundsChunkSize = chunkSize;
+ int nChunksX = m_heightStickWidth / chunkSize;
+ int nChunksZ = m_heightStickLength / chunkSize;
+
+ if (m_heightStickWidth % chunkSize > 0)
+ ++nChunksX; // In case terrain size isn't dividable by chunk size
+ if (m_heightStickLength % chunkSize > 0)
+ ++nChunksZ;
+
+ if(m_vboundsGridWidth != nChunksX || m_vboundsGridLength != nChunksZ)
+ {
+ clearAccelerator();
+ m_vboundsGridWidth = nChunksX;
+ m_vboundsGridLength = nChunksZ;
+ }
+
+ if (nChunksX == 0 || nChunksZ == 0)
+ return;
+
+ // TODO What is the recommended way to allocate this?
+ // This data structure is only reallocated if the required size changed
+ if (m_vboundsGrid == NULL)
+ m_vboundsGrid = new Range[nChunksX * nChunksZ];
+
+ // Compute min and max height for all chunks
+ for (int cz = 0; cz < nChunksZ; ++cz)
+ {
+ int z0 = cz * chunkSize;
+
+ for (int cx = 0; cx < nChunksX; ++cx)
+ {
+ int x0 = cx * chunkSize;
+
+ Range r;
+
+ r.min = getRawHeightFieldValue(x0, z0);
+ r.max = r.min;
+
+ // Compute min and max height for this chunk.
+ // We have to include one extra cell to account for neighbors.
+ // Here is why:
+ // Say we have a flat terrain, and a plateau that fits a chunk perfectly.
+ //
+ // Left Right
+ // 0---0---0---1---1---1
+ // | | | | | |
+ // 0---0---0---1---1---1
+ // | | | | | |
+ // 0---0---0---1---1---1
+ // x
+ //
+ // If the AABB for the Left chunk did not share vertices with the Right,
+ // then we would fail collision tests at x due to a gap.
+ //
+ for (int z = z0; z < z0 + chunkSize + 1; ++z)
+ {
+ if (z >= m_heightStickLength)
+ continue;
+
+ for (int x = x0; x < x0 + chunkSize + 1; ++x)
+ {
+ if (x >= m_heightStickWidth)
+ continue;
+
+ btScalar height = getRawHeightFieldValue(x, z);
+
+ if (height < r.min)
+ r.min = height;
+ else if (height > r.max)
+ r.max = height;
+ }
+ }
+
+ m_vboundsGrid[cx + cz * nChunksX] = r;
+ }
+ }
+}
+
+
+void btHeightfieldTerrainShape::clearAccelerator()
+{
+ if (m_vboundsGrid)
+ {
+ // TODO What is the recommended way to deallocate this?
+ delete[] m_vboundsGrid;
+ m_vboundsGrid = 0;
+ }
+}
+
+
diff --git a/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h b/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h
index 8a50a57e31..e23b548cb2 100644
--- a/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h
+++ b/thirdparty/bullet/BulletCollision/CollisionShapes/btHeightfieldTerrainShape.h
@@ -18,6 +18,7 @@ subject to the following restrictions:
#include "btConcaveShape.h"
+
///btHeightfieldTerrainShape simulates a 2D heightfield terrain
/**
The caller is responsible for maintaining the heightfield array; this
@@ -71,6 +72,12 @@ subject to the following restrictions:
ATTRIBUTE_ALIGNED16(class)
btHeightfieldTerrainShape : public btConcaveShape
{
+public:
+ struct Range {
+ btScalar min;
+ btScalar max;
+ };
+
protected:
btVector3 m_localAabbMin;
btVector3 m_localAabbMax;
@@ -100,9 +107,14 @@ protected:
btVector3 m_localScaling;
+ // Accelerator
+ Range *m_vboundsGrid;
+ int m_vboundsGridWidth;
+ int m_vboundsGridLength;
+ int m_vboundsChunkSize;
+
virtual btScalar getRawHeightFieldValue(int x, int y) const;
void quantizeWithClamp(int* out, const btVector3& point, int isMax) const;
- void getVertex(int x, int y, btVector3& vertex) const;
/// protected initialization
/**
@@ -154,6 +166,13 @@ public:
virtual void setLocalScaling(const btVector3& scaling);
virtual const btVector3& getLocalScaling() const;
+
+ void getVertex(int x,int y,btVector3& vertex) const;
+
+ void performRaycast (btTriangleCallback* callback, const btVector3& raySource, const btVector3& rayTarget) const;
+
+ void buildAccelerator(int chunkSize=16);
+ void clearAccelerator();
//debugging
virtual const char* getName() const { return "HEIGHTFIELD"; }
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-30 01:12:12 +0000