Point inside a Cone Detection

I want to be able to determine whether a point is inside a cone.

I have three vectors (eyePosition), (eyeDirection) and (Test Point) which are all relative to the origin.

I want a cone of length l and the angle between the diagonal sides to be alpha (both of which can be modified). I know you can use the dot product to find this answer out but my implementation seems to be giving me quite weird results.

Math Theory

My idea is that two vectors A and B where A is the vector from eyePosition to Test Point and B is the axis of the cone pointing towards eyeDir*l.

That if acos(A.B / |A||B|) < 0.5 * alpha then the point can be in the cone.
And for a stricter definition if the dot product of A.B is <= length of the axis (l) then the point is definitely inside the cone.

Is that correct?

My C Code is as such

int insideLightCone(double x, double y, double z, double px, double py, double pz,
                    double ang, double height) {
   double dotP = dotProduct(x * height, y*height, z*height, px, py, pz);
   cDistance = (eyex - px) * (eyex - px) + (eyey - py) * (eyey - py) + (eyez - pz) * (eyez - pz);
   double magOfVecs = magnitude(x*height, y*height, z*height) * magnitude(px, py, pz);

   double theta = acos(dotP / magOfVecs);
   
   return ((theta <= 0.5 * ang) && (cDistance <= height));
}

I'm not sure any of this code or math is correct so I am asking for help.

Thanks
neutrinohunter
neutrinohunterAsked:
Who is Participating?
 
ozoCommented:
you might want
   double dotP = dotProduct(x , y, z, px, py, pz);
   double hDistance = magnitude(x, y, z);
   double pDistance = magnitude(px, py, pz);
   cDistance = dotP / hDistance;
   double theta = acos(dotP / (Distance * pDistance));
    return ((theta <= 0.5 * ang) && (cDistance <= height)) && cDistance > 0;
 

   
0
 
neutrinohunterAuthor Commented:
Mmm, so hDistance is the magnitude of my (lookat - eyevector) and pDistance is the magnitude of the test vector(px, py pz).

What is Distance?

Thanks
0
 
ozoCommented:
Sorry, that should have been
acos(dotP / (hDistance * pDistance));
0
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 
neutrinohunterAuthor Commented:
I am actually using this for a cone based lighting system and my output comes as such:
http://img265.imageshack.us/img265/4953/screenshot4gp6.jpg

The lit vertices correspond to the points that exist within the cone. But not all the vertices are lit within the cone which exists from the viewpoint.

Are you sure my math is correct?

Should all my vectors be normalised? Or none at all if any?

Thanks
jamie
0
 
ozoCommented:
I'm not sure where the cone is supposed to be in the picture
It shouldn't matter whether or not you normalise as long as you are consistent
is px, py, pz the point to be tested, and is the axis of the cone x , y, z with the apex of the cone at 0, 0, 0 ?
0
 
NovaDenizenCommented:
I can't really follow your example code.  Here is some code that will hopefully be clear to you.

vec is a structure with .x, .y, and .z members.
apex is the location of the apex of the cone, the pointy bit.
axis is a unit vector (normalized so that magnitude == 1) pointing from the apex to the center of the base disc.
halfcossq is (cos(alpha/2))^2.  If you precalculate this then you don't need to do trig for every single point tested.

p is the point we're testing to see if it's inside the cone.

boolean pointInCone(vec apex, vec axis, double height, double halfcossq,
                                   double p) {
    vec pdiff = vec(p.x - apex.x, p.y - apex.y, p.z - apex.z);
    double d= axis.x * pdiff.x + axis.y *pdiff.y + axis.z * pdiff.z;
    if (d < 0 || d > height) return false; // above the apex or below the base
    // we want to know if acos(d / magnitude(pdiff)) < alpha/2.
    // applying cos reverses the sign of the comparison.  No real improvement,
    // since it trades a cos for an acos.  However, it sets up other tradeoffs.
    // d/magnitude(pdiff) > cos(alpha/2)
    // this trades a multiply for a divide, a good deal
    // d > cos(alpha/2) * magnitude(pdiff)
    // this trades a multiply for a sqrt, another good deal
    // d^2 > cos(alpha/2)^2 * magnitude(pdiff)^2
    return (d*d > halfcossq * (pdiff.x*pdiff.x + pdiff.y*pdiff.y + pdiff.z*pdiff.z));
}
0
 
NovaDenizenCommented:
That should be "vec p" in the parameter list.
0
 
lbertaccoCommented:
My understanding is that you want to find if "test point" is at a distance not greater then "l" from "eye position" and within an angle of "alpha"/2 from the "eye position"-"eye direction" vector.
Given
e="eye position"
d="eye direction" (not necessarily normalized)
t="test point"
The first test is
(t-e) . (t-e)<=l^2  (note that "." is dot-product)
So your math is correct but your cdistance is, actually, the square of the distance (you might have to compare it with square of "height" - but I'm not sure what "height" is)

The second test is
(t-e) . d >= length(t-e) * cos(alpha/2)

You can divide this last test by length(t-e) and take the acos of both sides to get it in the same form you used (acos(A.B / |A||B|) < 0.5 * alpha ) which is correct. However I'd avoid using acos and prefer my form as, with my form, you can precompute cos (alpha/2) and use it for testing multiple points (with your form, you should computer the acos for each test point).





So your "acos(A.B / |A||B|) < 0.5 * alpha " is correct (just take the ac

0
 
lbertaccoCommented:
Oops, sorry for the last line (cut&paste garbage)
0
 
lbertaccoCommented:
And another error (in my post) is that if d is not normalized, the second test should be
(t-e) . d >= length(t-e) * length(d) * cos(alpha/2)
0
 
ozoCommented:
Do you want a cone of height h, or a sphere sector of radius h?
0
 
neutrinohunterAuthor Commented:
Sorry for the long reply, not had access to a computer for a few days

Ozo: The picture was supposed to demonstrate a circular or jagged shaped conical shape on an area of terrain.

If my code was working right, it should check whether points in my view (demonstrated by the blue crosshair) are in distance, then they should be illuminated, so it would look like a dark room and some one turns on a torch.

I was doing this with my code.

if (coneLighting && insideLightCone(vec[0], vec[1], vec[2], p1.x-eyex, p1.y-eyey, p1.z-eyez, ANG, coneLength))

Where vec was a normalised array of floats corresponding to a normalised lookat vector. p1 would be the test point, coneLength (or i described height as well) would be the length of the cone from the apex to the center of the base and ANG would be the angle between the two diagonal sides of a cone.

Somehow I think I incorrectly encoded what you said, i'll try again in a second.

Also I'm searching for a flashlight effect, if a sphere sector could produce a similar effect I would be welcome to listen to it.

NovaDenizen

I tried your method and got a similar effect to Ozo's so am trying to track down errors and see if my code is buggering something up somewhere. But yes, I agree your form although probably harder to see  is probably a lot more efficient than calling acos() for 10000 points.

Ibertacco

Yes, I basically just want to have a cone which is my eye position and determine whether a point at a distance d away is inside the cone. Obviously this cone can be translated or rotated about the y and x to show movement as if I look down on the floor or to the skys.

You speak of two tests, does this refer to the similar math I describe?

Thanks for all your input, ill have another look at what I have done and see if its a stupid mistake I've done somewhere.

Neutrinohunter
0
 
lbertaccoCommented:
I mentioned two tests because my understanding was that you wanted to verify if a point is inside an infinite cone of a given angle and within a given distance (which are 2 tests).
Actually I'm not sure why you want to test for the distance if what you are looking for is a "torch"/spotlight effect (maybe the idea is that the torch can't get too far? - in this case the distance check I proposed is more appropriate than the finite cone idea, but doesn't really change much).

Still, in your code,  next to last line (the "return" line), you should compare cdistance with square of height as in:
return ((theta <= 0.5 * ang) && (cDistance <= height*height));
0
 
neutrinohunterAuthor Commented:
Mmm, I think the math is definitely correct unfortunately im not getting the desired results with my program and am quite unsure why.

Anyhow, you have all helped and I will give out the well earned points.
0
 
ozoCommented:
How are you using the results of your test?
0
 
lbertaccoCommented:
Have you tried with the change I suggested? Beside fixing a math error it also seems to match the wrong results you get in the posted images. The posted image shows a "donut" of light around some mountains. The black area inside the donut can indeed be caused by not squaring height when you compare it with cdistance (in fact, as I'vee already pointed out, cdistance is not really the distance, but the square of the distance).

Try with this code (Note that I"m assuming that (x,y,z) is normalized as it seems from your code, correct?):
int insideLightCone(double x, double y, double z, double px, double py, double pz, double ang, double height) {
   double hsquared = height*height;
   double cosangle = cos(0.5*ang);  
   cDistance = (eyex - px) * (eyex - px) + (eyey - py) * (eyey - py) + (eyez - pz) * (eyez - pz);
   return(cDistance<=hsquared && dotProduct(x, y, z, eyex - px, eyey - py, eyez - pz)>=sqrt(cDistance)*cosangle);
}

As you can see, hsquared and cosangle don't change unless you change the cone size/angle, so you could avoid computing them for each poiint....

Also in your code, cDistance seems to be a global var? (otherwise it would be better to add a "double" in front of "cDistance ="). If you use cDistance in other parts of your code, be careful that it still is not really the distance but the square of it
0
 
neutrinohunterAuthor Commented:
Originally cDistance was going to be a method of determining a colour for a vertex based on the intensity of the light eminating from the apex of the cone. At the moment, it isn't being used but it was being used in a manner: glColor3f(1.0 / (1.0 + cDistance)) for the illumination of a vertex inside the cone.

Ozo: Basically I was doing

/* Ncenter# is the normalised look at vector
   P1 is the TestPoint
   eye# is the position of the observer
*/

if (insideLightCone(ncenterx, ncentery, ncenterz, p1.x - eyex, p1.y - eyey, p1.z - eyez))
   set colour of the test point to white i.e glColor3f(1.0,1.0,1.0);
else
   set colour to black i.e glColor3f(0.0,0.0,0.0);

Ibertacco: I just get a black screen. Though I'm wondering why you are doing:

eyex - px since px = testp.x - eyex so basically I am getting back testp.x, if this was supposed to be the parameter x rather than eyex then I get an effect which is better. But the shape is only very small and doesn't change on movement of my lookat vector, which it is programmed to do.

http://img519.imageshack.us/img519/231/coneeffectuh1.jpg
0
 
lbertaccoCommented:
Sorry, I believed px/py/pz was the test point.

So, now, my understanding is that:
x,y,z is the cone axis direction, normalized
px,py,pz is testpoint - eyeposition
ang, is the cone aperture angle
height is the light maximum distance

and the revised code is:

int insideLightCone(double x, double y, double z, double px, double py, double pz, double ang, double height) {
   double hsquared = height*height;
   double cosangle = cos(0.5*ang);  
   cDistance = px*px + py*py + pz*pz;
   return(cDistance<=hsquared && dotProduct(x, y, z,  px, py, pz)>=sqrt(cDistance)*cosangle);
}
0
 
neutrinohunterAuthor Commented:
Yes, that is correct, however unfortunately I get no cone shape with that code so I'm not sure whats effecting my results.

I'm not sure how familiar you are with OpenGL, but the idea was to set a colour of a point to fully illuminated if was inside the cone and it seems that no point I have falls within the cone, however that shouldn't be the case. My angle is at around 60 degrees and my coneLength is at around 30 (since my whole scene of size (100, 20,100) in the approriate dimensions.


0
 
neutrinohunterAuthor Commented:
Actually I think it now works, I was doing something stupid normalising the axis direction twice, once with a function that works, then with another with must have been modifying my results, I'd like to thank you all for your patience with me and for your suggestions.

Thanks
neutrinohunter
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.