| --- Log opened Sat Aug 14 00:00:34 2010 |
| 00:10 | | AnnoDomini [annodomini@Nightstar-a39828b8.adsl.tpnet.pl] has quit [[NS] Quit: As I am. Zzzz.] |
| 01:00 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has joined #code |
| 01:01 | | shade_of_cpux is now known as cpux |
| 01:06 | | Derakon [Derakon@Nightstar-5213d778.ca.comcast.net] has joined #code |
| 01:06 | | mode/#code [+o Derakon] by Reiver |
| 01:08 | <@McMartin> | "But, because of the lo-hi storage order, the first byte coming from the file will actually be GGGBBBBB, and the second will be ARRRRRGG." |
| 01:09 | < Namegduf> | Appropriate? |
| 02:31 | | * Derakon eyes S-hull, tries to think of an efficient way to determine which nodes in a planar graph are visible to a given node "outside" the graph. |
| 02:31 | <@Derakon> | (Visible == edges connected the outside node to the node in the graph would not cross any existing edges) |
| 02:34 | <@Vornicus> | 1. convex hull. 2. backface culling. |
| 02:35 | <@Derakon> | Yes, I'm generating a convex hull as I go. More words? |
| 02:36 | <@Vornicus> | ...actually convex hull won't necessarily work. But backface culling will. ...hang on, gotta figure out how to describe. |
| 02:37 | <@Derakon> | ...heh, there's a typo in the S-hull paper. |
| 02:37 | <@Derakon> | "Porpagating". |
| 02:40 | <@Vornicus> | Okay, here's what you do. 1. find the closest node in the graph to your target node. |
| 02:41 | <@Vornicus> | 2. follow the "leftmost" edge -- the one that is angled closest to the target node. Then from there, follow the edges keeping left until you've gone all the way around the outer edge of the graph. |
| 02:42 | <@Derakon> | Those are the possible nodes to connect to, yes. |
| 02:42 | <@Vornicus> | 3. these edges represent the hull of the graph. |
| 02:42 | <@Derakon> | A.k.a. the external edges. |
| 02:42 | <@Vornicus> | Now, cull the edges that go the "wrong direction" |
| 02:43 | <@Derakon> | Define "wrong" as its angle relative to the position of the external node somehow? |
| 02:43 | <@Vornicus> | -- the ones that go left-to-right as seen by the external node. |
| 02:43 | <@Derakon> | Er... |
| 02:44 | <@Vornicus> | (as we started by going left, the visible edges will go right-to-left. |
| 02:44 | <@Derakon> | I'm not visualizing this properly, I'm afraid. |
| 02:44 | <@Vornicus> | And I don't have a decent drawing tool. :( |
| 02:44 | <@Derakon> | Let's say we have three nodes in the hull -- a triangle. |
| 02:44 | <@Derakon> | Make it equilateral for visualization's sake. |
| 02:45 | <@Derakon> | Place an external node so that it can't see one of the nodes in the triangle. |
| 02:45 | <@Derakon> | (e.g. put it opposite the obscured node) |
| 02:45 | <@Vornicus> | Okay. |
| 02:46 | <@Derakon> | So now we pick the closest node. This will automatically be visible. |
| 02:46 | <@Vornicus> | So then we pick the closest node. Right. |
| 02:46 | <@Derakon> | Now we examine the edges that node has... |
| 02:46 | <@Vornicus> | Now, we go to (what the external node sees as) the left. |
| 02:47 | <@Derakon> | Okay, let's break that down. |
| 02:47 | <@Derakon> | Get the angle from the external node to the closest node. That's our base angle. |
| 02:47 | <@Derakon> | Get the angles from the closest node to each of its neighbors, and subtract off the base angle. |
| 02:48 | <@Vornicus> | -- visit the closest node's neighbors. The one that is first going clockwise from the closest-target line is the one we want. |
| 02:48 | <@Derakon> | Find the smallest resulting angle (wrapping around at 2pi, of course), and take that? |
| 02:48 | <@Derakon> | Ah, okay. |
| 02:49 | <@Derakon> | Let's say our triangle has vertices (0, 1), (0, -1), and (-1, 0). |
| 02:49 | <@Derakon> | And our external node is at (1, 0). |
| 02:49 | <@Derakon> | We have two choices for closest internal node; let's say we picked (0, -1). |
| 02:49 | <@Derakon> | Our "next" node would then be (-1, 0), wouldn't it? |
| 02:50 | <@Vornicus> | Yes. That's. |
| 02:50 | <@Vornicus> | fine. |
| 02:50 | <@Vornicus> | We're going to keep going around until we visit the same edge in the same direction. |
| 02:50 | <@Derakon> | I don't follow. |
| 02:51 | <@Vornicus> | We go (0, -1) to (-1, 0) to (0, 1) to (0, -1) |
| 02:51 | <@Derakon> | Okay, but how does that help us determine which nodes are visible? |
| 02:51 | <@Vornicus> | This gives us the external shape of the gaph. |
| 02:52 | <@Vornicus> | These are all the nodes that are visible from /anywhere/ outside the graph. |
| 02:52 | <@Derakon> | (Seems to me it should be possible to maintain a list of external nodes as we add edges, as each new node is automatically external until a new edge occludes it) |
| 02:55 | <@Vornicus> | Well, yes, but the thing is we don't want to really see the innards of a complicated planar graph. |
| 02:55 | <@Derakon> | Fair. |
| 02:55 | <@Derakon> | Having generated this list of edges/nodes, then, we need to decide which are visible. |
| 02:56 | <@Vornicus> | So then, once we've gone through our graph, we then do two things: 1. backface cull -- any edge that goes left to right is invisible. |
| 02:56 | <@Derakon> | Which it seems to me could be decided as "the two nodes that are furthest away from each other along the vector perpendicular to that connecting the external and closest nodes are the last two visible") |
| 02:56 | <@Derakon> | Okay, in our example, which edges go left-to-right? |
| 02:57 | <@Vornicus> | In our example, (0, -1) to (-1, 0) to (0, 1) go left to right. |
| 02:57 | <@Derakon> | It's right-handed, yes? So ordering would be something like (0, 1), (-1, 0), (0, -1). |
| 02:57 | <@Vornicus> | (0, 1) to (0, -1) is going right-to-left. |
| 02:57 | <@Derakon> | ...it's vertical. ¬.¬ |
| 02:57 | <@Vornicus> | As seen from the target node. |
| 02:58 | <@Derakon> | Ah. |
| 02:58 | <@Derakon> | So the only edge we'd cull is the one we want to keep, which implies to me I got left-handed and right-handed confused. |
| 02:58 | <@Vornicus> | Yes. |
| 02:59 | <@Vornicus> | We want to cull those that are going left-to-right. |
| 02:59 | <@Vornicus> | Not those going right-to-left. |
| 02:59 | <@Derakon> | And then any node that is part of an unculled edge is visible? |
| 03:00 | <@Vornicus> | No. |
| 03:00 | <@Vornicus> | We also need to do z order culling. |
| 03:01 | <@Derakon> | Ugh. |
| 03:01 | <@Derakon> | Sort the nodes by their distance to the external node? |
| 03:02 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [[NS] Quit: ChatZilla 0.9.86 [Firefox 3.6.8/20100722155716]] |
| 03:06 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 03:06 | <@Vornicus> | Not necessarily - remember, the edge goes straight, but something behind it might be closer via the circle. |
| 03:07 | <@Derakon> | Mm, point. |
| 03:07 | <@Derakon> | Sort by distance along the vector from external node to closest node? |
| 03:08 | <@Derakon> | Even then, I'm not seeing what our cull condition is. |
| 03:09 | <@Vornicus> | Go through the edges (this can be slipstreamed into the backface cull) and keep track of the edges you keep /and/ the angles to each of the points on that edge, including rejected ones - consider a thing shaped like this: /_\ coming in from the top you might not see the interior nodes, but the edge will still cull things. |
| 03:10 | <@Vornicus> | (not a very good drawing) |
| 03:10 | <@Derakon> | Urgh. You know, I don't think I'm in quite the mental state to incorporate this. |
| 03:10 | <@Derakon> | Sorry. |
| 03:10 | <@Derakon> | Mind if we pick this up later? |
| 03:14 | <@Derakon> | Thanks for the help, though. |
| 03:14 | <@Vornicus> | Sure. |
| 04:37 | | 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!] |
| 04:45 | | Kazriko [kaz@Nightstar-e09690fa.client.bresnan.net] has joined #code |
| 04:45 | | mode/#code [+o Kazriko] by Reiver |
| 06:46 | | Derakon is now known as Derakon[AFK] |
| 08:08 | | Reiver [reaverta@ServerAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 08:10 | | AnnoDomini [annodomini@Nightstar-ace84000.adsl.tpnet.pl] has joined #code |
| 08:13 | | Reiver [reaverta@ServerAdministrator.Nightstar.Net] has joined #code |
| 08:13 | | mode/#code [+qo Reiver Reiver] by ChanServ |
| 08:16 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has joined #code |
| 08:40 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has quit [Connection closed] |
| 09:00 | | Netsplit *.net <-> *.split quits: @Vornicus, Alek, @Attilla, @Kazriko, @jerith, SmithKurosaki, Thaqui, AnnoDomini, @Reiver |
| 09:02 | | Netsplit over, joins: ~Reiver, @jerith, Thaqui, @Vornicus, @Kazriko, SmithKurosaki, @Attilla, AnnoDomini, Alek |
| 09:02 | | Reiver [reaverta@ServerAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 09:06 | | Reiver [reaverta@ServerAdministrator.Nightstar.Net] has joined #code |
| 09:07 | | mode/#code [+qo Reiver Reiver] by ChanServ |
| 09:28 | | You're now known as TheWatcher |
| 09:52 | | Rhamphoryncus [rhamph@Nightstar-bbc709c4.abhsia.telus.net] has quit [Client exited] |
| 10:02 | | Serah [Z@26ECB6.A4B64C.298B52.D80DA0] has quit [Ping timeout: 121 seconds] |
| 10:46 | | Attilla [Obsolete@Nightstar-4b1a7c86.threembb.co.uk] has quit [Ping timeout: 121 seconds] |
| 11:38 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has joined #code |
| 11:52 | | Vornicus [vorn@Nightstar-66efdaa0.ct.comcast.net] has quit [Ping timeout: 121 seconds] |
| 12:01 | | RichardBarrell [mycatverbs@Nightstar-689c9c54.cable.virginmedia.com] has joined #code |
| 12:39 | | celticminstrel [celticminstre@Nightstar-f8b608eb.cable.rogers.com] has joined #code |
| 12:57 | | 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!] |
| 13:31 | | RichardBarrell [mycatverbs@Nightstar-689c9c54.cable.virginmedia.com] has quit [Connection closed] |
| 15:22 | | Thaqui [Thaqui@27B34E.D54D49.F53FA1.6A113C] has quit [Connection closed] |
| 17:07 | | Derakon[AFK] is now known as Derakon |
| 17:21 | | Stalker [Z@26ECB6.A4B64C.298B52.D80DA0] has joined #code |
| 19:23 | | Netsplit *.net <-> *.split quits: Alek, Tarinaky, @Kazriko, SmithKurosaki, Stalker, AnnoDomini, @Reiver |
| 19:24 | | jerith [jerith@ServerAdministrator.Nightstar.Net] has quit [*.net ] |
| --- Log closed Sat Aug 14 19:24:36 2010 |
| --- Log opened Sat Aug 14 19:28:04 2010 |
| 19:28 | | TheWatcher [chris@Nightstar-b4529b0c.zen.co.uk] has joined #code |
| 19:28 | | Irssi: #code: Total of 17 nicks [4 ops, 0 halfops, 0 voices, 13 normal] |
| 19:28 | | mode/#code [+o TheWatcher] by Reiver |
| 19:28 | | Irssi: Join to #code was synced in 53 secs |
| 19:33 | | Tarinaky [Tarinaky@Nightstar-f349ca6d.plus.com] has quit [Connection closed] |
| 19:53 | | ToxicFrog [ToxicFrog@ServerAdministrator.Nightstar.Net] has joined #code |
| 19:53 | | mode/#code [+o ToxicFrog] by Reiver |
| 19:53 | | Syloq [Syloq@NetworkAdministrator.Nightstar.Net] has joined #code |
| 19:54 | | Syloq is now known as Syloqs-AFH |
| 20:11 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 20:18 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 20:34 | | Zed [Zed@Nightstar-e4835f03.or.comcast.net] has joined #code |
| 20:42 | | Stalker [Z@26ECB6.A4B64C.298B52.D80DA0] has quit [[NS] Quit: If the world didn't suck, we'd all fall off.] |
| 20:45 | | Stalker [Z@26ECB6.A4B64C.298B52.D80DA0] has joined #code |
| 21:06 | | Vornicus [vorn@Nightstar-66efdaa0.ct.comcast.net] has joined #code |
| 21:06 | | mode/#code [+o Vornicus] by Reiver |
| 21:13 | | Alek [omegaboot@Nightstar-c5f3565b.il.comcast.net] has quit [Ping timeout: 121 seconds] |
| 21:17 | | Alek [omegaboot@Nightstar-c5f3565b.il.comcast.net] has joined #code |
| 21:27 | | aoanla [AndChat@Nightstar-649942e1.range86-153.btcentralplus.com] has joined #code |
| 21:27 | | AndChat| [AndChat@Nightstar-649942e1.range86-153.btcentralplus.com] has joined #code |
| 21:27 | | aoanla [AndChat@Nightstar-649942e1.range86-153.btcentralplus.com] has quit [Client closed the connection] |
| 21:30 | | AndChat| [AndChat@Nightstar-649942e1.range86-153.btcentralplus.com] has quit [[NS] Quit: ] |
| 21:35 | | aoanla [AndChat@Nightstar-649942e1.range86-153.btcentralplus.com] has joined #code |
| 21:42 | | cpux_ [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 21:43 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 21:43 | | cpux_ is now known as cpux |
| 22:06 | | PinkFreud [WhyNot@NetworkAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 22:12 | | Rhamphoryncus [rhamph@Nightstar-bbc709c4.abhsia.telus.net] has joined #code |
| 22:14 | | Serah [Z@Nightstar-41ddd748.0.fullrate.dk] has joined #code |
| 22:15 | | Stalker [Z@26ECB6.A4B64C.298B52.D80DA0] has quit [Ping timeout: 121 seconds] |
| 22:18 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 22:22 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 22:34 | | Rhamphoryncus [rhamph@Nightstar-bbc709c4.abhsia.telus.net] has quit [Client exited] |
| 22:45 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has quit [Ping timeout: 121 seconds] |
| 23:10 | | aoanla [AndChat@Nightstar-649942e1.range86-153.btcentralplus.com] has quit [[NS] Quit: ] |
| 23:49 | | You're now known as TheWatcher[T-2] |
| 23:52 | | cpux [cpux@Nightstar-20a84089.dyn.optonline.net] has joined #code |
| 23:56 | | You're now known as TheWatcher[zZzZ] |
| --- Log closed Sun Aug 15 00:00:35 2010 |