algorithm - Combining items into fixed sized groups for k-d tree -


i'm using k-d tree spacial partitioning in ray-tracer. want combine near-by primitives fixed-sized groups data in each group can deinterleaved , processed simultaneously using simd instructions. fast algorithm find (approximately) smallest fixed-sized groups?

ideally augment k-d tree building algorithm instead of adding separate pass, complicated fact primitives close primitives belong more 1 leaf node , can't have groups duplicate items because floating point precision errors mess shadows , reflections.

i figure i'm far first person try solution exists, relevant solutions found searching internet grouping objects deal point data , variable-sized groups.

one popular way group objects pick random object, add "closest" k objects group it. "closest" defined mean giving smallest surface area combined bounding box. can use hilbert curve distance; either distance on 3d curve between objects' centers, or in 6d space bounding boxes become points:

(x_min, y_min, z_min, x_max, y_max, z_max)

Comments

Post a Comment

Popular posts from this blog

javascript - RequestAnimationFrame not working when exiting fullscreen switching space on Safari -

request animation frame stops working when exiting fullscreen clicking on original space's safari window. fine if fullscreen mode canceled escape key or calling cancelfullscreen(). steps reproduce: open https://dl.dropboxusercontent.com/u/769042/prezi/safari-fullscreen.html click "draw raf", kittie appears click "fullscreen", go fullscreen click "draw raf", kittie appears go space original safari was, showing "click exit fullscreen mode", click anywhere, out fullscreen click "draw raf", nothing happens what handling click calling: window.requestanimationframe(draw); which draws on canvas context: function draw() { ctx.drawimage(img, math.random()*500|0, math.random()*400|0, 100, 100); } i checked .hidden , .visibilitystate, updated correctly. tested on osx 10.9.3, safari 7.0.4 (9537.76.4). has workaround/solution other switching old settimeout? this sounds webkit bug 88940 : using reque...
Read more

c# - How do I get the Nth largest element from a list with duplicates, using LINQ? -

i've seen in various stackoverflow answers can nth largest element in list doing var nthfromtop = items.orderbydescending().skip(n-1).first(); but wouldn't work if there no duplicates in list? if list contains duplicates, there way nth largest element (or set of elements) using linq? if not, efficient way in c#? to set of items equal nth largest item you'll need group items, order groups, , decrement n group size while n positive. when n reaches zero, you've hit group containing nth largest item. public static ienumerable<t> foo<t>(this ienumerable<t> source, int n) { return source.groupby(x => x) .orderbydescending(group => group.key) .skipwhile(group => { n -= group.count(); return n > 0; }) .first(); }
Read more

jsp - "Sending a redirect is forbidden after the response has been committed" in sendRedirect -

if(insertlen==6) { nextpag="&whichpage=/jsp/dealer/callcentre/careprocess.jsp" redirectpath += actionpath+nextpag; response.sendredirect(redirectpath); return; } else { nextpag="&whichpage=/jsp/dealer/callcentre/complaintfeedback.jsp"; response.sendredirect(redirectpath); } here when execute above, got following error : sending redirect forbidden after response has been committed may know why happening?
Read more