![]() |
Forum Index : Microcontroller and PC projects : The Great Colour Maximite 2 Octahedron Prize Challenge
![]() ![]() ![]() ![]() |
|||||
Author | Message | ||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
This needs to be decided by @matherp because the rotation method using the previous coordinates is faster than always applying rotation over the initial coordinates. This second approach implies recalculating the rotation matrix for each iteration due to the angle will change after each rotation. The first approach will use the same rotation matrix with the angles X=2, Y=1 and Z=0.5 for all iterations. The example in the Graphics Programming on the CMM2 documentation uses the first approach, applying quaternion rotation over the previous vertices position. |
||||
mkopack73 Senior Member ![]() Joined: 03/07/2020 Location: United StatesPosts: 261 |
Yeah the problem with doing it based on the previous iteration's result is that if you change the rotation (or position or scale) then you can't reuse the previous and get the proper result. Calculating off the original position might be slower but its more consistent and will always work. What I mean by that is if you do it on the previous iteration, and you're basically just reusing the same pre-calculated changes then if you alter the rotation vector you end up having to redo all the calculations again. But yeah it's totally up to matherp. |
||||
PeteCotton![]() Guru ![]() Joined: 13/08/2020 Location: CanadaPosts: 557 |
Er, wow. I just made a small change and shaved 200ms off my time and I can't explain why. The culprit/hero is this line: triangle x1,y1,x2,y2,x3,y3, ,cl(v) Where I had worked out (in a previous firmware) that leaving the line parameter (second last) blank gave me a small speed improvement. The above line gives me a total time of 1272ms. Changing the line colour to a fixed number (e.g. &H0) does not affect the time. But if I change it to a variable like follows. triangle x1,y1,x2,y2,x3,y3,cl(v) ,cl(v) My time drops to 1067ms Edited 2020-11-13 10:00 by PeteCotton |
||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
Yeah the problem with doing it based on the previous iteration's result is that if you change the rotation (or position or scale) then you can't reuse the previous and get the proper result. Calculating off the original position might be slower but its more consistent and will always work. What I mean by that is if you do it on the previous iteration, and you're basically just reusing the same pre-calculated changes then if you alter the rotation vector you end up having to redo all the calculations again. But yeah it's totally up to matherp. I agree mkopack73, but this is a performance challenge ![]() |
||||
PeteCotton![]() Guru ![]() Joined: 13/08/2020 Location: CanadaPosts: 557 |
With regards to the discussion on rotation. I get the argument that absolute rotation is more useful, but in fairness the rules just asked that we rotate by a set amount on the x,y,z. I would argue that re-applying the same rotation repeatedly does meet that criteria. But yeah, it's a call for Peter. Edited 2020-11-13 10:03 by PeteCotton |
||||
PeteCotton![]() Guru ![]() Joined: 13/08/2020 Location: CanadaPosts: 557 |
..... Changing the line colour to a fixed number (e.g. &H0) does not affect the time. But if I change it to a variable like follows. triangle x1,y1,x2,y2,x3,y3,cl(v) ,cl(v) My time drops to 1067ms Aha. Mystery solved. If the line colour equals the fill colour, then it is signifcantly faster. Edited 2020-11-13 10:08 by PeteCotton |
||||
PeteCotton![]() Guru ![]() Joined: 13/08/2020 Location: CanadaPosts: 557 |
Probably you can improve your time using matrix math operations instead of using basic to perform calculations. With exception of the projection, I'm performing all operations using matrix math. For rotation, I changed the loop to rotate each vertice to pure matrix multiplication. I'm performing 3 multiplications, one per axis. I'll try to figure out a way to rotate the 3 axis with only one matrix multiplication. If I'm able to do it, I can reduce my time. Interestingly, the matrix multiplication did not give me any speed improvement. I could see it might if I was re-applying the same rotation maybe, but that would require quite a bit of a re-write of my code. But as it is I have to rebuild my x, y and z rotation matrixes each time, which seems to offset the boost I get from the actual matrix multiplication operation. Unless there's a fast way of assigning multiple variables at once in to an array? My rotation code is pretty tight as it is. |
||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
It's interesting how this challenge has improved our code. We started the challenge with the time close to 2s and now we are close to 1s ![]() |
||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
I was wrong, after a new optimization, my new time is 1009.80 ms. The adjusted time is 1191.56 ms. Can we get down to less than 1s? ![]() Edited 2020-11-13 15:53 by LeoNicolas |
||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
I managed to drop the execution time by a few milliseconds. The code is bigger than the last version but is faster. Total time: 1006.48 ms Adjusted time (x 1.18): 1187.64 ms ![]() |
||||
vegipete![]() Guru ![]() Joined: 29/01/2013 Location: CanadaPosts: 1140 |
Here is some fun with colours, and more triangles: (There may be some glitches from an editor attack... ![]() ' 3D Solids Get Dizzy ' vegipete, Nov 2020 mode 1,16 cls print @(0,0) " 0/1000 " page write 1 : cls print @(125,580) "Press [space] to start/stop, any other key to step when stopped." pause 3000 ' wait for monitor to sync timer = 0 '====================================== d = 800 ' distance to view plane rho = 1000 ' distance to object (center) cx = MM.HRES/2 cy = MM.VRES/2 pmode = 0 dim f_cols(50) ' colour of each face dim s_verts(50,2) ' all the vertices dim s_faces(50,2) ' faces, composed of 3 vertices in couererlolowiwi o oerer dim proj_x(50) ' projected coordinates dim proj_y(50) ' \ of each vertex dim light(2)=(0,2,10) ' direction of light source (not distance!) dim v1tmp(2), v2tmp(2), fnorm(2) restore facecolours ' read in face colours for i = 0 to 49 read f_cols(i) next i ' build rotation matrix ct = cos(rad(2)) : st = sin(rad(2)) dim xrot(2,2) : math set 0, xrot() xrot(0,0) = 1 : xrot(1,1) = ct : xrot(1,2) = st : xrot(2,1) = -st : xrot(2,2) = ct ct = cos(rad(1)) : st = sin(rad(1)) dim yrot(2,2) : math set 0, yrot() yrot(0,0) = ct : yrot(0,2) = -st : yrot(1,1) = 1 : yrot(2,0) = st : yrot(2,2) = ct ct = cos(rad(.5)) : st = sin(rad(.5)) dim zrot(2,2) : math set 0, zrot() zrot(0,0) = ct : zrot(0,1) = -st : zrot(1,0) = st : zrot(1,1) = ct : zrot(2,2) = 1 dim trot(2,2) ' total rotation matrix - order matters math scale xrot(),1,trot() math m_mult trot(),yrot(),trot() math m_mult trot(),zrot(),trot() restore octashape ReadShape SpinIt page write 0 'print timer print "Press a key for more sides..." do : loop until inkey$ <> "" restore icosashape ReadShape SpinIt page write 0 'print timer print "Press a key to end..." do : loop until inkey$ <> "" end sub SpinIt page write 1 ' draw iteration 0 DrawSolid ' erase box = 0 at start for iter = 1 to 1000 ' rotate the vertex cloud in 3 dimensions for i = 0 to nverts-1 v1tmp(0) = s_verts(i,0) : v1tmp(1) = s_verts(i,1) : v1tmp(2) = s_verts(i,2) math v_mult trot(),v1tmp(),v2tmp() s_verts(i,0) = v2tmp(0) : s_verts(i,1) = v2tmp(1) : s_verts(i,2) = v2tmp(2) next i DrawSolid print @(0,0) iter "/1000 " page copy 1,0,B k = asc(inkey$) if pmode then do if k = 32 then pmode = 0 if k <> 0 then exit do k = asc(inkey$) loop else if k = 32 then pmode = 1 endif next iter end sub sub DrawSolid ' calculate erasing box bx = math(min proj_x())+cx : bh = math(max proj_x())+cx+&h2 by = math(min proj_y())+cy : bv = math(max proj_y())+cy+&h2 ' project all vertices to viewing plane for i = 0 to nverts-1 ze = rho - s_verts(i,2) proj_x(i) = -d * s_verts(i,0) / ze proj_y(i) = d * s_verts(i,1) / ze next i ' erase previous image box bx,by,bh-bx,bv-by,,&h0,&h0 ' draw the faces for i = 0 to nfaces-1 x0 = proj_x(s_faces(i,0)) : y0 = proj_y(s_faces(i,0)) x1 = proj_x(s_faces(i,1)) : y1 = proj_y(s_faces(i,1)) x2 = proj_x(s_faces(i,2)) : y2 = proj_y(s_faces(i,2)) if (x0-x1)*(y0-y2)<(x0-x2)*(y0-y1) then ' face visible? v1tmp(0) = s_verts(s_faces(i,0),0) - s_verts(s_faces(i,1),0) v1tmp(1) = s_verts(s_faces(i,0),1) - s_verts(s_faces(i,1),1) v1tmp(2) = s_verts(s_faces(i,0),2) - s_verts(s_faces(i,1),2) v2tmp(0) = s_verts(s_faces(i,0),0) - s_verts(s_faces(i,2),0) v2tmp(1) = s_verts(s_faces(i,0),1) - s_verts(s_faces(i,2),1) v2tmp(2) = s_verts(s_faces(i,0),2) - s_verts(s_faces(i,2),2) math v_cross v1tmp(),v2tmp(),fnorm() ' calculate face normal c = math(magnitude light()) * math(magnitude fnorm()) if c then c = abs(math(dotproduct light(), fnorm()) / c) else c = 1 endif rc = ((f_cols(i) and &hFF0000) >> 16) * c gc = ((f_cols(i) and &h00FF00) >> 8) * c bc = ((f_cols(i) and &h0000FF) ) * c triangle x0+cx,y0+cy,x1+cx,y1+cy,x2+cx,y2+cy,,rgb(rc,gc,bc) endif next i end sub ' read shape data set by rtoto c cmamand sub ReadShape math set 0, s_faces() math set 0, s_verts() math set 0, proj_x() math set 0, proj_y() ' read in vertices read nverts for i = 0 to nverts-1 read s_verts(i,0) : read s_verts(i,1) : read s_verts(i,2) next i ' read in faces read nfaces for i = 0 to nfaces-1 read s_faces(i,0) : read s_faces(i,1) : read s_faces(i,2) next i end sub sub ShowVerts for i = 0 to nverts-1 print s_verts(i,0), s_verts(i,1), s_verts(i,2) next i end sub octashape: ' vertices (first value is count) data 6, 0,250,0, 250,0,0, -250,0,0, 0,-250,0, 0,0,250, 0,0,-250 ' faces (first value is count) data 8, 4,2,3, 4,3,1, 4,1,0, 4,0,2, 5,3,2, 5,1,3, 5,0,1, 5,2,0 icosashape: data 12 data 0,150,243, 0,-150,243, 0,150,-243, 0,-150,-243 ' (0, 1, f) Where f = data 150,243,0, -150,243,0, 150,-243,0, -150,-243,0 ' (1, f, 0) (1 + v5) / 2 data 243,0,150, 243,0,-150, -243,0,150, -243,0,-150 ' ( f, 0, 1) golden ratio 1.618 data 20 dat 16 6,,8, 18 8,,0, 10 0,,0, 1010, 7 ' vertices for data 1, 7, 6, 6, 7, 3, 6, 3, 9, 6, 9, 8 ' each face in data 8, 9, 4, 8, 4, 0, 0, 4, 5, 0, 5,10 ' counter-clockwise data 10, 5,11, 10,11, 7, 7,11, 3, 3,11, 2 ' order data 2,11, 5, 2, 5, 4, 2, 4, 9, 2, 9, 3 facecolours: data &hFF0000,&h00FF00,&h0000FF,&hFFFF00,&hFF00FF,&h00FFFF,&hFFFFFF,&h404040 data &hFF4000,&h80FF00,&h4040FF,&hFFFF40,&hFF00FF,&hC0FFFF,&hFFFFFF,&h404040 data &hFF8000,&hC0FF40,&hC000FF,&hFFFF80,&hFF80FF,&h00FFFF,&hFFFFFF,&h404040 data &hFFC000,&h40FF00,&h0080FF,&hFFC000,&hFF00FF,&h80FFFF,&hFFFFFF,&h404040 data &hFF0000,&h00FF00,&h4000FF,&hFF8000,&hFF40FF,&h00FFFF,&hFFFFFF,&h404040 data &hFF0000,&h00FF00,&h0000FF,&h80FF00,&hFF00FF,&h00FFFF,&hFFFFFF,&h404040 data &hFF0000,&h00FF00,&h0000FF,&hFFFF00,&hFF00FF,&h00FFFF,&hFFFFFF,&h404040 Visit Vegipete's *Mite Library for cool programs. |
||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
Wow, it's beautiful. I loved ![]() ![]() ![]() |
||||
vegipete![]() Guru ![]() Joined: 29/01/2013 Location: CanadaPosts: 1140 |
Sorry folks, that previous listing was slightly garbled. One of the data statements (the 8th one) got munched. The CMM2 editor has been mashing my programs a bit for unknown reasons. Here's a zip copy that hopefully works properly. You can move the direction of the light around in line 21. You are looking at the left, positive y is down. So if you put the light at (0,0,-1), you should only see black triangles. If you put the light at (-1,-1,2), triangles facing up and right should be brightest. Edited 2020-11-14 07:24 by vegipete Visit Vegipete's *Mite Library for cool programs. |
||||
vegipete![]() Guru ![]() Joined: 29/01/2013 Location: CanadaPosts: 1140 |
Great Scott! I just flashed RC18. My octahedron spins its 720 iterations in just under 770 milliseconds. Wow. There has clearly been some tremendous triangle speed up. Changing the triangle border colour to the same as the fill helped a bunch. Also, more garbled text in my previous post. Must be something wrong with my fingers. Its should have said: Edited 2020-11-14 09:32 by vegipete Visit Vegipete's *Mite Library for cool programs. |
||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
Wow, now we are officially below 1s. Congratulations, 770ms in a 400MHz CMM2 is impressive. |
||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
vegipete, I really don't know how you achieved this execution time, it's amazing. I'm curious to see your code... let's wait for the end of the challenge. This is an awesome opportunity to learn new optimization strategies ![]() I've checked my octahedron width and length to see if I'm rendering it with the wrong size (greater than the specification) but it is right. It has 400px height and width before rotation. My main loop is very very small and even removing the rotation process I cannot drop below 1s ![]() After updating my CMM2 to the R14 firmware my time dropped to 1004.14 ms |
||||
LeoNicolas![]() Guru ![]() Joined: 07/10/2020 Location: CanadaPosts: 511 |
For those interested to understand how we are rendering the 3D polygon, I recommend watching this playlist: https://www.youtube.com/playlist?list=PLzH6n4zXuckrPkEUK5iMQrQyvj9Z6WCrm |
||||
PeteCotton![]() Guru ![]() Joined: 13/08/2020 Location: CanadaPosts: 557 |
My octahedron spins its 720 iterations in just under 770 milliseconds. WOW! That is bloody brilliant. I am blown away! Great job! |
||||
matherp Guru ![]() Joined: 11/12/2012 Location: United KingdomPosts: 10407 |
RULE CHANGE/ADDITION/CLARIFICATION In the interest of fairness, if you are not rotating from the initial starting position each time then you must generate the rotation matrix afresh each time through the main loop. In the evaluation of the code I will check the 650 iteration coordinates using either of the approaches which we now understand will give different results (something else learned). In terms of building 3D functionality into the firmware it has to be the approach that the base object is created and then rotated from it initial position each time. Latter today I will post RC19 which should give another performance improvement thanks to your collective work and you will want to upgrade for the challenge The simple change that makes a huge difference is in the treatment of scalar constants. You will find in RC19 the penalty for "255" vs "&HFF" has disappeared or even been reversed. This makes little difference for ordinary assignments but think how often you use scalars in array indexing e.g. a(4) |
||||
vegipete![]() Guru ![]() Joined: 29/01/2013 Location: CanadaPosts: 1140 |
Boooo. Recalculating my rotation matrix each iteration adds about 100 ms to my time - 875 ms. Changing to absolute rotations, instead of incremental rotations, makes my final image match the initial image. Also, my iteration _649_ coordinates EXACTLY (to every decimal digit!) match PeteCotton's posted image (08:20pm 09 Nov 2020, page 4 of this thread) Visit Vegipete's *Mite Library for cool programs. |
||||
![]() ![]() ![]() ![]() |
![]() |
![]() |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |