指向定向包围盒内？ [英] Point inside Oriented Bounding Box?

问题描述

我有一个基于SAT的OBB2D类。

这是我在OBB方法中的要点：

<$ p
$ new $（float）（Math.sin（angle）*（y - center.y）+ Math.cos（angle）*
（x - center.x））;
float newx =（float）（Math.cos（angle）*（x - center.x） - Math.sin（angle）*
（y - center.y））;
return（newy> center.y - （getHeight（）/ 2））&&
（newy< center.y +（getHeight（）/ 2））
&& （newx> center.x - （getWidth（）/ 2））&&
（newx< center.x +（getWidth（）/ 2））;


public boolean pointInside（Vector2D v）
{
return pointInside（v.x，v.y）;
}

这是课程的其余部分;相关的部分：

 公共类OBB2D 
 {
私有Vector2D projVec = new Vector2D（）; 
 private static Vector2D projAVec = new Vector2D（）; 
 private static Vector2D projBVec = new Vector2D（）; 
 private static Vector2D tempNormal = new Vector2D（）; 
 private Vector2D deltaVec = new Vector2D（）; 
 private ArrayList< Vector2D> collisionPoints = new ArrayList< Vector2D>（）; 
 
 
 //框的角落，其中0是左下角。 
 private Vector2D corner [] = new Vector2D [4]; 
 
 private Vector2D center = new Vector2D（）; 
 private Vector2D extents = new Vector2D（）; 
 
 private RectF boundingRect = new RectF（）; 
私人浮动角度; 
 
 //盒子的两个边缘远离角落[0]延伸。 
 private Vector2D axis [] = new Vector2D [2]; 
 
 private double origin [] = new double [2]; 
 
 public OBB2D（float centerx，float centery，float w，float h，float angle）
 {
 for（int i = 0; i  {
 corner [i] = new Vector2D（）; 
 
（int i = 0; i< axis.length; ++ i）
 {
 axis [i] = new Vector2D（）; 
} 
 set（centerx，centery，w，h，angle）; 
} 
 
 public OBB2D（float left，float top，float width，float height）
 {
 for（int i = 0; i< corner.length ; ++ i）
 {
 corner [i] = new Vector2D（）; 
 
（int i = 0; i< axis.length; ++ i）
 {
 axis [i] = new Vector2D（）; 
} 
 set（left +（width / 2），top +（height / 2），width，height，0.0f）; 
 
 $ b $ public void set（float centerx，float centery，float w，float h，float angle）
 {
 float vxx =（float）Math.cos （角度）; 
 float vxy =（float）Math.sin（angle）; 
 float vyx =（float）-Math.sin（angle）; 
 float vyy =（float）Math.cos（angle）; 
 
 vxx * = w / 2; 
 vxy * =（w / 2）; 
 vyx * =（h / 2）; 
 vyy * =（h / 2）; 
 
 corner [0] .x = centerx  -  vxx  -  vyx; 
 corner [0] .y = centery  -  vxy  -  vyy; 
 corner [1] .x = centerx + vxx  -  vyx; 
 corner [1] .y = centery + vxy  -  vyy; 
 corner [2] .x = centerx + vxx + vyx; 
 corner [2] .y = centery + vxy + vyy; 
 corner [3] .x = centerx  -  vxx + vyx; 
 corner [3] .y = centery  -  vxy + vyy; 
 
 this.center.x = centerx; 
 this.center.y = centery; 
 this.angle = angle; 
 computeAxes（）; 
 extents.x = w / 2; 
 extents.y = h / 2; 
 
 computeBoundingRect（）; 
} 
 
 
 //角落移动后更新坐标轴。假设
 //转角实际上形成一个矩形。 
 private void computeAxes（）
 {
 axis [0] .x = corner [1] .x  -  corner [0] .x; 
 axis [0] .y = corner [1] .y  -  corner [0] .y; 
 axis [1] .x = corner [3] .x  -  corner [0] .x; 
轴[1] .y =转角[3] .y  - 转角[0] .y; 
 
 
 //将每个轴的长度设置为1 /边缘长度，以便我们知道任何
 //点积必须小于1以落入边界内。 
 
 for（int a = 0; a< axis.length; ++ a）
 {
 float l = axis [a] .length（）; 
 float ll = l * l; 
轴[a] .x =轴[a] .x / ll; 
轴[a] .y =轴[a] .y / ll; 
 origin [a] = corner [0] .dot（axis [a]）; 
 
 
 
 
 
 public void computeBoundingRect（）
 {
 boundingRect.left = JMath.min（JMath。 min（corner [0] .x，corner [3] .x），JMath.min（corner [1] .x，corner [2] .x））; 
 boundingRect.top = JMath.min（JMath.min（corner [0] .y，corner [1] .y），JMath.min（corner [2] .y，corner [3] .y）） ; 
 boundingRect.right = JMath.max（JMath.max（corner [1] .x，corner [2] .x），JMath.max（corner [0] .x，corner [3] .x）） ; 
 boundingRect.bottom = JMath.max（JMath.max（corner [2] .y，corner [3] .y），JMath.max（corner [0] .y，corner [1] .y）） ; （rect.centerX（），rect.centerY（），rect.width（），rect.bat .height（），0.0F）; 
} 
 
 //如果其他重叠其中的一个维度，则返回true。 
 private boolean overlapps1Way（OBB2D other）
 {
 for（int a = 0; a< axis.length; ++ a）{
 
 double t = other.corner [0] .DOT（轴[A]）; 
 
 //找出坐标轴2上轴的长度a 
 double tMin = t; 
 double tMax = t; 
 
 for（int c = 1; c< corner.length; ++ c）{
 t = other.corner [c] .dot（axis [a]）; 
 
 if（t  tMin = t; 
} else if（t> tMax）{
 tMax = t; 
} 
} 
 
 //我们必须减去原点
 
 //查看[tMin，tMax]是否与[0,1]相交（（tMin> 1 + origin [a]）||（tMax< origin [a]））{
 //沿这个维度没有交集; 
 //这些框不可能重叠。 
返回false; 
} 
} 
 
 //没有没有交点的维度。 
 //所以箱子重叠。 
返回true; 
 
 
 
 $ b public void moveTo（float centerx，float centery）
 {
 float cx，cy; 
 
 cx = center.x; 
 cy = center.y; 
 
 deltaVec.x = centerx  -  cx; 
 deltaVec.y = centery  -  cy; 
 
 
（int c = 0; c <4; ++ c）
 {
 corner [c] .x + = deltaVec.x; 
转角[c] .y + = deltaVec.y; 
} 
 
 boundingRect.left + = deltaVec.x; 
 boundingRect.top + = deltaVec.y; 
 boundingRect.right + = deltaVec.x; 
 boundingRect.bottom + = deltaVec.y; 
 
 
 this.center.x = centerx; 
 this.center.y = centery; 
 computeAxes（）; 
} 
 
 //如果两个方框的交点非空，则返回true。 
 public boolean overlapps（OBB2D other）
 {
 if（right（）< other.left（））
 {
 return false; 
 
 
 if（bottom（）< other.top（））
 {
 return false; （）（）> other.right（））
 {
 return false; 
} 
 
 if （$）
 
 
 if（top（）> other.bottom（））
 {
 return false; 
 
 
 
 if（other.getAngle（）== 0.0f&& getAngle（）== 0.0f）
 {
 return真正; 
} 
 
 return overlaps1Way（other）&& other.overlaps1Way（本）; 
} 
 
 public Vector2D getCenter（）
 {
 return center; 
} 
 
 public float getWidth（）
 {
 return extents.x * 2; 
} 
 
 public float getHeight（）
 {
 return extents.y * 2; 
} 
 
 public void setAngle（float angle）
 {
 set（center.x，center.y，getWidth（），getHeight（），angle）; 
} 
 
 public float getAngle（）
 {
 return angle; 
 
 
 public void setSize（float w，float h）
 {
 set（center.x，center.y，w，h，angle）; 
} 
 
 public float left（）
 {
 return boundingRect.left; 
} 
 
 public float right（）
 {
 return boundingRect.right; 
} 
 
 public float bottom（）
 {
 return boundingRect.bottom; 
} 
 
 public float top（）
 {
 return boundingRect.top; 
} 
 
 public RectF getBoundingRect（）
 {
 return boundingRect; 
 
 $ b $ public boolean overlapps（float left，float top，float right，float bottom）
 {
 if（right（） {
返回false; 
 
 
 if（bottom（）< top）
 {
 return false; 
} 
 
 if（left（）> right）
 {
 return false; 
 
 
 if（top（）> bottom）
 {
 return false; 
} 
 
返回true; 
 
 
 public static float distance（float ax，float ay，float bx，float by）
 {
 if（ax< bx）
返回bx  -  ay; 
 else 
 return ax  -  by; 
} 
 
 
 public Vector2D项目（float ax，float ay）
 {
 projVec.x = Float.MAX_VALUE; 
 projVec.y = Float.MIN_VALUE; 
 
 for（int i = 0; i< corner.length; ++ i）
 {
 float dot = Vector2D.dot（corner [i] .x，corner [I] .Y，AX，AY）; 
 
 projVec.x = JMath.min（dot，projVec.x）; 
 projVec.y = JMath.max（dot，projVec.y）; 
} 
 
 return projVec; 
} 
 
 public Vector2D getCorner（int c）
 {
 return corner [c]; 
} 
 
 public int getNumCorners（）
 {
 return corner.length; 
 
 
 $ b public boolean pointInside（float x，float y）
 {
 float newy =（float）（Math.sin（angle）* （y  -  center.y）+ Math.cos（angle）* 
（x  -  center.x））; 
 float newx =（float）（Math.cos（angle）*（x  -  center.x） -  Math.sin（angle）* 
（y  -  center.y））; 
 return（newy> center.y  - （getHeight（）/ 2））&& 
（newy< center.y +（getHeight（）/ 2））
&& （newx> center.x  - （getWidth（）/ 2））&& 
（newx< center.x +（getWidth（）/ 2））; 
 
 
 public boolean pointInside（Vector2D v）
 {
 return pointInside（v.x，v.y）; 
} 
 
 public ArrayList< Vector2D> getCollsionPoints（OBB2D b）
 {
 
 collisionPoints.clear（）; 
 for（int i = 0; i< corner.length; ++ i）
 {
 if（b.pointInside（corner [i]））
 {
 collisionPoints.add（corner [i]）; 
 
 
 
（int i = 0; i< b.corner.length; ++ i）
 {
 if（pointInside （b.corner [i]））
 {
 collisionPoints.add（b.corner [i]）; 
} 
} 
返回碰撞点; 
} 
}; 
  

有什么可能是错误的？当我为2个OBB获得CollisionPoints时，我知道它们是穿透性的，它不会返回任何分数。

谢谢

我也尝试过：

$ $ $ $ $

$ b $ x $ center.x）;
float yy =（y - center.y）;
float newx =（float）（xx * Math.cos（angle） - yy * Math.sin（angle））;
float newy =（float）（xx * Math.sin（angle）+ yy * Math.cos（angle））;
return（newy> center.y - （getHeight（）/ 2））&&
（newy< center.y +（getHeight（）/ 2））
&& （newx> center.x - （getWidth（）/ 2））&&
（newx< center.x +（getWidth（）/ 2））;
}

没有运气。

解决方案

我没有读完所有的类，但我假设 angle 是您需要的角度

我相信 sin（angle）*（y-center.y ）和 cos（角度）*（x-center.x）等于您的中心点与测试点之间的距离。因此， newy 总是等于该距离的两倍， newx 将始终等于0。

这是我更喜欢旋转另一点的点：获得两点之间的角度和距离，然后将旋转应用于角度，然后根据角度和距离计算新位置。在伪代码中：

  //获取一个点并旋转它`theta`角度
 //围绕给定中心逆时针旋转点
函数rotateAboutPoint（x，y，centerX，centerY，theta）{
 radius = sqrt（（centerX-x）** 2 +（centerY-y）** 2）// ** `是指数运算符
 currentAngle = atan2（y-centerY，x-centerX）//如果你可以得到它，比普通`atan`优先`atan2` 
 newAngle = currentAngle + theta 
 newX = centerX + radius * cos（newAngle）
 newY = centerY + radius * sin（newAngle）
 return（newX，newY）
} 
 
函数pointInside x，y）{
 //点必须顺时针旋转，所以我们提供一个负角
 newX，newY = rotateAboutPoint（x，y，center.x，center.y，--angle）
 return（
 newY> center.y  - （getHeight（）/ 2）&& 
 newY< center.y +（getHeight（）/ 2）&& 
 newX> center.x  - （getHeight（）/ 2）&& 
 newX&l吨; center.x +（getHeight（）/ 2）&& 
）
} 
  

I have an OBB2D class based on SAT.

This is my point in OBB method:

public boolean pointInside(float x, float y)
{
    float newy = (float) (Math.sin(angle) * (y - center.y) + Math.cos(angle) *
            (x - center.x));
    float newx = (float) (Math.cos(angle) * (x - center.x) - Math.sin(angle) * 
            (y - center.y));
    return (newy > center.y - (getHeight() / 2)) && 
            (newy < center.y + (getHeight() / 2)) 
            && (newx > center.x - (getWidth() / 2)) && 
            (newx < center.x + (getWidth() / 2));
}

public boolean pointInside(Vector2D v)
{
    return pointInside(v.x,v.y);
}

Here is the rest of the class; the parts that pertain:

public class OBB2D
{
   private Vector2D projVec = new Vector2D();
   private static Vector2D projAVec = new Vector2D();
   private static Vector2D projBVec = new Vector2D();
   private static Vector2D tempNormal = new Vector2D();
   private Vector2D deltaVec = new Vector2D();
   private ArrayList<Vector2D> collisionPoints = new ArrayList<Vector2D>();


// Corners of the box, where 0 is the lower left.
   private  Vector2D corner[] = new Vector2D[4];

   private Vector2D center = new Vector2D();
   private Vector2D extents = new Vector2D();

   private RectF boundingRect = new RectF();
   private float angle;

    //Two edges of the box extended away from corner[0]. 
   private  Vector2D axis[] = new Vector2D[2];

   private double origin[] = new double[2];

   public OBB2D(float centerx, float centery, float w, float h, float angle)
    {
       for(int i = 0; i < corner.length; ++i)
       {
           corner[i] = new Vector2D();
       }
       for(int i = 0; i < axis.length; ++i)
       {
           axis[i] = new Vector2D();
       }
       set(centerx,centery,w,h,angle);
    }

   public OBB2D(float left, float top, float width, float height)
  {
       for(int i = 0; i < corner.length; ++i)
       {
           corner[i] = new Vector2D();
       }
       for(int i = 0; i < axis.length; ++i)
       {
           axis[i] = new Vector2D();
       }
       set(left + (width / 2), top + (height / 2),width,height,0.0f);
   }

   public void set(float centerx,float centery,float w, float h,float angle)
   {
       float vxx = (float)Math.cos(angle);
       float vxy = (float)Math.sin(angle);
       float vyx = (float)-Math.sin(angle);
       float vyy = (float)Math.cos(angle);

           vxx *= w / 2;
           vxy *= (w / 2);
           vyx *= (h / 2);
           vyy *= (h / 2);

           corner[0].x = centerx - vxx - vyx;
           corner[0].y = centery - vxy - vyy;
           corner[1].x = centerx + vxx - vyx;
           corner[1].y = centery + vxy - vyy;
           corner[2].x = centerx + vxx + vyx;
           corner[2].y = centery + vxy + vyy;
           corner[3].x = centerx - vxx + vyx;
           corner[3].y = centery - vxy + vyy;

           this.center.x = centerx;
           this.center.y = centery;
           this.angle = angle;
           computeAxes();
           extents.x = w / 2;
           extents.y = h / 2;

           computeBoundingRect();
   }


   //Updates the axes after the corners move.  Assumes the
   //corners actually form a rectangle.
   private void computeAxes()
   {
       axis[0].x = corner[1].x - corner[0].x;
       axis[0].y = corner[1].y - corner[0].y;
       axis[1].x = corner[3].x - corner[0].x;
       axis[1].y = corner[3].y - corner[0].y;


       // Make the length of each axis 1/edge length so we know any
       // dot product must be less than 1 to fall within the edge.

       for (int a = 0; a < axis.length; ++a) 
       {
        float l = axis[a].length();
        float ll = l * l;
        axis[a].x = axis[a].x / ll;
        axis[a].y = axis[a].y / ll;
           origin[a] = corner[0].dot(axis[a]);
       }
   }



   public void computeBoundingRect()
   {
       boundingRect.left = JMath.min(JMath.min(corner[0].x, corner[3].x), JMath.min(corner[1].x, corner[2].x));
       boundingRect.top = JMath.min(JMath.min(corner[0].y, corner[1].y),JMath.min(corner[2].y, corner[3].y));
       boundingRect.right = JMath.max(JMath.max(corner[1].x, corner[2].x), JMath.max(corner[0].x, corner[3].x));
       boundingRect.bottom = JMath.max(JMath.max(corner[2].y, corner[3].y),JMath.max(corner[0].y, corner[1].y)); 
   }

   public void set(RectF rect)
   {
       set(rect.centerX(),rect.centerY(),rect.width(),rect.height(),0.0f);
   }

    // Returns true if other overlaps one dimension of this.
    private boolean overlaps1Way(OBB2D other)
    {
        for (int a = 0; a < axis.length; ++a) {

            double t = other.corner[0].dot(axis[a]);

            // Find the extent of box 2 on axis a
            double tMin = t;
            double tMax = t;

            for (int c = 1; c < corner.length; ++c) {
                t = other.corner[c].dot(axis[a]);

                if (t < tMin) {
                    tMin = t;
                } else if (t > tMax) {
                    tMax = t;
                }
            }

            // We have to subtract off the origin

            // See if [tMin, tMax] intersects [0, 1]
            if ((tMin > 1 + origin[a]) || (tMax < origin[a])) {
                // There was no intersection along this dimension;
                // the boxes cannot possibly overlap.
                return false;
            }
        }

        // There was no dimension along which there is no intersection.
        // Therefore the boxes overlap.
        return true;
    }



    public void moveTo(float centerx, float centery) 
    {
        float cx,cy;

        cx = center.x;
        cy = center.y;

        deltaVec.x = centerx - cx;
        deltaVec.y  = centery - cy;


        for (int c = 0; c < 4; ++c)
        {
            corner[c].x += deltaVec.x;
            corner[c].y += deltaVec.y;
        }

        boundingRect.left += deltaVec.x;
        boundingRect.top += deltaVec.y;
        boundingRect.right += deltaVec.x;
        boundingRect.bottom += deltaVec.y;


        this.center.x = centerx;
        this.center.y = centery;
        computeAxes();
    }

    // Returns true if the intersection of the boxes is non-empty.
    public boolean overlaps(OBB2D other)
    {
        if(right() < other.left())
        {
            return false;
        }

        if(bottom() < other.top())
        {
            return false;
        }

        if(left() > other.right())
        {
            return false;
        }

        if(top() > other.bottom())
        {
            return false;
        }


        if(other.getAngle() == 0.0f && getAngle() == 0.0f)
        {
            return true;
        }

        return overlaps1Way(other) && other.overlaps1Way(this);
    }

    public Vector2D getCenter()
    {
        return center;
    }

    public float getWidth()
    {
        return extents.x * 2;
    }

    public float getHeight() 
    {
        return extents.y * 2;
    }

    public void setAngle(float angle)
    {
        set(center.x,center.y,getWidth(),getHeight(),angle);
    }

    public float getAngle()
    {
        return angle;
    }

    public void setSize(float w,float h)
    {
        set(center.x,center.y,w,h,angle);
    }

    public float left()
    {
        return boundingRect.left;
    }

    public float right()
    {
        return boundingRect.right;
    }

    public float bottom()
    {
        return boundingRect.bottom;
    }

    public float top()
    {
        return boundingRect.top;
    }

    public RectF getBoundingRect()
    {
        return boundingRect;
    }

    public boolean overlaps(float left, float top, float right, float bottom)
    {
        if(right() < left)
        {
            return false;
        }

        if(bottom() < top)
        {
            return false;
        }

        if(left() > right)
        {
            return false;
        }

        if(top() > bottom)
        {
            return false;
        }

        return true;
    }

    public static float distance(float ax, float ay,float bx, float by)
    {
      if (ax < bx)
        return bx - ay;
      else
        return ax - by;
    }


    public Vector2D project(float ax, float ay)
    {
        projVec.x = Float.MAX_VALUE;
        projVec.y = Float.MIN_VALUE;

      for (int i = 0; i < corner.length; ++i)
      {
        float dot = Vector2D.dot(corner[i].x,corner[i].y,ax,ay);

        projVec.x = JMath.min(dot, projVec.x);
        projVec.y = JMath.max(dot, projVec.y);
      }

      return projVec;
    }

    public Vector2D getCorner(int c)
    {
        return corner[c];
    }

    public int getNumCorners()
    {
        return corner.length;
    }


    public boolean pointInside(float x, float y)
    {
        float newy = (float) (Math.sin(angle) * (y - center.y) + Math.cos(angle) *
                (x - center.x));
        float newx = (float) (Math.cos(angle) * (x - center.x) - Math.sin(angle) * 
                (y - center.y));
        return (newy > center.y - (getHeight() / 2)) && 
                (newy < center.y + (getHeight() / 2)) 
                && (newx > center.x - (getWidth() / 2)) && 
                (newx < center.x + (getWidth() / 2));
    }

    public boolean pointInside(Vector2D v)
    {
        return pointInside(v.x,v.y);
    }

    public ArrayList<Vector2D> getCollsionPoints(OBB2D b)
    {

        collisionPoints.clear();
        for(int i = 0; i < corner.length; ++i)
        {
            if(b.pointInside(corner[i]))
            {
                collisionPoints.add(corner[i]);
            }
        }

        for(int i = 0; i < b.corner.length; ++i)
        {
            if(pointInside(b.corner[i]))
            {
                collisionPoints.add(b.corner[i]);
            }
        }
        return collisionPoints;
    }
};

What could be wrong? When I getCollisionPoints for 2 OBBs I know are penetrating, it returns no points.

Thanks

I also tried:

public boolean pointInside(float x, float y)
{
    float xx = (x - center.x);
    float yy =  (y - center.y);
    float newx = (float) (xx * Math.cos(angle) - yy * Math.sin(angle));
    float newy = (float) (xx * Math.sin(angle) + yy * Math.cos(angle));
    return (newy > center.y - (getHeight() / 2)) && 
            (newy < center.y + (getHeight() / 2)) 
            && (newx > center.x - (getWidth() / 2)) && 
            (newx < center.x + (getWidth() / 2));
}

With no luck.

解决方案

I didn't read all of your class, but I'm assuming angle is the angle by which you would need to rotate your rectangle clockwise in order to make it axis-aligned.

I believe that both sin(angle) * (y-center.y) and cos(angle) * (x-center.x) are equal to the distance between your center point and the point you're testing. So newy will always equal twice that distance, and newx will always equal 0.

This is how I prefer to rotate a point about another point: get the angle and distance between the two points, then apply the rotation to the angle, then calculate the new position from the angle and distance. In pseudocode:

//takes a point and rotates it `theta` angles 
//counterclockwise around the given center point
function rotateAboutPoint(x,y, centerX, centerY, theta){
    radius = sqrt((centerX-x)**2 + (centerY-y)**2)  //`**` is the exponentiation operator
    currentAngle = atan2(y-centerY, x-centerX)      //prefer `atan2` over ordinary `atan` if you can get it
    newAngle = currentAngle + theta
    newX = centerX + radius*cos(newAngle)
    newY = centerY + radius*sin(newAngle)
    return (newX, newY)
}

function pointInside(x,y){
    //point must be rotated clockwise, so we provide a negative angle
    newX, newY = rotateAboutPoint(x,y,center.x, center.y, -angle) 
    return (
        newY  > center.y - (getHeight() / 2) &&
        newY  < center.y + (getHeight() / 2) &&
        newX  > center.x - (getHeight() / 2) &&
        newX  < center.x + (getHeight() / 2) &&
    )
}

这篇关于指向定向包围盒内？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！