Sunday, June 22, 2008
Raytracing
When reading the August 2006 issue of Scientific American, an article on raytracing caught my eye as I was actively involved in drafting, CAD, 3-D modelling and animation at the time.
Raytracing is a very interesting technique in computer graphics. It involves tracing rays forward from the lens through the image plane until intersected by some object in the scene. Then, the ray is tested against its nearest neighbours for incoming light. Finally, the pixel on the image plane is coloured using the object properties in conjunction with scene lighting to produce exotic properties such as reflection, refraction, scattering, aberration, caustics, and shadows. Raytracing is, at the moment, slower than its counterpart scanline rendering, but can produce far better results (see Photorealism).
Due to its high computational cost, it has yet to be implemented as hardware for real-time rendering for use in entertainment (e.g. computer games). However, a team at the University of Saarland has already made progress in producing Ray Processing Units (RPUs). It still remains to be seen if this new technology will replace conventional GPUs and make its way to the market via industry powerhouses such as Nvidia and ATI.
Links:
A Great Leap in Graphics - Scientific American http://www.sciam.com/article.cfm?id=a-great-leap-in-graphics
Ray tracing (graphics) - Wikipedia
http://en.wikipedia.org/wiki/Ray_tracing_%28graphics%29
Photorealism - Wikipedia
http://en.wikipedia.org/wiki/Photorealism
RPU: A Programmable Ray Processing Unit for Real Time Ray Tracing - University of Saarland
http://graphics.cs.uni-sb.de/~woop/rpu/rpu.html
An Old Probability Problem, Revisited
Friday, May 23, 2008
Self-replication, self-replication, ...
Imagine a machine that could, given the required raw materials and energy, assemble a copy of itself with utmost precision. Would you call it ALIVE?
Self-assembly and self-replication has received a great deal of attention in nanotechnology, especially after K. Eric Drexler's Engines of Creation. However, to produce a machine, at any scale, to make itself is a formidable challenge. Scientists argue that if life is possible naturally via self-replicating molecular machinery in systems such as DNA and cells and tissue, then artificial self-replication is not theoretically impossible. Although self-replication is not restricted to the nanoscale, it seems natural to start at the molecular level just as nature did billions of years ago.
Although the physics of the nanoscale is a bizzare paradigm compared to the Newtonian framework which we are accustomed to living in, many futurists and sci-fi authors begin with a very traditional extension of mechanistic assembly into smaller scales. They envision little nanorobots with arms fitting parts together to make a second nanorobot. These nanorobots may be multi-purpose and even capable of machine evolution. Some of the more fanciful plots conjure up what is now termed "gray goo," where swarms of ultra-smart nanorobots become uncontrollable. But before going further into details, it is imperative to remove ourself from this fantasy world and examine things with a more academic poise. A mechanistic assembler, even at large scales, is very difficult to design. Imagine a modified multi-purpose tool such as a robotic arm or CNC lathe. In fact, we can combine these two into a single machine where the arm is used for materials transport, and the lathe is for machining. Trying to plan out this sort of scheme quickly becomes extraordinarily complicated. Important questions dealing with the prefabrication of parts need to be addressed. How complex can the available raw materials be for the machine to qualify as a self-assembler. We may need to compare it to cell, which receives the water, simple nutrients, and energy it needs to perform mitosis. It is not desirable to have an assembler of too great a complexity so that it becomes a design issue to plan the copying process. However, we do not want something too simple either or it won't be able to replicate itself. Clearly, there needs to be an equilibrium between these factors for a simple, elegant self-replicator. Moreover, it is important to point out the end-result need not be a useful machine. Purely accomplishing this for even academic purposes is enough to get the wheels of industry in motion.
What may look good on TV and in sci-fi novels just may not fly when it comes to engineering. So some scientists are taking a very different view to nano self-assembly and self-replication: an approach based mainly on biochemistry. We simply cannot ignore the quantum effects, thermal noise, and fluid viscosities when a machine's size is reduced to the order of one hundred thousandth of the thickness of a human hair. It seems that the next generation of nano-devices will be "soft machines," a term coined by Prof. Richard Jones from the University of Sheffield, UK. These machines will be actively using biological and chemical principles to manipulate molecules. Many of these machines try to imitate what already exists in cells and proteins, while others even steal parts of natural molecular machinery.
How does DNA miraculously replicate itself? Rather than delve into the depths of biochemistry, we can take a very unorthodox approach to understanding the mechanism of self-assembly: computer science. Although the concepts are greatly simplified (no physical movement of atoms), a great deal can be gleaned from "virtual" self-assembly, perhaps the purest form (because no errors are made). First, we examine the work of John von Neumann, one of the most prolific mathematicians of the 20st century. Most importantly, he proved theorems on the existence of a self-replicator and developed the theory of cellular automata. In addition, he worked with concepts such as open-ended machine evolution. He designed the first "universal constructor" with a total of 29 states. His designs have been significantly simplified since. Here are some definitions for quick reference:
Cellular Automaton (Wikipedia):
"A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states.The grid can be in any finite number of dimensions. Time is also discrete, and the state of a cell at time t is a function of the states of a finite number of cells (called its neighborhood) at time t − 1. These neighbors are a selection of cells relative to the specified cell, and do not change (though the cell itself may be in its neighborhood, it is not usually considered a neighbor). Every cell has the same rule for updating, based on the values in this neighbourhood. Each time the rules are applied to the whole grid a new generation is created."
Open-ended evolution (University of Hertfordshire, UK - http://homepages.feis.herts.ac.uk/~comqcln//al7ev/nehaniv-cpx/node3.html):
"An evolutionary system E exhibits open-ended evolution if for every integer N, there exists a time t such that at time t, the system includes an entity e whose complexity is at least N, i.e. cpx(e) >= N.
Now, using these concepts as background, consider a program that will output only its own source code. This is known as a quine. In a sense, this is like a virtual organism. We can by analogy, extend several of it's components (lines of code) to have physical meaning. Consider the following: "A quine exists in any programming language that has the ability to output any computable string, as a direct consequence of Kleene's recursion theorem." (Wikipedia) It may seem simple to write a quine, but reality is that it cannot be done without some clever tricks. For example, some programmers use recursion to feed the program to itself, therefore making it the input and the output. Others try to reconstruct it from the strings used to write the code. Some make use of the preprocessor, where the code is read before being executed. A friend of mine suggested a UNIX shell script (text file) that would, when executed, display itself using something similar to this:
(Courtesy of Wikipedia)
The image shown above depicts a simple idea for a macroscopic self-replicator. In fact, many teams across the world are pursuing this lofty goal. The concept of rapid prototyping has become of great relevance to this topic. Rapid prototyping is defined as, "the automatic construction of physical objects using solid freeform fabrication." (Wikipedia) Most notably, the RepRap team at the University of Bath, UK has made enormous headway with this technique. As of May 2008, the team claims that their machine, essentially a 3-D printer, has reproduced all of its parts (which need to be manually assembled to create the copy).
Links:
John von Neumann - Wikipedia
http://en.wikipedia.org/wiki/Von_Neumann
Cellular automaton - Wikipedia
http://en.wikipedia.org/wiki/Cellular_automata
Conway's Game of Life - Wikipedia
http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
Quine (computing) - Wikipedia
http://en.wikipedia.org/wiki/Quine_%28computing%29
Rapid prototyping - Wikipedia
http://en.wikipedia.org/wiki/Rapid_prototyping
RepRap Home
http://reprap.org/bin/view/Main/WebHome
Thursday, May 22, 2008
An Old Probability Problem
What is a probability that a quadratic equation of the form x^2+2bx+c=0 (where b and c are real numbers) will have real roots?
Here is my solution:
I used the same technique stated here:
http://webs.wichita.edu/facsme/cbl/functions/roots.pdf
Remember that we are considering the probability of a point being in the space below the curve c=b^2 (condition for discriminant to be real). Therefore we consider the size of our square from -a to a on the horizontal axis and take this to the infinite limit (whole real line). We consider a one-sided problem due to the inherent symmetry of the curve b^2. The curve is integrated from 0 to sqrt(a) because this bounds the curve within a square of size a^2 in the first quadrant. The remainder area from sqrt(a) to a in the top quadrant is provided by the second term in the numerator. The last term is for the square in the bottom quadrant. The denominator simply doubles the square for top and bottom quadrants. Simplifying the limit, we obtain 1.
"Little Neutral One": The Neutrino and Understanding the Cosmos
The following text is an essay that I submitted to DuPont Challenge in 2007.
__________
Every second, millions of neutrinos are rushing through the period at the end of this sentence. The story of this puzzling particle begins with the process of beta decay in which a proton in a radioactive nucleus is converted into a neutron, and an electron is emitted. According to predictions, the emerging electron was expected possess specific energy quanta, but empirical evidence indicated a range of energies. In 1930, Austrian physicist Wolfgang Pauli eventually solved this problem by proposing the existence of a third and previously unknown neutral particle: the neutrino (Close et al. 2002).
Neutrinos are fundamental particles with miniscule mass, classified under the family of leptons (particles unaffected by the strong nuclear force). Since neutrinos scarcely interact with other particles or each other, detection is a daunting task (Alpert 2006). As a consequence, neutrino detectors have to be placed deep underground to filter out ‘noise’ from cosmic rays (Close et al. 2002). After its experimental verification in 1956 by physicists Cowan and Reines (Close et al. 2002), three flavours of neutrinos have been identified: the electron neutrino, the muon neutrino, and the tau neutrino. With a more firm understanding of these particles, neutrino research continues in particle physics with aims to understand the very fabric of matter. More importantly, it has given impetus to the emergence of a relatively new field: neutrino astronomy.
The Sun has always intrigued humans, as it unfailingly provides our planet with light and warmth. Though this stellar neighbour may be close, its inner workings are still not entirely understood. The fierce thermonuclear reactions that take place within the Sun emit copious amounts of neutrinos; a dazzling 60 billion of them pass through every square centimetre of the Earth’s surface per second (Close et al. 2002). American physicist Raymond Davis and his associates first detected solar neutrinos, which tend to be primarily of the electron type, in the 1970s. This led to the predictions of the solar flux of neutrinos and subsequent testing of these models in detectors such as Super Kamiokande (
As the heliophysical research on neutrinos breaks new ground, astronomers are turning to another massive source: supernovae. One of the first well-documented supernova events was on 23 February 1987, when a vibrant cosmic shower of particles arrived from the ancient explosion of Sanduleak-69202 in the Large Magellanic Cloud. In fact, two Cerenkov detectors around the world confirmed an unprecedented 19 neutrino interactions within a span of 13 seconds (Suzuki 2002, Learned 2004). This was quickly recognized to be the typical trace of events taking place at the centre of star when it collapses. It decisively confirmed theories of stellar evolution that predicted 99% of the star’s binding energy to be released as neutrinos and only the remaining 1% as visible light and other forms of radiation (Suzuki 2002). In particle astronomy, using neutrinos to track cosmic events became very popular; unlike charged cosmic rays, neutrinos are completely unaffected by strong magnetic fields in our galaxy (Close et al. 2002). Therefore, neutrino trajectories can be retraced exactly to their sources. In addition, related particles like pions and muons are affected by traversing through large bodies of matter, while “a low-energy neutrino in flight would not notice a barrier of lead 50 light-years thick.” (Learned 2004) By studying supernovae through neutrinos, a great deal about the final phases of stellar evolution can be revealed, be it the stellar collapse into a neutron star or a black hole.
In the world of physics, confirmation of the neutrino’s mass caused a total revolution. New insights on what we now call “dark matter” are emerging. “[New] models of the universe [indicate] that much more matter must be present in addition to the matter that scientists can detect. If neutrinos have mass, they could account for some of this missing matter.” (Hofstadter 2006) In response, scientists have thought of solutions such as MACHOs (massively compact halo objects) made of normal matter in invisible form. However, recent developments show that dark matter is in fact very different from normal matter. It is thought to be made of extremely light particles such as axions, neutrinos or the highly hypothetical species of WIMPs (weakly interacting massive particles) (Hawking 2001). On the other hand, neutrinos are also shedding light on a prominent theory of the universe’s origins, the Big Bang. “At about a hundredth of the second after the big bang, the temperature would have been 100 billion degrees, and the universe would have contained mostly photons, electrons, and neutrinos…and their antiparticles…” (Hawking 2001) As the study of neutrinos takes us closer to Stephen Hawking’s Grand Unified Theory, other sources of high-energy neutrinos such as collapsing galaxies, exploding galactic nuclei, black holes and matter-antimatter annihilation are being postulated.
Thorstein Veblen once commented, “The outcome of any serious research can only be to make two questions grow where only one grew before.” ("Thorstein Veblen") This is especially true in particle physics and astronomy. Though the neutrino guides us in the odyssey of comprehending the physics of the Sun, stellar collapse, even dark matter and the Big Bang, the particle itself remains elusive as ever. A researcher at
References:
Alpert, Mark. "The Neutrino Frontier." Scientific American Aug. 2006: 20-22.
Close, Frank, Michael Marten, and Christine Sutton. The Particle Odyssey: a Journey to the Heart of Matter. 2nd ed.
Hofstadter, Richard, and Schwarz, Cindy. "Neutrino." Microsoft® Student 2007 [DVD].
John G. Learned, "Neutrino astronomy", in AccessScience@McGraw-Hill, http://www.accessscience.com, DOI 10.1036/1097-8542.757595, last modified: February 3, 2004.
John N. Bahcall, "Solar neutrinos", in AccessScience@McGraw-Hill, http://www.accessscience.com, DOI 10.1036/1097-8542.633600, last modified: January 4, 2005.
"Neutrino Astronomy." Microsoft® Student 2007 [DVD].
"Thorstein Veblen." Microsoft® Student 2007 [DVD].
Yoichiro Suzuki, "Neutrino", in AccessScience@McGraw-Hill, http://www.accessscience.com, DOI 10.1036/1097-8542.450700, last modified: August 2, 2002.
Tuesday, May 20, 2008
Caustics and Parametric Curves
Circle Catacaustic (Courtesy of Wolfram MathWorld)
If you have ever stared at a cylindrical glass of water sitting on table on a sunny day, you might have seen an intricate geometry of filaments of light projected onto the table behind the glass (in the direction away from the sun). This is called the caustic of the glass.
What exactly is a caustic? It is the envelope of rays from the reflection (catacaustic) or reflection (dicaustic) of light from an object. Actually the projected envelope from a glass is a nephroid (arising due to the differential equations involved) or a kidney-shaped object (see etymology).
It was this trivial experience, seeing something magical in a glass that started my obsession with optics/photonics. It also introduced me to the wonderful world of parametric curves, like the nephroid.
Parametric curves are interesting because they arise from very simple physical constraints (e.g. minimized degrees of freedom, path of least time, etc.). Consider the following problems:
Brachistochrone Problem
http://mathworld.wolfram.com/BrachistochroneProblem.html
Tautochrone Problem
http://mathworld.wolfram.com/TautochroneProblem.html
Other parametric curves such as involutes have important applications in engineering such as gears (so that a pair of gears mesh perfectly).
http://en.wikipedia.org/wiki/Involute_gear
Fun with Cryptography - Cyptoquip
The basic premise of this puzzle is a simple plaintext encoded using a substitution cipher, of which one letter clue is given (i.e. Today's Clue: L equals S). Using this clue and the properties of the message itself, you must solve the puzzle. It requires some logic, some intuition and also quite a bit of luck (so be patient).
Strategies:
Look for one-letter words (they have to be "A" or "I")
Look for common three-letter words (i.e. "THE")
Use hyphenated words, exclamations and quotations to your advantage (e.g. a quotation may be preceded by a word like "SAY")
Cross-check your guess letters in multiple locations, when possible.
With a little practice, you can become a skilled code-breaker. The punny messages are great fun to crack and I have to say that I am already addicted.
197 free Cryptoquips can be found here: http://www.cse.ucsd.edu/~mstepp/cryptoquip/crypto.html