Hi, I am wondering if there is a better way to my problem as the solution I found seems not optimal.

Looking at the picture, I need to know the 3d position of E and F.

Here's what I do know:

B is my camera position.

A and D are known and moving in world space, so I also know AB and AD.

I also know the radius of each spheres.

Here the solution I found:

I compute angle alpha knowing AB and AC.

Then I compute the angle BAD with the dot product of the two vector... This is the part I'm not sure as it is suppose to give me the cos of BAD I hope.

Then I compute CAE doing the difference between BAD and alpha.

Then knowing CAE I can compute the hypothenuse AE.

Repeat the operation for the second sphere and I finally get F.

Any better, clever way ?

Thanks to all you maths guys.

#include 
#include 

void GetCircleTangentPoints(
	float cx, 
	float cy, 
	float radius, 
	float px,
	float py,
	float & t0x,
	float & t0y,
	float & t1x,
	float & t1y) 
{
	if(radius <= 0.0f) return;
	float xy,ax,ay,x0,x1,v;

	// Use circle's center as 0,0 and scale to unit
	ax = (px - cx) / radius;
        ay = (py - cy) / radius;

	// Get squared distance from circle to point
	xy = pow(ax,2)+pow(ay,2);
  
	
	if(xy == 1.0f) { // Point on circle?
		t0x = t1x = px;
		t0y = t1y = py;
		return;
	} else if(xy <= 1.0f) { // Point in circle?
		t0x = t1x = cx;
		t0y = t1y = cy;
		return;
	}
	
	// Point outside of circle
	
	// Pythagoras FTW
	v = sqrt(xy - 1.0f) * ay;
	t0x = (ax - v) / xy;
	t1x = (ax + v) / xy;
	
	if(ay == 0.0f) { // In case point if on horizontal 0 of circle avoid /0
		v = sqrt(1.0f - pow(t0x,2)) * radius;
		t0y = cy + v;
		t1y = cy - v;
	} else {
		t0y = cy + (radius * ((1.0f - (t0x * ax)) / ay));
		t1y = cy + (radius * ((1.0f - (t1x * ax)) / ay));
	}
	
	// Scale & translate back
	t0x = cx + (radius * t0x);
	t1x = cx + (radius * t1x);
}

int main() {
	float t0x,t0y,t1x,t1y;

	GetCircleTangentPoints(1,1,1,-2,-2,t0x,t0y,t1x,t1y);
	std::cout << "result: " << t0x << " x " << t0y << " , " << t1x << " x " << t1y << std::endl;
	return 0;
}

Wouawh, looks promising, I'm not really getting the details on how you use Pythagoras to get the two points but I'll have to test that.

First need to implement it for 3d points.

Many thanks.

Ok, I like the way the tangent points are computed but I really don't like too much the use of 3d line intersection.

Isn't there another way to get point E and F from what I have ? I think it's the secante but I still need to find the angle CAE.

The easiest way I can think of is to use vector math to find BC (BA+AC=BC) and AD (AD = DB-BA) and get the intersection E from them. You can find the analogue to point C on the circle around D (call it G) to construct a line BG and F would be the intersection of BG and AD.

I wrote an article that details a method that simply uses the cross product to determine the intersection of 2 lines. The lines need to be in an implicit form (ax+by+c=0) and the resulting point is in homogeneous coordinates (x*w,y*w,w), but those transformations are very simple. This method also doesn't yield any infinities if the lines are parallel, and no trigonometric functions are used.

http://www.gamedev.net/page/resources/_/technical/math-and-physics/advanced-intersection-test-methods-r3536

I cannot have your line intersection method to work.

I'm getting really confused about all those 2d to 3d to homogeneous or 4d vectors or (ax+by+c=0) lines.

Apparently it's so simple that I couldn't find any clear explanation and I feel really stupid to ask but...

Could you explain how from 4 3d points I can have the 2 implicit lines to do the cross product with ? Cause all I'm getting at the moment is the expected recturn vector of the cross product which as no connection with an intersection point.

Many thx.

I think it should work without intersection tests.

You can get the solid angle from a sphere to camera by: solidAngle = asin (sphereRadius / distanceToCamera)

You also need the angle between both sphere centers in relation to camera: angleAtoD = acos((posE-cam).Unit().Dot((posD-cam).Unit()))),

then it should be possible to do this:

vector diff = posD - posA.

posE = posA + diff * solidAngleA / angleAtoD

posF = posD - diff * solidAngleD / angleAtoD

EDIT: Removed all those divides by 2 from pseudo code - that was wrong thinking.

EDIT2: Fixed another bug.

In case there are still bugs, here is how it is supposed to work:

All the rays from the camera are straight lines.

Also the line between the spheres is straight.

Thus their interesctions are linear related to the angles, and the angles are easy to calculate here.

Thank you JoeJ, your method seems to be very nice and clear. I didn't think of this way to calculate the angles. That is great, I'm going to test that soon.

@cadjunkie: I'm still interested to understand the relation to transform 3d points/vectors to the implicit form you need for the cross product.

Cheers

I cannot have your line intersection method to work.

I'm getting really confused about all those 2d to 3d to homogeneous or 4d vectors or (ax+by+c=0) lines.

Apparently it's so simple that I couldn't find any clear explanation and I feel really stupid to ask but...

Could you explain how from 4 3d points I can have the 2 implicit lines to do the cross product with ? Cause all I'm getting at the moment is the expected recturn vector of the cross product which as no connection with an intersection point.

Many thx.

Sorry, I missed the part that you wanted the 3D position. Using implicit lines is a 2D thing since a 3D line can't be represented as a single implicit equation. Homogeneous coordinates are a simple idea that make computational geometry much easier from a certain standpoint. If you've ever seen a 2D point (x,y) become a 3D point (x,y,1) or the graphics perspective divide (x,y,z,1) = (X/w,Y/w,Z/w,w), then that's using homogeneous coordinates. Barycentric coordinates are also a form of homogeneous coordinates as well if you've ever seen those. It's basically taking a problem into a higher-dimensional space and for some problems, it helps find better solutions. In the case of finding an intersection of implicit lines in 2D, it reduces that to a simple cross-product type operation.

I think you could find a simple solution given that all the points you want lie on the plane ABD. This reduces the 3D problem into a 2D-ish one. Since the plane is defined by the centers of the spheres, the circle resulting from the plane-sphere intersection will be the great circle.