Sign in to follow this  
Butabee

Getting 3D coords to screenspace without matrix transforms.

Recommended Posts

Are you talking about theory, or practice?

Theory-wise, matrices represent linear transformations. 3D Perspective projection and orthographic trasnformation are both linear transformations in four dimensions. If you are asking for a simpler theory, you are looking for a 3D->2D mapping that is a simpler operation than a linear one. I'm quite confident that doesn't exist.

Practice-wise, the only complaint one can have with matrices is that if you have a matrix that has lots of zeroes or ones, you are doing redundant multiplications that could easily be optimized by hand if you did the transformation manually. (With generic 4x4 homogeneous transforms, you could be doing a redundant homogeneous divide per transform as well!) With GPUs and vectorized instruction sets this hardly a problem since they have dedicated instructions for the task. If you are looking to optimize this part, it is as simple as taking a pen and paper, and multiplying out the perspective projection matrix with your vector, and canceling out all the useless terms there. What remains are the "essential" operations that need to be done, and you can craft manual expressions that perform the projection, instead of doing the Matrix*Vector multiply.

If my reply was off, please try to be more specific what you are looking for?

Share this post


Link to post
Share on other sites
It's not possible to just 'render faster' in the general case. This mathematics for 3d rendering have been developed by decades by very smart people, some guys on a game forum aren't just going to invent a new way to do it that is any faster.

Now if you can be more specific there may be optimizations you can do to your restricted case. If you can add constraints to the equation you may be able to optimize, but you can't shortcut the transformation process unless you're willing to give up something. I don't know what that might be in your case.

Share this post


Link to post
Share on other sites
As a practical matter, 3D graphics are executed on graphics cards whose hardware is specifically designed do matrix transformations fast. Obviously, doing not-matrix-transformations on hardware optimized for matrix transformations will almost certainly be slower [smile]

But that said, computer scientists haven't all just been using matrices to represent coordinate transformations by some weird accident. It's actually a pretty fast way to do things.

What specifically do you find slow about matrices? Is it just that you don't understand the math?

-me

Share this post


Link to post
Share on other sites
Quote:
Original post by karwosts
It's not possible to just 'render faster' in the general case. This mathematics for 3d rendering have been developed by decades by very smart people, some guys on a game forum aren't just going to invent a new way to do it that is any faster.

Now if you can be more specific there may be optimizations you can do to your restricted case. If you can add constraints to the equation you may be able to optimize, but you can't shortcut the transformation process unless you're willing to give up something. I don't know what that might be in your case.



Are you saying there's no smart people in game development?

I guess to be more specific, I want to speed up transformation. Or maybe even do without it? Come up with a way to map 3D-2D like clb said? Something like that.

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
As a practical matter, 3D graphics are executed on graphics cards whose hardware is specifically designed do matrix transformations fast. Obviously, doing not-matrix-transformations on hardware optimized for matrix transformations will almost certainly be slower [smile]

But that said, computer scientists haven't all just been using matrices to represent coordinate transformations by some weird accident. It's actually a pretty fast way to do things.

What specifically do you find slow about matrices? Is it just that you don't understand the math?

-me


That's pretty much my point, I want a faster way to find 3D coordinates on the CPU because they aren't designed to do matrix transforms fast like a GPU.

Share this post


Link to post
Share on other sites
I played around very briefly with some software rendering stuff before there was such thing as 3d vid cards and opengl/directx (as im sure lots of people here did)

How i converted from 3d points to screen space was just this...

xScreen = xWorld / zWorld;
yScreen = yWorld / zWorld;

It worked just fine. Less math than doing matrix transforms but of course it isn't as powerful.

If you wanted rendering to be even faster, you might be able to do this:

xScreen = xWorld * zWorld;
yScreen = yWorld * zWorld;

and just make objects store their z coordinate as 1/z so you could turn the division into a multiplication during rendering. It would speed up your rendering, but whenever you moved an object it would take more time. If you have a lot of static objects it may be worth while.

If going this route, i'd say get it working with the first equation first before trying to get fancy.

Also, after you get your xScreen and yScreen you can do something like this to get a poor man's fov setting:

xScreen *= xFactor;
yScreen *= yFactor;

Hope this helps!

PS: If using the above equations, you probably will need to add half the screen width and half the screen height to the xScreen and yScreen so that the origin/vanishing point is in the center of the screen like you would expect instead of the upper left corner (which is the traditional 2d origin)

Share this post


Link to post
Share on other sites
Quote:
Original post by Atrix256
I played around very briefly with some software rendering stuff before there was such thing as 3d vid cards and opengl/directx (as im sure lots of people here did)

How i converted from 3d points to screen space was just this...

xScreen = xWorld / zWorld;
yScreen = yWorld / zWorld;

It worked just fine. Less math than doing matrix transforms but of course it isn't as powerful.

If you wanted rendering to be even faster, you might be able to do this:

xScreen = xWorld * zWorld;
yScreen = yWorld * zWorld;

and just make objects store their z coordinate as 1/z so you could turn the division into a multiplication during rendering. It would speed up your rendering, but whenever you moved an object it would take more time. If you have a lot of static objects it may be worth while.

If going this route, i'd say get it working with the first equation first before trying to get fancy.

Also, after you get your xScreen and yScreen you can do something like this to get a poor man's fov setting:

xScreen *= xFactor;
yScreen *= yFactor;

Hope this helps!


Thanks, this is the kind of stuff I'm looking for.

Share this post


Link to post
Share on other sites
Quote:
Original post by Butabee
Quote:
Original post by Atrix256
I played around very briefly with some software rendering stuff before there was such thing as 3d vid cards and opengl/directx (as im sure lots of people here did)

How i converted from 3d points to screen space was just this...

xScreen = xWorld / zWorld;
yScreen = yWorld / zWorld;

It worked just fine. Less math than doing matrix transforms but of course it isn't as powerful.

If you wanted rendering to be even faster, you might be able to do this:

xScreen = xWorld * zWorld;
yScreen = yWorld * zWorld;

and just make objects store their z coordinate as 1/z so you could turn the division into a multiplication during rendering. It would speed up your rendering, but whenever you moved an object it would take more time. If you have a lot of static objects it may be worth while.

If going this route, i'd say get it working with the first equation first before trying to get fancy.

Also, after you get your xScreen and yScreen you can do something like this to get a poor man's fov setting:

xScreen *= xFactor;
yScreen *= yFactor;

Hope this helps!


Thanks, this is the kind of stuff I'm looking for.


This is exactly what the matrices are doing. They are just a compact representation of a series of formulas (Object to world scaling, rotation, transformation, world to view transformation, rotation, projection).

And
x' = c * x / z;
y' = c * y / z;
is exactly what the projection part of the projection matrix is doing. And it's doing even more (far / near clipping planes, aspect ratio)

Share this post


Link to post
Share on other sites
I guess you got tired of my asking what you were really trying to do, huh? :) You could have just posted to your existing thread, you know - it's allowed ;)

I think it's worth noting that you got a similar response here:
Quote:
Original post by clb
If my reply was off, please try to be more specific what you are looking for?
Quote:
Original post by karwosts
Now if you can be more specific there may be optimizations you can do to your restricted case.
Which suggests that the responses you got in your original thread maybe weren't that out of line after all.
Quote:
Original post by Butabee
Are you saying there's no smart people in game development?
What's being said is that smart people have been working on these problems for decades, so it's unlikely that some random person on this forum or any similar forum, no matter how smart, is just going to suddenly come up with a radical new way of rendering things that's more efficient/powerful/whatever than existing methods. It's not that innovation never occurs, since it obviously does; it's just kind of unlikely that some random person who's not already at the forefront of ongoing research is going to be the one to do it. (Or so I would guess.)

As for what you're wanting to do, sure, you can eliminate redundant or unnecessary computations in some special circumstances. But, keep in mind that in order for it to be a win performance-wise, you have to be able to perform your 'fewer computations' faster than specialized hardware can perform the 'usual amount' of computations. So don't just assume that you're going to be able to perform a few divisions here and there and suddenly have a groundbreaking new renderer; you'll need to compare your results carefully against similar results derived using conventional techniques to see if you're actually getting anywhere.

Share this post


Link to post
Share on other sites
Whenever you want to speed up a specific type of matrix transformation, take a copy of your matrix-multiply function, then determine which variables (cells of the matrix/vector) are going to be constants (like 0 or 1) and factor them out of the equation.

i.e. A general matrix/vector multiplication, performed on a perspective-matrix and a position-vector will include a lot of "+0" and "*1" operations. If you strip these out, you've discovered the actual operation that the matrix multiply is performing. Then take this operation and write it optimally.

Share this post


Link to post
Share on other sites
I guess what you want to do is related to the voxel mapping thread. In this case you can use interpolation to speed up the rasterization.

You plan to rasterize a hightmap right?

so you have 2 plane vectors and the plane normal

p3d = plane_origin + plane_u * a + plane_v * b + normal * heightmap[a,b]

Afterwards you do the perspective divide.

For each step in the inner plane loop you just need one vector add and the normal * heightmap[a,b] computation to get the current 3d coordinate.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
Whenever you want to speed up a specific type of matrix transformation, take a copy of your matrix-multiply function, then determine which variables (cells of the matrix/vector) are going to be constants (like 0 or 1) and factor them out of the equation.

i.e. A general matrix/vector multiplication, performed on a perspective-matrix and a position-vector will include a lot of "+0" and "*1" operations. If you strip these out, you've discovered the actual operation that the matrix multiply is performing. Then take this operation and write it optimally.
For what it's worth, clb actually gave this exact same answer earlier in the thread (first reply to the original post).

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
I guess you got tired of my asking what you were really trying to do, huh? :) You could have just posted to your existing thread, you know - it's allowed ;)

I think it's worth noting that you got a similar response here:
Quote:
Original post by clb
If my reply was off, please try to be more specific what you are looking for?
Quote:
Original post by karwosts
Now if you can be more specific there may be optimizations you can do to your restricted case.
Which suggests that the responses you got in your original thread maybe weren't that out of line after all.
Quote:
Original post by Butabee
Are you saying there's no smart people in game development?
What's being said is that smart people have been working on these problems for decades, so it's unlikely that some random person on this forum or any similar forum, no matter how smart, is just going to suddenly come up with a radical new way of rendering things that's more efficient/powerful/whatever than existing methods. It's not that innovation never occurs, since it obviously does; it's just kind of unlikely that some random person who's not already at the forefront of ongoing research is going to be the one to do it. (Or so I would guess.)

As for what you're wanting to do, sure, you can eliminate redundant or unnecessary computations in some special circumstances. But, keep in mind that in order for it to be a win performance-wise, you have to be able to perform your 'fewer computations' faster than specialized hardware can perform the 'usual amount' of computations. So don't just assume that you're going to be able to perform a few divisions here and there and suddenly have a groundbreaking new renderer; you'll need to compare your results carefully against similar results derived using conventional techniques to see if you're actually getting anywhere.


Sorry about that, I don't really want to outperform hardware methods, but I'd like to be able to do something in software that's comparable to it in terms of looks and performance, although I really doubt I can since ALL of software rendering is slow compared to hardware with scenes of similar complexity and not just this one part.

Share this post


Link to post
Share on other sites
>>I'd like to be able to do something in software that's comparable to it in terms of looks and performance, although I really doubt I can since ALL of software rendering is slow compared to hardware with scenes of similar complexity and not just this one part.

Well, you can try CUDA or OpenCL

Share this post


Link to post
Share on other sites
Quote:
Original post by Atrix256
I played around very briefly with some software rendering stuff before there was such thing as 3d vid cards and opengl/directx (as im sure lots of people here did)

How i converted from 3d points to screen space was just this...

xScreen = xWorld / zWorld;
yScreen = yWorld / zWorld;



I think this only holds true if your camera is effectively at the center of the world -- 0, 0, 0?

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
It's not that innovation never occurs, since it obviously does; it's just kind of unlikely that some random person who's not already at the forefront of ongoing research is going to be the one to do it. (Or so I would guess.)


That's a common delusion.
People believe that there are geniuses who can invent stuff that nobody thought of. WRONG. Those times are gone in about 1930 or so.
There's nothing left to invent in the garage any more. All those stuff have been invented. All new garage inventions are proven to be fake/lie or just reinvention of something. Inventions today require way too much resources, knowledge and time for a lone wolf genius.

I'm talking about scientific inventions. You can still invent toys.


And as others have already stated: matrices are not magic. It's just a representation of linear equations. Sure, the calculations on the GPU are generalized, so a special perspective projection is much simpler than a general matrix operation. But it's hardware accelerated.

So if you do a software renderer, that division thing will be faster than your own fully implemented matrix multiplication.

The question is: is that the bottleneck, or you are just trying to be smart?


EDIT: before someone (who is Jyk) states, that these all have been discussed already: Do you think I don't take the opportunity show how freaking smart I am by reading the thread? [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
EDIT: before someone (who is Jyk) states, that these all have been discussed already
Um...no, I don't think what you posted above had been said in the thread previously - at least not in those words ;)

Share this post


Link to post
Share on other sites
Back in the day we would use a 3x3 rotation plus a vector offset (functionally identical to a 3x4 matrix). You don't need a full 4x4--it just simplifies clipping, and to a lesser extent, z buffering.

You won't beat a 3x3 matrix for rotating a 3d point. There's no "waste" there. That bone was picked clean centuries ago (literally).

Share this post


Link to post
Share on other sites
I was thinking I might try to do something with the angles of vectors compared to the camera. If you take a ray for each pixel it will have have a certain angle too. Then there just needs to be a fast way to match the vector angle with the ray angle.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this