Category: "C++"

Quad(copter) of the Damned

C++, engineering, embedded Send feedback »

This post introduces the concepts and vocabulary related to quad-copters, and overview of what is involved from an embedded software perspective to build one of these flying contraptions. Progress will be documented as incremental steps in posts that follow.

Introduction

As part of my coursework in the pursuit of a Masters degree in Cybersecurity I took a course called Software Engineering for Real-Time Embedded Systems. The course focused on the concepts and challenges that are encountered when developing software for systems that have hard real-time deadlines for the system to function properly. The homework was a series of projects that led up to the development of a quad-copter with streaming video.

Many of the developers that I follow on Twitter have asked for resources on how to get started with embedded development. I thought this would be a great project to build and document the process for those of you that are interested in learning what is required to create one of these machines. I plan to build a general-purpose drone that is suited for aerial-photography with longer-than-average flight-times. However, the software that I develop can be adapted to all types of multi-rotor air-vehicles. This means that by changing the components such as frame and motors, you could easily build your own drone suitable for FPV racing.

There are plenty of pre-built and DIY (do-it-yourself) kits available to amateurs and enthusiasts. If I simply wanted to fly model aircraft I would purchase one of these kits and I wouldn't be writing this series. My chosen career is Software Engineering and it just so happens that is also my hobby. While I will be using the same components found in the DIY kits, I will be foregoing the flight-controller. Instead, I will be designing and documenting my journey as I develop this controller and integrate it with the drone. If you aren't interested in writing your own flight controller from scratch, you can still build a drone based on an embedded controller and use the open-source software Ardupilot. This development for this software is definitely active and contains support for many different types of air-vehicles. Alternatively, you could purchase a flight controller circuit-card that has all of the required functionality built into the hardware.

I will definitely cover all of the software aspects required to build a drone for yourself. I also plan to write some entries that will be of interest to you if you are interested in embedded development. For example, reading component data sheets, setting up interrupts and other aspects important to real-time embedded development.

What is a Quad-copter?

A quad-copter is considered a multi-rotor air-vehicle. Other common multi-rotor configurations include 3, 6 and 8 rotors. Four rotors provides a relatively stable configuration that is symmetric and won't be as expensive as the 6 or 8 rotor configurations.

There are two other types of radio-controlled air-vehicles common with hobbyists.

  1. Fixed-Wing (Airplanes):

    These are relatively efficient craft that allow for much longer flight times. However, they typically require a large amount of setup/teardown time when moving to the flight zone, and these craft require large open areas where the craft can maintain constant forward momentum to create lift over the wings.

  2. Rotary Wing: The Traditional Helicopter

    This is a single-rotor aircraft. The flight direction is controlled by changing the attitude of the main rotor and a secondary tail rotor is required to counteract the gyroscopic rotation caused by the primary blade.

Gyroscopic Rotation

I mentioned that a traditional helicopter requires a tail-rotor to counteract the gyroscopic rotation introduced by the primary blade. A quad-copter is subject to the same forces as its rotors spin. To counteract this effect, we will spin two of the motors clockwise and the other two motors counter-clockwise. At this point I do not know if it matters which motors that we command to rotate in each direction. Unless I find a definitive reference or someone comments with the definitive answer, this seems like something worth experimenting with when I reach that point.

This is the rotation configuration that we will start with as we work towards the final quad-copter:

Rotation Orientation
Rotation Orientation

We will alternate the direction of rotation for each motor

How does a quad-copter change direction?

The four rotors on a quad-copter allow for a relatively stable and very maneuverable aircraft. A quad-copter has 6-degrees of freedom in movement, 1) up, 2) down, 3) left (port), 4) right (starboard), 5) forward, and 6) backwards (aft). Additionally, the craft is also capable of hovering in-place and rotating in both the clockwise and counter-clockwise directions.

Attitude

A different set of terminology is used in navigation of ships and aircraft, and I will be using these terms moving forward.

Thrust

This describes the overall rotation speed of the rotors. Thrust adjusts the relative speed of each rotor equally. Therefore, if the thrust is increased, the speed of the rotors will increase and the air-vehicle will ascend. Alternatively, if the thrust is decreased the air-vehicle will descend. Assuming the air-vehicle is in the air, if the thrust is left at a steady neutral position, the vehicle will hover in place. This will require the calibration and selection of the hover level for thrust. The hover level is the neutral thrust level.

Roll

This causes the craft to rotate either to the left or the right. This rotation will cause the drone the move to the side as well. To introduce this motion the two rotors on the side in the direction of the roll should be reduced, while the rotors on the opposite side are increased.

Pitch

This causes the craft to move forward or backward by rotating the orientation of the craft. Again, to introduce this motion the rotors on the opposite side of the desired direction of movement should be increased.

Yaw

This is the rotation of the craft around the vertical access. The gyroscopic forces of the spinning rotors are used to control this aspect of flight. Two of the rotors spin clockwise and two spin counter-clockwise. Increasing the speed of the clockwise motors relative to the counter-clockwise motors will induce a force that causes the craft to yaw to the right (clockwise). The craft moves in the opposite direction when the rate of the counter-clockwise motors is increased relative to the clockwise motors.

Components

The list below contains a description of the components that are required to build a basic quad-copter / quad-rotor. I have also included the parts that I am using for my build.

Frame

There are many types of frames, built with a variety of materials such as wood, plastic and carbon fiber. It is important to get a frame that is light and well-balanced. I chose to work with the Tarot - IronMan 650, which is built from carbon fiber. This frame collapses easily to make it more portable. It has a solid core with two plates to protect the internal components. This frame was about 100 dollars. It is a larger frame, so it is not suited for FPV-racing. I am more interested in developing a platform that I can additional sensors to perform interesting tasks remotely.

Tarot IronMan 650
Tarot IronMan 650

Motors

Multi-rotor copters typically use outrunner type motors because of their high efficiency. Outrunners are a type of motor where the internal coil is mounted fixed and the entire brushless outer bell-housing rotates with the shaft, attached to the propeller. Motors are rated by a unit represented as KV. This means Kilo-rotations / Volt. Typical batteries run at 12 volts. Therefore, the 1000KV motor would rotate at a top speed of 12000 RPM.

I selected the Turnigy - Multistar Elite 4006 740KV motor for my drone. This is a slower motor at 740KV that has a larger number of magnetic poles to produce more torque. I will pair this with a steeper pitch of propeller to create a drone that can handle a heavier payload with the additional sensors that I will eventually add. The specs for these motors indicate they are capable of handling from 10" to 17" rotors. To start with, I have selected 11" carbon-fiber rotors. If you are purchasing equipment to build your own drone, I suggest you order extra rotors. Because you will break a few before you attain stable flight.

Multistar Elite 4006 740KV
Turnigy - Multistar Elite 4006 740KV

Electronic Speed Controller (ESC)

The motors are ultimately controlled by an Electronic Speed Controller (ESC). They are colloquially called "Escapes". The motor is controlled by 3 input wires, which the ESC uses to adjust the voltage across the different wires to cause the motor to spin. The controller side of the ESC has two wires that the flight controller uses Pulse-Width Modulation (PWM) signals to signal the desired speed. I will elaborate on the ESC in later posts when I describe its integration with the flight controller.

Most ESCs are designed to support a single motor. These ESCs are attached to each arm of the multi-rotor so they can connect to the flight controller in the center of the frame, and the motor on the edge of the arm. A separate ESC is required for each motor. This electronic component is one of the most important elements of your drone. So don't go cheap on this component. ESCs are rated by the current that they control. I have seen ratings in increments of 5A and 10A. I would go one level greater than the rating of the battery that you plan to use. ESCs can support additional features to protect the other electronics in your system, such as a low-voltage protector for your lithium-polymer battery. These features are often programmable.

When searching for the ESC that I wanted to use, I discovered a 4-in-1 module that is installed at the center of the drone and supports up to 4 motors. This module also has a Battery Elimination Circuit (BEC) that can be used to power a 5 volt flight-controller. I chose the Q Brain 4x25A Brushless Quadcopter ESC. I wanted to simplify the circuitry that I would have to create for the drone. I am more interested in the software that plan to write than the physical circuits that are created.

QBrain ESC
Q Brain 4x25A Brushless Quadcopter ESC

Lithium Polymer Battery

The current drones are powered by Lithium-Polymer (Lipo) type batteries. They are very dense and can store quite a bit of energy. There are a few metrics used to rate these batteries:

Current Output Rate (C)

Lipo batteries are rated by the rate of current that can be drawn from the battery. This quality will be indicated with a "C" in the battery description. For example, a battery that is capable of sustaining a current of 10 amps will be marked 10C.

Total Stored Power (mAh)

The amount of energy contained in a fully charged battery is indicated in milli-amp hours (mAh). Smaller batteries may only contain 100 mAh, while the types of batteries used to control a multi-rotor drone store between 2500 mAh to 12000 mAh. This rating typically determines the amount of flight time you will get per charge. I don't know if there is a calculation to approximate your flight times. I will be sure to post it if I run across one.

Number of Cells (S)

Most entry-level drones uses batteries with 3 cells. When you read a batteries rating, it will indicate the number of cells with an "S". Therefore a 3 cell battery will be described as 3S. More cells generally means more stored power to provide longer flight times or support a stronger current draw.

I will be using a Turnigy MultiStar battery rated at 5200 mAh 4S 14.8V @ 10C. note: I couldn't find an image to match the rating of the battery that I purchased. (I also didn't look that hard).

Turnigy Battery
Turnigy MultiStar Battery

Inertial Measurement Unit (IMU)

This is the most important sensor on a quad-copter. This sensor is also found in smart phones. An IMU contains a collection of accelerometers and gyroscopes to deduce the orientation and current motion of your drone. The absolute orientation of the drone can also be determined by locating magnetic North when the IMU contains a magnetometer. All of these sensors are typically packaged into a relatively inexpensive MEMS unit and integrated on a circuit board. The processor board that I selected is designed for robotics applications and it contains an IMU. If you want to use a different processor board, you can pick up an inexpensive IMU from AdaFruit.

Radio Transmitter / Receiver and Controller

To control the drone, you will need a radio transmitter and receiver pair. The most straight-forward solution is to simply buy a RC controller from a hobby shop or online. The transmitter is typically a controller with a channel selector and joysticks. The radio receiver is a small component that integrates with the Analog-Digital Converters (ADC) of your processor board to read the signal levels for each control.

While I initially develop my drone, I am going to use a standard 802.11 wifi network that connects my tablet to the wifi radio in AP mode on the flight controller processor board. I capture the control inputs with an Xbox 360 controller. Using this method allows me to capture useful information and display it on a display on my computer on the ground while I am testing. This wifi link will also facilitate streaming of live video once basic flight is achieved. We can go back at any point in time and integrate support for a traditional RC controller if desired.

Flight Controller

This control board is the component that coordinates all of the information required to make a multi-rotor drone capable of flight. As I have already mentioned, many flight controllers exist and can be purchased just like all of the other components that I have mentioned. Except, that is not why we are here. We are going to explore the embedded world, and take on the challenge of developing our own flight controller.

I originally planned to use the BeagleBone Black. This is a very cool open-source prototype board that has lots of capabilities related to embedded systems development. It is very similar to the Raspberry Pi. The BeagleBoard runs an image of Debian Linux. I really enjoy working on these boards, because I can eliminate the need for setting up a cross-compiling toolchain. I compile the BeagleBoard's software directly on the BeagleBoard. I will add another post soon to help get you started with this platform.

Finally, this board requires a 5v power-supply. When I first assembled the drone, this configuration was great, in that I was able to use the 5v BEC from the ESC controller to power the Beagle board. But then...

I discovered the recently released (March 2017) BeagleBoard Blue. This is a version of the board is specifically designed for robotics applications. It contains an embedded IMU, and a wifi radio. This meant that I would no longer have to integrate those two components into the drone as they would be contained within this single board. However, this board requires a 12v power supply, or a 2 cell battery. I will be powering the flight controller with a separate 2 cell battery.

Beagle Bone Blue
Beagle Bone Blue

Summary

That covers the basic concepts of a quad-copter and hardware that I plan to start with. The next few posts will focus on getting started with the BeagleBone processor board and developing basic electronics projects. This will set the stage to integrate all of the components I described in this post. The final goal is to have a working quad-copter with supporting software that is ready to be expanded for custom purposes. The software will be available from GitHub. So if you are interested, check back soon. Follow me on Twitter to receive tweets when I post new updates.

Fundamentals of C++: Introduction to Templates

C++, knowledge, beginner Send feedback »

Recently I have been helping a colleague convert a series of painfully repetitive code segments into function templates and template classes. I respect this colleague very much and he is a very skilled developer, including the use of the C++ Standard Library. However, he has never developed any templates of his own. As I was helping him learn how to develop new templates it occurred to me that there are plenty of fundamental C++ concepts that are given very little attention. This creates an enormous gap in reference material to progress from the competent skill level to proficient and expert levels.

Therefore, I am going to periodically write about fundamental concepts and how to actually apply them to your daily development. This post discusses templates at a very basic level. Entire books have been written about them. I will revisit with more sophisticated applications of templates in the future.

Full story »

Steganography

C++, Alchemy Send feedback »

A software library provides no value if it does not simplify the task of creating your application. At the very least we would like to show that the library contains all of the tools required to complete the intended goal. Ideally, the library is complete, easy to use, and is efficient. The only way to learn how well the library is designed and implemented is to use it.

Furthermore, it is useful and sometimes necessary to provide an exemplar for others to see how the library is intended to be used. The Steganography sample program included with Alchemy is this exemplar. I chose steganography to demonstrate that Alchemy is much more useful than the serialization of data for networking. In the process of developing this application I discovered some pain-points with the library and added tools to Alchemy to eliminate this pain.

Steganography

What is steganography?

Steganography is the hiding of messages within plain-sight. This should not be confused with "Stenography," which is the recording of dictation. Steganography can be performed in may ways. Normal words can be given special meaning and included within a message that appears to be mundane. The location of words relative to others in the message can have a significant meaning. The second letter of every other word can be extracted to form the message. The possibilities are endless.

The form of steganography that I have implemented with Alchemy embeds a text message within a bitmap image. This can be achieved by taking advantage of the fact that the low-order bits for the color channels in an image affect the final color much less compared to the high-order bits.

The table below shows a sample for each color channel, with and without the two lower-bits set. The row with binary indicates the values of the four lower-bits for each 8-bit color. For demonstration purposes, the alpha channel is represented with grayscale.

Red‬‬   Green‬‬‬   Blue   Alpha
FF FC   FF FC   FF FC   FF FC
1111 1100   1111 1100   1111 1100   1111 1100
       

Compare this to the result if we substitute only the single high-bit for each color channel:

Red‬‬   Green‬‬‬   Blue   Alpha
7F FF   7F FF   7F FF   7F FF
0111 1111   0111 1111   0111 1111   0111 1111
       

The only caveat is the image should have a sufficient amount of entropy, otherwise the noise added by the encoded data may become visible; if not to a human, then most certainly to computer searching for such anomalies. Photographs with a range of gradients are good candidates for this form of steganography.

Why Use Steganography as a Sample?

Through the development of the base set of features for Alchemy, I focused solely on the serializing of data for network data transfer protocols. However, Alchemy is a flexible serialization library that is not restricted to network communication. Portable file formats also require serialization capabilities similar to the capabilities found in Alchemy. To this end, loading and storing a bitmap from a file is a good serialization task; bitmaps are relatively easy to acquire, and the format is simple enough to be implemented in a small sample program.

I wanted to keep the program simple. Writing a portable network communication program is not simple; especially since Alchemy does not provide functionality directly related to network communication. I also felt that if I were to use a network related exemplar, potential user of Alchemy would assume it can only be used for network related tasks. Moreover, I did not want to add extra support code to the application that would hide or confuse the usage of Alchemy.

Strategy

In keeping with simplicity, the sample program requires 32-bit bitmaps. For this type of encoding, there are four color channels (Red, Green, Blue, and Alpha) for each pixel, where each channel is one-byte in size. We will encode a one-byte of data within each pixel. To accomplish this, we will assign two-bits of the encoded byte into the two lower-bits of each color channel. This results in a 25% encoding rate within the image.

Consider an example where we combine the orange color 0xFF9915 with the letter i, 0x69:

    Channel 1   Channel 2   Channel 3   Channel 4
Input   0xFF   0x99   0x15   0x00
Value   1111 1111   1001 1001   0001 0101   0000 0000
Data   01   10   10   01
Result   1111 1101   1001 1010   0001 0110   0000 0001
Output   0xFD   0x9A   0x16   0x01

This is not a very complex encoding strategy. However, it will allow me to demonstrate the serialization of data for both input and output, as well as the packed-data bit (bit-field) functionality provided by Alchemy.

Bitmap Format

The bitmap file format has many different definitions. The variety of formats are a result of its inception on IBM's OS/2 platform, migration to Windows, and evolution through the years. Additionally, the format allows for an index 8-bit color table, Run-Length Encoded (RLE) compression, gamma correction, color profiles and many other features.

The sample application simply uses the bitmap format introduced with Windows 3.0. It contains a file header that indicates the file is of type BITMAP, a bitmap information section, and the pixel data. The Alchemy definitions for each section are found below. These definitions provide the fundamental structure for the data; the goal was to provide a table-based definition that looks very similar to the definition of a struct. This declaration is also for generating the majority of the serialization logic for Alchemy:

File Header

The bitmap file header is a short constructor that is only 14-bytes large. The first two bytes will contain the letters "BM" to indicate that this is a bitmap. The length of the file, and the offset to the first pixel data are also encoded in this structure:

C++

//  *************************************************************
ALCHEMY_STRUCT(bitmap_file_header_t,
  ALCHEMY_DATUM(uint16_t, type),
  ALCHEMY_DATUM(uint32_t, length),
  ALCHEMY_DATUM(uint16_t, reserved_1),
  ALCHEMY_DATUM(uint16_t, reserved_2),
  ALCHEMY_DATUM(uint32_t, offset)
)

Bitmap Information Header

The bitmap information section is 40-bytes of data that defines the dimensions and color-depth of the encoded bitmap:

C++

//  *************************************************************
ALCHEMY_STRUCT(bitmap_info_header_t,
  ALCHEMY_DATUM(uint32_t, size),
  ALCHEMY_DATUM(int32_t,  width),
  ALCHEMY_DATUM(int32_t,  height),
  ALCHEMY_DATUM(uint16_t, planes),
  ALCHEMY_DATUM(uint16_t, bit_depth),
  ALCHEMY_DATUM(uint32_t, compression),
  ALCHEMY_DATUM(uint32_t, sizeImage),
  ALCHEMY_DATUM(int32_t,  x_pixels_per_meter),
  ALCHEMY_DATUM(int32_t,  y_pixels_per_meter),
  ALCHEMY_DATUM(uint32_t, color_count),
  ALCHEMY_DATUM(uint32_t, important_color)
)

Bitmap Information

This is a utility definition to combine the information header and the color data from the buffer for convenience:

C++

//  *************************************************************
ALCHEMY_STRUCT(bitmap_info_t,
  ALCHEMY_DATUM(bitmap_info_header_t, header),
  ALCHEMY_ALLOC(byte_t, header.sizeImage, pixels)
)

Pixel Definition

This is a convenience structure to access each color-channel independently in a pixel:

C++

//  *************************************************************
ALCHEMY_STRUCT(rgba_t,
  ALCHEMY_DATUM(byte_t, blue),
  ALCHEMY_DATUM(byte_t, green),
  ALCHEMY_DATUM(byte_t, red),
  ALCHEMY_DATUM(byte_t, alpha)
)

Alchemy Declarations

Storage Buffer

Alchemy supports both static and dynamic memory management for its internal buffers; dynamic allocation is the default. However, the storage policy can easily be changed to a static policy with a new typedef. The definition below shows the static buffer definitions used by the sample program:

C++

namespace detail
{
typedef Hg::basic_msg<Hg::bitmap_file_header_t,
                      Hg::BufferedStaticStoragePolicy>      hg_file_t;
 
typedef Hg::basic_msg<Hg::bitmap_info_t,
                      Hg::BufferedStaticStoragePolicy>      hg_info_t;
}

Alchemy Message

For convenience, we also pre-define a type for the message format type.

C++

typedef Hg::Message< detail::hg_file_t>   file_t;
typedef Hg::Message< detail::hg_info_t>   info_t;

Bitmap Abstraction

As I mentioned previously, I wanted to keep this sample application as simple as possible. One of the things that I was able to do is encapsulate the bitmap data details into the following Bitmap abstraction. This class provides storage for a loaded bitmap, loads and stores the contents, and provides a generic processing function on each pixel:

C++

class Bitmap
{
public:
  bool Load (const std::string &name);
  bool Store(const std::string &name);
 
  void process( std::string &msg,
                pixel_ftor   ftor);
private:
  std::string   m_file_name;
 
  file_t        m_file_header;
  info_t        m_info;
};

The processing function takes a function-pointer as an argument that specifies the processing operation to be performed each time the function is called. This is the definition for that function-pointer.

C++

typedef void (*pixel_ftor) ( Hg::rgba_t&  pixel,
                             Hg::byte_t&  data);

Load and Store

This section shows the implementation for both the Load and Store operations of the bitmap. The implementation uses the Standard C++ Library to open a file, and read or write the contents directly into the Hg::Message type with the stream operators.

C++

//  *************************************************************
bool Bitmap::Load (const std::string &name)
{
  m_file_name = name;
 
  std::ifstream input(m_file_name, std::ios::binary);
  if (input.bad())
  {
    return false;
  }
 
  input >> m_file_header;
 
  const size_t k_info_len = 0x36ul;
  if (k_info_len != m_file_header.offset)
  {
    return false;
  }
 
  input >> m_info;
 
  return true;
}

And the implementation for Store:

C++

//  ************************************************************
bool Bitmap::Store (const std::string &name)
{
  std::ofstream output(name, std::ios::binary);
  if (output.bad())
  {
    return false;
  }
 
  output << m_file_header;
  output << m_info;
 
  return true;
}

Process

I mentioned at the beginning that it is important to implement programs that perform real-work with your libraries to verify that your library is easy to use and provides the desired functionality as expected. With my first pass implementation of this program, both of those qualities were true for Alchemy, except the performance was quite slow. The cause turned out to be the load and initialization of every single pixel into my implementation for Hg::packed_bits.

The problem is that the bytes that represent the pixel data are normally read into an array as a bulk operation. Afterwards, the proper address for each pixel is indexed, rather than reading the data into an independent object that represents the pixel. When I recognized this, I came up with the idea for the data_view<T> construct. This allows a large buffer to be loaded as raw memory, and a view of the data can be mapped to any type desired, even a complex data structure such as the rgba_t type that I defined.

The data_view is an object that provides non-owning access to the underlying raw buffer. If this sounds familiar that is because it is very similar to the string_view construct that is slated for C++17. It was shortly after I implemented data_view that discovered that string_view existed. So I was a bit shocked, and delighted when I realized how similar the concepts and implementations are to each other. It was a bit of validation that I had chosen a good path to solve this problem.

I plan to write an entry that describes the data_view in detail at a later time. Until then, if you would like to learn more about the approach, I encourage you to check out its implementation in Alchemy, or the documentation for the string_view object.

The purpose of process is to sequentially execute the supplied operation on a single message byte and source image pixel. This is continued until the entire message has been processed, or there are no more available pixels.

C++

//  *************************************************************
void Bitmap::process( std::string &msg,
                      pixel_ftor   ftor)
{
  auto t    = Hg::make_view<Hg::rgba_t>(m_info.pixels.get());
  auto iter = t.begin();
 
  // Calculate the number of bytes that can be encoded or extracted
  // from the image and ensure the the message buffer is large enough.
  size_t length = t.end() - iter;
  msg.resize(length);
 
  for (size_t index = 0; iter != t.end(); ++iter, ++index)
  {
    ftor(*iter, (Hg::byte_t&)(msg[index]));
  }
}

Weave and Extract

These are the two functions that provide the pixel-level operations to encode a message byte into a pixel with the strategy that was previously mentioned. Weave combines the message byte with the supplied pixel, and Extract reconstructs the message byte from the pixel.

I am investigating the possibility of implementing a union-type for Alchemy. If I end up doing this I will most likely revisit this sample and provide an alternative implementation that incorporates the Hg::packed_bits type. This will completely eliminate the manual bit-twiddling logic that is present in both of these functions:

C++

//  *************************************************************
void weave_data ( Hg::rgba_t&  pixel,
                  Hg::byte_t&  data)
{
  using Hg::s_data;
 
  s_data value(data);
 
  pixel.blue  = (pixel.blue  & ~k_data_mask)
              | (value.d0    &  k_data_mask);
  pixel.green = (pixel.green & ~k_data_mask)
              | (value.d1    &  k_data_mask);
  pixel.red   = (pixel.red   & ~k_data_mask)
              | (value.d2    &  k_data_mask);
  pixel.alpha = (pixel.alpha & ~k_data_mask)
              | (value.d3    &  k_data_mask);
}

Extract implementation:

C++

//  *************************************************************
void extract_data ( Hg::rgba_t&  pixel,
                    Hg::byte_t&  data)
{
  using Hg::s_data;
 
  s_data value;
 
  value.d0  = (pixel.blue  & k_data_mask);
  value.d1  = (pixel.green & k_data_mask);
  value.d2  = (pixel.red   & k_data_mask);
  value.d3  = (pixel.alpha & k_data_mask);
 
  data = value;
}

The Main Program

The main program body is straight-forward. Input parameters are parsed to determine if an encode or decode operation should be performed, as well as the names of the files to use.

C++

//  *************************************************************
int main(int argc, char* argv[])
{
  if (!ParseCmdParams(argc, argv))  {
    PrintHelp();
    return 0;
  }
 
  string         message;
  sgraph::Bitmap bmp;
  bmp.Load(input_file);
  if (is_encode)  {
    message = ReadFile(msg_file);
    bmp.process(message, weave_data);
    bmp.Store(output_file);
  }
  else  {
    bmp.process(message, extract_data);
    WriteFile(output_file, message);
  }
 
  return 0;
}

Results

To demonstrate the behavior of this application I ran sgraph to encode the readme.txt file from its project. Here is the first portion of the file:

========================================================================
    CONSOLE APPLICATION : sgraphy Project Overview
========================================================================

AppWizard has created this sgraphy application for you.

This file contains a summary of what you will find in each of the files that
make up your sgraphy application.

Into this image:

Source Image

This is the result image:

Result Image

For comparison, here is a sample screen-capture from a Beyond Compare diff of the two files:

Difference Between Images

Summary

I implemented a basic application that performs steganography to demonstrate how to use the serialization features of my library, Alchemy. I chose a unique application like this to make the demonstration application a bit more interesting and to show the library can be used for much more than just serialization of data for network transfer.

Ode to the Anagramic Poem

general, communication, C++ Send feedback »

Twitter is an... interesting way to spend one's time. It can be quite a challenge to cram a thought into 140 characters. However, I have found there are many ways to be entertained by this micro-blogging site. One of them includes interacting and learning from a wide variety of people. During an interaction with a creative-writer, I was a bit challenged by a poem.

Inspiration from Twitter

This is a brief entry that includes my implementation of that "Poem Anagram Generator."

The Original Poem

The first thing that is required, is the poem. You can find the original at what_adri_writes[^].

Here is an excerpt:

Stanley the fishmonger
told me how to know it
when I saw it
without a poet
And we fished out drowned Phlebas,
Patron saint of Unconsidered Phoenicians
and failed Changers of Minds.
The Highlander Art double-checked the veil
of Reichenbach Falls
three days later
and found
A beekeeper.

Strategy

When I thought about it, I realized it wouldn't take much to actually write a program to reorganize the words of the poem. Especially if I were to use the algorithms that are available in the C++ Standard Library. That is, of course, creating the naïve implementation that ignores such possibly desirable features such as sentence structure or proper grammar.

Then again, this is poetry!

So let's go ahead and throw those concerns out the window. This will be a post-modern avant-garde cyber-experience.

Tokenize

My original goal was to tokenize all of the words from the poem, then randomize with something like next_permutation. However, when I really started to look at the text I saw all of the punctuation. Did I want to remove the punctuation and just live with the words? Well then there are also the new-lines that give the text form and clues the reader in that "pssst, this is probably a poem"

So I decided that I would include both the punctuation and new-lines as tokens to be generated for the poem generator.

To do this I put a space between ever word, punctuation mark, and new-line in the poem; like so:

C++

const std::string poem( "Oh but I too want to be a poet ! \n "
                        "and yet \n "
                        "Tell me where is meaning bred \n "
                        "In my heart or in your head ? \n "
 
                         // omitted for brevity
 
                        "And so the poem \n "
                        "was not to be . \n");

Here is a simple function to add each token into a vector for future modification:

C++

typedef vector<string>    words_t;
 
//  ************************************************************
words_t tokenize(const string &poem)
{
  words_t words;
  size_t  next = 0;
 
  do
  {
    size_t cur = next;
    next = poem.find(' ', cur);
 
    size_t count = next == string::npos
                  ? string::npos
                  : next - cur;
    words.push_back(poem.substr(cur, count));
 
    if (next != string::npos)
      next += 1;
 
  } while (next != string::npos);
 
  return words;
}

If I missed a potential algorithm from the standard library that would perform this task I would be interested to learn how this function could be simplified.

The Generator

The generator code is found below. It contains three algorithms from the standard library; A random number generator, shuffle and copy. Then of course the call to tokenize.

You can run the code below to generate a new poem each time.

C++

//  ************************************************************
int main()
{
  // Tokenize the poem.
  words_t words(tokenize(poem));
 
  // Jumble the words.
  random_device rdev;
  mt19937 rng(rdev());
 
  shuffle(words.begin(), words.end(), rng);
 
  // Print the results.
  copy(words.begin(), words.end(), ostream_iterator<string>(cout, " "));
 
  cout << "\n";
 
  return 0;
}
Run this code

Output:

Twitter and Poetry...

Instant art!

Maybe to improve upon this I could pre-tokenize based on particular phrases.

Summary

Twitter is fun!

C++ is fun!

Combining Twitter and C++ makes poetry fun even for a left-brained analytic like myself.

If you end up generating an interesting poem, post it in the comments.

The "Little Planet" Effect

C++, math, computer graphics 3 feedbacks »

The "Little Planet" effect is the colloquial name often used to refer to the mathematical concept of a stereographic projection. The end result is quite impressive, especially considering the little amount of code that is actually required to create the image. All that is required is a panoramic image with a 360° view from side to side, or a photo-sphere, such as used with Google Earth to provide an immersive view of a location.

Golden Gate Bridge Stereographic Projection

Stereographic Projection

This is a mapping from a spherical position onto a plane. You will commonly see this type of projection in cartography; two examples are mapping the earth and planispheres (celestial charts). This projection is useful because it is not possible to map from a sphere to a plane without some type of distortion. The stereographic projection preserves angles and distorts areas. This trade-off is preferred for navigation, which is typically performed with angles.

The projection is typically performed from one of the poles. However, it can originate from any point on the sphere. For simplicity, unless otherwise stated I will refer to projections that originate at the North Pole of the sphere. For a unit-sphere located at the origin, this would be at \(\matrix{[0 & 0 & 1]}\)

The distortion of the image depends on the placement of the plane relative to the sphere. The upper hemisphere exhibits most of the distortion. The distortion becomes more extreme the closer the point in the sphere's surface approaches the origin of the projection. The projection extends to infinity as the projection's origin is undefined.

If the plane bisects the sphere at the equator, the lower hemisphere will be projected within an area the size of the circumference of the sphere, and the upper hemisphere is projection on the plane outside of the sphere.

When the plane is located at the surface of the sphere, opposite from the projection's origin, the lower hemisphere will project over an area that is twice that of the sphere's equator. The image below illustrates this configuration.

Stereographic Projection

We can reference any point on the spheres surface with two angles representing the latitude \(\phi\) and longitude \(\lambda\), where:

\(-\pi \lt \lambda \lt \pi, -\cfrac{\pi}{2} \lt \phi \lt \cfrac{\pi}{2} \)

The following image is a scaled down version of the panorama that I used to generate the stereographic projection of the Golden Gate Bridge at the beginning of the article. Normally we would index the pixels in this image with two variables, \(x\) (width) and \(y\) (height).

Golden Gate Bridge Panorama

We can simplify the math to map a full-view panorama to a sphere by normalizing the dimensions for both the sphere and our surface map; that is, to reduce the scale to the unit scale of one. This means we will perform the surface map operation on a unit-sphere, and the dimensions of our panorama will then span from: \(-1 \lt x \lt 1, -1 \lt y \lt 1\).

The following image shows how the coordinate system from the sphere maps to the image:

normalized coordinates

Project the sphere onto the Plane

We will create a ray, to calculate the projection of a single point from the sphere to the plane. This ray begins at the projective origin, passes through the sphere and points at any other point on the surface of the sphere. This ray continues and will intersect with the projective plane. This intersection is the point of projection. Alternatively, we can calculate the intersection point on the sphere's surface, given a ray that points between the projective origin and the projection plane. This demonstrates that the stereographic projection is a bijective operation; there is a one-to-one correspondence for the values on both surfaces.

The diagram below depicts the projection in two-dimensions:

Side Intersection

If \(\lambda_0\) as the central longitude and (\phi_1\) as the central latitude, this relationship can be stated mathematically as:

\( \eqalign{ u &= k \cos \phi \sin(\lambda - \lambda_0) \cr v &= k [ \cos \phi_1 \sin \phi - \sin \phi_1 \cos \phi \cos(\lambda - \lambda_0)]\cr & where \cr k &= \cfrac{2R}{1+ \sin \phi_1 \sin \phi + \cos \phi_1 \cos \phi \cos(\lambda - \lambda_0)} } \)

The term \(k\) determines where the projected plane is located.

Codez Plz

That is enough theory and explanation. Here is the code that I used to generate the stereographic projections of the Golden Gate Bridge and Las Vegas. The code presented below is adapted from a project I just completed that used the Computer Vision library OpenCV. The only important thing to note in the code below is that Mat objects are used to store images and pixels are represented with a type of std::vector. You should have no problem converting the pixel access operations from the code below to whatever image processing API that you are using.

If you do run into problems, leave a comment and I will help you work through porting the code.

First, here are two constants defined in the code:

C++

const double k_pi         = 3.1415926535897932384626433832795;
const double k_pi_inverse = 0.31830988618379067153776752674503;

There are three functions:

Main Projection

This function works by creating a ray between the projection origin and a pixel location on the projection plane. The intersection of the sphere's surface is calculated, which indicates the location to sample from the sphere's surface map. Because we are dealing with discrete, pixelated digital images, this sampling process creates visual artifacts. To help improve the smoothness of the image, we use a bilinear filter to average the values of four surrounding pixels of the sample location from the sphere.

C++

void RenderProjection(Mat &pano, long len, Mat &output) {
  output.create(len, len, CV_16UC3)
  long half_len = len / 2;
  Size sz       = pano.size();  
 
  for (long indexX = 0; indexX &lt; len; ++indexX) {
    for (long indexY = 0; indexY &lt; len; ++indexY) {
      double sphereX = (indexX - half_len) * 10.0 / len;
      double sphereY = (indexY - half_len) * 10.0 / len;
      double Qx, Qy, Qz;
 
      if (GetIntersection(sphereX, sphereY, Qx, Qy, Qz))
      {
        double theta  = std::acos(Qz);
        double phi    = std::atan2(Qy, Qx) + k_pi;
        theta          = theta * k_pi_inverse;
        phi            = phi   * (0.5 * k_pi_inverse);
        double Sx      = min(sz.width -2.0, sz.width  * phi);
        double Sy      = min(sz.height-2.0, sz.height * theta);
 
        output.at<Vec3s>(indexY, indexX) = BilinearSample(pano, Sx, Sy);
      }
    }
  }
}

Calculate the Intersection

This calculation is an optimized reduction of the quadratic equation to calculate the intersection point on the surface of the sphere.

C++

bool GetIntersection(double u, double v,
  double &x, double &y, double &z)
{
  double Nx    = 0.0;
  double Ny    = 0.0;
  double Nz    = 1.0;
  double dir_x = u - Nx;
  double dir_y = v - Ny;
  double dir_z = -1.0 - Nz;
 
  double a = (dir_x * dir_x) + (dir_y * dir_y) + (dir_z * dir_z);
  double b = (dir_x * Nx) + (dir_y * Ny) + (dir_z * Nz);
 
  b *= 2;
  double d = b*b;
  double q = -0.5 * (b - std::sqrt(d));
 
  double t = q / a;
 
  x = (dir_x * t) + Nx;
  y = (dir_y * t) + Ny;
  z = (dir_z * t) + Nz;
 
  return true;
}

Bilinear Filter

The bilinear filter calculates a weighted-sum of the four surrounding pixels for a digital image sample.

C++

Vec3s BilinearSample(Mat &image, double x, double y) {
  Vec3s c00 = image.at<vec3s>(int(y), int(x));
  Vec3s c01 = image.at<vec3s>(int(u), int(x)+1);
  Vec3s c10 = image.at<vec3s>(int(y)+1, int(x));
  Vec3s c11 = image.at<vec3s>(int(y)+1, int(x)+1);
 
  double X0 = x - floor(x);
  double X1 = 1.0 - X0;
  double Y0 = y - floor(y);
  double Y1 = 1.0 - Y0;
 
  double w00 = X0 * Y0;
  double w01 = X1 * Y0;
  double w10 = X0 * Y1;
  double w11 = X1 * Y1;
 
  short r  = short(c00[2] * w00 + c01[2] * w01
                 + c10[2] * w10 + c11[2] * w11);
  short g  = short(c00[1] * w00 + c01[1] * w01
                 + c10[1] * w10 + c11[1] * w11);
  short b  = short(c00[0] * w00 + c01[0] * w01
                 + c10[0] * w10 + c11[0] * w11);
 
  return make_BGR(b, g, r);
}

...and a helper function:

C++

Vec3s make_BGR(short blue, short green, short red)
{
  Vec3s result;
  result[0] = blue;
  result[1] = green;
  result[2] = red;
 
  return result;
}

Here is another sample of a stereographic projection and the panorama that I used to create it:

Las Vegas Stereographic Projection

Las Vegas Panorama

Summary

The stereographic projection has been known and used since the time of the ancient Greeks. It was heavily used in the Age of Exploration to create maps of the world where the distortion was applied to distances, and the relative angles between local points is preserved. When it is applied to full-view panoramas a neat effect is created called, "The Little Planet Effect." With just a little bit of theory and some concepts from computer graphics we were able to turn this concept into code with less than 100 lines of code.

Rvalue References Applied

C++, Alchemy, engineering Send feedback »

A continuation of a series of blog entries that documents the design and implementation process of a library. The library is called, Network Alchemy[^]. Alchemy performs automated data serialization with compile-time reflection. It is written in C++ using template meta-programming.

My previous entry was a condensed overview on rvalue references. I described the differences between value expressions and types. I also summarized as much wisdom as I could collect regarding how to effectively use move semantics and perfect-forwarding. After I completed the essay, I was eager to integrate move semantics for my serialization objects in Alchemy. This entry is a journal of my experience optimizing my library with rvalue references.

Full story »

C++: Rvalue References

CodeProject, C++ 2 feedbacks »

Rvalue references were introduced with C++11, and they are used to implement move semantics and perfect-forwarding. Both of these techniques are ways to eliminate copies of data parameters for efficiency. There is much confusion around this new feature that uses the && operator, because its meaning is often based on the context it is used. It is important to understand the subtleties around rvalue references in order for them to be effective. This entry will teach you how to use the rvalue reference with plenty of live-demonstrations.

Full story »

Alchemy: PackedBits (BitLists Mk3)

C++, Alchemy, design Send feedback »

A continuation of a series of blog entries that documents the design and implementation process of a library. The library is called, Network Alchemy[^]. Alchemy performs low-level data serialization with compile-time reflection. It is written in C++ using template meta-programming.

My second attempt to create a bit-field type was more successful. The size of the container only grew linearly with each sub-field that was added, and the implementation was cleaner. However, I showed an image of what this implementation looked like in the debugger and it was very in convenient. The thing I was concerned with the most was the pitiful performance that was revealed by my benchmark tests.

This entry describes my discoveries and the steps that I took to re-invent the bit-field type in Alchemy for the third time. This is also the current implementation in use by Alchemy, which is about 10% faster than hand-coded collection of packed-bits.

Full story »

C++: Template Meta-Programming 2.0

CodeProject, C++ 2 feedbacks »

I was amazed after I had converted only the first few portions of the TypeList from the C++98 implementation to Modern C++. I have decided to convert my Alchemy API to use Modern C++ in order to truly learn the nuances by application of acquired knowledge. The code of these meta-programs are very elegant and completely readable. This really does feel like a new language, and an entirely new version of meta-programming.

The elegance enabled by the new constructs will allow me to present a complete TypeList implementation for Modern C++ in this entry.

Full story »

C++: auto

CodeProject, C++ Send feedback »

The keyword auto has been given a new behavior since the C++11 Standard was ratified. Instantly I could appreciate the value of its new function when I considered things like declaring an iterator for a container. However, I was skeptical of any value that auto could provide for general purpose use.

Now that I have had a chance to study this new keyword I believe that it is quite a valuable addition to Modern C++. While there are situations that could still cause some grief, they are not difficult to detect, and the solutions to the problem are straight-forward to apply

Full story »

Contact / Help. ©2017 by Paul Watt; Charon adapted from work by daroz. blogging software / hosting.
Design & icons by N.Design Studio. Skin by Tender Feelings / Skin Faktory.