Carmack On Future Graphics Engines

[MikeC]

Reminded me of David Kirk's comments a while back about rendering "smarter polygons."

In a recent statement, id software's John Carmack said that he didn't want more polygons. Instead, he wants "100 passes per polygon." (With each rendering "pass" a computer makes before it displays the graphics, more and more detail can be added.)

Carmack is no longer demanding more polygons, he wants smarter polygons. He wants the ability to bump map -- simulate raised textures on the surface on polygons -- and to add sophisticated lighting effects. By adding more rendering passes, designers will be able to polish their creations on a pixel-by-pixel basis.

http://www.gamespy.com/futureofgaming/engines/

[Tagrineth]

Crikey, 100 passes... WTF would you do with 100 bloody passes? Surely nothing realtime. :|

Carmack's gone bonkers, IMO...

[MikeC]

Crikey, 100 passes... WTF would you do with 100 bloody passes? Surely nothing realtime. :|

Carmack's gone bonkers, IMO...

That's probably a bit extreme with today's technology :)

But Kevin Stephens of Monolith followed up by stating that "10 or 20 passes per polygon will not be uncommon."

[sancheuz]

What is a pass? (in plain english please :lol: )

[MfA]

When he says passes per polygon he doesnt necessarily mean with the same projection I think.

BTW, I would like Doom3 to have a couple more polygons ;)

[fresh]

Crikey, 100 passes... WTF would you do with 100 bloody passes? Surely nothing realtime. :|

Carmack's gone bonkers, IMO...

Sure, everybody said he went bonkers too when he asked for 128 bit frame buffers.

[Ilfirin]

Crikey, 100 passes... WTF would you do with 100 bloody passes? Surely nothing realtime. :|

Carmack's gone bonkers, IMO...

Sure, everybody said he went bonkers too when he asked for 128 bit frame buffers.

Ah.. wha? No one who knew what they were talking about did

[Fuz]

Why not have both?
Carmack says he doesn't want more polygons, but wants more passes per polygon. Imho, you can not make up for a lack of polygons no matter how many special effects you add to a pixel.

Probably explains why Doom III looks so poly deprived. :wink:

[Chalnoth]

I just have to say, the majority of DOOM3's effect on the gamer will be dependent upon motion. That means you should absolutely not judge it until you see it in motion.

That said, yes, we do need higher polycounts, but for what DOOM3's going to be, I definitely think JC made the right decisions. As technology improves, we will have both better polygons and more polygons.

[Brent]

I think the biggest thing about Doom 3 is its lighting and shadow system

From some screenshots people have debated over it looks like the poly count in some situations aren't as high as some would like :p

I dunno, I guess we'll just have to wait to see it in action in person to judge it...

100 passes may sound like a lot now, but so have many other things that are common now compared to a year or two ago...

one thing is for certain, and is the theme of that article, is that we are coming into some very cool 3d times up ahead... things keep getting better and better...

[Johnny Rotten]

I always snicker at those who make comments about Doom3's looking 'low poly'.

It just tells me they havent seen it in motion. :)

[V3]

Polygon also allow you to put more enemies in one room at once. Its not just how model look blocky. Also bigger room to boot.

Before he did the 100 passes or so, I want to see more dynamic environment, not just shadow and light and occasional object, but everything.

100 passes is probably doable if you went with some eDRAM solution.

[DemoCoder]

You don't need 100 passes per surface if you have unlimited texture reads, "effectively" unlimited per-pixel shader lengths, and the ability to render to multiple targets.

On most architectures you could collapse most of these passes using shaders. You only need to resort to multipass for some rare calculations.

[Humus]

I'm not sure about "rare". As long as you need information about the rest of the scene and not only the current texture you'll have to resort to multipass. Shadows is such a case, and I would argue it is or will become a quite common case.

[DemoCoder]

Except for shadows (e.g. stenciled shadow volumes) and some 2d image based effects can you really provide an example of where you need 100 passes?

Most algorithms touch a dataset O(N) - O(N^4) times. Can you point out any algorithms or effects that require O(N^100)? Seems ludicrous. If you're using hacks like stencil for conditionals (no pixel shader predicates) or branching emulation, that's one thing, something which will be alleviated as shaders get more powerful, and we already acknowledged multi-passes for each light, and I'll even acknowledge extra passes for occlusion query, but this is a far cry from 100.

I stand by my point. For any given procedure P, chosen from the list of all possible computable algorithms that are relevant to 3D shading, the proportion that requires explicit multipass is small compared to the proportion that can be encoded strictly in a pixel shader.

[LeStoffer]

In a recent statement, id software's John Carmack said that he didn't want more polygons. Instead, he wants "100 passes per polygon." (With each rendering "pass" a computer makes before it displays the graphics, more and more detail can be added.)

Maybe Gamespy didn't understand the term passes per polygon as we normally do around here (e.g. in DX 9 hardware you only need to send the polygon once to render 16 textures in one pass)?

Anyway on DX 10 Vertex Shaders and Pixel Shaders are set to be integrated/blend much more. This huge futore flexibility really shouldn't point in the direction of having to use 100 passes per polygon to add the detail you need. You will advanced 2. or 3. generation displacement mapping in future VS and very good per-pixel lightning alhgoritms in future PS.

[Dio]

I think that's a touch confused on computational complexity. An O(n^100) algorithm implies that for every increase in the size of the dataset (or some other 'number' on which it is dependent) the time goes up to the 100th power. I.E. that's a totally unimplementable algorithm - if it even took 2 instructions or had 2 items of data the execution time would be longer than the length of the universe, etc.

[arjan de lumens]

Except for shadows (e.g. stenciled shadow volumes) and some 2d image based effects can you really provide an example of where you need 100 passes?

Most algorithms touch a dataset O(N) - O(N^4) times. Can you point out any algorithms or effects that require O(N^100)? Seems ludicrous. If you're using hacks like stencil for conditionals (no pixel shader predicates) or branching emulation, that's one thing, something which will be alleviated as shaders get more powerful, and we already acknowledged multi-passes for each light, and I'll even acknowledge extra passes for occlusion query, but this is a far cry from 100.

I stand by my point. For any given procedure P, chosen from the list of all possible computable algorithms that are relevant to 3D shading, the proportion that requires explicit multipass is small compared to the proportion that can be encoded strictly in a pixel shader.

Just a nit on the O-notation: 100 passes would imply O(100*N) operations, which is still just O(N) with a large hidden constant. O(N^100) is O(N*N*N*N*N* ... 100 times), which is something totally different.

Still curious on what anybody would need 100 passes for ... doing stencil shadows using an extended light source emulated as 100 point light sources, perhaps?

[DemoCoder]

Err, your right, my bad. Need more sleep.

Let me rephase the statement by making another analogy (this time hopefully correct)

In the theory of computation, we have this notion of computability on a given class of abstract machine. e.g. regular expressions /DFA, context free grammars/PDFA, and of course, turing machines and mostly everything else.

I would assert that in 3D shading, there is a similar notion of computability classes with respect to abstract shader languages/machine models. Note, I am not talking about whether such an algorithm would run on machine M efficiently, but whether it can run at all within the machine (without unbounded augmentation by the CPU).

For the DX9 streaming processor + VS2.0/PS2.0, there would exist a class of algorithms that can be implemented on this model in a single pass (ignoring # regs and max program length, I'm talking about an algorithm that fundamentally needs 2 passes because of the way of evaluates the scene). Call this PS2.0 Class 1. Then there would exist a class of algorithms which run on PS2.0 in minimum 2 passes, call this a class 2 shader. And so on....

However, sooner or later you would encounter an algorithm in which the number of passes required on PS2.0 could not be bounded by looking at the algorithm alone, but would be data dependent. Call these Class Null. I would say that Class Null shaders are effectively not computable on M (PS2.0) and require outside help (CPU). The fact that you can translate Class Null into having the CPU push hundreds of passes aimed at emulating a general purpose processor IMHO does not machine that Class Null "runs" on machine M, since you have augmented M with an external CPU.


Similarly, you can design computability equivalence classes for PS3.0, architectures with a per-primitive processor, 3DLabs P10, etc.


Now comes my final unproven conjecture:

The Cardinality of Class Null is less then Epsilon * the Cardinality of Class 1 Union Class 2 Union .....

That is, Class Null algorithms are "rare" compared to all other classes on PS2.0/PS3.0


An example of how to build Class N algorithms (an algorithm that *requires* N passes) is to design a recursive function F(a,b,c,d) where a,b,c,d are pixels and F is not analytic. To compute F(a_n, b_n, c_n, d_n) you need to compute F(a_n-1, b_n-1, c_n-1, d_n-1) and so on. Since F is not analytic, you really can't "unroll" the recursion into a linear pixel shader.

I don't really know of there are any "useful" Class N (where N > some large integer) 3D shading algorithms.

I suspect you will find that there are oodles and oodles of useful Class 2, 3, and 4 algorithms, but after a certain constant, you will find nothing really useful until you hit Class Null. Call it a hunch.

[PC-Engine]

Would photon mapping require 100 or more passes? :-?

[arjan de lumens]

Class1 is a finite class, since a PS2.0 program has a fixed maximum length, and thus can be represented by a fixed number of bits, say N. Then Class1 has at most 2^N members, Class2 has 2^(2N) members, Class3 has 2^(3N) members etc.

Let's call the union of Class1, Class2, Class3 and so on ClassX. Obviously, since it is a union of infinitely many non-empty classes, the cardinality of ClassX is an infinity. The set of all programs has size aleph0, so ClassX has cardinality aleph0.

As far as I can see, any program containing data-dependent loops or recursive function calls cannot be shoehorned into ClassX, and thus ends up in ClassNull. Since you can easily produce a ClassNull program by adding a recursive function to a program that is otherwise ClassX, the cardinality of ClassNull is no less than that of ClassX: both are aleph0.

What your conjecture is saying is that the set of programs with data-dependent loops and recursive functions is somehow smaller that the set of programs without, which doesn't make very much sense to me.

[Humus]

If we skip the theory for a while and think about it in pratice. While multipass isn't going to be rare it's not going into the levels of hundreds either, as DemoCoder pointed out. However, it may go to the level of tens. Say if I need to do shadows and some reflections and refractions on a water surface for instance. If I use a cubemap for the shadows like in my "Shadows that don't suck" demo, that's 6 passes. For the reflection and refractions it's another 6 passes. Then a final pass combining them, which sums it up to 13 passes. I suppose you could add a few more effects to get more passes, but then with the possibility to output to several render targets you will probably be able to pack some of them in the same pass too.

[DemoCoder]

Arjan,
You are reading too formally. Your math reasoning is excellent, but I didn't meant for it to be treated as a provable theorem (especially in terms of Cantor-style reasoning about sets) more as an analogy for reasoning. I stated several times that the criteria is "programs useful to 3D shading". Given an N-bit long shader, the vast majority of the "shaders" possible are junk or "uninteresting". That's why I mentioned that I didn't know of too many "ClassNull" algorithms.

By straight construction, you can invent one (as I showed), by how many are relevant? This is sort of like asking about the halting probability of a random program, except the criteria is even more complex :)

[arjan de lumens]

OK .. point taken that the vast majority of possible programs, ClassNull or not, are garbage - but couldn't it be that the reason that we don't see many per-pixel ClassNull algorithms is just that there is no hardware acceleration present for them - a chicken & egg problem? I would expect a recursive pixel shader to be capable of accelerating e.g. ray-tracing, anything fractal-related, probably a lot of other stuff as well.

[DemoCoder]

Arjan,
You're probably right. Part of my motivation for introducing the concept of ClassNull is to ask "Is algorithm X in ClassNull?" where X is PhotoMapping, MonteCarlo methods, Radiosity, etc

Then the next logical question is, how can we extend the machine so that X is not longer ClassNull on Machine M. :)

[OpenGL guy]

Class1 is a finite class, since a PS2.0 program has a fixed maximum length, and thus can be represented by a fixed number of bits, say N. Then Class1 has at most 2^N members, Class2 has 2^(2N) members, Class3 has 2^(3N) members etc.

Let's call the union of Class1, Class2, Class3 and so on ClassX. Obviously, since it is a union of infinitely many non-empty classes, the cardinality of ClassX is an infinity. The set of all programs has size aleph0, so ClassX has cardinality aleph0.
Sorry, I have to jump in here :)

Cardinality of Integers = aleph0. Cardinality of real numbers = 2^(aleph0) = lim (n -> infinity) 2^n. Thus, your ClassX has an uncountable number of elements.

The continuum hypothesis is that 2^(aleph0) = aleph1, i.e. 2^aleph0 is the next larger order of infinity above aleph0.

[DemoCoder]

Good catch, ClassX is a powerset.

[arjan de lumens]

Sorry, I have to jump in here :)

Cardinality of Integers = aleph0. Cardinality of real numbers = 2^(aleph0) = lim (n -> infinity) 2^n. Thus, your ClassX has an uncountable number of elements.

Somehow, I don't think you are allowed to pull infinities other than aleph0 out of limits that way. The problem is that you are adding in Class(aleph0) - which contains all aleph0-length "programs" - into your calculation where no such class appeared in the original union ClassX.

Otherwise, consider this: the set of all programs has cardinality aleph0 (which can be proven easily: every possible program is uniquely represented by a finite-length sequence of bytes, and every finite-length sequence of bytes can easily be mapped to a unique, finite integer, so we get the set of all programs mapped to a subset of the integers) and ClassX is a proper subset of the set of all programs, so there is no way ClassX can have a greater cardinality than aleph0.

[OpenGL guy]

Somehow, I don't think you are allowed to pull infinities other than aleph0 out of limits that way. The problem is that you are adding in Class(aleph0) - which contains all aleph0-length "programs" - into your calculation where no such class appeared in the original union ClassX.
That's the beauty of infinities: The results can be surprising.

Let me give another example. Take the "function" F(x) = f1(x) union f2(x), where f1(x) = 1/3 x and f2(x) = 1/3 x + 2/3. Start with the set X = {0}. F(X) = {0, 2/3}, F(F(X)) = {0, 2/9, 2/3, 8/9}, etc. lim (n -> infinity) F^n (X) = Cantor set, which has an uncountable number of elements.

Otherwise, consider this: the set of all programs has cardinality aleph0 (which can be proven easily: every possible program is uniquely represented by a finite-length sequence of bytes, and every finite-length sequence of bytes can easily be mapped to a unique, finite integer, so we get the set of all programs mapped to a subset of the integers) and ClassX is a proper subset of the set of all programs, so there is no way ClassX can have a greater cardinality than aleph0.
Bad argument: The set of subsets of the integers is uncountable.

Edit: To put this another way. Consider a set with n elements. The number of subsets of this set is 2^n. Lim (n -> infinity) 2^n = cardinality of the real numbers.

[arjan de lumens]

Otherwise, consider this: the set of all programs has cardinality aleph0 (which can be proven easily: every possible program is uniquely represented by a finite-length sequence of bytes, and every finite-length sequence of bytes can easily be mapped to a unique, finite integer, so we get the set of all programs mapped to a subset of the integers) and ClassX is a proper subset of the set of all programs, so there is no way ClassX can have a greater cardinality than aleph0.
Bad argument: The set of subsets of the integers is uncountable.

Reread what I wrote. I was *not* mapping each program to a set of integers - I was mapping each program, as a whole, to a SINGLE integer (for a 1 Kbyte program, that would typically be a ~2400-digit integer, under the scheme I suggested)

[Nagorak]

Reminded me of David Kirk's comments a while back about rendering "smarter polygons."

In a recent statement, id software's John Carmack said that he didn't want more polygons. Instead, he wants "100 passes per polygon." (With each rendering "pass" a computer makes before it displays the graphics, more and more detail can be added.)

Carmack is no longer demanding more polygons, he wants smarter polygons. He wants the ability to bump map -- simulate raised textures on the surface on polygons -- and to add sophisticated lighting effects. By adding more rendering passes, designers will be able to polish their creations on a pixel-by-pixel basis.

http://www.gamespy.com/futureofgaming/engines/

Considering how bad the Doom3 alpha demo looks, maybe we should stop listening to what Carmack has to say about graphics. I'm really starting to question whether he actually understands what 3D graphics needs. He makes pretty good engines, but his team is artistically deficient. It'd be nice if in one game they actually used colors other than olive green, brown and burgundy. It gets old... And if they don't know how to make a pretty picture, then who says Carmack knows how to make an engine that's good for people who do?

Granted I haven't seen the lighting effects in motion, but who cares? If all the light is shining on is a bunch of olive green crap, then I'd rather I was just left in the dark (pun intended).

id really should have called themselves ego (psychological sense, not that they have big heads ;) ) because none of their games display any creativity at all. It's all just logic and done well, but that certainly doesn't fir their name.

[OpenGL guy]

Reread what I wrote. I was *not* mapping each program to a set of integers - I was mapping each program, as a whole, to a SINGLE integer (for a 1 Kbyte program, that would typically be a ~2400-digit integer, under the scheme I suggested)
Let me try a different way. Let Xn = set of all programs of length n. The number of such programs is b^n where b is the number of opcodes available. Lim (n -> infinity) b^n = lim (n -> infinity) 2^n = cardinality of the real numbers.

I'm not a set theorist, so I can't explain this in better terms. But, I am an analyst and have dealth many times with these sorts of limits when talking about the attractor in contraction mappings (like my "function" F, in a previous post).

As I stated earlier, it makes no difference that each program is of finite length: The limit of the set is still uncountable.

Edit: Fixed quoting problem.

[psurge]

every possible program is uniquely represented by a finite-length sequence of bytes


This statement is untrue: you appear to define
ClassX as

lim(N->infinity) { Class1 U Class2 U ... ClassN }

In the limit you have programs with infinite lengths, i.e. there is a 1 to 1 mapping from elements of ClassX to the set of all possible sequences of a countably infinite number of bits (i.e. real numbers, R).

Unless a 1 to 1 mapping from R to ClassX does not exist, card(ClassX) = card(R), by the Cantor-Bernstein theorem.

Serge

[arjan de lumens]

Let me try a different way. Let Xn = set of all programs of length n. The number of such programs is b^n where b is the number of opcodes available. Lim (n -> infinity) b^n = lim (n -> infinity) 2^n = cardinality of the real numbers.

OK, let's try that different way: Let Xn = set of all INTEGERS of length n (digits). The number of such programs is b^n where b is the number of different digits (0,1,2,3,...,9) available. Lim (n -> infinity) b^n = lim (n -> infinity) 2^n = cardinality of the real numbers = the cardinality of the integers. See the problem with your argument now?

My point is that any program can be represented as a string of 8-bit bytes and can thus be seen as an integer stored in base-256 format, and that therefore there is a 1:1 mapping between all valid programs and a subset of the integers.

[arjan de lumens]

every possible program is uniquely represented by a finite-length sequence of bytes


This statement is untrue: you appear to define
ClassX as

lim(N->infinity) { Class1 U Class2 U ... ClassN }

In the limit you have programs with infinite lengths, i.e. there is a 1 to 1 mapping from elements of ClassX to the set of all possible sequences of a countably infinite number of bits (i.e. real numbers, R).

Unless a 1 to 1 mapping from R to ClassX does not exist, card(ClassX) = card(R), by the Cantor-Bernstein theorem.

Serge

Time to use the integer argument here too: If Class1 was every 1-digit number (base 10), Class2 was every 2-digit number, Class3 was every 3-digit number, then the number of integers in each class would easily be seen to be about ~10^N. This would imply that the size of their union would be lim(N->infinity) 10^N = 10^aleph0 = 2^aleph0. This despite that their union is simply the set of all integers .... :-?

[psurge]

arjan:
their union is not the set of all integers. In the limit N->infinity, ClassN contains programs P of infinite length. These are not representible as integers.

your claim: there is a one to one mapping from the set of all programs to the set of integers.

you then define a set (using a limit) which contradicts your claim.

do you see what I'm saying?

[OpenGL guy]

Time to use the integer argument here too: If Class1 was every 1-digit number (base 10), Class2 was every 2-digit number, Class3 was every 3-digit number, then the number of integers in each class would easily be seen to be about ~10^N. This would imply that the size of their union would be lim(N->infinity) 10^N = 10^aleph0 = 2^aleph0. This despite that their union is simply the set of all integers .... :-?
The problem is that 111111111111111... is in your set and that your union is not the set of all integers. The set you are defining is equivalent to the real numbers.

[psurge]

To clarify a little further, an example :

For any real number r, you can construct a rational number arbitrarily close to it:

i.e. assume the number r is in [0,1].
define f as
f(N) = 1/2 + s(0)/4 + s(1)/8 ...... +s(N - 1)/2^N

where
s(N - 1) = +1 if ( f(N-1) < r )
s(N - 1) = -1 if ( f(N-1) > r )

now f(N) for any N in the positive integers is clearly a rational number.
--

Now the process for computing f(N) is a member of Class(N) (without loss of generality let the computation of s(N-1) take all the program storage allotted to a single pass)

For any finite N, the program for f(N) will have finite length, and output a rational number (representible as a finite number of bits).

*But*, when you take the limit, things change :
lim N->infinity f(N) = r

- r is not a rational number, but a real number: it is not representible in a finite number of bits.

- furthermore, the program for lim N->infinity f(N) is not representible in a finite number of bits, but is clearly a member of lim N->infinity Class(N),
hence also a member of ClassX.

--

[arjan de lumens]

Time to use the integer argument here too: If Class1 was every 1-digit number (base 10), Class2 was every 2-digit number, Class3 was every 3-digit number, then the number of integers in each class would easily be seen to be about ~10^N. This would imply that the size of their union would be lim(N->infinity) 10^N = 10^aleph0 = 2^aleph0. This despite that their union is simply the set of all integers .... :-?
The problem is that 111111111111111... is in your set and that your union is not the set of all integers. The set you are defining is equivalent to the real numbers.
So it appears that I have managed to subdivide the set of integers into an infinite number of classes whose union has a greater cardinality than the set of integers itself ...? :o

I need to think through that one for a while .... infinities are even weirder that I used to think ....

[Tagrineth]

Considering how bad the Doom3 alpha demo looks, maybe we should stop listening to what Carmack has to say about graphics. I'm really starting to question whether he actually understands what 3D graphics needs. He makes pretty good engines, but his team is artistically deficient. It'd be nice if in one game they actually used colors other than olive green, brown and burgundy. It gets old... And if they don't know how to make a pretty picture, then who says Carmack knows how to make an engine that's good for people who do?

Granted I haven't seen the lighting effects in motion, but who cares? If all the light is shining on is a bunch of olive green crap, then I'd rather I was just left in the dark (pun intended).

id really should have called themselves ego (psychological sense, not that they have big heads ;) ) because none of their games display any creativity at all. It's all just logic and done well, but that certainly doesn't fir their name.

Carmack knows graphics from the programmer's perspective...

And the Quake3 Engine spawned some pretty darn good-looking games (Alice).

But it seems that the Quake VS Unreal issue is based mostly around 'brute force - high performance with lots of "stuff"' (Quake) VS. 'not a whole lot, but great texturing abilities for artists' (Unreal).

[OpenGL guy]

So it appears that I have managed to subdivide the set of integers into an infinite number of classes whose union has a greater cardinality than the set of integers itself ...? :o
But this is always the case though. As I mentioned above, if you take a set with n elements, the number of subsets is 2^n, which is a whole lot larger than n.

The trick with inifinities is that you can get limit points. Take this example: Xn = { 2^-i | i = 0, ..., n}. Each Xn consists solely of powers of 2, however lim (n -> infinity) Xn contains 0.

[DemoCoder]

The integers are countable. The sets {1}, {2}, ..., {inf} (set containing 1 element, the ith integer) is countable and directly mappable to the integers.

But the "set of all subsets" includes things like {}, {{}, {}}, {1, {1}}, {1, { {1}, {} } } etc. Unioning together all possible subsets of the integers produces a set which is not countable and is easily proven by diagonalization.


However, with regards to programs of length N, you do not end up with a powerset.

For example, it might be the case that Class 1 Union Class 2 = Class 2.

That is, for all N, Class N is a proper subset of Class N+1. Therefore, unioning together all the Classes 1 ... N merely produces set N+1, therefore the Union of countably many sets produces a countable set.

I take back what I said earlier. The union of all the Classes is not neccessarily a powerset.

[OpenGL guy]

The integers are countable. The sets {1}, {2}, ..., {inf} (set containing 1 element, the ith integer) is countable and directly mappable to the integers.

But the "set of all subsets" includes things like {}, {{}, {}}, {1, {1}}, {1, { {1}, {} } } etc. Unioning together all possible subsets of the integers produces a set which is not countable and is easily proven by diagonalization.
Your example is slightly flawed. A subset is a set whose elements are in the original set. Thus, {1} is a subset of the integers, but {1, {1} } is not because {1} is not an element of the integers. Also, you wouldn't count {1,1} as a subset of the integers because you normally talk about distinct elements. Thus, the set {1, 2, ..., n} has 2^n subsets.


However, with regards to programs of length N, you do not end up with a powerset.

For example, it might be the case that Class 1 Union Class 2 = Class 2.
Irrelevant. Take the sets {0}, {0, +/- 1}, {0, +/- 1, +/- 2}, etc., each of the smaller sets is contained in the larger, yet the limit of these sets is still the integers.

Now look at my previous example regarding the Cantor set. Each of the F^n(X)'s is finite! Yet, the limit is uncountable.

Edit: Also note that F^n(X) is a subset of F^(n+1)(X).

[Riptides]

Why am i suddenly struck with the image from Deliverence, the one scene with the dualing banjo's at this point :) :lol:

[Chalnoth]

I don't really know of there are any "useful" Class N (where N > some large integer) 3D shading algorithms.

I suspect you will find that there are oodles and oodles of useful Class 2, 3, and 4 algorithms, but after a certain constant, you will find nothing really useful until you hit Class Null. Call it a hunch.

Sounds reasonable...the only thing is, if you're attempting to describe a data-dependent program length, you're also describing what is effectively an N^m algorithm (m > 1). That is, the accuracy of the final output doesn't depend linearly on the computational power used, but by some other power. Such algorithms are essentially useless for realtime 3D graphics, and must be brought down to an N^1 algorithm before being useful.

An example of an N^m algorithm would be a transparent 3D texture, like fog. If you really want to render this in all its detail, you would need to render in all three dimensions, N^3 times. Since the screen is 2D, you have N^2 pixels. That makes for an N^2 algorithm, which is totally unfeasible for realtime 3D graphics. That is, you'll either end up with fog that runs far too slowly, or you'll end up with fog that looks terrible.

So, of course, the solution is to bring it down to an N^1 algorithm by simply using a constant number of depth slices.

Not all algorithms will have similarly-easy simplifications.

Regardless, back on topic, the most obvious use for 100 passes (assuming 100 passes = 100 total inputs...generally textures) would be for a very complex 3D scene with lots of lights, shadows, bump maps, and transparent 3D textures. Hopefully what we're talking about here is an algorithm that would take 100 passes/texture reads on, say, NV1x hardware, but far, far fewer on an R300 or NV30.

[Chalnoth]

Your example is slightly flawed. A subset is a set whose elements are in the original set. Thus, {1} is a subset of the integers, but {1, {1} } is not because {1} is not an element of the integers. Also, you wouldn't count {1,1} as a subset of the integers because you normally talk about distinct elements. Thus, the set {1, 2, ..., n} has 2^n subsets.

Well, if you're talking about nonrepeating sets, then yours is a bit flawed, because there's no requirement on having just two in the subset. And even then, it's off. The correct calculation would include the following form:

aCb = a!/(b!(a - b)!)

Where the final result would be:

nCn + nC(n-1) + nC(n-2) + ... + nC1

Here's a few terms in this series:

n : s(n)
1 : 1
2 : 3
3 : 7
4 : 15
5 : 31
100 : 1.267 * 10^30 (Yes, I used my trusty ol' TI-85 for this one)

Another quick update:
This is assuming that this subset is a set of one or more integers contained within the chosen set of n integers, where there are no two repeating integers in the subset, and {2,1} is the same as {1,2}. If the subset is defined as order-dependent, the calculation is similar.

[Fred]

Eep, you guys are wading on very tenous grounds here.

Definition: a Perfect set E

This set is closed, and every point of E is a limit point of E.

Theorem: Let P be a nonempty perfect set in R^n. P is then uncountable.

The Cantor set is a perfect (and compact) set in R^1 which contains no segments, is lebesque measure zero and is uncountable.

The set of all subsets of a nonfinite set is undetermined. You need further axioms in set theory to do anything with it.

[OpenGL guy]

The set of all subsets of a nonfinite set is undetermined. You need further axioms in set theory to do anything with it.
As I said, I'm an analyst: I take the axiom of choice as a given :)

Edit: Here's some info on the Axiom of Choice from http://www.math.vanderbilt.edu/~schectex/ccc/choice.html:
Axiom of Choice. Let C be a collection of nonempty sets. Then we can choose a member from each set in that collection. In other words, there exists a function f defined on C with the property that, for each set S in the collection, f(S) is a member of S.

The best part of the axiom of choice: Take a sphere of volume X. You can divide it into a finite number of parts, rearrange them and get a sphere of volume 2X. (Banach-Tarski Paradox.) Now if only that worked with gold! ;) (Obviously, some of the pieces you divide the sphere into are not measurable... one of the things I didn't like about analysis. But, analysis without Choice is even more strange.)

[OpenGL guy]

Edit: Also note that F^n(X) is a subset of F^(n+1)(X).

If you're talking only about n = integer >= 0, or integer >= 1, then isn't it the other way around?
No. As I said:

Take the "function" F(x) = f1(x) union f2(x), where f1(x) = 1/3 x and f2(x) = 1/3 x + 2/3. Start with the set X = {0}. F(X) = {0, 2/3}, F(F(X)) = {0, 2/9, 2/3, 8/9}, etc. lim (n -> infinity) F^n (X) = Cantor set, which has an uncountable number of elements.
Once a number is in F^n, it will be in all F^m where m > n.

Your example is slightly flawed. A subset is a set whose elements are in the original set. Thus, {1} is a subset of the integers, but {1, {1} } is not because {1} is not an element of the integers. Also, you wouldn't count {1,1} as a subset of the integers because you normally talk about distinct elements. Thus, the set {1, 2, ..., n} has 2^n subsets.

Well, if you're talking about nonrepeating sets, then yours is a bit flawed, because there's no requirement on having just two in the subset. And even then, it's off.
Who ever said anything about limiting subsets to 2 elements? I was simply giving examples.
The correct calculation would include the following form:

aCb = a!/(b!(a - b)!)

Where the final result would be:

nCn + nC(n-1) + nC(n-2) + ... + nC1

Here's a few terms in this series:

n : s(n)
1 : 1
2 : 3
3 : 7
4 : 15
5 : 31
100 : 1.267 * 10^30 (Yes, I used my trusty ol' TI-85 for this one)
Sorry, this is totally wrong.
Take X = {}.
Subsets of X: {} = 1
Take X = {1}.
Subsets of X: {} and {1} = 2
Take X = {1, 2}.
Subsets of X: {}, {1}, {2} and {1,2} = 4.

I leave the proof that for X={1, 2, ... , n} the number of subsets of X = 2^n to the reader. Hint: Try induction.

Edit: Sorry, didn't mean to sound so harsh. Your calculation is only off-by-one (I guess you didn't count the empty subset). Anyway, my calculation is much, much easier :)

[OpenGL guy]

The Cantor set is a perfect (and compact) set in R^1 which contains no segments, is lebesque measure zero and is uncountable.
Other fun facts about the Cantor set:
Hausdorff dimension = log 2 / log 3 = box counting dimension
Hausdorff measure for dimension log 2 / log 3 = 1

Lebesgue measure is too coarse to measure a set like the Cantor set :)

Cantor set can be easily mapped to the interval [0, 1]. Let C = Cantor Set. Then C is the set of all values of the form 0.XXXXXXXXXXXX... in base 3 where X is either 0 or 2. To map C to [0,1], simply replace all 2's with 1's.

Another interesting fractal: Sierpinski triangle. It's constructed of a contraction mapping F(x,y) = f1(x,y) union f2(x,y) union f3(x,y) where f1(x,y) = (1/2 x, 1/2 y), f2(x,y) = (1/2 x, 1/2 y) + (1/2, 0) and f3(x,y) = (1/2 x, 1/2 y) + (0, 1/2). It's box counting dimension = log 3 / log 2 = Hausdorff dimension. Hausdorff measure of this set at dimension log 3 / log 2 is 1, if I remember correctly.

[Natoma]

I suppose there's no way to translate all of this graphics-equations-masturbation into english is there? Mebbe I should just stick with C-based languages.. hehe.

[OpenGL guy]

I suppose there's no way to translate all of this graphics-equations-masturbation into english is there? Mebbe I should just stick with C-based languages.. hehe.
You think this is bad? You should've seen my dissertation! :D I had to type the whole thing in LaTeX... I could hardly read the thing until I converted it to Postscript (not that I can read Postscript, but at least you can print it or use Ghostview ;) ).

[stevem]

I would've gone apoplectic without Scientific Workplace...

[DemoCoder]

Irrelevant. Take the sets {0}, {0, +/- 1}, {0, +/- 1, +/- 2}, etc., each of the smaller sets is contained in the larger, yet the limit of these sets is still the integers.


And the union of those sets is countable (and the number of those sets is countable as well). Which was my point. I can map, one to one, an element in each of those sets to the integers.

Arjan's original point holds. The union of all possible programs out of a set of programs of length N is countable as N approaches infinity. This is actually proven early on in most theory of computation classes (that the number of possible programs is countable)

You can prove Arjan's assertion very simply. If a program P_n of length N is in Set N, it is also in sets N+1, N+2, .... by virtue of the fact that a program of length N can be represented as a program of length N+1 by padding.

Therefore, you only need to consider Set N as N approaches infinity and the Union operation is irrelevant. Set N is the set of all possible computer programs, 1,2,3..., numbered by the integers. Since they are numbered by the integers, they are countable.


The same thing goes for the Union of all possible "multipass" rendering algorithm Classes. Any Class N can be represented as Class N+1 by simply padding out a separate "NOP" pass. Same argument applies.

[OpenGL guy]

Irrelevant. Take the sets {0}, {0, +/- 1}, {0, +/- 1, +/- 2}, etc., each of the smaller sets is contained in the larger, yet the limit of these sets is still the integers.


And the union of those sets is countable (and the number of those sets is countable as well). Which was my point. I can map, one to one, an element in each of those sets to the integers.
You ignored my second example.
X0 = {0}
X1 = {0, 2/3}
X2 = {0, 2/9, 2/3, 8/9}
X3 = {0, 2/27, 2/9, 8/27, 2/3, 20/27, 8/9, 26/27}
etc.

Each of these sets is finite. Xn is a subset of Xm for all m > n, yet the limit of the Xn's is the Cantor set: An uncountable set. Here, lim (n -> infinity) Xn = Union of Xn as n tends to infinity.

[DemoCoder]

I'm not disagreeing with you OGL guy. I have a math degree and all this stuff rings a bell, but I was specifically talking about the case where you are subsetting the integers and the union operation merges sets.

If we're talking a powerset, it's different because the the subsets do not merge.

E.g. S = {A,B,C}, powerset = { {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}} (corresponding to every 3-bit bitstring)

Here, the "elements" of the powerset are sets themselves and {A} union {A,B} = { {A}, {A,B} } not {A,B}. But in the case of computer programs we were talking about earlier, all programs of length 1 unioned with all programs are length 2 is the same set as all programs of length 2 since in computer languages, we can represent a program of length 1 as a program of length 2 padded out with the "terminal symbol"

Thus, the number of possible computer programs is countably infinite, no matter how you slice and dice the set and union the results. Now in the world of real numbers, we have a separate case.

[OpenGL guy]

I'm not disagreeing with you OGL guy. I have a math degree and all this stuff rings a bell, but I was specifically talking about the case where you are subsetting the integers and the union operation merges sets.

If we're talking a powerset, it's different because the the subsets do not merge.

E.g. S = {A,B,C}, powerset = { {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}} (corresponding to every 3-bit bitstring)

Here, the "elements" of the powerset are sets themselves and {A} union {A,B} = { {A}, {A,B} } not {A,B}. But in the case of computer programs we were talking about earlier, all programs of length 1 unioned with all programs are length 2 is the same set as all programs of length 2 since in computer languages, we can represent a program of length 1 as a program of length 2 padded out with the "terminal symbol"

Thus, the number of possible computer programs is countably infinite, no matter how you slice and dice the set and union the results. Now in the world of real numbers, we have a separate case.
No no, it's my fault. The whole time I was reading the union I was thinking limit... Anyway, it's good to sweep the dust off the gears every now and then otherwise you forget everything you knew :)

Edit: Here's what I should have thought of from the start:
http://www.shu.edu/projects/reals/infinity/proofs/combctbl.html

[noko]

Isn't Carmack basically describing a ray tracing algorithm where the VPU could accuratly calculate lighting calculations up to 100 times off of each polygon? Really sounds like a new approach, where the VPU can do ray tracing in real time.

[alexsok]

Isn't Carmack basically describing a ray tracing algorithm where the VPU could accuratly calculate lighting calculations up to 100 times off of each polygon? Really sounds like a new approach, where the VPU can do ray tracing in real time.

Nope, Carmack is a firm believer that real time raytracing is not needed.

Here is his rather large comment about this whole issue:

Now there's two directions to go about this. There's companies that have made ray-tracing acceleration chips, that do ray-tracing in a fairly conventional way, where it's object/ray intersections. There's some benefit there... it's going to be a little bit of a hard sell. It might show up in some specialized markets. That type of thing might happen when ray-tracers are getting their asses kicked so thoroughly by rasterizers using real-time hardware that that type of hardware may wind up getting some small market there... but I don't see it really as effective enough for the real-time gaming market. You've still got all of the scene data management issues.

What I do think is still a potential interesting thing is, and this is something I've thought... there can be some opportunity to maybe make a go at, is ray-tracing into voxels basically, where you make an obtuse, surface-skin voxelization of the world. That's something that's so ideally suited for hardware rasterization on there... it's one of those things where it's tantalizingly close to the type of thing that I tend to do, to like... try and write a hardware rasterizer for voxel tracing. I'm surprised there hasn't been a university project or something like that, because that's something which could be done really, really fast and would give you effectively unlimited geometric detail. There's a bunch of trade-offs there in how you wind up exactly getting some of the specular effects that you're used to getting, where you're not sure about surface geometry, but there's interesting potential directions for a lot of the bi-directional ... [*obscured*] ... at a voxel level.

[SA]

Ray tracing is primarily useful for specular and refractive touchups IMO.

Transformed geometry is much more efficient for first hit computation and first order diffuse and specular reflection. Soft shadows with area lights approximated by stocastic multiple sources are handled much more efficiently using antialiased shadow maps than with distributed ray tracing. The situations that transformed geometry can handle cover the vast majority of real world scenes with essentially the same amount of realism as ray tracing.

That said, a hardware ray tracer will be very useful for touching up those parts of a scene where refraction and specular reflection require it and the sooner such a capability is available the better.

[SA]

It seems you can never have too much triangle rate, fill rate, memory bandwidth, or rendering efficiency. The more you have of any of the above, the less developers are restrained and the more realistic the graphics.
Different developers take different approaches placing different emphasis on some aspects of the pipeline over others at any given time. However, all aspects of the pipeline have a long way to go before real-time Hollywood quality CGI graphics is a reality.

[noko]

Voxel tracing?? LOL, can anyone explain? What he said there backs up the other comment on reducing polycount but higher quality pixels or something to that effect.

[psurge]

OpenGL Guy, DemoCoder,

I would agree so long as the set of all programs only contains programs of finite length. AFAICS however, as defined ClassX contains programs of infinite length, and hence is not countable.

Serge

[WaltC]

Considering how bad the Doom3 alpha demo looks, maybe we should stop listening to what Carmack has to say about graphics. I'm really starting to question whether he actually understands what 3D graphics needs. He makes pretty good engines, but his team is artistically deficient. It'd be nice if in one game they actually used colors other than olive green, brown and burgundy. It gets old... And if they don't know how to make a pretty picture, then who says Carmack knows how to make an engine that's good for people who do?

Granted I haven't seen the lighting effects in motion, but who cares? If all the light is shining on is a bunch of olive green crap, then I'd rather I was just left in the dark (pun intended).

id really should have called themselves ego (psychological sense, not that they have big heads ;) ) because none of their games display any creativity at all. It's all just logic and done well, but that certainly doesn't fir their name.

This is actually a pretty valid point. There've been many comments Carmack has made over the years which decry his own personal lack of artistic ability and creativity. Many of the effects he's "wanted to see" in the past were easily obtainable with existing hardware using existing tools *if* you knew how to manipulate the hardware and the tools to get the results you were after. What Carmack seems to want is 3D hardware that works in a manner that mimics Carmack's programming approaches. Hence his "100 passes" remarks--ie, there are ways to get the same effects he's thinking about with present hardware if you are a skilled artist and you know how to use your tools. Carmack doesn't know how to use the artistic tools so he's asking for their function to be duplicated in hardware because *to his way of thinking* this is the only way to achieve the effects he imagines he'd like to see.

I'm not sure if Carmack fully understands what he's asking for when he asks for it, frankly. He's attempting to bridge the stilted, precise world of the programmer with the intuitive, artistic role of the artist, it seems to me. And as such he's actually getting a few things confused in the process, and simply doesn't realize that most of the effects he imagines are already possible given sufficient artistic talent and competency with a decent set of tools (it's amazing what you can do with tools--often go far beyond anything the programmers making the tools ever imagined was possible with them.)

From a hardware standpoint I think multiple parallel vertex and pixel shading is hugely important, and I also think adding FP precision to the color pipeline of up to 128-bits of color--specifically to increase the dynamic range (the number of shades of a particular color) of each color--will be the "breakthrough" in upcoming 3D games we've all been looking for. But this won't happen until the tool sets and the artists involved internalize the new freedoms this hardware brings and begin to utilize them. Unfortunately, because of that ever-present demon of backwards compatability, it probably won't be any time soon that we see 3D games which *require* > 32-bits of color accuracy (which is a shame, frankly.)
But when we do start seeing such games--ho, boy, watch out....;)

The odd thing here is that Carmack doesn't seem to understand the degree to which his company is making Doom III to be backwards-compatible with 32-bit and < 3D hardware presently on the market. Take away those limitations and I think Carmack would be astounded at what present artists could do with hardware like the R300 (and supposedly nv30 when it ships.) Amazed, actually.

Backwards compatability, more than any other bugaboo, is what's been holding back the graphical state of 3D game graphics more than any other factor, IMO. As big a fan of 3dfx as I was when the company was shipping products, I am nonetheless amazed to read on the infrogames forums the number of people who are complaining that UT2K3 "won't work right" with their V5 or even V3 3D accelerators. What's even more amazing than that, however, is the contortions Epic seems to be undergoing in trying to make their base code "more compatible" with the V5/V3. Personally, I think that's a mistake. But it's that kind of thinking, which for some reason seems very elusive to some 3D game programmers, that really holds back the state of 3D game graphics--which aren't doing a fraction of what they could do under the GF4/Radeon8500, let alone products like the exceptional R300.

If Doom III seems somewhat unimpressive to some it's certainly not because of the limits of present top-of-the-line 3D hardware, even though such hardware is not capable of 100 passes, etc. It's because the goals that are being handed to ID's artists are backwards-compatible goals, and thus in a real sense a straight-jacket the artists are given to work in. Carmack, maybe, tends to forget that at times. He seems to me to often blur distinctions between what his company is presently shipping with what *he'd like to see them ship* at some indefinable future date.

It would be nice, for instance, to hear Carmack say, "We aren't shipping Doom III in 64-bit color because at the time we ship it there will only be a couple of 3D accelerators on the market it could run on, and we don't want to limit our buying audience to that subset of the whole. Therefore our software will be constrained to limits far below the maximum achievable in some current 3D hardware. Also, we ourselves need to move beyond 24-bit +8 graphical tools into a class of 64-bit color tools and the like, and that's taking some time as well." I mean, I think that would be far more valuable than talking about "100 passes" and that type of thing which, when you think about it, really tells you very little....;)

[Entropy]

Nagorak, you have a point in that id games have pretty much stuck to a single theme, Q3 being the exception to some extent. Not too strange given how small an outfit they are (limited resources) and that many of the key people are the same.

If you don't like beige, don't buy beige computers. Simple as that. Same goes for olive green software. :)

WaltC, it is odd that you point out what you percieve to be deficiencies in Carmack, then turn around and note that other developers than id perform the same "sins" to an even larger degree! Plus of course, that you praise features that Carmack has been instrumental in pushing.

I think JC is probably quite aware both of his limitations and his abilities. I can see no particular reason to question that. You may not agree with his priorities and way of expressing things, but that's the way life is. If you don't like the way he is doing things, you are free to do something better. John Carmack has earned a fair bit of respect, not from being successful, but from actually making an effort to be correct in his official statements, and for making efforts to clarify, if his statements despite his efforts turned out questionable. Furthermore, he (and id software) has consistently tried to push the envelope technologically compared to his contemporaries. id software has also had a very positive relationship with both with players and with mod makers - a scene and technological/artistic proving ground they helped create. Additionally, Carmack has been very open and helpful to other parties involved in 3D - his attitude to software patents has been a boon to the entire industry. Plus, he generally makes a lot of sense.

No man is perfect.
You seem bent on shooting at Carmack, perhaps because he has been turned into an icon, and you don't like icons. I can't know.
But he doesn't particularly deserve it.
And suggesting that he doesn't understand the rendering consequences of his engine decisions is going a bit far IMHO.

Entropy

[Oats]

WaltC, hard to beleive you are serious. What's harder to beleive, and hilarious to me, is that you could understand something Carmack fails to grasp. No offense, but you ain't even in the same league (very few people are).

Backtrack a few years, youll see that carmack pushed hard for the features you deem important today.

[SA]

The following is an interesting paper on hardware assisted real time ray tracing using pixel shaders to perform the computations.

http://citeseer.nj.nec.com/cache/papers/cs/25937/http:zSzzSzgraphics.stanford.eduzSzpaperszSzrtongf xzSzrtongfx.pdf/purcell02ray.pdf

I thought the conclusions on the effectiveness of conditional branching and tiling were enlightening. Also the ideas of being able to store shader results to a stream buffer. I also thought that their mentioning the potential use and control of rasterization from within shaders was interesting. All of these ideas have a lot of other uses outside the context of real time ray tracing.

[OpenGL guy]

OpenGL Guy, DemoCoder,

I would agree so long as the set of all programs only contains programs of finite length. AFAICS however, as defined ClassX contains programs of infinite length, and hence is not countable.

Serge
I thought so at first, but reread Arjan's original post: He's talking about a union, so you can't get more elements than exist in the sets being unioned. Thus, there are no programs of infinite length because each of the unioned sets has only programs of finite length.

If he was talking about a limit, as I originally was thinking, then you would be correct.

[SA]

By the way, in the paper on real time ray tracing, look at the number of passes in the pixel shader: 1000 to 3000. Of course they are only drawing one rectangle per pass, but still it is interesting.

[DemoCoder]

Even if the program lengths are allowed to approach infinity, it's still countable.

Each program is represented by an integer N. ClassX is just the set of all natural counting numbers N. Thus, ClassX == N. Thus, it is countable (countably infinite)

For any integer n in N, I can provide a mapping to a program p in ClassX. Likewise, for any program p in ClassX, I can assign it an integer n in the natural numberss. ClassX literally IS the Integers (natural numbers). Classes N < X are just proper setsets of N. The union of all proper subsets of a set is the set itself.

I could switch this discussion over to discussing N, the set of subsets of N call it S1, S2, S3, etc where Sk = {all n in N such that log_2(n) < k} and the union of all Sk, call it X. Sk is the set of all integers of bit-length k or less. X is the union of all sets Sk. Set X is definately countable. In fact, set X = N.

[MfA]

I tried to stay silent, because I cannot say this without a certain amount of hypocrisy ... but I feel it has to be said ...

BOOOOOOOOORING

(which is not a bad thing in itself, but combined with the fact that you guys are highjacking the thread it is a bit ... ;)

[PC-Engine]

I tried to stay silent, because I cannot say this without a certain amount of hypocrisy ... but I feel it has to be said ...

BOOOOOOOOORING

(which is not a bad thing in itself, but combined with the fact that you guys are highjacking the thread it is a bit ... ;)

:lol: At least this time around there's no lawyers involved :lol:

I'm gonna go read that hardware assisted raytracing article now 8)

[no_way]

I tried to stay silent, because I cannot say this without a certain amount of hypocrisy ...
BOOOOOOOOORING

Refreshing IMHO, and quite like the old B3D used to be.
In contrast to endless nv vs ati wars and rumour mill.

(Nostalgia isn't what it used to be.-- Anonymous quote ) ;)

[MfA]

People argueing over semantics and having long discussions about trivial non essential parts of arguements you mean? :) Voxels, raytracing et al. Ill agree with you, but set theory 101 discussions I find a bit tedious and off topic ... but then again my argueing with you is even moreso :/

[DemoCoder]

Actually it was originally analysis, not set theory. :) It did include some automata theory, Canter's theory of ordinals, and complexity theory. :)

[OpenGL guy]

Even if the program lengths are allowed to approach infinity, it's still countable.
Untrue. As I mentioned before, if you take the limit of these sets, you will get an uncountable number of programs. The problem is that in the limit you will get programs on infinite length, which your mapping doesn't handle. In the limit, this is a power set because the number of elements grows exponentially. Thus, the number of elements in the limit is uncountable.

I have no problem accepting that the union of these sets is countable.

[psurge]

well, this is what happens when people with math degrees start arguing ;)

The OT trivial discussion on sets might be boring, but i find it much more interesting than arguing about some 100 pass blah blah. but that's just me.

[DemoCoder]

A program is just an integer. How can the union of integers, as the size of the integers approach infinity, result in an uncountable set? The integers by definition are countable. Any union of integers, no matter how large, is countable. Let's dispense with calling these things "programs", they are integers. When we talk of program length, we are just talking about a set of integers bounded above and below, e.g. ceiling(log_2(n)) <= "length"



Consider the following: Let Sk = {k}. That is, a set considering of a single element, k. Now let us consider U, the union of Sk with k>1..inf. Are you claiming that U is uncountable?

[OpenGL guy]

A program is just an integer. How can the union of integers, as the size of the integers approach infinity, result in an uncountable set? The integers by definition are countable. Any union of integers, no matter how large, is countable. Let's dispense with calling these things "programs", they are integers. When we talk of program length, we are just talking about a set of integers bounded above and below, e.g. ceiling(log_2(n)) <= "length"
As I said, your mapping is flawed. Consider the follow example:
Let Xn = { numbers between 0 and 1 whose decimal expansion has less no more than n digits}. Obviously, Xn is contained in Xm if m > n. However, lim Xn = real numbers

I can do the same thing with your example: Take your integers, map them to the reals by placing a decimal in front of the integer (in other words, divide by 10^n where n = number of digits in integer). This set converges to the real numbers.

[Althornin]

I can do the same thing with your example: Take your integers, map them to the reals by placing a decimal in front of the integer (in other words, divide by 10^n where n = number of digits in integer). This set converges to the real numbers.
By your argument, the set of integers is uncountable.
However, that is simply not the case.

[OpenGL guy]

I can do the same thing with your example: Take your integers, map them to the reals by placing a decimal in front of the integer (in other words, divide by 10^n where n = number of digits in integer). This set converges to the real numbers.
By your argument, the set of integers is uncountable.
However, that is simply not the case.
That's not what they Democoder is arguing. Democoder is arguing that the limit of the ClassX sets is countable. But the limit of the ClassX sets is not countable because you have numbers of infinite length. The integers do not contain numbers of infinite length.

From arjan's post:
Class1 is a finite class, since a PS2.0 program has a fixed maximum length, and thus can be represented by a fixed number of bits, say N. Then Class1 has at most 2^N members, Class2 has 2^(2N) members, Class3 has 2^(3N) members etc.
This converges to "2^infinity" in the limit. I.e. you get programs with bit patterns like 101001000100001..., 10110111011110..., etc. The are analogous to the irrational numbers in the real line.

[Nagorak]

Nagorak, you have a point in that id games have pretty much stuck to a single theme, Q3 being the exception to some extent. Not too strange given how small an outfit they are (limited resources) and that many of the key people are the same.

If you don't like beige, don't buy beige computers. Simple as that. Same goes for olive green software. :)

My main point is everyone is going crazy saying "OMG such great graphics" when in fact the artwork isn't even that impressive. There's more to a game than shadowing, lighting, etc. id does make good engines, but Doom3 isn't half as impressive as everyone is making it out to be. It could be, but not with their lack of good artwork and game (not engine) design.

[Nagorak]

WaltC, hard to beleive you are serious. What's harder to beleive, and hilarious to me, is that you could understand something Carmack fails to grasp. No offense, but you ain't even in the same league (very few people are).

Backtrack a few years, youll see that carmack pushed hard for the features you deem important today.

:roll: :roll: :roll: :roll: :roll:

[DemoCoder]

I can do the same thing with your example: Take your integers, map them to the reals by placing a decimal in front of the integer (in other words, divide by 10^n where n = number of digits in integer). This set converges to the real numbers.

False. Your example is the same example Cantor used to prove the non-existence of a mapping between the integers and the reals. Simply write your list of integers with decimal point in front out in the limit, and you can trivially construct reals which are not included in the list.

Why are we arguing about this? The following facts have already been proven and are in your textbook:

1. The set of all programs, theorems, languages, et al, are countable (look in theory of computation textbook). This works just like Goedel numbering. Any program or theorem in any language can be assigned a unique integer. There are no programs which cannot be numbered by the integers, therefore the set of all possible programs are countable.

2. the union of countably many countable sets is countable (should be in your set theory book. also,look http://www.wikipedia.org/wiki/Countable


ClassX is simply the class of all possible programs (or subset thereof). This set is countable. Class1 ... ClassN are also countable subsets. The union of these subsets is countable. QED.

Edit: It appears we have differing ideas of what ClassX is, perhaps that's the confusion. ClassN is simply the class of all N-pass algorithms. ClassX is simply ClassN in the limit. Any given ClassN algorithm can be reduced to a class < N but augmenting a machine to run it in fewer passes.

You appear to assume that there is the possibility that each pass can be infinite. That is, you are executing two infinitely long shaders in each pass and ClassX could be infinitely many passes each consisting of infinitely long shaders. This is false. Our shaders are limited by the power of the Church-Turing thesis. There are no infinitely long programs and we assume nothing more powerful than a turing machine.

If you cannot assign an integer to a shader, it is not a valid program.

[OpenGL guy]

I can do the same thing with your example: Take your integers, map them to the reals by placing a decimal in front of the integer (in other words, divide by 10^n where n = number of digits in integer). This set converges to the real numbers.

False. Your example is the same example Cantor used to prove the non-existence of a mapping between the integers and the reals. Simply write your list of integers with decimal point in front out in the limit, and you can trivially construct reals which are not included in the list.

Why are we arguing about this? The following facts have already been proven and are in your textbook:

1. The set of all programs, theorems, languages, et al, are countable (look in theory of computation textbook). This works just like Goedel numbering. Any program or theorem in any language can be assigned a unique integer. There are no programs which cannot be numbered by the integers, therefore the set of all possible programs are countable.
You are still talking about the union.
2. the union of countably many countable sets is countable (should be in your set theory book. also,look http://www.wikipedia.org/wiki/Countable (here)
This is not a union we are talking about now: We are talking about a limit. I already said in a previous post that the union of these sets is countable. However, the limit of these sets is uncountable.

Here's why:
1
10
101
1010
10100
101001
etc.

These are elements in the union. However, it's limit 1010010001... is not.

ClassX is simply the class of all possible programs (or subset thereof). This set is countable. Class1 ... ClassN are also countable subsets. The union of these subsets is countable. QED.
I don't disagree with this. What I have been saying is that the limit (i.e. let the length of the programs go to infinity) is not. The limit contains the limit points, many (all, from a measure theory point of view) of which lie outside the union.

Read my post:
http://www.beyond3d.com/forum/viewtopic.php?p=51632#51632
It sounds like you are talking about a limit in the line I quoted.

[DemoCoder]

This is not a union we are talking about now: We are talking about a limit. I already said in a previous post that the union of these sets is countable. However, the limit of these sets is uncountable.


We are talking about a union of sets. Each set is defined to be countable, even in the limit. We have a countable number of sets, each of whose cardinality is countable, therefore the union is countable.


Here's why:
1
10
101
1010
10100
101001
etc.

These are elements in the union. However, it's limit 1010010001... is not.



Your argument is tautological. You start out with an uncountable sequence of sets and end up with the result that a transcendental number is not in the union. Well, that's a surprise. I could just as easily propose the following: Let Sk = {open interval set of all reals between 0 and 1 with decimal point removed}. 1.0 is not in this set. Each number in my set is a legal integer digit string, therefore the integers are uncountable?

The sequence you propose of sets (10, 10100, 101001000, 10100100010000, ...) is uncountable. There is no bijection between the integers and this sequence. Here's another example: (k > 0) Sk = { k if Theorem K is true, -k otherwise } or Sk = {k if Program K halts, -k otherwise }. Choose any unprovable, or uncountable condition and generate your own.


Remember, the requirements are: countably many sets, each set countable, produces countable union. You are not allowed to define a limit sequence of sets which is uncountable. If you keep all of your math in the real of integers and Turing computable numbers, you will that it works out.

The fact remains: All possible computer programs can be ordered and assigned integers. Any possible sequence of such programs (and the logic to construct such a sequence would have to be a program itself which itself has a number!) is countable.

I can claim that there exist sequences that can be constructed "in theory" and invoke the axiom of choice (e.g. the sequence of all programs that halt), but for which no possible program can be constructed to produce such a sequence. This by no means means that the set of all computer programs is uncountable! If I start out by choosing something which makes a bijection into the integers impossible, I end up with uncountability. No surprise.


All it means is that there are some sequences for which no decision procedure exists. You can invoke the axiom of choice all you want to claim that the existence of such a set means the limit is uncountable, I will maintain that if we can produce a set of decision procedures for classifying multipass programs, such a sequence of programs would be countably infinite.

(the classification procedure itself proves the countability, since any procedure would enumerate all possible programs. It literally *IS* the mapping from the integers.)

[OpenGL guy]

This is not a union we are talking about now: We are talking about a limit. I already said in a previous post that the union of these sets is countable. However, the limit of these sets is uncountable.


We are talking about a union of sets. Each set is defined to be countable, even in the limit. We have a countable number of sets, each of whose cardinality is countable, therefore the union is countable.

If you're not going to read what I post, then why bother replying?

Even if the program lengths are allowed to approach infinity, it's still countable.
This is a limit. The limit of these sets is not countable. I don't have any problem with the union being countable, but that's not what your above statement is saying.

The limit contains programs of infinite length, these are not mappable to the integers in any meaningful way.

That's enough from me.

[DemoCoder]

The limit contains programs of infinite length, these are not mappable to the integers in any meaningful way.



What limit? Are you saying that if I define a set S_k = {k} and let k go to infinity, it isn't countable? Or are you saying let S_k = {all n < log_2(k)} (length in bits) is not countable? Can you actually produce a construction for the set that you are claiming isn't countable?

BTW, there is no program of infinite length, unlike real numbers. Programs can approach arbitrarily long length, but can't reach it. It makes no sense to speak of *two* infinitely long programs, unlike say, two irrational numbers. That's what I mean "allow lengths to approach infinity" The lengths can get arbitrarily big, that is, for any program N, there is a program N+1 (the successor) which is bigger.

[Fred]

Im not so sure about that. There could exists programs that invoke themselves recursively an infinite amount of time, in an manner that is no longer directly mappable to the integers (they would map themselves to the reals actually)

It depends on if we're allowed to enumerate recursion. I'm not a pro on computer set theory formalisms, as I don't know the basic assumptions we're working under. Probably little turing machines.

Also, If in reality theres only a set amount of primitive instructions (say an algebra of instructions), there exists most certainly sets of programs which cannot be included in the language of the algebra, unless you approximate them to within a compact space.

[OpenGL guy]

The limit contains programs of infinite length, these are not mappable to the integers in any meaningful way.

What limit? Are you saying that if I define a set S_k = {k} and let k go to infinity, it isn't countable?
Define Sn = {all integers of length n or less}. What's the limit set of Sn? I'll give you a hint: lim (n -> infinity) n is an element of this limit set.

Take ClassX as defined by arjan, but instead of mapping the programs to the integers as strings of 1's and 0's, map them to the rationals as decimals by adding a decimal point before your string of 1's and 0's and call this ClassY. There is clearly a 1-1 mapping between ClassX and ClassY. Now, take limit as n goes to infinity, ClassY goes to the real numbers.

When you say "let n tend to infinity" that is a limit. If you want to talk about an infinite union, then say that because it's not the same thing.

BTW, there is no program of infinite length, unlike real numbers. Programs can approach arbitrarily long length, but can't reach it. It makes no sense to speak of *two* infinitely long programs, unlike say, two irrational numbers. That's what I mean "allow lengths to approach infinity" The lengths can get arbitrarily big, that is, for any program N, there is a program N+1 (the successor) which is bigger.
The original union makes no sense when compared to reality: Eventually n will be larger than all the atoms in the universe, so you can't even store such a program.

Let me give a different example. Let Xn = { n-tuples composed of As and Bs}. Thus, X1 = {A, B}, X2 = {AA, AB, BA, BB}, etc. The limit of Xn as n goes to infinity contains strings of infinite length.

Now, replace A with "0" and B with "1". You get strings of 0s and 1s of infinite length. Note: These are not integers, but that's ok because limit points can be outside the set in question. In fact, these aren't real numbers, but they can make sense as a program:
mad
mad
mad
...

Doesn't that make sense? Who cares that it's never going to finish? We aren't talking about reality here.

Now consider:
lrp
lrp
lrp
...

Two distinct infinitely long programs.

This is why I prefer to use ClassY instead of ClassX: The limit set is easily understood to be the real numbers. In fact, I think taking the limit of ClassX makes little sense, however, I can put an measure on these infinite strings that makes sense.

Anyway, here's a link regarding my above construction:
http://merlin.capcollege.bc.ca/rbrewste/math224/ass2soln.pdf

[Oats]

:roll: :roll: :roll: :roll: :roll:


:roll: :roll: :roll: :roll: :roll:

[arjan de lumens]

Im not so sure about that. There could exists programs that invoke themselves recursively an infinite amount of time, in an manner that is no longer directly mappable to the integers (they would map themselves to the reals actually)

A program can have a finite size, yet have infinite running time, like this rather useless C program:

int main() { return main(); }

The mappings we seem to be discussing are mappings between the program source or object code and the integers, rather than between program invocations and the integers.

And - offtopic? Yes indeed :-?

[Fred]

Right there the program has a recursive call that is enumerated by an instruction.

lets say the program is

start (main)
printf('hello')
call (main)
end

If we are talking about something like a turing machine, that program is reducible to an infinitely countable set. (let hello = 1, fundamental sourcecode = 1111111....) unless you make a new instruction that defines an infinite loop, then its say (12, 2= loop). Thats where it gets hazy in my mind, without specifying a number of fundamental instructions the actual length of the program is secondary.

However if we are talking only about pure length, with an infinite amount of instructions available, then I still side with OGL. For the reasons he gave.

Either way really, its uncountable.

[arjan de lumens]

Right there the program has a recursive call that is enumerated by an instruction.

lets say the program is

start (main)
printf('hello')
call (main)
end

If we are talking about something like a turing machine, that program is reducible to an infinitely countable set. (let hello = 1, fundamental sourcecode = 1111111....) unless you make a new instruction that defines an infinite loop, then its say (12, 2= loop). Thats where it gets hazy in my mind, without specifying a number of fundamental instructions the actual length of the program is secondary.

A program that runs forever essentially corresponds to a turing machine that is unable to halt. If the langauge we use to define a program is turing-complete (which the PS2.0 shader language isn't), we can always code an infinite loop with a finite number of states/instructions/commands. Going back to ClassX versus ClassNull, any program with an infinite loop is a member of ClassNull.


However if we are talking only about pure length, with an infinite amount of instructions available, then I still side with OGL. For the reasons he gave.

Either way really, its uncountable.
The set of all turing machines is countable, as far as I can see. The set of all inifinite-length "programs" is, of course uncountable, though, but only as long as these "programs" are not in any way expressible in a finite number of symbols (otherwise you just count the expressions).

[Basic]

Key point for those who want to untie the knot:

What is the definition of "lim An as n->inf", especially when it's the limit of a series of sets. (Be careful with this one.)

Is there a difference between
"There can exist limit points to a set E outside E."
and
"The union of a (countable) sequence of sets En can contain a point that is outside all of En."

[Fred]

Every neighborhood of the limit point P should contain a point Q != P such that q is still in the set.

Ie every neighborhood of P should contain infinitely many points of the set.

[OpenGL guy]

Key point for those who want to untie the knot:

What is the definition of "lim An as n->inf", especially when it's the limit of a series of sets. (Be careful with this one.)
Easy: It's the limit points of the An's. Or, expressed another way, if there is a convergent sequence of xn's such that xn is an element of An, then the limit point of this sequence is in lim An.

Is there a difference between
"There can exist limit points to a set E outside E."
and
"The union of a (countable) sequence of sets En can contain a point that is outside all of En."
A union B = set of all x such that x is in either A or B. An element of an infinite union must be in one of the sets being unioned.

And there can certainly be limit points to a set outside the set itself. The limit points of the rational numbers is the whole real line, which contains irrational numbers, for example. Or take X = {1, 1/2, 1/3, 1/4, ...}. 0 is a limit point of this set.

[Basic]

Maybe I should have ploughed through more of the posts, ... but naaah. (I noticed after I posted that you already had addresed some of it, but your last post was clearer to me.)


The point I wanted to get at was that you were thinking of ClassX as two different things.
But given the idea you had about what ClassX is, you all made a correct analysis of it.


Let's call the union of Class1, Class2, Class3 and so on ClassX.here (http://www.beyond3d.com/forum/viewtopic.php?t=2961&postdays=0&postorder=asc&star t=20)
That's an union of an infinite amount of countable sets. Not a limit set. The union is countable. It does not contain the limit points. Elements can be arbitrarily large, but not be infinite.

If you instead define ClassUN as the union of Class1,...ClassN. And then define ClassZ as lim (N->inf) ClassUN, with the definition of limit you said above. Then you'll get an uncountable set.
But that wasn't what arjan said (at least not in the post I read).

I think ClassX is a more interesting class than ClassZ.


The first question I asked wasn't a "have you got this right"-check. It was for the reason that I don't remember seeing a definition of it in any book. (It was a long time since I read any math though.) So I tried to think of the normal definition. That would need a distance function between two sets. First thought was the Lebesgue measure, but it didn't quite cut it.

So I thought about of the definition of lim (n->inf) f(n). (For every epsilon there is...) And got to this:

Ainf = lim (n->inf) An
<=>
For every point x in Ainf, there is an N such that x is in An for all n>=N.

This definition (as opposed to the definition you gave) would have the property that:
lim (n->inf) union (i=1...n) Ai = union (i=1...inf) Ai

Is the definition you gave established as THE definition? And in that case, can you give the reason why we'd want a definition that includes limit points of the set. It doesn't have to be the same kind of "limit" in "limit points of the sequence of sets" and "limit of the sequence of sets".

[Althornin]

And there can certainly be limit points to a set outside the set itself.
Only if the set is open... (or rather, NOT closed)

[OpenGL guy]

And there can certainly be limit points to a set outside the set itself.
Only if the set is open... (or rather, NOT closed)
I did say "can", didn't I? I didn't say "must exist". "can" implies "possibly", not "must be".

[Fred]

In a pure topological space, the limit is defined via the natural concepts of open sets and neighborhoods.

Textbooks often will define things in different manners, depending on their purposes.

Since we are dealing with objects that map to a subset of the reals, it seems obvious that computer set theory models would use manifolds, or even less general constructs (eg spaces with an associated distance function).

In R^k for instance, a less general notion of Cauchy sequences can also be utilitized to extract limit points.

[DemoCoder]

Scott Topology has been used to do analysis of computable algorithms. It models the non-continuuous nature of computer logic in the reals.