Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Point inside a Cone Detection

Posted on 2007-07-20
20
Medium Priority
?
2,652 Views
Last Modified: 2008-01-09
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
0
Comment
Question by:neutrinohunter
  • 7
  • 6
  • 5
  • +1
20 Comments
 
LVL 85

Accepted Solution

by:
ozo earned 400 total points
ID: 19532283
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
 

Author Comment

by:neutrinohunter
ID: 19532508
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
 
LVL 85

Expert Comment

by:ozo
ID: 19532533
Sorry, that should have been
acos(dotP / (hDistance * pDistance));
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

by:neutrinohunter
ID: 19532621
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
 
LVL 85

Expert Comment

by:ozo
ID: 19532708
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
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 400 total points
ID: 19534940
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
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 19534962
That should be "vec p" in the parameter list.
0
 
LVL 11

Assisted Solution

by:lbertacco
lbertacco earned 400 total points
ID: 19537216
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
 
LVL 11

Expert Comment

by:lbertacco
ID: 19537218
Oops, sorry for the last line (cut&paste garbage)
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 19537223
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
 
LVL 85

Expert Comment

by:ozo
ID: 19537228
Do you want a cone of height h, or a sphere sector of radius h?
0
 

Author Comment

by:neutrinohunter
ID: 19542556
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
 
LVL 11

Expert Comment

by:lbertacco
ID: 19542650
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
 

Author Comment

by:neutrinohunter
ID: 19544591
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
 
LVL 85

Expert Comment

by:ozo
ID: 19544882
How are you using the results of your test?
0
 
LVL 11

Expert Comment

by:lbertacco
ID: 19545375
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
 

Author Comment

by:neutrinohunter
ID: 19547126
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
 
LVL 11

Expert Comment

by:lbertacco
ID: 19547866
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
 

Author Comment

by:neutrinohunter
ID: 19556559
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
 

Author Comment

by:neutrinohunter
ID: 19556629
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

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
This article covers the basics of data encryption, what it is, how it works, and why it's important. If you've ever wondered what goes on when you "encrypt" data, you can look here to build a good foundation for your personal learning.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses

580 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question