?

Log in

No account? Create an account
We do what we must, because we can - Spectre Gruedorf Challenge Blog [entries|archive|friends|userinfo]
Spectre Gruedorf Challenge Blog

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

We do what we must, because we can [Mar. 22nd, 2008|02:44 am]
Spectre Gruedorf Challenge Blog

spectreblog

[mad_and_crazy]
A token update because, for once, I had a busy week. Sadly, not much has gotten done this week, and hence my Lame Score will go up.

At least, nothing with pictures of it anyway. Some days, most of what you do just consists of fucking about writing systems code that doesn't do anything useful. Other days, you do research that goes nowhere. And this, too, is part of life. So, let us discuss and analyze what's been up - in terms of Spectre code, at least.

This week, specifically, I spent a great deal of time working on the code to kill T-Junctions. It completely fails to do this. I honestly don't know why this is giving me such trouble, but I think it's because I'm too lazy to write code to generate a proper data structure for doing edge collapses and splits "nicely". I think I'm thinking of what you would call a double-winged edge list if you were a comp. sci nerd, but Matthew will probably tell me that this isn't what it's called at all. Oh well. I will probably write the damn nice data structure this weekend and then maybe CSG will not fail.

Interestingly enough, you mainly get T junctions where the 'split triangles' from object A meet the split triangles from object B. Remember that the Thibault + Naylor CSG algorithm operates by feeding polygons (Naylor calls this 'a B-Rep', which I'm guessing is short for boundary representation?) from object A into a BSP tree representation of object B, and then only keeping the bits that are on the outside of the other object. The actual output before you put the two halves together seems to be T-junction free, or at least nothing that a vertex welding pass won't sort out. The natural question: is there an ordering on the triangles of A and B and the BSP trees of A and B such that the Thibault + Naylor CSG operation produces no t-junctions, or at least the same set of splits? My gut instinct is "no", or at least not without splitting the triangles of B along the planes of B's own BSP tree. Maybe if you kept both A and B as BSP trees and then did the intersection/operation that way, you would get a result that was better. I think you'll need to do a T-junction pass regardless.

The second main thing that got done this week, that actually DID get done, was actually moving the new brush data out of SLED and into the main game engine. Currently it assumes that brushes are contained in a sector (which they are - however, there really is only one sector at this point) - and then each sector contains, cunningly divided into material batches, big chunks of stinking brush geometry. (And brick data, which is what we call prefabricated meshes. And objects. And lights. And particle systems. And portals. And occluders. And Balls!(TM). And...)

I'm still having trouble sorting out the just-in-time editing system, and exactly how that's going to work. I think that it internally maintains a set of compiled output (read: a copy of the world and game universe defined entirely in terms of SLED objects) and then a collection of linking data relating SLED objects to their real world counterparts. Instead of loading a world from compiled data, a 'trick' is played on the game engine: the data it receives is really pseudo-compiled data from SLED.

Also, I'm breaking in a new character modeller. The hope is that I'll have something interesting to show at my various sordid interviews next week. I'm sure that aen, at least, will want to see the engine running if he gets half a chance.

Begin Rant:

I was thinking about what it is that I actually do on a daily basis, and this is what I came up with: as a programmer doing graphics work/game work/whatever work, I tend to think of myself as an algorithmic designer. Day-to-day programming work, say 99.9% of what actually happens doing web development, is uninteresting. It revolves around writing interfaces that make libraries talk to other libraries. You can do this in a nice fashion, and you can make it all pretty and unit tested, but really it's not about creative problem solving beyond thinking in terms of pretty structures.

Most of what I do, on the other hand, involves finding solutions to problems that are a) algorithmic as opposed to implementation-centered, b) hard, c) math-oriented. Most of computer graphics is math; furthermore, a lot of that math is Hard Math. To just get a cube up and running requires linear algebra - a lot of it. Implementing dot product bump mapping is actually an exercise in differential geometry - the idea of a tangent space stems from the work of nineteenth century differential topologists. Spherical Harmonics, the new in-technology, are the solutions in spherical coordinates to a system of partial differential equations. Even something as simple as making a good looking particle system work is a mild form of numerical integration.

So that's why graphics programming is some of the most interesting programming you can do. And also, I think, some of the hardest.
LinkReply

Comments:
[User Picture]From: egometry
2008-03-23 07:20 am (UTC)
You obviously don't understand the lame score.
(Reply) (Thread)
[User Picture]From: mad_and_crazy
2008-03-23 09:17 am (UTC)
I know. Sorry.
(Reply) (Parent) (Thread)
[User Picture]From: nothings
2008-03-23 10:21 pm (UTC)
0.

b-rep = boundary rep = boundary representation = polygonalization, yeah.

1.

The classic t-junc BSP arises as follows:

Suppose you have two split planes; one is the root. Without loss of generality, let's have the first be a split at x=0, and the child (on one side only, let's say the x>0 side) be a split at y=0.

Now, suppose you have some totally unrelated polygon. Perhaps this polygon lives in the plane z=0, and it extends on all sides of the origin.

When you clip that polygon by the BSP tree, what do you get? You get three polygons (one for each leaf). First you split the polygon at x=0. Then you split the right-side (x>0) polygon along y=0.

And now you have a t-junc at the origin, because the split induced at y=0 is only on the right side, so the origin is a vertex of the two right-side polygons, but not of the left-side polygon.

2.

The classic t-junc fixer works as follows: for every edge, see if there are any coincident edges. (You can classify each edge with a vector and a location; if you canonicalize these, then you can just do a fuzzy match for edges. Or you can say that each edge was defined by the intersection of two planes--e.g. the two planes of the two polygons that share it if it was in an original brush, otherwise if it came from clipping, the plane of the polygon and the clipplane--and if you keep around unique identifiers for the clip planes you don't need to fuzzy test.)

Now take the set of all coincident edges along a given line, and insert t-juncs as needed so all the edges are divided properly.

As I said before, for Thief I had a crazy system that as a midpoint of processing just represented the world with the BSP tree (and a state for each leaf), and then generated the final polygons directly from that (essentially by clipping an infinite solid world by the BSP tree), and I made that generate t-junctions as it went (by keeping track of shared edges across the BSP planes), but there were a lot of weird subtle cases and it took way too long to make it work right.

Edited at 2008-03-23 10:23 pm (UTC)
(Reply) (Thread)
[User Picture]From: mad_and_crazy
2008-03-23 10:50 pm (UTC)
Okay - interesting. I was looking for edges that were unmatched in the mesh geometry, and then trying to glue points into place so that that makes sense. That way seems like it might work better.
(Reply) (Parent) (Thread)
[User Picture]From: nothings
2008-03-23 11:00 pm (UTC)
You can certainly use unmatched edges as the starting place for it (as a filter for what to include or not).
(Reply) (Parent) (Thread)
[User Picture]From: aen
2008-03-26 03:46 pm (UTC)
What do you mean by "it's not about creative problem solving beyond thinking in terms of pretty structures"? Are you referring to design?

Architecting the bigger picture is by far the more interesting problem to me. Deep knowledge about all the moving parts and their interactions beyond "It works." is what I crave!
(Reply) (Thread)
[User Picture]From: mad_and_crazy
2008-03-27 09:34 am (UTC)
I think what I'm trying to say is that given the delineation between (A) computer science and (B) software engineering, the stuff that I like to do on a regular basis is in category (A) - the bits where you need to build an algorithm to do something interesting and difficult. This is not to say that there are not many, many places in game development where (B) is really, really important. Clean design and having a really awesome pleasant source tree is a goal to keep in mind overall when you're building a game system, but each piece is a difficult exercise in (A).

Compare the ratio of doing (A) and (B) in writing a game engine to, say, building a website or a spreadsheet. Certainly game engine development is probably also the mathiest area of computer programming that people actually do on a day to day basis - I really worry that there's not enough people in the game biz with math skills. More on THAT later.
(Reply) (Parent) (Thread)