Hi there! I'm writing a program (in c#) that counts a system of equations: (x-x1)^2 + (y-y1)^2 + (z-z1)^2 = r1^2 (x-x2)^2 + (y-y2)^2 + (z-z2)^2 = r2^2 . . . (x-xn)^2 + (y-yn)^2 + (z-zn)^2 = rn^2, where xn, yn, zn, rn are known In my case n will be range <2; 6> So, there are few spheres and I have to find the shared points (and show it - I'll use DirectX). And because of that I'm looking for a kind of a smart algorithm to that counts it. Can anybody help ? Thx

Um. I think you are confusing yourself about the complexity of the problem. If you want to actually solve that system of equations I imagine you will need a computer algebra system. This would NOT just be a smart algorithm. On the other hand, can't you just code special cases for finding the intersections?
I mean, intersection of two spheres is a circle. Intersection of a circle and a sphere has 1/2 intersection points, etc...

If you just want to show the result you can draw the first sphere with a pixel shader that discards the fragment if the other n-1 equations are not satisfied.
(This should work because the shared points have to be on every sphere specially on the first one, you ask the gpu to draw one of the the sphere and let it draw just the shared pixels!
But instead of writing something like (x-x1)^2 + (y-y1)^2 + (z-z1)^2 = r1^2 you should use something like this (x-x1)^2 + (y-y1)^2 + (z-z1)^2 - r1^2 < epsilon for a small epsilon because of the errors)

Quote:Original post by TheAdmiral
...
Onto a plain background, render each sphere, with partial opacity. The resulting render will be brightest in the projected area of intersection. A simple bright-pass filter could extract this.
...

This will not work because you loose depth information rendering the all the spheres this way.
Just think you have two spheres at the origin one with a radius of 1 and the other with a radius of 2 when you render them that way you will get the inner sphere as the intersection result but that is not correct because the the spheres do not share any points.

(Tell me if I'm wrong...)

It seems to me that there should exist a good algorithmic solution to this kind of problem. As DaBookshah mentioned the intersection (assuming it exists) of two sphere shells is going to be a circle, and the intersection of a third sphere shell will either be that same circle, two points, one point, or nothing. This is assuming a unique set of spheres, as obviously two spheres that are the same will intersect as a third sphere that is the same as both the original spheres.

So you first find two spheres that intersect, and find their intersection. If no such spheres exist, then you're done and there's nothing to visualize. If they do exist, you know the radius and location of both spheres as well as their distance between each other, thus it should be possible to calculate the radius, location, and orientation of the cross-section circle. Then you find a third sphere, different from the first two, that intersects the circle. If no such sphere exists, then again you're done and there's no intersection. Proceed like this until you find a sphere that doesn't intersect what you have left (no intersection), or you run out of spheres to check (the intersection is what you have left).

I might have missed something, but that's the type of process that pops into my mind.

Thanks a lot for you answers.
I've talked to my teacher and he said that the coordinates of the intersections were necessary.
Zipster - a method proposed by you is OK but I'm afraid that counting the coordinates may not be so easy. So, I'm still looking for a good way to solve that problem.
Actually I struggle with transparency of meshes in DirectX, but I will describe that problem in DirectX section.

good question.

i never fail to be amazed at what programs like solidworks do. i cant say i have the slightest idea of the algorithms they use to pull all that off.

I've solved that problem - maybe in the future it will help somebody.


From 3 equations we take 2( for example 1 and 2) and make some transformations as shown below

1.step
(x-x1)^2 + (y-y1)^2 + (z-z1)^2 = r1^2
(x-x2)^2 + (y-y2)^2 + (z-z2)^2 = r2^2

2. step

x^2 - 2xx1 + x1^2 + y^2 - 2yy1 + y1^2 + z^2 - 2zz1 +z1^2 = r1^2
x^2 - 2xx2 + x2^2 + y^2 - 2yy2 + y2^2 + z^2 - 2zz2 +z2^2 = r2^2

3. We subtract second from the first


-2xx1 +2xx2 + x1^2 - x2^2 - 2yy1 + 2yy2 +y1^2 - y2^2 -2zz1 - 2zz2 + z1^2 - z2^2 = r1^2 - r2^2
.
from that we have

-2[x(x1-x2) + y(y1-y2) + z(z1-z2)] = -x1^2 + x2^2 - y1^2 +y2^2 - z1^2 +z2^2 + r1^2 -r2^2
.
.
.
x(x1-x2) + y(y1-y2) + z(z1-z2) = (-x1^2 + x2^2 - y1^2 +y2^2 - z1^2 +z2^2 + r1^2 -r2^2)/ -2



(-x1^2 + x2^2 - y1^2 +y2^2 - z1^2 +z2^2 + r1^2 -r2^2)/-2 = this variables are known so we can call this as a

"k"

.
.
.
x(x1-x2) + y(y1-y2) + z(z1-z2) = k - this is equation of plane



4.step - we take equation 1 and 3 and do the same

After that we have equations of two planes.

From that we count equation of line (if it exists).

I won't show how to do it bacause it's not hard to do.

After that we recived the line:

(for example)
x= x0 +at
y = y0 +bt
z =t

(x0, y0, a, b are known)

Now we have to put this values into equation of sphere, after that we recive equation easy to count: at^2 + bt + c = 0,

t1 and t2 we put back to the straight line, and we have the points coordinates

and thats all :)
Hope that I didn't forget anything

Any questions ?