Mathemagic: ray-tracing woes

ID:163982
 
Jul 24 2007, 12:32 am (Edited on Jul 24 2007, 2:02 pm)
What I'm trying to accomplish here is a ray-tracing system, specifically designed to compare the distances of objects it passes near to see if the ray is within a certain distance of the object. If the ray is within a certain distance of the object, a "hit" has occurred.

There are three points involved:

"location": the origin point of the ray being fired
"new_location": an arbitrary point along the ray being fired
"A.location": the point of an object that is near the ray


My intended solution is as follows:
1) Find the equation of the line. The y-intercept of the line is automatically zero, as the original location is taken to be the origin.

2) Find the equation of the perpendicular line that passes through the coordinate of the object near the ray. I know the coordinate of the object near the ray and I know the slope of the perpendicular line is equal to the negative-inverse of the original slope.

3) Find the point where the two lines intersect.

4) Compare the distance between the intersection point to the object's coordinates to see if the object's central point is within X units of the intersection point. If so, the object is "touched" by the ray. If not, the ray does not touch that object and the evaluation continues.


What I'm having trouble with is the third step. How could I write a formula that would allow me to find an x coordinate and a y coordinate of an intersection point, knowing only three points, and knowing that the first line goes between the first two points and the [second] line is perpendicular to the original line and passes through the third point?


[edit]Should say "second line", not "third line".


        //Find the slope of the line from starting location to ending location.
        var/slope   = (new_location.y - location.y) / (new_location.x - location.x)

        //Find the slope of the perpendicular line to that line
        var/perpend = (new_location.x - location.x) / (new_location.y - location.y) * -1

        //Find the line that passes through the object's coordinates on the
        // perpendicular slope, and find the intersection point between the
        // perpendicular line and the original line.
        //Intersection point is the x coordinate where both functions have equal
        // y coordinates.
                    
        //Let original line be y = mx + 0
        // where m = "slope" (as above)
                                
        //Let new line be y = mx + b
        // where m = "perpend" (as above)
        // and b = y intercept = y - mx = (Ay-locy) - (perpend)(Ax-locx)
                    
        //y = (slope)*x
        //y = (perpend)*x + (Ay-locy) - (perpend)(Ax-locx)

        //Solve as a system of equations?


This is what I worked out so far, but I'm pretty sure my math is fudged up something terrible. Math and I just don't get along sometimes.

(Incidentally, I already trap the conditions where y = 0 or x = 0 in my if-else chain, so don't worry about divide by zero errors.)
Jul 24 2007, 1:40 am
Well when I read this I had something come to mind.

Since all liniar lines can be written down in a formula were x and y are connected to eachother maybe you could use this to see see if something is on it's path.

Lets use a simple formula for a 45 degree line

y = x

Meening everytime x increases with 1, Y does so aswell.
This is very basic and is asuming you get all that stuff.

Now if we know the x or y value of the object a, we can input this into the formula.
Lets say a's x = 1 and a's y = 5

y = x meening if we input 5 as y, its x should be 5 to be in the path of the ray.
Since its not we can conclude this object's location isnt on the line.

To get a formula you can just stick to the rule, what effect has a increase of 1 x on the y and then make sure that a's x or y is relative to the forumla.

Was that any help, or did I just insult you by telling you all this basic stuff you already knew?

Fint
Jul 24 2007, 8:40 am (Edited on Jul 24 2007, 2:16 pm)
In response to Fint
Fint wrote:
Was that any help, or did I just insult you by telling you all this basic stuff you already knew?


Well, you didn't insult me, but yeah, I already knew it. ;-)

The idea of a ray-tracing system is to determine not if a specific point lies on the line, but to determine if a specific point is "close enough" to the line to be considered a hit.

For instance, if I'm firing a laser beam at a ship that is at coordinates (4,8) and the ship has a radius of 1, a beam that passes through coordinates (4,7.5) should hit that ship even though the ship's coordinates don't lie exactly on the line traced by the laser.

To do determine whether the ray is close enough, you have to measure distance from the point to the line. To do that, the most precise solution that I'm aware of is to find the perpendicular line that intersects the specific point, since the perpendicular line will always represent the shortest distance between the ray and the point.

I'm mostly asking for mathematical help on solving systems of equations. I tried looking it up on PurpleMath, but didn't see anything that really helped me. The way I see it, I need to solve the following for "x":

(slope)*x = (perpend)*x + (A.location.y - location.y) - (perpend)*(A.location.x - location.x)

That'll give me the x-coordinate of the intercept, and then I can just plug that x coordinate in:

y = (slope)*x

to find the y coordinate.


The problem is, if I isolate the x terms on one side of the equation:

(slope)*x - (perpend)*x = (A.location.y - location.y) - (perpend)*(A.location.x - location.x)

I'm not sure how to proceed from that point. I want to divide out the (slope) and (perpend) terms from the left side of the equation, but I know you can't just divide the coefficients if there's a subtraction operation (if the left side was "(slope)*(perpend)*x", there'd be no problem).
Jul 24 2007, 8:55 am
In response to Jtgibson
There's a chance this post might be of some help:
[link]

It uses circles, and worked well for me.

Jul 24 2007, 2:01 pm
In response to DarkCampainger
Yeah, the reason I wanted to avoid limiting it exclusively to circles is the possibility of having square or triangular bounding boxes (vehicles are going to be rectangular). Though it's still possible in some limited circumstances to miss, even though the line would have actually passed over a corner, in most cases the to-hit check will "catch" the corner of the object.

Precision is my biggest goal in this system: I want precision down to pixel level.


If I was just going to use it for a tile-based game, I'd've simply used Shadowdarke's excellent PixelProjectiles library instead!
Jul 24 2007, 2:05 pm
In response to Jtgibson
Jtgibson wrote:
Yeah, the reason I wanted to avoid limiting it exclusively to circles is the possibility of having square or triangular bounding boxes (vehicles are going to be rectangular). Though it's still possible in some limited circumstances to miss, even though the line would have actually passed over a corner, in most cases the to-hit check will "catch" the corner of the object.

Understandable. If you can't get an answer here, you might be able to find a general programming article on it and then convert it to DM


Precision is my biggest goal in this system: I want precision down to pixel level.


If I was just going to use it for a tile-based game, I'd've simply used Shadowdarke's excellent PixelProjectiles library instead!

It is pixel-based. In fact, I used it to create the shooting system in Pixel Soldier.

Good luck! I hope you figure it out :)
Jul 24 2007, 2:15 pm
In response to DarkCampainger
DarkCampainger wrote:
Understandable. If you can't get an answer here, you might be able to find a general programming article on it and then convert it to DM

I've been searching for ages for any ray-tracing article, but they're all about interacting with polygons in 3D space, usually for rendering purposes. So that's pretty unlikely. ;-)
Jul 24 2007, 2:16 pm (Edited on Jul 24 2007, 2:24 pm)
I tried three times to get this to appear as an edit in the original post, but my edits wouldn't take, so I have to post it as a reply.

[edit]

Epiphany?

1. (slope)*x = (perpend)*x + (A.location.y - location.y) - (perpend)*(A.location.x - location.x)

   (slope)*x   (perpend)*x   (A.location.y - location.y)   (perpend)*(A.location.x - location.x)
2. --------- = ----------- + --------------------------- + -------------------------------------
   (perpend)    (perpend)             (perpend)                           (perpend)

    (slope)               (A.location.y - location.y)
3. --------- * x =  x  +  ---------------------------  +  (A.location.x - location.x)
   (perpend)                       (perpend)

                                 (A.location.y - location.y)
4. (slope)*(-slope) * x =  x  +  ---------------------------  +  (A.location.x - location.x)
                                          (perpend)

5. -1 * (slope)*(slope) * x - x = (A.location.y - location.y) / (perpend) + (A.location.x - location.x)


...Nope, still stuck. Don't know what to do once I move the x term over.
Jul 24 2007, 2:49 pm (Edited on Jul 24 2007, 2:59 pm)
I just solved it as a generalization. If I still have all my mental faculties operating properly (I often don't after a long day of school and work), I do believe what you want is, where x=b/(m1-m2), just the point (x,m1*x)

Then, with that x,y pair, your distance is obviously sqrt((O.x-x)*(O.x-x)+(O.y-y)*(O.y-y))

so...
proc/getDist(m1, m2,b, testObj)
    var
        x = b/(m1-m2)
        y = m1*x
        xDist = testObj.x-x
        yDist = testObj.y-y
        rDist = sqrt(xDist*xDist + yDist*yDist)
    return rDist

Proof:

let m2 = -m1^(-1)

y1 = m1x
y2 = m2x + b

To solve simultaneously, y1 = y2

m1x = m2x + b
m1x - m2x = b
x(m1 - m2) = b
x = b/(m1 - m2)

Therefor, they cross where x = b/(m1 - m2)

The y-coordinate of that point is therefore, substituting back into y1, m1x = m1(b/(m1 - m2))

That's the point where the lines cross; then, of course, you just use our friend from the pythagoreans to find the distance from there to the object.
Jul 24 2007, 3:26 pm (Edited on Jul 24 2007, 3:50 pm)
The absolute best way to do this is with vectors. That way you won't get any problems with infinite slopes when your lines are parallel to an axis.

I don't know if there's a vector library available for DM; but it's not too hard to write it all out in terms of coordinates, anyway.

Say your origin point (this is your "location") is O (coordinates Ox, Oy)
Your point on the firing line ("new_location") is A (Ax, Ay)
Your point on the object ("A.location") is B (Bx, By)
And the point of closest approach is C (Cx, Cy).

The firing vector is F = A-O = (Ax - Ox, Ay - Oy) = (Fx, Fy)

Find the length of this vector, |F| = f = sqrt( Fx*Fx + Fy*Fy)
and normalize it by dividing by its length:

D = (Dx, Dy) = norm(F) = (Fx/f, Fy/f)

The distance along this line to the intersection point (C) is given by the dot-product of D and (B-O):

g = D.(B-O) = Dx*(By-Oy) + Dy*(Bx-Ox)

Now the intersection point is given by:

C = O + D*g
= (Ox + Dx*g , Oy + Dy*g)

And the closest distance between the line and the point on the object is h = |B-C|:

h = sqrt( (Bx-Cx)*(Bx-Cx) + (By-Cy)*(By-Cy) )

And that's the distance you are looking for.

So the total series of computations are:
Fx = Ax - Ox
Fy = Ay - Oy
f = sqrt( Fx*Fx + Fy*Fy )

Dx = Fx/f
Dy = Fy/f

g = Dx*(By-Oy) + Dy*(Bx-Ox)

Cx = Ox + Dx * g
Cy = Oy + Dy * g

h = sqrt( (Bx-Cx)*(Bx-Cx) + (By-Cy)*(By-Cy) )

And that's it. Of course you don't actually need to use all these variables, I've just written it all out for clarity.
Jul 24 2007, 4:54 pm (Edited on Jul 24 2007, 5:46 pm)
In response to Hobnob
Actually, I have a vector library!

http://developer.byond.com/hub/Jtgibson/jt_vectors


So thanks! I can put that to good use, then. I'm already using the vector library for the origin of the projectile, its current location, and where it will end up when ray-tracing, so this is good to know.

(I need to brush up on my vector math, it seems. I know how to compute dot product but aside from normals I didn't know I could apply it in this situation.)


[edit]
As I interpret your post:

var/vector/unit_vector = projectile.velocity.UnitVector()
var/dot_product = unit_vector.DotProduct(projectile.location.VectorTo(A.locati on))
var/vector/vector_to_point = unit_vector.ScaleToMagnitude(dot_product)
var/coordinate/closest = projectile.location.AddVector(vector_to_point)


[edit2]

Er, wait, duh. Normals are cross-products, not dot-products. =P
Jul 24 2007, 7:54 pm
In response to Jtgibson
I ported a basic raytracer over to DM. I can let you have a gander, if you'd like. I think you're going to have to write intersect procs for each type of bounding structure, like boxes and spheres. I had come across an article that explained how to go about determining the formula you'd need, but I don't have the link on hand. I'll stumble around and see if I can locate it.

~X
Jul 25 2007, 7:45 am
In response to Jtgibson
Yep, that should do it. Actually, if you just want the distance from the object to the closest point of approach (i.e. you've no need to calculate the actual position of point C), you can do it a different way using a cross product:

distance = |norm(A-O) x (B-O)|

or

distance = (projectile.velocity.UnitVector().CrossProduct( projectile.location.VectorTo(A.location) ) ).Magnitude()

This works because of the definition of the magnitude of a cross product:

|AxB| = |A||B| sin(θ)

so if |A| = 1 (i.e. its normalized), then |AxB| is just |B|sin(θ), or length of the BC side of the right-angled triangle OBC.

Also, nice library.
Jul 26 2007, 10:18 pm (Edited on Jul 26 2007, 10:23 pm)
In response to Hobnob
Hobnob wrote:
Yep, that should do it. Actually, if you just want the distance from the object to the closest point of approach (i.e. you've no need to calculate the actual position of point C), you can do it a different way using a cross product:

distance = |norm(A-O) x (B-O)|

or

distance = (projectile.velocity.UnitVector().CrossProduct( projectile.location.VectorTo(A.location) ) ).Magnitude()

Sadly, DM isn't quite that good at processing the "." operator. So if someone wanted to use that, they'd have to unravel that and create the variables.

(I could do it, so I'm not asking for you to do it. I'm just saying for future reference. ;-))


This works because of the definition of the magnitude of a cross product:

|AxB| = |A||B| sin(θ)

so if |A| = 1 (i.e. its normalized), then |AxB| is just |B|sin(θ), or length of the BC side of the right-angled triangle OBC.

Interesting stuff! However, I do want to know the exact coordinates of the point on the ray, since I want to know whether that point is inside the object's bounding box; the bounding box isn't always an ellipse in the case of some objects (like vehicles, whose bounding boxes are convex rectangular polygons -- treated as systems of inequalities).

It's not perfect -- it's possible to pass through a corner and not register as a hit -- but it's still quite precise. In soft code like DM it's probably better not to try to compute an exact point of impact on the collision box, since that'd be extremely intensive.



Also, nice library.

Thanks! Most people who look at it think "wow, that looks nice, but I have no idea what I'd use it for". ;-)