Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

3D rendering on Codea

edited March 2012 in General Posts: 196

Hey there,

First time here, I first want to thank you guys for making such a nice app ;)

I just finished building my first Codea app, I wanted to make a little 3D renderer for fun, but I wasn't expecting Codea to be so fast.

Edit: Think i'm nearly done with optimizing the code...Now hitting 36 fps in quality 2 on iPad 1 (that's 4096 polygons or 12 288 vertices!)

update: Textures are up and running:

http://i42.tinypic.com/b9ghw5.png

http://i41.tinypic.com/90vchz.png

http://i44.tinypic.com/1zbdyxk.png

Video on shading:

Old video:

Source: http://pastebin.com/i7P5wLmC (updated to shading)

Cheers,
Xavier

Tagged:
«1

Comments

  • Wow, that's just awesome!

  • Posts: 2,820

    Tells you about Codea. That's awsome. Code?

  • Posts: 196

    Hey there and thanks for the comments,

    Regarding the code, I'm new to lua, so I'm sure people are going to mock me hehe :P

    Seriously though, I want to clean it up and comment it before I share it. I'll try to optimize it some more on my own too, but forums could actually be a pretty nice place for me to get insight on how to make it run faster...

    Cheers,

    Xavier

  • Posts: 2,820

    I accept messy coders... You won't be mocked... I promise.

  • SimeonSimeon Admin Mod
    Posts: 4,459

    Xavier that's incredible. Do you mind if we show it off as a news item on the Codea main screen?

  • Posts: 196

    oh absolutely not, that would actually make me fell pretty good about myself heh :P
    It's 5 in the morning here in france, i'll clean up the code tomorrow and post it before this WE Zoyt )

    Cheers,

    Xavier

  • SimeonSimeon Admin Mod
    Posts: 4,459

    No problem @Xavier — I just meant the video, by the way.

  • beebee
    Posts: 377

    This is awesome! You guys keep surprising me with what you've done with Codea. Try to remove the text. It might increase the frame rate a bit. :)

  • Posts: 2,160

    I want to see this code! You have far more vertices than I managed in my 3D viewer before I got a noticeable lag in the rendering - I want to see where the saving is.

  • Posts: 273

    Welcome to the community Xavier! :)

  • Posts: 159

    @Xavier - that's incredible! :)

    Do you have any link / reference to the Populous sphere trick from Glenn Corpes that you mention in the video? I had a quick Google but couldn't find anything.

  • Posts: 196

    @Simeon - That's what I figured, code section was aimed at Zoyt ;)

    @Andrew_Stacey - I'm nearly done cleaning up code, i'll post an ugly version of it in a few minutes, hope you guys will help me improve it !

    @frosty - here is the link to the post in question: http://glenncorpes.blogspot.com/2011/07/topia-landscape-finger-painting-and.html
    His blog is pretty nice :)

    Cheers,

    Xavier

  • edited February 2012 Posts: 196

    Ok, here is the code.
    Note that I am very new to lua, so don't make fun :P I could really use all the help to clean it up and optimize it.

    edit: code now on top comment

    Feel free to ask if you have any questions,

    Cheers,

    Xavier

  • Posts: 146

    This is a very nice piece of code, very cool idea :)

  • edited February 2012 Posts: 72

    For the first time I saw the video, I thought you might have a lot of code. But, when I saw the code, it is not too long. It means that the Codea is great!


    @Xavier Thank you for your fantastic code.


    I am thinking that to render the simple objects such as a cube might not be too hard. However, I have to learn the 3D modelling a lot.

  • edited February 2012 Posts: 196

    @sanit

    yeah, the principle is very easy, hence the code being pretty lightweight (Codea is indeed great though :))

    All you need is a model (i generate a heightmap using perlin noise), which is nothing more than a bunch of vertices (points in 3D space).

    However, if you want to your object to display properly, you need to use a list of indices to connect your points.
    In the program, I use an array of triangles, and each contain 3 indices

    -- basic structure
    vertices[1] = vec3( 0, 0, 10)
    vertices[2] = vec3(10, 10, 10)
    vertices[3] = vec3( 0, 10, 10)
    
    polygon[1] = vec3(1, 2, 3)
    

    vertices[ faces[1].x ].z would then give me the z value of the first point in the triangle.

    To render it on screen, you need to go through all the polygons and project each vertex onto the 2D screen.
    The basic formula for that is x2D = x3D/z3D and y2D = y3D/z3D

    @Andrew_Stacey
    The only real optimization I do is "cache" the projected points. This way, if the triangles are connected, i don't have to recalculate the projection of the duplicated points.
    That was a huge boost in rendering speed, but note that it is ideal in my case since i'm using a grid,

    Cheers,

    Xavier

  • Posts: 2,160

    Initial comments on looking at the code:

    1. I see you're projecting from the origin onto the place z=1. That probably produces the fasted algorithm (computationally) for stereographic projection (though if you later add other things like transformations it can get complicated).

    2. You're removing back-facing triangles. This looks a little strange in wire-frame mode. I doubt that this produces a lot of saving in rendering the mesh as that's pretty fast so the main saving here is that you don't have to sort these faces. I'd test to see if this is an actual saving or not - the test to see whether or not to remove a face might actually take longer than sorting the faces.

    3. Your formula for the distance of a face can be simplified. As you're only using this for comparing faces, you don't need to divide by 3: x > y if and only if 3x > 3y, and you don't need to square root the sum of squares: if x and y are positive then x > y if and only if x^2 > y^2.

    4. I wonder if it is possible to circumvent the sorting. Once you've computed the f.dist, you know already where it fits into the scheme so simply insert it in the right place.

    5. You're resetting the mesh for every triangle. Again, you'd need to test this to see if this was actually faster, but I would have set up a table of all the vertices (arranged into triangles) and drawn the mesh all in one go. Indeed, I expected to see a huge saving between using the filled shape (ie using the mesh) and the wireframe (not using the mesh) but I don't, so maybe if you draw the mesh once you'll get a faster rendering.

    6. On that, in wireframe mode then you could use the mesh. It might not look as good, but if you use a texture with three points and lines between them then this would render the wireframe using a mesh. That might be faster.

    7. You could use table.insert(obj,f) instead of obj[poly] = f poly = poly + 1 and then drop poly altogether. Similarly, f.visible seems to do nothing: a face is visible if and only if it is in the obj table and it is drawn if and only if it is in the obj array, and the obj array is reinitialised every draw.

    All of these are just suggestions of where there might be savings. I'm no programmer and don't know which actually save time or not, but are things that could be worth investigating.

  • Posts: 2,160

    One more thing: in lua, arrays (tables) start at 1, not 0.

  • Posts: 2,160

    Point 5 is a big saving. With quality at 2 then I got a FPS of about 8.8 with your original code (all other settings as defaults). Once I'd implemented point 5, I got up to 13.5. That's half as much again.

  • Posts: 196

    @Andrew_Stacey

    Thanks for the help Andrew :)

    For point 1, it is indeed the fastest projection possible I believe, you can change the camera position for a negligible fps loss, but not the direction you look at, if you see what i mean.

    For point 2, after implementing point 5, it is only an fps gain when a LOT of triangles are culled, so I removed it.

    For point 3, totally, i mentionned in the comment it could be simplified, wanted people to "see" i was doing the distance formula :)

    for point 4, i've been toying with the idea after implementing point 5.
    After optimizing the code structure, i hit the 60fps cap at quality 3, and 25fps at quality 2, which is incredible, but I cannot get the depth sorting to work.

    here is some pseudocode (tris is my list of vec2):

    -- without depth sorting i do this for each poly
    for each polygon(a,b,c)
    ins(tris, a)
    ins(tris, b)
    ins(tris, c)
    end
    p.vertices = tris
    p:draw()
    

    Now, if i want to add depth sorting, i could do something like that (I need to shift the insert order so that final result is correct, right ?):

    for each polygon(a,b,c)
    ins(tris, depth, c)
    ins(tris, depth, b)
    ins(tris, depth, a)
    end
    p.vertices = tris
    p:draw()
    

    That obviously doesn't work since p.vertices needs to be sorted with no holes (has to be 1, 2, 3, 4, etc....can't be 1, 4, 25, 97.
    If you have any idea to normalize the depth value, or a way to circumvent this, i'd be glad to hear it.
    For now, i'm back to using table.sort, so down to around 35-40fps in quality 3

    For point 5, indeed, huge fps boost thanks a lot ! I had no idea you could have more than three points in a "mesh()" (had tried table.insert with p.vertices but it didn't work). When you said you implemented it, i realised I had to work on a table then do p.vertices = table. Huge fps boost thanks :)

    for point 6, i had thought of using textures to simulate wireframe, but I didn't know you apply an image to a mesh, thought it had to come from an external file and I didn't want to "hack" codea. I plan to try and implement at a later time !

    for point 7, i'm now using table.insert everywhere (i changed it to a "local ins = table.insert", seem to gain 1 fps. f.visible is something I forgot to update. f.visible doesn't actually exist anymore,was old code.
    But in my draw loop, i had a check with "if f then", that way if no faces are visible at all (all culled), program wouldn't crash. It's now completely gone though, since i remove backface culling

    Thanks for the help, i'll update the posted code soon.

    Ok, so...anger time :P
    First, with my original code, in quality 2, i'm at 5.9fps, then 11fps with point 5 implemented.
    How do you get 8.8fps, then 13.5fps with point 5 implemented ? Why is my iPad slower ? hate that, heh :)

  • Posts: 176

    iPad 1 vs. iPad 2?

  • Posts: 2,160

    I'm on an iPad2, maybe that's the rest.

    One minor thing. I found the fps almost impossible to read. If you use textMode(CORNER) then it effectively left-justifies the text so it doesn't jump around so much (need to adjust the coordinates). I also got it to display a more averaged fps by saving the last 100 deltatimes and getting an average from them.

    Okay, so to the sort. I've been experimenting off-and-on and have nothing definite yet. I've been looking at binary trees, but as yet no saving. It is quicker to sort a table of pure numbers than of objects, but I'm not sure how to exploit that. Also, the vertices will be in roughly the same order each time so a merge sort maybe be quicker than quicksort - I guess that table.sort is a quick sort - but then you have to remember the order from frame to frame.

  • edited February 2012 Posts: 196

    hey, ok i think i found a reasonable way.
    I'm keeping my last optimization, where i was getting 60fps in quality 3
    what I do is the

    -- for all triangles
    ins(tris, depth, a)
    ins(tris, depth, b)
    ins(tris, depth, c)
    
    -- remove the "holes" in tris
    local tri = {}
    for k, v in pairs(tris) do
      tri = v
    end
    

    I got a graphical glitch somewhere, some polygons are messed up, but it's running at 50/55 fps

    edit: nm... fixing all glitches and adding color brings me to the same fps approx as before... /cry

  • Posts: 2,160

    Just tried it via linked lists and got a stackoverflow!

  • edited February 2012 Posts: 196

    thanks for heads up about being able to make a whole mesh with all the vertices Andrew, you were great help :)

    Along with a few other tweaks, I now have it running at 40fps in quality 3 on iPad 1, it's not 60 but it's still very good.
    Turning off z-ordering after at least one render pass gives you that pretty boost without losing too much quality :P

    Code is updated. I'm sure i can still optimize it, going back to it :)

    I would have imagined iPad2 to be even faster ^^

  • Posts: 196

    Greetings,

    I've been looking for a way to handle texture parameters such as wrapping (and filtering), but I cannot find any info, so my guess is that it's not implemented, correct ?

    If it's not possible in Codea, I was wondering if there was someone that could help me with "fixing" my problem :)

    Let's say, when you want to map your textures to a terrain built from a grid, you do something like this:

    -- texture mapping
    for z=0, mapSize, step do
       for x=0, mapSize, step do
    
          i = (x + z * (mapSize+step)/step)/step + 1
    
          color_texCoords[i] = vec2( x/mapSize, y/mapSize )
          detail_texCoords[i] = vec2( x/step, y/step)
    
       end
    end
    

    Here I'm setting up the UV coordinates of two textures to be applied to the terrain:

    1. The color map. It will be applied over the whole terrain using the UV formula for color_texCoords (like a big texture applied to the whole terrain).
      This works fine with Codea because the resulting UV goes from 0.0 to 1.0, within the texture range.

    2. The detail map. This is applied to every pair of triangles to give the impression of a more detailed texture up close.
      My problem is that it won't work with Codea because it's impossible (or at least I can't find the way) to set the texture parameters to "repeat".
      The resulting UV would go from 0.0 to 1.0 on the first tile, but then from 1.0 to 2.0 on the next and so on. Without "repeat", this points to an area outside the texture and results in nothing being applied to the quad

    My mind is not working right now and I cannot find a way to successfully make it repeat itself for every tile.
    Anyone have an idea ?

    Cheers,

    Xavier

  • BortelsBortels Mod
    Posts: 1,557

    @Andrew says "I'm no programmer..."

    Feh. I'm no mathematician, and I was a math major for two years. You are more a programmer than I am a mathematician.

    To be fair - being a programmer is easier. :-)

  • SimeonSimeon Admin Mod
    Posts: 4,459

    @Xavier texture parameters are implicitly set as follows:

    Texture filtering: use smooth() and noSmooth(). smooth = bilinear, noSmooth = nearest neighbour.

    Texture wrapping: all textures are clamped to edge UNLESS the texture size is a power-of-two, in which case we use repeat. The reason for this is because non-power-of-two textures can only user clamp-to-edge on PowerVR hardware.

    So if you want to repeat your texture, make sure it's rendered into a power of two image (e.g. 512x512).

  • Posts: 196

    @simeon

    Oh thanks a lot for the explanation, I had no idea of that limitation and was using a random picture from the library

  • beebee
    Posts: 377

    @bortels: I'm no mathematician. Though I'm ('was' to be exact) a programmer, I'm no visual programmer. Both you and @Andrew, also some other as well, have impressed me by what you've done using Codea. Compare to you and @Andrew, I'm almost nothing. :)

  • beebee
    Posts: 377

    @bortels: I'm no mathematician. Though I'm ('was' to be exact) a programmer, I'm no visual programmer. Both you and @Andrew, also some other as well, have impressed me by what you've done using Codea. Compare to you and @Andrew, I'm almost nothing. :)

  • edited February 2012 Posts: 72

    @bee Everyone has his/her way. You might be good at solving. I might be good at thinking. But we all share. Thus, I might borrow what you are excellent.

  • Posts: 196

    hahaha....hahahaahaha....HAHAHAAHAHAHAHAHAHA

    60fps in quality 3 at last !!!!! :D
    The final optimization process was extremly complicated and hard to implement, but i'll try and detail it here:

    1. use brain
    2. Decide I can get easy fps increase by only calling the z ordering once every few frames
    3. profit

    hahahah....HAHAHAHAAHAH...... I should slap myself for not thinking about it earlier :(

    I'll update the code in a couple of minutes, also using wireframe textures now. It's not ideal, but it does the job.

    Going to work on dynamic textures now, then shadowing (by coloring the texture), this should be fun

    Cheers,

    Xavier

  • Posts: 2,160

    Excellent. I've been playing with different sort methods, but none beat quicksort. However, I suspect that it's becuase I'm not implementing them optimally, and quicksort is builtin. Maybe if there were more hardcoded sorts there'd be more of a level playing field.

    When I've seen your solution used before, then the system switches to wireframe when the shape is being moved, only switching back when it's worth the computational time to recompute the face ordering.

  • Posts: 2,160

    I'll take a look at your code in a bit, but I've just employed step one of your optimisation process and believe that I have a new Step 2 for you. You only need to call the z-ordering when something happens that changes what is in front of what (and the key point is that this is not the same as the distances of the faces from the eye). The two actions that I can think of in your setting that do thus are:

    1. Adding more faces
    2. Translating the coordinates

    In particular, changing the heights (noise) does not change this relationship. The point is that changing the heights moves a face on a line anchored at the centre of the pseudo-globe. For two faces, the line for pne is always in front of (or behind) the line for another so no matter where on the line the faces are placed, the one on the front line can be rendered after the one on the back line. So you work out the right ordering at the start by looking at the z-levels for the faces with no height variation, the keep this orderong and only update it if one of the two things above occurs.

    (I'm not a programmer, but I am a geometer so I'm more sure - not absolutely - that this is right, more than I am about sorting algorithms)

    I might try to implement this with your revised code later today if I get a chance.

  • Posts: 196

    Have been pretty busy with work, but I managed to find the time to add in proper controls:

    1. One finger color or height painting (meaning use the fingers to change the geometry and paint the map)
    2. Pinch to zoom in or out
    3. Two finger swipe for rotations

    It feels really cool :) Finger painting is pretty nice so far and butter smooth, but user input is not completely precise (some issues with depth).

    I'm using vertex color for now, will work on painting on an actual texture when i fix this precision issue :(

    I'll update the code tomorrow if I find the time to make color picking friendly !

  • Posts: 72

    @Xavier I think many people are waiting for your update. Now the Codea 1.3.1 is approved. It makes code exporting easier.

  • It wont let me copy the program can you put it on there a different way please

  • Posts: 196

    @sanit - Hey, I sort of put a hold on working with finger painting, as I'm not happy enough with it.
    I'm done with lightning (calculating the normals/shading as i'm generating the texture) and it looks gorgeous. I'm now plan on working on blending textures with it (based on height values) so I could get an actual terrain renderer.

    However, generating the texture is rather slow (a 128*128 one kills the framerate).
    Unless I'm using a very low resolution (and then it's not pretty), playing with light position to see real time shading isn't as fun as I'd hoped :(
    A possible tweak would be to pre-calculate the shadow maps and store them, but that's barbaric :/

    @jakeallstars - Hey there. Updated the link to be more iPad friendly

  • Posts: 72

    @Xavier Thank your for your update. It seems that we have a small Blender here. I look forward to seeing your update.

  • Posts: 196

    Well, Here is a small video to show the current progress:

    Texturing is a lot of fun :D

    I really wish I could find a way to make it generate faster in high resolution... But apart from using magic, I don't think I really can :P

    I'll update the code once it's commented

    /cheers

  • edited March 2012 Posts: 196

    @sanit - haha not quite there ... yet :P

    Code updated btw

    Cheers,

    Xavier

  • Posts: 196

    Well... I'll be damned ^^
    I said I couldn't make it generate the textures much faster, I was so wrong... Optimized the function as much as I could and boom, textures are generated 4 times faster !

    I wish there was a clamp(x) function... min(1, max(0, x)) is so ugly :(

    Code updated for now, I'm going to go see what else I can do :P

    Cheers,

    Xavier

  • Posts: 2,820

    Like it! Something worth putting Xavier in the beta :-)

  • SimeonSimeon Admin Mod
    Posts: 4,459

    @Xavier I'm sure you've already done this. If not — write it as a function?

    function clamp( x, min, max )
        return math.min( max, math.max( min, x ) )
    end
    

    Though it would be a good thing for us to add. I'm not sure if we should start modifying Lua's internal math library. Adding it outside of math.* seems inconsistent.

  • edited March 2012 Posts: 196

    @simeon - Oh I wasn't even thinking about asking for a clamp function, I was just stating that - takes a deep breath - mycodelooksuglybutIhavenochoicegrrrmybrainisdead :P

    I briefly considered using a custom function, but figured there would be just enough overhead to make me realize how much I should appreciate my code...

    Actually, the only things I miss are built-in vec3 and matrix functions, but you already stated it was planned ;)

    Anyway, going back to coding... after I browse the forums for cool stuff :)

    big hugs to http://www.lua.org/gems/sample.pdf

    Xavier

    edit - wohoo gained another 4 fps in quality 2 :D this post needs more smileys :) :P ;) :O :( ;(

  • SimeonSimeon Admin Mod
    Posts: 4,459

    Interesting document on Lua optimisation.

    I'm adding the vec3 and matrix features to the issue tracker so I remember to add them.

  • edited March 2012 Posts: 196

    @Simeon thanks! Codea will be even more 3D ready :D

    I have a question... In my program, I loop through my model on touch so I can translate raw vertices (no choice when using sphere trick).

    When using max quality, I go through the 4225 points of my model, but I'm running into a weird issue.

    When sphere transformation is active, this line gets included in the loop:

    v.y = v.y - (v.x * v.x + v.z * v.z)*0.001.
    

    What happens is that the draw function won't be called until touch has ended (although it's running at like 12fps). I therefore cannot see my sphere rotate on touch

    When sphere transformation is disabled however, the draw function gets called properly and I can see model translate on screen as I touch it.

    Do you have any idea what that means ? Here is the code:

    local vs = mdl.vertices
            
            for i=1, #vs do
                local v = vs[i]
                local vx = v.x
                local vz = v.z
                
            -- restore the shape of the model (turn it from pseudo-sphere to simple heightmap)
                if sphere == 1 then
                    v.y = v.y - (vx * vx + vz * vz)*0.001
                end
                
            -- due to the way the trick works, translating the vertices rotates the "planet"
                v.x = vx + deltaX
                v.z = vz + deltaY
                v.y = v.y + delta
               
            -- once the translation work is done, turn it back into a pseudo-sphere
                if sphere == 1 then
                    vx = v.x
                    vz = v.z
                    v.y = v.y + (vx * vx + vz * vz)*0.001
                end
        
                v.done = false
            end
    

    Apart from that, I think I'm done optimizing the code (well I always say that).
    I'm now getting 36 fps in quality 2, that's 4096 textured polygons or 12 288 vertices :O

    I got that final speed boost optimizing loops and getting rid of the table.insert (now using premade arrays at the correct size).
    Before I started optimizing, It wasn't running above 1.5 fps at that setting without textures...

    Anyway, source is updated.

    I think I can start making a game out of it, and since it won't need anywhere near that polygon count, that leaves a LOT of room for physics and cool stuff :D

    Thanks again for making such a cool app!

    Cheers,

    Xavier

  • Posts: 196

    @Andrew_Stacey - I'm actually going to implement what you suggested for zsorting.

    Right now I'm sorting every few frames even when it's not needed.

    You're right that if I make it so it only happens on rotations (every few frames), and initialisation, I'll be more efficient :)
    Thanks again for your help and suggestions !

  • edited March 2012 Posts: 196

    Hey all,

    I've implemented textures, and imo it looks pretty damn great. Can't believe I made this entirely on my old iPad... Codea is making my ego skyrocket right now :P

    For now the textures are obviously generated so it's somewhat slow to load, and i'm not great at it. Results will be even better when Codea adds an image upload

    Here are some screenshots:

    http://i42.tinypic.com/b9ghw5.png

    http://i41.tinypic.com/90vchz.png

    http://i44.tinypic.com/1zbdyxk.png

    Well it's 6 in the morning, time to sleep...

    Xavier

Sign In or Register to comment.