November 16, 2017

Computational Geometry - Part 1

0 comments
I've spent some time studying an area called Computational Geometry, which according to Wikipedia is "a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry." Examples include: Are two lines intersecting? How can you triangulate random points? If you are interested in the area, the best book I found was Computational Geometry: Algorithms and Applications. The algorithms I've studied are:

Find the convex hull of random points. If you have some points and you want to find the smallest possible area that includes these points, then you need to find the convex hull of those points.



Triangulate polygons. If you have a convex polygon or a concave polygon, how can you triangulate them? 



Triangulate points. If you have random points, how can you triangulate those?



Delaunay triangulation. If you look at the images above, the triangles look kinda odd. To improve the triangulation you can use an algorithm called Delaunay triangulation.


Voronoi diagram. If you run a stores in different cities, then you can create a Voronoi diagram to find out where those customers live that live the closest to a specific store.


That's it for part 1. Next part will include boolean operations on polygons!

November 11, 2017

Books about engineering you can read on the beach

0 comments
Engineering is fun and it's also fun to read about other engineers so you can learn something from their mistakes and find inspiration. Engineering is also about math, physics, etc, but this is a collection of books without any math that you can read on the beach. So leave your calculator behind!


A Thread Across the Ocean: The Heroic Story of the Transatlantic Cable. One of the big engineering projects that took place in the 1800's was to connect Europe with America by dragging a 2500 tonnes heavy telegraph cable from one continent to the next. If that was possible, it would take just a minute to send information between the continents, compared to the weeks it took to send the same information with a ship. How this was possible is explained in the book.

Structures: Or Why Things Don't Fall Down. I've always been fascinated by those engineers who worked without calculators. How could they build a ship like Titanic without computers? This book will tell you the history of how to engineer buildings, bridges, ships, and much more.

Fermat's Enigma: The Epic Quest to Solve the World's Greatest Mathematical Problem. Math and engineering are deeply connected. This book will tell you the story of when one guy tried to prove Fermat's last theorem. It will also tell you the history of mathematics.

Clouds of Glory: The Life and Legend of Robert E. Lee. This book tells the story of one of the famous generals from the American Civil War. But little is known that Robert E. Lee was also an engineer, which is maybe the reason he was successful as a general? The book includes a lot about the war, but also about the engineering challenges to build a fort and change the flow of a river.

Wizard: The Life and Times of Nikola Tesla: Biography of a Genius. Nikola Tesla was a famous inventor, and one of Elon Musk's role models, but the problem was that he never made money from his inventions so he died poor. This book will teach you why great engineering is not the end goal - make money is always the goal.

The Martian. What if you are on Mars, then an accident happens which forces your team to leave you behind, so you have to survive with what you have until someone can rescue you? This is of course a made up story, but the author worked as an engineer before he began writing books so the book is realistic.

Alan Turing: The Enigma. One of the great engineering challenges during the Second World War was to break the German codes. He wasn't alone, but one of the persons who accomplished this was Alan Turing, and this is the best biography on him.

Moon Lander: How We Developed the Apollo Lunar Module. It might have been difficult to drag a telegraph cable across the Atlantic Ocean without the help of computers, but what if you want to land on the Moon with only primitive computers? This book is written by the engineer who was responsible for designing the vehicle that actually landed on the Moon, so you will learn all about it.

The Quest for Artificial Intelligence. Artificial Intelligence or smart computers are becoming an increasingly larger part of our life, such as self-driving cars. The area is actually not new, people have always tried to build smart machines, and this book will tell you all about it.

The Innovators: How a Group of Hackers, Geniuses, and Geeks Created the Digital Revolution. This book will tell you the history of the computer - from the first attempt to build a calculator up to the guys who designed Google. It is written by the same author who wrote the best Steve Jobs biography, so you should read both!

The Boy Who Harnessed the Wind: Creating Currents of Electricity and Hope. What if you grew up in a poor place in Africa and decided you wanted to help the community to get electricity. This book will tell you how William Kamkwamba built a wind turbine from scrap.

Skunk Works: A Personal Memoir of My Years at Lockheed. One of the most recognizable planes is the F-117 which was the first plane that was hard to detect on a radar - a so called stealth fighter. This book is written by one of the engineers who built that plane and other innovative aircraft at the company Skunk Works.

Masters of Doom: How Two Guys Created an Empire and Transformed Pop Culture. One of the most famous computer games is Doom, and this book will tell you the story of how Doom was created.

And finally some shameless self-promotion. If you have read all books about engineering you should also read my book about engineering, which is a biography on Elon Musk: The Engineer: Follow Elon Musk on a journey from South Africa to Mars.

November 4, 2017

Would Leonardo da Vinci have streamed his work online?

0 comments
Television is 20th century technology and the new way to consume entertainment is to watch streamers on services like Twitch. A streamer is someone who is showing him/herself through a web camera while the person is doing something like playing a game, drawing a picture, or even looking for zebras in South Africa. Why? Traditional television has a broader audience, so the television shows tend to become kinda dull. Watching a stream on Twitch is more personal and you can even interact with the person through a chat. Streamers are also calming background noise, and I was listening to an art streamer while writing this article.

But watching someone else doing art is not something new. I've recently read a biography on Leonardo Da Vinci, written by Walter Isaacson - the same author who wrote the official Steve Jobs biography. He has also written a biography on Albert Einstein, and I've read all three of those books. In the book on Leonardo da Vinci, it's revealed that people were watching him when he was doing art, while he was saying "Drawing in company is much better than alone."
When Leonardo da Vinci was painting The Last Supper, spectators would visit and sit quietly just so they could watch him work. The creation of art, like the discussion of science, had become at times a public event. According to the account of a priest, Leonardo would "come here in the early hours of the morning and mount the scaffolding," and then "remain there brush in hand from sunrise to sunset, forgetting to eat and drink, painting continually." On other days, however, nothing would be painted. "He would remain in front of it for one or two hours and contemplate it in solitude, examining and criticizing to himself the figures he had created." Then there were dramatic days that combines his obsessiveness and his penchant for procrastination. As if caught by whim or passion, he would arrive suddenly in the middle of the day, "climb the scaffolding, seize a brush, apply a brush stroke or two to one of the figures, and suddenly depart."

Here are some other lessons learned from the book on Leonardo da Vinci:
  • You have to observe the real world and this is more important than learning from someone else:
    • If you look around you, you will not see any sharp lines, so why should you paint using sharp lines? "Paint so that a smokey finish can be seen, rather than contours and profiles that are distinct and crude."
    • Use shadows, not lines, and this is the secret to modeling 3d objects on a 2d surface. Leonardo da Vinci spent more time studying shadows (and thus light) than he did on any other artistic topic.   
    • Leonardo da Vinci took this one step further by dissecting human bodies to really learn how to make better paintings. Art and science is interwoven. If you paint someone, you should begin with the skeleton, then the skin, and finally add the clothing.
    • Study the movement of bodies. Many say that Leonardo da Vinci's characters are moving, and he said that "movements should announce the motions of the mind." If he met someone on the street with an appearance he wanted to study closer, he invited the person over for supper. 
    • To remember all observations, he always brought a notebook with him. In these books he wrote what he observed and what he wanted to observe, such as "Describe the tongue of the woodpecker."
  • He failed a lot. In some cases it could take 20 years before he finished a painting, and in some cases he never finished a painting he was working on. Leonardo da Vinci wanted is art to be flawless, so he could never finish them because they were so complicated if you took the lighting into account. In one case he had to dissect a body to learn how a muscle worked before he was satisfied with the painting.
  • Combine fantasy with observation. Leonardo da Vinci is famous for coming up with futuristic machines, like helicopters and tanks. But it turned out most of these machines were not meant to function because he created those machines for theatrical plays. If you want to draw a dragon, it's easier to combine parts from other animals, like the head from a dog, the eyes from a cat, the ears from a pig, and so on.
  • Procrastinate is not always bad. Leonardo da Vinci was having a discussion on how creativity occurs. Sometimes it requires going slowly, pausing, even procrastinating. "Men of lofty genius sometimes accomplish the most when they work least for their minds are occupied with their ideas and the perfection of their conceptions, to which they afterwards give form."

October 1, 2017

Evil pumpkins - or how to simulate subsurface scattering

0 comments
If you are making a game, it's really important that the game looks good and that the game runs as fast as possible on the computer. It's often difficult to achieve both good looks and speed, so you have to cheat by using various tricks. One of the cheats I read about was how to achieve fast subsurface scattering in Unity. The idea behind subsurface scattering is that light tends to shine through some materials. For example, if you are holding up your hand against a strong light source, you will see that some of the light shines through you the edges of your fingers. To implement this effect I decided to make a Halloween pumpkin.

I began by making a pumpkin sculpture in Blender.


Making a sculpture in a 3D software is not that far from using physical clay. This is why the technique has become popular because it's easier to model something in clay than by adding triangles one after the other. The most popular sculpt software is ZBrush, but Blender has a sculpt part which is also working fine. The problem with a sculpture is that it consists of far too many triangles so it will fail if you put it in a game:


The solutions is that we once again have to cheat by making a less complicated model on the top of the more complicated model. This process is called retopo. The less complicated version looks like this:


But this less complicated version is kinda ugly. To make it look better we can use the more complicated version and "bake" normals and ambient occlusion, which is again a cheat to make an ugly model look better:


...and now it's just a matter of adding the subsurface scattering materials to the pumpkin, and it will look like this:


July 24, 2017

This self-driving car is now faster with the flow field algorithm

0 comments
So I've made a self-driving car in Unity. The car is using the Hybrid A* pathfinding algorithm along with other algorithms to find its way around a confined area, such as a parking lot. You can test it here or here. The old version was working fine, but one can always improve. The updates in this version are:
  • Added lines showing the waypoints 
  • Fixed a bug where the wrong value was added to the sum or errors in the PID controller, so the car is now following the path much better 
  • Added a cost for switching driving direction, like forward -> reverse, because it would be annoying to sit in a car that constantly is switching driving directions
  • Fixed a bug where the smooth path algorithm optimized the distance to obstacle in 3d space and not 2d space 
  • Added an improved obstacle-intersection algorithm which is faster and more accurate. It's now using rectangle-rectangle intersection instead of circle-circle intersection
  • Added UI where you can display the grid and the flow field 
  • When optimizing the final path, it's now optimizing the distance to the average of the surrounding obstacles and not just the closest obstacle 
  • Cleaned up the code
  • Added flow fields as heuristic and for obstacle detection, which makes the pathfinding much faster 
  • Made so that the Hybrid A star can expand to a cell if this expansion has a lower cost than previously
  • Improved path following so the car is slowing down gradually before it reaches the end or a turning point such as "reverse -> forward". Previously you could often see how the car crashed into walls because it was driving too fast

This is the flow field the car is using to faster detect if it's colliding with an obstacle:


The area is divided into cells, and the darker the cell is, the further away it is from an obstacle. So if you want to check if a car is colliding with an obstacle while generating the path, you can see in which cell it is and see how far away from an obstacle it is. If it can't possible be colliding with an obstacle, then it's not colliding with an obstacle and you don't need to use a slow rectangle-rectangle intersection algorithm to check if it's colliding with an obstacle.

Update 2017-07-26
I realized that a good idea might be to close cells depending on the heading the car had when entering the cell. So the car can drive to the same cell even if it is closed if it hasn't arrived to that cell before with the same heading. The result looks like some abstract art:


...but the algorithm is now finding more solutions and the car can even turn around on its spot. The problem is that sometimes this solution is much slower, so maybe a combination between the slow and the faster algorithm can be used?