Wednesday, October 19, 2011

64 – 3D Week 4 in review

Ohhhh yeahhhh! One month of working on the 3D engine. Nice progress if I do say so myself: 


No more barrellands! This time you get to see the table and stool created by BrewStew. To limit performance loss only the current level is populated with items, but in the future I’ll add an option to render all levels with full detail. There is no reason not to allow people with beefy computers to use their full potential. Also useful for anyone for taking high detail screenshots. 

Also stick around until the second part of the video, where you get to see a long lost feature that has made its glorious return: selection with the mouse. The problem is that selection with the mouse is far too slow. You won’t see that in the video, but it is. Optimizing this will be a low priority task. First I must make sure that the geometry generation time for a volume unit is as fast as it gets. Then I must make sure that a minimal number of volume units are updated. 

The high priority task is to figure out which algorithm to use for world construction, geometry building and buffer management. I have at least 6 strong contenders, each with their own advantages and disadvantages, plus probably a bunch of buffer interaction and fragmentation properties that I am yet not aware of. I also need to stick a huge number of different entities in the same scene. Up to this moment I mostly stuck a huge number of the same entity in the scene (trees, barrels). BTW, the trees are not visible in the video because they are not mesh based, they are procedural. Because I transitioned to the new hardware buffer based rendering I need to update the procedural generation for trees and I did not get to it yet. 

The algorithm that I am using right now is different from the one that created low poly 300.000 barrels. This one focuses on fewer higher quality objects. It is also lossy. Each section has a potential for holding items based on maximal buffer sizes, and when you go over this potential, items start to get skipped. Using the density from the video skipping should not occur, but maybe one or two items were dropped from the busier section. The dropping is class based, meaning that if you have a ton of tables and only a few barrels, the excess tables will not cause the barrels to disappear. Only excess items from within a category are lost: if you can have at most 300 tables, 400 barrels or 500 stools alone in a section (example number), you can have all of them visible at once in the same section. But if you have 302 tables, 405 barrels and 600 stools, 2 tables, 5 barrels and 100 stools will be dropped. 

A natural evolution of this algorithm will be to determine how many high poly entities to convert to low poly in order to not drop a single item. So instead of trying to render 405 high poly barrels and ending up only rendering 400 high poly barrels and dropping 5, the engine should render 395 high poly barrels and 9 low poly barrels. Again, example numbers. This can be easily done and I’ll implement it soon, but first I must add an analyze and caching step to world creation, so you know the totals for each section. 

One problem that is especially visible with highly zoomed out top down view is that it is sometimes very hard to tell what is going on. I need to figure out a method to make thing pop or something so you can tell what you are looking at. This is not a problem for first person camera, where the current semi realistic proportions and first person viewpoint make it a lot easier to tell what is going on. One trick I’ll try is to scale up small objects based on the vertical distance from the surface plane of the current level and the camera position. When you are zoomed in close, proportions are similar to the current ones. As you zoom out, small objects become larger and larger. I can also experiment with adding a few black borders to the textures to fake a cell shading style border, but I am not prepared for real cell shading right now.

How does Starcraft 2 do it?

21 comments:

  1. have u considered (experimented with) 2D cutouts? especially for trees.

    ReplyDelete
  2. Argh! still with the XY plane as the floor! It's like fingernails on a blackboard watching you try to navigate with everything sideways.

    This isn't maths class, it's a rendering engine. XZ is the floor D=

    ReplyDelete
  3. To Anonymous #1:
    Yes, the low end setting will probably use bill boarding heavily.

    But for high end I am testing if I can get it fast enough for full 3D models.

    Or did you mean for increasing the visual clarity using 2D cutouts?

    To Anonymous #2:
    Well I could change it to XZ but it would look exactly the same. I would adjust coordinates so camera still has the same relative logical position. With floor being XY or XZ it should be pixel perfect identical.

    I don't know how you can tell the difference? How do you expect the camera to work. Does not matter which coordinate you use, you fly up in the sky and look down at the floor. What changes should I do so you don't think it is sideways anymore?

    ReplyDelete
  4. It's all to do with the mouselook.

    Camera rotation conceptually has 3 degrees of freedom - pitch, yaw and roll. A mouse only has 2 dimensions of input and so typically we map these to pitch and yaw.

    This is a completely intuitive analogue to reality, since we can look up and down (pitch) and turn around (yaw) but human necks typically do not facilitate much roll. =)

    The problem with the camera as it stands right now is that you have no mechanism to stand on the "ground" and pan around laterally. The intuitive input for this is moving the mouse from side to side but that results in roll, which is completely bizarre.

    In terms of 3D engine design, there is a very good reason why XZ should be considered the floor. In any 2D system on a computer, the screen is an XY plane. When adding a third dimension, we look at a screen and consider Z as "depth" not height.

    Coordinate systems in 3D engines use this approach. You can consider a default camera position to be standing on the XZ floor, so that "up" is the positive Y direction, and "right" is the positive X direction.

    Until you start zooming around, this view "looks at" the XY plane, which is the same as what you would be looking at in a purely 2D system. I won't go into it, but this connection between the two systems makes the matrices for projection between 2D<->3D much nicer =)


    QUICK FIX:
    call setUpVector() on your camera object with a vector (0,0,1);

    Usually a camera object will require 3 vectors to set up:

    Position, Rotation, Normal OR
    Position, Look At, Normal

    For some reason, in Irrlicht you can only supply 2 vectors to the default camera on instantiation. The up vector (normal) defaults to (0,1,0).

    I understand if it's hugely painful to rewire your brain (and your existing code) to use this coordinate system. However, it is the industry standard and you would struggle to find ANY tutorial or example code that doesn't.

    ReplyDelete
  5. What you describe there is I think the way the "dwarf eye" camera works. You start in the middle on the map, a little bit above the floor, with the direction of you line of sight parallel to the floor. Moving the mouse up or down causes you to look up or down. Moving side to side pans around.

    Like in the video Experimental: First person camera ( http://www.youtube.com/watch?v=3fc0dvccrvM ). Is this what you want?

    But in the "fly" camera you start with the direction of the line of sight camera perpendicular to the floor. Pressing forward brings you closer, pressing back takes you further away. Moving mouse up pans to the north of the scene and moving left to the west.

    So there are two different cameras. Intentionally. The fly camera is an exploration camera, a "god's eye" camera, so I think it should be looking down.

    Even if I do make the fly camera behave like the dwarf camera, this could be done without changing the floor axes. Or am I mistaken? Maybe using the up vector modification you proposed is enough to change the fly camera to a dwarf eye camera behavior.

    ReplyDelete
  6. I think the problem here is that in this video it looks like you are rotating about the Z axis (causing roll) a lot, when instead you should be rotating about the Y axis (changing the Yaw) but because of the orientation of the world it isn't rotating correctly.

    ReplyDelete
  7. DHD:

    The fly camera should behave nicely if you simply tell it that "up" is the vector 0,0,1 using the method I suggested. You will still able to fly around but it will feel much more like you are "above" the world.

    In general, your coordinate system is not "bad" for any reason except that it is different from what every engine and every other developer would expect. If you don't adhere to standards that are as totally universal as this one, you're only disadvantaging yourself. Your code will be less readable, reusable and portable, and you'll have a harder time incorporating publicly available modules like this one:

    http://www.irrlicht3d.org/wiki/index.php?n=Main.RTSCameraByCmdKewin

    Anyway I've harped on enough =O I hope it was thought provoking!

    Anon #2

    ReplyDelete
  8. I tried setting that vector. Except for some very strange behavior, probably due to the different axes used by me, it makes your movement take place in a more parallel feeling plane to the floor. Not a perpendicular one. So no longer a "god's eye view". I want a view point similar to the Tropico franchise for this camera.

    Anyway, changing axes right now would be a huge endeavor. I do not place discrete meshes/scene nodes in the scene in the traditional sense or the Irrlicht specific way because that is far too slow.

    I ask again: do you want the camera to behave like in the Experimental: First person camera ( http://www.youtube.com/watch?v=3fc0dvccrvM ) (skip the first 10 seconds) video, only not grounded on the floor surface?

    ReplyDelete
  9. The default flying camera IS a first person camera by definition as it rotates around it's own axes. As such, given that your ground is XY, you should tell it that "up" is along the Z axis (I've just realised that you might have wanted to use (0,0,-1)). At that point, yes it will behave similarly to the ground level first person camera, but without restriction to a horizontal plane. At the moment, if you move your mouse up to look to the north, you can then move your mouse side to side to perform barrel rolls, which is glaringly unhelpful.

    If you want a third person camera like Tropico ( Example: http://www.youtube.com/watch?v=jdyojOFkUv8 ) then that is great, but it's a fundamentally different thing. The camera would need to rotate around the axes of whatever point you are looking at. In your case, the intersection between the ground plane and the camera line of sight - which you've already worked out for the cursor.

    ReplyDelete
  10. I have code that does Tropico style camera in Opengl using gluLookAt. Let me know if u would like to have a look.

    As mentioned above, you must be looking down on the ground in this mode. U cannot look skyward. So u may need different handling for first person view.

    ReplyDelete
  11. No, I want a first person Tropico style camera and I think that I kind of achieved that.

    But I'm would like to see your camera code. If I like how it behaves I could add such a camera. More options can't hurt (unless you have too many of them).

    ReplyDelete
  12. /*
    the following 3 vectors define a view in gluLookAt
    _ref ... what u are looking at
    _eye ... eye position
    _upv ... up vector, orthogonal to (-ref-_eye)

    the functions below implement the changes needed to _ref,_eye and _upv.

    tilt is a rotation of _eye about _ref. constrained along plane formed by (_ref-_eye) and _upv.

    turn is rotation about the vector (0,0,1). _eye is rotated along.

    zoom moves _eye along (_ref-_eye).

    panx pans the map horizontally. this moves _eye and _ref by the same amount.

    pany pans the map vertically. this moves _eye and _ref by the same amount.

    note that panning moves _ref. so u may no longer be looking at the ground.
    u need to set _ref back to ground after panning.
    */


    int tilt(float amt) { amt *= 0.8f; _cull = 1;
    vect t,s = { _eye.x-_ref.x,_eye.y-_ref.y,_eye.z-_ref.z };
    vect cr = crosspd(s,_upv); normalize(&cr);
    GLfloat m[16];
    glLoadIdentity(); glRotatef(+amt,cr.x,cr.y,cr.z);
    glGetFloatv(GL_MODELVIEW_MATRIX,m);
    t.z = _upv.x*m[8]+_upv.y*m[9]+_upv.z*m[10];
    t.y = _upv.x*m[4]+_upv.y*m[5]+_upv.z*m[6];
    t.x = _upv.x*m[0]+_upv.y*m[1]+_upv.z*m[2];
    if (t.z < -0.95f || t.z > +0.0f) {
    return 1;
    }
    _upv = t;
    t.z = s.x*m[8]+s.y*m[9]+s.z*m[10];
    t.y = s.x*m[4]+s.y*m[5]+s.z*m[6];
    t.x = s.x*m[0]+s.y*m[1]+s.z*m[2];
    _eye.x = _ref.x+t.x; _eye.y = _ref.y+t.y;
    _eye.z = _ref.z+t.z;
    return 1;
    }

    int turn(float amt) { amt *= 0.8f; _cull = 1;
    vect t,s = { _eye.x-_ref.x,_eye.y-_ref.y,_eye.z-_ref.z };
    GLfloat m[16];
    glLoadIdentity(); glRotatef(+amt,0.0f,0.0f,1.0f);
    glGetFloatv(GL_MODELVIEW_MATRIX,m);
    t.z = _upv.x*m[8]+_upv.y*m[9]+_upv.z*m[10];
    t.y = _upv.x*m[4]+_upv.y*m[5]+_upv.z*m[6];
    t.x = _upv.x*m[0]+_upv.y*m[1]+_upv.z*m[2];
    _upv = t;
    t.z = s.x*m[8]+s.y*m[9]+s.z*m[10];
    t.y = s.x*m[4]+s.y*m[5]+s.z*m[6];
    t.x = s.x*m[0]+s.y*m[1]+s.z*m[2];
    _eye.x = _ref.x+t.x; _eye.y = _ref.y+t.y;
    _eye.z = _ref.z+t.z;
    return 1;
    }

    int zoom(float amt) { amt *= 0.8f; _cull = 1;
    vect s = { _ref.x-_eye.x,_ref.y-_eye.y,_ref.z-_eye.z };
    float dt = sqrt(s.x*s.x+s.y*s.y+s.z*s.z);
    vect cr = s; normalize(&cr); cr.z *= dt/500;
    cr.x *= dt/500; cr.y *= dt/500;
    float dx = _eye.x+amt*cr.x-_ref.x;
    float dy = _eye.y+amt*cr.y-_ref.y;
    float dz = _eye.z+amt*cr.z-_ref.z;
    dt = dx*dx+dy*dy+dz*dz;
    if (dt > 4000) {
    _eye.x = dx+_ref.x;
    _eye.y = dy+_ref.y;
    _eye.z = dz+_ref.z;
    _dist = dt;
    }
    return 1;
    }

    int panx(float amt) { amt *= 0.4f; _cull = 1;
    vect t,s = { _eye.x-_ref.x,_eye.y-_ref.y,_eye.z-_ref.z };
    float dt = sqrt(s.x*s.x+s.y*s.y+s.z*s.z);
    vect cr = crosspd(s,_upv); cr.z = 0; normalize(&cr);
    cr.x *= dt/500.0f; cr.y *= dt/500.0f;
    float crx = amt*cr.x,rx = _ref.x+crx;
    float cry = amt*cr.y,ry = _ref.y+cry;
    if (rx > 0 && rx < MAPSIZE && ry > 0 && ry < MAPSIZE) {
    _eye.y += cry; _ref.y = ry;
    _eye.x += crx; _ref.x = rx;
    }
    return 1;
    }

    int pany(float amt) { amt *= 0.4f; _cull = 1;
    vect t,s = { _eye.x-_ref.x,_eye.y-_ref.y,_eye.z-_ref.z };
    float dt = sqrt(s.x*s.x+s.y*s.y+s.z*s.z);
    vect cr = _upv; cr.z = 0; normalize(&cr);
    cr.x *= dt/500.0f; cr.y *= dt/500.0f;
    float crx = amt*cr.x,rx = _ref.x+crx;
    float cry = amt*cr.y,ry = _ref.y+cry;
    if (rx > 0 && rx < MAPSIZE && ry > 0 && ry < MAPSIZE) {
    _eye.y += cry; _ref.y = ry;
    _eye.x += crx; _ref.x = rx;
    }
    return 1;
    }

    ReplyDelete
  13. http://tower22.blogspot.com/2011/10/compressor-part-22.html

    part 2 of DDS is there

    ReplyDelete
  14. You know if you get this game with enough game play as DF, I would be willing to pay 50-70 dollars for it (probably even more). It looking good.

    ReplyDelete
  15. To Anonymous:
    Thanks! I need to find out if Irrlicht can handle the compressed textures.

    To Ian Fischer:
    That is very generous of you! But I'm afraid I'll have to with a more reasonable pricing policy :).

    ReplyDelete
  16. To Anonymous with the camera:
    Thanks! I'll investigate that and reevaluate what camera modes will be available.

    ReplyDelete
  17. As for cell shading by adding black borders to textures, I have always found it better to just create a replica of the object slightly scaled up a bit more and coloured black. You then invert the vertex order for the triangles in the mesh so that front facing triangles become back facing and visa-versa .. of course you have added triangles to render so that's something to take into consideration.

    ReplyDelete
  18. @ Anonymous
    I think thats not possible, because you have one cube next to another. Even if you coul handle that, you'd have doubled the amount of triangles and that would lead to a massive performance problem...

    ReplyDelete
  19. Not really, it kinda depends on how you are storing and drawing the data, for example rendering loads of triangles separately will be detrimental to performance over drawing the same amount of triangle in one call as graphics cards are designed to handle massive amounts of polygons. And of course you have the backfacing triangles removed from low lods of the model where you wouldn't be able to see the border. It's not a perfect solution no, but it would be a much better effect than just painting borders on the textures themselves. Naturally there are other ways of doing this using shader effects.

    ReplyDelete
  20. Really good blog, very interresting game dev, can't wait next post and to try a alpha of this ui for df !! Bravo!

    ReplyDelete
  21. Jerome, this is not a UI por DF, it's a "clone" of DF with a nice UI.
    I hope the lack of news mean that the developer is working hard on the project

    ReplyDelete