Thread: Detecting an object is inside / intersecting a conic area with elliptical base.

Hi,

Not sure if I am putting this in the right forum. But here goes. I am trying to make a method to check whether or not an object is inside a conic area in 3D world. The catch is the major and minor angle of the cone's tip is different. So the base is not circular but elliptical. So far I have only managed to make a method that has the same major & minor angle (circular base). But what I really need is the one with elliptical base. This is my current method:

Code:

bool Sensor::checkInsideCone(const CTransform& sensorXform, const CTransform& objXform, float angle) const
{
    CPos3D sensorTrans = sensorXform.getTranslation();
    CPos3D objTrans = objXform.getTranslation();
    CVector3f sensorToObjectVec (objTrans - sensorTrans);
    if ( sensorToObjectVec.getLength() <= getRadius() )
    {
        CVector3f forwardVec;
        CMatrixf sensorRot;

        sensorRot = sensorXform.getRotationMatrix();

        forwardVec = sensorRot.getRow(1);
        forwardVec.normalize();
        sensorToObjectVec.normalize(); 
        
        //Get angle between sensor-object and forward vector;
        float objAngle = acosf(forwardVec * sensorToObjectVec); //arc cos of dot product
        
        return (objAngle <= angle);
    
    }   
    
    return false; 
}

I've got an empty declaration of a method like this:

Code:

bool Sensor::checkInsideCone(const CTransform& sensorXform, const CTransform& objXform, float angleHorizontal, float angleVertical) const

But for the body of that method, I'm blank. Can anybody help me please? Thanks in advance.

This isn't precisely a C++ question (you could have used any language to implement your approach). I'd suggest it is more an algorithmic question for which the "Tech Board" forum here is as good a place as any.

In any event ..... one approach to address your problem ....

If you stretch the smaller axis of the ellipse so it is the same length as the major access, you get a circle. That is done with a particular geometric transformation, that is fairly easy to work out. The result of applying that same transformation to your "conic area with an elliptical base" will result in a "conic area with a circular base" (aka cone). Apply the same transformation to every point you wish to check, and check if the transformed point is inside the cone.

Boy, I left a few typos in that last message. When I said "major access" I meant "major axis".

Thanks for the reply. Sorry that it took a while to reply because I was away for the week end.

Just as I thought, I put this in the wrong forum. Would any moderator kindly move this thread into the proper one? Thank you.

As for your answer, grumpy, I'm not exactly following. Can you elaborate more?

thanks again.

In two dimensions, do you know what the transformation is to turn an ellipse into a circle?

Originally Posted by grumpy

In two dimensions, do you know what the transformation is to turn an ellipse into a circle?

Won't that lead to a potential error? The point may be inside a circular cone expanded from the elliptical one, but not inside the original ellipse.

Originally Posted by MK27

Won't that lead to a potential error? The point may be inside a circular cone expanded from the elliptical one, but not inside the original ellipse.

No, you just don't understand the logic of it. The transformation ensures that the elipse becomes a circle.

Originally Posted by grumpy

In two dimensions, do you know what the transformation is to turn an ellipse into a circle?

You mean scaling one of its axii into the same length as the other?

Oh yeah, BTW, actually I'm not quite sure about the efficiency of the method that I put here. Because there are 2 sqrt calls in the 2 normalize methods and an acos call to get the angle. So any advice on that one will also be appreciated.

So do you understand Grumpy's advice?

You work out the rotation that would make the ellipse tallest and least wide, like an upright "0" shape. Then you apply a scale to the x-axis coordinates about the centre of the ellipse such that the width would equal the height, and the points on the permieter of the elipse would now form a circle.
That part should all reault in one matrix that you can apply to all the points to test, so the bulk of that work is only done once.

You can then scale the X and Y coordinates of the resulting rotated points, according to their Z coordinate. This transforms the conical volume you would have had to test against, into a cylinder. Check the Z coordinates to make sure your points are in the right range, placing them in the right part of the infinite doublecone, and you can then throw away the z-coordinate.
Now you are left with a simple 2D point in circle test. By checking the squared distance against the desired squared radius you even avoid the sqrt. If you do the scaling cleverly to begin with, your desired radius at this point can be always exactly 1.0.

Let us know how it goes.

Originally Posted by MK27

Won't that lead to a potential error? The point may be inside a circular cone expanded from the elliptical one, but not inside the original ellipse.

If you are stretching (or squashing) an ellipse so it becomes a circle, you are applying a transformation. If you want to check of a point (x,y) is in that circle, then you apply the SAME transformation to that point.

Then determine if the transformed point is within the transformed ellipse. If the transformed ellipse is a circle ....

Google for "coordinate system transformation" if you want more information.

Originally Posted by grumpy

If you are stretching (or squashing) an ellipse so it becomes a circle, you are applying a transformation. If you want to check of a point (x,y) is in that circle, then you apply the SAME transformation to that point.

Got it.

OIC. So I should have these matrices then:

M1 = the matrix to reposition the cone.
M2 = the matrix to scale the axis.
M3 = the matrix to transform the cone to cylinder.
Mtotal = M1 * M2 * M3

And then I apply the Mtotal to the point and check it against the points that will be checked. After that, I should check all off the points against the base circle based only on the x & y elements in 2D space (and disregard the z value). Am I right?

Ok, I can see the big picture, but I still have other questions:
1. I can imagine and calculate the M1 and M2, but what about M3? How do I transform a cone to a cylinder?
2. So does this mean that I have to recalculate the matrices on every tick based on the position and orientation of the cone? Assuming the cone is moving constantly.

Thanks.

Originally Posted by g4j31a5

OIC. So I should have these matrices then:

M1 = the matrix to reposition the cone.
M2 = the matrix to scale the axis.
M3 = the matrix to transform the cone to cylinder.
Mtotal = M1 * M2 * M3

And then I apply the Mtotal to the point and check it against the points that will be checked. After that, I should check all off the points against the base circle based only on the x & y elements in 2D space (and disregard the z value). Am I right?

Close. The transformation of cone to cylinder is a non-linear transform, so you can't do that via a transformation matrix. It's a separate division step afterwards.

2. So does this mean that I have to recalculate the matrices on every tick based on the position and orientation of the cone? Assuming the cone is moving constantly.

Yes you'd need to recalculate Mtotal from a new M1 and M2 if the cone moves or changes size/shape.

Originally Posted by iMalc

Close. The transformation of cone to cylinder is a non-linear transform, so you can't do that via a transformation matrix. It's a separate division step afterwards.
Yes you'd need to recalculate Mtotal from a new M1 and M2 if the cone moves or changes size/shape.

So, how do I transform from a cone to cylinder then?

As long as the cone is pointed along the z axis then you should just be able to divide the x and y values by their z. Where z < 1 it'll make the x & y values wider and where z > 1 (and z > -1) it'll make them narrower, result being that the cone becomes a cylinder, then you can throw away the z.
Of course it'll fail where z = 0, which is where the two doublecones meet at a point, so you have to check for that also.