3D Object Selection

[Baker]

3D Object Selection

This used to be one of the larger wants on my to-do list. A few days ago, I searched for this info like the holy grail, some tutorial or same project to explain it as I suck at 3D maths.

Better than finding one that works, I found one that almost worked. It was SO CLOSE. But it didn't work 100% right. Succumbing to being so close, I opened up DarkPlaces and searched for PRYDON_CURSOR and did a Googling frenzy on the topic. For hours, I was on the brink of fixing it, trying to work out the missing components and in my head the mechanics.

Finally, I did something I felt would work. It didn't. After 10 hours of frustration. And then I clicked it again. And it did work, I clicked wrong the first time.

3D calculations are, in fact, easy. I can say this in hindsight. And what makes me rather happy about this experience is that if I ever get time to mess with the QuakeEd editor source code by Sikkpin, I should be able to add rotating brush texture rotation into it. And work with the BSP editor tools.

[I get ever increasingly irritated that when I took all those matrix math kind of college courses they never did explain decent practical uses or applications of matrix math. Had they done so ... grrrr]

But better than that, I'm going to explain the basics of 3D math calculations. I have some more to learn. But going from not understanding it to rather well understanding it, I think I can explain how it works very well even for people like myself from a week ago that struggled deeply with the concepts. And do it lucidly and easily. It really is super easy.

(To be continued. Next time ... explanation. The following time: a really fun working project I already wrote for Mac OS X but I need to convert it to MSVC6 and CodeBlocks for Windows. Won't have a MSVC Express 2008 project, my Vista notebook died in September and my XP desktop doesn't have the right stuff to run 2008.)

[mankrip]

I'm deeply interested. There are tons more I could do in Quake if I knew 3D maths well.

Also, when I found this article I wondered if it hadn't been written by you. I've built a quite long to-read list over the last year.

[Spike]

what really annoys me about matrix maths is that a*b is not the same as b*a.
I'm never sure if I'm multiplying it the right way.

Then there are column major and row major matrices, etc...
Note that model+view matricies in OpenGL and Direct3D are 100% identical. The differences are purely in the documentation.
(d3d projection matricies are different, however, as the hardware z range is 0 to 1 in d3d and -1 to 1 in opengl - this thus applies to all combined modelviewprojection matricies as well).
Thus you can (for the most part) reuse your matrix code for either rendering api.

to go from screen to 3d space, there's always gluUnProject.
FTE has a Matrix4x4_CM_UnProject function to do the equivelent work.
If you unproject a cursor at z=-1 and z=1, you will calculate the point at both the near clip plane and the far clip plane, you can then just trace a line from near to far to see what you hit.

unproject is also one of the functions provided in the csqc api (with a slight difference - z is world distance from near clip plane rather than z fraction, which is renderer api agnostic and more logical).

[Baker]

PART 1 of X: Placement of Entities in World

Entities have the following characteristics:

1. X, Y, Z position in world.
2. pitch, yaw, roll. Yaw is like is the grunt facing you (0 degrees) or away from you (180 degrees)
3. Size scale

grunt.xyz = {25, 15, 0]; grunt.angles = {pitch 0, yaw 90, roll 0}

// We are going to render a grunt using OpenGL 1.x
glTranslate (Grunt.x, Grunt.y, Grunt.z) // Position grunt in worldspace

glRotate (grunt.pitch, 1, 0, 0) // The grunt has a pitch of 0. Rotate on X axis.
glRotate (grunt.yaw, 0, 1, 0) // With a pitch of 0, the grunt might be facing you. pitch 180: facing away pitch 90: facing right. Rotate on Y axis.
glRotate (grunt.roll, 0, 0, 1) // Hopefully the grunts roll is 0, otherwise he'd look quite silly. Rotate for Z axis.

glScale (1, 1, 1) // Draw him using a width scale of 1, a height scale of 1 ...

Render_Grunt () // Now draw the grunt model ....

What is particularly fun about the above. Those simple instructions ... you are using matrix math and you don't even know it.

[mh]

D3D is nice in that it doesn't really enforce any matrix convention. You can use row major or column major, left handed or right handed, and so long as you pass it to your shader properly it works. It does mean that you get a load of extra work loaded on you that the OpenGL stack handles automatically for you though, but it's neat being able to go in there and manually adjust values as needed (not that you'll often need to).

Interestingly, while most D3D documentation and code will use row-major, when it's shaders are doing the position * MVP calc it uses column-major, so the matrix must be transposed when passing to the shader. D3D9 handles this automatically for you, in 10+ you must do it yourself. D3DXMatrixTranspose to the rescue - the D3DX stuff is really really good indeed, but it does tend to require that you use it's own data types rather than generic float arrays. If you do build code around it's own types you get a lot of really neat helper routines though.

D3DXMATRIX is really lacking only one thing and that's members to perform transforms in-place on the matrix. I've ended up writing a class that inherits from D3DXMATRIX and adds these.

Code: Select all

class QMATRIX : public D3DXMATRIX
{
public:
   QMATRIX () {};
   QMATRIX (float _11, float _12, float _13, float _14,
          float _21, float _22, float _23, float _24,
          float _31, float _32, float _33, float _34,
          float _41, float _42, float _43, float _44);
   void LoadIdentity (void);
   void Translate (float x, float y, float z);
   void Translate (float *xyz);
   void Rotate (float x, float y, float z, float angle);
   void Scale (float x, float y, float z);
   void Scale (float *xyz);
   void OrthoOffCenterRH (float l, float r, float b, float t, float zn, float zf);
   void PerspectiveFovRH (float fovy, float Aspect, float zn, float zf);
   void Projection (float fovx, float fovy, float zn, float zf);
   void MultMatrix (D3DXMATRIX *in);
   void LoadMatrix (D3DXMATRIX *in);
   void TransformPoint (float *in, float *out);
   static void UpdateMVP (QMATRIX *mvp, QMATRIX *m, QMATRIX *v, QMATRIX *p);
};

There is (or at least was) an ID3DXMatrixStack interface which gives you a GL-like stack, but without the silly stack depth limits. I found it nasty to use though.

I used this instead of a plain float array in RMQ and found it quite suitably awesome:

Code: Select all

typedef struct _glmatrix
{
   union
   {
      // put first because gcc barfs a little
      float m16[16];
      float m4x4[4][4];

      struct
      {
         float _11, _12, _13, _14;
         float _21, _22, _23, _24;
         float _31, _32, _33, _34;
         float _41, _42, _43, _44;
      };
   };
} glmatrix;

Cute fact #1 - you can extract the frustum planes and values of vpn, vup and vright from your main matrixes in Quake, but you'll need 3 matrixes instead of two for it - the "Z going up" thing needs to go into the third. Then multiply them out and you get your MVP. Cute fact #2 - a vector by matrix multiply is just a series of DotProducts.

(Yeah, I always end up doing matrix multiplies twice too; I invariably get the order wrong first time).

[Baker]

I'm deeply interested. There are tons more I could do in Quake if I knew 3D maths well.

(btw: Spike hit on the annoying Quake vs. OpenGL vs. Direct3D coordinate system.) No that link you provided isn't me, mostly float around here/Func/QuakeOne and that's mostly it.

[Baker]

PART 2 of X: Drawing a Scene Outline

To draw a scene ...

Define the screen real estate in terms of screen size.
Define where we are in the map or our "camera position" or our point-of-view.
For each monster, tell hardware where monster is and render monster.

In a bit more detail. Again, the OpenGL 1.x way of doing things ...

// Define 2D presentation parameters using screen width/height and FOV
A1. Viewport. You need to define the real display area. In 1024x768 full screen resolution, this would be (0,0) to (1024,768). This is the Viewport.
A2. Define field of view for our viewport. (Then you calculate the frustum using a standard formula). This is the Projection Matrix.

// Fill in the 3D world by defining the world coordinate system, camera position and drawing each entity.
B1. Define the coordinate system for the world. This step is usually unnecessary, but this is the World Matrix.
B2. Camera Position X, Y, Z + roll angle pitch. This is the View Matrix

C. For every object or monster in the world ...
C0. ----- Save our position ..
C1. ----- Move to the location (translate), rotate the object as needed (rotate) and set the sizing if needed (scale). Effectively ... the ModelView Matrix
C2. ----- Render the object
C3. ----- Restore our position.

D1. We are done. OpenGL has our scene painted to an image of size 1024 x 768. This is the color buffer.
D2. Update the display by copying the color buffer picture to our display. Swap the buffer. Or flip the buffer. Or flush the buffer or whatever word you prefer.

By saving every one of these matrix calculations we can calculate some interesting stuff ... as to be explained next ...

[mh]

Put the inverse of the world space matrix into R_PushDlights (it will be identity for the world), multiply each dlight origin by that, and suddenly you get dynamic lights being able to properly affect moving bmodels. Awsome example #1.

[Baker]

Put the inverse of the world space matrix into R_PushDlights (it will be identity for the world), multiply each dlight origin by that, and suddenly you get dynamic lights being able to properly affect moving bmodels. Awsome example #1.

Yeah, during the summer I achieved a few successes like getting shadows on brush models, but also experienced a few fails related to stuff like this with possibly dynamic light being in the fail category.

Knowing how to do the calculations now, I think my next attempt will have different results.

[Baker]

I've been making a fun little demo that I should be able to make work in WebGL too (nothing beats beating able to play around without loading anything ... well ... except that it requires Google Chrome or Firefox. WebGL is inherently insecure in a way but that's another story ...).

However, I have sort of a stumbling block. Mentally. And I've always known this: there is no such thing as "ROLL" for avelocity. Part of the fun of the demo is mimicking Quake entities way of thinking.

ROLL only exists from a first person perspective. An object seen in 3rd person cannot have a roll, since roll is pitch seen from the side. 2 angles completely define an orientation and therefore any angular movement.

Also of a side note: Quake doesn't deal with roll from a map navigation point-of-view (therefore no upside down players walking on the ceiling ), like say a flight simulator would. And the addition of roll in first-person navigation changes what pitch and yaw and side stepping represent.

/Is thinking ...any insightful comments welcome.

[Spike]

roll angles in quake exist in a form relative to the pitch+yaw angles. you can decouple them by using a matrix/quaternion instead.
you cannot express all orientations without a roll angle.
quake also doesn't change gravity based on pitch, so its at least consistant - a pitch of 180 is just as much fun as a roll of 180.
it could be fun to have some tunnel that changes your gravity direction based upon distance from the center, but doing it with eular angles is going to be painful.
if you were making a game like descent, you'd not use such terse angles, but just keep everything as a matrix. if you want to pitch up and down, you'd multiply the ship's current matrix by a rotation matrix, same as if you were rolling or yawing, the only difference is the rotation matrix's axis.
the most useful feature of eular angles is that if you interpolate them, your value will always travel around the edge of a sphere. but the issue there is that they won't travel in a straight line across the surface, especially if there's a roll angle. with an interpolated matrix, that point on the sphere would go from A to B *through* the sphere instead of across the surface. I'm not quite sure what a quaternion will do, but those can at least be normalized/scaled easily.

[qbism]

To mimick Quake navigation, give the viewer a jetpack... fly above the horizontal surfaces and look down (or under/up). Or give the entity a jetpack. Without a surrounding environment there's no basis to judge whether it's the camera or the object that's moving.

[Baker]

roll angles in quake exist in a form relative to the pitch+yaw angles. you can decouple them by using a matrix/quaternion instead.
you cannot express all orientations without a roll angle.
quake also doesn't change gravity based on pitch, so its at least consistant - a pitch of 180 is just as much fun as a roll of 180.
it could be fun to have some tunnel that changes your gravity direction based upon distance from the center, but doing it with eular angles is going to be painful.
if you were making a game like descent, you'd not use such terse angles, but just keep everything as a matrix. if you want to pitch up and down, you'd multiply the ship's current matrix by a rotation matrix, same as if you were rolling or yawing, the only difference is the rotation matrix's axis.
the most useful feature of eular angles is that if you interpolate them, your value will always travel around the edge of a sphere. but the issue there is that they won't travel in a straight line across the surface, especially if there's a roll angle. with an interpolated matrix, that point on the sphere would go from A to B *through* the sphere instead of across the surface. I'm not quite sure what a quaternion will do, but those can at least be normalized/scaled easily.

Useful infos. Been thinking about physics and such lately. That gravity ideas is rather interesting.

With MH's super jumbo sizing capabilities, I think a sphere world might be possible if the physics could work. And well ... the navigation. The map would be possible maybe, but the user interface and the QuakeC couldn't be done without huge modifications.