Using QuadTrees In Papervision3D


How to Use It

To get the corrective z-sorting working, you simply need to use a new RenderEngine – QuadrantRenderEngine.  It takes one parameter – type – and depending how you set it you will get different results (and different performance).

type values:

  • QuadrantRenderEngine.CORRECT_Z_FILTER – This filter (QuadrantZFilter) does exactly what it sounds like – it sorts the triangles (when possible) correctly – removing the issues you would normally have with the painters algorithm.  Note that this will not correctly sort triangles that pass through each other.  For that you will need to use the next value.
  • QuadrantRenderEngine.QUAD_SPLIT_FILTER – The QuadrantFilter actually splits faces that intersect each other.  Since you can’t correctly z sort triangles that run into each other – if you need the ability to cut faces that intersect, you can use this option.  Often though, after using this, you will still need to use the CORRECT_Z_FILTER to sort the newly cut faces properly.  Which brings us to:
  • QuadrantRenderEngine.ALL_FILTERS – This option uses both the CORRECT_Z_FILTER and QUAD_SPLIT_FILTER – which will give you corrective sorting of triangles no matter if they pass through each other or not.  An alternative to using this value is using CORRECT_Z_FILTER | QUAD_SPLIT_FILTER.

Making it run a little better

One feature we did add to the QuadTree is the ability to turn off testing for certain objects.  While in alot of cases this won’t be a huge performance gain – it does offload some math thats not needed if you know it won’t be an issue.  An example of this would be having a model floating in a courtyard.  You know the model will never have z-fighting with the courtyard, so you can turn off the courtyard from the tests.  It will still be sorted in the usual pv3d fashion, so you don’t have to worry.

To turn off QuadTree testing for a DisplayObject3D – you can set the do3d.testQuad property.  When this boolean is set to false, the faces of the object will not have any QuadTree testing performed on them.  This will save you calculations when you don’t need them.

You can also set the maximum depth the QuadTree will subdivided.  This can be set with the QuadTree.maxlevel property.  Mess with this to find a good balance of node size and performance.  Too many nodes can be a waste of infromation and requires testing rediculously small areas – but too large of nodes requires extra processing in many cases, and won’t be as accurate.  Play with it per-project to find a good balance.

So When Should I Use This?

Honestly?  This is a feature that everyone wants but isn’t the miracle cure they hoped for.  While a very cool feature – it can destroy your CPU.  For things such as model viewers, where you have no control over certain models, it is a great option.  However, for most thing you are MUCH better off using ViewportLayers and correct modeling techniques.  These will add no overhead and will give you the results you want.  In addition, since the QuadTree operates at runtime, if you have a static scene, you can use BSP, which preprocesses the scene.

QuadTreeVisualizer

I’ve included an extra class (you can see it in action by pressing “V” in the demos).  It is the QuadTreeVisualizer which will show you all the subdivisions you are currently using.  Doesn’t help much – but is cool to check out and might help when debugging.

Demos

Demo One – This demo shows Papervision using the QuadrantRenderEngine.ALL_FILTERS property.  Both splitting and corrective z-sorting is performed on the objects.  You can toggle the “testQuad” property for the bottom plane as well.  Check it out HERE

Demo Two – This demo is only using corrective z-sorting.  Toggle it on and off and you can see where triangles are fixed where they were previously messed up.  Check it out HERE

Get The Source – Both demos use the same source – just uncomment where required :)

Enjoy!  And of course let us know of any bugs!


62 Comments, Comment or Ping

  1. Well done, for now i stick on vpl’s then :)

    October 14th, 2008

  2. Matthew

    this may be perfect timing! I have a dead line for friday, for a complex model for a website. I wasn’t looking forward to creating vpl’s everywhere, and figuring that out. :) I’ll let you know how it goes.

    October 14th, 2008

  3. Nice! Just what I needed :) But I hope the destroying-cpu-feature is a joke..

    October 14th, 2008

  4. Where do you get the energy from?! Tell me! :)

    By the way, What’s with the quadtree splitting? It looks to me that it’s generating a bunch of unneded polygons?

    I wonder what are the benefits between this technique and BSP subdivision:
    http://blog.alternativaplatform.com/ru/files/2007/12/bspdemo.swf

    October 14th, 2008

  5. @Marcus – sorry, no joke. This is a very heavy operation (just take a look at the code). In many cases it will be fine, but for complex scenes it will chug.

    @Mr. Doob – I’ll check to see if there are some more optimizations i can do. There are alot of tris for 1) the corrective z sorting and 2) The fact that the cube material is double sided. It is MUCH less if that cube is single sided :)

    October 14th, 2008

  6. Only one thing to say… You are ONE OF THE STRONGEST ;-)

    October 14th, 2008

  7. Matt Pelham

    Hey there, this fixes so many of papervision’s niggling issues. However, interactive objects seem to break when QuadTree is enabled. Is this due to the viewport being “split”? What are the solutions?

    October 15th, 2008

  8. Bravo à toi, tu roxx !

    October 16th, 2008

  9. Hi Andy

    great progress on papervision, just one project too late for me :/ Had lots of fun with viewport layers although your blog really helped. The quadtree looks like a great time saver especially when dealing with .3ds files.

    On a separate note, is there some way of changing materials for clone objects dynamically. Using replace material by name is fine for the original object, but clone obj properties seem locked and applying a change to the original object makes the change throughout all the clones

    October 16th, 2008

  10. mh

    Hi everyone,

    the testQuad property doesn´t work for me. it doesn´t make any difference wheter testQuad is set to false or not. I imported a DAE object into Papervision and set the testQuad =false, but nevertheless it is rendered in exactly the same way as when testQuad = true!
    what do a wrong?

    I load my DAE and onLoadComplete I set testQuad = false and then add it to the scene with scene.addChild().

    Please help! greetings miriam

    October 16th, 2008

  11. @mH – You can see the difference it should make if you visit http://rockonflash.wordpress.com/2008/10/14/papervision3d-quadtree-released/. Remember that testQuad only works if you are using QuadrantRenderEngine :)

    @Matt – Interactivity has been fixed with QuadTree support. Thanks for the notice.

    October 16th, 2008

  12. This is great news! I would’ve thought constructing the quad tree with every render would be too slow, but hey here you go :D It’s great to see your latest Papervision additions, they really push the engine to the next level.

    October 17th, 2008

  13. saul

    New Papervision is built well.

    Your beginning to ROCK MY WORLD~xD!

    October 17th, 2008

  14. Svitovyda

    It’s really cool!

    But now with this renderer interactivity doesn’t work…

    October 17th, 2008

  15. Svitovyda

    Sorry, I found fix. It’s great job!

    Also, I don’t know to whom send this:

    I’m using BitmapFileMaterial very intensive for different skinned objects. And I had some troubles with maxU/maxV settings.
    In org.papervision3d.materials I changed line 581:

    Instead of:
    this.maxU = this.maxV = 1;

    I added checking if those values alredy set:

    if( ! this.maxU )
    {
    this.maxU = this.maxV = 1;
    }

    And also, to calculate maxU and maxV I need to know size of loaded image, so I added information about loaded content to FileEvent’s dataObj parameter in org.papervision3d.materials. BitmapFileMaterial, line 303.

    Maybe I don’t use it correctly (this is my first experience with 3D at all) and there is better ways to use this material for my needs. But may be my fixes can be useful to others…

    October 17th, 2008

  16. Awesome! Thanks so much for this. With so few true explanations and examples out there, this solved mucho problems for me! You are awesome, and I thank you!

    October 26th, 2008

  17. zh.

    So what about rendering of doubleSliced materials? One side is good, and another is bugged.. Every polygon is flipped (or rotated).
    Try BitmapMaterial to see that.

    Is it fixable?

    October 28th, 2008

  18. @zh – Double Sided materials work for me. Try turning on precise to see if it is an issue of perspective. If that doesn’t work, copy me some code that can reproduce the problem :)

    October 28th, 2008

  19. Hi!

    I’ve posted on the papervision blog a comment about a bug using the QuadRenderEngine and you asked me for some code to reproduce the problem.
    You can download the sorce code here:
    http://www.andreanaya.com/quadrender_issue.zip

    I’m using a BitmapMaterial with transparency and applying to an 3DS mesh.

    I will appreciate if you send me some feedback about this issue.

    Thanks

    October 28th, 2008

  20. zh.

    Something simple like this:
    _vp = new Viewport3D(800, 600, false, true);
    addChild(_vp);
    _renderer = new QuadrantRenderEngine(QuadrantRenderEngine.ALL_FILTERS);
    _scene = new Scene3D();
    _cam = new Camera3D();
    _cam.focus = 100;
    _cam.zoom = 10;
    _holder = new DisplayObject3D();
    _scene.addChild(_holder);
    _mat = new BitmapMaterial(someLoadedBitmap.bitmapData);
    _mat.doubleSided = true;
    _mat.interactive = true;
    _plane = new Plane(_mat, WIDTH, HEIGHT); // predefined size
    _holder.addChild(plane);

    perframe action:
    _holder.yaw(.2);
    _renderer.renderScene(_scene, _cam, _vp);

    And on another side something stange is happening.
    I could send you screenshots if you want.

    October 28th, 2008

  21. @Everyone – okay – update your SVN and let me know if that fixed it for you.

    Thanks for the update on the problem!

    October 28th, 2008

  22. YEAH!!!!!
    Now it’s working perfect!!!

    Great job!!!

    October 28th, 2008

  23. yryim

    Hi Andy
    I am testing your quadtree and need comparable performance
    I am sorry but i can’t find your posting about viewport layers
    Please point the link to the posting

    October 29th, 2008

  24. yryim

    I am sorry I found it

    October 30th, 2008

  25. Can i use the QuadrantRenderEngine with Vectorvision packages?

    November 2nd, 2008

  26. Oh man! That’s so cool work! I would like to share mine.
    I’ve created a simple Papervision 3D Gallery, could you please check it and comment if you’ll have time.
    http://www.flashmoto.com/flash-galleries/papervision-3d-flash-gallery
    I’ve also made a tutorial for it so ppl could create the same …
    http://www.flashmoto.com/flash-galleries/papervision3d-flash-gallery-tutorial/

    Regards,
    Dementrio

    November 12th, 2008

  27. Tom Callahan

    Does this cause any problems for Viewport layers (or “useOwnContainer” for that matter)? I have an example where if I use BasicRenderEngine I can do alpha or filters, but if I switch to Quadrant using just the correct-z-filter option it simply doesn’t work — no error messages or anything, just no alpha or filter effects. Nothing else changed.

    The project is a simple set of 5 planes with bitmap file materials, each attached to empty DO3Ds (as hinges) and then all of that placed in another empty DO3D to act as a main pivot. The filter adds a faint gray shadow/glow to offset the white-on-white edges.

    Example w/QRE:
    http://www.thomascallahan.org/posting/3d/wedding-qre/Wedding.html

    Example w/BRE:
    http://www.thomascallahan.org/posting/3d/wedding-bre/Wedding.html

    Source:
    http://www.thomascallahan.org/posting/3d/wedding-src.zip

    The only difference is the rendering engine.

    November 12th, 2008

  28. Leymon

    Yes Tom. I’ve got the same problem. With QuadrantRenderEngine the filters and blending applied to layers seem to not work.
    It would be great to fix that limitation Andy.

    November 20th, 2008

  29. felipe

    what a lasy you are….how much time visiting your web site, hoping to find a new post. what a lose of time… i try to imaging people leaving your web site disapointed.

    November 22nd, 2008

  30. PeterPetty

    where are you man, one month age the last post.
    too many people going to delete your site from the F list.

    November 22nd, 2008

  31. Tom

    Yep, I’m having the same problem with filters and quadrender engine – would be great if I could use both at the same time!!… anyone have a fix?

    In the meantime i’m swapping out the renderengine as I only need to apply a filter when a Collada object is clicked. i.e. on object click (use the basic render engine and apply useowncontainer and filters to object) otherwise use quadrenderengine.

    P.S I think Andy went on holiday for a month or 2. Don’t blame him the amount of work they seem to put into Papervision!

    Tom

    December 4th, 2008

  32. Tom

    Giving it more thought I think it may be impossible to have both effects support and QuadTrees — the way it breaks everything up it would result in multiple different objects and you’d get seams in the middle and sorting-order problems, for example if it split a shape in two and you had an outer glow on it, you’d have the outer glow apply to both pieces so you’d have a visible artifact down the seam. I’ve already run into a similar problem doing a DOF blur on a wall of planes — you can’t have zero space between the planes because when they’re blurred the seams become visible, so I had to do either small gaps on purpose between all of the planes, or no gaps and drop the DOF blur.

    Maybe I’m wrong but I don’t see a way around it. Still, awesome to have in case it’s needed — in this particular case I’ll just switch to using a transparent PNG for the loaded textures with a baked-in fuzzy edge, or maybe I can get away with adding the edge to the entire viewport since there won’t be any other 3d elements.

    December 8th, 2008

  33. @Tom – Yea – this is the reason i didn’t support layers in QuadTree. It would add extra overhead for everything, but only be useful in very specific use cases. Sorry i didn’t respond sooner – been slammed with life :)

    December 8th, 2008

  34. Leymon

    Thank you guys for these informations. By using Basic Engine and layers we can get a good result anyway if we really do it carefully.
    So the problem is that the sorting is only made on object level and not on face level to avoid heavy caculations right? Maybe it would be better to have both depending on the situation.
    I’ve got a question (sorry i’m quite a newb), is it possible to run the Basic render engine in one layer (ex: FX) and the Quadtree in another one (ex:decor & characters).
    Also, I’m wondering whether in the future there is a way that pixelbender can speed up the z-sorting and do it very accurately.

    December 9th, 2008

  35. ynk

    Hey there !

    I’m having some difficulties with this powerful render engine.

    I have a iphone 3D model low poly made with 3ds max. There was some leaks with face Z-sorting (i guess) so it was not well rendered. I found your blog and tried this engine. It works great but it makes my computer very slow. I’m running a mac G5 and i can do only… 5, 6fps maybe.

    Is there anything you/i could do to fix this ?

    Thanks a lot for your answers

    January 14th, 2009

  36. I use QuadrantRenderEngine.CORRECT_Z_FILTER ,it working. but this destroy my Memory , it use little time , my memory will max.
    I don’t know why, When I render normal it’s OK but When I use QuadrantRenderEngine I have problem.

    I want to use ‘QuadrantRenderEngine.CORRECT_Z_FILTER’ because my model don’t have problem.

    “How to clear memory” help me plz .

    February 22nd, 2009

  37. Chris Guin

    I’ve been using the CORRECT_Z_FILTER and it helps things tremendously :D . It appears to ignore particles, however. Anyone know how I can integrate RenderParticles into the algorithm as well as RenderTriangles? Thanks.

    February 24th, 2009

  38. Chris Guin

    Also, there’s an error (I think) in the zconflict method of QuadrantZFilter – the second if statement checks if q has testQuad set to true – it should be w, it looks like.

    February 24th, 2009

  39. Great renderer, but I found a bug.

    Seems like it does not like TriangleMesh3D objects that get Mesh deformations. I’ve got a Cloth-like test where each vert is given a WSphere (WOW engine 3D sphere with physics) and immediately on any physics based deform the engine will crash. I’m betting it has to do with self-intersection, but this is just an uneducated guess.

    Matt

    April 28th, 2009

  40. Terry Corbet

    I’m curious, when you decided to invest the time necessary to port Away3D’s “AnotherRivalFilter” did you look to see if either of these speedups could be used:

    a. move the filter() method — with all its dependencies of course — into an equivalent set of Alchemy calls;
    b. move that code into PixelBender — since there do not seem to be any for or while loops anyway — and try to heuristically perturb the degree of parallelization — perhaps just using the approximate square root of the number of primitives in the tree.list as the height and width of a source ByteArray constructed out of that primitive list?

    I don’t claim to know the code well enough, or the ‘gotchas’ of either Adobe Lab’s tool, but it appears that one or both of those techniques could be employed for something approaching a half-an-order-of-magnitude improvement in rendering for correct Z order conflict resolution short of refactoring and rewriting either 3D platform from the ground up.

    June 23rd, 2009

  41. Berni

    Hi!
    i´ve loaded a collada model with papervision, but it looks “bad” in some angles,, how can i solve this?
    here is my sample:
    http://www.zix.com.mx/Auto_Lv.swf
    thanks

    August 8th, 2009

  42. Berni

    Ok, i´ve managed to load correctly my model, but now, the problem is that the filters, alpha and bitmapLayerEffects, are gone!
    heres the new sample:
    http://www.zix.com.mx/Auto_Lv2.swf
    (notice how the sphere lost the blur filter after using the quadrantRender)
    could someone please help me?

    August 8th, 2009

  43. dbam

    No BitmapEffectLayer (per object) and no ViewportLayer effects (per layer) make dbam a dull boy…

    One year passed, and i got to the same idea as Leymon, mixing various “layers” (rendered views) over each other to get some glow-like effect over a spotlight-model.
    I’m far too tired to code now, but give some feedback ASAP.

    by the way, IMPRESSIVE posts and work You got piled up in Your blog Andy!!!
    all the thumbs up.

    December 29th, 2009

  44. dbam

    …just for the record.
    I did manage that two-way-render (one for hero view + one for effects) to work. Obviously, rendering two scenes is painfully slow.
    Finally i did a .pbj filter (that extracts objects with colorRGB) on the result bitmapViewport3D.bitmapdata chaining the process of getting the glow done.
    Just to let You know, it is almost as slow as the other method of two layers (a bit faster), but less code to handle two different scenes. (Has some obvious limitations too.)
    But, for now it works for the kind of stuff i was looking for. Hopefully, with the desktop release of FlashPlayer 10.1 (including working/real gpu support) all the Adobe Lab-tech will get pushed to the next level, right where it was planned to be from the beginning of AVM2.

    January 3rd, 2010

  45. steve

    I have identified a memory leak with using the QuadrantRenderEngine. I’ve identified the cause, and my solution seems to work.

    http://forum.papervision3d.org/viewtopic.php?f=15&t=1701

    February 9th, 2010

Reply to “Using QuadTrees In Papervision3D”