Rank: ? (5)
Member #: 11576

Greetings!

Given two cones of infinite length in 3d space, with arbitrary origins, orientation vectors and opening angles, how can we find if the two cones intersect or not?

An answer in the form of a C, Lisp or Scheme function would be prefered, but a math based explanation is just as good.

Good luck

Rank: ? (856)
Member #: 2

This is the first official challenge at Free2Code!

The first person to solve this problem as stated above ( to Maloeran's satisfaction ) will recieve a USD$10 gift voucher at Amazon.com. A solution proving that there is no solution, would also receive the prize.

Since Maloeran asked about this problem on IRC a week or two ago, many people have thought about it, and we have all realised it is not a no-brainer.. So we decided it would definatly be worth using as a challenge.

Good luck everyone!

Rank: ? (4540)
Member #: 51

Just adding a little extra info. This is, I understand, a real-life problem encountered in game programming where it would allow adjustment to lighting if an object or area is lit up by two light sources. So, these cones are actually light cones.

People have searched for a solution through Google and found nothing. I would imagine that this problem was encountered quite a bit in theoretical physics where light cones abound. So, it should be a good challenge for the high IQ types... or the ones who know whom to ask for an answer.

Rank: ? (179)
Member #: 7065

A quick question: How important is accuraccy versus speed here? Is a "false positive" catastrophic if the conic sections come very close to intersecting? If it's hideously slow, but still solves the problem, does that matter?

Rank: ? (4540)
Member #: 51

It's really up to Maloeran to answer the question but, in case he doesn't notice it for a while, I'd advise you to assume that the "infinite" in the question means he wants the accurate answer, not a speedy short-cut. It's true that in a 3D game scenario, the "infinite" would not strictly apply but I guess a complete answer would cover all possibilities.

Rank: ? (883)
Member #: 3

e=mc² , lol

Rank: ? (4540)
Member #: 51

as yet unsolved ... we need Einstein V2.x , lol

Rank: ? (401)
Member #: 4497

Code:

Rank: ? (3049)
Member #: 265

oh...can we have something easier? i'm not really smart in physics... 8(

Rank: ? (179)
Member #: 7065

I'm working on a solution, however, I don't think that this equation is actually solvable, as such, it can only be approximated, hence my earlier question.

BTW, this isn't really physics, it's more like geometry

Gian

Rank: ? (883)
Member #: 3

I always hated math... and with programming; it seems to always resort to damn math. In one way or another. The most help was by Arizona putting this problem in an actual situation with programming. Best of luck whoever figures this out. I think i'll email my college algebra teacher and get the solution, -l-

Rank: ? (401)
Member #: 4497

I posted it on another forum and here is the Solution, but I do not know if that is what you wanted.

Rank: ? (90)
Member #: 1672

lol, You didn't come up with this Zackstorm :P

http://www.neowin.net/forum/index.php?showtopic=115967&st=0&#entry1372067

Rank: ? (179)
Member #: 7065

That's not a solution. That's simply an illustration of one such possible situation which the solution to this problem could solve.

Because of the seeming lack of interest in this challenge, may I suggest that people investigate BReps (google will tell you more). Unfortunately, I'm currently in the midst of exams, and therefore am unlikely to be able to field my own challenge, but I'll give my best try at detailing how I would craft a solution, and then people can tell me what they think and perhaps someone can try and implement it and gain themselves an Amazon voucher

Okay, here goes:

Use planar polygons to approximate the shape of the cone section. Of course, this requires the cones to be finite, but I'll address that later. For now, just make them as large as is humanly possible

From this, you can test for the intersection of polygons (a relatively trivial task - Google will tell you). Now, some cleverness may be required to make the infinite side of things work, but I will detail more about that when I get some more time.

Anyway, back to studying

Gian

Rank: ? (401)
Member #: 4497

 stu

Well duh, stu. Did you not even read my post? I said I got it from another forum and was wondering if it counted. 8(

I hate it when poeple lurk on forums that I am on and I do not even know who they are on that forum. I think that is the last post I make there...

Rank: ? (179)
Member #: 7065

It sounds as thought the people on that forum really didn't have a clue anyway, so it's probably no loss

You would think that the inclusion of "with arbitrary origins, orientation vectors and opening angles" would pretty much clear up the "We don't have enough information" objections. Oh well.

Gian

Rank: ? (179)
Member #: 7065

Okay, enough of that studying stuff, I thought I would detail the other method with which one could possibly check for conic sections intersecting:

First of all, you need to create a sphere inside one of the conic sections, at the very top (either one will do) with a radius matching that of the cone at that particular point. From there, you can perform a test for Cone-Sphere intersection (as detailed at Mathworld). By adding some sort of terminating condition (such as, the length of the cone goes beyond some given length or the like), you can simply move the sphere down the conic section, adjust its radius and re-test for cone-sphere intersection. This is far from ideal, obviously, but in terms of a programming implementation, it's probably perfectly adequate. One could also enter in intelligent conditions, such as checking that the conic sections are not facing in completely opposite directions etc, but this is optional. All that really needs to be added is an intelligent "end" condition, at which point you stop moving the sphere down the cone and decided that they aren't going to intersect any time soon

Gian

Rank: ? (4540)
Member #: 51

Good to see that Gian is exploring this problem intelligently. That Mathworld site is a wonderful resource. It's worth a visit just for fun.

Rank: ? (200)
Member #: 9404

3D graphics is still something I'm learning - I'm still with wireframes right now. Anyway, here's what I've come up with:

From the terms Maloeran used in his post I'm assuming that a cone is represented by an orientation vector which is it's axis, a support point which is the tip of the cone and an angle which the sides of the cone makes to its axis.


The two cones intersect if:

The support point of atleast one of the cones lies within the other,
OR
The 'shortest distance' between the two orientation vectors is toward the positive direction of both the orientation vectors AND The mid-point of the 'shortest distance line' between the orientation vectors lies within both cones.

If BOTH the above are not satisfied the cones will intersect only if the angle between the two orientation vectors is exceeded by the sum of the opening angles of the cones.

Hmm, hope I have not made too much of a fool of myself!

Rank: ? (4540)
Member #: 51

The above sounds curiously plausible but would need to be expressed mathematically or as a program function, so that Maloeran can test it. Or, you would need to "prove" it with finer arguments.