# An algorithm that count system of equations

This topic is 4269 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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...

##### Share on other sites
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)

##### Share on other sites
Edit: Fallacy disclaimer - most of the following is patently false [rolleyes].

While it is possible to compute the intersection, there are much easier ways to render it.

Kambiz's method may work out for you, but I propose another that's perhaps simpler yet:

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.
If you render the n spheres in white one-by-one with an alpha value of 1/2, the intersection will have a lightness of (1 - 1/2^n). Simpler still, you could render them additively with a blending factor of 1/n to give a maximum (intersection) lightness of 1.

If the spheres are hollow (with equalities as you have written) then I see no problem in this. If they are solid, however, the intersection will be a connected volume, which you would likely want to render with some kind of lighting, in which case your work is cut out for you.

Let us know if any of this is helpful, or if you truly need to operate on the geometry.

Regards

[Edited by - TheAdmiral on September 30, 2006 8:23:39 AM]

##### Share on other sites
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...)

##### Share on other sites
Quote:
 Original post by KambizThis will not work because you loose depth information rendering the all the spheres this way.

Good observation, Kambiz. I'll go back to the drawing board [rolleyes].

Regards

[Edited by - TheAdmiral on September 30, 2006 8:36:10 AM]

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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 ?

1. 1
Rutin
19
2. 2
3. 3
JoeJ
16
4. 4
5. 5

• 26
• 20
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631700
• Total Posts
3001781
×