Days and days trying to figure out normalized device coordinates...

UberGoober · June 12, 2013, 6:04pm

Hi everybody–

So, at various many places in these forums people are trying to figure out how to get from coordinates in 3D space to plain old iPad-screen x and y. At none of them can I actually find a solution for it–at least not one I’ve been able to implement myself.

I’ve been at it for days. My head is sore from the wall I’ve been banging it on. Here’s the code I’ve built trying to understand all this, if somebody can help me make it work right, may a thousand blessings comfort thee. It should be pretty clear what I’m trying to do once you paste it into Codea and play with it a little.

--# Main
-- Analysis Lab
-- by UberGoober

-- I'm trying to figure out how to convert from 3D coordinates to 2D. This project puts a red square (I call it a box in the code, but it's really a square) at 0,0 then transforms it according to parameters dictated by parameter widgets. It then tries to figure out the absolute screen location of the square's upper right corner, according to two methods: one suggested in a thread begun by pat(shown as a green circle), one suggested in a thread by spaceMonkey(shown as a blue circle). It almost works for x and y transforms, but not camera and z transforms and angle and perspective--oy.


saveProjectInfo( "Description", "Trying to figure out $&?!* normalized device coordinates." )

function setup()
    setUpLocationTracking()
end

function draw()
    background(53, 30, 69, 255)
    applyTracking()
end
--# Position
function setUpLocationTracking()
    --a bunch of stuff to fiddle with and watch
    parameter.watch("allMatrix")
    parameter.watch("duoMatrix")
    parameter.watch("patCoords")
    parameter.watch("offset")
    parameter.integer("rotateBoxByAngle", 0, 360, 0)
    parameter.integer("fieldOfView", 1, 200, 45)
    parameter.integer("eyeAndLookX", -WIDTH, WIDTH, 0)
    parameter.integer("moveBoxByX", -2000, 2000, 0)
    parameter.integer("moveBoxByY", -2000, 2000, 0)
    parameter.integer("moveBoxByZ", -2000, 2000, 0)
    parameter.integer("rotateBoxX", 0, 1, 0)
    parameter.integer("rotateBoxY", 0, 1, 0)
    parameter.integer("rotateBoxZ", 0, 1, 1)
    patCoords = vec2()
    allMatrix = matrix()
    watchVector = vec2(20,20) --i.e. *normally* the corner of the red box
    --a bunch of functions to do what needs to be done, applied in the right order later:
    --draw best guess as to screen x, y of the red box's corner onto the screen.
    --this isnt really the best guess at this point
    function printInfoText()
        pushStyle()      
        textMode(CORNER)
        textWrapWidth(0)
        font("Futura-MediumItalic")
        fontSize(HEIGHT/35)
        local textIndentX, textIndentY = HEIGHT/15, HEIGHT-(HEIGHT/15)       
        infoText = string.format("best guess at screen location of red box UR corner: %d,%d",
            SMCoords.x, SMCoords.y)
        fill(21, 24, 34, 255)
        text(infoText,textIndentX+2, textIndentY-2)
        fill(248, 248, 248, 255)
        text(infoText,textIndentX, textIndentY)
        popStyle()
    end
    --draw the red box, 40 pixels square, centered over 0,0, (to be transformed by parameters)
    function drawTrackingBoxAt(x,y)
        pushStyle()
        strokeWidth(6)
        stroke(255, 7, 0, 255)
        rect(x-21,y-21,44,44)
        stroke(255, 255, 255, 255)
        fill(255, 7, 0, 255)
        rect(x-19,y-19,40,40)
        fill(255, 255, 255, 255)
        rect(x-4,y-4,10,10)
        popStyle()
    end  
    --apply the parameters set by the fiddlies   
    function applyParameters()
        perspective(fieldOfView,WIDTH/HEIGHT,0.1,0)
        camera(eyeAndLookX,0,1250,eyeAndLookX,0,0)
        translate(moveBoxByX,moveBoxByY,moveBoxByZ)
        rotate(rotateBoxByAngle,rotateBoxX,rotateBoxY,rotateBoxZ)
    end
    --undo all the fiddlies
    function cancelPerspective()
        viewMatrix(matrix())
        ortho()
    end
    --apply the conversion suggested in pat's thread:
    function patConversion(vector)
        local nV = vec3()
        local vectorX, vectorY, vectorZ = vector.x, vector.y, 0
        if not vector.z == nil then vectorZ = vector.z end
        duoMatrix = modelMatrix()*viewMatrix()
        nV.x = vectorX*duoMatrix[1] + vectorY*duoMatrix[5] + vectorZ*duoMatrix[9] + duoMatrix[13]
        nV.y = vectorX*duoMatrix[2] + vectorY*duoMatrix[6] + vectorZ*duoMatrix[10] + duoMatrix[14]
        nV.z = vectorX*duoMatrix[3] + vectorY*duoMatrix[7] + vectorZ*duoMatrix[11] + duoMatrix[15]
        return nV
    end
    --apply the conversion suggested by spaceMonkey:
    function spaceMonkeyConversion(vector)
        --trying to correct for projection matrix, which puts 0,0 at center screen and other goofy 
        --stuff, so to match it we gotta do like so:
        allMatrix = modelMatrix()*viewMatrix()*projectionMatrix()
        offset = vec3()
        if allMatrix[15] ~= 0 then
            offset = vec2((allMatrix[13]/allMatrix[16]+1)*WIDTH/2,
                (allMatrix[14]/allMatrix[16]+1)*HEIGHT/2)
        end
        offset.x = vector.x + offset.x
        offset.y = vector.y + offset.y
        return offset
    end
    --put it all together:
    function applyTracking()
        pushMatrix()
        applyParameters() --do what the fiddlies say
        drawTrackingBoxAt(0,0) --draw the box, under the influence of the fiddlies
        patCoords = patConversion(watchVector) --get the x,y predicted by pat's method
        SMCoords = spaceMonkeyConversion(watchVector) --get the x,y from spaceMonkey's method
        cancelPerspective() --undo all the fiddlies' stuff
        popMatrix()
        fill(0, 255, 38, 255)
        ellipse(patCoords.x,patCoords.y,21,21) --draw a green circle at the x,y from pat
        fill(0, 15, 255, 255)
        ellipse(SMCoords.x, SMCoords.y,21,21) --draw a blue circle at the x,y from spacemonkey
        printInfoText() --
    end    
end

Ignatz · June 12, 2013, 7:51pm

Why?

UberGoober · June 12, 2013, 9:16pm

Originally I wanted it so I could figure out how to touch things in 3D space, then I realized there were a lot of other things I could use it for, then finally I just wanted it because it tasked me. It tasked me and I will have it!

Ignatz · June 12, 2013, 10:27pm

When I was building my 3D tabletop I looked at this, because if you want to add point and shoot capability, you have to know what you’re pointing at. However, I didn’t find anything on the net, and other programmers seem to use internal memory maps, so I gave it up as too hard.

I have a book on the maths behind 3D graphics I can share, and the secret may be in there, but it is the kind of book only Andrew Stacey understands. :-??

DaDo · June 13, 2013, 12:08am

Are you trying a 3D projection to 2D?

http://en.wikipedia.org/wiki/3D_projection

I fooled arround in EXCEL with using this
http://www.gamasutra.com/view/feature/3563/microsoft_excel_revolutionary_3d_.php
as a starting point.

Ok Ok I was at work and bored very bored …

My newest project is understanding the source code of the Cargo Bot example while trying to write it in EXCEL with VBA :)) I will never finish it because sooner or later I will get bored with it …

Ignatz · June 13, 2013, 12:39am

@DaDo - Excel VBA? I’ve been writing code in that for many years, in business. It’s amazing what you can do with it. :)>-

UberGoober · June 13, 2013, 1:06am

@DaDo - a Wikipedia entry on the theory behind it is all well and good, but it doesn’t really help me fix my code. Do you have any pointers on that?

Andrew_Stacey · June 13, 2013, 2:31am

I’ll take a look at your code later on, but in the meantime you might find my post on this useful. I wrote it after reading, frankly, a load of confused nonsense about it on these forums.

http://loopspace.mathforge.org/discussion/13/matrices-in-codea

DaDo · June 13, 2013, 2:34am

@Ignatz: Yes VBA is very powerfull. I do a VBA at work.
@UberGoober: Did you find this already?
Prespective Projection 3d to 2d coordinates written in lua (form Marlbert):
http://www.leaguebot.net/forum/Upload/showthread.php?tid=1991

spacemonkey · June 13, 2013, 3:33am

I was going to point you at my bit of code. What my code that you used does is tell you the screen position of the origin of you transforms. You need the screen position of the vector after transforms.

Below I added a function that multiplies a vector by the transforms, and tweaked the spacemonkey function you had put in to use it. I think the behaviour might be what you wanted.

--# Main
-- Analysis Lab
-- by UberGoober

-- I'm trying to figure out how to convert from 3D coordinates to 2D. This project puts a red square (I call it a box in the code, but it's really a square) at 0,0 then transforms it according to parameters dictated by parameter widgets. It then tries to figure out the absolute screen location of the square's upper right corner, according to two methods: one suggested in a thread begun by pat(shown as a green circle), one suggested in a thread by spaceMonkey(shown as a blue circle). It almost works for x and y transforms, but not camera and z transforms and angle and perspective--oy.


saveProjectInfo( "Description", "Trying to figure out $&?!* normalized device coordinates." )

function setup()
    setUpLocationTracking()
end

function draw()
    background(53, 30, 69, 255)
    applyTracking()
end
--# Position
function setUpLocationTracking()
    --a bunch of stuff to fiddle with and watch
    parameter.watch("allMatrix")
    parameter.watch("duoMatrix")
    parameter.watch("patCoords")
    parameter.watch("offset")
    parameter.integer("rotateBoxByAngle", 0, 360, 0)
    parameter.integer("fieldOfView", 1, 200, 45)
    parameter.integer("eyeAndLookX", -WIDTH, WIDTH, 0)
    parameter.integer("moveBoxByX", -2000, 2000, 0)
    parameter.integer("moveBoxByY", -2000, 2000, 0)
    parameter.integer("moveBoxByZ", -2000, 2000, 0)
    parameter.integer("rotateBoxX", 0, 1, 0)
    parameter.integer("rotateBoxY", 0, 1, 0)
    parameter.integer("rotateBoxZ", 0, 1, 1)
    patCoords = vec2()
    allMatrix = matrix()
    watchVector = vec2(20,20) --i.e. *normally* the corner of the red box
    --a bunch of functions to do what needs to be done, applied in the right order later:
    --draw best guess as to screen x, y of the red box's corner onto the screen.
    --this isnt really the best guess at this point
    function printInfoText()
        pushStyle()      
        textMode(CORNER)
        textWrapWidth(0)
        font("Futura-MediumItalic")
        fontSize(HEIGHT/35)
        local textIndentX, textIndentY = HEIGHT/15, HEIGHT-(HEIGHT/15)       
        infoText = string.format("best guess at screen location of red box UR corner: %d,%d",
            SMCoords.x, SMCoords.y)
        fill(21, 24, 34, 255)
        text(infoText,textIndentX+2, textIndentY-2)
        fill(248, 248, 248, 255)
        text(infoText,textIndentX, textIndentY)
        popStyle()
    end
    --draw the red box, 40 pixels square, centered over 0,0, (to be transformed by parameters)
    function drawTrackingBoxAt(x,y)
        pushStyle()
        strokeWidth(6)
        stroke(255, 7, 0, 255)
        rect(x-21,y-21,44,44)
        stroke(255, 255, 255, 255)
        fill(255, 7, 0, 255)
        rect(x-19,y-19,40,40)
        fill(255, 255, 255, 255)
        rect(x-4,y-4,10,10)
        popStyle()
    end  
    --apply the parameters set by the fiddlies   
    function applyParameters()
        perspective(fieldOfView,WIDTH/HEIGHT,0.1,0)
        camera(eyeAndLookX,0,1250,eyeAndLookX,0,0)
        translate(moveBoxByX,moveBoxByY,moveBoxByZ)
        rotate(rotateBoxByAngle,rotateBoxX,rotateBoxY,rotateBoxZ)
    end
    --undo all the fiddlies
    function cancelPerspective()
        viewMatrix(matrix())
        ortho()
    end
    --apply the conversion suggested in pat's thread:
    function patConversion(vector)
        local nV = vec3()
        local vectorX, vectorY, vectorZ = vector.x, vector.y, 0
        if not vector.z == nil then vectorZ = vector.z end
        duoMatrix = modelMatrix()*viewMatrix()
        nV.x = vectorX*duoMatrix[1] + vectorY*duoMatrix[5] + vectorZ*duoMatrix[9] + duoMatrix[13]
        nV.y = vectorX*duoMatrix[2] + vectorY*duoMatrix[6] + vectorZ*duoMatrix[10] + duoMatrix[14]
        nV.z = vectorX*duoMatrix[3] + vectorY*duoMatrix[7] + vectorZ*duoMatrix[11] + duoMatrix[15]
        return nV
    end
    --apply the conversion suggested by spaceMonkey:
    function spaceMonkeyConversion(vector)
        --trying to correct for projection matrix, which puts 0,0 at center screen and other goofy 
        --stuff, so to match it we gotta do like so:
        allMatrix = modelMatrix()*viewMatrix()*projectionMatrix()
        offset = matrixByVector(allMatrix, vec4(vector.x,vector.y,vector.z,1.0))
        print(offset)
        offset.x = offset.x*WIDTH/2 + WIDTH/2
        offset.y = offset.y*HEIGHT/2 + HEIGHT/2
        --[[ --this returns the position of the origin after the transforms
        offset = vec3()
        if allMatrix[15] ~= 0 then
            offset = vec2((allMatrix[13]/allMatrix[16]+1)*WIDTH/2,
                (allMatrix[14]/allMatrix[16]+1)*HEIGHT/2)
        end
        offset.x = vector.x + offset.x
        offset.y = vector.y + offset.y]]
        return offset
    end
    --put it all together:
    function applyTracking()
        pushMatrix()
        applyParameters() --do what the fiddlies say
        drawTrackingBoxAt(0,0) --draw the box, under the influence of the fiddlies
        patCoords = patConversion(watchVector) --get the x,y predicted by pat's method
        SMCoords = spaceMonkeyConversion(watchVector) --get the x,y from spaceMonkey's method
        cancelPerspective() --undo all the fiddlies' stuff
        popMatrix()
        fill(0, 255, 38, 255)
        ellipse(patCoords.x,patCoords.y,21,21) --draw a green circle at the x,y from pat
        fill(0, 15, 255, 255)
        ellipse(SMCoords.x, SMCoords.y,21,21) --draw a blue circle at the x,y from spacemonkey
        printInfoText() --
    end    
end  

function matrixByVector(m, v)
    m=m:transpose()
    vx = vec4(m[1], m[2], m[3], m[4]):dot(v)
    vy = vec4(m[5], m[6], m[7], m[8]):dot(v)
    vz = vec4(m[9], m[10], m[11], m[12]):dot(v)
    vw = vec4(m[13], m[14], m[15], m[16]):dot(v)
--    return vec4(vx, vy, vz, vw)
    return vec4(vx/vw, vy/vw, vz/vw)
end

Andrew_Stacey · June 13, 2013, 4:24pm

Shouldn’t the check in @spacemonkey’s original code be if allMatrix[16] ~= 0? There seems little point in checking if allMatrix[15] is non-zero since it is the 16th term that you divide by. Also, matrixByVector is not as clean as it could be: given that you do the matrix multiplication by extracting the entries then there’s no need for the m = m:transpose() line - just swap the matrix entries. Lastly, you’re returning a vec4 but only specifying three terms.

If you read my post on matrices in Codea, you end up with the following code:

function staceyConversion(vector)
    local m = modelMatrix() * viewMatrix() * projectionMatrix() 
    m = m:translate(vector.x,vector.y,0)
    return vec2(WIDTH * (m[13]/m[16] + 1)/2, HEIGHT * (m[14]/m[16]+1)/2)
end

Functionally, this is the same as @spacemonkey’s revised code. In the absence of a native way to multiply a matrix by a vec4, neither one is more elegant than the other. Presumably one is faster than the other but I haven’t tested that.

(NB Mine is set up to take and return a vec2. There’s an obvious extension for a vec3.)

spacemonkey · June 13, 2013, 4:34pm

Nice… I threw together the matrixByVector from some stuff in one of your libraries, and to be honest the transpose was just me randomly kicking it until I saw a correct result come out. I really can’t grok the maths sufficiently… I shall consider your approach in my other project.

Andrew_Stacey · June 13, 2013, 4:51pm

@spacemonkey Well I’ll be … I didn’t recognise that at all.

If I had a time machine, I’d go back in time and force the openGL folks to implement matrices the same way as just about everyone else in the universe. Yes, it’s only a convention to have matrices act on the left but it’s an overwhelming one so I do not understand why they chose to have them act on the right. Anyway, the transpose converts action-on-right to action-on-left so the code you have is for ordinary matrix multiplication and the transpose is a fix to make it work well with the convention that openGL have chosen.

UberGoober · June 13, 2013, 8:20pm

Oh my non-denominational deity, this is freeking awesome! Guys, I’m so thankful! Days of frustration at an end == madly smiling emoji.