Quick Links: Download Gideros Studio | Gideros Documentation | Gideros Development Center | Gideros community chat | DONATE
Fake 3D maths problem — Gideros Forum

Fake 3D maths problem

totebototebo Member
edited May 2016 in General questions
How about a maths challenge this friday!

image

How would I go about z ordering these boxes? Currently I'm doing it by y position only, which works well for flatter objects, but not for chunky ones like above.

I have these parameters to play with for each object:

image

I'm trying to avoid recursively looping through all sprites, because I have a lot of them. That's why the y position solution was so good, until I started adding deep objects.

Tricky!
My Gideros games: www.totebo.com

Comments

  • hgy29hgy29 Maintainer
    Hmm I don't really understand :P But why faking 3D when you can do it for real, and let OpenGL figure out what should be drawn thanks to its Z buffer ?
  • keszeghkeszegh Member
    edited May 2016
    just a fast guess, is this good?

    order according to the bottom right coord, call this (x,y).

    and the order should be the following:
    B needs to be rendered earlier than A if and only if (x_A smaller than x_B) OR (y_A is higher than y_B).


    so basically if they are in a grid then start with the bottom right, go through e.g. the bottom row and then continue with the next row above it, again going from the right to the left. etc.
  • totebototebo Member
    @hgy29, I'm faking the 3D because the game is a pixel art with semi-isometric perspective. The above boxes were for illustrative purposes only. :) Although, maybe real 3D is an option even still?

    @keszegh, that could work. I would have to compare each game object with all other game objects each frame, though, which isn't really an option because I have to many of them. I could reduce the frequency I check it I suppose, but I was hoping for a one-variable silver bullet. :)
    My Gideros games: www.totebo.com
  • hgy29hgy29 Maintainer
    Actually it is an interesting question! Real 3D should work, all we need is a suitable projection. After a quick search, most people seems to use an orthographic projection (the default in gideros) and rotate the world in 3D: 45° around Y axis, and ~30° around X axis.

    It won't look like your pictures though, but I am pretty sure we can craft a projection matrix that will. After all the transform should be something like (X,Y,Z) -> (X-Z*f,Y-Z*f,Z), with f being some depth factor of your choice, sqrt(2) basically.

    Upcoming Viewport enhencements will allow that.
  • totebototebo Member
    Well, @hgy29, you just blew my mind. Please let a mere mortal in on where to even begin implementing a 3D layer such as this? Also: Would it be efficient, CPU wise?
    My Gideros games: www.totebo.com
  • keszeghkeszegh Member
    edited May 2016
    @totebo, i don't think it is more complicated than one coordinate. you anyway need to sort the sprites before rendering or in case you have many static objects then at each frame you have to remove the (probably fewer) moving objects from your order and readd them one by one.
    and irrespective to how the 'smaller' is defined, ordering takes nlogn time for n objects or adding an object into an order is logn time per object. these methods are completely oblivious to the definition of 'smaller' so you can just make a comparison function that says e.g. that

    [EDIT]this comparison function is not correct[END of EDIT]
    function isBefore(a,b)
       if a.x>b.x then return true 
       else 
       if a.y>b.y return true end   
       end
       return false
    end
    and use it when you are ordering your table of toberendered elements.
    for sorting a table t according to this order you can use the lua function
    table.sort(t, isBefore)
    of course remember that x and y should be the bottomright coords!
  • keszeghkeszegh Member
    now i wonder that this is just a partial order of the elements so ordering according to this might cause problems indeed. let me think.
  • keszeghkeszegh Member
    edited May 2016
    so i was wrong, the comparison function needs to be more complicated, considering sometimes other coordinates of the object too.
    for example if the bottomright corners are positioned as in
    __x
    x__
    of two such objects, then it still depends on their height which one has to be rendered before the other.
    however, if you get the comparison function right, then the rest applies.

    (also you never said how the 'plane' of the elements is positioned, parallel to the screen or going into z coord (like an isometric tile-map) - i guess parallel to the screen, at least i thought it that way)

    Likes: totebo

    +1 -1 (+1 / -0 )Share on Facebook
  • hgy29hgy29 Maintainer
    Quick try (with 2016.6 beta version):

    Output:
    image

    Code:
     
    local function face(color,rx,ry)
    	c=Sprite.new()
    	s=Shape.new()
    	s:setFillStyle(Shape.SOLID, color,1)
    	s:beginPath()
    	s:moveTo(-1,-1)
    	s:lineTo(-1,1)
    	s:lineTo(1,1)
    	s:lineTo(1,-1)
    	s:lineTo(-1,-1)
    	s:endPath()
     
    	--[[mesh:setVertexArray(-1,-1,-1,
    	                    -1, 1,-1,
    						 1, 1,-1,
    						 1,-1,-1)
    	mesh:setColorArray(color,0.5,color,1,color,0.5,color,1)
    	mesh:setIndexArray(1,2,3,1,3,4)]]
    	s:setZ(-1)
    	c:addChild(s)
    	c:setRotationX(rx)
    	c:setRotationY(ry)
    	return c;
    end
     
    local function buildCube()
    local cube=Mesh.new(true)
    cube:addChild(face(0xFF0000,0,0))
    cube:addChild(face(0xFFFF00,90,0))
    cube:addChild(face(0xFF00FF,-90,0))
    cube:addChild(face(0x00FF00,180,0))
    cube:addChild(face(0x00FFFF,0,90))
    cube:addChild(face(0x0000FF,0,-90))
    return cube
    end
     
    base=Sprite.new()
     
    cube=buildCube()
    cube:setScale(50,50,50)
    cube:setPosition(200,200,-50) 
    base:addChild(cube)
     
    cube=buildCube()
    cube:setScale(50,50,50)
    cube:setPosition(350,200,-50) 
    base:addChild(cube)
     
    --[[ transform matrix iso
     x=x-z*0.7
     y=y-z*0.7
     z=z/1000 
     
     1 0 0 0
     0 1 0 0
     -0.7 -0.7 0.001 0
     0 0 0 1
     ]]
     
    local m=Matrix.new()
    local alpha=-0.7
    local zmax=1000
    m:setMatrix(1,0,0,0, 0,1,0,0,-alpha,-alpha,1/zmax,0, 0,0,0,1)
    base:setMatrix(m)
    stage:addChild(base)
    testIso.png
    444 x 253 - 4K
    +1 -1 (+4 / -0 )Share on Facebook
  • antixantix Member
    Or you could just sort your objects on the x axis since that seems to be where they are overlapping.
  • john26john26 Maintainer
    edited May 2016
    @totebo, the best place to start is my new 3D graphics tutorial:

    http://giderosmobile.com/guide

    (3D graphics section)

    For orthographic display you want to set the frustum like this

    application:configureFrustum(0,200)

    for example, where 200 is the distance to the near and far cut planes in pixels (basically make this big enough to encompass your 3D scene)

    And, yes, it will be very CPU efficient. OpenGL will do all the z-ordering for you, in fact it will all happen on the GPU which is highly optimised for this task.
    +1 -1 (+3 / -0 )Share on Facebook
  • antixantix Member
    @john26 Wow, thats a big tutorial. I will watch it soon but I feel that I will get sidetracked with 3D if I do :)

    I think a small class that can render a simple 3D mesh with textures would be really cool. It could be used for games where you are using 2D but want to have 3D items in inventory screens and stuff.
  • john26john26 Maintainer
    Yes, sorry I went on a bit! Perhaps I should cut the beginning part where I show people how to start a new project. If you're doing 3D you already know that I guess...
  • totebototebo Member
    @john26, thanks. Complicated stuff! I hope to have time to fully understand 3D in Gideros one day. For this project, it feels like I'm taking a simple 2D game to 3D to achieve a small part of the game. I bet I'll get sufficiently annoyed by other solutions and end up doing it in 3D in the end, though.

    @antix, x axis won't work regrettably. See illustration below. I'm trying to get a combination of x and y going, but so far no luck. image
    My Gideros games: www.totebo.com
  • simwhisimwhi Member
    @john26 Great video tutorial. I wouldn't cut anything from the video by the way.

    Likes: john26

    +1 -1 (+1 / -0 )Share on Facebook
  • keszeghkeszegh Member
    @totebo, i thought your objects are arranged on a plane parallel to one of their faces (in 3d) - like the plane parallel to the screen. however, in your last example they are in a 'comletely 3d' position. if you need objects positioned like this, then it's better to use the 3d engine, it's not worth to recreate on your own how 3d rendering ordering works.
  • totebototebo Member
    @keszegh, the illustration above is still just isometric 2D, and an issue which assume is very common in those type of games. I'll ping back here if I solve it.
    My Gideros games: www.totebo.com
  • antixantix Member
    edited May 2016
    @totebo, ahh I thought you only needed to sort on the x axis. So why do your shapes overlap? Do they not collide?

    Here is a very interesting article about "Drawing isometric boxes in the correct order" that you might find useful.. http://shaunlebron.github.io/IsometricBlocks/. Actually I bookmarked it because it's quite fantastic :D

    @john26 I agree with simwhi, don't cut anything. If you feel its too long you could put in one of those note things where you can say "skip to 10:52" if you already know how to start a new project or something.
  • totebototebo Member
    edited May 2016
    Hey @antix, thanks for the link, could be the next thing to try.

    I seem to be stuck with Lua's sort function currently. Here is an illustration of the theoretical solution I've come up with to solve the problem:

    image

    This is an example of the table I need to sort (z_objects).
    table
    	[1]	table
    	[1]	[x2]	number	1816.6666666667
    	[1]	[y2]	number	438
    	[1]	[y1]	number	423
    	[1]	[x1]	number	1761.6666666667
    	[2]	table
    	[2]	[x2]	number	1454.6666666667
    	[2]	[y2]	number	62
    	[2]	[y1]	number	-58
    	[2]	[x1]	number	1084.6666666667
    	[3]	table
    	[3]	[x2]	number	44
    	[3]	[y2]	number	153
    	[3]	[y1]	number	143
    	[3]	[x1]	number	4
    I'm using this function to sort the data:
    local function sortZ(a,b)
    	return a.x2 < b.x2 or a.y2 > b.y1
    end
    table.sort( z_objects, sortZ )
    This produces one of these errors (which one seems to be random):
    GameWorld.lua:965: attempt to index local 'a' (a nil value)
    GameWorld.lua:965: attempt to index local 'b' (a nil value)
    GameWorld.lua:967: invalid order function for sorting
    Can someone see an obvious problem here? I'm guessing I'm not using table.sort in the right way.
    Artboard 1.png
    529 x 385 - 16K
    My Gideros games: www.totebo.com
  • totebototebo Member
    Blimey, talking about trickier than I thought. I believe the earlier sort function fails because I'm trying to do iterative sorting. I have since tried to do this "manually" in nested for loops, but it appears beyond me to take all scenarios into account.

    I also tried the isometric link above, which doesn't work, I think, because my objects are skewed, and not straight up isometric.

    Taking a break from this, but do let us know if you feel you have an idea that can help. :)
    My Gideros games: www.totebo.com
  • antixantix Member
    edited May 2016
    Okay so will the faces of the objects (with the letters on) ever intersect?
  • antixantix Member
    edited May 2016
    Well if your faces will NOT intersect then here is an example that I threw together this afternoon which seems to work. It's a little messy but you should be able to get the idea.

    In the example there are 6 boxes that move about the screen. Bump collision bounces them off eachother and the screen edges. They get sorted and drawn in the correct order in the sortThings() function of the Game class.

    I hope it's of some use to you @totebo and maybe others too :)
    math.randomseed(os.time()) for i = 1, 4 do math.random() end
    application:setBackgroundColor(0xffffff)
     
    Thing = Core.class(Bitmap)
    function Thing:init(texture, x, y, w, h, d, name)
      self.name = name
      self.width = w
      self.height = h
      self.depth = d
     
      self:moveTo(x, y)
     
      local speed = math.random(15, 60) -- Each thing moves at a random speed in a random direction
      local angle = math.random(0, 360)
      self.velocity = {x = speed * math.cos(math.rad(angle - 90)), y = speed * math.sin(math.rad(angle - 90))}
      self.isShape = true
    end
     
    function Thing:moveTo(x, y) -- Move a thing to the desired location
      self.x2 = x + self.depth
      self.y2 = y + self.depth
      self:setPosition(x, y)
    end
     
    Game = Core.class(Sprite)
    function Game:init()
      local WIDTH, HEIGHT = application:getContentWidth(), application:getContentHeight()
     
      self.thingSprites = Sprite.new() -- container sprite to hold our things
      self:addChild(self.thingSprites)
     
      self.things = {} -- table of all things in the world
     
      -- Create a bunch of things
      table.insert(self.things, Thing.new(Texture.new("images/redthing.png", false), 64, 64, 48, 40, 24, "red") )
      table.insert(self.things, Thing.new(Texture.new("images/greenthing.png", false), 200, 64, 48, 40, 24, "green") )
      table.insert(self.things, Thing.new(Texture.new("images/bluething.png", false), 64, 380, 48, 40, 24, "blue") )
      table.insert(self.things, Thing.new(Texture.new("images/purplething.png", false), 200, 380, 48, 40, 24, "purple") )
      table.insert(self.things, Thing.new(Texture.new("images/yellowthing.png", false), 64, 200, 48, 40, 24, "yellow") )
      table.insert(self.things, Thing.new(Texture.new("images/greything.png", false), 200, 200, 48, 40, 24, "grey") )
     
      self.bump = require("bump").newWorld() -- Create collision world
     
      -- Create walls so things can't escape the display
      local walls = { {000, 000, 320, 010, isWall = true}, {000, 470, 320, 010, isWall = true,}, {000, 000, 010, 480, isWall = true,}, {310, 010, 010, 480, isWall = true,} }
      for i = 1, #walls do self.bump:add(walls[i], walls[i][1], walls[i][2], walls[i][3], walls[i][4]) end
     
     -- Add things to collision world so they can collide
      local things = self.things
      for i = 1, #things do
        local thing = things[i]
        self.bump:add(thing, thing.x2, thing.y2, thing.width, thing.height) -- Each thing can collide with other things (and walls)
      end
     
      self.currentTimer = os.timer()
      self:addEventListener(Event.ENTER_FRAME, self.update, self)
    end
     
    -- This is the main function that does the sorting magic (possibly)
    function Game:sortThings()
      local things = self.things
      local sorted = {}
      table.insert(sorted, things[1]) -- Always just insert the first one
     
     -- Return true if a is behind b
      local function isBehind(a, b)
        if a.x2 + a.y2 < b.x2 + b.y2 then -- Magic
          return true
        end
        return false
      end
     
     -- Insert thing into table at correct position
      local function insertThing(a)
        for j = 1, #sorted do
          local b = sorted[j]
          if isBehind(a, b) then
            table.insert(sorted, j, a)
            return
          end
        end
        table.insert(sorted, a) -- Must be at the top
      end
     
     -- Sort the things
      for i = 2, #things do
        local thing = things[i]
        insertThing(thing)
      end
     
      -- Remove all child sprites from display group
      local group = self.thingSprites
      local nc = group:getNumChildren()
      if nc > 0 then
        for i = nc, 1, -1 do
          group:removeChildAt(i)
        end
      end
     
     -- Add sorted sprites to display group
      for i = #sorted, 1, -1 do
        group:addChild(sorted[i])
      end
    end
     
    -- Update a things position and bounce it off anything it collides with
     function Game:updateThing(thing, dt)
      local v = thing.velocity
      thing.x2 = thing.x2 + v.x * dt -- Set desired x, y position
      thing.y2 = thing.y2 + v.y * dt
     
      local filter = function(item, other) -- Collision filter
        if other.isWall or other.isShape then return "bounce" end
      end
     
      local actualX, actualY, cols, len = self.bump:move(thing, thing.x2, thing.y2, filter)
      thing:moveTo(actualX - thing.depth, actualY - thing.depth)
      for i=1,len do
        local col = cols[1]
        local bounciness = 1
        local nx, ny = col.normal.x, col.normal.y
        local vx, vy = v.x, v.y
        if (nx < 0 and vx > 0) or (nx > 0 and vx < 0) then
          vx = -vx * bounciness
        end
        if (ny < 0 and vy > 0) or (ny > 0 and vy < 0) then
          vy = -vy * bounciness
        end
        v.x, v.y = vx, vy
      end
    end
     
    -- Main loop
    function Game:update(e)
      local timer = os.timer()
      local dt = timer - self.currentTimer
      self.currentTimer = timer
     
      local things = self.things -- Update all of our things
      for i = 1, #things do
        local thing = things[i]
        self:updateThing(thing, dt)
      end
     
      self:sortThings() -- Sort them to draw in the right order
    end
     
    stage:addChild(Game.new())
    @totebo iso things.png
    336 x 540 - 9K
    zip
    zip
    @totebo IsoThings.zip
    17K

    Likes: totebo

    +1 -1 (+1 / -0 )Share on Facebook
  • totebototebo Member
    Amazin. This intrigues me no end:
    if a.x2 + a.y2 < b.x2 + b.y2 then -- Magic
    The faces will never intersect in my case, so this may just do it. So look forward to trying it out. Thanks!

    Likes: antix

    My Gideros games: www.totebo.com
    +1 -1 (+1 / -0 )Share on Facebook
  • antixantix Member
    @totebo, if the faces never intersect then this will work just fine :)
  • antixantix Member
    edited May 2016
    I wasn't totally happy with the messiness of my example above so I rewrote it to be smaller and more easy to understand.

    This better example just uses a filter to sort the things table which makes things a lot tidier. It also does away with collision stuff and just ensures that no things overlap when they are created.
    math.randomseed(os.time()) for i = 1, 4 do math.random() end
    application:setBackgroundColor(0xffffff)
     
    Game = Core.class(Sprite)
    function Game:init()
      local WIDTH, HEIGHT = application:getContentWidth(), application:getContentHeight()
     
      local thingImage = Texture.new("thing.png", false)
     
      local thingSprites = Sprite.new() -- container sprite to hold our things
      self:addChild(thingSprites)
     
      local THINGWIDTH, THINGHEIGHT, MAXTHINGS, MAXATTEMPTS = 48, 40, 32, 500
     
      -- Create a table to store things and insert a thing at a random x, y position
      local things = {}
      table.insert(things, {x = math.random(0, WIDTH - THINGWIDTH), y = math.random(0, THINGHEIGHT), width = THINGWIDTH, height = THINGHEIGHT})
     
      -- Create a new thing at a random x, y position and return true and add it to the thing table if the new thing does not intersect (overlap) any other existing thing
      local function newThing()
     
        -- Return true of rectangles intersect (overlap)
        local function rectIntersectsRect(r1, r2)
          if r1.x + r1.width >= r2.x and r1.x <= r2.x + r2.width and r1.y + r1.height >= r2.y and r1.y <= r2.y + r2.height then
            return true
          else
            return false
          end
        end
     
        local newThing = {x = math.random(0, WIDTH - THINGWIDTH), y = math.random(0, HEIGHT - THINGHEIGHT), width = THINGWIDTH, height = THINGHEIGHT}
        for i = 1, #things do
          local existingThing = things[i]
          if rectIntersectsRect(newThing, existingThing) then
            return false
          end
        end
        table.insert(things, newThing)
        return true
      end
     
      -- Create our things
      local done, attempts = false, 0
      repeat
        newThing()
        attempts = attempts + 1
        if #things == MAXTHINGS or attempts > MAXATTEMPTS then
          done = true
        end
      until done
     
     -- compare ISO depth of 2 things
      local function filter(a, b)
        if a.x + a.y < b.x + b.y then -- Magic
          return false
        end
        return true
      end
     
      table.sort(things, filter) -- Sort things into correct depth order
     
      -- Add things to display group
      for i = 1, #things do
        local thing = things[i]
        local bitmap = Bitmap.new(thingImage)
        bitmap:setPosition(thing.x, thing.y)
        bitmap:setColorTransform(math.random(), math.random(), math.random())
        thingSprites:addChild(bitmap)
      end
     
    end
     
    stage:addChild(Game.new())
    @totebo iso things.png
    336 x 540 - 20K
    zip
    zip
    @totebo IsoThings.zip
    3K

    Likes: totebo, pie, john26

    +1 -1 (+3 / -0 )Share on Facebook
Sign In or Register to comment.