Fake 3D maths problem

totebo · May 2016

How about a maths challenge this friday!

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:

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!

hgy29 · May 2016

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 ?

keszegh · 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.

totebo · May 2016

@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.

hgy29 · May 2016

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.

totebo · May 2016

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?

keszegh · 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!

keszegh · May 2016

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.

keszegh · 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)

hgy29 · May 2016

Quick try (with 2016.6 beta version):

Output:

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)

antix · May 2016

Or you could just sort your objects on the x axis since that seems to be where they are overlapping.

john26 · 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.

antix · May 2016

@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.

john26 · May 2016

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...

totebo · May 2016

@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.

simwhi · May 2016

@john26 Great video tutorial. I wouldn't cut anything from the video by the way.

keszegh · May 2016

@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.

totebo · May 2016

@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.

antix · 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

@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.

totebo · 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:

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.

totebo · May 2016

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.

antix · May 2016

Okay so will the faces of the objects (with the letters on) ever intersect?

antix · 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 · May 2016

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!

antix · May 2016

@totebo, if the faces never intersect then this will work just fine

antix · 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())

Howdy, Stranger!

Categories

In this Discussion

Top Posters

Fake 3D maths problem

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

Fake 3D maths problem

Comments