| 00:35.26 | *** join/#brlcad sofat (~sofat@202.164.45.212) |
| 00:40.19 | Stragus | You really should focus on a way to make this work in a single pass |
| 00:40.41 | vasc | i think that would require a miracle |
| 00:41.10 | vasc | have you seen how the regular algorithm works? |
| 00:41.21 | vasc | calling it a single "pass" is a misnomer |
| 00:41.31 | Stragus | I mean a single raytracing pass |
| 00:41.34 | vasc | the same hit points are looped over and over and over again |
| 00:41.55 | Stragus | Fine, at least gather the raytracing hits just once |
| 00:42.09 | Stragus | Any kind of sorting obviously involves revisiting hits multiple times |
| 00:42.14 | vasc | that means buffers |
| 00:42.22 | vasc | lots of buffers |
| 00:42.31 | vasc | the classical time vs space tradeoff |
| 00:42.58 | Stragus | Hum yes, that's true in some ways |
| 00:43.10 | vasc | two z buffers two color buffer and one stencil buffer |
| 00:43.39 | Stragus | Z buffers?... |
| 00:43.48 | Stragus | Just gather and buffer all hits, sort, process |
| 00:44.08 | vasc | you need to store the backs and the fronts of objects |
| 00:44.15 | vasc | so you can do the csg |
| 00:44.19 | Stragus | That's the hits you buffer |
| 00:45.09 | vasc | if i had those z-buffers i don't think i would need the per pixel hit list at all |
| 00:45.51 | vasc | you know... the DYNAMIC one |
| 00:46.18 | vasc | i haven't quite gotten the peculaliar of these methods yet |
| 00:46.22 | Stragus | Geometry is often flawed, it's possible to: Enter A, Enter B, Exit A, Exit B |
| 00:46.26 | vasc | some claim to be O(kN) |
| 00:46.29 | Stragus | So you do need to buffer stuff |
| 00:46.47 | vasc | the 1989 one said its complexity was based on the number of segments |
| 00:46.55 | vasc | per primitive |
| 00:46.56 | vasc | max |
| 00:47.16 | vasc | that's why you need those two buffers |
| 00:47.19 | vasc | and the stencil bits |
| 00:48.04 | Stragus | How many CSG primitivies can you have simultaneously with these stencil bits? |
| 00:48.14 | vasc | depends on the paper |
| 00:48.28 | Stragus | I mean... if you have 8 CSG primitives, then you could use a 8 bits stencil buffer to track if you are in/out of each object |
| 00:48.32 | Stragus | That's a little limited |
| 00:48.45 | vasc | the bits are used to encode which state of the CSG tree you are in |
| 00:48.57 | vasc | not the primitive per se |
| 00:49.25 | Stragus | Thinking. |
| 00:49.35 | vasc | better ways of storing the csg tree mean more objects in same bits |
| 00:50.23 | Stragus | Right, I see what they mean, with the object-based space partitionning |
| 00:50.26 | vasc | log2(n+2) stencil bits for number of primitives in expression for blister |
| 00:50.48 | vasc | which is the sorta crappy compress one |
| 00:51.37 | vasc | if you read the rossignac paper |
| 00:52.00 | vasc | he encodes the tree in a way that you can encode 10^38 primitives in 7 stencil bits |
| 00:52.52 | Stragus | You'll want a 32 bits integer per ray anyhow, for efficient memory access, so that should be plenty |
| 00:53.52 | Stragus | I'm not informed enough to know if all that is really preferable to buffering hits in shared memory and sorting |
| 00:54.27 | vasc | i haven't wrapped my head around this properly yet |
| 00:54.32 | vasc | quite |
| 00:54.39 | vasc | it probably depends |
| 00:54.48 | vasc | its sorting and more sorting vs buffers |
| 00:55.13 | vasc | and the sorting may have dynamic reallocs |
| 00:58.08 | vasc | i still haven't got how the sorting would be done |
| 00:58.59 | vasc | http://i.imgur.com/YwIBlpt.png |
| 00:59.02 | vasc | i don't get that |
| 00:59.14 | Stragus | Probably some insertion sort since the hits will always be nearly sorted |
| 00:59.50 | vasc | do i need like an array of size num_primitives+1 |
| 01:00.00 | vasc | i mean a 2d array |
| 01:00.18 | Stragus | Hum, no |
| 01:00.30 | vasc | or a 1d list of tuples with 1+n_primitives elements |
| 01:00.37 | vasc | bits |
| 01:01.26 | vasc | like {distance, prim0bit, prim1bit,....} |
| 01:01.27 | Stragus | Let's assume you have some struct able to store 16 hits. Each ray is born which a bunch of such structs in shared memory. If they are exausted, then it's allocated dynamically from some global static buffer with atomics |
| 01:01.46 | vasc | i'm just trying to understand this. in c. |
| 01:01.53 | vasc | or c++ |
| 01:02.10 | vasc | then you apply that Roth table |
| 01:02.34 | vasc | and filter stuff out |
| 01:04.10 | Stragus | The struct should hold whatever information you need to register for each hit |
| 01:04.21 | Stragus | Distance is obviously required for sorting |
| 01:04.42 | vasc | yeah but what else do i need to annotate the hits with |
| 01:04.52 | vasc | and how to generate that table for a tree |
| 01:05.00 | vasc | and how to apply the tree table to the hits |
| 01:05.08 | vasc | to transform and then filter them |
| 01:05.27 | vasc | at least the list length doesn't seem to increase in the temp steps |
| 01:05.49 | vasc | also |
| 01:06.16 | vasc | from what i read you can compute if something is in/out by doing that dot(r.d,n) on the normal of each hit point |
| 01:06.38 | vasc | so you don't need to store the info on cols 1,2 at all |
| 01:06.47 | vasc | you can compute it with lots dot products |
| 01:07.39 | vasc | so the first bullet and second bullet is tame |
| 01:07.44 | vasc | in fact 1 is kinda done |
| 01:07.50 | vasc | well 2 actually |
| 01:07.52 | vasc | already |
| 01:08.03 | vasc | just not the in/outs but that's just doing the normals with dot products |
| 01:09.02 | vasc | so now we need that Roth table |
| 01:09.09 | vasc | but for a TREE |
| 01:09.44 | vasc | hm remembered one bit |
| 01:10.21 | vasc | better to have that per primitive tupples thingie after all |
| 01:11.21 | vasc | more dynallocs |
| 01:11.28 | vasc | well at least this one is easy to compute |
| 01:11.48 | vasc | i'm kinda curious how the current code actually does it again |
| 01:11.50 | vasc | *shudder* |
| 01:11.55 | vasc | last time i tried to read it was bad |
| 01:14.52 | vasc | time to fire old netbeans to swim into the noodlestream of BRL-CAD boolean eval |
| 01:19.11 | vasc | 2118 lines of code |
| 01:20.04 | vasc | maybe i should print it and go read it at the beach |
| 01:20.07 | vasc | it just doesn't compute |
| 01:20.57 | vasc | http://brlcad.org/websvn/filedetails.php?repname=BRL-CAD&path=%2Fbrlcad%2Ftrunk%2Fsrc%2Flibrt%2Fbool.c |
| 01:21.32 | vasc | and loads and loads of dynamic linked lists |
| 01:22.37 | vasc | rt_boolfinal and rt_weave0seg are the ones that matter |
| 01:22.58 | vasc | i mean rt_boolfinal and rt_boolweave |
| 01:23.52 | vasc | i think i managed to remove the gotos of rt_boolweave once |
| 01:25.22 | vasc | maybe i could try applying the automatic man-bot code cleaner on that code |
| 01:25.26 | vasc | just like i did on the solver |
| 01:26.26 | vasc | turns BRL-CADish code into cleanish nearly OpenCL compatible code |
| 01:27.39 | vasc | i'm good at that. i turn my brain off and become a man-compiler |
| 01:28.06 | vasc | a great skill to have as a maintainer |
| 01:28.13 | vasc | not much of a developer skill though |
| 01:28.50 | vasc | must have been from reviewing reformatting, fixing like 2-3 patches a day for like 5 years for freeciv |
| 01:28.53 | vasc | i got good at that |
| 01:29.32 | vasc | first to check if those two functions are all we need |
| 01:29.38 | vasc | then time to get the hatchet |
| 02:09.18 | vasc | remove unused functions and bug printfs done |
| 02:09.30 | vasc | 1578 LOC |
| 02:09.42 | vasc | that's 540 otu |
| 02:09.44 | vasc | out |
| 02:09.59 | vasc | still too bleeping complicated |
| 02:10.22 | Stragus | I'm not fond of the way the code was written |
| 02:10.39 | Stragus | I would have broken stuff into static inlined functions... |
| 02:10.57 | vasc | next i'm gonna do inlining of small functions and cleanup more unused code |
| 02:11.22 | Stragus | In their defense, compilers might not have been able to do proper inlining when it was written |
| 02:11.27 | vasc | but its still a mess |
| 02:12.11 | vasc | try porting *that* to opencl... |
| 02:12.28 | vasc | %s/register //g |
| 02:12.29 | Stragus | I would understand the purpose and rewrite, but that's me |
| 02:12.49 | vasc | it's a real pain to rewrite this |
| 02:12.56 | vasc | to convert it into opencl |
| 02:13.02 | vasc | that's why i wanted something whole new |
| 02:13.16 | Stragus | I would find it easier than trying to work with the existing code |
| 02:13.22 | vasc | new to BRL-CAD at least. just like i did for bvhs and bots. |
| 02:13.27 | Stragus | It's just... not designed for GPUs, or for parallel hardware |
| 02:13.35 | Stragus | Right |
| 02:13.37 | vasc | i have been doing a mixed approach. |
| 02:14.14 | vasc | some is conversion of brl-cad code to opencl. partly the primitives because we had specific requirements on error output on those |
| 02:14.26 | vasc | and partly because the alternatives aren't that much better |
| 02:14.38 | vasc | except the triangles |
| 02:14.40 | vasc | the bot |
| 02:14.43 | vasc | i did that one |
| 02:14.46 | vasc | even though its not complete |
| 02:14.50 | Stragus | Primitives were just math, that's fine |
| 02:14.51 | vasc | it doesn't support the plate mode and so on |
| 02:15.00 | Stragus | This dynamic allocation stuff to manage hits and segments is... bad |
| 02:15.03 | vasc | then i used the bvh instead of whateverr |
| 02:15.13 | vasc | well yeah you saw the code right |
| 02:16.15 | Stragus | Even if it were CPU code, I would never malloc() every little thing, I would use a static buffer that grows if and when required |
| 02:16.20 | vasc | http://pastebin.com/2mTFicUL |
| 02:16.24 | vasc | this is the calling code |
| 02:16.25 | Stragus | doesn't like that code |
| 02:16.54 | vasc | just there it moves segments from one list to another, then another then another |
| 02:17.05 | vasc | and that's without the boolean processing |
| 02:18.33 | vasc | http://pastebin.com/1cfyRbHe |
| 02:18.37 | vasc | this is the boolean weaving |
| 02:18.48 | vasc | after i removed the debug messages. all over 500 LOC of them |
| 02:18.59 | vasc | i still left comments... |
| 02:19.16 | vasc | more list SHIT |
| 02:19.28 | vasc | double linked list SHIT and GOTOS |
| 02:19.46 | Stragus | Eh yup |
| 02:20.02 | vasc | and guess what it uses that per ray bitvector which states ALL intersected solids that i worked so hard to remove |
| 02:20.35 | vasc | it even has handlers |
| 02:20.37 | Stragus | A per-ray array of bits, N bits for N primitives? |
| 02:20.39 | vasc | function pointers |
| 02:20.55 | vasc | per ray array of bits. N bits for N primitives. |
| 02:20.56 | vasc | yes. |
| 02:21.24 | vasc | rt_boolfinal uses it |
| 02:21.30 | Stragus | This is atrociously bad |
| 02:21.35 | Stragus | Seriously... WTF |
| 02:21.47 | vasc | const struct bu_bitv *solidbits |
| 02:22.12 | Stragus | Don't bother trying to port to OpenCL, there's nothing you can use |
| 02:22.17 | Stragus | Everything has to be rewritten |
| 02:23.22 | vasc | see that's the thing |
| 02:23.25 | vasc | i would like to |
| 02:23.28 | vasc | but it's so... |
| 02:23.29 | vasc | GAH |
| 02:23.50 | vasc | after i dunno like 20 or 30 refactors |
| 02:23.55 | Stragus | Understand what goes in, and what goes out, close your eyes and rewrite |
| 02:23.55 | vasc | maybe it would shape up |
| 02:24.03 | Stragus | I don't think so |
| 02:24.23 | Stragus | The whole algorithm is based on fundamental concepts that must be changed, all of them |
| 02:24.47 | vasc | well |
| 02:24.54 | vasc | some lists are only being iterated |
| 02:25.09 | vasc | or copied verbatim to others |
| 02:25.12 | vasc | or filtered |
| 02:25.37 | vasc | good luck getting which is which though |
| 02:27.16 | vasc | if i wanted to do that |
| 02:27.24 | vasc | first thing would be to change lists to arrays |
| 02:27.32 | vasc | preferably well known sized arrays |
| 02:27.38 | vasc | and remove gotos |
| 02:27.46 | vasc | and the function pointers |
| 02:28.39 | Stragus | Yup |
| 02:32.17 | vasc | ok i think i removed the function pointers and inlined one function |
| 02:35.19 | vasc | 4 gotos out |
| 02:40.23 | vasc | another |
| 02:42.28 | vasc | 10 more gotos |
| 02:53.59 | vasc | a couple more but this one is a bit tangled |
| 02:59.36 | vasc | ok... another 12 gotos or so |
| 03:00.08 | vasc | and these were nearly useless |
| 03:01.07 | vasc | the compiler can optimize those branches easily |
| 03:02.42 | vasc | grep goto src/librt/bool.c |wc -l |
| 03:02.42 | vasc | 49 |
| 03:02.45 | vasc | this is the old file |
| 03:02.51 | vasc | grep goto bool.c |wc -l |
| 03:02.51 | vasc | 19 |
| 03:02.54 | vasc | this is the new file |
| 03:03.51 | vasc | the most hairy one is the rt_boolweave |
| 03:04.42 | vasc | i mean rt_booleval |
| 03:15.06 | vasc | 13 |
| 03:23.23 | vasc | 12 |
| 03:25.16 | vasc | bah |
| 03:26.03 | vasc | well at least i'll have something smaller to look at |
| 03:49.04 | *** join/#brlcad merzo (~merzo@111-44-132-95.pool.ukrtel.net) |
| 04:14.46 | *** join/#brlcad vasc (~vasc@bl12-167-49.dsl.telepac.pt) |
| 05:03.06 | *** join/#brlcad merzo (~merzo@83-29-133-95.pool.ukrtel.net) |
| 06:33.12 | *** join/#brlcad Boquete (~piotr@dwd173.neoplus.adsl.tpnet.pl) |
| 07:58.10 | *** join/#brlcad merzo (~merzo@119-70-133-95.pool.ukrtel.net) |
| 08:17.20 | *** join/#brlcad Ch3ck_ (~Ch3ck@154.70.111.68) |
| 10:02.21 | *** join/#brlcad merzo (~merzo@user-94-45-58-141.skif.com.ua) |
| 10:19.58 | *** join/#brlcad sofat (~androirc@101.214.230.247) |
| 10:29.42 | *** join/#brlcad dracarys983 (dracarys98@nat/iiit/x-nujuyalijwjubmio) |
| 10:29.57 | *** join/#brlcad bhollister (~brad@2601:647:cb01:9750:7d54:b79d:72f2:3078) |
| 10:32.55 | *** join/#brlcad bhollister (~brad@2601:647:cb01:9750:7d54:b79d:72f2:3078) |
| 10:34.35 | *** join/#brlcad sofat (~androirc@101.214.230.247) |
| 10:53.07 | *** join/#brlcad sofat (~androirc@101.214.230.247) |
| 11:00.16 | *** join/#brlcad konrado (~konro@41.205.22.55) |
| 11:13.15 | *** join/#brlcad shaina (~shaina@117.214.247.98) |
| 11:18.14 | *** join/#brlcad ih8sum3r (~ih8sum3r@122.173.197.231) |
| 11:38.41 | *** join/#brlcad merzo (~merzo@user-94-45-58-141.skif.com.ua) |
| 12:05.58 | *** join/#brlcad sofat (~androirc@101.213.170.115) |
| 12:30.14 | *** join/#brlcad merzo (~merzo@user-94-45-58-141.skif.com.ua) |
| 12:47.57 | *** join/#brlcad merzo (~merzo@user-94-45-58-141.skif.com.ua) |
| 13:24.48 | *** join/#brlcad Ch3ck_ (~Ch3ck@154.70.111.105) |
| 14:15.04 | *** join/#brlcad sofat_ (~androirc@106.192.162.255) |
| 14:35.51 | *** join/#brlcad ih8sum3r (~ih8sum3r@122.173.197.231) |
| 15:27.10 | *** join/#brlcad localhost__ (~Ch3ck@154.70.98.105) |
| 15:30.45 | *** join/#brlcad merzo (~merzo@user-94-45-58-141.skif.com.ua) |
| 15:32.30 | brlcad | maths22: hah, that's awesome! |
| 15:32.37 | brlcad | maths22: did you have to make any source mods? |
| 15:32.56 | brlcad | ih8sum3r: can you be more specific? |
| 15:35.42 | ih8sum3r | brlcad: Hello, I'm getting this error: http://paste.ubuntu.com/12195946/ when I run startvm on server |
| 15:36.14 | ih8sum3r | and |
| 15:36.17 | ih8sum3r | vboxheadless --startvm OGV gives this : exec: /usr/local/lib/virtualbox/VBoxHeadless: Permission denied |
| 16:07.41 | brlcad | ih8sum3r: try running those commands via sudo |
| 16:09.07 | ih8sum3r | my ssh stops again :( |
| 16:09.38 | ih8sum3r | contacting with my ISP provider to solve this, till then can you please set my ssh problem |
| 16:10.16 | brlcad | i don't know what that means |
| 16:10.35 | ih8sum3r | with ssh to brlcad.org I'm getting this : ssh_exchange_identification: Connection closed by remote host |
| 16:10.45 | brlcad | pm me your IP |
| 16:11.14 | ih8sum3r | Okay doing |
| 16:11.59 | ih8sum3r | done please check |
| 16:12.14 | brlcad | eh? |
| 16:12.32 | brlcad | send me your IP in a private message (via IRC) |
| 16:12.52 | brlcad | that is not your IP |
| 16:12.57 | brlcad | that is a local address |
| 16:13.10 | Ch3ck_ | brlcad, I've been having a similar issue |
| 16:13.17 | brlcad | go to whatismyip.com |
| 16:13.24 | brlcad | Ch3ck_: ditto then... :) |
| 16:14.09 | Ch3ck_ | brlcad, (y) |
| 16:14.33 | *** join/#brlcad dracarys983 (dracarys98@nat/iiit/x-kdustzmopbtsohxg) |
| 16:20.20 | brlcad | your ISPs are misconfigured, you IP address maps to a name and that name does not map back to that IP address |
| 16:20.31 | brlcad | in both your cases, your IP maps to a name and that name does not resolve to anything |
| 16:20.58 | brlcad | that's why the denials started occurring -- that's a common trick of people spoofing IP addresses |
| 16:21.09 | brlcad | and is a failure of RFC931 |
| 16:22.17 | brlcad | try logging in now |
| 16:23.23 | ih8sum3r | working now |
| 16:23.24 | brlcad | I note that both of you seem to be on dynamic IP addresses, which means this problem will continue as soon as your IP changes |
| 16:24.34 | brlcad | you should contact your ISP and ask them to either remove the DNS entry for their IP addresses or add the reverse mapping of DNS name to IP (which is currently missing) |
| 16:25.03 | brlcad | you can confirm this yourself by running "nslookup YOURIP", then "nslookup WHATEVERNAME" that the first nslookup reported |
| 16:25.07 | brlcad | they should match |
| 16:26.22 | Ch3ck_ | brlcad, I see now |
| 16:27.41 | Ch3ck_ | is back in bizznis! |
| 16:27.57 | brlcad | you IP address is specifically whitelisted, so like I said -- you'll be unable to get in again as soon as your IP address changes |
| 16:29.01 | brlcad | e-mail me or ``Erik your new IP (which may take hours/days to whitelist) to add to /etc/hosts.allow or bounce through an intermediate server that does not have misconfigured DNS and you should be good |
| 16:30.15 | Ch3ck_ | brlcad, Alright, will do. |
| 16:30.27 | Ch3ck_ | I have a small issue, it seems the bzflag server does not have gcc? |
| 16:30.40 | Ch3ck_ | I've tried compiling brlcad and there's no gcc |
| 16:32.27 | brlcad | there's no symlink (apparently) |
| 16:32.28 | sofat_ | Ch3ck, i complied brlcad code on bz server using cmake |
| 16:32.34 | brlcad | probably upgrade wiped it out recently |
| 16:32.38 | brlcad | just use gcc47 |
| 16:33.23 | Ch3ck_ | Alright |
| 16:43.52 | *** join/#brlcad Boquete (~piotr@acou191.neoplus.adsl.tpnet.pl) |
| 16:56.05 | *** join/#brlcad konrado (~konro@41.205.22.38) |
| 17:09.19 | dracarys983 | brlcad: I am interested on doing work on the spherical convergence algorithm you talked about in my project. Is there something I can read to get more familiar with the idea? |
| 17:12.48 | dracarys983 | brlcad: I see that it was kind of stupid of me to have gone the other way if at the end spherical is the one that would stay instead of what I did. |
| 17:19.28 | *** join/#brlcad Stragus_ (~alexis@modemcable090.29-19-135.mc.videotron.ca) |
| 17:23.22 | brlcad | dracarys983: awesome! |
| 17:23.43 | brlcad | dracarys983: yes, start with researching pseudorandom spherical sampling |
| 17:23.51 | brlcad | and/or spherical tessellation |
| 17:24.46 | dracarys983 | Okay |
| 17:24.48 | brlcad | you can think of spherical pseudorandom sampling as picking random points in a tessellation of a sphere |
| 17:25.28 | brlcad | sorry QUASIRANDOM |
| 17:25.36 | brlcad | wrong term |
| 17:25.45 | dracarys983 | And we keep doing finer tessellation after each pass? |
| 17:26.12 | brlcad | sampling with that approach, going from one quasirandom point to another quasirandom point, which ensures even unbiased coverage of the volume without any alignment affects |
| 17:26.16 | brlcad | effects |
| 17:26.38 | dracarys983 | Okay. quasirandom -- noted. |
| 17:26.39 | brlcad | no, you just keep picking different points |
| 17:27.32 | brlcad | well, I guess you could keep doing a finer tessellation .. that really would be an implementation detail |
| 17:28.01 | brlcad | you're really just picking two quasirandom points at a given density and shooting a ray through those two points |
| 17:28.42 | brlcad | just have to make sure the points are on or outside the sphere (especially if you tessellate) and that you exhaust all points in a set so that your sampling is "even" density |
| 17:29.49 | dracarys983 | Um, "even" density means points should always be taken in pairs and all should be exhausted? |
| 17:30.22 | Stragus | I have done multiple randomly rotated icosahedrons (or tesselated icosahedrons), seemed to work pretty well even with low sampling |
| 17:31.10 | brlcad | dracarys983: yes, you're shooting through those two points and sampling the volume .. so you want the interior sampled with an even density |
| 17:31.34 | dracarys983 | brlcad: Gotcha! |
| 17:31.36 | brlcad | Stragus: yep, that's the basic idea for quasi |
| 17:32.24 | dracarys983 | brlcad: Why is quasi-randomness important here? |
| 17:32.41 | brlcad | read up on what it means and it should hopefully become apparent ;) |
| 17:32.43 | Stragus | *nods* Just saying it's a good approach as some other quasi-random distribution techniques require way too many random numbers, it's costly |
| 17:34.28 | dracarys983 | brlcad: Okay. Thanks for the heads up. |
| 17:35.16 | brlcad | dracarys983: whatever you do, keep track of your seed -- must be reproducible behavior |
| 17:35.35 | brlcad | Stragus: *nod* |
| 17:35.51 | brlcad | though this isn't a performant-critical function |
| 17:37.02 | dracarys983 | brlcad: Sure thing |
| 17:37.06 | brlcad | it's for some unknowable analysis bit that will use the information for some application-domain calculation(s) that can take a while to be computed or compute in the background or whatever |
| 17:37.42 | brlcad | on-demand volume, surface areas, centroids, moments, interference reporting, etc |
| 17:38.13 | dracarys983 | basically all analysis performed right now by gqa |
| 17:38.22 | dracarys983 | Maybe plus a couple |
| 17:38.49 | brlcad | fast would be fine and dandy, but more concerned that the calculations are correct, values actually converge to within a specified epsilon, etc |
| 17:39.06 | brlcad | need to be able to compute the error bars on what is reported |
| 17:40.44 | dracarys983 | Precision precedes speed here then |
| 17:41.14 | dracarys983 | brlcad: Will keep in mind. |
| 17:41.25 | Stragus | liked the part about unknowable analysus on undefined formation for vague applications in some ambiguous context |
| 17:41.31 | Stragus | analysis* too |
| 17:44.56 | brlcad | :) |
| 17:46.12 | brlcad | Stragus: thanks for all your help with vasc! I see he's still stuck on the terrible depth peeling papers, but you seemed to slowly start getting him convinced that a different direction is better |
| 17:47.15 | brlcad | depth peeling is just a terrible idea ... we tested it out 9 or so years ago and it completely falls apart on big models with the number of iterations it has to perform |
| 17:48.06 | Stragus | Indeed, Lee had also hired some guy to try it out. I don't recall the numbers but Rayforce was over 100x faster |
| 17:48.26 | brlcad | don't see why he's so averse to fast on-demand dynamic allocation (which will likely never need to occur or will probably only occur once some small percentage of the time) |
| 17:48.47 | Stragus | Probably because there isn't a paper about it :p |
| 17:48.48 | brlcad | big static buffer to stash results |
| 17:48.51 | Stragus | Yup |
| 17:48.53 | brlcad | sort them |
| 17:48.56 | brlcad | eval |
| 17:48.56 | brlcad | done |
| 17:49.19 | brlcad | all crazy fast steps |
| 17:49.31 | Stragus | Yes, and very GPU-friendly when done properly |
| 17:57.02 | brlcad | even cpu friendly, coherent |
| 17:57.56 | brlcad | it's been plan for a long time to accumulate all partitions (and their segments) during tracing so that they can be sorted+evaled in separate steps |
| 17:58.11 | brlcad | that's basically the goto hell in boolweave now per ray |
| 17:58.37 | Stragus | That code really needs to be rewritten, even on CPUs |
| 17:58.46 | brlcad | this is going to be a bit of code that will be REALLY easy to get wrong |
| 17:59.23 | brlcad | boolweave isn't just doing booleans -- it account for floating point fuzz in provably correct ways while also being performant (in 1980's terms) |
| 17:59.58 | brlcad | just eliminating the registeres and gotos without re-architecting the rest is pretty much guaranteed to slow it down by 5-25% |
| 18:00.15 | brlcad | and will likely produce wrong results |
| 18:00.38 | brlcad | I would eaily bet that vasc got that wrong the other night, introduced incorrect weaving |
| 18:00.57 | Stragus | I really would rewrite the whole thing, but taking care of understanding all the floating point fuzz magic that the old code implemented |
| 18:01.00 | brlcad | gotta back it up to what the algorithm is doing and just apply that to coherent processing (whether gpu or not) |
| 18:01.36 | brlcad | the fundamental algorithm can be expressed in less than 100 lines of code iirc |
| 18:02.03 | brlcad | handling all geometry cases including bad geometry and fuzz jacks that up a bit, but not a crazy amount |
| 18:02.20 | brlcad | the other 10x code in boolweave+boolfinal is old school optimization |
| 18:03.48 | Stragus | Old school optimization should have involved not calling malloc() for every little piece of data :p |
| 18:04.08 | brlcad | malloc used to be free compared to the calculations |
| 18:04.46 | brlcad | and it doesn't actually alloc iirc -- it's using pooled structures getting added to lists |
| 18:07.17 | brlcad | ``Erik: trying to load the virtual box kernel driver and it's saying: depends on kernel - not available or version mismatch |
| 18:07.35 | brlcad | ``Erik: can only presume that means /usr/src/sys is out of sync (ahead of) the running kernel? |
| 18:08.19 | brlcad | is there one staged for reboot or are the actual sources needing an update or something? |
| 18:08.36 | brlcad | "kldload vboxdrv" to see it |
| 18:12.15 | *** join/#brlcad vasc (~vasc@bl8-192-144.dsl.telepac.pt) |
| 18:16.32 | brlcad | and there he be! howdy vasc :) depth peeling sucks |
| 18:17.20 | brlcad | rossignac is awesome, good old friend |
| 18:17.21 | brlcad | but that was pretty much a toy technique -- it falls apart on real models really fast, really hard |
| 18:18.34 | brlcad | you end up with too many layers, way too many iterations |
| 18:19.45 | brlcad | great for demos with relatively simple somewhat flat hierarchies |
| 18:29.35 | *** join/#brlcad Izakey (~Izakey@41.205.22.9) |
| 18:31.33 | maths22 | brlcad: no source mods |
| 18:31.37 | brlcad | maths22: did you e-mail your log? |
| 18:31.42 | brlcad | maths22: wow, cool |
| 18:31.53 | maths22 | What log? |
| 18:31.56 | brlcad | last time I tried, required a few mods |
| 18:32.01 | maths22 | The benchmark one? |
| 18:32.01 | brlcad | the benchmark log |
| 18:32.11 | maths22 | All I did was install svn and cmake |
| 18:32.20 | maths22 | Check out, and built |
| 18:32.24 | brlcad | optimized build? |
| 18:32.28 | maths22 | No |
| 18:32.34 | brlcad | oh, sweet .. even faster |
| 18:33.03 | brlcad | if you can try an optimized / release build, would be great to get that log mailed |
| 18:33.16 | brlcad | and know the vgr for it |
| 18:33.20 | *** join/#brlcad sofat_ (~androirc@106.192.162.255) |
| 18:33.27 | maths22 | I can run an optimized build. I guess that model pi is quad core, so I can speed up compilation |
| 18:33.35 | brlcad | no rush :) |
| 18:33.51 | brlcad | how you been, ltns! |
| 18:34.17 | brlcad | google's completely redoing the gci interface this year, I shared what you worked on with them |
| 18:34.17 | maths22 | I've been doing well |
| 18:34.33 | brlcad | helping with some of the design requirements |
| 18:34.34 | maths22 | Did you see the beta.brlcad.org/wp menubar |
| 18:34.40 | maths22 | Good about GCI |
| 18:36.48 | brlcad | cool, no I hadn't seen that |
| 18:36.56 | brlcad | looks like it's working responsive too |
| 18:37.01 | maths22 | I need to do the circle around the logo. |
| 18:37.02 | brlcad | awesome |
| 18:37.11 | maths22 | I used the bootstrap menubar-makes things easier |
| 18:37.13 | brlcad | logo color is a bit off too |
| 18:37.31 | brlcad | notes we need to publish an official icon set still |
| 18:37.43 | brlcad | did you see sofat_'s documentation interface? |
| 18:37.50 | sofat_ | Yee |
| 18:37.51 | sofat_ | Yes |
| 18:38.08 | maths22 | I used the same logo that was already there |
| 18:38.10 | sofat_ | I want to link my work with this website |
| 18:38.21 | sofat_ | It is possible ? |
| 18:38.22 | brlcad | sofat_: yeah, definitely |
| 18:38.25 | maths22 | I last took alook at sofat_'s stuff a few months ago |
| 18:38.35 | brlcad | maths22: take a quick peek, it's pretty cool |
| 18:39.01 | brlcad | it's just the docs, but it's sync'd with our repo docs and has awesome navigation |
| 18:39.29 | sofat_ | Any think wrong with my old stuff ? |
| 18:39.34 | maths22 | sofat_: is it a wordpress plugin or something like that? |
| 18:39.38 | brlcad | basic raw editing ability too, but won't be focusing on that the first go round |
| 18:39.39 | maths22 | That is what I remember it being |
| 18:39.46 | maths22 | But I didn't look closely |
| 18:40.21 | sofat_ | Yes in gsoc i made plugin to handle the editing |
| 18:40.43 | brlcad | sofat_: give him the url ;) |
| 18:42.26 | sofat_ | https://github.com/sofathitesh/brlcad-code |
| 18:43.06 | sofat_ | For document we just made the page which hold the wordpress theme style |
| 18:43.11 | sofat_ | My work is there |
| 18:43.31 | sofat_ | brlcad.org/~nouhrasofat/ |
| 18:46.24 | sofat_ | maths22, if you any problem to use plugin so please tell me |
| 18:46.29 | sofat_ | Face |
| 18:47.04 | maths22 | sofat_: How is the language list genrated |
| 18:47.31 | sofat_ | Using google language translator plugin |
| 18:47.36 | maths22 | I have read recently that it is a good idea to not use flags to indicate languages-particularly where the same language is spoken in many countries |
| 18:47.41 | *** join/#brlcad Shubham (012720ce@gateway/web/freenode/ip.1.39.32.206) |
| 18:47.47 | maths22 | Using google translate makes sense |
| 18:48.05 | sofat_ | Yes ;-) |
| 18:48.06 | brlcad | there's two language lists |
| 18:48.10 | maths22 | The order of that list is rather odd as well |
| 18:48.18 | maths22 | brlcad: ours, and google translate's? |
| 18:48.32 | sofat_ | Yes |
| 18:48.35 | brlcad | the drop-down is google translate, the ones before it are our manual translations (which will generally be superior) |
| 18:48.46 | maths22 | That makes sense |
| 18:48.53 | brlcad | the tutorials were all manually translated to spanish, for example |
| 18:48.53 | maths22 | What is the order of the drop down? |
| 18:49.22 | maths22 | brlcad: I'm rebuilding in release mode on the pi |
| 18:49.28 | brlcad | cool |
| 18:49.41 | brlcad | maths22: any idea why I get an empty img tags on beta? |
| 18:49.52 | brlcad | see http://brlcad.org/tmp/missing.png |
| 18:50.20 | sofat_ | What is rebuilding please tell me? |
| 18:50.38 | ih8sum3r | brlcad: Is this website's mockup made by inderpreet? If I'm not wrong |
| 18:50.44 | ih8sum3r | beta.brlcad.org |
| 18:50.46 | ih8sum3r | one |
| 18:51.01 | starseeker | glowers at MSVC Release config... |
| 18:51.25 | brlcad | ih8sum3r: the mockup predates inderpreet iirc, but has had many people working on it the past ... four years? |
| 18:51.31 | brlcad | it started as a GCI task |
| 18:52.04 | brlcad | maths22: you recall the first originator? you? |
| 18:52.11 | ih8sum3r | oh! I see |
| 18:52.20 | maths22 | I think I started it, then anita did the theme |
| 18:52.34 | maths22 | The images were never there on beta |
| 18:52.51 | maths22 | They never imported right from Anita's GCI task |
| 18:53.06 | maths22 | I updated drupal my first year, then did the wordpress migration my second |
| 18:53.32 | maths22 | ih8sum3r: inderpreet did the wiki, I think, but he did not do wordpress |
| 18:53.33 | sofat_ | Waao |
| 18:53.44 | maths22 | sofat_: ? |
| 18:54.18 | maths22 | brlcad: I also brought fisheye back online about a week ago |
| 18:54.40 | brlcad | heh, so I should keep an eye on the cpus? |
| 18:54.51 | sofat_ | For you means great you have much knowledge in small age ;-) |
| 18:56.29 | brlcad | sofat_: he's not quite so young any more, but his level of experience is definitely advanced and impressive for someone of his age :) |
| 18:56.43 | maths22 | brlcad: probably, but they have seemed OK lately |
| 18:56.49 | maths22 | No making branches :( |
| 18:57.00 | maths22 | They just take a long time and a lot of cpu to process |
| 18:57.02 | brlcad | that's probably good |
| 18:57.07 | sofat_ | Yes i see |
| 19:05.45 | maths22 | Because? |
| 19:06.18 | vasc | i'm working on my own toy technique |
| 19:07.38 | brlcad | maths22: just because it had whatever problem it had before where it was locking up the server |
| 19:07.51 | brlcad | giving it less work is a good idea until that is sorted out |
| 19:07.56 | brlcad | is it the same version or updated? |
| 19:08.33 | sofat_ | Hey i am passed my final evaluation . thanks to mr sean and starseeker |
| 19:08.41 | sofat_ | Thank you so much |
| 19:09.02 | brlcad | sofat_: thank you for all your efforts |
| 19:09.13 | brlcad | the work doesn't stop here, though ;) |
| 19:09.21 | sofat_ | Yah i know |
| 19:09.39 | brlcad | you did well, despite the communication challenges |
| 19:10.10 | ih8sum3r | Hey, I got mail too. Thanks everyone from the core of my heart. Specially to Sean my mentor, Erik who had provided me lot of guidance. |
| 19:10.14 | sofat_ | Thanks so much for you trust on me |
| 19:10.16 | *** join/#brlcad kintel (~kintel@unaffiliated/kintel) |
| 19:10.51 | sofat_ | You gave me chance to did this think happen i just say thank you so much |
| 19:12.40 | brlcad | since notifications are going out already |
| 19:13.03 | brlcad | two more did not pass this year, so 9 out of 12 passed |
| 19:14.02 | brlcad | two others were very close to failure, maybe should have failed so they would learn, but were ultimately passed |
| 19:17.02 | maths22 | brlcad: still the save version-will update soon |
| 19:17.31 | maths22 | brlcad: where is the list of gsoc projects? |
| 19:19.58 | brlcad | brlcad.org/wiki/Google_Summer_of_Code/2015 |
| 19:30.44 | Boquete | hey brlcad, brlcad will be an org in Google Code in 2015? |
| 19:35.39 | *** join/#brlcad sofat_ (~androirc@106.192.162.255) |
| 19:36.17 | *** join/#brlcad Ch3ck_ (~Ch3ck@154.70.98.105) |
| 19:36.48 | brlcad | Boquete: hablas espan~ol? |
| 19:37.23 | brlcad | Boquete: that is not yet decided, but I do love GCI :) |
| 19:37.31 | Boquete | Sorry I do not speak spanish :D |
| 19:37.45 | brlcad | ah, no problem |
| 19:37.56 | Boquete | brlcad, hope you will be there, I'm really looking forward to be in Brl-cad :D |
| 19:38.04 | brlcad | there's a place in panama called boquete -- thought you might be from there ;) |
| 19:38.31 | brlcad | Boquete: glad to hear it, but you're welcome to get involved regardless ;) |
| 19:38.59 | konrado | hello brlcad and other members of the community thanks for helping me get through with GSoC successfully. |
| 19:39.00 | brlcad | even if you have to jump ship to a different org, anything you do with us will almost certainly be experience that translates to better chances of winning ;) |
| 19:39.52 | brlcad | konrado: thank you for all your efforts! you made a lot of progress |
| 19:40.08 | brlcad | there's obviously still more work, but it's an exciting feature that is much wanted |
| 19:42.04 | konrado | I would do my best to make all the improvement I can. |
| 19:43.16 | *** join/#brlcad Boquete (~piotr@acou191.neoplus.adsl.tpnet.pl) |
| 19:43.43 | vasc | hmmm.. this almost works... |
| 19:45.23 | Boquete | Sorry I disconnected :v brlcad about my nickname, It was "changed" word "bouquet", but funny thing is that I heard in .. spanish or portugeese it mean "bad/dirty" word :v That's why I was not sure about using it. I use it on IRC but on Google Melange I used "antonow" (like Oleg Antonow, you know this russian constructor). Hope nobody will feels bad about my nickname :D |
| 19:46.16 | Boquete | Ow I checked now what it mean in portugeese.. lol. I think I need change my nickname. BUT in spanish it mean gap xD |
| 19:47.02 | Stragus | "Bouquet" is a french word too, like a... bundle |
| 19:47.32 | Boquete | Ow yes it's too |
| 19:48.36 | Boquete | https://en.wikipedia.org/wiki/Baguette That was first meaning of my nickname. I just changed it a little :D |
| 19:48.49 | brlcad | Boquete: https://en.wikipedia.org/wiki/Boquete,_Chiriqu%C3%AD |
| 19:48.56 | brlcad | it's a very beautiful place |
| 19:49.23 | vasc | i always get the subtraction and the xor working but not the intersection |
| 19:49.24 | vasc | BAH |
| 19:49.49 | vasc | in my little toy example |
| 19:49.54 | Boquete | So I think I will keep this nickname. I hope that no one feels offended |
| 19:50.15 | brlcad | it means "gap" or some sort of opening in spanish |
| 19:50.18 | brlcad | you can't please everyone |
| 19:50.48 | brlcad | similar to french meaning (a bouqet of flowers "opens up") |
| 19:51.15 | Boquete | I wanted to changed on Google Melange from antonow to Boquete (I use it everywhere) but I think I cant. I will write to Stephanie before GCI :D |
| 19:51.39 | brlcad | write the melange devs first |
| 19:51.48 | brlcad | see if one will change it for you instead of bothering steph |
| 19:52.13 | Boquete | Ow yes, right |
| 19:52.37 | Boquete | I will check it later (before GCI) and I will see hwo can I contact :D |
| 19:52.44 | brlcad | there is going to be a completely redesigned website for GCI 2015, so it might not matter at all |
| 19:52.50 | brlcad | the new site is not based on melange |
| 19:52.52 | Boquete | Ow I heard that |
| 19:53.57 | Boquete | I heard that ther's going to be few more changes but nothing sure so I don't want to spread the word :D |
| 19:54.07 | brlcad | there definitely will be |
| 19:54.28 | brlcad | one pretty big one |
| 19:54.46 | brlcad | but it's a good one in the grand scheme of things |
| 19:55.13 | Boquete | Last year that I can contribute in GCI 2015. So nervous |
| 19:55.30 | vasc | bouquet |
| 19:55.31 | Boquete | That's bad I didn't know about GCI before.. :/ |
| 19:55.34 | Boquete | Yes? |
| 19:56.59 | brlcad | no, not really |
| 19:57.25 | brlcad | vasc: yes, just a typo ;) |
| 19:57.32 | Boquete | I mean "Yes?" was to vasc :D |
| 19:57.53 | brlcad | he was correcting my spelling |
| 19:58.22 | Boquete | Oh ok :D |
| 19:58.58 | ``Erik | brlcad: /usr/src/sys and /boot/kernel should be in sync, but those should be newer than what's live right now, been waiting for a good time to reboot... |
| 20:01.36 | brlcad | ``Erik: ah, so that would explain why the module won't load |
| 20:02.20 | vasc | too many years of french classes to that to you |
| 20:02.38 | brlcad | ``Erik: good time for a reboot whenever you are ready, in case disaster ensues :) |
| 20:03.48 | brlcad | missing, a word he is |
| 20:03.57 | vasc | figures. it can't get the normals right |
| 20:04.01 | vasc | the surfaces either |
| 20:14.55 | vasc | bah |
| 20:15.04 | vasc | this isn't working like its suppose to |
| 20:34.57 | vasc | well it kinda looks ok |
| 20:35.03 | vasc | kinda |
| 20:35.06 | ``Erik | brlcad: I'll be around for a little bit if you want to hit that big button... (I kinda don't want to be the trigger-man... might be good to crank a backup before doing that?) |
| 20:40.06 | vasc | the normal look different from stock |
| 20:46.03 | vasc | i think the normals are all screwed up |
| 21:11.50 | brlcad | ``Erik: good idea, okay I'll kick off a backup first .. that'll probably take a long time to finish, so maybe we can give the reboot a go on sunday if it's done |
| 21:12.15 | brlcad | ``Erik: is there anything specific needed to put the new kernel in place? |
| 21:12.26 | brlcad | or anything else that would be good to do while we're rebooting? |
| 21:13.58 | vasc | so what's bad about rossignac's paper brlcad? |
| 21:15.04 | brlcad | hm? I shared the reasons why... |
| 21:17.00 | vasc | the too many iterations? |
| 21:17.27 | brlcad | we implemented that paper about 9 years ago |
| 21:17.40 | vasc | oh? |
| 21:17.44 | brlcad | even using blister, you can see problems |
| 21:17.53 | vasc | that paper is after blister |
| 21:17.57 | brlcad | cst sure |
| 21:17.59 | vasc | it claims to fix the blister surface acne |
| 21:18.02 | brlcad | but really just rebranded |
| 21:18.26 | brlcad | that was all really hable's work, rossignac was his advisor iirc |
| 21:18.42 | vasc | well yeah hable's the first author |
| 21:18.44 | brlcad | regardless, the issue is that the method just really falls apart on real models |
| 21:19.21 | brlcad | doesn't work well with arbitrary depth, really assumes few depths to be performant |
| 21:21.11 | brlcad | production models usually have crazy complexity, especially compared to our sample demos |
| 21:22.00 | brlcad | object counts in the 10^5 to 10^8 range with depths commonly in the dozens to hundreds range |
| 21:22.30 | brlcad | and that's for a single vehicle, not considering full scenes with lots going on |
| 21:22.52 | vasc | so which method you use? it seems 1980s stuff |
| 21:23.06 | brlcad | what do you mean? |
| 21:23.16 | vasc | i cleaned up the code |
| 21:23.20 | vasc | and it just ... |
| 21:23.21 | vasc | well |
| 21:23.35 | vasc | it generates list of segments and more lists of segments and evals them against the tree |
| 21:23.36 | brlcad | I know, lots of comments and questions :) |
| 21:23.56 | vasc | uses a dynamic stack |
| 21:24.07 | vasc | and a bitvector per ray with size of n primitives |
| 21:24.11 | brlcad | some things I noticed you changed were guaranteed to slow it down (but also necessary to ultimately speed it up) |
| 21:24.30 | vasc | ? |
| 21:24.49 | vasc | the opencl code doesn't do csg right now |
| 21:24.55 | brlcad | you should have noticed that there's pretty much not a limit on anything -- that's part why everything was dynamic |
| 21:25.10 | brlcad | not just a throwback to days when malloc cost less than a division |
| 21:25.13 | vasc | there's always a choice between multiple passes and more memory |
| 21:25.39 | vasc | like the bitvector for one |
| 21:25.53 | vasc | i could just iterate the list of hits and see if the primitive is in there |
| 21:26.45 | brlcad | except traversing a list is slow as you noted |
| 21:26.55 | vasc | in fact i did just that while i was trying to implement the goldfeather algorithm |
| 21:27.04 | vasc | there's that too |
| 21:27.11 | vasc | we need static arrays not dynamic linked lists |
| 21:27.23 | brlcad | sure |
| 21:27.28 | brlcad | well, we need arrays |
| 21:27.39 | vasc | its a start to do the arrays first |
| 21:27.43 | vasc | and then bound them somehow |
| 21:27.45 | brlcad | whether they are technically static or just really big and rarely ever need to grow is the big question |
| 21:28.11 | vasc | i tried cleaning up the gotos in that code as well |
| 21:28.15 | vasc | but its real hard |
| 21:28.23 | vasc | i went down to 13 gotos |
| 21:28.24 | brlcad | that's part where I can almost guarantee you didn't get it right ;) |
| 21:28.40 | brlcad | and almost certainly slowed it down if you did straight up conversions |
| 21:28.53 | vasc | i didn't just use any mechanical algorithm |
| 21:28.54 | brlcad | there's lots of dragons in the boolean weaving goto logic |
| 21:29.00 | vasc | want to try my version of it? |
| 21:29.16 | brlcad | of course :) |
| 21:29.40 | vasc | haven't tried compiling it |
| 21:29.56 | brlcad | for what it's worth, I've rewritten the boolean weaving code three times over the years |
| 21:30.18 | brlcad | the first time I was a naive student appalled at all the gotos, coming from a "all gotos are evil" education |
| 21:30.35 | vasc | let's see |
| 21:30.45 | brlcad | first attempt compiled great, and was outright wrong |
| 21:31.31 | brlcad | second attempt years later, wiser and more carefully undertaken compiled great, was demonstrably correct and was some 15% slower iirc |
| 21:32.09 | brlcad | third attempt was much better performance wise, but actually was more code and (arguably) harder to read |
| 21:32.53 | brlcad | really for performance, the state of the current code is half-irrelevant |
| 21:33.12 | brlcad | it needs to be completely restructured for coherency, processed differently |
| 21:33.19 | brlcad | the core algorithm is something like 100 lines of code |
| 21:34.07 | brlcad | boolweave/final has a LOT of magic built into it for handling real geometry fast, i.e., handling floating point conditions with extreme consistency and verifiable behavior |
| 21:34.35 | brlcad | that's usually the part that gets dorked up on a naive restructure |
| 21:35.38 | vasc | i just cleaned up some gotos and inlined some functions and removed the debug thigns |
| 21:35.43 | vasc | the debug messages |
| 21:35.45 | brlcad | the robustness logic bumps that 100 lines of logic a fair bit and the rest you see (the goto spagetti) is mostly unrolled optimization, which kicks it up to the 1500-2000 lines sizing you see |
| 21:36.24 | brlcad | for gpgpu/opencl, it's really just a matter of going back to the core algorithm and inputs, and figuring out how to pack that data in arrays |
| 21:36.41 | vasc | yes. when i know WHAT the core algorithm actually is |
| 21:36.46 | brlcad | which is almost certainly going to need to be large pages of memory storing results, sort them, evaluate |
| 21:37.37 | vasc | sorting is quite likely |
| 21:37.45 | vasc | but the dynalloc i hope to avoid |
| 21:38.12 | vasc | i can just try redoing that algorithm |
| 21:38.15 | vasc | but its gonna be pain |
| 21:38.26 | vasc | like i said i just replaced the kd-trees for the bvhs and it was fine |
| 21:38.30 | vasc | was trying to do the same here |
| 21:42.28 | vasc | cpu code like that is really hairy to port over |
| 21:42.37 | vasc | we needed something less heavy on complexity |
| 21:43.17 | brlcad | no disagreement there, but that's also why I say trying to transcode the existing is going to be .. |
| 21:43.20 | brlcad | really hard |
| 21:43.47 | brlcad | I at least wouldn't start there -- I'd start with the same inputs and then compare outputs |
| 21:43.56 | brlcad | i.e., just implement how I'd do the eval |
| 21:44.20 | brlcad | for what it's worth, here's a completely different approach expanded with some of the production stability tolerance testing needed |
| 21:44.30 | brlcad | written by one of our core devs years ago in java |
| 21:44.37 | brlcad | http://brlcad.org/websvn/filedetails.php?repname=BRL-CAD&path=%2Fjbrlcad%2Ftrunk%2Fsrc%2Forg%2Fbrlcad%2Fgeometry%2FPartition.java&peg=34288 |
| 21:44.47 | vasc | http://pastebin.com/QQrGudYu |
| 21:44.49 | vasc | try this one |
| 21:45.27 | brlcad | you can look for the intersect(), subtract(), and union() functions |
| 21:45.46 | brlcad | can't get to pastebin.com, blocked |
| 21:45.54 | brlcad | ~paste |
| 21:45.54 | infobot | i guess paste is http://pastebin.org/ or http://bin.cakephp.org/ or http://pastebin.ca/ |
| 21:46.15 | brlcad | (org is blocked too) |
| 21:46.24 | vasc | that doesn't have the boolean evaluator |
| 21:46.31 | vasc | oh |
| 21:46.33 | brlcad | and ca, sorry -- debian's is good though |
| 21:46.35 | brlcad | yeah it does |
| 21:46.41 | brlcad | it's completely OO fashion, very different |
| 21:48.12 | vasc | gah |
| 21:48.15 | brlcad | and iirc, that implementation was verified to a large extent (and written by one of our most senior devs before he retired, for fun) |
| 21:48.16 | vasc | well yeah |
| 21:48.30 | vasc | is it more accurate or less accurate? |
| 21:48.45 | brlcad | does not compute |
| 21:48.49 | brlcad | it's faithful |
| 21:49.01 | brlcad | so it's doing the right thing |
| 21:49.10 | vasc | so you mean you get the same results? |
| 21:49.16 | vasc | even if it doesn't implement the xor operator? |
| 21:49.24 | brlcad | right |
| 21:49.28 | brlcad | we don't use xor |
| 21:49.36 | vasc | scratches his head |
| 21:49.37 | brlcad | i ripped that out of one of our branches |
| 21:49.51 | brlcad | xor will probably be gone in v8 |
| 21:49.55 | vasc | so you check the outputs and got the same outputs? |
| 21:50.05 | vasc | exact same |
| 21:50.11 | brlcad | yep |
| 21:50.36 | vasc | i'm usually not a big fan of java porting in a case like this because the code obfuscates memory allocation a lot |
| 21:50.51 | vasc | but i'll see |
| 21:50.57 | brlcad | sure, it's just a reference for understanding the algorithm |
| 21:51.19 | brlcad | with all the C optimizations obviously yanked |
| 21:52.01 | brlcad | it's actually shorter than the C version by quite a lot, even more so if you ignore the logging statements |
| 21:52.27 | vasc | so why don't you port that over to C and use that instead ? |
| 21:52.33 | brlcad | and it fixed a limitation of the C version |
| 21:52.55 | brlcad | it was an order or so slower :) |
| 21:53.03 | vasc | even ported over? |
| 21:53.07 | vasc | java is slowe |
| 21:53.10 | vasc | slow |
| 21:53.32 | brlcad | yep, untested what that code implemented coherently would be like |
| 21:53.42 | brlcad | it's still not using arrays and you'd want to |
| 21:54.05 | brlcad | still needs the partitions coming in sorted |
| 21:54.11 | brlcad | so you need them all first |
| 21:54.21 | brlcad | front to back processing, etc |
| 21:54.35 | vasc | its like this |
| 21:54.40 | vasc | the per pixel lists aren't that big |
| 21:54.49 | brlcad | lists of what? |
| 21:54.57 | vasc | as a first approach i can just inline insertion sort them |
| 21:55.04 | vasc | like we do in so much of the code already |
| 21:55.24 | vasc | when i get a good library then i can do a global segmented sort |
| 21:55.26 | vasc | or something |
| 21:55.37 | brlcad | how you sort probably won't make a huge difference |
| 21:55.51 | brlcad | just saying that sorting is assumed with this evaluation approach/code |
| 21:56.09 | brlcad | certainly ways to do it without sorting, but haven't thought about it much |
| 21:56.12 | vasc | the sorting ain't the problem. the problem is the list partitioning and filtering and merging and dynamically growing them |
| 21:56.17 | vasc | and reallocating stacks |
| 21:56.19 | vasc | and so on and on |
| 21:56.28 | vasc | gotos |
| 21:56.39 | vasc | lots and lots of memory caches |
| 21:56.44 | vasc | per pixel |
| 21:57.03 | brlcad | so the lists you're referring to are partitions or segments along the shotline? |
| 21:57.10 | vasc | well its like this |
| 21:57.24 | brlcad | wonders why you rarely answer questions :) |
| 21:57.34 | vasc | the current code first shoots all the rays and to compute how large the per pixel hit point lists will be |
| 21:57.51 | vasc | then it does one huge malloc of that for all pixels |
| 21:58.08 | vasc | and recomputes the shots again to fill those per pixel arrays of hit points |
| 21:58.14 | vasc | so i got the arrays of hit points per pixel |
| 21:58.35 | vasc | i was trying to use an algorithm which could enable me to do the csg incrementally so i would avoid all of this |
| 21:58.36 | brlcad | need more than hit points, you need at least segments, but ideally partitions and segments |
| 21:58.39 | vasc | but nevermind |
| 21:58.50 | brlcad | to guarantee correct solidity preservation |
| 21:58.58 | vasc | the segments are tuples of in/out hitpoints right? |
| 21:59.09 | brlcad | yes |
| 21:59.09 | vasc | now the partitions i'm more vague about |
| 21:59.19 | brlcad | and partitions are one or more segments |
| 21:59.38 | brlcad | you need to know that a given segment "belongs with" another |
| 21:59.48 | vasc | because? |
| 21:59.58 | brlcad | when evaluating them, it matters when it comes time to merge or split |
| 22:00.10 | vasc | merging and splitting. evil. |
| 22:00.17 | brlcad | is that the same object, or another reference from a different object |
| 22:00.31 | brlcad | CSG == lots of merging and splitting |
| 22:01.04 | vasc | well the goldfeather algorithm doesn't care about that crap |
| 22:01.15 | vasc | it only wants the front and back of an object |
| 22:01.25 | brlcad | this is also a huge deviation from most academia -- solid modeling has somewhat different requirements |
| 22:01.27 | vasc | shame i can't implement it properly |
| 22:01.32 | vasc | no man |
| 22:01.51 | brlcad | there are older solid modeling papers on this topic |
| 22:01.53 | vasc | i read about the way you do the csg computation in a thesis by jahnsen |
| 22:02.02 | vasc | from 1989 |
| 22:02.11 | vasc | but it's ... |
| 22:02.12 | brlcad | csg goes back to the 60's and 70's |
| 22:02.18 | vasc | well i can understand it conceptually |
| 22:02.39 | vasc | but as a practical high-performance algorithm? or a simple one? no |
| 22:03.08 | brlcad | there's also general CSG from a computational geometry perspective, CSG as a modeling operator on boundaries, and CSG for solid modeling (our domain) |
| 22:03.15 | brlcad | all three have somewhat different behaviors |
| 22:03.37 | brlcad | how you track and what you track is different for all three |
| 22:03.49 | vasc | so let me see if i get this: you have initially a bunch of segments. and then you partition them. |
| 22:03.53 | vasc | but how and for what? |
| 22:04.12 | vasc | and where does the tree eval kick in |
| 22:04.21 | vasc | and should be tree be optimized into a different form |
| 22:04.25 | vasc | questions questions |
| 22:05.02 | brlcad | no no.. when you intersect a primitive, you get back a partition with one or more segments if there is a hit |
| 22:05.04 | vasc | jahnsen's thesis goes on and on about it |
| 22:05.06 | vasc | but i didn't get it |
| 22:05.17 | brlcad | partitioning isn't an action |
| 22:05.26 | brlcad | it's just a grouping |
| 22:05.27 | vasc | so initially a partition is one partition per object ? |
| 22:05.49 | brlcad | at the leaves of the CSG hierarchy, yes |
| 22:05.50 | vasc | so you partition the hits of a primitive |
| 22:06.01 | brlcad | it's a set of in/out segments |
| 22:06.14 | brlcad | and whether those can be combined per the boolean logic depends |
| 22:06.43 | vasc | ok but the boolean logic tree isn't in the order and some of those objects might not even be in that pixel even if they are in the tree |
| 22:07.03 | vasc | and how do you combine the segments |
| 22:07.58 | vasc | do you sometimes break partitions? |
| 22:08.07 | brlcad | disregarding all optimizations (and there are many), consider a ray going through a complex single object (one boolean recipe) |
| 22:08.13 | vasc | like split a primitive partition in the middle? |
| 22:08.34 | brlcad | you evaluate the ray against all the primitives, each returning a partition with segments in it |
| 22:09.01 | brlcad | since this is the same object, that drives a given boolean evaluation to know that those partitions are mergeable |
| 22:09.27 | brlcad | so it can look at each segment in turn, and apply the boolean expression rules |
| 22:09.52 | brlcad | which creates new segments, destroys segments, splits them, etc, based on the unions/subtractions/intersects |
| 22:10.46 | brlcad | evaluate the whole expression, and you're left with a partition with one or more segments for that object |
| 22:10.52 | vasc | from what i get you only need like three operators. union, intersection, and negation |
| 22:11.00 | vasc | and maybe the solid one |
| 22:11.09 | vasc | the others can be done as combinations |
| 22:11.27 | brlcad | it's boolean algebra, you technically only need two operators, but in practice more are used in order to do various optimization operations |
| 22:11.46 | vasc | the user might like them but it doesn't mean the machine uses them directly |
| 22:11.55 | vasc | its a RISCy way of seeing things |
| 22:12.17 | brlcad | e.g., A xor B is equiv to (A minus B) union (B minus A) |
| 22:12.33 | brlcad | but is evaluatable in one step, so I can put that in my boolean tree and cut two ops |
| 22:12.59 | vasc | the minus isn't a basic op either |
| 22:13.08 | vasc | i wonder how simplifiable that is |
| 22:13.11 | brlcad | sure it is |
| 22:13.25 | brlcad | basic CSG is union, subtraction (minus), and intersection |
| 22:13.49 | brlcad | boolean algebra brings in more concepts, but that's the userland of CSG |
| 22:14.19 | brlcad | for solid modeling, for example, there's no conceptualization of a not operator (even though we obviously use that construct when evaluating an expression for efficiency) |
| 22:15.06 | brlcad | you end up with infinity spaces, which violates notions of solidity closure testing |
| 22:15.34 | brlcad | you can certainly use it when evaluating though |
| 22:15.53 | vasc | i mean a-b is kinda like a|~(a&b) |
| 22:16.04 | vasc | or whatever |
| 22:16.09 | brlcad | yep, there are tons of transforms like that possible |
| 22:16.37 | brlcad | given the entire expression, there are reductions possible, sometimes even eliminations (called null object tree contraction in csg parlance) |
| 22:16.45 | vasc | yes |
| 22:16.59 | vasc | but let's say we support the goldfeather ones |
| 22:17.19 | vasc | union, intersection, difference |
| 22:17.37 | vasc | i think it has negation too |
| 22:18.09 | vasc | oh |
| 22:18.11 | brlcad | reductions are an optimization |
| 22:18.20 | brlcad | the algorithm should work regardless |
| 22:18.27 | brlcad | now normalization is a different topic |
| 22:18.32 | vasc | but brlcad has half-planes yes? |
| 22:18.46 | vasc | half-spaces |
| 22:18.51 | brlcad | want to use goldfeather's normalization approach, go for it (just recognize that it's one of many possible normalizations) |
| 22:18.55 | vasc | i just discard those right now |
| 22:19.09 | vasc | do we even use a normalization right now? |
| 22:19.11 | brlcad | they're a pain because they totally violate many notions :) |
| 22:19.24 | vasc | didn't seem like it |
| 22:19.25 | brlcad | librt has a variety of normalization routines |
| 22:19.30 | vasc | wow |
| 22:19.36 | brlcad | but for the eval, it just uses what it was given |
| 22:19.50 | brlcad | so you could do any normalization you wanted beforehand |
| 22:20.15 | brlcad | that's really your baseline that is needed regardless |
| 22:20.59 | brlcad | that's kind of getting ahead, optimizing something to evaluate less that doesn't yet evaluate anything :) |
| 22:21.43 | *** part/#brlcad Izakey (~Izakey@41.205.22.9) |
| 22:22.39 | vasc | forgot that one |
| 22:22.40 | brlcad | if the expression is A u B u C - D and D's segments completely overlap ABC (creating a null case), there's nothing wrong with the boolean evaluator doing the unions (wasted computation) at this point |
| 22:23.00 | brlcad | there's so much validation that has to happen to prove the evaluation is correct, it's not funny |
| 22:23.07 | vasc | its ok |
| 22:23.18 | vasc | i just want to understand the basic at this point |
| 22:24.59 | brlcad | it definitely gets more complicated too .. my earlier example was a single object that was mergeable -- continuing up a hierarchy (above the region level) where overlaps become possible introduces another layer of complexity |
| 22:25.57 | brlcad | A u B where A and B are not mergeable results in a separate partition for A and B with an overlap getting reporting |
| 22:26.08 | brlcad | this starts getting into the solid modeling domain |
| 22:27.26 | brlcad | and in that same context, A - B is okay even though it's really existentially questionable |
| 22:27.30 | brlcad | what is a copper sphere subtracted from a wooden cylinder, for example |
| 22:27.54 | vasc | its good for drilling holes |
| 22:27.59 | brlcad | definitely can't union them, but we can say the shape is subtractable as conventino |
| 22:28.41 | brlcad | at least without introducing a notion of multi-materials or different grouping operators |
| 22:28.58 | vasc | some unions aren't mergeable? |
| 22:29.13 | vasc | i mean i get all those log messages whenever i try to render everything |
| 22:29.16 | vasc | like OVERLAP whatever |
| 22:29.27 | brlcad | there's no copper in the wood, so subtracting it is kind of nonsensical except from a convention standpoint |
| 22:29.47 | vasc | i get that the surface materials will look uhh odd |
| 22:30.00 | brlcad | yep, those overlaps are technically modeling errors, but must be detectable and reportable |
| 22:30.00 | vasc | unless you nanocoat that wood |
| 22:30.23 | brlcad | if I coated it, I have introduced a new object C |
| 22:30.44 | vasc | it just grounded itself into the wood by friction you see |
| 22:30.54 | vasc | or something |
| 22:30.59 | brlcad | solid modeling works on a materials science basis as these things are meant to represent physical things manufactured |
| 22:31.06 | vasc | yeah |
| 22:31.12 | vasc | in that case what you want is tools |
| 22:31.26 | vasc | you have blocks of materials and you use TOOLS to carve them |
| 22:31.28 | vasc | not csg |
| 22:31.56 | brlcad | what's unobtanium subtracted from dark matter? or alloy #125 subtracted from alloy #82921 |
| 22:32.06 | brlcad | it's nonsensical |
| 22:32.11 | vasc | you can't subtract them |
| 22:32.18 | vasc | you can use a tool to drill a hole in it |
| 22:32.34 | vasc | or cut it |
| 22:32.47 | vasc | a materialess tool |
| 22:32.51 | vasc | made of fluffleware |
| 22:33.10 | brlcad | you're not getting it :) |
| 22:33.40 | brlcad | you posed a non-problem ... |
| 22:33.44 | vasc | yes |
| 22:33.52 | vasc | back to brass tacks |
| 22:34.16 | vasc | so the segments are indivisible and immutable |
| 22:34.18 | brlcad | that's why we do allow subtractions and by *convention* we basically treat it as materialless |
| 22:34.20 | vasc | but the partitions aren't |
| 22:34.46 | brlcad | but it's important to realize it's just convention -- would be completely valid to say it's an invalid operation too |
| 22:35.00 | brlcad | it's allowed because modelers do that kind of thing all the time |
| 22:35.01 | vasc | its until something better comes along |
| 22:35.16 | vasc | did you see that video the other guy showed? |
| 22:35.26 | *** join/#brlcad kintel (~kintel@unaffiliated/kintel) |
| 22:35.32 | brlcad | not all the way through my backlog yet, don't think so |
| 22:35.34 | vasc | http://www.mattkeeter.com/projects/antimony/3/ |
| 22:36.41 | vasc | ah whatever back to csg |
| 22:37.05 | vasc | its like this |
| 22:37.13 | vasc | i could reorder segments fine |
| 22:37.19 | vasc | it doesn't change array size |
| 22:37.41 | vasc | i could even change the boundaries of the partitions |
| 22:37.50 | vasc | at most you can have as many partitions as segments right? |
| 22:37.53 | vasc | so its bounded too |
| 22:38.05 | vasc | the problem is duplication, elimination, and crap like that |
| 22:38.57 | vasc | can you have duplicate segments? |
| 22:40.55 | vasc | i also don't get where the equivalents of rt_boolean_weave and rt_bool_final are in that code |
| 22:41.03 | vasc | the java one |
| 22:46.18 | brlcad | sure you can have duplicates |
| 22:46.26 | vasc | oh neat |
| 22:46.35 | brlcad | they'd be in different partitions |
| 22:46.59 | brlcad | in the same partition would probably be a bug in a primitive |
| 22:47.05 | brlcad | I think |
| 22:47.27 | brlcad | would have to think about that more, might be some weird procedural case where that'd be valid somehow |
| 22:48.20 | brlcad | like I said, you will need to pay attention to both segments and partitions |
| 22:48.38 | brlcad | but in terms of processing limits, coherency containers and such -- sure, I think that's a limit |
| 22:49.07 | brlcad | trying to think if you could have a boolean recipe where you'd end up with more segments than you start with... |
| 22:50.29 | brlcad | at least the naive case of 1 long segment getting chopped up 10 short segments will result in 11 segments, so 1+10 isn't violated |
| 22:50.41 | vasc | i need to read jansen's thesis better |
| 22:50.46 | vasc | i feel like we are missing something |
| 22:50.58 | vasc | even in this style of csg eval |
| 22:51.08 | brlcad | 2 long, 5 short subtractions on each gives 12, 2+5+5 is good |
| 22:51.14 | vasc | its 111 pages |
| 22:51.25 | brlcad | not at all surprising |
| 22:51.37 | vasc | of all the things i read his is the one that describes your techniques the most |
| 22:51.40 | vasc | for the bool eval |
| 22:52.26 | brlcad | link? feels like I read it, but not sure |
| 22:53.28 | brlcad | not that I can get into browsing a 111 page thesis right this minute.. heh |
| 22:53.38 | vasc | well he describes every method really |
| 22:54.04 | vasc | repository.tudelft.nl/assets/uuid...de4c.../TR%20DISS%201555(1).PDF |
| 22:54.12 | vasc | crap google |
| 22:54.30 | vasc | http://repository.tudelft.nl/assets/uuid:552472ce-de4c-42a9-9fb2-fd3919bb64b5/TR%20DISS%201555(1).PDF |
| 22:54.46 | vasc | start at page 43 |
| 22:55.19 | vasc | i keep skimming it. it's well written but i don't have the mood for it |
| 22:55.26 | vasc | maybe eventually it will sink in |
| 22:55.52 | *** join/#brlcad chick_ (~chick_@41.205.22.26) |
| 22:56.38 | brlcad | ahh, have to be careful -- there's a lot of research, this included that talks about boolean evaluation of boundary representations |
| 22:57.00 | brlcad | surface evaluation, not necessarily solid evaluation |
| 22:57.26 | brlcad | facetted modeling and doing booleans on facet sets is another topic altogether |
| 22:58.02 | brlcad | that's evaluating mesh against mesh, deriving resulting meshes |
| 22:58.28 | brlcad | this is very different from a ray-tracing based approach where you are directly evaluating primitives (and keeping them in implicit form) |
| 22:59.04 | brlcad | the basic applications of booleans is about the same, but just have to make sure you don't go down a rabit hole |
| 22:59.21 | brlcad | the java code should be more help in terms of figuring out how to apply booleans given two partitions |
| 23:01.24 | vasc | the talk about solids comes way before that |
| 23:01.38 | vasc | i think this is like the state of the art in csg whatever in 1989 |
| 23:01.41 | brlcad | on the surface, evaluating the segments is really really simple -- "A union B" takes the inHit of A to the outHit of B if the outHit of A comes after the inHit of B, resulting in a single segment ... otherwise it's two segments merged |
| 23:01.46 | vasc | and guess what the same techniques apply too |
| 23:02.03 | vasc | so why not do that? |
| 23:02.35 | brlcad | no reason not to! :) |
| 23:02.37 | brlcad | that's why I showed you the java code that distills it that simply |
