Like Tree4Likes

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

This is a discussion on Detecting an object is inside / intersecting a conic area with elliptical base. within the C++ Programming forums, part of the General Programming Boards category; Hi, Not sure if I am putting this in the right forum. But here goes. I am trying to make ...

  1. #1
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476

    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.
    Last edited by g4j31a5; 03-09-2012 at 12:26 AM.
    ERROR: Brain not found. Please insert a new brain!

    “Do nothing which is of no use.” - Miyamoto Musashi.

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,299
    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.
    g4j31a5 likes this.
    Right 98% of the time, and don't care about the other 3%.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,299
    Boy, I left a few typos in that last message. When I said "major access" I meant "major axis".
    Right 98% of the time, and don't care about the other 3%.

  4. #4
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476
    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.
    ERROR: Brain not found. Please insert a new brain!

    “Do nothing which is of no use.” - Miyamoto Musashi.

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,299
    In two dimensions, do you know what the transformation is to turn an ellipse into a circle?
    Right 98% of the time, and don't care about the other 3%.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by grumpy View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by MK27 View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476
    Quote Originally Posted by grumpy View Post
    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.
    ERROR: Brain not found. Please insert a new brain!

    “Do nothing which is of no use.” - Miyamoto Musashi.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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.
    g4j31a5 likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,299
    Quote Originally Posted by MK27 View Post
    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.
    MK27 likes this.
    Right 98% of the time, and don't care about the other 3%.

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by grumpy View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #12
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476
    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.
    ERROR: Brain not found. Please insert a new brain!

    “Do nothing which is of no use.” - Miyamoto Musashi.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by g4j31a5 View Post
    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.
    g4j31a5 likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476
    Quote Originally Posted by iMalc View Post
    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?
    ERROR: Brain not found. Please insert a new brain!

    “Do nothing which is of no use.” - Miyamoto Musashi.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Detecting path to shared object
    By dev.fb0 in forum Linux Programming
    Replies: 5
    Last Post: 04-07-2011, 04:48 PM
  2. delete object from inside object
    By Drogin in forum C++ Programming
    Replies: 10
    Last Post: 01-02-2009, 07:55 PM
  3. Replies: 2
    Last Post: 05-21-2008, 10:40 PM
  4. elliptical button
    By geek@02 in forum Windows Programming
    Replies: 0
    Last Post: 11-21-2006, 01:15 AM
  5. Replies: 3
    Last Post: 02-12-2002, 09:09 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21