经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » 游戏设计 » 查看文章
功能实现的数学模型选择 -- (点与线段交点的例子)
来源：cnblogs　　作者：tiancaiKG　　时间：2019/6/18 8:39:26　　对本文有异议

　　在实现很多数学相关的功能的时候, 数学模型的选择尤为重要, 一个是在准确性上, 一个是在扩展性上.

比如最近我要计算一个射线跟一个线段的交点, 初中的时候就学过, 直线和直线外一点的交点怎样计算, 这里

直接上已经写完的两段代码.

简图

 

　　因为是计算机, 肯定是通过两点来确定直线方程了, 首先是用点斜式的计算方法( 原始方程 y = kx + b, 推导过程略 ): 

  1.         /// <summary>
  2.         /// 点斜式推理出的交点方程
  3.         /// </summary>
  4.         /// <param name="ray"></param>
  5.         /// <param name="p1"></param>
  6.         /// <param name="p2"></param>
  7.         /// <param name="point"></param>
  8.         /// <returns></returns>
  9.         [System.Obsolete("Incorrect", false)]
  10.         public static bool IntersectRayAndLineSegment_XOZ_PointSlope(Ray ray, Vector3 p1, Vector3 p2, out Vector3 point)
  11.         {
  12.             var p3 = new Vector3(ray.origin.x, 0, ray.origin.z);
  14.             float k1 = (p2.z - p1.z) / (p2.x - p1.x);
  15.             float k2 = -1.0f / k1;
  16.             float b1 = p1.z - (k1 * p1.x);
  17.             float b2 = p3.z - (k2 * p3.x);
  19.             float x = (b2 - b1) / (k1 - k2);
  20.             float z = x * k1 + b1;
  22.             point = new Vector3(x, 0, z);
  23.             var rayDir = ray.direction;
  24.             rayDir.y = 0;
  26.             bool intersect = Vector3.Dot(point - p3, rayDir) > 0;
  27.             if(intersect)
  28.             {
  29.                 intersect = (x >= Mathf.Min(p1.x, p2.x) && x <= Mathf.Max(p1.x, p2.x)) && (z >= Mathf.Min(p1.z, p2.z) && z <= Mathf.Max(p1.z, p2.z));
  30.             }
  31.             return intersect;
  32.         }

 

　　然后是两点式的计算方法( 原始方程 (y-y1)/(x-x1) = (y-y2)/(x-x2), 推导过程略 ):

  1.     /// <summary>
  2.     /// 两点式推出的交点方程
  3.     /// </summary>
  4.     /// <param name="ray"></param>
  5.     /// <param name="p1"></param>
  6.     /// <param name="p2"></param>
  7.     /// <param name="point"></param>
  8.     /// <returns></returns>
  9.     public static bool IntersectRayAndLineSegment_XOZ_TwoPoint(Ray ray, Vector3 p1, Vector3 p2, out Vector3 point)
  10.     {
  11.         point = Vector3.zero;
  12.         Vector3 p3 = new Vector3(ray.origin.x, 0, ray.origin.z);
  13.         Vector3 p4 = ray.GetPoint(1.0f);
  14.         p4.y = 0;
  16.         float a1, b1, c1;
  17.         PointToLineEquation_2D_XOZ(p1, p2, out a1, out b1, out c1);
  18.         float a2, b2, c2;
  19.         PointToLineEquation_2D_XOZ(p3, p4, out a2, out b2, out c2);
  21.         float D = a1 * b2 - a2 * b1;
  22.         if(D == 0)
  23.         {
  24.             return false;
  25.         }
  26.         float D1 = -c1 * b2 + c2 * b1;
  27.         float D2 = -c2 * a1 + a2 * c1;
  28.         point = new Vector3(D1 / D, 0, D2 / D);
  29.         var rayDir = ray.direction;
  30.         rayDir.y = 0;
  32.         bool intersect = Vector3.Dot(point - p3, rayDir) > 0;
  33.         if(intersect)
  34.         {
  35.             intersect = (point.x >= Mathf.Min(p1.x, p2.x) && point.x <= Mathf.Max(p1.x, p2.x)) && (point.z >= Mathf.Min(p1.z, p2.z) && point.z <= Mathf.Max(p1.z, p2.z));
  36.         }
  37.         return intersect;
  38.     }
  39.     public static void PointToLineEquation_2D_XOZ(Vector3 p1, Vector3 p2, out float a, out float b, out float c)
  40.     {
  41.         float x1 = p1.x;
  42.         float y1 = p1.z;
  44.         float x2 = p2.x;
  45.         float y2 = p2.z;
  47.         a = y2 - y1;
  48.         b = x1 - x2;
  49.         c = (y1 * x2) - (y2 * x1);
  50.     }

 

　　在大部分情况下它们的结果是正确的, 可是在线段是平行于坐标轴的情况下, 点斜式的结果就不对了, 往回看计算过程: 

  1.             var p3 = new Vector3(ray.origin.x, 0, ray.origin.z);
  3.             float k1 = (p2.z - p1.z) / (p2.x - p1.x);
  4.             float k2 = -1.0f / k1;
  5.             float b1 = p1.z - (k1 * p1.x);
  6.             float b2 = p3.z - (k2 * p3.x);
  8.             float x = (b2 - b1) / (k1 - k2);
  9.             float z = x * k1 + b1;

 

　　点斜式在刚开始就计算了斜率k, 然后k被作为了分母参与计算, 这样在平行于x轴的时候斜率就是0, 被除之后得到无穷大(或无穷小), 在平行y轴的时候( 两点的x相等 ), k直接就是无穷大(或无穷小).

所以点斜式在计算平行于坐标轴的情况就不行了. 点斜式的问题就在于过早进行了除法计算, 而且分母还可能为0, 这在使用计算机的系统里面天生就存在重大隐患.

 

　　然后是两点式, 它的过程是由两点式推算出一般方程的各个变量( 一般方程 ax + by + c = 0 ), 然后联立两个一般方程来进行求解, 它的稳定性就体现在这里:

  1.         a = y2 - y1;
  2.         b = x1 - x2;
  3.         c = (y1 * x2) - (y2 * x1);

　　它的初始计算完全不涉及除法, 第一步天生就是计算上稳定的.

　　然后是计算联立方程的方法, 这里直接用了二元一次线性方程组的求解:

  1.         float D = a1 * b2 - a2 * b1;
  2.         if(D == 0)
  3.         {
  4.             return false;
  5.         }
  6.         float D1 = -c1 * b2 + c2 * b1;
  7.         float D2 = -c2 * a1 + a2 * c1;
  8.         point = new Vector3(D1 / D, 0, D2 / D);

 

　　使用行列式计算的好处是很容易判断出是否有解, D==0 时就是无解, 这也是计算稳定性的保证, 然后这里是只计算x, z平面的, 也就是2D的,

如果要计算3D的或更高阶的, 只需要把行列式和一般方程封装成任意元的多元方法即可, 例如一般方程为( ax + by + cz + d = 0 )甚至更高阶的(  ax + by + cz + dw......+n = 0  ),

然后行列式求多元线性方程组的解就更简单了, 这就提供了很强大的扩展性, 不仅2维, 3维, 甚至N维都能提供解. 

　　所以在做功能前仔细想好怎样做, 慎重选择数学模型是非常重要的. 虽然这些活看似初中生也能做, 大学生也能做, 差距还是一目了然的吧.

 

补充一下上面说过的多元线性方程组的解, 分成行列式和线性方程组:

  1.     public class Determinant
  2.     {
  3.         public int order { get; private set; }
  4.         public float[,] matrix { get; private set; }
  6.         private int m_index = 0;
  8.         public Determinant(int order)
  9.         {
  10.             if(order < 2)
  11.             {
  12.                 throw new System.Exception("order >= 2 !!");
  13.             }
  14.             this.order = order;
  15.             CreateMatrix();
  16.         }
  18.         #region Main Funcs
  19.         public void SetColumn(int column, params float[] values)
  20.         {
  21.             if(column >= 0 && column < order && values != null)
  22.             {
  23.                 for(int i = 0, imax = Mathf.Min(order, values.Length); i < imax; i++)
  24.                 {
  25.                     matrix[i, column] = values[i];
  26.                 }
  27.             }
  28.         }
  29.         public void SetRow(int row, params float[] values)
  30.         {
  31.             if(row >= 0 && row < order && values != null)
  32.             {
  33.                 for(int i = 0, imax = Mathf.Min(order, values.Length); i < imax; i++)
  34.                 {
  35.                     matrix[row, i] = values[i];
  36.                 }
  37.             }
  38.         }
  39.         public void SetRow(params float[] values)
  40.         {
  41.             SetRow(m_index, values);
  42.             m_index++;
  43.         }
  44.         public Determinant Clone()
  45.         {
  46.             Determinant tag = new Determinant(this.order);
  47.             System.Array.Copy(matrix, tag.matrix, matrix.Length);
  48.             return tag;
  49.         }
  50.         public Determinant GetSubDeterminant(int row, int column)
  51.         {
  52.             Determinant tag = new Determinant(this.order - 1);
  53.             for(int i = 0, tagRow = 0; i < order; i++)
  54.             {
  55.                 if(i == row)
  56.                 {
  57.                     continue;
  58.                 }
  59.                 for(int j = 0, tagColumn = 0; j < order; j++)
  60.                 {
  61.                     if(j == column)
  62.                     {
  63.                         continue;
  64.                     }
  65.                     tag.matrix[tagRow, tagColumn] = this.matrix[i, j];
  66.                     tagColumn++;
  67.                 }
  68.                 tagRow++;
  69.             }
  70.             return tag;
  71.         }
  72.         public float GetValue()
  73.         {
  74.             if(order == 2)
  75.             {
  76.                 float value = matrix[0, 0] * matrix[1, 1] - matrix[0, 1] * matrix[1, 0];
  77.                 return value;
  78.             }
  79.             else
  80.             {
  81.                 float value = 0.0f;
  82.                 int row = order - 1;
  84.                 for(int column = 0; column < order; column++)
  85.                 {
  86.                     var aij = matrix[row, column] * ((row + column) % 2 > 0 ? -1 : 1);
  87.                     var subMatrix = GetSubDeterminant(row, column);
  88.                     var mij = subMatrix.GetValue();
  89.                     float tempValue = (aij * mij);
  90.                     value += tempValue;
  91.                 }
  93.                 return value;
  94.             }
  95.         }
  96.         #endregion
  97.  
  98.         #region Help Funcs
  99.         private void CreateMatrix()
  100.         {
  101.             matrix = new float[order, order];
  102.         }
  103.         #endregion
  104.     }
  106.     public class DeterminantEquation
  107.     {
  108.         public Determinant determinant { get; private set; }
  109.         public int order
  110.         {
  111.             get
  112.             {
  113.                 return determinant != null ? determinant.order : 0;
  114.             }
  115.         }
  117.         public DeterminantEquation(int order)
  118.         {
  119.             determinant = new Determinant(order);
  120.         }
  122.         #region Main Funcs
  123.         public float[] CaculateVariables(params float[] values)
  124.         {
  125.             var D = determinant.GetValue();
  126.             if(D == 0)
  127.             {
  128.                 Debug.LogWarning("This Determinant has no Result !!");
  129.                 return null;
  130.             }
  132.             float[] variables = new float[order];
  133.             for(int i = 0; i < order; i++)
  134.             {
  135.                 var subDeterminant = determinant.Clone();
  136.                 subDeterminant.SetColumn(i, values);
  137.                 var Di = subDeterminant.GetValue();
  138.                 var variable = Di / D;
  139.                 variables[i] = variable;
  140.             }
  141.             return variables;
  142.         }
  143.         #endregion
  144.     }

　　因为多元方程组的一般方程就是 NxN 的等边矩阵, 所以行列数量是一样的, 用二维数组表示. 各个解通过克拉默法则计算得出.

而行列式值的计算就通过按行展开, 降阶通过代数余子式计算. 这样就可以计算任意阶的方程组了.

　　那么两点式的计算代码改一改, 就能看出扩展性了:

  1.         /// <summary>
  2.         /// 两点式推出的交点方程
  3.         /// </summary>
  4.         /// <param name="ray"></param>
  5.         /// <param name="p1"></param>
  6.         /// <param name="p2"></param>
  7.         /// <param name="point"></param>
  8.         /// <returns></returns>
  9.         public static bool IntersectRayAndLineSegment_XOZ_TwoPoint(Ray ray, Vector3 p1, Vector3 p2, out Vector3 point)
  10.         {
  11.             point = Vector3.zero;
  12.             Vector3 p3 = new Vector3(ray.origin.x, 0, ray.origin.z);
  13.             Vector3 p4 = ray.GetPoint(1.0f);
  14.             p4.y = 0;
  16.             float a1, b1, c1;
  17.             PointToLineEquation_2D_XOZ(p1, p2, out a1, out b1, out c1);
  18.             float a2, b2, c2;
  19.             PointToLineEquation_2D_XOZ(p3, p4, out a2, out b2, out c2);
  21.             //float D = a1 * b2 - a2 * b1;
  22.             //if(D == 0)
  23.             //{
  24.             //    return false;
  25.             //}
  26.             //float D1 = -c1 * b2 + c2 * b1;
  27.             //float D2 = -c2 * a1 + a2 * c1;
  28.             //point = new Vector3(D1 / D, 0, D2 / D);
  30.             DeterminantEquation determinantEquation = new DeterminantEquation(2);
  31.             determinantEquation.determinant.SetRow(a1, b1);
  32.             determinantEquation.determinant.SetRow(a2, b2);
  33.             var variables = determinantEquation.CaculateVariables(-c1, -c2);
  34.             if(variables == null)
  35.             {
  36.                 return false;
  37.             }
  38.             point = new Vector3(variables[0], 0, variables[1]);
  40.             var rayDir = ray.direction;
  41.             rayDir.y = 0;
  43.             bool intersect = Vector3.Dot(point - p3, rayDir) > 0;
  44.             if(intersect)
  45.             {
  46.                 intersect = (point.x >= Mathf.Min(p1.x, p2.x) && point.x <= Mathf.Max(p1.x, p2.x)) && (point.z >= Mathf.Min(p1.z, p2.z) && point.z <= Mathf.Max(p1.z, p2.z));
  47.             }
  48.             return intersect;
  49.         }
  50.         /// <summary>
  51.         /// 一般方程变量计算
  52.         /// </summary>
  53.         /// <param name="p1"></param>
  54.         /// <param name="p2"></param>
  55.         /// <param name="a"></param>
  56.         /// <param name="b"></param>
  57.         /// <param name="c"></param>
  58.         public static void PointToLineEquation_2D_XOZ(Vector3 p1, Vector3 p2, out float a, out float b, out float c)
  59.         {
  60.             float x1 = p1.x;
  61.             float y1 = p1.z;
  63.             float x2 = p2.x;
  64.             float y2 = p2.z;
  66.             a = y2 - y1;
  67.             b = x1 - x2;
  68.             c = (y1 * x2) - (y2 * x1);
  69.         }

　　把行列式的类( Determinant ) 改成结构体应该在效率上会高效一些.

PS: 数学模型这里有两个, 第一个是通过各个点获取联立方程, 第二个是怎样解联立方程

　　点斜式获取的是点斜式方程

　　y = k1*x + b1 

　　y = k2*x + b2 

　　

　　两点式获取的是标准方程

　　 a1*x + b1*y + c1 = 0

 　　a2*x + b2*y + c2 = 0

这两个方程的计算差别上面已经说了.

解联立方程的方法也用了两种, 点斜式用的是一般推论, 就是普通的求解过程, 两点式使用了线性代数(注意点斜式的联立方程也能用线性方程解的, 只是作为对比),

可以预想到如果联立方程的维数增加到很多的时候一般求解过程的难度会大大增加, 

比如

　　3元方程 -> 6个变量

　　4元方程 -> 24个变量

　　5元方程 -> 120个变量... 所以初中生最多就教到3元方程

而 DeterminantEquation 这个类就能很简单的计算出多元方程式的解. 所以在扩展性上胜出.

 

原文链接：http://www.cnblogs.com/tiancaiwrk/p/11039595.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

游戏设计热门文章

  • DirectX11--深入理解与使用2D纹理资源
  • unity渲染篇：烘焙模型贴图
  • Unity导入模型出现 (Avatar Rig Configuration mis-match. Bone length in configuration does not match position in animation)?
  • Unreal: Dynamic load map from Pak file
  • 《unity 3D 游戏开发 第二版》宣雨松 分享 pdf下载
  • 空间划分的数据结构(网格/四叉树/八叉树/BSP树/k-d树/BVH/自定义划分)
  • Unity编辑器汉化(中文语言包)
  • [Unity编辑器扩展基础总结] 第3章 编辑器下的数据保存
  • Unity 3D游戏开发 pdf高清下载
  • 用C#写一个俄罗斯方块

    • 游戏设计推荐文章

  • Unity3D开发入门教程（二）—— Lua入门
  • Unity3D开发入门教程（三）——添加启动脚本
  • Unity3D开发入门教程（四）——用Lua实现组件
  • RectMask2D裁剪Canvas无效问题
  • Python编程环境设置
  • Minecraft类游戏地形生成机制
  • 3D网页小实验-基于Babylon.js与recast.js实现RTS式单位控制
  • Unity3D OpenVR 虚拟现实 保龄球打砖块游戏开发
  • [Unity编辑器扩展基础总结] 第3章 编辑器下的数据保存
  • 关于看门狗的两种模型以及带来的思考

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号