Formulas faster than PolarProjections for lines

01-01-2006, 09:15 AM

Ok, I recently came to the conclusion that it is possible to draw geometrical shapes (such as lines and circles) simply by using formulas, and not use PolarProjection. PolarProjection not only that it is a function (yes yes, PolarProjectionX and PolarProjectionY if you want) but it also uses Cos and Sin functions. Calling those functions a lot of times can be a problem, and even calling them once, if creating too many lines can cause a problem.

So, as an alternative I chose to do some research and try to base everything on a non-function method. It is possible to determine a grade one function if you know two points which belong to its graphic. The graphic of a grade one function is a line, so if I have the two points between which I want to draw the line, I should be able to determine the function.

Code:

f(x)=ax+b => y=ax+b

So practically for each x value I can determine the y. Now we write the function for the two points:

Code:

f(x1)=a*x1+b and f(x2)=a*x2+b <=> y1=a*x1+b and y2=a*x2+b

Now we have a system, we substract from the first function the second one and we get:

Code:

y1-y2=a(x2-x1) <=> a=(y1-y2)/(x2-x1)

Now problem, we have to divide with x2-x1. But what happens if x2-x1=0? It means that x2=x1 and so, the two points are identic, meaning that we have no line.
Now let's replace in the first function a with the stuff above.

Code:

y1=(y1-y2)/(x1-x2)*x1+b <=>b=(x1*y2-x2*y1)(x1-x2)

However, after this I came to another conclusion:

x1=x2 it's a particular case. If we have y1!=y2 then normally, the whole stuff is absurd because practically you would have f(x1)=y1 and f(x1)=y2. But for a value from the domain, you can't get multiple values from the codomain. Conclusion? This is a particular case.

How to solve it? Simple: keep X unmoved and go with y from min(y1,y2) to max(y1,y2), hehe, simplified code to get the idea. That will solve the problem of the particular case . But really, I know in graphics it is possible, but in math...

So applying this in JASS is very simple. Here is the code:

JASS:

function line takes real x1, real y1, real x2, real y2 returns nothing
local real a = (y1-y2)/(x2-x1)
local real b = y1-a*x1
local integer x

if (x1==x2) then
     set x=y1
     loop
          exitwhen x>y2 
          call CreateUnit(Player(15), 'hfoo', x1, x, 0.00)
          set x = x+10.00
     endloop
else
     set x=x1
     loop
          exitwhen x>x2
          call CreateUnit(Player(15), 'hfoo', x, a*x+b, 0.00)
          set x = x+10.00
     endloop
endif

This is just a simple example, to prove that this is correct! I hope this helps and that it is something new!

~Daelin

01-01-2006, 12:54 PM	#2
iNfraNe	I think everyone who has math at school knows this. dy / dx is called the derivative. Therefore you get the slope of the line and yes you can "draw" a line between. Usefull for.. guys who dont have math I suppose.

01-01-2006, 01:14 PM	#3
Vexorian	well he also meant that it is faster to forget about PolarProjection and I agree, I actually did so a while ago, none of my spells uses that function, that function is the spawn of Satan

01-01-2006, 01:20 PM	#4
Daelin	Ooh then Vex, what do you do for circles? Because using PolarX and PolarY is quite the same. I have a formula there too (found it in some math book) but it does not create points equally distanced. Moreover, it uses an Sqrt, but on the other hand, I think an Sqrt is better than two Cos and two Sin. ~Daelin

01-01-2006, 01:33 PM	#5
iNfraNe	ax²+by²=c = a circle I think it was or was this already an ellipse? refresh my memory :)

01-01-2006, 01:34 PM	#6
Daelin	Actually for circle it's x²+y²-2ax-2by+a²+b²-r²=0. ~Daelin

01-01-2006, 01:35 PM	#7
Blade.dk	I myself use the contents of polarprojection without, locations and directly.

01-01-2006, 01:36 PM	#8
Vexorian	(x-h)^2 + (y-k)^2 = r^2 h,k the center, r the radious , it is what Daelin posted but configured to have sense

01-01-2006, 01:45 PM

Daelin

Well yes, but you have to get y anyway. After doing the grade 2 equation stuff I got something like this (btw a is the x coordinate of the central point and b the y coordinate)

delta=4b²-4(x²-2ax+a²+b²-r²)

I replaced the stuff from the paranthesis with k and I got something this:
delta=4b²-4k

So y=(2b+-2*Sqrt(k))/2 => y1=b-sqrt(k) and y2=b+sqrt(k)

But the problem comes when k is negative. The sqrt is rounded by the function to 0 and so, the whole stuff is messed up. I know you can't have SquareRoot from negative value, so what do you do in this case?

~Daelin

01-01-2006, 01:58 PM	#10
iNfraNe	In that case there are no "zeropoints", the circle doesnt exist (in real numbers that is).

01-02-2006, 07:35 AM

#11

Extrarius

If you want fast line and/or circle drawing, look up a guy named 'Bresenham'. He formulated very, very fast methods to draw both that don't use reals, square roots, trigonometry, or anything else really costly. Articles on his algorithms can be found by typing 'fast line drawing'(minus quotes) or 'fast circle drawing'(likewise without quotes) into google, or typing his name into wikipedia.

For another 'obvious way'(meaning not using bresenham's algorithm or something similar), the starting point should be the parametric formula for a line between two points:
Position = Delta * (End - Start) + Start
Since we're only interested in the segment between Start and End, we will only work with Delta between 0 and 1
Next, since we want evenly spaces coordinates between Start and End, Delta must be increase by a specific value which will depend on the value of (End - Start). Specifically, it must be based on the normalized value of these two variables:

JASS:

function Line takes real StartX, real StartY, real EndX, real EndY returns nothing
    local real Length = SquareRoot(Pow(EndX - StartX,2) + Pow(EndY - StartY,2))
    local real DeltaInc = 10.0 / Length
    local real Delta = 0.0
    local real DeltaX = EndX - StartX
    local real DeltaY = EndY - StartY
    call DisplayTextToPlayer(GetLocalPlayer(), 0.0, 0.0, R2S(DeltaInc))
    loop
        call DisplayTextToPlayer(GetLocalPlayer(), 0.0, 0.0, R2S(Delta))
        call CreateUnit(Player(15), 'hfoo', DeltaX * Delta + StartX, DeltaY * Delta + StartY, 0.00)
        call TriggerSleepAction(3.0)
        exitwhen Delta > 1.0
        set Delta = Delta + DeltaInc
    endloop
endfunction

Should probably change the 10.0 to something larger, though, since footmen have a default collision size of 31