OSG中的弹跳球（译文）

原文地址：https://www.codeproject.com/Articles/28939/Bouncing-Balls-in-OSG

原文作者：Adrian Savage

译文由本站 robot-v1.0 翻译

前言

Simulation in OSG using discrete events, a Ternary Heap and Interpolation

使用离散事件,三元堆和插值在OSG中进行仿真

• 下载源34.24 KB(Download source - 34.24 KB)

内容(Contents)

• 介绍(Introduction)
• 动机(Motivation)
• 总览(Overview)
• 建造(Building)
• OSG场景(OSG Scene)
• 优先队列(Priority Queue)
• 三元堆(Ternary Heap)
• 连续运动和插补(Continuous Motion and Interpolation)
• 变化(事件)(Changes (Events))
• 修订记录(Revision History)

介绍(Introduction)

该项目是模拟的演示,其中对象可以连续(移动和旋转球)并且瞬时(碰撞)变化.它适用于OSG(至少2.2版)和Visual Studio/Express 2005或2008.(This project is a demonstration of a simulation in which objects can change continuously (moving and rotating balls) and instantaneously (collisions). It is for OSG (at least version 2.2) and Visual Studio/Express 2005 or 2008.)

动机(Motivation)

许多物理模拟通过以固定的时间间隔执行计算来估计对象的位置.这为许多使用有限元分析的仿真引擎提供了很好的结果,例如(Many physical simulations estimate positions of objects by performing calculations at regular intervals of time. This gives great results for a number of simulation engines that use finite element analysis such as) 颂(ODE) .但是,如果时间间隔过长,则可能会导致精度降低-例如,应该碰撞的对象会彼此飞越.我创建了这个项目,以通过计算发生更改的确切时间(在本示例中为发生冲突的时间)来对系统建模.这样,仿真可以更快地运行而不会损失准确性.(. But this can result in a loss of accuracy if the time intervals are too long - for example, objects which should collide, fly through each other instead. I created this project to model a system by calculating the exact time a change occurs - in this example, when a collision occurs. In this way, a simulation can run more quickly without loss of accuracy.) 在许多示例OSG应用程序中,对象在渲染每一帧后都会更新,从而导致动作抖动.在此示例中,对象使用(In many sample OSG applications, objects are updated after rendering each frame, resulting in a jerky motion. In this example, the objects are updated with an) osg::NodeCallback 这样他们才能平稳移动.(so that they move smoothly.)

总览(Overview)

该模拟可预测弹跳在盒子中的球的位置和旋转,并通过OSG渲染它们的运动.它根据球的当前轨迹预测球何时碰撞,并处理这些碰撞.随着仿真的进行,它必须检查是否应该进行任何更改.如果是这样,它将找到下一个预测的变化,并通过更新当时球的速度进行处理.(The simulation predicts the position and rotation of balls bouncing in a box, rendering their motion with OSG. It predicts when balls collide based on their current trajectory, and processes these collisions. As the simulation moves forward in time, it must check whether any changes should have occurred. If so, it finds the next predicted change, and processes it by updating the velocity of the balls at that time.)

建造(Building)

要构建或运行此项目,请使用OSG((To build or run this project, OSG () OpenSceneGraph )必须安装.通过按照链接下载适用于Visual Studio相关版本的预构建二进制文件,可以最轻松地完成此操作() must be installed. This is most easily done by downloading pre-built binaries for the relevant version of Visual Studio by following the links) 这里(here) ,在这种情况下,应在发布模式下构建该项目.(, in which case this project should be built in release mode.)

OSG场景(OSG Scene)

OSG场景包含一个透明框((The OSG scene consists of a transparent box () osg::Box ,(,) osg::Material )和多个球体(() and a number of spheres () osg::Sphere )的表面() with a textured surface () osg::Texture2D ),它会旋转和旋转(() which moves and rotates () osg::PositionAttitudeTransform ,(,) osg::NodeCallback ).().)

优先队列(Priority Queue)

优先级队列是允许我们添加项目和删除优先级最高的项目的任何数据结构.在这种情况下,项目是由于碰撞预测而引起的变化.如果预计将首先发生更改,则该更改的优先级高于其他更改.该模拟使用优先级队列来查找下一个更改,以便可以随时给出准确的情况. STL库包含一个优先级队列,但是我们还希望能够在碰撞后更新模拟时增加或减少项目的优先级.(A priority queue is any data structure which allows us to add items, and to remove the item with the highest priority. In this case, the items are the changes due to collision predictions. One change has higher priority than another if it is predicted to occur first. The simulation uses a priority queue to find the next change so that it can give the accurate situation at any time. The STL library contains a priority queue, but we also want to be able to increase or decrease the priority of items when the simulation is updated after a collision.)

三元堆(Ternary Heap)

堆是一棵树,其中每个项的父项具有更高的优先级,而根项具有最高的优先级.这称为堆属性.我们可以使用堆作为优先级队列.(A heap is a tree in which the parent of each item has a higher priority, and the root item has the highest priority. This is known as the heap property. We can use a heap as a priority queue.) 在三元堆中,每个项目都有3个子项(最后一个项目可能除外,为添加或删除项目留出空间).这些项目存储在一个数组中.这很容易维护,也很容易在数组的特定索引处找到项目的父项和第一个子项. (三元堆的性能优于二进制堆.)(In a ternary heap, each item has 3 children (except possibly the last item, leaving room to add or remove items). The items are stored in an array. This is easy to maintain and it is also easy to find the parent and first child of an item at a particular index in the array. (A ternary heap performs better than a binary heap.))

int Parent(int index)
{
return (index - 1) / 3;
}
int Child(int index)
{
return index * 3 + 1;
} 

当项目在堆中的优先级发生变化时,这可能会破坏堆属性,但事实证明,我们可以与其父项或子项交换项目,直到恢复堆属性(向上或向下移动)为止,这使我们能够更改,添加或删除堆中的项目.(When the priority of an item in the heap changes, this may break the heap property, but it turns out that we can swap an item with its parent or child until the heap property is restored (shifting up or down), and this allows us to change, add or remove items in the heap.) 我们可以通过将项目附加到数组的末尾,然后将其向上移动到堆中来将其添加到堆中.我们还可以通过与数组的最后一项交换,删除最后一项并向下移动新的根来删除数组中的第一项(堆的根).(We can add items to the heap by appending them to the end of the array, then shifting the item up the heap. We can also remove the first item in the array (the root of the heap) by swapping with the last item of the array, removing the last item, and shifting the new root down.)

连续运动和插补(Continuous Motion and Interpolation)

建议在OSG中更新对象的位置和旋转的方法是使用(The recommended way to update the position and rotation of objects in OSG is to use an) osg::NodeCallback 目的.这用于使仿真更新为渲染帧的正确时间.然后更新球的位置和旋转.(object. This is used to bring the simulation up-to-date for the correct time of the frame being rendered. Then the position and rotation of the ball is updated.) 如果某时球的位置(If the position of a ball at time) t0 是一个向量(is a vector) s0 ,它的速度是一个常数向量(, and its velocity is a constant vector) v0 ,那么很容易随时计算(插值)其位置(, then it is simple to calculate (interpolate) its position at any time) `` .(.)

s = s0 + (t-t0) * v0 

如果它旋转的时候(If its rotation at time) t0 用四元数表示(is represented by a quaternion) rot0 它的角速度是(and its angular velocity is) a0 然后我们也可以旋转球. (我避免了(then we can also rotate the ball. (I have avoided) osg::Quat::slerp 会在两个四元数之间进行插值,因为它对于我们的目的而言不太准确).旋转四元数计算如下:(which interpolates between two quaternions as it is less accurate for our purposes). The rotation quaternion is calculated as follows:)

osg::Quat Rotation( double time ) const
{
double angular_speed = a0.length();
if( angular_speed < 1.0e-5 )
return rot0;
double t = time - t0;
double half_angle = 0.5 * t * angular_speed;
double cos_half_angle = cos( half_angle );
double sin_half_angle = sin( half_angle );
double factor = sin_half_angle/angular_speed;
osg::Quat rotation;
rotation.x() = a0.x() * factor;
rotation.y() = a0.y() * factor;
rotation.z() = a0.z() * factor;
rotation.w() = cos_half_angle;
return rot0 * rotation;
} 

变化(事件)(Changes (Events))

当球碰撞时,球的速度会改变,因此必须重新计算其碰撞预测.(When a ball collides, the velocity of the ball is changed, so its collision predictions must be recalculated.) 球和壁之间的碰撞很容易预测和处理,因为壁与壁对齐.(Collisions between balls and walls are easy enough to predict and process since the walls are aligned with the) x ,(,) y ,(,) z 轴.(axes.) 我发现使用矢量可以轻松解决两个球之间的碰撞.让(I found collisions between two balls easier to work out using vectors. Let) v 和(and) s 一次是两个球之间的相对速度和位置(be the relative velocity and position between two balls at a time) t0 .我们想找时间(. We want to find the time) t 当相对位置向量具有幅度时(when the relative position vector has magnitude) r (球半径的总和).然后我们可以如下预测碰撞:((the sum of the ball’s radii). Then we can predict the collision as follows:)

double s2 = s * s; // dot product
double v2 = v * v; // "
double sv = s * v; // "
double r = b0->radius + b1->radius;
double r2 = r * r;
double sqr = sv*sv - v2 * (s2 - r2 );
if( sqr > 0.00001 )
{
double t = t0 + ( - sqrt( sqr ) - sv ) / v2;
if( t > time )
{
// Collision occurs at time t
ChangeTime( t );
Enable( true );
}
else
{
// Collision occurred in the past
Enable( false );
}
}
else
{
// Collision does not occur
Enable( false );
} 

修订记录(Revision History)

• 29(29)日(th)2008年8月:原始文章(August, 2008: Original article)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。