# GL Viewer "Up Vector" perpendicular to sphere surface

• 12-06-2005
psychopath
GL Viewer "Up Vector" perpendicular to sphere surface
I was wondering how to keep the camera's up vector perpendicular to the surface of a sphere (to simulate planetary gravity). As a subquestion, I was wondering how hard it would be to implement terrain collision if the sphere had a terrain-like (bumpy) surface.

Thanx,
-psychopath
• 12-06-2005
BobMcGee123
I've solved this problem by setting the up vector to the cross product between the newly rotated strafe and view vectors (strafe cross view).

Doing any sort of collision detection against terrain is very costly, and requires some sort of a partitioning system. I wouldn't advocate using a per polygon type system for terrain unless you have a very intelligent method of culling *most* of the un-needed polygon checks. subsequently a brush collision detection method would be more intuitive, but only useful for swept volume collision detection (no rotating boxes and checking them against brushes).

I can show you some code for each method described, but unless you're actually landing on the planet I'd just keep it to sphere collision detection.
• 12-06-2005
Shamino
I'm doing a space sim type game and I've decided to ignore most physics and collision detection, except for major things like space stations and planets, most of it just seems unessecary to me :d, Afraid I cannot help with your problem though, I have no real collision detection experience
• 12-07-2005
VirtualAce
The normal for any point on the sphere can be found by subtracting the point in question from the centroid of the sphere. Normalize this value and that is the normal. No need for 3 vertices or any triangles or surfaces since all points are equidistant from the center (ideally).

You can find the altittude at any point on a terrain by using bilinear interpolation. You find out how far into a given cell you are and interpolate using the four corner height values.
This is precise and if you combine it with the dot product to tell you which side the player is on, you can determine object to terrain collision very precisely.

Bob is right, however, concerning terrains. They are extremely dense due to the amount of vertices required. This easily overloads the hardware vertex limit. You need some type of algo to determine what is visible and what is not, and how to render parts of the terrain that are far away as opposed to close to the camera. No point in rendering ten thousand triangles in the distance if the same could be approximated with 20. The percentage of terrain that actually contributes to the overall detail is algorithmic in nature. That means that detail level can drastically fall off with increased Z (or decreased in GL) and you will still 'fool' the eye into thinking the terrain stretches for miles.

Google for terrain algorithms and terrain generation algorithms. You will get hits on quad trees, octrees, ROAM, etc, etc.
• 12-07-2005
BobMcGee123
I'm pretty sure he meant sphere as in sphereical coordinates, in which case you can't know the point on the sphere without performing some math.

Also, does the terrain/heightmap math still work when it's wrapped around a sphere? I had the impression that's what the op meant.
• 12-07-2005
VirtualAce
Wrapping a terrain around a sphere is a bad idea unless you are trying to simulate space to planet entry in which case that is necessary. However, not many have been successful at this and it requires a good algo. There is one algo on www.gamedev.net forums that actually generates planet texture on the fly and as you get close to the surface, it adds more and more detail. It uses pixel shaders to do this and I'm sure the scope of it is far beyond this thread.

His sphere should be created using x,y and z. If he knows this then the centroid is always 0,0,0 in local space. Subtract and normalize.

If you are using the normals for light calculations, don't bother. You will never get a vertex resolution dense enough to approximate the surface and it will look ugly. And you don't need normal information for collision detection on a grid - which is what a sphere mesh is. Find where in the 'flat' grid the object is and use bilinear interpolation to find the height. You must also know which triangle of the quad the object is in. Linear interpolate using both triangles. This stuff is all over the internet.

To create a sphere i believe it is this:

-90<alpha<90
0<beta<360

Check mathworld for more.

Code:

```Vector3 VectorFromCenter; VectorFromCenter=Vector3(px,py,pz); Normalize(&VectorFromCenter,&VectorFromCenter); Sphere.Normal=VectorFromCenter;```
• 12-07-2005
BobMcGee123
Quote:

There is one algo on www.gamedev.net forums that actually generates planet texture on the fly and as you get close to the surface, it adds more and more detail. It uses pixel shaders to do this and I'm sure the scope of it is far beyond this thread.

Quote:

Trust me on this one guys I've done it.
I have too, I've implemented looking/movement in every way possible.

Quote:

To create a sphere i believe it is this:

Yeah, this is what I was saying. You need to compute the point on the sphere by doing some sort of transformation (either what I put above, where if for whatever reason you have the view and strafe vector, then the XYZ of the up vector is strafe x view) or the transformation from sphereical to cartesian coordinates (also the same as doing the rotation matrix transformation that has two angles, pitch and yaw).

But yeah ultimately we're on the same page.
• 12-07-2005
VirtualAce
I liked the algo but I didn't like the fact that:

• It required pixel shaders. Therefore there was no way to "fall-back" to a software algo for systems that couldn't do the shaders.
• Generating on the fly is ok, but if you want persistent landscapes then the first generation would have to be saved somehow. Great for a demo, but maybe not so great for a game.
• Spending all the GPU cycles on simple texture generation doesn't leave room for much else.

My conclusion is that, as of yet, our computers are not yet ready for this. The data sets are just too large to do it right. There is another algo that actually uses a different technique and it looks promising but framerates are not applicable to also adding in objects, spaceships, stations, etc, etc.

The big problem comes from the fact that your sim must not only be able to do a flight sim type engine, it must also do a space-sim type engine. Space sims use techniques to cull the data that cannot be used in a flight sim.

Also let's say you do get it right. What is the advantage? We can't even simulate our own planet in enough detail to make it interesting enough - save for Flight Simulator 2004. So you would basically have to make datasets as large as FS2004 for every planet in your game to make it any fun. Not something I want to do. If you don't then you end up with the Battlecruiser Millenium or BC3000 paradigm. Yeah you can land on every planet, but there isn't anything to look at or do when you get there. Flying mindlessly over thousands of miles of terrain is not what I would deem an intense space sim.

This is why I chose the Freelancer type land, do your business, and leave type interface for planets. It provides a more centralized way of dealing with planetfall and yet still having something to actually do on the surface. Universal Combat, the most recent version of BC3000 and BCM, allows you to go planetside on every planet, but it's hardly any fun (for me at least) and the graphics suffer planetside. The information is just too vast to get it all right.

Look at our FPS shooters now. They have great graphics, but in very limited spaces. In other words the graphics are concentrated in 'levels'. Beating the level means loading a new world map and it's a world that you cannot leave. If you do, it's because they messed up somewhere. The only major free-form go anyhere, do anything game I've seen is FS2004 and it's purely a flight sim. The graphics could never be used for an FPS. A space sim wanting to do planetfall has to somehow merge two gaming genres successfully. The FPS and the flight sim.
Usually when this is done, one, or both sections of the game suffer.

So the easiest way to do this is to provide 'gates' to fly through to land on the planet. If you don't use a gate, you burn up. Collision can be found by using bounding spheres. Make the bounding sphere slightly larger than the planet. If the player is on the very fringes of the sphere, create some type of effect showing they are entering the atmosphere. Any farther and it's certain death. Many games have done this quite well - but Freelancer probably does it best.

The sphere is:
(x^2)+(y^2)=(r^2)

Looks somewhat like the distance formula because, well, it is.

float dist=sqrtf( ( (x2-x1)*(x2-x1) ) + ( (y2-y1)*(y2-y1) ) );

Parentheses added for clarification. If you don't want to use sqrtf then work in terms of the square of the distance. You know that if the result is 10, you are 100 units from the object. So when you are 100 units from the object, you know your actual distance is 10. No one ever said you have to take the square root.

Here is a thread concerning 3D spheres.
http://cboard.cprogramming.com/showt...358#post403358
• 12-07-2005
BobMcGee123
Quote:

It required pixel shaders. Therefore there was no way to "fall-back" to a software algo for systems that couldn't do the shaders.
I've seen many games that rely purely upon the GL 2.0 specification, to such an extent that just trying to use anything fixed-function OpenGL would crash the engine. i think it's interesting that you are now allowed to program the rendering pipeline but i've never really gotten the appeal of shaders...I think it's just partly the way my brain works, graphics doesn't turn me on as much as other people.

Quote:

Look at our FPS shooters now. They have great graphics, but in very limited spaces. In other words the graphics are concentrated in 'levels'. Beating the level means loading a new world map and it's a world that you cannot leave. If you do, it's because they messed up somewhere. The only major free-form go anyhere, do anything game I've seen is FS2004 and it's purely a flight sim. The graphics could never be used for an FPS. A space sim wanting to do planetfall has to somehow merge two gaming genres successfully. The FPS and the flight sim.
Usually when this is done, one, or both sections of the game suffer.
Yeah, and this is why games such as everquest, guildwars, and others of the same genre have hackish looking terrain/trees/buildings (still professional quality, but obviously not superb) but with expansive universes...they're very popular.

Coincidentally, I was recently thinking of writing just a simple gravitation screen saver...I had seen a version on gamedev.net where a bunch of point masses are spawned, and they are attracted to each other...when they collide, they spawn into a larger point mass and eventually suck up the smaller particles. I really enjoyed watching that and wanted to write my own version.

Quote:

So the easiest way to do this is to provide 'gates' to fly through to land on the planet. If you don't use a gate, you burn up. Collision can be found by using bounding spheres. Make the bounding sphere slightly larger than the planet. If the player is on the very fringes of the sphere, create some type of effect showing they are entering the atmosphere. Any farther and it's certain death. Many games have done this quite well - but Freelancer probably does it best.

I very much feel like writing something that has to do with a planet/spaceships right now. If I get some pending work done I might do just that. Incidentally, about two years ago I started writing a demo where you fly around in a spaceship, but the spaceship is very large, subsequently you can choose two different modes: inside the spaceship, which is actually just an indoor BSP level, or outside the spaceship, which was just an octree (and where you'd pilot the spacecraft). It really wouldn't be too hard for me to whip something like that up, but I've got work pending. If I make anything I'll post it.

As an aside, this is the code I use for determining if two spheres collide. I was going to write a version in FPU (I've been on an assembly crunch lately, as you probably noticed by my thread in GD, so I've been going back and forth between my high languages and asm). It's just a swept-sphere collision test, the parameters denote the starting and ending positions of the vectors, and returns a float between 0 and 1 denoting the interpolation between each sphere's start and end positions.
Code:

```double        TimeOfSphereIntersection(double        PosA1X,double        PosA1Y,double        PosA1Z,                                                           double        PosA2X,double        PosA2Y,double        PosA2Z,                                                           double        PosB1X,double        PosB1Y,double        PosB1Z,                                                           double        PosB2X,double        PosB2Y,double        PosB2Z,                                                           double        Radius1,double        Radius2,double        Epsilon) {         Vector3D        V1(PosA2X - PosA1X, PosA2Y - PosA1Y, PosA2Z - PosA1Z);         Vector3D        V2(PosB2X - PosB1X, PosB2Y - PosB1Y, PosB2Z - PosB1Z);                 //A is the difference in initial positions         Vector3D        A(PosA1X - PosB1X, PosA1Y - PosB1Y, PosA1Z - PosB1Z);         //B is the difference in velocities         Vector3D        B = V1 - V2;         double        sep_dist        =        Radius1 + Radius2 + Epsilon;         double        sep_dist_sq = sep_dist * sep_dist;         double        AdotB = DotProduct(&A,&B);         double        AdotB_sq = AdotB * AdotB;         double        Bsq          = B.BasicLength();        //length of b squared         double        Asq          = A.BasicLength(); #if        0         double        iBsq  = Bsq > .0000001 ? (1/Bsq) : 1;        //Inverse of b squared #else         double        iBsq  = 1 / Bsq; #endif                 double        closest_sep_dist_sq        =        Asq - (AdotB_sq * iBsq);         if(closest_sep_dist_sq > sep_dist_sq)        //spheres never collide         {                 COLLISION_DEBUG( trace << "Closest_sep_dist_sq > sep_dist_sq, spheres never collide" << "\n"; )                 return        -1;         }         double        under_root = AdotB_sq - (Bsq * (Asq - sep_dist_sq));                 if(under_root        <        0)         {                 COLLISION_DEBUG( trace << "Collision debug, under_root negative" << "\n"; )                 return        -2;                }         double        root = sqrt(under_root);         double        time(0);                         time = (-AdotB - root) * iBsq;         return        time; }```
I've tested it and afaik it's 100% effective. The epsilon is added if you want a bit of extra space paddding between the two spheres (so they aren't quite exactly tangential when updated to their collision positions, avoid floating point weirdness)
• 12-08-2005
VirtualAce
Looks cool. I like that your function returns a time. It is more precise to find out when the collision will happen or 'if' it will happen rather than find out geometrically when it occurs. Many physics engines are based on time intervals. If the interval is empty, the collision definitely will not happen. If it's not empty, then it 'could' happen and you might need to do some collision detection to see if it has or will.

Physics code is actually easy. The collision detection stuff well....isn't...at least not for me.
Lots of things to test for.

I totally lost all of my space-sim but I remember how I did it. I won't pursue it again until I find a better sphere-mapping algo for textures. None of the one's I found worked well and the BumpEarth sample that MS created is a mess, but it does texture correctly.

But I'd be interested. Right now I'm working on a 2D tile editor and engine for a Zelda fan game. I'm just the core engine programmer and tools programmer so when that is done, they can do the rest. The only thing I asked them is that they do not use actual Zelda Nintendo graphics and create their own. They agreed and thus far everything is ok. But Nintendo did give us permission to use Zelda and all sprites as long as we do not sell it, we do not claim any affiliation with Nintendo, and we give credit for the artwork somewhere in the credits section. But they didn't mind us making a fan game for Zelda. It is supposed to be a trilogy but my portion is just the engine and the editor. I'm attempting to make the editor robust enough to handle a trilogy so I don't have to re-code anything - they just make new data with it. After that I'll just release the editor to the Zelda fan community so others can make their own games. I don't think I'll be releasing the source as of yet. The Zelda game engine is cake since it's just 2D and that is just a lot of textured quads all over the screen. Most of it is extremely simple.

By the way, tools programming sucks. I always thought scrolling and selecting tiles was a piece of cake. Not. Easy math but a major pain in the rump. Is it just me or do you find that a Windows-based program eventually becomes a huge mess no matter what you do to keep it clean?

BTW, I think I've hijacked this thread.
• 12-08-2005
BobMcGee123
Yeah that's what is nice about just doing swept volumes, you can get a more-or-less exact and elegant collision time. It avoids the problem of tunneling which emerges when doing overlap collision tests, where objects can pass through each other, they never technically collide (...tryign to find doom3 developer interview where they talked about solving that problem...btw the doom3 homegrown physics is entirely in the doom3 sdk, not included as a part of the engine...the rationale as I understand it being that realistic physics isn't necessarily what every other game wants, subsequently it's too specific to be included in an engine).

Quote:

Physics code is actually easy. The collision detection stuff well....isn't...at least not for me.
Lots of things to test for.
I've had an easy time with sphere-to-sphere and sphere-to-world, but even then trying to get static vs friction work even in the simplest cases for objects that can both translate and rotate is basically really hard...I keep trying to come back and actually sit down and write the rigid body physics for just simple stupid boxes, I know I can do it, it's so just damn involved I can't find the time to actually do it.

Quote:

I totally lost all of my space-sim but I remember how I did it. I won't pursue it again until I find a better sphere-mapping algo for textures. None of the one's I found worked well and the BumpEarth sample that MS created is a mess, but it does texture correctly.
Was that in the hard drive defrag diasco?

Quote:

But I'd be interested. Right now I'm working on a 2D tile editor and engine for a Zelda fan game....
That's pretty cool. I think it's just as important to actually finish something as it is to make it look awesome and pretty. Every single 'image of the day post' that looks superb on gamedev.net is always a 'work in progress,' you typically don't see many playable finished games.

Quote:

Easy math but a major pain in the rump. Is it just me or do you find that a Windows-based program eventually becomes a huge mess no matter what you do to keep it clean?
Unfortunately, this certainly always seems to be the case (whether I was trying direct windows API or MFC it always turned into spaghetti code hell). Visual basic does have its merits, but I haven't touched that in years.
• 12-10-2005
psychopath
Ok, thanx! I think iv'e got enough information here to last me quite a while!

-psychopath