Databases
StackOverflow2013
Postsdbo
POOpenMP parallelization on a recursive function
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOpenMP parallelization on a recursive function
    text
    copied!<p>I'm trying to use parallelization to improve the refresh rate for drawing a 3D scene with heirarchically ordered objects. The scene drawing algorithm first recursively traverses the tree of objects, and from that, builds an ordered array of essential data that is needed to draw the scene. Then it traverses that array multiple times to draw objects/overlays, etc. Since from what I've read OpenGL isn't a thread-safe API, I assume the array traversal/drawing code must be done on the main thread, but I'm thinking that I might be able to parallelize the recursive function that fills the array. The key catch is that the array must be populated in the order that the objects occur in the scene, so all functionality that associates a given object with an array index must be done in the proper order, but once the array index has been assigned, I can fill the data of that array element (which isn't necessarily a trivial operation) using worker threads. So here's the pseudo code that I'm trying to get at. I hope you get the idea of the xml-ish thread syntax.</p> <pre><code>recursivepopulatearray(theobject) { &lt;main thread&gt; for each child of theobject { assign array index &lt;child thread(s)&gt; populate array element for child object &lt;/child thread(s)&gt; recursivepopulatearray(childobject) } &lt;/main thread&gt; } </code></pre> <p>So, is it possible to do this using OpenMP, and if so, how? Are there other parallelization libraries that would handle this better?</p> <p><strong>Addendum:</strong> In response to <a href="https://stackoverflow.com/questions/835893/openmp-parallelization-on-a-recursive-function/835974#835974">Davide's request for more clarification</a>, let me explain a little more in detail. Let's say that the scene is ordered like this:</p> <pre><code>-Bicycle Frame - Handle Bars - Front Wheel - Back Wheel -Car Frame - Front Left Wheel - Front Right Wheel - Back Left Wheel - Back Right Wheel </code></pre> <p>Now, each of these objects has lots of data associated with it, i.e. location, rotation, size, different drawing parameters, etc. Additionally, I need to make multiple passes over this scene to draw it properly. One pass draws the shapes of the objects, another pass draws text describing the objects, another pass draws connections/associations between the objects if there are any. Anyway, getting all the drawing data out of these different objects is pretty slow if I have to access it multiple times, so I've decided to use one pass to cache all that data into a one-dimensional array, and then all the actual drawing passes just look at the array. The catch is that because I need to do OpenGL pushes/pops in the right order, the array must be in the proper depth-first search order that is representative of the tree heirarchy. In the example above, the array must be ordered as follows:</p> <pre><code>index 0: Bicycle Frame index 1: Handle Bars index 2: Front Wheel index 3: Back Wheel index 4: Car Frame index 5: Front Left Wheel index 6: Front Right Wheel index 7: Back Left Wheel index 8: Back Right Wheel </code></pre> <p>So, the ordering of the array must be serialized properly, but once I have assigned that ordering properly, I can parallelize the filling of the array. For example once I've assigned Bicycle Frame to index 0 and Handle Bars to index 1, one thread can take the filling of the array element for the Bicycle Frame while another takes the the filling of the array element for Handle Bars.</p> <p>OK, I think in clarifying this, I've answered my own question, so thanks Davide. So I've posted my own <a href="https://stackoverflow.com/questions/835893/openmp-parallelization-on-a-recursive-function/836657#836657">answer</a>.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload