|
Just to ensure that you know that testing for intersection with circles is reasonably inexpensive:
if floating point, normalise equation of line
ax + by + c = 0
so that a^2+b^2=1
then the test for intersection with circle centre (x0,y0) radius r0 is
abs(a*x0 + b*y0 + c) <= r0
If integers, then there are several ways, but
(a*x0 + b*y0 +c)^2 < (a^2+b^2)*r0^2
is reasonably cheap (4 multiplications and 2 additions) assuming that r0^2 and (a^2+b^2) is precomputed. You may have to be careful about overflows.
With modern GFLOP processors, you can test a lot of circles in real time. It all depends on how many circles you have and how they are organised.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Hi,
this is great, and mathematically correct.
When all coordinates use no more than 14 bits (that is 16000 pixels), then everything
can be calculated in 32-bit signed integer arithmetic without risking overflows.
Seems much better than the sorted-squares stuff...
|
|
|
|
|
Hmm… I'd have to agree that dividing MAP into regions would be horribly complex (I haven't even implemented the code yet), but then again, I'm restricted to floating-point math, so I can't take the integer math approach. I'm also quite skeptical about testing every circle. Maybe I should make it more scalable, and allow automatic selection of algorithms based on certain conditions.
In the end, we converge towards an optimal solution, but we never reach it.
ROFLOLMFAO
|
|
|
|
|
Hi,
some more thoughts:
1. Whatever was said about integers can be done in float as well.
2. how many circles are there ? thousands ? and how many times per second
do you need the hit testing ? a modern CPU executes 1 billion instr/sec !
3. in my experience, reflecting before implementing is good (it allows for
wise initial choices), but optimizing things that dont exist yet is not;
optimization must be based on observations and measurements.
Good luck !
|
|
|
|
|
I'll take every idea into consideration. It is a testing platform for a bigger project after all, and a better idea can't be ignored!
Thank you for all your input! 
ROFLOLMFAO
|
|
|
|
|
Thanks. I'm guessing this goes back to the "l × c"* approach — comparing every line with every circle. If that turns out to be faster, I'll implement that too (you gotta love interfaces and virtual methods!).
By the way, everything is done using the Double type. (It's the type that Windows Presentation Foundation works with.)
* Represents the number of comparisons that needs to be made based on the number of lines and circles. The number of lines never exceeds the number of circles, so a lower bound would be 0 tests for no activity, and Math.Pow(c, 2) for the upper bound (when everyone is firing their uzis at once).
ROFLOLMFAO
|
|
|
|
|
If a line intersects a circle then it also intersects a square centered at the same location and with a side length equal to the diameter of the circle. That fact could be use as the first stage in your hit detection.
Steve
|
|
|
|
|
I can't see how to test for intersection with a square that is cheaper than testing for intersection with a circle. The best methods I can come up with are actually harder to test with a square than a circle.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
I haven't seen the algorithms being used but I don't find it hard to imagine that an algorithm based on the Cohen-Sutherland line clipping algorithm, for example, could speed things up. Also lines of code need not mean slower code.
Steve
|
|
|
|
|
Thanks for the link Steve - now I see where you are coming from. Guess there is no right answer (particularly without knowing all the problem), for finite line segments algorithms like you propose may be the best (although the answer will depend on the level of hardware support available), for infinite line segments the simple testing earlier in the thread could be promising. This looks like a semi-infinite problem so maybe a combination will turn out to be the best.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
I've never done any gaming programming, so my idea may be way off, but...
I assume that the circles are objects that maintain data about themselves. Could you have the circle objects keep track of what ray would intersect them? That way all the calculations would be done at the time of movement, and at the time the gun is fired, all that needs to be done is to check each circle to see if the shot qualifies as a hit.
Roy.
|
|
|
|
|
Hum. Thats an interesting approach. It helps the animation effect for sure,
but to apply this in a WPF context ?
And what if there are other kinds of objects around ? Bullets hitting each other ?
Walls being hit ? (well, if this matters it needs a solution anyhow).
|
|
|
|
|
How can I use Runge Kutta algorithm to programme a fractal?
Noha.Y
|
|
|
|
|
long time ago I used Runga-Kutta for numerical integration.
I dont see the use/need for it in fractals...
|
|
|
|
|
The use of runge kutta method is for dynamical systems, and fractals are dynamical systems..
My question now is: how did you use Runga Kutta for numerical integration?
Noha.Y
|
|
|
|
|
I once wrote a simulator for electronic circuits (a precursor of Spice);
using Fortran, the high-level language at that time.
for "time analysis" one has to cope with the intgerating effect of capacitors
and inductors; this is where different integration techniques can be useful,
e.g. Runge-Kutta.
You can find more on RK through Google, for instance here[^]
|
|
|
|
|
Thank you very much 
It helped me!
But what if I want to write a program??
|
|
|
|
|
Hi Luc,
I used Spice in college. Are you an author?
Jeff
|
|
|
|
|
No I am not an author of Spice, I met some of its authors when visiting Berkeley
University tho. And I participated in the development of similar programs in
Belgium, and did one myself. At that time SPICE (SPICE 1 that is) missed several
features that we needed badly, mostly in frequency analysis(poles and zeroes,
impedance calculation, S-parameters ...).
|
|
|
|
|
RK is used for approximating solutions to differential equations, which don't really have anything to do with fractals.
Do you have any particular reason to try and program something using Runge-Kutta or fractals? If you explain what you want to do a bit better, I might be able to point you in the right direction.
|
|
|
|
|
OK.. Can you give your email to send for you the mission I have to do?
Mine is: noha.yassin@gmail.com
Thanks
Noha.Y
|
|
|
|
|
i wish to learn about timetabling problem. From the surface, it does look quite easy to understand. but i don't really understand how does algorithm such as GA/SA/ACO can solve the problem? I mean, how to apply those algorithm into the problem?
|
|
|
|
|
Have you figured it out yet? Or are you still working on it?
"Any sort of work in VB6 is bound to provide several WTF moments." - Christian Graus
|
|
|
|
|
Hello,
I'm trying to develop an application that handles 3D data and plots it using OpenGl.
Do you know of any good 3D Math library to use with c#?
For OpenGl I will try to use Tao Framework.
By the way, in case this is not the rigth forum, where should I post this?
Thanks in advance
Just a c# newbie 
-- modified at 19:05 Tuesday 26th June, 2007
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
