| --- Log opened Sat Nov 13 00:00:40 2010 |
| 00:02 | | Orthia [orthianz@Nightstar-53889107.xnet.co.nz] has joined #code |
| 00:16 | | cpux is now known as cpux[uggh] |
| 00:23 | | Orthia [orthianz@Nightstar-53889107.xnet.co.nz] has quit [Connection reset by peer] |
| 00:32 | | Orthia [orthianz@Nightstar-53889107.xnet.co.nz] has joined #code |
| 00:33 | | kwsn [kwsn@Nightstar-ca9721ae.dyn.centurytel.net] has joined #code |
| 01:08 | | RichardBarrell [mycatverbs@Nightstar-3b2c2db2.bethere.co.uk] has joined #code |
| 01:09 | <@McMartin> | Man. Still not sure what it says about me that when I think "I should write a program to solve this problem for me" my first thought is for that program to be in Haskell |
| 01:09 | <@McMartin> | Though in this case I guess it *is* a graph theory problem |
| 01:17 | | Anno[Laptop] [annodomini@Nightstar-a4c2923e.adsl.tpnet.pl] has quit [[NS] Quit: Sleep.] |
| 01:22 | | Derakon[AFK] is now known as Derakon |
| 01:34 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has joined #code |
| 02:24 | | Derakon is now known as Derakon[AFK] |
| 02:41 | | gnolam [lenin@Nightstar-38637aa0.priv.bahnhof.se] has quit [[NS] Quit: Z?] |
| 02:41 | < RichardBarrell> | McMartin: pure functional graphs are a bit of a mindscrew, unless you opt for the very straightforward representations such as (Data.Map Int (label, [Int]). |
| 02:42 | <@McMartin> | Which is really all I'd need for this. |
| 02:42 | <@McMartin> | The problem is, given an undirected graph, find its Bacon Equivalent Node. |
| 02:42 | <@McMartin> | That is, the one from which the largest possible number of nodes are the smallest number of average hops from. |
| 02:43 | < RichardBarrell> | Huh. That is not the definition for "Bacon node" that would have occurred to me. |
| 02:43 | <@McMartin> | You have to say "largest connected subgraph" because otherwise isolates win with an average number of hops of zero~ |
| 02:45 | < RichardBarrell> | I would have expected that you'd want the node "Bacon" which minimised (maximum, ?v, distance between "Bacon" and v). |
| 02:45 | < RichardBarrell> | Apologies for my godawful notation. |
| 02:46 | < RichardBarrell> | (With the Dijkstra-ish assumption that the distance to any node that isn't connected is infinite. So, um, my idea of "bacon" is only interesting to find for connected graphs.) |
| 02:48 | < RichardBarrell> | Anyway. There's a library called "fgl" on Hackage, which implements an inductive implementation of graphs. |
| 02:50 | < RichardBarrell> | There's also a Data.Graph in the "containers" library, which I think ships with GHC 6.12. That one is based on purely functional arrays, so lookups are fast constant time but resizing arrays to add vertices or edges one by one is quadratic. |
| 02:51 | < RichardBarrell> | Or if you're going to implement graphs as (Data.Map Int (label, [Int])) then please use (Data.IntMap (label, [Int])) instead. Data.IntMap is just a more-efficient specialisation of Data.Map to Int keys. :) |
| 02:52 | < RichardBarrell> | I'm not sure how good fgl is in practice. I think I've heard people bandying about the idea that it works well for up to a few tens of thousands of vertices, but I don't really know. Its implementation led to a -really- cool paper, though. :D |
| 02:52 | < RichardBarrell> | McMartin: does any of that help at all, please? |
| 02:52 | < RichardBarrell> | I await your answer with bated breath, from the floor. |
| 02:58 | <@ToxicFrog> | I propose that we call it the MAXIMUM BACON NODE. |
| 02:59 | <@McMartin> | Sorry, I was AFK |
| 02:59 | <@McMartin> | Reading backscroll now |
| 03:00 | <@McMartin> | OK |
| 03:00 | <@McMartin> | In order |
| 03:00 | <@McMartin> | (a) Yours is defined only on connected graphs, which is fair, but you fix that by first restricting yourself to nodes in the largest connected subgraph. |
| 03:01 | <@McMartin> | (b) You're defining "lowest maximum" instead of "lowest average", and under certain kinds of graph shapes that produces what I would consider unintuitive results |
| 03:02 | <@McMartin> | In particular, if you had something shaped like a dandelion in seed, I'd want the result to be in the middle of the dense cloud, while you would put it a little over halfway up the stem |
| 03:02 | <@McMartin> | No reason to not compute both at once, though~ they seem related in a way not dissimilar to mean vs median |
| 03:03 | <@McMartin> | (Continuing that metaphor, the 'mode' equivalent would be the node that had the largest number of edges it was part of) |
| 03:03 | <@McMartin> | (I'm not sure if that one should be restricted to largest-subgraph though it's very likely to except in very unusual cases) |
| 03:05 | <@McMartin> | And now I AFK again! |
| 03:23 | < RichardBarrell> | McMartin: I was assuming maybe you'd want a bacon node per connected subgraph. I hadn't thought of dandelion shapes. It'd be kind of neat to ask for given graphs how near max-bacon and avg-bacon are to one another. |
| 03:24 | < RichardBarrell> | ToxicFrog: you've caused me to think of them a MAXIMUM BACON NODE and MEAN BACON NODE. I'm going to have to find a random human on deviantart and commission visual representations of both of those phrases. :) |
| 03:25 | < RichardBarrell> | McMartin: peace and good luck with silly graph libraries. ^_^ |
| 03:25 | | RichardBarrell [mycatverbs@Nightstar-3b2c2db2.bethere.co.uk] has quit [[NS] Quit: zzzzzzzzzz] |
| 03:25 | | * McMartin totally read that as MAXIMUM BACON MODE |
| 03:25 | <@McMartin> | Obviously a setting in far-future cantinas |
| 03:26 | <@Namegduf> | I've ordered MAXIMUM BACON MODE buns before. |
| 03:30 | <@McMartin> | Actually |
| 03:30 | <@McMartin> | MAXIMUM BACON NODE would be a *superb* name for a diner. |
| 03:30 | <@Vornicus> | Mmmm, maximum bacon. |
| 03:59 | | Kazriko [kaz@Nightstar-e09690fa.client.bresnan.net] has quit [Ping timeout: 121 seconds] |
| 04:00 | | Orthia [orthianz@Nightstar-53889107.xnet.co.nz] has quit [Ping timeout: 121 seconds] |
| 04:06 | | Kazriko [kaz@Nightstar-e09690fa.client.bresnan.net] has joined #code |
| 04:06 | | mode/#code [+o Kazriko] by Reiver |
| 04:17 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
| 04:21 | | Rhamphoryncus [rhamph@Nightstar-473f8685.abhsia.telus.net] has quit [Client exited] |
| 04:48 | | Orthia [orthianz@Nightstar-3346512d.xnet.co.nz] has joined #code |
| 05:10 | | kwsn [kwsn@Nightstar-ca9721ae.dyn.centurytel.net] has quit [Ping timeout: 121 seconds] |
| 06:16 | | cpux[uggh] is now known as shade_of_cpux |
| 07:01 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| 07:05 | | Derakon[AFK] is now known as Derakon |
| 07:44 | | Derakon is now known as Derakon[AFK] |
| 07:47 | | Vornicus is now known as Vornicus-Latens |
| 08:59 | | Anno[Laptop] [annodomini@Nightstar-a4c2923e.adsl.tpnet.pl] has joined #code |
| 09:11 | | You're now known as TheWatcher |
| 09:40 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has quit [Connection closed] |
| 11:19 | | Rhamphoryncus [rhamph@Nightstar-473f8685.abhsia.telus.net] has joined #code |
| 12:31 | | thalass [thalass@5A981D.2CB1A3.012A9B.AA31F5] has joined #code |
| 12:31 | < thalass> | Evening all |
| 12:44 | | thalass [thalass@5A981D.2CB1A3.012A9B.AA31F5] has quit [[NS] Quit: Leaving] |
| 13:02 | | Anno[Laptop] [annodomini@Nightstar-a4c2923e.adsl.tpnet.pl] has quit [Ping timeout: 121 seconds] |
| 13:04 | | Anno[Laptop] [annodomini@Nightstar-520aa444.adsl.tpnet.pl] has joined #code |
| 13:37 | | gnolam [lenin@Nightstar-38637aa0.priv.bahnhof.se] has joined #code |
| 14:07 | | Gruber [lenin@Nightstar-38637aa0.priv.bahnhof.se] has joined #code |
| 14:07 | | gnolam [lenin@Nightstar-38637aa0.priv.bahnhof.se] has quit [Ping timeout: 121 seconds] |
| 14:08 | | Gruber is now known as gnolam |
| 14:31 | | RichardBarrell [mycatverbs@Nightstar-689c9c54.cable.virginmedia.com] has joined #code |
| 15:29 | | You're now known as TheWatcher[afk] |
| 15:36 | | kwsn [kwsn@Nightstar-ca9721ae.dyn.centurytel.net] has joined #code |
| 15:53 | | shade_of_cpux is now known as cpux[uggh] |
| 15:53 | | cpux[uggh] is now known as cpux |
| 16:32 | | RichardBarrell [mycatverbs@Nightstar-689c9c54.cable.virginmedia.com] has quit [Ping timeout: 121 seconds] |
| 17:06 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has joined #code |
| 17:59 | | Derakon[AFK] is now known as Derakon |
| 18:30 | | * gnolam hmms. |
| 18:33 | < gnolam> | I think I might have to do some creative filtering of my tone mapping buffer. |
| 18:34 | < gnolam> | Otherwise, even extremely bright spots (e.g. the sun) get lost in the final (4x4) buffer. |
| 18:37 | < gnolam> | Any input? |
| 18:39 | <@Derakon> | I'm afraid I don't have the graphics chops to comment usefully here. |
| 18:44 | <@Vornicus-Latens> | Tone mapping... what, you're making a map of the sky and then using that for, uh... ambient occlusion or some such? |
| 18:48 | < gnolam> | HDR. |
| 18:49 | < gnolam> | Where tone mapping is a pretty much a fancy way of saying "use whatever light intensities you fancy, and then scale into a desired result". |
| 18:51 | <@Vornicus-Latens> | I'm not sure then. |
| 18:53 | < gnolam> | Normally, that scaling is to pretty much divide by the maximum intensity in your scene (with some additional fancy stuff, like adaptation delays or weighting by the position in the player's FOV). |
| 18:54 | <@Derakon> | Oh, but you change the divisor depending on area so you can have e.g. deeply shadowed areas next to really bright areas? |
| 18:54 | <@Derakon> | And the tone mapping is your divisor? |
| 18:56 | <@Vornicus-Latens> | The tone map I suspect is something the program renders to to determine the maximum intensity... but since the sun is very small, it doesn't actually contribute much to the tone map. |
| 18:57 | < gnolam> | The tone mapping is the whole scaling bit (technically, it's /any/ f: color -> color mapping, but eh). |
| 18:57 | < gnolam> | Anyway. The problem is finding the scaling factor. |
| 18:58 | <@Vornicus-Latens> | er, rather, the tone mapping buffer. |
| 18:58 | < gnolam> | Right. |
| 18:58 | <@Vornicus-Latens> | Is something the program renders etc etc etc |
| 19:00 | < gnolam> | Everything is rendered to an FBO. That FBO is then scaled down to a tone map buffer, whose values are fetched through a glReadPixels() call and examined to get a scaling factor. |
| 19:02 | <@Vornicus-Latens> | If you could use a "max" or "min" filter -- or both -- you could really get somewhere. |
| 19:03 | < gnolam> | You can't use the entire screen because A) getting data out of video memory is sloooooow and so you want as small a data set as possible, and B) you'd have to do a pixel-by-pixel read on an entire screen-sized buffer on the CPU every frame. |
| 19:03 | < gnolam> | So my final buffer is 4x4 pixels. |
| 19:04 | < gnolam> | Vornicus: yeah, that's what I was thinking. Adapting my gaussian blur shaders to do a max of neighboring intensities instead. |
| 19:13 | < gnolam> | Hmm... maybe I can do both? In the bloom pass, calculate and store max intensities in the alpha channel. |
| 19:13 | < gnolam> | No wait. That wouldn't work. I have to do blooming after the tone mapping. Bugger. |
| 19:33 | | Taki^ [ikat@Nightstar-0816732d.consolidated.net] has quit [Ping timeout: 121 seconds] |
| 19:37 | | Taki^ [ikat@Nightstar-0816732d.consolidated.net] has joined #code |
| 19:54 | | Taki^ [ikat@Nightstar-0816732d.consolidated.net] has quit [Ping timeout: 121 seconds] |
| 19:55 | | You're now known as TheWatcher |
| 19:58 | | Taki^ [ikat@Nightstar-0816732d.consolidated.net] has joined #code |
| 20:52 | | Taki^ [ikat@Nightstar-0816732d.consolidated.net] has quit [Ping timeout: 121 seconds] |
| 20:56 | | Taki^ [ikat@Nightstar-0816732d.consolidated.net] has joined #code |
| 21:33 | | Taki^ [ikat@Nightstar-0816732d.consolidated.net] has quit [Ping timeout: 121 seconds] |
| 21:38 | | Taki^ [ikat@Nightstar-0816732d.consolidated.net] has joined #code |
| 22:09 | < gnolam> | Tested with the blur shaders with a max function instead of a gaussian kernel. Much better, but there's something wrong with the pingponging. I should probably code this properly instead of inserting ugly hacks into the pipeline... |
| 22:21 | | Rhamphoryncus [rhamph@Nightstar-473f8685.abhsia.telus.net] has quit [Client exited] |
| 22:41 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
| 23:55 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| --- Log closed Sun Nov 14 00:00:42 2010 |