Ray Casting for Points _Behind The Camera_

Page 1 of 1

6 Replies - 218 Views - Last Post: 10 March 2015 - 10:03 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=371727&amp;s=b47ec101cf871dfcfd68a63de01df9c6&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 dogcat

Reputation: 0
• Posts: 3
• Joined: 08-March 15

Ray Casting for Points _Behind The Camera_

Posted 08 March 2015 - 12:07 PM

In a nutshell, I have a ray casting engine that uses rotation and some trigonometry, not matrices (vector math). I'd like to add something that draws a line from any two points, but when one of those points is beyond the viewing plane, it goes bat-attack crazy (skyrocketing in terrible directions).

Imagine shooting an arrow, but if one end of the arrow is outside the screen, it stretches the arrow obscenely, obviously not accurately representing the point anymore. This is a fake 3d world after all, such as wolfenstein. The calculation that's taking place for the verticle "z" axis is mearly scaling an arbitrary value.

I haven't found any information that addresses this, but after looking around I'm suspicious that using matrices might be the solution. I'd like to avoid having to learn that or adapt the engine I've already made, especially if that isn't the solution, or the only solution.

Here's some of the code I'm using:

```pLoc is the x,y of the camera.
mLoc is the x,y of the point.
pRot is the rotation of the camera.
pHgh is the height (z) of the camera.
mHgh is the height (z) of the point.
```

On the grid, x increases to the right, and y down.
The grid size of the world is 128 pixels, and that's also the max height for the camera.
The screen is 320 by 200 pixels.

```xxx = pLoc.x-mLoc.x
yyy = pLoc.y-mLoc.y

moo = atan(xxx,-yyy)*(180/pi)
if moo < 0 then moo = moo+360

tmp = pRot+120-moo

if moo < 180 and pRot > 90 then
tmp = tmp-360
else if moo > 180 and pRot > 270 then
tmp = tmp-360
end if

m = sqrt(power(pLoc.x-mLoc.x,2)+power(pLoc.y-mLoc.y,2))   -- distance to point
m = m*cos(pRot-moo)*(pi/180)   -- eliminates "fisheye" from distance

boo = (tmp*-320/60)-160   -- this is x spot on screen.
poo = (64-pHgh+mHgh)*(300/(m))   -- this is the y spot.
goo = 128/m*2   -- this is a converted distance for whatever.
```

Again, if the point goes off-screen, its position goes crazy: it's not being represented correctly. If the answer really is that this would work with vector math, that's fine, but if there's any chance to even fake it in this approach, I'd very much like to discover it.

Thanks. Hugs.

Is This A Good Question/Topic? 0

Replies To: Ray Casting for Points _Behind The Camera_

#2 BBeck

• Here to help.

Reputation: 630
• Posts: 1,463
• Joined: 24-April 12

Re: Ray Casting for Points _Behind The Camera_

Posted 09 March 2015 - 02:00 PM

Edit:

Quote

On the grid, x increases to the right, and y down.

I actually was thinking x increasing down and y increasing right in my code below and then I went back and reread what you said.

The code here is looking pretty 2D. Are you just trying to do a 2D top down game with a 3D look? I'm not seeing the third dimension in code here.

And use some descriptive variable names, please. You're killing me with this moo, boo, goo, and poo stuff. LOL

It's personal preference, but I use variable names like:ShipsStarboardEngineAccelerationMeasuredInMetersPerSecondEachSecond. Ok, actually that one is even a bit long for me but I really do use variable names like StarboardAccelInMetersPerSecSqr. Generally, I try to keep it under about 20 letters if I can.

Looks like you're using the 2D Pythagorean theorem to calculate the distance to the point. That might be thrown off if the point crosses the X,Y axis and goes negative. (Probably not now that I think about it a bit more.) I'm just kind of glancing over the code here. Normally I would look at this in the debugger and set variable watches to see the values changing and step through each line of code until I found the exact line of code where the problem is. So, I'm not very good at just eyeballing code and finding the bugs.

What language is this in?

So, assuming we're working in 2D here - and I wanted to draw a line between any two points even if they were off the screen, you need to know where the line intercepts the screen edges. It's easier if the starting point is always on screen and only the other point can go off screen. But you're basically dealing with the entire X,Y plane and asking what two points a line intersects a box that represents the screen size.

Maybe you're looking for the slope line intersection. y=mx+b

The place where the line goes off the left side of the screen should be a line where y=0 and the point where it goes off the top of the screen should be a line where x=0. The right and bottom should be the screen size. If you can get the slope of the line, you should be able to calculate the points where the line leaves the screen. You could check that the points are on the screen and avoid this check. Then when one goes off the screen you could calculate that point.

I might actually use vectors on this problem because I'm very comfortable with vectors and it would probably simplify the problem. Any two points on the 2D plane can be represented as vectors. By subtracting one vector from the other you get a vector that points from one to the other. It represent the direction between them and its length will be exactly the distance between them. You can check if they are on screen before doing this test and only doing it when one point goes off screen.

So, say point A is on screen and point B is off screen. The vector you will get by subtracting the two points represented as vectors will point from A to B and will have the exact length of their distance (and there's usually a function to get the vector's length for you so this is super simple for the programmer). Now, I already know point B is off screen because that's why we're doing this and we checked for this condition. So, I want to know what the last on screen position is along this line/vector that points from A to B. (I actually did this in my 3D Pong game code in 3D. But XNA has a built in function for determining the intersection point with a plane.) I need to know at what point the ray represented by my line on the two points intersects the screen edge. So, we're back to the slope line intersect equation y=mx+b. Once I know the intersection point, I can normalize the vector and set it's length to the exact length to the screen edge. If I add that vector to vector A, it will give me the exact screen coordinate position I need to substitute for B in order to keep B on screen.

But we keep coming back to the slope-line intercept formula. So may we should just do algebra here.

```float DetermineYIntercept(float PointAsX, float PointAsY, float PointBsX, float PointBsY)
{
float Slope;
float YIntercept;

Slope = (PointBsY - PointAsY)/(PointBsX - PointAsX);
//If Slope is zero the line is vertical, and therefore never intersects the X axis,
//all Y values on such a line will be equal including the Y intercept.
//The slope calculation will give a divide by zero error if the line is perfectly horizontal.
YIntercept = Slope * PointAsY - PointAsX;
//This will be the Y intercept for all lines. I did not include code to handle straight lines
//but all sloped lines will cross the Y axis somewhere (top of the screen I assume).

return YIntercept;
}

float DetermineBottomScreenIntercept(float PointAsX, float PointAsY, float PointBsX, float PointBsY, int ScreenHeight)
{
float Slope;
float YIntercept;
float BottomIntercept;  //Y value of X,Y point where the line crosses the bottom of the screen.
//The X value will always be screen height.

Slope = (PointBsY - PointAsY)/(PointBsX - PointAsX);
YIntercept = Slope * PointAsY - PointAsX;
BottomIntercept = Slope * (float) ScreenHeight - YIntercept;

return BottomIntercept;
}

```

Ok. The more I think about this the more I realize I'm over complicating it in an effort to make it easy. We should use the formula for two intersecting lines. I was thinking it would be more complicated because that assumes both lines are not axis aligned and our screen edges will always be axis aligned. But that won't hurt anything and I think it will be more simple treating the screen edges as lines.

This uses the same slope-line formula, but you now have two lines instead of one. The point where the two lines intersect is where both have x and y equal to one another. It's the only point on the two lines where there x and y match. You can use that to combine the two formulas to solve for that point.

I need to return a point here and so I'm going to use a vector to store the point rather than returning two values from one function. These aren't real vectors; they're basically just point structures holding an X and Y value as one structure.

```Vector2D PointA;
Vector2D PointB;
Vector2D PointWhereLineIntersectsScreenTop;
Vector2D PointWhereLineIntersectsScreenBottom;

PointWhereLineIntersectsScreenTop = PointWhereTwoLinesIntersect(PointA, PointB, Vector.Zero, new Vector2D(0, ScreenWidth);
PointWhereLineIntersectsScreenBottom = PointWhereTwoLinesIntersect(PointA, PointB, new Vector2D(ScreenHeight, 0), new Vector2D(ScreenHeight, ScreenWidth);
PointWhereLineIntersectsScreenLeft = PointWhereTwoLinesIntersect(PointA, PointB, Vector.Zero, new Vector2D(ScreenHeight, 0);
PointWhereLineIntersectsScreenRight = PointWhereTwoLinesIntersect(PointA, PointB, new Vector2D(0, ScreenWidth), new Vector2D(ScreenHeight, ScreenWidth);

Vector2D PointWhereTwoLinesIntersect(Vector2D LineOneA, Vector2D LineOneB, Vector2D LineTwoA, Vector2D LineTwoB)
{
float SlopeOfLineOne;
float SlopeOfLineTwo;
float LineOnesYIntercept;
float LineTwosYIntercept;
Vector2D IntersectionPoint;

SlopeOfLineOne = (LineOneB.y - LineOneA.y)/(LineOneB.x - LineOneA.x);
SlopeOfLineTwo = (LineTwoB.y - LineTwoA.y)/(LineTwoB.x - LineTwoA.x);
LineOnesYIntercept = DetermineYIntercept(LineOneA.x, LineOneA.y, LineOneB.x, LineOneB.y);  //Should have used vectors...
LineTwosYIntercept = DetermineYIntercept(LineTwoA.x, LineTwoA.y, LineTwoB.x, LineTwoB.y);  //Should have used vectors...

//y = ax + c
//y = bx + d
//Therefore ax + c = bx +d
//ax - bx = d - c
//x = (d - c) / (a - B)/>/>/>
//y = a * ((d - c) / (a - B)/>/>/>) + c

//x = (LineTwosYIntercept - LineOnesYIntercept) / (SlopeOfLineOne - SlopeOfLineTwo)
IntersectionPoint.x = (LineTwosYIntercept - LineOnesYIntercept) / (SlopeOfLineOne - SlopeOfLineTwo);
IntersectionPoint.y = SlopeOfLineOne * ((LineTwosYIntercept - LineOnesYIntercept) / (SlopeOfLineOne - SlopeOfLineTwo)) + LineOnesYIntercept;

return IntersectionPoint;
}

```

Ok. Here's where I'm really ready to break down and use vectors. The vectors in the example above are really points and not vectors, but I could sure use some vector math here to make the rest of this problem easier.

At this point, we can determine if the 2 points are off screen or not, and we can determine the points where the infinite line between the two points intersect the screen edges. But we still have the big problem of determining which of the two points is off screen or whether they are both off screen and then which point at the screen edge to substitute for which of our two points. I'm racking my brain trying to think of an easy way to do that and coming up with nothing but vectors (although this vector math is basically trigonometry and could probably be reduced to trig if you had to but you would just be doing vector math the hard way at that point).

Anyway, I could use vectors at this point to solve the problem. Let's say PointB is offscreen and PointA is onscreen. I can use vector subtraction to get a vector that points parallel with the line from PointA to PointB. Once I have the correct direction, I need the correct distance to the screen edge. Basically, I need a vector that will point in this same direction, but have a length of the distance between PointA and the Screen edge and not PointA to PointB. No problem. Normalize the vector then multiply it by the scalar number of the distance. You can use the 2D Pythagorean theorem to calculate the distance between two points and you now have the screen edge point although you need to figure out which of the 4 screen edges it's crossing. The easy way to do that is to use the vector you already have and determine which screen edge it points towards. But there are probably a couple ways to determine which screen edge it crosses that are similar.

You could probably rewrite the functions above to tell you which two screen edges the infinite line crosses and which two it does not. Then you just have to narrow it down to which direction it is from the two.

If both points are off screen it's even easier because you just use the screen intersection points.

Anyway, you could do something like that to determine where the line crosses the edge of the screen by making the edge of the screen a second line.

There is apparently a nifty way to solve this with 3D vectors, but the math is super ugly. If you want to look, google "Intersection of two lines in three-space". But I'm very comfortable with vectors and matrices and that math is a bit of a stretch for me. If I were doing this for me, I might actually go that route and just spend a weekend learning how to solve the problem with linear algebra using vectors, but you would still probably need a couple years experience with vectors before trying to understand it even if I were then to try and explain it. That is advanced vector math, most certainly not the place to start learning about vectors.

Does that help?

This post has been edited by BBeck: 09 March 2015 - 02:10 PM

#3 dogcat

Reputation: 0
• Posts: 3
• Joined: 08-March 15

Re: Ray Casting for Points _Behind The Camera_

Posted 09 March 2015 - 05:34 PM

@BBeck,

Thank you, that was wonderful. I'm getting a good picture of the problem and slapping my forehead. The game is fake 3D, and i've been looking at it that way for so long now, i totally forgot to trouble shoot in 2D. I've done a lot with an implied z axis; you can look up and down, crouch and jump; even the collision detection pays respect to z. Between the floor casting and sprites jumping around it certainly doesn't feel 2D, but sure enough it started with some top down tests that looked like a flashlight.

I'll have to read your post a few more times. Yes it helped a lot, thanks again. The more i look around the more errotic vector math is becoming. And i'm thinking it could amount to speed gain as well.

Actually i've always been paranoid about long varible names, thinking they could add even a fraction of a millisecond to processing or even a few k to the file. Is that totally paranoid? I've always been impressed how fast a computer can chug away though, and i know everything looks different in binary, but yeah, i must be paranoid. I have an easier time seeing things tightly though, like a simplified picture.

When you say normalize a vector i imagine it being set to 0. I definitely want to learn this stuff, and that settles it. Hugs you.

#4 BBeck

• Here to help.

Reputation: 630
• Posts: 1,463
• Joined: 24-April 12

Re: Ray Casting for Points _Behind The Camera_

Posted 09 March 2015 - 06:52 PM

Wow. I can't believe I just did that. I typed a whole long post and then clicked on a link before posting it and lost everything I typed. Ya godda love that.

Anyway, I've got a couple things here. First, I dug up some actual code that does something pretty similar. It's from my Pong prototype I did in 2D about a year ago. I needed to calculate the collision point with a wall so I could reflect the ball off it. So this is actual working code in C# for XNA.

```      Vector2 PositionAfterReflection;
Vector2 RequestedPosition;
Vector2 CollisionPosition;
Vector2 ReflectedVelocity;
Vector2 TangentPoint;
Vector2 TangentWithWall;
float FarWallXPlane;
float TopWallPlane;
float BottomWallPlane;
double AttackAngleOnWall;
float DistanceToCollisionPoint;
CollisionType ReflectionType;

ReflectionType = CollisionType.None;
FarWallXPlane = TheGame.DrawAreaWidth - CourtWallThickness - GameBall.Size/2;
TopWallPlane = CourtWallThickness + GameBall.Size/2;
BottomWallPlane = TheGame.DrawAreaHeight - CourtWallThickness - GameBall.Size/2;
RequestedPosition = GameBall.Position + GameBall.Velocity;
PositionAfterReflection.X = GameBall.Position.X;
PositionAfterReflection.Y = GameBall.Position.Y;

if (RequestedPosition.X >= FarWallXPlane) ReflectionType = CollisionType.Right;
if (RequestedPosition.Y >= BottomWallPlane) ReflectionType = CollisionType.Bottom;
if (RequestedPosition.Y <= TopWallPlane) ReflectionType = CollisionType.Top;

if (GameBall.Velocity.X < 0 && RequestedPosition.X <= PlayerOnePaddle.XPosition + GameBall.Size/2)
{
TangentPoint.Y = GameBall.Position.Y;

TangentWithWall = TangentPoint - GameBall.Position;
AttackAngleOnWall = AngleBetweenVectors(GameBall.Velocity, TangentWithWall);
DistanceToCollisionPoint = TangentWithWall.Length() / (float)Math.Cos(AttackAngleOnWall);
CollisionPosition = GameBall.Velocity;
CollisionPosition.Normalize();
CollisionPosition *= DistanceToCollisionPoint;
CollisionPosition += GameBall.Position;
{
ReflectedVelocity = RequestedPosition - CollisionPosition;
ReflectedVelocity.X *= -1;
GameBall.Velocity = new Vector2(GameBall.Velocity.X * -1, GameBall.Velocity.Y);
PositionAfterReflection = CollisionPosition + ReflectedVelocity;
GameBall.Velocity = RotateVector(GameBall.Velocity, (PercentageOfHitFromCenter * MathHelper.PiOver4)  );
GameBall.Velocity *= 1.09f; //109% faster ball.
}
else
{
if (RequestedPosition.X <= 0) ReflectionType = CollisionType.Left;
}
}

```

The key code being this:
```AttackAngleOnWall = AngleBetweenVectors(GameBall.Velocity, TangentWithWall);
DistanceToCollisionPoint = TangentWithWall.Length() / (float)Math.Cos(AttackAngleOnWall);

```

It might be helpful to see this code as well:
```        private float AngleBetweenVectors(Vector2 FirstVector, Vector2 SecondVector)
{
FirstVector.Normalize();
SecondVector.Normalize();

return (float)Math.Acos(Vector2.Dot(FirstVector, SecondVector));
}

private Vector2 RotateVector(Vector2 OriginalVector, double Angle)
{
Vector2 ReturnValue;

ReturnValue.X = OriginalVector.X * (float)Math.Cos(Angle) - OriginalVector.Y * (float)Math.Sin(Angle);
ReturnValue.Y = OriginalVector.X * (float)Math.Sin(Angle) + OriginalVector.Y * (float)Math.Cos(Angle);

return ReturnValue;
}

```

Notice the long variable names. I've never worried about it. I have a little experience with Assembly Language which is one of my favorites. When you compile C++ code down to object code all those variable names are lost. It's in the symbols file, but in the object code it's just numbers no matter what you typed for a variable name. It's just pointers to memory addresses which will be the same size if your variable name was 1 character or 1 million characters.

Some environments may be a bit different but I don't imagine it causing a problem. The primary problem with long variable names is that you may get sick and tired of typing a 40 character variable name. I have a high tolerance for this for a couple of reasons, not the least of which is that I do tutorials to try and help people understand this stuff and always want to help people understand what I'm intending.

It really does help when you come back to read your own code a year later though. This here was an actual example of my own code mostly intended for just my own eyes.

So, a normalized vector has it's length set to one. That allows you to reset it's length. If you multiply a normalized vector by a number it will take the length of that number. So, you can tell the vector how long to be.

Here's a wonderful opportunity for me to shamelessly plug my new YouTube Channel VirtuallyProgramming.com where I teach a lesson on matrices and another on vectors (probably do the vector video first since the matrix video builds on that somewhat).

The videos are very long, but I hope they are thorough and actually explain these topics to people who have basically no previous exposure to them. I never know if I'm doing a good job teaching or not, but I certainly try to introduce people to using vectors and matrices in game programming in those videos. The first 3 videos add up to about 2 hours. Edit:Excuse me about 4 hours. Wow that's a lot

I'm getting close to doing my 4th video which should introduce the topic of programming in DirectX 11. But the videos that are there currently are mostly math and not language specific.

I explain normalized vectors a little better there.

Understanding vectors in 3D is an absolute must as well as matrices. But understanding vectors in 2D is very helpful and opens up a lot more options. Once you "get" vectors it actually makes things easier in a lot of ways.

This post has been edited by BBeck: 09 March 2015 - 07:15 PM

#5 BBeck

• Here to help.

Reputation: 630
• Posts: 1,463
• Joined: 24-April 12

Re: Ray Casting for Points _Behind The Camera_

Posted 09 March 2015 - 08:49 PM

When you normalize a vector, that means you set it's length to one. If you zero a vector you destroy it. Thing of it as an arrow where the X and Y values are the position of the head and the tail is at 0,0. By zeroing the length all points are at 0,0. What is the length? What direction does it point in? The definition of a vector is a length tied to a direction. In the case of a zero'ed vector you've destroyed both the length and the direction. Thus, you've destroyed the vector. There is no vector at that point.

The purpose of a normalized vector is generally to represent an arrow that points in a specific direction. You're trying to represent a direction without an amount when you use a normal. You don't care about the amount of 1.

1 is a handy number to use for this because any number times 1 is the same number. If you multiply a normalized vector times a number the length of the vector will take on that amount. So, let's say I want to set a vector to a length of 7.16 without changing it's direction. I don't even need to know what length it was. I merely normalize it and then multiply by 7.16 and it now has a length of 7.16 while pointing in the same direction.

This combined with a rotation formula allows you to control the length and the direction of the vector/arrow.

When you hear about a vector "normal" it means that it has a length of one and thus the direction matters but the amount does not. If the length were zero it would be incapable of pointing in any direction.

#6 dogcat

Reputation: 0
• Posts: 3
• Joined: 08-March 15

Re: Ray Casting for Points _Behind The Camera_

Posted 10 March 2015 - 09:27 AM

Neat. That makes sense. All the code i've looked at with vectors makes a lot more sense already. I'll definitely check out your videos. I'm not much of a verbal thinker so for me to absorb information by reading is like finding the bathroom in pitch darkness at somebody elses house. Videos will help a lot. Tremendous thanks

#7 BBeck

• Here to help.

Reputation: 630
• Posts: 1,463
• Joined: 24-April 12

Re: Ray Casting for Points _Behind The Camera_

Posted 10 March 2015 - 10:03 AM

Yes, I have a lot of info on my website regarding Vectors and Matrices, but I haven't felt like a lot of people were interested in reading through my website. I thought a lot of people might find it more helpful if I presented the information as videos and so I decided to refocus everything on a YouTube channel. I know I've gone through a lot of Unity and Blender tutorials on YouTube myself and found them helpful.

I'm also refocusing everything to teach DX11 instead of XNA, which is what I was previously trying to teach. But now that MS has abandoned XNA, I've decided to refocus on DX which should be around for a long time. Although, with Unity, I'm not sure a lot of people want to go the DX route anymore. Still, I want to cater who those who do and maybe to do OpenGL one day.

The first 3 videos that are currently there are not really specific to any computer language and would apply to any programming especially 3D programming in any environment.

I always wonder if anyone is getting any value out of my videos. So, it's always good to get feedback from people. I spend a lot of time effort and money at it not really knowing if anyone is even getting anything out of it. So, it's much more rewarding for me if I know some people are getting something from it and thought it was worth their time.

I'm trying to wrap up commenting the computer code for my next videos. I'm almost done with commenting the code. The code itself is written and running. Then I hope to post the code to the website and shoot two chapters of video on it that I probably will break up into multiple videos per chapter. Chapter one will be core DX code that is required in every single DX program you will ever write. And chapter two will be how to draw objects in a scene and move the camera around in the scene. It's all focused on 3D.