Sign in to follow this  
cvahoo

An algorithm that count system of equations

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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
Admiral

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

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Kambiz
This 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
Admiral

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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 ?

Share this post


Link to post
Share on other sites
Dunno about all that algebra, but if you REALLY want to solve an arbitrary number of equations, I would have gone with a grobner basis implementation(yes, i've written one).

And i would have thought just coding in the fact that intersection of two spheres = circle, intersectino of two circles = 1/2 points, etc, would have been easier.

But if it works, who cares.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this