 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : The Great Colour Maximite 2 Octahedron Prize Challenge
  Page 3 of 11   |
|||||
| Author | Message | ||||
LeoNicolas Guru  Joined: 07/10/2020 Location: CanadaPosts: 449 |
This is amazing. My rotation and normal algorithms are extremely optimised. The only part in my code that I can improve is the 2D projection. My current code is calculating the 2D position based on the view plane and X,Y and Z distances for each iteration. Probably I can pre calculate part of this values outside of the main loop. |
||||
| yock1960 Senior Member  Joined: 18/08/2020 Location: United StatesPosts: 167 |
Very nice of you Leo, but it's alive once more! Someone out there would love one though! Steve |
||||
CaptainBoing Guru Joined: 07/09/2016 Location: United KingdomPosts: 1993 |
Try using CONSTs for your absolute values so instead of n=n+1 try CONST o=1 ... n=n+o It is a tiny point but on micromites it means less work for the parser and makes a big difference in big loops. It takes less time to look up a variable (CONSTs are just like them) than to build the number from the program code. I know there are a lot of differences in CMM2 MMBasic, maybe absolutes are tokenised or something but this trick works for MicroMites. jus' sayin' Edited 2020-11-10 02:00 by CaptainBoing |
||||
PeteCotton Guru Joined: 13/08/2020 Location: CanadaPosts: 316 |
Given that I imagine a lot of my speed comes from tuning specific to this version of BASIC, (and in the spirit of fair play) I think it only fair that I share what I have done to see if it helps you get faster. If the end result is to find the fastest method for drawing 3D shapes, then you may well have a much better method than me. Some of these shave only a fraction of a millisecond off, but when you iterate 720 times - it starts to make a difference. For some reason using hex numbers &H0 is faster than decimal. For example if (a(x))=&H0 then is slightly faster than if (a(x))=0 then When drawing the triangles, don't use RGB(x,y,z) colours. It's faster to just use an integer and then remap the colour for that integer. For example if X% is the unique number of the triangle/side you are drawing. triangle px1,py1,px2,py2,px3,py3,,X% rather than triangle px1,py1,px2,py2,px3,py3,,rgb(X%*16,128,128) sometimes it's faster to put a whole bunch of variable assignments on the same line, rather than have them on seperate lines (but not always... you need to experiment with this one) x=1:y=1:z=1 I tried putting my triangle draw code on the same line as the IF statement that decides whether to draw it, and was suprised that it was slower. i.e. it is faster to have a seperate IF... ENDIF block rather than one line to do it all. This may need some testing to see if it's applicable to your code. When calculating my surface removal I originally had the following cross product calculation if (x1-x2)*(y1-y3)-(y1-y2)*(x1-x3)>0 then ... draw triangle End IF But in that code the program has to calculate both sides of the formula, subtract one from the other and then compare to zero. I realised it would have the same result if I just had it calculate both sides of the formula and then see if the first part was greater than the second - this has one less calculation (the subtraction). if (x1-x2)*(y1-y3)>(y1-y2)*(x1-x3) then ... draw triangle End IF I don't use subroutines for anything in that 720 loop (apart from one to record the values at the 650th iteration point - but it's only called once). I have moved all logic inline in to the loop body. Finally, my code isn't doing any clipping (the image is always within the bounds of the screen) or viewpoint rotation (my camera is fixed looking along the Z-axis) - both of which would need to be implemented in a real 3d graphics engine. I hope some of this helps others! Edited 2020-11-10 03:35 by PeteCotton |
||||
| LeoNicolas Guru Joined: 07/10/2020 Location: CanadaPosts: 449 |
I did all of these optimizations before and other optimizations using math. Probably I can improve my time only by improving the 2D projection. Currently, I'm using perspective projection that needs to recalculate the X and Y coordinates accordingly with the Z value for each vertice in each iteration. Which 2D projection are you using, orthographic, or perspective? |
||||
| PeteCotton Guru Joined: 13/08/2020 Location: CanadaPosts: 316 |
Perspective. |
||||
vegipete Guru Joined: 29/01/2013 Location: CanadaPosts: 1085 |
This is certainly entertaining and educational. I'm down to 1895ms for the 720 iterations (400MHz Waveshare) although a chunk of that is due to a couple of 'cheats'. The trouble is, much of the tweaking is due to silly little things like removing spaces or using variables instead of numbers and has nothing to do with the algorithms. I haven't determined yet if my giant matrix multiplication is the best method. math m_mult trot(),rotavert(),rotavert() Both of these are 6x6 arrays, yet more than half of the elements are zero.(trot() is the combined rotation, rotavert() is the rotated set of vertices.) =============== This does identify some math commands that would be beneficial if a complete 3-D engine does not come to fruition. 1) Triangle visibility calculation time for me is about 300 milliseconds. If the TRIANGLE command could be told to only draw the triangle if the 3 points were in counter-clockwise order (for example), that would be helpful. (A dot product like calculation) 2) I'm not sure how to name this, but piece-wise matrix multiplication would be helpful. Suppose I have a 2D array vertex(n,3) where n is some arbitrary number of corners, and 3 represents the x,y,z of each. Think of it as an array of vectors. To work with this array of vertices, I need 3 types of operation: 1 - translation: add the components of a vector to each vector in the array 2 - scaling: multiply components 3 - rotation: multiply each vector of vertex() by a rotation matrix. This differs from normal matrix multiplication (I think.) My use of 6x6 matrix multiplication takes about 650 ms. I could try break that apart into individual vectors and rotate each, but then general purpose-ness goes out the window. The above can already be done on a non-array basis. For example, the command MATH V_MULT matrix(), inV(), outV() can perform a rotation, but only on a single vector, not an array of them. The new SLICE command is interesting but I don't see how to use it to quickly extract a slice from an array, perform an operation on the slice, and then push the result back into the array.Of course, I always have more to learn... Visit Vegipete's *Mite Library for cool programs. |
||||
| LeoNicolas Guru Joined: 07/10/2020 Location: CanadaPosts: 449 |
@vegipete I thought to use a huge matrix to rotate the vertices but the code should accept other types of objects, not only octahedrons. I've asked Peter about optimize the code only for octahedrons. This approach only works for 6 vertices objects. and I'm using extensively math for matrix operations. |
||||
| PeteCotton Guru Joined: 13/08/2020 Location: CanadaPosts: 316 |
I'm at 1582ms on a 480mhz. Using Peters 1.18 multiplication factor that puts us at almost exactly the same speed. I don't think I can optimise it much further using the method I am using. One of the "cheats" I am doing that made a big difference to my speed was that I'm using BOX to clear the draw area rather than CLS. That shaved a chunk of speed off my time. (Just in case that helps either of you guys get your time down). After all the challenge was to rotate the object as fast as possible! I am very interested to see how all of our different methods compare when the code is revealed. I'm using straight old fashined sin/cos rotations based off my Elite program. I would love to see if Quaternions (which I freely admit I don't understand) provides a significant boost. |
||||
| PeteCotton Guru Joined: 13/08/2020 Location: CanadaPosts: 316 |
[oops double posted] - deleted Edited 2020-11-10 07:21 by PeteCotton |
||||
| vegipete Guru Joined: 29/01/2013 Location: CanadaPosts: 1085 |
Yeah, got that one already.  I've been looking at quaternions but there is the same issue with dealing with only vectors and not arrays of vectors. Visit Vegipete's *Mite Library for cool programs. |
||||
| LeoNicolas Guru Joined: 07/10/2020 Location: CanadaPosts: 449 |
@PeteCotton, I've compared matrix rotation X quaternion rotation and the first one is faster. This is the approach I'm using with math v_mult to apply the transformation. Does your method with direct rotation calc more efficient than math v_mult? I'm very curious about this. |
||||
| PeteCotton Guru Joined: 13/08/2020 Location: CanadaPosts: 316 |
I am not using Math Mult, just line by line calculation. It would require a bit of a rewrite of my logic to allow it to work with math mult. But it would be interesting to compare. P.S. Time is now 1551ms (I realised I could clear out a flag array using Math Set 0. array). |
||||
| PeteCotton Guru Joined: 13/08/2020 Location: CanadaPosts: 316 |
Okay, I just ran a wee test and did some of my calcs using Math Mult. It made the code a lot more complex and did not speed it up (interestingly, it didn't realy slow it down either).  Make of that what you will.While I was in there though I did re-order my equations to make them more efficient and speed is now down to 1525ms (1522ms if I remove the comments). |
||||
| LeoNicolas Guru Joined: 07/10/2020 Location: CanadaPosts: 449 |
@Pete I'm learning a lot with this challenge. I'm curious about what I'm doing wrong to still 100ms behind you. Let's wait for the end of the challenge to exchange some ideas. I will try to improve my code to gain more ms. My last version is running in 1634ms starting the counter from the first code line and taking the total time after the main loop. I'll use them for sure in my 3D API. |
||||
| PeteCotton Guru Joined: 13/08/2020 Location: CanadaPosts: 316 |
Interestingly, if I remove everything except the rotation calculation, it takes 308ms. i.e. I set timer=0 right before the main loop, and the only thing in the main loop is the rotation/translation for the vertices. If I add in the logic for hidden face removal but do not clear the screen or draw the triangles I go up to 613ms When I add the screen clearing (but no triangles drawn) it goes up to 752ms And with everything enabled, the total time is 1521 (note - this is with the timer=0 line right before the loop - normally it's 1525 when the timer=0 is at the start of the program). This means 308ms for rotation calcs 305ms for hidden surface removal 139ms for clearing the screen 769ms drawing the triangles I don't know how this compares to you guys code, and whether there is anything we can glean from it. |
||||
| vegipete Guru Joined: 29/01/2013 Location: CanadaPosts: 1085 |
I've only timed some of the parts. Seems like my triangle visibility might be slightly faster, your rotation is definitely faster. And I think I've found a bug in "MATH V_MULT matrix(),inV(), outV()" If inV() and outV() are the same array, the results are rubbish. The new results replace the original values as they are generated, resulting in the later results using the earlier results, not the original values. Visit Vegipete's *Mite Library for cool programs. |
||||
| LeoNicolas Guru Joined: 07/10/2020 Location: CanadaPosts: 449 |
I have seen this same issue. For rotating the three axis I'm using 2 arrays to avoid this error. I'll measure my code parts time and post them here. |
||||
| vegipete Guru Joined: 29/01/2013 Location: CanadaPosts: 1085 |
Oh yeah! Some serious unrolling and matrix shrinking gives me under 1585 milliseconds. And that's at 400MHz. The unrolling is largely because there are no 'arrays of vectors' - otherwise it could be done in a loop. And I'm no longer locked to only octahedrons as a result. =============== I gather you are finding too that the end position is not the same as the start position? If I perform only single axis rotations, the end does match the start, but not with compound rotations. Visit Vegipete's *Mite Library for cool programs. |
||||
| PeteCotton Guru Joined: 13/08/2020 Location: CanadaPosts: 316 |
I've installed RC15 of the firmware, and it knocked 200ms off the triangle draw time. I know the rules state RC14, but still it's very useful to know. |
||||
| Page 3 of 11 |
|||||
 Print this page |
