IRC log for #brlcad on 20170801

00:17.03Notify03BRL-CAD:mdtwenty * 70033 (brlcad/branches/opencl/include/rt/shoot.h brlcad/branches/opencl/src/librt/primitives/bool.cl and 3 others): skipping unevaluated partitions
00:18.06*** join/#brlcad https_GK1wmSU (~deep-book@169.55.27.131)
00:19.05*** part/#brlcad https_GK1wmSU (~deep-book@169.55.27.131)
00:38.53*** join/#brlcad sqrosuofcvzwzywq (~armin@dslb-094-216-164-255.094.216.pools.vodafone-ip.de)
00:41.13Notify03BRL-CAD:Marco-domingues * 10149 /wiki/User:Marco-domingues/GSoC17/Log: /* 31 July */
02:13.37*** join/#brlcad yukonbob (~bch@S0106b81619e90b96.ok.shawcable.net)
02:13.40yukonbobhello #brlcad
02:43.36*** join/#brlcad https_GK1wmSU (~deep-book@77.234.42.183)
02:44.37*** part/#brlcad https_GK1wmSU (~deep-book@77.234.42.183)
03:34.33*** join/#brlcad gabbar1947 (uid205515@gateway/web/irccloud.com/x-uthcarhicquzqbhn)
05:55.07*** join/#brlcad merzo (~merzo@20-21-132-95.pool.ukrtel.net)
06:45.42*** join/#brlcad Caterpillar (~caterpill@unaffiliated/caterpillar)
07:14.18*** join/#brlcad KimK (~Kim__@2600:8803:7a81:7400:8dd6:e12e:6013:7834)
07:15.00*** join/#brlcad KimK (~Kim__@2600:8803:7a81:7400:8dd6:e12e:6013:7834)
07:18.05*** join/#brlcad teepee (~teepee@unaffiliated/teepee)
07:27.36*** join/#brlcad teepee (~teepee@unaffiliated/teepee)
07:53.52*** join/#brlcad Stragus_ (~alexis@modemcable131.0-202-24.mc.videotron.ca)
08:14.30*** join/#brlcad merzo (~merzo@user-94-45-58-139.skif.com.ua)
08:25.19*** join/#brlcad Caterpillar (~caterpill@unaffiliated/caterpillar)
08:34.02*** join/#brlcad KimK (~Kim__@2600:8803:7a81:7400:c482:d704:f9cf:4675)
08:39.31*** join/#brlcad KimK (~Kim__@2600:8803:7a81:7400:c482:d704:f9cf:4675)
08:42.54*** join/#brlcad KimK (~Kim__@2600:8803:7a81:7400:c482:d704:f9cf:4675)
08:51.44*** join/#brlcad teepee (~teepee@unaffiliated/teepee)
09:11.44*** join/#brlcad teepee (~teepee@unaffiliated/teepee)
09:15.52*** join/#brlcad KimK_ (~Kim__@2600:8803:7a81:7400:c482:d704:f9cf:4675)
09:17.31*** join/#brlcad KimK_ (~Kim__@2600:8803:7a81:7400:c482:d704:f9cf:4675)
09:21.01*** join/#brlcad KimK_ (~Kim__@2600:8803:7a81:7400:c482:d704:f9cf:4675)
09:32.36*** join/#brlcad gabbar1947 (uid205515@gateway/web/irccloud.com/x-ltbxxbrtphejfhrl)
09:33.46*** join/#brlcad teepee (~teepee@unaffiliated/teepee)
10:30.52*** join/#brlcad teepee (~teepee@unaffiliated/teepee)
11:55.55Notify03BRL-CAD:Amritpal singh * 10150 /wiki/User:Amritpal_singh/GSoC17/logs: /* Coding Period */
12:02.13Notify03BRL-CAD:Amritpal singh * 0 /wiki/File:Bentrebar.png:
12:07.20Notify03BRL-CAD:Amritpal singh * 0 /wiki/File:PopimageUshapeRebar.png:
12:08.05Notify03BRL-CAD:Amritpal singh * 10153 /wiki/User:Amritpal_singh/GSoC17/logs: /* Coding Period */
12:09.25Notify03BRL-CAD:Amritpal singh * 10154 /wiki/User:Amritpal_singh/GSoC17/logs: /* Coding Period */
12:20.59*** join/#brlcad teepee (~teepee@unaffiliated/teepee)
13:22.06*** join/#brlcad gabbar1947 (uid205515@gateway/web/irccloud.com/x-uzhthiaatgjhxdcu)
13:35.38Notify03BRL-CAD:mdtwenty * 70034 brlcad/branches/opencl/src/librt/primitives/rt.cl: Fix bug in partitions shading. Shading closest partition
13:39.29*** join/#brlcad yorik (~yorik@2804:431:f720:4929:290:f5ff:fedc:3bb2)
13:39.45*** join/#brlcad vasc (~vasc@bl4-147-121.dsl.telepac.pt)
13:41.09Notify03BRL-CAD:Marco-domingues * 0 /wiki/File:Shade_closest_partition.png:
13:48.37Notify03BRL-CAD:Marco-domingues * 10156 /wiki/User:Marco-domingues/GSoC17/Log: /* 1 August */
14:16.26*** join/#brlcad mdtwenty (bc519789@gateway/web/freenode/ip.188.81.151.137)
14:21.57vaschey mdtwenty
14:22.07mdtwentyhello!
14:22.38*** join/#brlcad mdtwenty[m] (mdtwentyma@gateway/shell/matrix.org/x-zzjodrxmmmvwtbhh)
14:23.09vasconce you put the changes to skip unevaluated partitions and the bug fix for the closest partition on svn then tell me so i can look at the code
14:23.15vascabout bool_eval()...
14:23.35vascdid you see patch i posted on the patches tracker?
14:23.51vasc<PROTECTED>
14:24.22mdtwenty[m]I have commited the changes already in the opencl branch
14:24.58vaschttps://sourceforge.net/p/brlcad/patches/473/
14:24.58i5o[ BRL-CAD / Patches / #473 Eliminate gotos from bool_eval() ]
14:25.34vascapply this patch to brlcad trunk/ and try running your tests on that to see what's the performance difference vs the old code.
14:25.59vascif that's fast enough, then we can work on a simplified prototype in ANSI C to port to OpenCL later.
14:26.22vascwith a linearized binary tree in an array, instead of storing the expression tree in rpn format.
14:26.32vascso the tree would be in infix notation.
14:27.08vascit shouldn't even use more memory if we do it right.
14:27.43mdtwenty[m]hm okay I will apply the patch and test it
14:28.03vascok. i'll try to advance the pseudocode for the solution to speed this up.
14:28.58mdtwenty[m]yeah I think most of the bugs with the csg code are fixed now
14:31.19mdtwenty[m]the images match the results from the ANSI C code, although some scenes have missing geometry from the primitives that are not supported yet (goliath.g is one example of this, where some pipes are missing)
14:31.33vasci'm gonna need to know the first material in a solid so i can shade the primitives properly in the one-hit shader though.
14:31.45vascyeah pipe is used quite often.
14:32.15vascbut the code is kinda more complicated than that of regular primitive. that's why i didn't ask you to work on it.
14:32.28vascpipe is a composite primitive.
14:32.44vascits a list of segments of things.
14:33.37vascit would distract from the purpose of getting the csg working.
14:33.51vasclet's see...
14:34.16vasci need some data structure.
14:34.17mdtwenty[m]hm yes I remember you saying that porting that primitive would take some work
14:35.21vascin case you're curious you can look at src/librt/primitives/pipe/pipe_shot.c or something like that.
14:36.04vaschttps://svn.code.sf.net/p/brlcad/code/brlcad/trunk/src/librt/primitives/pipe/pipe.c
14:36.53vascif you do a 'wc -l' to get a linecount on the pipe.c file vs, say, ehy.c you would see that's it's a lot more complex.
14:37.10vascanyway...
14:38.07vascimplementing bool_eval() is easier than that.
14:38.15vascseriously.
14:40.36mdtwenty[m]hm yes lets first optimize the code and then I can look into porting some more primitives into OpenCL :)
14:42.58vascnah.
14:43.05vascwe want to optimize this to the max.
14:43.12vascscrew the primitives.
14:43.22vascwe only have one month.
14:44.01mdtwenty[m]ah yes, I meant eventually after the gsoc period
14:44.16vascmaybe next year. :-)
14:45.01vascand mind you, implementing pipe would be a breeze compared to the other main ticket item left to do... the brep intersector.
14:45.44vascgah.
14:45.49vascthat's another gsoc or two.
14:46.36vascif we get all that working, i think this will have a more complete GPU intersector than ANYTHING ELSE in the market right now.
14:47.01vascif it happens.
14:47.16vascanyway...
14:51.27vascwe'll use something like this bin tree representation
14:51.32vaschttps://github.com/mmp/pbrt-v2/blob/master/src/core/kdtree.h
14:51.33i5o[ pbrt-v2/kdtree.h at master · mmp/pbrt-v2 · GitHub ]
14:52.13vascthat's for a spatial kd-tree, but the data structure is more or less the same a bintree. in fact ours is simpler because we don't need to store as much data on the nodes.
14:59.31mdtwenty[m]okay, IIRC the idea is to store the jumps in the data structure, along with the boolean tree information?
15:00.14vascyes.
15:00.23vascthis is the data structure the code uses now:
15:00.37vascunion tree {
15:00.37vasc<PROTECTED>
15:00.37vasc<PROTECTED>
15:00.37vasc<PROTECTED>
15:00.37vasc<PROTECTED>
15:00.38vasc<PROTECTED>
15:00.40vasc<PROTECTED>
15:00.42vasc<PROTECTED>
15:00.44vasc<PROTECTED>
15:00.46vasc<PROTECTED>
15:00.48vasc<PROTECTED>
15:00.50vasc<PROTECTED>
15:00.52vasc<PROTECTED>
15:00.54vasc<PROTECTED>
15:00.56vasc<PROTECTED>
15:00.58vasc<PROTECTED>
15:01.00vasc<PROTECTED>
15:01.02vasc<PROTECTED>
15:01.04vasc<PROTECTED>
15:01.06vasc<PROTECTED>
15:01.08vasc<PROTECTED>
15:01.10vasc<PROTECTED>
15:01.12vasc<PROTECTED>
15:01.14vasc<PROTECTED>
15:01.16vasc<PROTECTED>
15:01.18vasc<PROTECTED>
15:01.21vasc<PROTECTED>
15:01.23vasc<PROTECTED>
15:01.25vasc<PROTECTED>
15:01.27vasc<PROTECTED>
15:01.29vasc<PROTECTED>
15:01.31vasc<PROTECTED>
15:01.33vasc<PROTECTED>
15:01.35vasc<PROTECTED>
15:01.37vasc};
15:01.39vascand this is what we'll use: (pseudo-code)
15:01.41vasc/ assume NOPs have been removed and all leafs are SOLIDs.
15:01.43vasc/ pseudo-code.
15:01.45vascstruct tree {
15:01.47vasc<PROTECTED>
15:01.49vasc<PROTECTED>
15:01.51vasc<PROTECTED>
15:01.53vasc<PROTECTED>
15:01.55vasc<PROTECTED>
15:01.57vasc<PROTECTED>
15:01.59vasc<PROTECTED>
15:02.01vasc<PROTECTED>
15:02.03vasc<PROTECTED>
15:02.05vasc};
15:02.07vascta-da.
15:02.09vasca linearized array binary tree.
15:02.24vascwhere nodes are either branches with binary ops (has_lchild = 1) or leafs with solids (has_lchild = 0)
15:03.10vascthe current code is a horrible, horrible waste of memory and has lotsa pointer chasing.
15:03.19vascwe're gonna fix that.
15:04.06StragusHaving the whole acceleration structure as a big linear blob of memory is good, and you can use relative offsets to jump around
15:05.06Stragus16 or 32 bits with a << 4 is pretty good. 32 bits is easier, 16 bits involves a complicated shuffling/ordering solution
15:05.08vascright. when it's a branch, left child is always at current_offset+1, and the right child is that current_offset+tree.rchild. or was that tree.rchild. i don't remember.
15:05.24StragusAh, or that
15:06.09vascso each tree node should fit into 32-bits.
15:06.18vasc4 bytes.
15:06.44vascinstead of... 4*2 + 8*3 bytes.
15:06.56vasc32
15:07.12vasc8x smaller.
15:07.22vascand not as much pointer chasing.
15:07.29vascso
15:07.42vascthat's the whole idea.
15:08.09vascnow the small detail of getting it to work.
15:08.29vasc"small detail"
15:08.52Stragus*nods* My raytracers always used a linear blob of memory for each graph. Another wonderful detail is that you can save the blob to disk and use "as is", you can use on both CPU and GPU directly, it just works
15:09.24vascyes. we'll use a simple recursive function the CPU to linearize this tree, and then we'll just copy that to the GPU.
15:10.33StragusLinearizing on CPU would be a good idea too
15:10.46Stragus(and it makes things easier, same data structure everywhere)
15:18.59vascmeh... the code for the kd-tree in pbrt is too complicated. i think I also saw this in Wald's thesis someplace.
15:21.47vascI think I first read about this in Gordon Stoll's SIGGRAPH presentation.
15:22.48vaschmmm...
15:23.09vasci probably has some of my own code someplace with this.
15:23.11vaschave
15:24.00mdtwenty[m]I've just tested your patch (https://sourceforge.net/p/brlcad/patches/473/) and it seems to match the current times with the version on the trunk
15:24.01i5o[ A 404 Error has Occurred ]
15:24.13vascok, but what about the times?
15:24.18vascoh
15:24.21vascgreat.
15:24.34vascso we got ourselves an algorithm without gotos.
15:24.36mdtwenty[m]goliath is the same (0.33 vs 0.33)
15:24.47vascwhich can't be used in OpenCL.
15:25.21vascnow we need an algorithm without gotos, wasted memory, needless pointer chasing, and no dynamic memory.
15:25.32mdtwenty[m]havoc (0.62 new version vs 0.63 in the trunk)
15:25.33vascthat takes care of the first problem.
15:25.35mdtwenty[m]so no big difference
15:25.47vascyeah, that could just be measuring error.
15:25.53vascshould be anyway.
15:26.33vascyou wanna code the ANSI C prototype?
15:27.09mdtwenty[m]yeah I can give it a try!
15:27.13vascwe basically need to code a tree builder and a tree traverser.
15:31.06vasci was trying to find some of my old code so you could use that as a base.
15:33.26vascah well.
15:33.46vascdunno if it survived my HD crash 3 years ago.
15:37.24vascmeh. finding mostly code snippets of bin trees accessed with shifts.
15:37.37vascbut that means it has to be a balanced bin tree, or it wastes a lot of memory so...
15:38.52vascanyway
15:41.12vaschttps://pastebin.com/R4SZpDMD
15:41.13i5o[ [C] #define OP_UNION          0         /**< @brief  Binary: L union R */  #define OP_INTERS - Pastebin.com ]
15:41.15vascthis should help
15:41.42vasci don't want you to waste a lot of time reinventing things that have already been invented.
15:41.53vascso we can use the remaining time to actually invent new stuff.
15:41.57vasc:-)
15:43.49vascstart by building the tree builder, that converts a trunk/ union tree into that array of uints with the layout i mentioned before, and a function to print it to examine the output.
15:44.38vascyou can use the KdTree() constructor and recursiveBuild() function I put in the pastebin from PBRT as a reference.
15:45.04vascbut you'll need to use shifts and things like that to store things in 32-bits.
15:45.19vascbecause OpenCL does not have support for bitfields in structs either.
15:45.23vascgotta love OpenCL.
15:46.08StragusManaging the bits yourself sometimes allows producing better code than with bitfields anyway
15:46.18vaschttps://stackoverflow.com/questions/9033947/why-are-bitfields-not-allowed-in-opencl
15:46.19i5o[ bit fields - Why are bitfields not allowed in OpenCL? - Stack Overflow ]
15:47.14vascah so it's because of endianess? bah.
15:47.29vascthen what about ints? those would need to be converted too...
15:47.36vascscratches his head.
15:48.01vascso it's just because of padding it seems.
15:49.18vascanyway the idea is the first bit says if its a branch or a leaf. if it's a branch the next 3 bits define the binary OP, and the remaining bits where right child is.
15:49.37vascif it's a leaf, then the other 30 bits have the solid id.
15:49.39vascthat's it.
15:49.49vasc31 bits actually
15:50.15vasci hope 2G solids are enough.
15:51.22vascand like 256 M bool nodes.
15:51.37vascif it's not enough we can use 64 bits.
15:53.49vascmdtwenty[m], thx for conducting the tests.
15:53.59vasci'll look at your code now.
15:54.27mdtwenty[m]no worries :)
15:54.45mdtwenty[m]i think I got the idea.. I will start working on this and see what I can get
15:55.40vascsure. if your ANSI C prototype code turns out to be faster than the one in trunk/ then we can ask Sean to test it and maybe we'll use it in the main ANSI C path as well.
15:56.10vascit might be because the nodes are going to be smaller and the memory accesses more coherent.
15:56.33vascalthough i haven't looked at how the code allocates the nodes yet.
16:00.17vascyou can use the RPN bool patch I made way back when to see which functions you need to implement to completely replace the existing boolean trees in trunk/.
16:02.04mdtwenty[m]okay thanks! I'll keep that in mind
16:02.44vascbut like i said, start with the tree builder and the print function.
16:02.56vascto debug.
16:13.22vascduh... ok, i see. the existing code has memory pool for tree nodes if the nodes get deleted and reallocated. but fresh nodes are just allocated with posix_memalign() or calloc()...
16:13.33vascyeah that should make them memory coherent. not.
16:13.53vascwell maybe if the malloc implementation is smart. which it usually isn't.
16:15.19*** join/#brlcad Caterpillar2 (~caterpill@unaffiliated/caterpillar)
16:15.44vascyes... the results of changing this code should prove quite interesting.
16:16.23vascnotice how my code which always evaluates the entire expression actually was either the same speed or faster in the simpler expressions.
16:17.00mdtwenty[m]i hope so!
16:17.55mdtwenty[m]one thing that i noticed the other day was that the max rpn tree lenght in the havoc scene was 583 IIRC
16:19.16vascyeah that doesn't seem so good.
16:19.31vascwell you know there are several possible strategies to optimize the tree evaluator.
16:21.47vascsay a solid is never intersected by any ray. so why evaluate that for every partition or whatever?
16:22.10vascit's possible to optimize the tree in runtime or prior to render.
16:22.49StragusA linear blob with small offsets rathre than pointers, all packed in memory, will definitely be faster on the CPU
16:23.33StragusAnd you can use something like a 3D space filling curve to sort data so it's spatially close, better filling cache lines. I remember getting a few extra percents from that
16:25.13vascyeah none of the buffers are in z-order. that likely has a negative impact.
16:25.39vasci also need to reduce the amount of memory used in between stages.
16:26.48StragusIf you ever want some pretty fast space filling curve code: http://www.rayforce.net/ccspacecurve.c  http://www.rayforce.net/ccspacecurve.h
16:27.01vascabout using SoA vs AoS...
16:28.07vasconce the code is cleaned up we might try that.
16:28.29vascbut right now i'm more concerned about thread divergence and poor usage of capacity.
16:28.47StragusYup, that's really something for the final touch
16:28.57Stragus(I gained 2-3% with that, woohoo)
16:29.39vasci had like order of magnitude improvements once because full GPU units weren't being used because of divergence.
16:30.00vascthat one can really bite.
16:30.42StragusInstead of testing 32 rays against a single sector or primitive, have you considered one warp testing one ray against 32 sectors or primitives?
16:30.58StragusFor highly incoherent rays, that seems like a better idea than trying to make coherent non-diverging bundles
16:31.27Stragus(replace the 32 with 4 or 8 on CPUs, 64 on AMD, etc.)
16:32.00vascwell right now the code only does primaries. well it's generic enough to be used with any rays, but those are the only rays the generator generates.
16:32.39vasci've had a lot of luck with sorting rays to decrease divergence.
16:33.19StragusReally?... Sorting rays either eat through your global memory banwidth, or you can't sort enough in on-chip shared memory
16:33.37StragusFor me, it was always faster to just trace incoherently than to bother sorting them
16:33.39vascin my own engine i actually fudged the RNG for the ambient occlusion rays so that those are more coherent. but don't tell anyone that... :-)
16:33.55StragusBut that could change if the acceleration structure was designed to test one ray against 32 primitives, instead of the other way around
16:34.06StragusEh, I did the same thing
16:34.12vascahah
16:35.02vascwell the sorting is useful if you have a fast sort.
16:35.09vascdid you try using the CUB sort?
16:35.20StragusThe problem wasn't the fast sort, the problem was the global memory banwdith
16:35.28vascoh that?
16:35.33StragusI could trace incoherent rays for the same amount of bandwidth as sorting them
16:35.34vascyou use compress-sort-decompress.
16:36.29vaschave you read this paper?
16:36.30vaschttp://www.keldysh.ru/pages/cgraph/articles/dep20/publ2010/GPU-RayTracing.pdf
16:36.32StragusAssuming rays bouncing everywhere, how do you compress the origin, vector and other contextual information about that ray's purpose?
16:36.51vasclook at that paper. :-)
16:37.29StragusThe "compression" is for the sort, sure
16:37.52StragusBut the write,read,write,read for bundling rays takes a lot of bandwidth
16:39.44StragusConsidering the typical incoherent ray for me had to touch about ~17 cache lines of 32 bytes...
16:39.51Stragus(if I remember the metric correctly)
16:40.17vaschm
16:40.21vascwell you know
16:40.37vascfor my own render pipeline i only use that for incoherent rays.
16:41.19vascalso i think it's not just a problem of memory coherence but of scheduling as well
16:41.38vasclike, adjacent rays typically have similar complexity.
16:42.12StragusRight, less waste from threads having nothing to do
16:42.43StragusWell, like I said, if I had to trace a ton of incoherent rays again, I would just use a different acceleration structure
16:42.52StragusTest a single ray against batches of 32 triangles instead
16:46.21vasci once read a poster by Yoon. he basically ran all the intersections against simplified geometry (like a convex hull of the geometry) to get an estimate for the hit points.
16:46.34vascsorted those in z-order. and then used that to schedule the rays.
16:46.52vascit was an out-of-core renderer. so it made even more sense there.
16:47.24vascactually he used a simplified mesh, not the convex hull now that i think of it.
16:48.04vascthe ray against triangles... well.
16:48.14vascthe thing is... triangles are "fatter" than rays.
16:49.08StragusBut it's a lot easier to make coherent bundles of 32 triangles than 32 rays ;)
16:49.25Stragus(assuming global illumination-like incoherent tracing)
16:49.45vasc3 vertexes with 3 coordinates of 4 bytes vs 2 vertexes with 3 coordinates.
16:49.53vascand that's not even assuming the rays have same origin.
16:50.32StragusRays also need to track contextual information, so you can accumulate back to whatever bounce it came from
16:50.55vascsure an id can take care of that.
16:50.58Stragus(assuming you short and shuffle them)
16:51.02Stragussort*
16:51.57StragusI don't know, there's a lot of potential for an acceleration structure designed to minimize the count of bundles of 32 triangles being tested (in the global cost function, 1 triangle in a sector has the same cost as 32)
16:53.08vasci think i mentioned this in some slides for a class i gave sometime.
16:53.43vasci was showing how you can reduce the amount of math ops in the intersections when testing with same ray origin vs same triangles and the like.
16:54.08vasci remember that was also less nice for the many triangle approach.
16:54.29vascthing is, when the many rays don't have the same origin though, then it changes.
16:55.15StragusRight sure, highly coherent rays (including with same origin) is a different problem with a different optimal solution
16:57.39vaschttps://drive.google.com/file/d/0B85Rkmt7rnCTWGVNUlhaZzZyQkU/view?usp=sharing
16:57.40i5o[ aula.pdf - Google Drive ]
16:57.55vascpage 6.
16:58.02vasci gave that class like 5 years ago.
16:58.59vasci remember i analyzed that as i thought it was interesting. and ran some tests. then i gave it up. :-)
16:59.31vascoh... what was that other thing...
16:59.38vascright.
16:59.53vascray-triangle fan and ray-triangle strip optimized intersection routines.
16:59.59vasci was looking at those back then too.
17:00.34vasci only found like one decent paper for each one.
17:00.58vascit's another way to reduce the bandwidth required for the triangles right?
17:03.10vascso i looked at this one: http://gamma.cs.unc.edu/RS/paper_rt07.pdf
17:03.31vascbut i dunno it seemed kinda lame to me, that you needed to build a BSP
17:04.32vascactually an skd-tree but whatever.
17:05.31vascit seemed lame to me. to use axis aligned separators.
17:05.44vascyou already have the planes defined by the triangles or whatever.
17:06.00vascso i also ignored that idea.
17:06.09*** join/#brlcad ``Erik (~erik@pool-100-16-14-17.bltmmd.fios.verizon.net)
17:11.07vascthere's all sorts of tricks you can ues.
17:11.09vascuse.
17:11.41vasclike... you know how they say for primary rays since the origin is always the same, only store the direction? well i only stored the index used to generate the ray.
17:11.58vascthen i have generator functions for rays. primaries, shadows, ambient occlusion the works.
17:12.03vascso the engine was all specialized.
17:13.37vascah whatever. i'm not gonna pick that up again.
17:13.50vasci've decided if i ever rewrite it, i'm gonna do everything differently.
17:14.43vascso Stragus, are many-triangle intersections in fashion again?
17:17.43StragusI have no idea what's in fashion. I almost never read papers, I just have fun ;)
17:18.11vascevery once in a while something comes out that makes a difference. that's why i read papers.
17:18.29vascits usually not a new idea, but, the twist makes the difference.
17:18.39StragusAnd really, I would recommend using a graph rather than a tree
17:18.49vascfor the geometry right?
17:18.52StragusA tree implies a stack, which implies per-thread stores and loads, and that's terrible
17:19.00StragusFor the space partitioning, yes
17:19.50vascisn't that like a tree with ropes like they usually call it? well at least that's how Havran calls it.
17:20.19StragusNo idea if there's a fancy term for it. But what I use is a graph, sectors connecting to other sectors, there's no tree
17:20.56vascthen how's the partitioning done? does it still use split planes somehow?
17:21.03StragusThe idea being to avoid all per-thread memory stores, until you have your intersection point and you need to do something with it
17:21.44StragusI use axis-aligned sectors, which can overlap in space, and each facet of a sector can either connect to another sector or a "node" with a splitting plane to decide where to go next
17:22.13StragusThere are other ways, that's not ideal for the one-ray-against-many-triangles approach
17:22.25StragusBut just avoid a per-thread stack, no matter how you do it
17:22.39vasci've read something similar in papers from the 1980s but i can't say i remember other people working on that. it seemed like a cool idea when i read it.
17:23.30vascback then a lot of people were trying to get ray tracing to scale in MPP architectures.
17:24.13vasclike Transputers or that Intel machine... the one with i860s.
17:24.21StragusTracking a stack in L1 on many-cores no-SIMD chips is no big deal
17:24.35StragusBut the situation is different with GPUs and modern wide SIMD
17:24.45vaschttps://en.wikipedia.org/wiki/Intel_iPSC#iPSC.2F860
17:24.46i5o[ Intel iPSC - Wikipedia ]
17:25.13vascthe Intel Paragon.
17:25.45vascmaan... they spent a lot of time trying to minimize inter thread communications and ops.
17:26.24vascwell i dunno if those processors actually had caches.
17:26.26StragusUsually, for massively parallel software, you just write code to _avoid_ requiring low latency inter-thread/device communication
17:27.14StragusLike for computational fluid dynamics, it's better to compute the same cells redundantely while you receive results from other devices from two time steps ago
17:27.27vascah right. the i860 had caches but early Transputers did not.
17:28.12vascah CFD. i always wondered how they implemented the data structures for the multi-grid solvers with AMR in those.
17:29.00vascever seen this?
17:29.01vaschttps://www.youtube.com/watch?v=vYA0f6R5KAI
17:29.03i5o[ GPUs to Mars: Full-Scale Simulation of SpaceX's Mars Rocket Engine - YouTube ]
17:29.03StragusAMR?
17:29.13vascAdaptive Mesh Refinement
17:29.34vaschttps://en.wikipedia.org/wiki/Adaptive_mesh_refinement
17:29.34i5o[ Adaptive mesh refinement - Wikipedia ]
17:32.29vaschttps://youtu.be/vYA0f6R5KAI?t=1510
17:32.31i5o[ GPUs to Mars: Full-Scale Simulation of SpaceX's Mars Rocket Engine - YouTube ]
17:32.31vascanimated
17:33.14vascis fascinated with grids.
17:38.53*** join/#brlcad KimK_ (~Kim__@2600:8803:7a81:7400:c482:d704:f9cf:4675)
18:33.13vascmdtwenty[m], the code changes you made to branches/opencl seem to be fine at a glance.
18:40.24Notify03BRL-CAD Wiki:Mariomeissner * 10157 /wiki/User:Mariomeissner/logs:
18:40.34mdtwenty[m]I noticed that some code from my previous patches still had indentation issues, so I fixed that and used it to make my first commit, like a test commit :)
18:41.40mdtwenty[m]the code to skip unevaluated partitions should be okay, I did some testing and it iterates only over the evaluated partitions, although that didn't make that much of a difference in performance
18:43.36vasci remembered now that it might also be possible to reuse the forward_pp in the partitions, so next_evalpp might not be necessary.
18:44.31vascin rt_boolfinal.
18:45.11vascyou just need to cache the partitions[current_index].forw_pp in a variable, which could be named next_index, before writing over the value.
18:45.43vascand then in the loop you get the next index from that cached variable instead of from the partition
18:47.39vascit should only make a difference in scenes with a lot of depth complexity.
18:47.52vascmaybe in golliath it makes a difference?
18:49.35mdtwenty[m]hm it has almost the same, but to be fair I only tested with the view az:35 el:25
18:50.02mdtwenty[m]front view could have a more noticeable difference
18:51.19mdtwenty[m]and I think that it is possible to discard the use of next_evalpp now that you mention it
18:52.08mdtwenty[m]and maybe we dont even need to cache the forw_pp, since I could only update the forw_pp of the last partition evaluated
18:52.13vascif we can reuse the foward_pp it would save memory in the partitions.
18:53.25vascwell you need to save it before you override it, because otherwise when the for (;;) loop iterates the value won't be correct.
18:54.12vascuint next_index;
18:54.26vascfor (uint current_index = head; current_index != UINT_MAX; current_index = next_index) {
18:54.35vasc<PROTECTED>
18:54.37vasc<PROTECTED>
18:55.15vasc<PROTECTED>
18:55.20vascoh i see what you mean.
18:55.30vascyeah it should be no problem.
18:56.13vascno need for the variable even.
18:57.50mdtwenty[m]yeah :) I will update it
19:04.06vasci was also looking at if it was possible to remove the back_pp index by caching the previous index in a variable wherever that is used.
19:04.28vasca lot of times algorithms with double-linked lists aren't actually necessary.
19:04.49mdtwenty[m]IIRC back_pp was only used in 1 condition in boolweave
19:05.22vascits used in boolweave and rt_defoverlap
19:07.14mdtwenty[m]oh yes, right
19:07.50mdtwenty[m]but I think that could be cached in a variable
19:11.16vasci'm not so sure about that..
19:11.24vascthe boolweave case sure.
19:11.30vascbut i'm not certain about defoverlap.
19:12.00vascbecause it doesn't iterate the list using the pointers
19:12.03vascit uses the ids
19:12.38vaschm
19:12.43vascyes it might also be possible
19:13.13vascby passing it the index to the previous partition via default_multioverlap in boolfinal
19:14.08vascso that would shave off like 8 bytes in each partition with these two modifications.
19:14.42vasci also have an idea to shave off like half the memory used in the struct hits in the partitions so.
19:15.08vascover half actually
19:15.22vascso the struct partition should become less than half the size.
19:20.12vascit seems like soon enough we'll have a our first generation system.
19:21.03vascthe only thing which might make things slower is the bitvectors. or not.
19:21.23vascit think it will depend on how sparse the bitvectors are.
19:21.51vasci suspect they'll be faster on average than if we used lists.
19:22.09vascit also makes memory management easier.
19:22.41vascoh right, nearly forgot
19:23.10vascwe're gonna need to make an array with uints, one uint per solid, where the uint has the id of the first region.
19:23.23vascso i can shade the materials in single-hit mode properly.
19:23.40vascits only necessary in single-hit mode.
19:24.01vascyou prolly noticed its shading everything white/gray in single-hit mode right now.
19:24.25vascand i can't remember anything else.
19:24.38vascbut there's plenty of optimizations we can do afterwards.
19:24.50mdtwenty[m]yeah I noticed it, when it wasn't white/gray was every solid it the same color
19:24.52Notify03BRL-CAD:n_reed * 70035 brlcad/trunk/src/tclscripts/checker/CMakeLists.txt: Add initial check command test script.Currently runs the check Tcl-command in mged (mged -a nu -c) to checkbasic invocation behavior, and also subtraction behavior on two simpleoverlap cases.No args, but finds check.tcl by CHECKER_DIR environment variable.Doesn't run check.sh. Test databases and overlap directories are writtenout by the
19:24.54Notifytest script itself.
19:24.55vascoh, right, i also need to fix the lights.
19:24.56Notify...
19:28.23mdtwenty[m]did you ever tried to render the havoc scene with your workstation GPU? I was curious about what the difference in time  would be
19:29.06vascit's bad...
19:29.14vascthere's too many roundtrips.
19:29.32vascthose can be fixed, but it requires a reduce algorithm.
19:29.42vasci think its better not to focus too much on that right now.
19:29.53vascwe can just focus on the CPU performance.
19:30.11vasci can later give you a piece of code with reduce for you to try out the difference.
19:30.30vascbut the license might not be compatible for wider distribution.
19:30.41vasclet's see...
19:30.53vascyeah i got that here.
19:32.10vascah we don't use the reduce, prolly just scan.
19:32.37vascthe reduce is a sum, and the scan is prefix sums.
19:32.47vaschttps://en.wikipedia.org/wiki/Prefix_sum
19:32.48i5o[ Prefix sum - Wikipedia ]
19:34.03vascso we can compute the offsets quickly on the GPU side without doing memory transfers.
19:36.00vasci.e. this code:
19:36.01vasc<PROTECTED>
19:36.01vasc<PROTECTED>
19:36.01vasc<PROTECTED>
19:36.01vascBU_ASSERT((counts[i-1] % 2) == 0);
19:36.01vasch[i] = h[i-1] + counts[i-1]/2;/* number of segs is half the number of hits */
19:36.03vascif (counts[i-1]/2 > max_depth)
19:36.05vasc<PROTECTED>
19:36.07vasc<PROTECTED>
19:36.09vascin clt_Frame()
19:36.46vascoh... except it does two things it computes the max and it does the prefix sums.
19:36.58vascthe max_depth is a sort of reduce i guess.
19:40.05vascwell enough of that
19:40.42vasckeep me notified of your progress on the ANSI C bool_eval() then mdtwenty[m]. i'll see if can work on the lights this week.
19:41.23vasc<PROTECTED>
19:41.38mdtwenty[m]Yeah I will update you as soon as I have some progress
19:41.51vascok see you later!
19:42.08mdtwenty[m]see you later!
19:44.09*** part/#brlcad mdtwenty[m] (mdtwentyma@gateway/shell/matrix.org/x-zzjodrxmmmvwtbhh)
19:59.45*** part/#brlcad mdtwenty (bc519789@gateway/web/freenode/ip.188.81.151.137)
20:05.54*** join/#brlcad mdtwenty[m] (mdtwentyma@gateway/shell/matrix.org/x-zzjodrxmmmvwtbhh)
20:15.04*** join/#brlcad yukonbob (~bch@S0106c8fb2656f971.ok.shawcable.net)
20:15.09yukonbobhello #brlcad
22:10.05*** join/#brlcad yukonbob (~bch@S0106c8fb2656f971.ok.shawcable.net)

Generated by irclog2html.pl Modified by Tim Riker to work with infobot.