3D rendering on Codea

Xavier

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

peteroyle

Wow, that's just awesome!

Zoyt

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

Xavier

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

Zoyt

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

Simeon

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

Xavier

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

Simeon

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

bee

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.

Andrew_Stacey

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.

Blanchot

Welcome to the community Xavier!

frosty

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

Xavier

@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

Xavier

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

gunnar_z

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

sanit

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.

Xavier

@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

Andrew_Stacey

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.

Andrew_Stacey

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

Andrew_Stacey

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.

Xavier

@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

jlslate

iPad 1 vs. iPad 2?

Andrew_Stacey

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.

Xavier

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

Andrew_Stacey

Just tried it via linked lists and got a stackoverflow!

Xavier

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

Xavier

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

Bortels

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

Simeon

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

Xavier

@simeon

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

bee

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

bee

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

sanit

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

Xavier

hahaha....hahahaahaha....HAHAHAAHAHAHAHAHAHA

60fps in quality 3 at last !!!!!
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

Andrew_Stacey

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.

Andrew_Stacey

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.

Xavier

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 !

sanit

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

jakeallstars

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

Xavier

@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

sanit

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

Xavier

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

Texturing is a lot of fun

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

Xavier

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

Code updated btw

Cheers,

Xavier

Xavier

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

Zoyt

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

Simeon

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

Xavier

@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 this post needs more smileys :P :O ;(

Simeon

Interesting document on Lua optimisation.

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

Xavier

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

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

Thanks again for making such a cool app!

Cheers,

Xavier

Xavier

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

Xavier

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