The problem with this is thinking of it in terms of how much time you've spent at it. Did you play the game and have fun during all those hours? If so, great, "mission accomplished." If not, maybe you should reconsider what you're doing.
If you're playing for fun, the memories of the good times you've had shouldn't be diminished just because somebody else now gets to see that content. You still got there first, anyway.
Ray tracing is great for static scenes. But movement is the key to games that require this much detail, and so each frame should not be beautifully rendered framebuffers, but a mix of several framebuffers over the span of one frame. No, no, no! Mixing several framebuffers together gives you *lousy* motion blur. You'll get severe artifacts from each pixel using the same set of uniform samples in the time domain -- very fast moving objects can appear cloned in multiple places, for example.
I'm glad to see that others thought of the HP calculators here too. Mine isn't quite that old -- it's an HP 48 that's now about 15 years old. Still works great, and I love the crisp snap to the buttons. It's occurred to me before that I'll probably end up passing it on to my son (now 2 1/2) someday.
Same thing with Emacs key combos. I've had times where someone notices me doing something interesting with and asks me how I did it. Then I'd have to stop and mime it again on the keyboard before I could tell them exactly what I'd pressed.
The page with the video linked to the OneUps' MySpace page for the music. The download link there doesn't work, but if you'd like a decent quality MP3 of it, it was posted on OCRemix.org some time ago.
I discovered the wxmaxima front end by accident from the list of Ubuntu packages (I originally mistook it for the standard xmaxima tk interface and was pleasantly surprised.) I've found that it makes Maxima much more pleasant to work with. Might be worth having a look at if you haven't seen it already.
Normally, Google's form uses q as the field for the search term, not searchQ. And btnI is the name of the "I'm Feeling Lucky" button. The link actually has nothing to do with IE 8. It's really just equivalent to an "I'm Feeling Lucky" search for contactlognet, for which Google immediately shoots back a redirect to that site. That site in turn sends you yet another redirect.
I agree that yapping on the phones in the middle of crowd or while driving is quite rude. But the problem with is that you assume that it's even necessary to answer a call immediately. Most phones have caller id and voicemail.
If I'm in the middle of something (e.g., driving) or in a public place where talking on the phone would be rude or annoying to the people around me, I'll just let the call go and then make a discrete exit to an area with some privacy where I won't be bothering anyone and return the call. This usually doesn't take more than a minute or two and the caller is still in a good situation to speak with me.
My cell phone is just a way to get in touch with me quickly, though not always instantaneously.
Certainly not "free" exactly. But in general, as long as you're using a good acceleration structure and can hold everything in-core, performance is roughly O(lg N) in the number of polygons. So the speed hit going from 50k to 100k polygons would be roughly equivalent to that of going from 100k to 200k. That's where the scalability of ray tracing comes in. There's still going to be quite a difference between one big polygon and 100k of them.
You'll also find that most ray tracers exhibit the same performance variation between facing a wall and facing a full landscape. It may not be as dramatic due to the relatively high constant of proportionality for a software ray tracer vs. a GPU but it's still there. A large part of that is probably just cache performance -- you'll have a lot more cache hits facing the wall.
Reflection-wise, you've got the right idea -- there will be a decent speed hit for them. But you've got it backwards. Doing a good job of computing color bleed effects require a ray tracer which supports global illumination and that can take astronomically more rays to compute than a decent implementation of basic specular reflections. You probably need at least 100 rays/pixel or more to even have a prayer of not having any excessively noisy image. Ray tracing is a point-sampling technique which means that any time you have any sort fuzzy/soft kinds of effect like ambient occlusion, glossy reflections, soft shadows or color bleed from indirect illumination.
Another option might be to require a credit-card for trial accounts. They could do the thing where they verify the credit card without actually placing a charge on it. Credit cards associated with accounts banned for farming/advertising would be barred from creating new accounts. This would mean the farmers would need to have a steady supply of credit cards to be able to keep up which should raise the bar a little. And having the credit card on file could make things easier on legitimate trial accounts by offering a one-click upgrade to a paid account at the end of the trial period.
Not to mention that speedup (i.e., best serial running time over best parallel running time) and efficiency (i.e., speedup over number of processors) are well defined ways of quantifying how well a piece of a code scales in parallelism. If, for example, you're still getting 95% efficiency running on 2000 nodes, then I'd call that pretty darn good given Ahmdal's Law and "massively scalable". The way the efficiency curve falls off as you increase the number of processors tells you a lot about how parallel a piece of code is.
Granted massively parallel is a fuzzy, qualitative phrase, but parallel efficiency at high numbers of processors is a pretty good measure.
[Forgive the LaTeX notation -- I'm not sure how else to best express the math without sub and sup tags.]
Newton-Raphson is a root finding method. Given a starting point it finds successively more accurate approximations to the root. The formula for it looks like: x_{n+1} = x_n - f(x_n)/f'(x_n), where f(x) is the function to find the root of, f'(x_n) is the derivative of that function and x_n are the successive approximations. Essentially, given a guess it looks at the slope of the function at that point follows a tangent line until it crosses the zero line. That point becomes the next guess.
Finding the reciprocal square root of a is equivalent to solving x^{-2} - a = 0 which means that you use f(x) = x^{-2} - a. The derivative of that is f'(x) = -2x^{-3}. Putting those into the Newton-Raphson formula gives you x_{n+1} = x_n - (x_n^{-2} - a) / -2x_n^{-3}, which simplifies down to x_{n+1} = x_n(3 - a*x_n^2)/2. This is equivalent to the last line before the return in that InvSqrt() function.
Convergence of Newton-Raphson is quadratic which means that each time you repeat that line with a previous guess you double the number of digits of accuracy (up to the limit of the hardware of course).
Because it's not actually a float-to-int cast as you'd normally think of it. Rather, it's mucking with the bit representation of the float. It's roughly equivalent to "union { float x; int i; };"
In addition to the vector calculus, and linear algebra already mentioned, I'd suggest looking into spatial data structures as well. Things like bounding volume hierarchies, BSP-trees and kd-trees. (Okay, so it's not *quite* math, but it's probably in the ball park.)
I'm really glad to see CMake finally getting used by a high-profile project. I hated CMake at first sight -- having to install it first before I could build a project seemed strange after the autoconf./configure; make routine. But it really is a nice system and has meant no longer having to support and keep in sync parallel make files, Visual Studio projects, XCode projects, etc. like I used to. Configure scripts failing on native Windows builds, for example, was always a pain. It's been a lot easier to build cross-platform projects now that I'm using CMake for everything.
Seeing KDE adopting it has been great news for me, since it means that I may be able to start releasing my own small projects with CMakeList.txt files without getting funny looks. I love that it's looking like KDE will blaze the trail for us little guys who prefer CMake over the autoconf tool chain.
My advice would be to pick up a decent intro book on graphics. The Foley and Van Dam is a classic, but nearly any good book on the topic tends to have a review of the basic math involved in 3d: linear algebra with 3- or 4-value vectors and 3x3 or 4x4 matrices, the perspective divide, etc. Knowing the basics will help you have a lot better idea of what to do. But for anyone curious about the most basic 3d, here's a simple way to do it that should work decently for simple wireframe plots.
1) Take each 3d point of interest and apply some set of rotations around the X, Y, and Z axis to get the view angle right. You'll probably want to just do one rotation around each axis. e.g.:
x2 = x * cos( z_angle ) + y * sin( z_angle ); y2 = x * -sin( z_angle ) + y * cos( z_angle );
At this point, you'll have rotated your original coordinate (x,y,z) by some angle around some axis to get (x3,y3,z3)
(To my fellow graphics geeks: yes, yes, I know full well that matrices and quaternions are better -- I'm trying keep this simple.)
2) Maybe add some distance to the z value, to move ("translate") it away from the "camera" at the origin. You'll need to add enough to make sure that all of your z-values are positive and non-zero before step 3:
z4 = z3 + z_translate
3) Do what's called the "perspective divide" to find the two dimensional coordinate of this point. e.g.:
4) Either plot a point at the (px,py) that you just got, or compute steps 1 and 2 twice for the end points of lines and then use your system's graphics primitives to draw lines between (px1,py1) and (px2,py2). If you're not using a language or a library that can do simple 2d graphics, then I'd suggest writing out a file with the lines in SVG format (and then rasterize to bitmap with a program like Batik, Inkscape, Illustrator, etc.) e.g.:
<?xml version="1.0" standalone="no"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd" > <svg width="4cm" height="4cm" viewBox="0 0 400 400" xmlns="http://www.w3.org/2000/svg" version="1.1">
<path d="M px1 py1 L px2 py2" fill="none" stroke="black" stroke-width="1"/> <!-- First line to draw -->
<path d="M px1 py1 L px2 py2" fill="none" stroke="black" stroke-width="1"/> <!-- Second line to draw -->
<path d="M px1 py1 L px2 py2" fill="none" stroke="black" stroke-width="1"/> <!-- Third line to draw, etc... --> </svg>
5) If you want more than wireframe, things will be a lot more complicated. At the very least, you'll need to be able to fill polygons and sort back to front by the z-value after the rotation so that everything gets drawn in the correct order. Z-buffers would be even better.
Well, I hope all that helps. Again, if anyone's really interested, I'd suggest getting a real book on the topic. But I hope this's enough to get the curious started.
This is the largest gripe I have with it after seeing it on my home machine (with a BGR flatpanel). By all means, use standard grey-scale antialiasing of images and text for the web, but subpixel antialiasing (a.k.a. ClearType) is monitor-specific. And it's worse when the text is small like this.
...sorting requires a certain number of comparisons, which it can be shown is on the order of n log n.
Just a nitpick -- that's only true for sorts based on comparisons. Other sorts that don't require comparisons, such as radix and counting sorts can achieve a potentially smaller asymptotic bound.
Other than that, I have to agree with you. I know at least two programmers with degrees in philosophy. One was a CS professors at the college I attended. He had a fairly unique approach to teaching some of his classes: rigorously formal but in a manner a little different from the usual mathematical way. I don't know if philosophy and CS are the perfect pairing, but I think it's important to have a fairly broad base of knowledge of other subjects in addition to basic CS. Most of the best coders I've known have been CS majors with well rounded educations. I really think liberal arts schools are the way to go.
Slashdot Mirror
The problem with this is thinking of it in terms of how much time you've spent at it. Did you play the game and have fun during all those hours? If so, great, "mission accomplished." If not, maybe you should reconsider what you're doing.
If you're playing for fun, the memories of the good times you've had shouldn't be diminished just because somebody else now gets to see that content. You still got there first, anyway.
Honestly, ray tracing has been getting motion blur right since 1984. Not to mention that it can even simulate the effect of camera shutters.
I'm glad to see that others thought of the HP calculators here too. Mine isn't quite that old -- it's an HP 48 that's now about 15 years old. Still works great, and I love the crisp snap to the buttons. It's occurred to me before that I'll probably end up passing it on to my son (now 2 1/2) someday.
Yep. I've had that.
Same thing with Emacs key combos. I've had times where someone notices me doing something interesting with and asks me how I did it. Then I'd have to stop and mime it again on the keyboard before I could tell them exactly what I'd pressed.
Uggh, you're right. I just noticed that Slashdot doesn't even slap the nofollow attribute onto links in comments.
The page with the video linked to the OneUps' MySpace page for the music. The download link there doesn't work, but if you'd like a decent quality MP3 of it, it was posted on OCRemix.org some time ago.
True. Put that way, it's basically Amdahl's law for air travel.
I discovered the wxmaxima front end by accident from the list of Ubuntu packages (I originally mistook it for the standard xmaxima tk interface and was pleasantly surprised.) I've found that it makes Maxima much more pleasant to work with. Might be worth having a look at if you haven't seen it already.
It is offtopic, but I'll answer anyway.
Normally, Google's form uses q as the field for the search term, not searchQ. And btnI is the name of the "I'm Feeling Lucky" button. The link actually has nothing to do with IE 8. It's really just equivalent to an "I'm Feeling Lucky" search for contactlognet, for which Google immediately shoots back a redirect to that site. That site in turn sends you yet another redirect.
I don't know what the conversion rate is anymore, since 2.1 was rolled out.
I agree that yapping on the phones in the middle of crowd or while driving is quite rude. But the problem with is that you assume that it's even necessary to answer a call immediately. Most phones have caller id and voicemail.
If I'm in the middle of something (e.g., driving) or in a public place where talking on the phone would be rude or annoying to the people around me, I'll just let the call go and then make a discrete exit to an area with some privacy where I won't be bothering anyone and return the call. This usually doesn't take more than a minute or two and the caller is still in a good situation to speak with me.
My cell phone is just a way to get in touch with me quickly, though not always instantaneously.
Certainly not "free" exactly. But in general, as long as you're using a good acceleration structure and can hold everything in-core, performance is roughly O(lg N) in the number of polygons. So the speed hit going from 50k to 100k polygons would be roughly equivalent to that of going from 100k to 200k. That's where the scalability of ray tracing comes in. There's still going to be quite a difference between one big polygon and 100k of them.
You'll also find that most ray tracers exhibit the same performance variation between facing a wall and facing a full landscape. It may not be as dramatic due to the relatively high constant of proportionality for a software ray tracer vs. a GPU but it's still there. A large part of that is probably just cache performance -- you'll have a lot more cache hits facing the wall.
Reflection-wise, you've got the right idea -- there will be a decent speed hit for them. But you've got it backwards. Doing a good job of computing color bleed effects require a ray tracer which supports global illumination and that can take astronomically more rays to compute than a decent implementation of basic specular reflections. You probably need at least 100 rays/pixel or more to even have a prayer of not having any excessively noisy image. Ray tracing is a point-sampling technique which means that any time you have any sort fuzzy/soft kinds of effect like ambient occlusion, glossy reflections, soft shadows or color bleed from indirect illumination.
Another option might be to require a credit-card for trial accounts. They could do the thing where they verify the credit card without actually placing a charge on it. Credit cards associated with accounts banned for farming/advertising would be barred from creating new accounts. This would mean the farmers would need to have a steady supply of credit cards to be able to keep up which should raise the bar a little. And having the credit card on file could make things easier on legitimate trial accounts by offering a one-click upgrade to a paid account at the end of the trial period.
Not to mention that speedup (i.e., best serial running time over best parallel running time) and efficiency (i.e., speedup over number of processors) are well defined ways of quantifying how well a piece of a code scales in parallelism. If, for example, you're still getting 95% efficiency running on 2000 nodes, then I'd call that pretty darn good given Ahmdal's Law and "massively scalable". The way the efficiency curve falls off as you increase the number of processors tells you a lot about how parallel a piece of code is.
Granted massively parallel is a fuzzy, qualitative phrase, but parallel efficiency at high numbers of processors is a pretty good measure.
...nobody knows you're a troll.
Is it just me or does it sound like he thinks he's invented the NaN?
[Forgive the LaTeX notation -- I'm not sure how else to best express the math without sub and sup tags.]
Newton-Raphson is a root finding method. Given a starting point it finds successively more accurate approximations to the root. The formula for it looks like: x_{n+1} = x_n - f(x_n)/f'(x_n), where f(x) is the function to find the root of, f'(x_n) is the derivative of that function and x_n are the successive approximations. Essentially, given a guess it looks at the slope of the function at that point follows a tangent line until it crosses the zero line. That point becomes the next guess.
Finding the reciprocal square root of a is equivalent to solving x^{-2} - a = 0 which means that you use f(x) = x^{-2} - a. The derivative of that is f'(x) = -2x^{-3}. Putting those into the Newton-Raphson formula gives you x_{n+1} = x_n - (x_n^{-2} - a) / -2x_n^{-3}, which simplifies down to x_{n+1} = x_n(3 - a*x_n^2)/2. This is equivalent to the last line before the return in that InvSqrt() function.
Convergence of Newton-Raphson is quadratic which means that each time you repeat that line with a previous guess you double the number of digits of accuracy (up to the limit of the hardware of course).
Because it's not actually a float-to-int cast as you'd normally think of it. Rather, it's mucking with the bit representation of the float. It's roughly equivalent to "union { float x; int i; };"
In addition to the vector calculus, and linear algebra already mentioned, I'd suggest looking into spatial data structures as well. Things like bounding volume hierarchies, BSP-trees and kd-trees. (Okay, so it's not *quite* math, but it's probably in the ball park.)
TFA links to a site, called "Coming Zune", which suggests that it's just "zoon", to rhyme with "soon".
I'm really glad to see CMake finally getting used by a high-profile project. I hated CMake at first sight -- having to install it first before I could build a project seemed strange after the autoconf ./configure; make routine. But it really is a nice system and has meant no longer having to support and keep in sync parallel make files, Visual Studio projects, XCode projects, etc. like I used to. Configure scripts failing on native Windows builds, for example, was always a pain. It's been a lot easier to build cross-platform projects now that I'm using CMake for everything.
Seeing KDE adopting it has been great news for me, since it means that I may be able to start releasing my own small projects with CMakeList.txt files without getting funny looks. I love that it's looking like KDE will blaze the trail for us little guys who prefer CMake over the autoconf tool chain.
My advice would be to pick up a decent intro book on graphics. The Foley and Van Dam is a classic, but nearly any good book on the topic tends to have a review of the basic math involved in 3d: linear algebra with 3- or 4-value vectors and 3x3 or 4x4 matrices, the perspective divide, etc. Knowing the basics will help you have a lot better idea of what to do. But for anyone curious about the most basic 3d, here's a simple way to do it that should work decently for simple wireframe plots.
" > /> <!-- First line to draw --> /> <!-- Second line to draw --> /> <!-- Third line to draw, etc... -->
1) Take each 3d point of interest and apply some set of rotations around the X, Y, and Z axis to get the view angle right. You'll probably want to just do one rotation around each axis. e.g.:
x2 = x * cos( z_angle ) + y * sin( z_angle );
y2 = x * -sin( z_angle ) + y * cos( z_angle );
x3 = x2 * cos( y_angle ) + z * sin( y_angle );
z2 = x2 * -sin( y_angle ) + z * cos( y_angle );
y3 = y2 * cos( x_angle ) + z2 * sin( x_angle );
z3 = y2 * -sin( x_angle ) + z2 * cos( x_angle );
At this point, you'll have rotated your original coordinate (x,y,z) by some angle around some axis to get (x3,y3,z3)
(To my fellow graphics geeks: yes, yes, I know full well that matrices and quaternions are better -- I'm trying keep this simple.)
2) Maybe add some distance to the z value, to move ("translate") it away from the "camera" at the origin. You'll need to add enough to make sure that all of your z-values are positive and non-zero before step 3:
z4 = z3 + z_translate
3) Do what's called the "perspective divide" to find the two dimensional coordinate of this point. e.g.:
px = x3 / z4 * scale + center_x;
py = y3 / z4 * scale + center_y;
4) Either plot a point at the (px,py) that you just got, or compute steps 1 and 2 twice for the end points of lines and then use your system's graphics primitives to draw lines between (px1,py1) and (px2,py2). If you're not using a language or a library that can do simple 2d graphics, then I'd suggest writing out a file with the lines in SVG format (and then rasterize to bitmap with a program like Batik, Inkscape, Illustrator, etc.) e.g.:
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd
<svg width="4cm" height="4cm" viewBox="0 0 400 400" xmlns="http://www.w3.org/2000/svg" version="1.1">
<path d="M px1 py1 L px2 py2" fill="none" stroke="black" stroke-width="1"
<path d="M px1 py1 L px2 py2" fill="none" stroke="black" stroke-width="1"
<path d="M px1 py1 L px2 py2" fill="none" stroke="black" stroke-width="1"
</svg>
5) If you want more than wireframe, things will be a lot more complicated. At the very least, you'll need to be able to fill polygons and sort back to front by the z-value after the rotation so that everything gets drawn in the correct order. Z-buffers would be even better.
Well, I hope all that helps. Again, if anyone's really interested, I'd suggest getting a real book on the topic. But I hope this's enough to get the curious started.
Mod parent up.
This is the largest gripe I have with it after seeing it on my home machine (with a BGR flatpanel). By all means, use standard grey-scale antialiasing of images and text for the web, but subpixel antialiasing (a.k.a. ClearType) is monitor-specific. And it's worse when the text is small like this.
...sorting requires a certain number of comparisons, which it can be shown is on the order of n log n.
Just a nitpick -- that's only true for sorts based on comparisons. Other sorts that don't require comparisons, such as radix and counting sorts can achieve a potentially smaller asymptotic bound.
Other than that, I have to agree with you. I know at least two programmers with degrees in philosophy. One was a CS professors at the college I attended. He had a fairly unique approach to teaching some of his classes: rigorously formal but in a manner a little different from the usual mathematical way. I don't know if philosophy and CS are the perfect pairing, but I think it's important to have a fairly broad base of knowledge of other subjects in addition to basic CS. Most of the best coders I've known have been CS majors with well rounded educations. I really think liberal arts schools are the way to go.