2
\$\begingroup\$

I learn matrix transformations for game design and I struggle with some basic concepts. I see the actual multiplication taking place before rendering in this sequence:

  1. MODEL into WORLD: multiply each model's vertex by worldMatrix. If the model is big it's a bit of a stress for GPU.
  2. WORLD into VIEW: well, if Model to World was bad, than multiplying the whole world full of models by some matrix is a huge burden on GPU. Why then in every book authors say that is much better to do exactly this? The VIEW is just a point (one vertex) it's much easier to change one vertex than millions.
  3. Well any other steps in this sequence are irrelevant to me right now. I just stuck in 2. cause I don't believe that any one will perform such multiplications.

I'm sure no one multiplies world vertexes by any matrix, If i'm right here then and HOW the whole multiplication stack of transformation happens? I guess I'm missing some low level understanding.

P.S. So to stress my point: Why multiply the whole world by anything? I will only see the part of it! How this huge multiplication is avoided in game engines (openGL, ect).?

P.S.S. Thanks for answers guys! Huge job just to help the me___ Those are the most detailed answers I've evere gotten on any stachexchange forums. :)

P.S.S.S. I come from 2D visualization of financial data. Some of you point out that it can be the reason of my missunderstanding about why every world object must be processed. My pipeline:

  1. object\model space = is just a data serie with bunch of bars and prices. It's a 2D object with "bar" units in X direction and "price" units in Y direction. So by using "i" Serie.bar[i] one navigates in this array. I usually say that data series is in "array space" since I use "i" to navigate therer.
  2. world space = where 2 data series can co-exist. For example you have price of Google and Tesla in the same chart stacked on top of eachother for analisys of correlation.
  3. Camera space - a 2D rectangle in world coordinates. For example camera.width=300bars, camera.X =11000bar, camera.Y=33 $ per share.

Using mouse, user changing only camera (that's why it's super wired for me when someone says that view should not be moved and the world should be moved around). Camera coordinates change and when it is time to render, you just look inside camera and do such thing: for (int i = camera.left; i < camera.right; i++) { g.DrawSerie(google.bar[i]); } So you see, there is no need in and world transformation here. I know all I need before rendering thanks to "camera being in world coordinates". I guess you can't do in in 3D, but some details are still missing for me.

\$\endgroup\$
  • \$\begingroup\$ You don't need to run the transformation on the GPU, you can do that on the CPU as well. I also don't understand what you mean by "The VIEW is just a point" - the view isn't a point. And it's further unclear how you intend to transform the model into screen coordinates by doing a "vice-versa" calculation \$\endgroup\$ – UnholySheep Mar 14 '17 at 12:50
  • \$\begingroup\$ By Vice-versa I mean that you either move world around camera (which means that you multiply many world vectors) or move camera in the world (which means you change only camera coordinates). \$\endgroup\$ – coobit Mar 14 '17 at 13:03
  • \$\begingroup\$ You do move the camera around in the world, but that's not part of the rendering - Your screen has coordinates ranging from 0,0 to screenwidth,screenheight (exact details depend on rendering API) - you need to get your 3D view into those coordinates, so you need to transform from model to world to view. \$\endgroup\$ – UnholySheep Mar 14 '17 at 14:14
  • 2
    \$\begingroup\$ I think you're severely underestimating how amazing your gpu is at calculating, especially when it comes to fundamental things such as vectors and matrices. \$\endgroup\$ – Charanor Mar 14 '17 at 15:12
  • \$\begingroup\$ It might help to think about what happens if you don't do those things, to understand why we do them. \$\endgroup\$ – user253751 Mar 15 '17 at 2:05
11
\$\begingroup\$

Think about it logically:

What is your goal when you render something?
To display it on the screen!

What are the constraints?
The model must be visible to the camera (i.e. in the view frustum, not occluded by other objects, etc.)

What are the inputs?

  1. A collection of vertices in a coordinate system local to the model's origin.
  2. A transformation matrix that describes where and how the model is oriented in the game world.

What are the outputs?

  1. A collection of vertices in view space (i.e. relative to the view, commonly defined by a single "camera") which can be used to generate fragments, which then become pixels in normalized device coordinates (just like a 2D game, the screen is 2D after all).

The process goes something like this:

  1. First, you start with a list of vertices in model space (relative to model origin/coordinate system). This allows you to easily modify meshes outside of your game (e.g. in Blender) because the coordinate system is self-contained.
  2. Then, the vertices are transformed to world space (relative to game world origin/coordinate system, or game chunk origin). This allows you to do collision detection or other game world dependent logic.
  3. Next, the vertices are transformed to view space (relative to camera origin/coordinate system) so that you can decide what is visible to the camera. One such technique is called "frustum culling" and calls for the renderer to ignore vertices behind the camera or outside of the field-of-view.
  4. Last, the view space vertices are transformed to normalized device coordinates so that the fragments can be depth-tested, blended, and any other post-processing effects can be applied (e.g. shaders). This is necessary because it allows you to calculate the final color to display at each pixel on the screen.

I suppose if you have no game world, you could eliminate the world space calculation step and go directly from model space to view space (essentially, you'd be saying your model space is your world space), but this means you can only have one object in the entire world, and there is no way to do any game world specific logic such as collision between multiple objects. In general, this is not very useful.

As you can see, all of these steps are not only necessary, but the later ones are actually HUGE optimizations (frustum culling, for instance) because they can save you from rendering the majority of the things in your scene (especially in small, enclosed areas like the inside of a building). Why spend time rendering the 400,000,000 vertex forest outside when you're standing inside of a 3,000 vertex shack with no windows?

\$\endgroup\$
5
\$\begingroup\$

MODEL into WORLD: multiply each model's vertex by worldMatrix. If the model is big it's a bit of a stress for GPU.

It's not actually that much of a "stress." The GPU is hardware that is tailor-built to perform this operation hundreds of thousands of times with ease. This is important since it seems to be the root of your confusion. It's just not nearly as big of a deal as you think it is.

WORLD into VIEW: well, if Model to World was bad, than multiplying the whole world full of models by some matrix is a huge burden on GPU.

In fact, unless some vertex shader needs to do some work in world space (which isn't always necessary, this step and the prior step are combined. That is, the model-to-world and world-to-view matrices are multiplied together once, before rendering, and every rendered vertex is multiplied just once by the combined matrix. Lighting work is sometimes done in view space, so the transformation tends to pause there, but it's also possible to combine the entire world->view->clip space transformation into a single matrix if one doesn't need to do anything in view space either.

This further reduces the effective cost of the transformations.

The VIEW is just a point (one vertex) it's much easier to change one vertex than millions.

No, the view is conceptually a point and a basis (a rotational frame of reference). You can't "just change the view." You need to know the positions of all vertices relative to the view's location and orientation eventually, so you must transform all the vertices. You could use the position and orientation of your view in world-space to do some lighting work, but ultimately you'll still need coordinates relative to the view frame for clipping them against the view frustum, so that's kind of a moot point.

I'm sure no one multiplies world vertexes by any matrix, If i'm right here then and HOW the whole multiplication stack of transformation happens? I guess I'm missing some low level understanding.

You're not right. World vertices are multiplied by matrices to bring them into clip space.

The geometry transformation pipeline is fairly straightforward: geometry starts in model space, is transformed to world space, then to view space, then to clip space, where clipping against frustum planes is performed. Then the perspective division is applied, coordinates are transformed to normalized device coordinates and eventually to window coordinates where they are rasterized.

There's no hidden tricks, really, other than the fact that you can sometimes skip spaces you don't need to explicitly be in by combining matrices (e.g., multiply model-space vertices by a combined world-view-projection matrix to go right to clip space). The cost for doing this transformation is extremely small on the vertex-by-vertex basis.

\$\endgroup\$
  • \$\begingroup\$ Well said. I pointed out the fact that certain matrices could be combined and the result cached to avoid the per-vertex cost of that multiplication in my chat with the OP (linked in the comments on my answer), but it seems the OP is trying to chart financial data and may not even need a 3D scene to begin with. There are definitely some more concerning decisions going on here. Nevertheless, we can both only answer the question we were given. \$\endgroup\$ – Dan Mar 14 '17 at 17:47
  • \$\begingroup\$ @Dan I saw this too so unfortunately yes. \$\endgroup\$ – Arthur P. R. Mar 15 '17 at 5:59
3
\$\begingroup\$

Please allow me to elaborate what the responsibility of the GPU should be in the most common scenarios as well as the responsibilities of the CPU, game-engine, and OpenGL.


Basics to the OpenGL Pipeline

First, in the context of the OpenGL rendering pipeline, the GPU has a vertex shader program which processes only 1 vertex at a time. This vertex is transformed by 3 special matrices (in this order):

  1. Model Matrix - the vertex is taken from local model coordinates and placed into world coordinates. This is where you position/orient/scale your model to be in its proper place relative to the whole scene.
  2. View Matrix - the vertex is transformed in such a way that it looks like it is being viewed from a particular location, angle, and distance. This mimics the behavior that a camera might; however, in OpenGL, there is only 1 camera (which is always facing into the screen).
  3. Projection Matrix - the vertex is transformed according to the parameters of the viewing frustum. This is where things like perspective divide occur (in the case of perspective projection).

After being processed by the vertex shader, the transformed vertex is combined with other vertices during primitive assembly, then further operations such as rasterization and fragment processing occur.


Who is responsible for what?

Your initial observation is valid, saying that the GPU could be stressed if it has process each vertex of a large scene. This means we have to be careful about what we send to the GPU. As you indicated, it is pointless to waste GPU time with processing things that never end up on the screen. So, in the context of game-design, a game-engine must decide, in some manner, how to manage which parts of the scene are drawn. There are many methods to doing this, but I'll list a few:

  • Game engines can divide the map into sections and only render objects within a certain distance of the observer/player. Optionally, fog is used to make a gradual seam to the parts of the world without content.
  • Game engines can control level of detail so low-poly models can be used where the difference is negligible (e.g. models in the distance).
  • Game engines can look at which parts of a scene might be occluded by those up front. Rather than relying on a depth test, the game engine can omit all of these vertices from being sent to the GPU in the first place! This is particular useful for rendering cities.
  • Rather than relying on mechanics of pre-built engines, you can write your own to control how the GPU is used.

All of the above game-engine optimizations occur on the CPU since they involve making decisions on which data to sent to the GPU. However, there are other optimizations provided by the GPU and the OpenGL pipeline. This includes things such as per-sample operations and tests (such as depth test), but also includes things such as view clipping. In the case of clipping, this prevents vertices outside of the viewing frustum from being further processed.

OpenGL also provides some more methods of optimization by allowing you to offload your models into the GPU memory through the use of Vertex Array Objects and various types of buffer objects. OpenGL also has various rendering modes, such as indexed rendering which can decrease the number of vertices actually sent to the vertex shader.

As far as optimizations go, there are predominantly two places where you save time the most.

  1. First, you save a large amount of time by deciding what to send to the GPU (these are the game-engine optimizations).
  2. Second, you save a large amount of time by offloading data to the GPU as opposed to sending data from the CPU each time you render a frame. Once in GPU memory, drawing the model becomes very quick.

Many of the other optimizations are still useful, but may only shave off a small amount of processing time.


I hope this helps provide you with the "low-level" understanding you were looking for. Feel free to ask questions if anything is unclear!

\$\endgroup\$
  • 1
    \$\begingroup\$ Excellent answer! It's a very large problem to cover in a single answer, but your overview is very good. \$\endgroup\$ – Dan Mar 15 '17 at 16:18
1
\$\begingroup\$

I think the other answers has already covered the bulk of this, yet I want to make some assertions on the P.S.:

P.S. So to stress my point: Why multiply the whole world by anything?

Because the world space does not match, it is representation on screen. For instance, in a 2D game, you may be contempt with applying an offset to the world position and drawing only what is in the bounds of the screen... not in 3D. Why? Because you have rotation and perspective. To archive these effects we use matrix transformations.

That is without solving the problem of occlusion. Without changing to camera coordinates you lack a way to tell what object hides another, and thus we need the transformation.

Furthermore, consider that you may need additional geometry (outside of viewing frustum) to make other effects, such as shadows or reflections.

I will only see the part of it! How this huge multiplication is avoided in game engines (openGL, ect).?

Game engines may resource to additional work to keep the GPU and CPU load low. It should be noted that video games has been using the techniques I describe below for a long time, and modern GPU hardware is much better than it was when they were first introduced.

Combining these techniques allows huge open world games with thousands or millions of objects, where sending everything to the GPU does have an impact on the performance.

For example, game engines no longer rely solely in the painter algorithm for 3D; instead, the engines leave the occlusion problem to the GPU, which can handle, for example, interlaced triangles thanks to the depth buffer. Although there are situation where the engine can optimize occlusion, it is not the general case.


Binary space partioning

Let's start at the age old Doom. The original Doom was big for the constraints of the hardware of the time. The engine was based on the one from Wolfenstein 3D which worked by ray-casting to find the distance to the walls across the horizontal field of view and scaling them in screen to make the effect of perspective.

Doom added vertical levels to the map, which meant that when a step on the floor was found, the engine had to revisit the area to find what is beyond that step in a recursive proccess... this implies that "complex" vertical structures (stairs) are very taxing to performance.

The solution was a technique known as BPS (Binary space partitioning), which in general terms means to divide the world in half (make a binary partition) and then in half again, and so... adding the whole structure to a tree structure that can be navigated to find nearby objects or objects that are in certain general direction from another. This means that they did not have to query the whole geometry each step.

Since, and thanks to Doom, BSP is common in game engines.


Split your world

We want to avoid loading the whole map at once. Instead, we want to load only the parts we need.

Various games for the original PlayStation would use every door of every room as a load point. It should be noted that loading was (and continues to be) a bottleneck for PlayStation.

But that doesn't means that there weren't clever solutions and workarounds. For instance Crash Bandicoot used narrow and sinuous paths for its levels, this allows hiding fact that only objects near the player are ever loaded, as the path twists often and keeps the distance the player may see limited.

Nintendo 64 had a different set of constraints. Even with better load speed, there is a cap for the size of the map. For instance, Mario 64 could not afford a large open world. Instead the world was divided in regions acceded by the pictures in the walls, and the size of each one was kept in check.

At some, point the same was considered for Zelda: Ocarina of Time (it would be constrained to Hyrule Castle, and you would enter pictures in the walls). Fortunately, improvements on the engine allowed for larger maps, yet there are still load points between regions.

Finally consider old GTA games, which divided the map in smaller ones. GTA Vice City had two main islands loaded separately, when the player is traveling from one to the other there is a load screen... from one city the other is visible at distance, but this is only a low polygon model.


Provessive load

Consider now Minecraft. In spite of its unsophisticated appearance, it has a high polygon count (consider all the triangles for all the cubes for a virtually endless map, that is a lot of vertex). How does it handle them? Well they are loaded in chunks, the engine only sends to the GPU chunks that are nearby the player.

If you experiment with render distance and other graphics options of Minecraft - or also due to a chunk that failed to load - you may find yourself looking at the void (well, just the skybox, actually) where there should be land.


Level of detail

GTA San Andreas did not have load screens dividing its map, how did they do it? They use LOD (Level of Detail)... GTA San Andreas works on a low polygon model of the complete game world (including roads and building) that is always loaded, and then other models are loaded on top of it (including roads and building, again). The models are replaced with other of higher level of detail as they get closer they get to the camera.

This means that if you move fast enough (or you PC is slow enough) you can catch up to the edge where models are being loaded... yet, thanks to the basic model that's always there, you will always see roads and a crude version of buildings instead of the void.


That much the state of the art (plus any custom optimizations for particular cases and any proprietary algorithms of which I am not aware). These technologies, in addition to the progress done GPU hardware allows huge maps such as those found in GTA, Skyrim, Red Dead Redemption, Breath of the wild, etc...

P.S. OpenGL? Not a game engine.

\$\endgroup\$
  • \$\begingroup\$ " For instance, in a 2D game, you may be contempt with applying an offset to the world position and drawing only what is in the bounds of the screen... not in 3D. Why? Because you have rotation and perspective. To archive these effects we use matrix transformations." I see here lies my troubles with understanding all of this... I draw in 2D financial data. I never multiply any world objects(data series in my case) by view, camera ect. I just store in my camera world coodinates, like camera has width = 30 bars, height = 400 ticks of price and located at 4th bar and price at 30bucks. \$\endgroup\$ – coobit Mar 14 '17 at 20:58
  • \$\begingroup\$ When I need to render, I just send unmultyplied data to drawing context. That is g.DrawLine(30bar, 5$, 30bar, 6$). Before that I look into my data and see that bars I should draw and what I shouldn't (so I do culling by hands). \$\endgroup\$ – coobit Mar 14 '17 at 21:01
  • \$\begingroup\$ @coobit may these videos help you Triangles and Pixels \$\endgroup\$ – Theraot Mar 14 '17 at 22:39
  • \$\begingroup\$ @coobit well that's just because you're not doing rotations. How would you do rotations? \$\endgroup\$ – user253751 Mar 15 '17 at 20:20

protected by Josh Mar 14 '17 at 20:01

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.