drawTriangles() & z-sorting

By Zevan | August 31, 2009
CLICK HERE TO COPY
Actionscript:
  1. [SWF(width = 500, height=500, backgroundColor = 0x000000)]
  2. x = stage.stageWidth / 2;
  3. y = stage.stageHeight / 2;
  4.  
  5. // standard Vectors for using drawTriangles and projectVectors
  6. var verts:Vector.<Number> = new Vector.<Number>();
  7. var pVerts:Vector.<Number>;
  8. var uvts:Vector.<Number>;
  9. var indices:Vector.<int>;
  10. // needed for z-sorting
  11. var sortedIndices:Vector.<int>;
  12. var faces:Array = [];
  13.  
  14. // we'll use this for transforming points
  15. // and as the transformation matrix for our render
  16. var m:Matrix3D = new Matrix3D();
  17.  
  18. // plot a poly
  19. var poly:Vector.<Number>;
  20. poly = Vector.<Number>([ 0, 0, 0,
  21.                         10, 0, 0,
  22.                         0,10, 0]);
  23.  
  24. verts = verts.concat(poly);
  25. faces.push(new Vector3D());
  26.  
  27. // add two more polygons by transorming the poly Vector
  28. // and concatenating it to the verts Vector
  29. // Vector3D instances are added to the faces
  30. // Array for z-sorting
  31.  
  32. // temp vect for any transformed polygons
  33. var transPoly:Vector.<Number> = new Vector.<Number>();
  34.  
  35. m.appendRotation(10, Vector3D.Z_AXIS);
  36. m.appendTranslation(0,-2,5);
  37. m.transformVectors(poly, transPoly);
  38.  
  39. verts = verts.concat(transPoly);
  40. faces.push(new Vector3D());
  41.  
  42. m.appendRotation(10, Vector3D.Z_AXIS);
  43. m.appendTranslation(0,-2,5);
  44. m.transformVectors(poly, transPoly);
  45. verts = verts.concat(transPoly);
  46. faces.push(new Vector3D());
  47.  
  48. // hard coded indices
  49. indices = Vector.<int>([0, 1, 2, 3, 4, 5, 6, 7, 8]);
  50. sortedIndices = new Vector.<int>(indices.length, true);
  51.  
  52. // create texture
  53. var tex:BitmapData = new BitmapData(100,100,false, 0x000000);
  54. tex.fillRect(new Rectangle(0,0,50,50), 0xFF0000);
  55. tex.fillRect(new Rectangle(50,0,50,50), 0x0000FF);
  56. tex.fillRect(new Rectangle(0,50,50,50), 0x00FF00);
  57.  
  58. // hard coded uvts
  59. uvts = Vector.<Number>([0,0,0, .5,0,0, 0,.5,0,
  60.                         .53, 0, 0, 1, 0, 0, .53, .5, 0,
  61.                          0,.6,.5, 0,.6,0, 0,1, 0]);
  62.                        
  63. // fix all vector lengths
  64. verts.fixed = true, uvts.fixed = true, indices.fixed = true
  65. pVerts = new Vector.<Number>(verts.length/3 * 2, true);
  66.  
  67. // we need these if we want perspective
  68. var persp:PerspectiveProjection = new PerspectiveProjection();
  69. // projection matrix
  70. var proj:Matrix3D = persp.toMatrix3D();
  71.  
  72. addEventListener(Event.ENTER_FRAME, onLoop);
  73. function onLoop(evt:Event):void {
  74.     m.identity();
  75.     m.appendRotation(mouseY * 2, Vector3D.X_AXIS);
  76.     m.appendRotation(mouseX * 2, Vector3D.Y_AXIS);
  77.     // push everything back so its not too close
  78.     m.appendTranslation(0,0,40);
  79.     // append the projection matrix at the end
  80.     m.append(proj);
  81.    
  82.     Utils3D.projectVectors(m, verts, pVerts, uvts);
  83.    
  84.     var face:Vector3D;
  85.     var inc:int = 0;
  86.     for (var i:int = 0; i<indices.length; i+=3){
  87.         face = faces[inc];
  88.         face.x = indices[i];
  89.         // it may look odd, but casting to an int
  90.         // when doing operations inside array sytnax
  91.         // adds a big speed boost
  92.         face.y = indices[int(i + 1)];
  93.         face.z = indices[int(i + 2)];
  94.         var i3:int = i * 3;
  95.         // get the average z position (t value) and store it in the Vector3D w property
  96.         // depending on your model, you may not need to do an average of all 3 values
  97.                 // (t is the distance from the eye to the texture)
  98.         face.w = (uvts[int(i3 + 2)] + uvts[int(i3 + 5)] + uvts[int(i3 + 8)]) * 0.333333;
  99.         inc++;
  100.     }
  101.    
  102.     // sort on w, so far this beats all other sorting methods for speed,
  103.     // faster than Vector.sort(), faster than any custom sort method I could find
  104.     faces.sortOn("w", Array.NUMERIC);
  105.    
  106.     // re-order indices so that faces are drawn in the correct order (back to front);
  107.     inc = 0;
  108.     for each (face in faces){
  109.         sortedIndices[inc++] = face.x;
  110.         sortedIndices[inc++] = face.y;
  111.         sortedIndices[inc++] = face.z;
  112.     }
  113.    
  114.     graphics.clear();
  115.     graphics.beginBitmapFill(tex, null, false, false);
  116.     graphics.drawTriangles(pVerts, sortedIndices, uvts, TriangleCulling.NONE);
  117. }

So you want to be able to do some z-sorting with drawTriangles()? Well, its extremely unintuitive. Here is what you need to know:

1) Vector.sort() is slow
2) Array.sortOn() is quite fast
3) I couldn't get any custom sorting method to be faster than Array.sortOn
4) You can use the t value from uvts to do z-sorting (like in this demo)
5) If your going for speed, don't forget to use fixed Vectors (I often forget this step)
6) When working with Vectors cast any operations inside brackets to int() (my tests showed this is a huge speed boost up to 3x faster - franky I think it's horrible that you have to do this).

The swf is not very interesting because I wanted to keep it super simple, but here it is anyway...


Questions

I was told and have read that drawTriangles is slower than using drawGraphicsData and a GraphicsTrianglePath instance. I tested this extensively and found that drawGraphicsData was slower. I'm still not sure which is faster but am up for checking out any simple benchmarks that people have.

drawTriangles is supposed to be faster without adding t values to the uvts Vector. In my benchmark tests there was no real difference in speed. The t value is used to render more accurate textures - which would mean you could potentially use less triangles in your models. One would assume that not using a t value would be faster... but I couldn't confirm this. Again if someone has a good benchmark for this, please let me know.

Help

I had a great deal of help from a few people on Twitter, Katopz (Away3D contributor) of sleepydesign.com made me aware of the fact that Array.sortOn is the way to go... You can see some great demos over at Katopz's blog. While I didn't end up using a custom sorting method, Inspirit
pointed me to his article about custom Vector sorting methods which proved to be very enlightening. I was able to get some really great results for doing different types of sorting - just sorting 1D Vectors with FlashSort can be very fast (faster than Array.sortOn - but not helpful for sorting a 1D Vector of indices).

I also learned a good deal by looking at this code post by Psyark... I actually optimized that code to run about 2x faster (will post that on wonderfl.net at some point, it just needs to be cleaned up).

kevinSuttle sent me a link to The video

This entry was posted in 3D, Graphics, Vector, matrix and tagged , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

2 Comments

  1. katopz
    Posted September 1, 2009 at 2:18 am | Permalink

    i think it’s depend on how you compare it zevan ;)
    i got this from my test

    #case 1 : if you using old render method traverse trough face (fp9), it’s still faster than new method and you need to call drawTriangles one by one per face, this case limited maximum dirty faces around 5,000 (q=medium)

    #case 2 : new method you actually no face need here just referrer to indices in case you need to z-sort (just like you try there), this case limited maximum dirty faces around 20,000 (q=medium)

    in this case#2 faster than case#1 because of Utils3D.projectVectors traverse trough 1 depth fixed vector really fast

    so when i said drawGraphicsData is faster than drawTriangles it’s mean
    drawGraphicsData with new method case#2
    compare to drawTriangles per face via old method case#1 to prevent your confuse but look like i didn’t clarify enough sry ;)

    and if you in case#2 it’s mean you will get result nearly same for both method because this happen internal

    method#1 drawGraphicsData
    drawGraphicsData -> drawPathObject -> drawTriangles

    method#2 drawTriangles
    beginBitmapFill + drawTriangles

    maybe this why is faster ;p

    you can see code for open3d in render loop i did provide both 2 method, you can test by set renderer.type = 1,2 to see speed diff at runtime :)

  2. Zevan
    Posted September 1, 2009 at 3:26 am | Permalink

    Very cool Katopz, that makes perfect sense now :)

One Trackback

  1. By Weekly Shared Items – 1. September, 2009 | TOXIN LABS - weblog of a german design student from wuerzburg on August 31, 2009 at 9:04 pm

    [...] drawTriangles() & z-sorting [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*