Ray Tracer in Python (Part 3) - Show Notes of "3D Balls in 2D Space"

    Graphics is what made Mathematics enjoyable for me. I first heard of trigonometric functions like sine and cosine when I read GW-BASIC manual. Geometry was easy to visualize with the rudimentary graphics of LINE and CIRCLE statements. While I could see many struggle with Mathematics, I always found it interesting.

    So my challenge was to make this math-heavy episode interesting so that you see how I see it. I needed to give personalities to Ray and Sphere before I could show their intersection formula. This needed a lot of illustration and animation work. But I believe the end result was worth it.

    This time there is a lot of furious typing and less talking because of the number of lines entered in this part. I did not want to fast forward code writing segments because it doesn’t help the learners. In any case, YouTube can speed up videos if you choose to.

    These are the topics we will cover in this episode:

    • Introduction
      • Why meshes in movies and spheres in raytracers
      • Simplified ray-tracing
      • Ray-sphere intersection
      • Aspect Ratio Corrections
    • First sub-problem: 3D Balls in 2D Space
    • Coding the solution
      • Hex colors
      • Classes for Engine, Ray, Sphere, etc.
      • Rendering Algorithm

    Here is the video:

    Code for part three is tagged on the Puray Github project

    Bonus (Traffic Lights) Code is available for download.

    Show Notes

    Books and articles that can help understand this part:

    Note: References may contain affiliate links

    Comments →

    Ray Tracer in Python (Part 2) - Show Notes of "Revealing the True Colors"

    It is always a good idea to create a visible output at the start of a long project. If you are making a game, start with showing something moving on the screen. It keeps you motivated and gives you something cool to show your friends as progress. In the second part of our ray tracer tutorial, I will introduce you to PPM a very simple image format that will be used for our renders. You don’t need to install any image libraries and yet PPM files can be read by most image viewers.

    The color class is a lot simpler than what I originally designed. Features like gamma correction and linear interpolation seemed like an overkill for a project like this. But I plan to add some convenience constructors later. Hopefully, this will be a good introduction to how colors are manipulated in computer graphics.

    These are the topics we will cover in this episode:

    • Introduction
      • Compressed Image are Hard
      • What Images are Made of
      • RGB triplets
    • First sub-problem: Revealing the True Colors
    • Coding the solution
      • Use the shebang line
      • Separate classes in separate files
      • Why fileobj instead of filename?

    Here is the video:

    Code for part two is tagged on the Puray Github project

    Bonus (Gradient) Code is available for download.

    Show Notes

    Books and articles that can help understand this part:

    Note: References may contain affiliate links

    Comments →

    Ray Tracer in Python (Part 1) - Show Notes of "Points in 3D Space"

    I’m really excited to start a new video tutorial series on creating a ray tracer from scratch. This a set of intermediate-level Python tutorials. Recently realtime ray tracing became a hot topic in the gaming community after various Minecraft Ray tracing videos started popping up. Of course, you need a monster of a machine to get decent framerates. However, we will be making an non-realtime ray tracer entirely in Python.

    These are the topics we will cover in this episode:

    • Introduction
    • Who should watch this tutorial?
    • What will you cover?
    • Ray tracing in a Nutshell
    • Getting Familiarized with my Emacs
    • First sub-problem: Points in 3D Space
    • Coding the solution
      • TDD (Test Driven Development)
      • Data Structures
      • 3D Vectors

    Here is the video:

    Code for part one is tagged on the Puray Github project

    Show Notes

    Books I recommend for learning Python:

    Some links to learn the Vector math I cover, in more detail:

    Note: References may contain affiliate links

    A Dream Forever in Making

    I have been forever interested in Computer Graphics since creating computer games is what really got me interested in programming (or “coding” as it is the fashionable term now). In early days, ray traced images used to blow my mind compared to the blocky graphics that 3D games generated.

    But trying to learn the algorithms was frustrating for two reasons - the mathematics seemed too dense and it took a really long time for each render. In 2015, I spent a weekend playing with various algorithms to create a simple ray tracer in Python by heavily leveraging NumPy.

    I felt the NumPy parts looked “un-pythonic”, so I reimplemented it without NumPy. It hit a sweet spot between functionality and readability. You needn’t be a math guru to figure out how it worked. I had to share what a learnt not because there was a lack of ray tracing tutorials but I wanted to make an accessible tutorial with gentle learning curve.

    However the process of creating video tutorials have changed over the years. Gone are the days of a simple screen recording or screencasts. Now we have to have slick intros, animations and click-baity thumbnails with a face overlay having a shocked expression. But honestly I am in awe of how much time people spend on making each video (it is way, way more than you think) and how frequently they make them (“new video every week”).

    The challenge is even harder when you need to break down all that math and physics behind computer graphics into simple concepts in a logical flow. That also takes way more time than you would expect. Sometimes you find that one clear diagram would explain an idea perfectly but nobody has made one so far so you need to draw a fresh one. Or you need to cut down your explanation because listeners are getting lost in the details. Plus your real life slows you down with work deadlines and goof ups like out of focus video recordings. This process of iterating until my script (and code) became streamlined took me months.

    My approach has always been about posting higher quality stuff at low frequencies. So I am happy if the end result was worth the wait (and I hope it is). This could be a tutorial that might outlive many of my other videos and that is satisfying in itself. Hope you’ll enjoy this journey with me as much as I did.

    Check back for part 2 (EDIT: it is out)!

    Comments →

    Black Holes and Python

    Black Hole at the center of M87 Galaxy
    Black Hole in M87 - Image Courtesy: BBC

    The first picture of a black hole is probably one of the most exciting developments in the world of science. The blurry ring of fiery orange might not seem difficult to produce. In fact, it involved years of effort by an international team of scientists, including computer scientists.

    Reading the account, I am excited about the role Python played in this endeavour. This is interesting because when we talk about a scientific discovery we usually talk about the people - the scientists who made leaps of intuitions and found correlations that no one else had. But increasingly technology is playing a significant role in discoveries by sifting through enormous amounts of data and extracting valuable insights.

    Python’s popularity in the scientific computing would not be a surprise to most Python programmers today. But back in 2009 when I attended the first PyCon India in IISc Bangalore, I was surprised to see talks on experimental Physics and fluid simulations. When I asked Prof Prabhu on why Python is so popular in scientific computing, he said “it is very accessible to us – non-programmers”.

    Casually browsing through the software used by the astronomers, you will find mentions of Python libraries like Numpy, Scipy, Matplotlib, Pandas and Jupyter. Remarkably, entire projects such as eht-python are written only in Python. Python is not just the language of choice, it is the lingua franca of scientific computing.

    Yet, if you think about it, there are better programming languages be it in terms of - speed, type safety or brevity. But Python overcomes these limitations and sometimes succeeds due to some pragmatic language design decisions.

    Speed Can Be Delegated

    Ironically, plain Python code can perform very poorly for computation intensive tasks. But libraries like NumPy are de facto when it comes to any form of number crunching. It provides an N-dimensional array object with several high level operations like cross product or transpose. The C engine of the library accelerates these operations close to raw machine speed.

    In the early days of Python, it was expected that performance intensive parts would be written in other languages like C or FORTRAN and a wrapper interface would be used to invoke them. Over time, wealth of libraries like NumPy made it unnecessary to write any custom C code. Why reinvent the wheel when you can just “import” and use it?

    Libraries that Play Well

    Obligatory XKCD 353
    import gravity - Obligatory XKCD 353

    Working with third party C libraries is not for the weak hearted. In 2002, when I was adapting the algorithm in a paper for my project on wavelet-based image compression, I learnt this the hard way. We needed to use an existing Fast Fourier transform library written in C.

    The library worked when you used it as is. But if you tried to extend a data structure, you might end up with a null pointer exception. Manual memory management by working out all the code paths turned out to be very stressful. The library was well documented but we practically needed to understand every line before tweaking it.

    Eventually, we gave up and started implementing most of the project in Python. It was much easier to work with higher level data structures like dictionaries and lists without going through the dance of malloc and free. Even better, the Python code was pretty much a direct translation of the mathematics in the paper to code.

    Python libraries tend to compose quite well (while C libraries don’t). This is partly due to its dynamic typing and automatic memory management, but I personally feel it is mainly due to good conventions. Most of the Python idioms are well documented and this leads to minimum surprises. For instance, a deeply nested class hierarchy is frowned upon because “flat is better”.

    Interactive Exploration

    Research is explorative. We not know what we may find. Even if we do, we cannot wait for ages to find out because we might be chasing a dead end. An interactive interface is a key tool for a researcher or scientist. A Jupyter notebook is close to the ideal with its live code and embedded visualization abilities.

    If you need to try a computation with a different set of parameters, you can invoke it and view the results. Even plot it to visualize it better. Then you could take the results and feed it to another computation. This recorded transcript is a valuable data pipeline that can be replayed by a different user for verification or with a different set of observations.

    If you think about it, a conversational interface could be more approachable to a non-programmer. Alan Kay was very impressed with an early interactive programming environment called JOSS developed in RAND that appealed to economists. I find it endearing that it replied to any command it did not understand with a “Eh?” or “SORRY”.

    Imagine using today’s voice recognition technology to build such a conversational virtual assistant for scientists. Considering much of science (especially physics) involves mathematics – spelling out complex equations can quickly get tedious. Listening to tables of numbers is no fun either. So unless the conversation steps up with an amazing level of artificial intelligence (imagine a reply like “I have run simulations on every known element, and none can serve as a viable replacement for the palladium core."), we are probably stuck with current interfaces.

    Future of Python

    Katie Bouman
    Katie Bouman, one of the key contributors, with the amazing amount of data

    M87 EHT project involved processing petabytes of information (which is publicly available). They plan to add new telescopes in the future, increasing the volume of data by orders of magnitude. In general, the computational demands of science will keep growing and even enter new domains. The question is - will Python keep up or get replaced?

    Python has a strong ecosystem with hundreds of libraries. It will be hard for another language to reproduce that. It is a very easy language to pick up. The readability is so good that Python code is often compared to pseudocode. I believe, it has changed the expectation of how code should look like. Any new language should have equal or better readability to inspire a switch.

    While there are several other promising languages like Julia or Rust, I am confident that Python will remain the scientist’s favourite programming language for a long while. Despite its limitations, Python has found a sweet spot between ease and power.

    Every year technological progresses keeps accelerating. This can translate into progress for humanity if we can make technology more accessible. We need physicists, mathematicians, biologists, economists, farmers and so on to use cheap computing power to build better things.

    Python does play a significant role by making coding less intimidating and more collaborative. That’s why I believe you will see it in bringing more people to computers and being a part of more future breakthroughs.

    Comments →

    Punchscript - A Rajinikanth Inspired Programming Language

    If you could design a new programming language, what would it be like? A question I had ever since I took the Programming Languages (PL) course in the third year of my Computer Science Engineering way back in 2001. For the first time, I have an answer – Punchscript.

    Punchscript is a programming language made up of punch dialogues by the Indian moviestar Rajinikanth. Punch dialogues are more punchlines than dialogues, delivered in Rajini’s inimitable style in the form of an aphorism or a retort.

    ![Cool Raking scene](/static/images/blog/punchscript/oru-thadave.gif)
    Rajinikanth in Baashha (1995)

    Here is how the customary Fizz Buzz looks like in Punchscript:

    Code Screenshot

    Punchscript works with only signed integer datatype. So instead of boolean logic operators, you’ll need to use integer arithmetic logic. Also, it supports only IF… ELSE rather than the IF… ELSEIF… compound statements. Notice how these limitations are worked around in the code above.

    You can try Punchscript in your browser and run various examples. Despite its limitations, you can write all kinds of non-trivial algorithms. It is Turing Complete, like most languages. So any computation can be performed it it. But I would not recommend betting your next startup on it.

    Chasing the Camel

    Remember my PL course of 2001? Among the half a dozen languages we read about, one language stood out as both elegant and practical. That was - ML (ML stood for Meta Language long before some smart guy recently called it Machine Learning). We learnt Standard ML at that time but even then OCaml was much more popular.

    Then, year after year, nearly every ICFP functional programming contest had OCaml mentioned by one of the top three winners (the trend changed in recent years). The syntax seemed easy enough and I could pick it up in a few days. After a while, I would completely forget about it, get interested in ML again and have to re-learn the whole thing. I have tracked this sisyphean task of learning OCaml in a decade old journal on Google Docs.

    Eventually, I realized I need to do something significant in OCaml. Now which programming problem would be of a moderate size and can be ideally solved in OCaml? The obvious answer was a Compiler (with Ray Tracer being a distant second). The language is excellent at manipulating algebraic data types which is perfect for abstract syntax trees. Even more, the js_to_ocaml tool helps you convert the implementation to Javascript, so that your compiler can run in the browser!

    Now comes the question of which language to implement.

    Why this Kolavari?

    It is way more fun to design your own programming language than to implement an existing one. You start by thinking what new syntax you can come up with.

    I thought - syntactic elements should be short and memorable like… punchlines. A bit of a stretch but sounded like a fun project. Rajnikanth movies seemed to be a goldmine of punch dialogues, with most movies having, at least, one.

    It took a lot of binge watching research to find the best phrase for a loop or condition statement. I learnt Tamil by the ear so it is not perfect. But I must say that inventing a new language from scratch is both demanding and rewarding.

    The hardest part is to select the least amount of syntax while still being useful. It is really tempting to assemble all the favourite features from other languages, but then your project would never get shipped. And as we know, shipping is the most important feature.

    The actual implementation took me 4 to 6 weeks (working mostly weekends including combing through user manuals of OCaml tools). Along the way, there were so many decisions to make, like:

    • Whitespace significance
    • Data structures
    • Compiled or Interpreted
    • Functions or procedures
    • Virtual Machine or direct AST execution

    Funnily enough, I often picked the the third choice of YAGNI. If we can live without a feature, leave it. This not only made the implementation easier but the language more elegant.

    There are so many way to set up an OCaml development environment. I’ve setup up all the modern OCaml tools needed in a Docker container. Keeping everything in Docker makes it easier to manage and reproduce.

    Opening the Toolbox

    The best instructions for setting up a modern OCaml development environment can be found at the Real World OCaml book’s site. The first step is to install Opam – OCaml’s package manager plus isolated environment manager (sort of like Python’s pipenv).

    I started by creating a Docker file based on the opam:alpine_ocaml image. You will need to reproduce the installation commands in the Dockerfile. The only change I made was installing using opam depext instead of opam install, so that external dependencies are installed.

    Next, we need to install OCaml’s compiler building tools - OCamlLex and Menhir. There is an excellent chapter on Parsing in the Real World OCaml book which is a good introduction to using these tools. If you are familiar with YACC and LEX from other programming languages like C, it should be like meeting an old friend.

    Then I went ahead and installed Emacs as well. This is because Emacs needs to call OCaml for its OCaml mode tuareg to work properly. I found this to be extremely convenient to have a self-contained development environment although Docker purists might prefer it to be separate.

    Make sure you are using Dune (previously called JBuilder) for building the project. You will probably still need a Makefile. Most of Punchscript is organized in a library, which can be built into bytecode or Javascript targets.

    Read Issu’s recent post on OCaml Best Practices, if you are interested in an overview of modern OCaml development tools.

    Learning the Mystical Arts

    Setting up everything right might take a while, but that’s only the beginning. There is a ton of resources to writing a compiler or learning OCaml. But hardly any about making a compiler in OCaml.

    Here are some books and articles which really helped me:

    • If you are novice then I would recommend reading OCaml from the Very Beginning.
    • If you are already familiar with OCaml (like I was), then I would recommend reading the OCaml User Manual, available in many formats for offline reading (I wish they had an EPUB too for Kindle readers).
    • If you want to learn or have forgotten compiler theory (what was LALR again?), then you can read Modern Compiler Implementation in ML, by Andrew W. Appel. Just Chapter 3 is enough to brush up on parser.
    • You ought to read the Mehir manual. The examples are extremely helpful.
    • The TOSS tutorial is great at explaining the entire toolchain.

    So you will need to read a lot of documentation to understand most OCaml tools. I know some get daunted by long manuals, but they are quite approachable. You just have to read some introductory sections and you should be good to go.

    Wiring up a Live Demo

    The fun part of the project was building a live demo for the web. The js_of_ocaml tool converts OCaml bytecodes into compact Javascript code. It was surprisingly small. The entire Punchscript interpreter is a single file weighing just 29K gzipped (132K minified)!

    The interpreter is invoked from the page using Web workers. There is something magical about watching a web page interact with your OCaml program synthesized from an almost sterile world of functional programming. Web workers makes the whole interaction asynchronous. No browser hangups while your code is running.

    ![Cool Rajini scene](/static/images/blog/punchscript/robot-hand.gif)
    Rajinikanth in Enthiran / Robot (2010)

    I always wanted the examples to have proper syntax highlighting in Punchscript. I used CodeMirror to build the code editor. Writing a custom syntax highlighter seemed to need a lot of Javascript code. So I heavily derived from the Python syntax highlighting mode.

    Taking it Further

    Punchscript is both a language and an implementation. Both have potential to grow. Language specs are public and new punch dialogues are welcome. You are also free to create your own implementation in your favourite language. I would be happy to link them.

    Have fun coding with punch dialogues!

    Thanks to Deepak and Ramakrishnan for reviewing the early drafts of the language specs.

    Comments →

    « Newer Page 2 of 38 Older »