Home
JAQForum Ver 24.01
Log In or Join  
Active Topics
Local Time 09:22 19 Sep 2025 Privacy Policy
Jump to

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 7 of 11    
Author Message
LeoNicolas

Guru

Joined: 07/10/2020
Location: Canada
Posts: 511
Posted: 11:36pm 12 Nov 2020
Copy link to clipboard 
Print this post

  mkopack73 said  Obviously I'm not the judge, but if you consider the rationale behind this challenge, the desire to provide an API for doing generic 3D graphics, then it really should be doing the rotation based on the initial state, not off the previous iteration. That's how 3D systems typically work.


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 States
Posts: 261
Posted: 11:45pm 12 Nov 2020
Copy link to clipboard 
Print this post

  LeoNicolas said  
  mkopack73 said  Obviously I'm not the judge, but if you consider the rationale behind this challenge, the desire to provide an API for doing generic 3D graphics, then it really should be doing the rotation based on the initial state, not off the previous iteration. That's how 3D systems typically work.


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.


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: Canada
Posts: 557
Posted: 11:56pm 12 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 511
Posted: 11:59pm 12 Nov 2020
Copy link to clipboard 
Print this post

  mkopack73 said  
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: Canada
Posts: 557
Posted: 12:02am 13 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 557
Posted: 12:07am 13 Nov 2020
Copy link to clipboard 
Print this post

  PeteCotton said  Er, wow. I just made a small change and shaved 200ms off my time and I can't explain why.
.....

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: Canada
Posts: 557
Posted: 12:13am 13 Nov 2020
Copy link to clipboard 
Print this post

  LeoNicolas said  Pete

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: Canada
Posts: 511
Posted: 01:31am 13 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 511
Posted: 05:49am 13 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 511
Posted: 07:16pm 13 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 1140
Posted: 07:48pm 13 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 511
Posted: 08:24pm 13 Nov 2020
Copy link to clipboard 
Print this post

  vegipete said  Here is some fun with colours, and more triangles:


Wow, it's beautiful. I loved      
 
vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1140
Posted: 09:00pm 13 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 1140
Posted: 11:06pm 13 Nov 2020
Copy link to clipboard 
Print this post

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:
  Quote  You are looking down at the shape from the positive z direction. Positive x is to the left, positive y is down.

Edited 2020-11-14 09:32 by vegipete
Visit Vegipete's *Mite Library for cool programs.
 
LeoNicolas

Guru

Joined: 07/10/2020
Location: Canada
Posts: 511
Posted: 11:38pm 13 Nov 2020
Copy link to clipboard 
Print this post

Wow, now we are officially below 1s. Congratulations, 770ms in a 400MHz CMM2 is impressive.
 
LeoNicolas

Guru

Joined: 07/10/2020
Location: Canada
Posts: 511
Posted: 03:54am 14 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 511
Posted: 06:07am 14 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 557
Posted: 07:21am 14 Nov 2020
Copy link to clipboard 
Print this post

  vegipete said  Great Scott!

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 Kingdom
Posts: 10407
Posted: 09:28am 14 Nov 2020
Copy link to clipboard 
Print this post

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: Canada
Posts: 1140
Posted: 05:35pm 14 Nov 2020
Copy link to clipboard 
Print this post

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.
 
     Page 7 of 11    
Print this page
The Back Shed's forum code is written, and hosted, in Australia.
© JAQ Software 2025