#low@irc.freenode.net logs for 4 Nov 2003 (GMT)

Archive Today Yesterday Tomorrow
LoW homepage

[00:06:09] <Coren_> Ack. There is a near-fatal flaw in my algorithm.
[00:06:54] * Coren_ will need to be very creative to figure out a way around that.
[02:38:11] <-- servus has left IRC (Read error: 110 (Connection timed out))
[06:05:45] --> servus has joined #low
[06:25:02] <Coren_> Erm. qbsp3 sucks greatly at wide open spaces.
[06:25:59] <Coren_> Castle british: 676 sectors; 392 of which are for the throne woom alone!
[06:28:14] <servus> Why do you think id has never made an outdoors game? :)
[06:29:24] <Coren_> The throne room is hardly "outdoors". I don't even dare try the sewers. :-)
[06:29:34] <servus> Tal-Or-Us. ;-)
[06:30:16] <servus> I haven't even implemented my PVS info yet, so I can't speak, but I don't foresee any huge problems... I know how I'm going to make the PVS tree, and it'll be fast to compute.
[06:31:16] <servus> I sure wish I could use fragment programs... I'd be so much further with my program by now!
[06:33:03] <servus> I'm moving away from those NV extensions, and everything turns into a hack to get per-pixel computations! Ugh!
[06:33:26] <Coren_> Look at http://tab.ctrl-alt-del.ca/~marc/hall.png
[06:33:32] <Coren_> Seems reasonable, yes?
[06:35:07] <Coren_> Now look at http://tab.ctrl-alt-del.ca/~marc/tr.png and witness how qbsp3 can turn a simple room into hamburger. :-)
[06:36:03] <servus> Why is hall so tesselated?
[06:36:56] <servus> Are you just feeding it the raw tiles from UW?
[06:37:07] <Coren_> "tesselated" means "turned into triangles". It's not. But it's subdivided a bit too agressively, but not so you'd complain. This actually does Good Things to light projection because it increases the chances of obstructions.
[06:38:00] <servus> tessellate - To form into a mosaic pattern, as by using small squares of stone or glass.
[06:38:13] <servus> From Latin tesselltus, of small square stones, from tessella, small cube, diminutive of tessera, a square.
[06:38:22] <Coren_> In CG, specifically, it means turn into triangles. :-)
[06:38:22] <servus> Mwuahahah. How does subdivision help the engine?
[06:39:28] <servus> Pfft, you get to play with fragment programs! *Pout*
[06:40:06] <Coren_> Because the smaller the sectors are, the higher the odds that it will never be reached by the light/viewpoint. Up to a point, of course, because too many sectors and traversing the portals becomes expensive. The Hall is nearly "just right" but you can see why the TR gives me headaches.
[06:41:04] <Coren_> Actually, my algorithm is O((s/p)^3); where s is the number of visible sectors and p the number of visible portals.
[06:41:11] <servus> However, in a wide-open-space, isn't it most likely that the entire plane will be viewed at once? I thought you clipped planes anyways, so tree-side-subdivision was superfluous?
[06:41:35] <Coren_> It is superfluous. I'm just having trouble convincing qbsp3 of it. :-)
[06:41:50] <servus> I assume you have the code. Good luck deciphering it. :)
[06:42:25] <servus> I started my project using qbsp3 until I realized precisely what it was. *grin*
[06:42:47] <Coren_> I'm probably going to get rid of the Q2 tools entirely. It's getting harder to fix them to my needs than it would be to whip something up from scratch.
[06:43:07] <Coren_> I was /really/ hoping I could use the Q2 editors, though. *sigh*
[06:43:19] <servus> Oh come now! .map files are **easy** to interpret!
[06:43:59] <servus> Using another game's editor is reasonable, but another game's compiler?
[06:44:02] <Coren_> Yes, but deriving the data I need from that representation is an NP-complete problem.
[06:44:45] <servus> I think my next engine will use some voxel-inspired display techniques...
[06:44:57] <Coren_> I was hoping iD did much of that work; turns out qbsp3 is ugly and not even near optimal. It, surprisingly, does a rather crummy job of it in fact.
[06:45:14] <servus> Well, Quake3 maps *do* run fast on lowend hardware.
[06:45:26] <servus> Their interpretation of the compiled maps is probably better, is all.
[06:46:41] <Coren_> No thanks to their code, I can garantee you. It generates *vastly* suboptimal splits. I would say that any map it produces has at least 3 times more splits than would have been truly needed, and the engine is forced into a great deal of unnecessary (because the data was there) overdraw.
[06:47:00] <servus> I can do per-pixel attenuation and bumpmapping with 2 TUs if I use a 3D attenuation texture, or 3 units if I use 2D attenuation textures... Which do you think?
[06:47:04] <Coren_> They simply skirted around their bad code with very good level design.
[06:47:21] <Coren_> I use 2 and a 3d-texture.
[06:47:27] <Coren_> Like you didn't know. :-)
[06:47:30] <servus> But 3D textures are ramhogs!
[06:47:56] <Coren_> Trust me, you *really* don't need a big one. 64^3 is more than enough. You've seen how my engine looks.
[06:48:21] <Coren_> In fact, the screenshots you've seen use a 32^3 texture. :-)
[06:48:22] <servus> That's 262K for a one-byte texture, though I guess that's a pretty standard grayscale depth...
[06:48:45] * servus shrugs... I wonder how common 3D textuer support is
[06:49:16] <Coren_> The correlation between the presence of _dot3 and _texture3d is ~95%
[06:50:03] * Coren_ chuckles. "So, in effect, your code is looking more and more like mine."
[06:50:16] <servus> Hardly!
[06:50:23] <servus> We use vastly different methodologies
[06:50:48] <Coren_> I mean, as far as the end render goes. We just decide /what/ we render quite differently.
[06:50:55] <servus> Besides, my shadow screenshots have been better so far >:)
[06:51:21] <servus> I think you're afraid to put complicated objects in your map:)
[06:51:24] <Coren_> Err, no. I've yet to see any of your screenshots with proper diffuse lighting, let alone bumpmapping. :-)
[06:52:00] <servus> How is this not proper lighting?
[06:52:18] <Coren_> You attenuate strictly by distance.
[06:52:34] <servus> You were expecting BRDF?
[06:52:47] <servus> A Fresnel term?
[06:53:06] <Coren_> No, but I was expecting angle of incidence being taken into account. Even GL Vertex lighting gets that. :-)
[06:53:20] <servus> That's a specular highlight.
[06:53:23] <servus> I don't even want those yet. :)
[06:53:50] <Coren_> No, specular highlights are hightlights derived from the angle between the angle of incidence and the viewpoint.
[06:54:45] <Coren_> At a given distance, the light that diffuses from a surface is proportional to the cosine of the angle between the light vector and the plane normal.
[06:54:57] <servus> Beside, what you describe will be *easy* for me to implement.
[06:55:01] <Coren_> Not just the distance.
[06:55:02] <servus> Just a few lines of VP asm. :)
[06:55:39] <servus> Although I'd like to first research a better way of doing it than vertex-wise...
[06:56:17] <Coren_> And yes, I *am* affraid to put complex obstructions in my map. You've /seen/ what a mess qbsp did around the simple columns. :-)
[06:56:29] <servus> Heh.
[06:56:41] <servus> How about some sort of bounding box system?
[06:56:59] <servus> If you were to put a... spiky starfish in the middle of your room, you'd surround it with an AABB or OBB sector?
[06:57:04] <Coren_> Heh. I did correct diffuse terms per fragment even before I had bumpmapping. :-)
[06:57:20] <servus> With a fragment program?
[06:57:41] <servus> If I wanted to do it with my current system, I'd have to add exactly two lines, and I know what those two lines are.
[06:57:44] <Coren_> Nope. Never *did* understand the stroke of genius that went into that 3d-texture, did you? :-)
[06:57:47] <servus> I don't want to bother with it right now.
[06:58:08] <Coren_> Hint: It's not RGB for no reason.
[06:59:12] <servus> Eek, double negatives!
[06:59:21] <Coren_> Every textel is a *denormalized* vector from the center of the texture, scaled by the square of the distance. Color the geometry with its normal (or map a normal map on it) and just _dot3 with the 3d texture. Voila
[06:59:31] <Coren_> s/textel/texel/
[07:00:08] <Coren_> Alternatively (that's what I do) paint the geometry with (0, 0, 1) and rotate the 3d texture.
[07:01:05] <servus> Okay
[07:01:15] <Coren_> The latter way allows you to paint the normal map with no processing whatever.
[07:01:16] <servus> So your 3D texture is a starburst of vectors?
[07:02:23] <Coren_> Specifically, every texel is the normalized vector of the direction from the center of the texture to the center of the texel, divided by the distance squared.
[07:02:50] <Coren_> So you get /both/ distance attenuation and the angle of incidence for free in one operation. :-)
[07:04:09] <servus> And you use that tex-vector for the dot
[07:04:18] <Coren_> And, because of linear filtering, you get pretty damn good results with fairly low resolution. The difference between 32^3 and 64^3 is minuscule and undetectabe in normal cases.
[07:04:41] <Coren_> Yes, after the texture has been suitably rotated so that its (0, 0, 1) faces the plane normal.
[07:04:51] <Coren_> (The origin of the texture is, of course, the lightsource)
[07:05:02] <servus> And you just take the vector, and divide it by the size of your texture, so that vectors near the edge of the texture are very dark?
[07:05:31] <Coren_> I don't get that last part.
[07:06:12] <Coren_> Ah, yes, the vector is mapped to [0 ... 1] with 0 at the edge of the texture.
[07:08:32] <servus> So you get a less drastic bumpmap at the edge of the attenuation as well?
[07:09:35] <Coren_> Yes an no; the effect is visibly pronounced but then distance attenuation kicks in. It ends up beging 'right'. Lighting a long corridor will let you see little but the bumps that face the light when far.
[07:10:31] <Coren_> [and the light is close to the surface; a light high overhead 'flattens' the bumps as it should]
[07:11:37] <Coren_> You may now admit being awed by my stroke of genius. I've checked. If anybody every figured that trick out yet, they're keeping it secret and it hasn't been used in a known game engine. :-)
[07:12:22] <servus> How about using an always-unit-length vector instead, and putting brightness in the alpha?
[07:12:43] <servus> That way you don't lose the precision.
[07:13:21] <servus> But yep, it's good. I'll keep it in mind
[07:13:33] <Coren_> _dot3 isn't quite as efficient if you mess with alpha as well. Besides, the precision loss is, by definition, where the light is dimmest so the artefacts are neglectable.
[07:15:22] <servus> _dot3 doesn't use the alpha channel, I believe.
[07:15:44] <servus> Yeah, only GL_DOT3_RGBA_ARB does
[07:15:58] <servus> That's why you're free to use it how you will.
[07:16:33] <Coren_> Hm. Might have misread that part. At any rate, it's worth checking out if the added precision is worth 33% increase in texture size.
[07:17:01] <Coren_> Hm. And the need to then blend with alpha.
[07:17:28] <Coren_> The advantage of that might actually vary from card to card; would be worth putting as runtime option.
[07:17:59] <Coren_> I expect it might be a noticable gain on cards which have fairly low precision in the fragment pipeline.
[07:18:46] <servus> Want a very simple version of my room in .map? :D
[07:19:21] * Coren_ chukles. Yes, although I won't be able to do much with it just yet. I'm in the middle of messing with my code.
[07:19:40] <servus>
[07:19:43] <servus> Ah okay
[07:19:50] <Coren_> It'd be fun to compare-- although it'll look a bit drab with everything rendered in nice, bumpy bricks. :-)
[07:19:53] <servus> I also put together a cheat sheet on ARB vertex programs, if you want.
[07:20:25] <Coren_> I'm staying away from those until they get wider support.
[07:20:28] <servus>
[07:20:36] <servus> How do you do vertex programs?
[07:20:43] <servus> Not fragment program, vertex program!
[07:20:48] <Coren_> Ah!
[07:21:12] <servus> At the least, that .txt has been invaluable to me so far... much more efficient than scrambling through the spec:)
[07:21:16] <Coren_> I don't use vertex programs in my code, actually. Not by concious decision, simply because I don't need them.
[07:21:47] <servus> Erm, how do you transform a normal map to tangent space?
[07:22:19] <Coren_> I don't have to! :-) I rotate the light texture!
[07:22:35] <servus> Your method won't work with vertex arrays then
[07:22:41] <servus> Thus, a vertex program is needed
[07:22:55] <servus> However, it'd be simpler to have my vertex program simply rotate the texture matrix..
[07:23:26] <Coren_> If you have triangles in the array that lie on different points, you're right.
[07:23:32] <servus> Though my vertex program is currently rather snappy.
[07:23:45] <servus> Remember that my engine supports, say, a triangle floating in the middle of space.
[07:24:01] <Coren_> But then you can still transform the normal map and leave the light texture oriented along (0, 0, 1)
[07:24:24] <servus> It amounts to the same thing.
[07:24:33] <servus> My vertex program currently works and it is very light, just a few dots.
[07:25:01] <Coren_> Yes, you carve shadows out of space. I push light into it. Your engine would kick butt in open spaces; whereas mine will be faster in cramped spaces with lots of occlusions.
[07:25:30] <servus> I actually use light volumes, not shadow volumes, now.
[07:26:13] <Coren_> Then you need to be able to cope with concave volumes or you *really* don't want too many of them floating triangles around. :-)
[07:26:27] <servus> I already cope with concave volumes.
[07:26:36] <servus> It's a happy side effect of my system
[07:26:45] <servus> Floating triangles, solid convex objects, they're all the same to me.
[07:27:14] <Coren_> Can't wait to see it in action with a non-toy world and bumpmapping, then. :-)
[07:27:41] <servus> Well, once I put my PVS info in, it should be unaffected by the amount of nonvisible data.
[07:28:21] <servus> My biggest bottleneck is in the rasterization area, if you can believe that
[07:28:28] <servus> Shadow volumes are fragment happy.
[07:28:35] <Coren_> ... which is a nice side effect of /my/ system. I don't need a PVS, I get exact visibility data for free. :-)
[07:28:59] <servus> Make some complex shadows, and we'll talk. :)
[07:29:06] * servus snickers evilly.
[07:29:54] <Coren_> Feh. The light in foo2.bsp is actualy very complex; you just don't see it. qbsp3 split that room in something like 30 sectors. :-)
[07:29:55] <servus> Once I finish this, I plan on popping a lot of the code into my Marble Madness program... my physics here are much better, faster, etc, and my support for nontrivial objects is better... I can create a full game! :D
[07:30:02] <Coren_> foo2.png
[07:30:20] <servus> Those pngs are huge, btw
[07:30:38] <Coren_> Yes, well, the cost of 24 bit color. :-)
[07:30:47] <servus> >.<
[07:31:12] <servus> They should make a mode for pallettized images of n-bit precision... None of this either-8-bit-or-24-bit nonsense!
[07:31:37] <servus> 12 bits would provide a very nice palette range indeed
[07:32:14] <servus> Okay okay, I have to get to work, I spend way too much time chatting
[07:32:19] <Coren_> *sigh*
[07:32:27] <Coren_> At any rate, *I* am back to my original problem.
[07:32:35] <servus> Lack of tools?
[07:32:56] <servus> Why can't you reprogram qbsp?
[07:33:07] <servus> I realize the code is disgusting, but...:)
[07:33:18] <Coren_> World editor mostly. I can definitely generate near-optimal sectors from the original tiled data, but then modifying the geometry to modernize it a bit would be a pain.
[07:33:48] <servus> I doubt you want to invest in a new approach?
[07:34:11] <servus> Do it with voxels. *Evil grin*
[07:34:18] <Coren_> You doubt right. While the lack of tools is a pain, the implementation is snappy and works wonderfully.
[07:34:31] <servus> I still think you should make a .map compiler
[07:35:19] <Coren_> Yeah, I would were my linear algebra up to snuff. iD tried and failed at what I need to do.
[07:36:16] <Coren_> From a random .map, I'd need to generate the set of the least number of concave volumes that describes the space bounded by csg. HARD problem.
[07:36:48] <servus> Oh, I know, I know, I've tried.:)
[07:36:51] <Coren_> Whereas from the tile data, I *know* what a 'room' is, and can generate the volumes appropriately in the first place.
[07:37:11] * servus is happy he took the caveman approach
[07:37:13] <Coren_> Hey, waitaminit!
[07:37:24] <Coren_> I've just had an idea!
[07:37:34] <servus> Does it involve cavemen?
[07:38:34] <Coren_> Generate 'rooms (volumes I know are large as possible, and concave) then feed them *individually* to qbsp3 (that does a good job when you don't give it anything complicated) then collect and stich the pieces together!
[07:39:02] <servus> That's good, but where's the caveman?
[07:39:18] <servus> Stitching them together will give an optimal flow?
[07:39:22] <Coren_> He's the one doing the stitching with deerhide.
[07:39:26] <servus> >.<
[07:39:55] <Coren_> If I split 'right'. But I'm working with tile data, so I can actually generate the optimal splits by strict brute force if needed.
[07:39:56] <servus> Does QBSP quantify maps (snap them to a grid)?
[07:40:21] <servus> Snap each point/plane to a grid, that is.
[07:40:26] <Coren_> No. Actually, QBSP will keep any vertex you feed it intact.
[07:40:46] <servus> Leaks aren't a problem if you're not compiling it from arbitrary data, I suppose
[07:42:16] <Coren_> Well, bedtime for me. I'll go dream about my new scheme for a few hours.
[07:42:19] * Coren_ waves.
[07:44:17] * Coren_ is away: sleep
[17:24:03] * Coren_ is back
[22:40:10] --> Dark-Star has joined #low
[22:40:10] <-- Coren_ has left IRC (Read error: 104 (Connection reset by peer))
[23:47:42] <-- Dark-Star has left IRC ()