1. Forum moved (you can use login and pass from old forum)

High Priority Task: Rendering algorithm

Discussion in 'Data' started by Istrebitel, Jun 15, 2017.

  1. Istrebitel

    Istrebitel Well-Known Member Official Developer Administrator
    3/28

    Joined:
    Aug 8, 2016
    Messages:
    185
    Likes Received:
    76
    Best Answers:
    1
    This is going to be something for people with programming skills, and I don't believe it will be possible to extract from vanilla, but I guess this is the best place to put it.

    We need to figure out in which order to draw stuff, so that the end result looks properly.

    So, the way objects in X-Com 3 are drawn is that each tile can contain 4 map parts.
    - Left wall (that is top left if you look at it on the screen),
    - Right wall (top right)
    - Ground (floor)
    - Feature (things like trees, columns etc.)

    We can figure out draw order for that easilly - draw ground, then walls, then feature. And then again, any tile with a higher coordinate should be drawn over a tile with a lower one. So we could draw tiles in any order (z->y->x or x->y->z) and get a proper picture.

    Z->Y->X was the chosen order for OpenApoc

    And then there are objects. Projectiles, items, units. The idea was simple: draw the object in the tile it belongs to.

    However, objects can span multiple tiles, and this is where it fails. Let's examine two screenshots from vanilla.

    Example 1:
    [​IMG]
    Here two right arrows indicate that we have a right wall in 0,0,1 (that is, x=0, y=0, z=1) and a left wall in 1,0,0. And there's a falling feature indicated by the left arrow. We have to either draw it when we draw 0,0,0 or 0,0,1. Now, if we put it in 0,0,0, then, since we draw in z->y->x order, everything with higher z is drawn after everything with lower z, so the right wall of 0,0,1 is drawn over it, and if we put it in 0,0,1, then for the same reason it is drawn over 1,0,0.

    It might seem that drawing objects in columns, meaning, X->Y->Z order, is the solution. However, that is not the case.

    Example 2:
    [​IMG]
    I could not find an example with a right wall, so just assume that there's a right wall in 1,0,0 (while actually it's a feature in 1,-1,0 but forget that).
    Anyways, we have a unit in 0,0,0 or 1,0,0 and ground at 0,0,1 and right wall at 1,0,0
    If we would draw in columns (Z last) we would either have to draw the unit in 0,0,0 in which case 1,0,0 would be drawn over it, or in 1,0,0 in which case it would be drawn over 0,0,1.

    The problem is obviously when object spawns more than one of whichever two dimensions we iterate over first.

    So if we draw Z then Y then X, our draw cycle looks like this:
    For every z
    For every y
    For every x
    Draw x,y,z

    Meaning our draw order is:
    0,0,0
    1,0,0
    ..
    n,0,0
    0,1,0
    1,1,0
    ..
    n,1,0
    etc

    So when an object spans multiple X tiles it's not a problem, just draw it in the last X it belongs to, but if it spans multiple Y's or Z's then there's a problem.

    X-Com 3 can have objects that span as many as 3 in every dimension (3x3x3). That would be a large unit moving diagonally while changing height at the same time (like, a Psimorth moving diagonally up, from 1,1,1 to 2,2,2).

    I was once given a link to how OpenXCom does it, but I couldn't make much sense from it:
    https://github.com/SupSuper/OpenXcom/blob/master/src/Battlescape/Map.cpp#L456

    It seems they always render objects so that they overlap everything, and then re-render overlapped tiles that should be over an object? How many tiles would we have to re-draw in OpenApoc since we can have 2x2x2 units moving in three directions at the same time?

    Anyways, need help with this one. Need to figure out how do we render objects so that nothing overlaps improperly.
     
    makus likes this.
  2. The Reaver of Darkness

    The Reaver of Darkness Registered
    31/56

    Joined:
    Sep 7, 2014
    Messages:
    88
    Likes Received:
    9
    Best Answers:
    0
    I think a falling object should count as being in the tile directly below it, with its sprite extending upward and occluded in the same way as if it were at the base of that space. Then everything else should work if you render it one layer at a time, from bottom to top.
     
  3. darkestaxe

    darkestaxe Registered
    39/56

    Joined:
    Jul 17, 2014
    Messages:
    18
    Likes Received:
    7
    Best Answers:
    1
    To Start with, drawing 3D 101: Start from the most distant point from the viewer/camera, not the left side world where you started recording in your data file. Tile 1 in the picture is properly behind tile 5, not so much 4 or 6 and tile 5 is certainly not behind 6 nor is 4 behind 3.

    How to Draw X-COM.png
    Correction: Walls are drawn before ground/floors because they are behind the rest of the tile.

    Draw the entire tile from the bottom of the battlescape to the highest point currently visable before moving on to the next tile, with the possible exception of the floor/ground of the bottom layer. When rendering, the location of a 2x2/3x3 unit is based on one of it's tiles. The code in the link is about handling that.

    Objects which span multiple battlescape layers are always located in the lowest battlescape layer they occupy. Because units and content from lower layers may cover floors and walls from higher layers, we need to start at the bottom and draw all left walls, then again at the bottom all right walls then all grounds, all contents, all units, etc starting at the bottom.

    Things get much more complicated when dealing with a moving 2x2 or 3x3 unit and OXCs code only covers 2x2. The concept should be the same however.
     
    makus likes this.
  4. Yataka Shimaoka

    Yataka Shimaoka Active Member Tester Translator/Writer
    8/28

    Joined:
    May 3, 2017
    Messages:
    35
    Likes Received:
    8
    Best Answers:
    0
    I'm not good at this topic, but I think that falling tiles should be treated as a temporary item until it hits the ground. Might be not helpful suggestion though.
     
  5. darkestaxe

    darkestaxe Registered
    39/56

    Joined:
    Jul 17, 2014
    Messages:
    18
    Likes Received:
    7
    Best Answers:
    1
    This code appears in 4 places where a soldier is drawn, prior to redrawing parts of the .

    Code:
    // the part is 0 for small units, large units have parts 1,2 & 3 depending on the relative x/y position of this tile vs the actual unit position.
    int part = 0;
    part += tileWest->getPosition().x - westUnit->getPosition().x;
    part += (tileWest->getPosition().y - westUnit->getPosition().y)*2;
    tmpSurface = westUnit->getCache(&invalid, part);
    It appears to me that it's selecting all the unit's tiles, then uses this selection to make sure to render parts of walls and/or wall-objects prior to a unit that is moving into those tiles. So how many and which tiles and walls need to be rendered before rendering a 3x3x3 object moving diagonally up/downward? And what about when all the units are moving? In real-time mode? All of them! OXC Code isn't going to work here at all. Not only do we have 3x3x3 in 3 directions, we could have 13 of them in the same area moving simultaneously and of various sizes with 5 others also of various sizes and directions off in the corners somewhere that we can still see.

    We will need to draw starting at the most distant point from the camera and render toward it, working our way inward from the edges as we go, and in all three dimensions. After that we can still do Wall,Wall,Floor,FloorSprite,Object,Unit. This way stuff in front will be drawn in front every time. OXC is making up for drawing along an axis or something. So if 0,0,0 is in the bottom back of the bscape, then we go 0,0,0; 1,0,0; 0,1,0; 0,0,1; 2,0,0; 0,2,0; 0,0,2; 2,1,0; 1,2,0; 0,1,2; ... something like that. Ask a mathematician. I'm not a mathematician. I suck at calculus so bad I failed out of Algebra II! They asked me what 2+2 was and I said -5n!

    Anyway the important thing is to stop doing 0,0,0; 1,0,0; 2,0,0; 3,0,0; 0,1,0; 1,1,0; 2,1,0; 3,1,0; crap. That's how you do 3D(tm) and when you do 3D(tm) you have to cheat the corners and all the tanks have to be 2x2.
     
  6. LootHunter

    LootHunter Translator/Writer Translator/Writer
    3/28

    Joined:
    Apr 26, 2017
    Messages:
    5
    Likes Received:
    7
    Best Answers:
    0
    As someone familiar with math, I would say that proper order of coordinates to draw is not Z->Y->X but X+Y->Z->X-Y, starting from lowest value, to highest. That is objects with minimal X+Y would be drawn first as they are most far from us and objects with max X+Y would be drawn last on top of others as they are the closest.
     
    makus and The Reaver of Darkness like this.
  7. darkestaxe

    darkestaxe Registered
    39/56

    Joined:
    Jul 17, 2014
    Messages:
    18
    Likes Received:
    7
    Best Answers:
    1
    It might end up working better to draw an entire tile column at once, bottom to top of visible bscape.
     
  8. AceSpade

    AceSpade Member Programmer Tester Designer/Artist
    3/28

    Joined:
    Jul 21, 2017
    Messages:
    5
    Likes Received:
    3
    Best Answers:
    0
    I was attempting to find some factual information that may help to solve this problem. I want to share this link as it pertains to what this task is trying to accomplish and maybe you guys have not seen this yet? It contains formulas and detailed info on the rendering with explanations.
    https://en.m.wikipedia.org/wiki/Isometric_graphics_in_video_games_and_pixel_art
    Hope this helps if not sorry for wasting time!
    I was also pondering if moving objects perhaps take a higher precedence over other tiles..
     
    makus likes this.

Share This Page