Adrian McCarthy

During this weekend’s heatwave, I’ve been tracking a shadow problem that’s been lurking in my ray tracer for a while. It occurs when a light source is at a grazing angle to some of the facets in a mesh object. I’ve ignored it with Utah Teapot and images, but now that I’m playing with cloth simulation, it became more prominent.

As is often the case, what I thought was one bug turned out to be two (or three, depending on how you count them).

Here’s an example of the problems. The shadows marked with red ellipses are clearly artifacts of the underlying mesh approximation. Also, the top of the knob on the teapot lid shows subtle, but clearly wrong, undulations. I thought these were two aspects of the same bug. They weren’t. I’ve solved the latter problem, and I now understand the former—I’m just not sure what to do about it.

A little background. The teapot is defined with Bezier patches, which are smooth two-dimensional curved surfaces. My ray tracer teselates the patches into a triangle mesh that approximates the curves. Tracing the patches directly is harder and generally slower.

To avoid the blocky appearance, we tweak the surface normals used in the shading calculations to more closely match the round object. This approach can give a nice rounded appearance despite the coarse triangle mesh (as long as you don’t scrutinize the profiles too closely). The is done by precomputing the desired surface normal at each vertex in the mesh and then by interpolating the from the nearest vertices.

The problems stem from the fact that the mesh is just an approximation. You can reduce the artifacts by increasing the resolution of the mesh, but they still persist, just smaller. If I were to add the ability to trace the patches directly, I’d still have the problem with other objects, like the bunny, that are natively defined as a mesh.

My instincts told me that I had messed up the interpolation of the normals. And indeed, that was the cause of the shading problem on the knob at the top of the lid. Lots of long, very skinny triangles come together there. To compute a vertex normal, I accumulated the surface normal of each triangle that touched the vertex and then normalized the sum.

It turns out that this is not the best way to compute the vertex normals. About half of the skinny triangles on top each have a side that is approximately zero in length. (Ideally, they would be exactly zero except for the imprecision of floating point arithmetic. Also, their normals would be very close to the correct value, but their very skinny nature introduces error into the cross product of the edges.) These almost non-existent triangles were contributing as much to the normal calculation as the larger triangles whose points meet at the center of the knob.

A did a search and found a page of course notes from Ken Perlin that explains how to compute normals by weighing the contributions of the larger facets more than those of the smaller ones. I changed my program to use this algorithm, and the strange shading on the top of the knob vanished.

But the other shadows remained.

And that is the key. The remaining problem had to do with shadows not shading.

Like scanline renderers, the ray tracer shades a point with calculations based on the surface normal and the direction to the light source. Surfaces that face the light are brighter than those that are angled away. This is shading.

Shadows depend on the visibility of the light source from the point in question. Scanline renderers require tricks (such as light buffers or shadow volumes) to determine if a light source actually reaches a particular point. A ray tracer, on the other hand, can simply trace the path back to the light source to see if anything stands in the way. If you forgive the perfect point light source approximation, this gives very realistic shadows without any of the complications the scanline renderers use.

And that’s the problem. We’re using a physically accurate test in order to check for a shadow on a physically inaccurate model of the teapot.

The thick straight lines represent the facets of our mesh (edge on), and the curved line is the actual contour we’re trying to approximate. We want to compute the shading for the point at the base of the blue arrow, which represents the interpolated surface normal. The light is at a grazing angle. Although the angle between the vector to the light source and the interpolated surface normal is less than 90 degrees, the shadow test fails. The corner where the two facets meet essentially casts a shadow across the entire left facet. This is the artifact seen in the teapot.

My first few debugging runs suggested that the problem was self shadowing. That is, the facet was casting a shadow across itself. I modified my code to disallow self-shadowing, but it didn’t help much. It turns out that the shadow, in most cases, is actually cast by an adjacent facet.

I’m not sure how to fix it at this point. I was hoping that writing this down might give me some ideas. Perhaps you have a suggestion.

Amendment I

Congress shall make no law respecting an establishment of religion, or prohibiting the free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the people peaceably to assemble, and to petition the Government for a redress of grievances.

Amendment II

A well regulated Militia being necessary to the security of a free State, the right of the people to keep and bear Arms shall not be infringed.

Amendment III

No Soldier shall, in time of peace be quartered in any house, without the consent of the Owner, nor in time of war, but in a manner to be prescribed by law.

Amendment IV

The right of the people to be secure in their persons, houses, papers, and effects, against unreasonable searches and seizures, shall not be violated, and no Warrants shall issue, but upon probable cause, supported by Oath or affirmation, and particularly describing the place to be searched, and the persons or things to be seized.

Amendment V

No person shall be held to answer for a capital, or otherwise infamous crime, unless on a presentment or indictment of a Grand Jury, except in cases arising in the land or naval forces, or in the Militia, when in actual service in time of War or public danger; nor shall any person be subject for the same offence to be twice put in jeopardy of life or limb; nor shall be compelled in any criminal case to be a witness against himself, nor be deprived of life, liberty, or property, without due process of law; nor shall private property be taken for public use, without just compensation.

Amendment VI

In all criminal prosecutions, the accused shall enjoy the right to a speedy and public trial, by an impartial jury of the State and district wherein the crime shall have been committed, which district shall have been previously ascertained by law, and to be informed of the nature and cause of the accusation; to be confronted with the witnesses against him; to have compulsory process for obtaining witnesses in his favor, and to have the Assistance of Counsel for his defence.

Amendment VII

In suits at common law, where the value in controversy shall exceed twenty dollars, the right of trial by jury shall be preserved, and no fact tried by a jury, shall be otherwise reexamined in any Court of the United States, than according to the rules of the common law.

Amendment VIII

Excessive bail shall not be required, nor excessive fines imposed, nor cruel and unusual punishments inflicted.

Amendment IX

The enumeration in the Constitution, of certain rights, shall not be construed to deny or disparage others retained by the people.

Amendment X

The powers not delegated to the United States by the Constitution, nor prohibited by it to the States, are reserved to the States respectively, or to the people.

With some help from my brother, I developed a simple mass and spring system simulation, which I’ve been using to model cloth. It was surprisingly east to implement. The simulator does some on-screen wireframe animation, but I can only capture snapshots in the ray tracer right now. I’ll work on rendering full animations soon.

A friend recently introduced me to Vimeo, a video-sharing site with much higher picture quality than a lot of the more popular sites. The downside is you need more patience or a faster connection. Vimeo seemed like a good way to show off what my 3D scanner can do.

I scanned a gargoyle while back, and it turned out surprisingly well.

Gargoyle scanned with homemade 3D scanner from Adrian on Vimeo.

Above is the recreation of the gargoyle from my ray tracer rendered at 720p.

The holes are places where the laser beam was occluded from the camera. To fill those in, I’ll have to figure out how to combine multiple scans in different orientations.

The undulations in the body are not accurate. I think they’re an artifact of the limitations of my setup. Looking closing at the photographs, it seems there’s a little camera and turntable jiggle, but it might also be quantization error. I’m trying to learn more about how to smooth the data.

There is a shadowing bug in my ray tracer that sometimes causes a triangle at a glancing angle to the light to be completely shadowed when it shouldn’t be. I’m still trying to track that down.

There are a couple wild triangles from the top, and a crazy cupcake wrapper like thing around the base. Those are from stray points that the algorithm mistakenly identified as points where the laser intersected the model. A part of the rig was visible in the lower left corner of the frame, which it what caused most of those incorrect triangles around the base.

So there’s definitely more work to do. Nevertheless, it’s encouraging to see how much I was able to do with such a simple approach.

Just a test. This is very similar to the animation I posted a while back, but this time I used a better codec, and I’m trying out YouTube.

Windows 32 has a thread synchronization primitive called a critical section. It’s defined as a C-style struct called CRITICAL_SECTION. There are a pair of lifetime functions called InitializeCriticalSection and DeleteCriticalSection. This just screams for a C++ wrapper that implements RAII (resource allocation is instantiation).

class CCriticalSection
{
  public:
    CCriticalSection(void)  { ::InitializeCriticalSection(&m_cs); }
    ~CCriticalSection(void) { ::DeleteCriticalSection(&m_cs); } 

  private:
    CRITICAL_SECTION m_cs;
};

Now, if you have a data structure that needs a critical section, you can simply add a CCriticalSection as a member variable. Not only don’t you have to worry about initialization and clean-up, the clean up will happen even if an exception is thrown. Wonderful.

There are two more functions related to critical sections, EnterCriticalSection and LeaveCriticalSection. We could expose these in our wrapper class.

class CCriticalSection
{
  public:
    CCriticalSection(void)  { ::InitializeCriticalSection(&m_cs); }
    ~CCriticalSection(void) { ::DeleteCriticalSection(&m_cs); } 

    Enter(void) { ::EnterCriticalSection(&m_cs); }
    Leave(void) { ::LeaveCriticalSection(&m_cs); }

  private:
    CRITICAL_SECTION m_cs;
};

Here’s how a class might use it:

class CSharedDataThing
{
  public:
    ...

    void Update(void)
    {
      m_cs.Enter();
      ... do stuff to the data ...
      m_cs.Leave();
    }

  private:
    CCriticalSection m_cs;
};

There’s a bug with the Update method. If an exception is thrown in the “do stuff” bit, the exception will propagate up, but the critical section will still be held. This could lead to a deadlock. Furthermore, the programmer has to be very careful to always pair calls to Enter with calls to Leave. In practice, this could be error prone.

The solution, according to RAII, is to treat Enter as construction and Leave as destruction. The rules of C++ will then guarantee that we always leave any critical section we enter, even if exceptions start flying. What we need is another class to encapsulate the idea of entering and leaving the critical section.

class CEnterCriticalCode
{
  public:
    CEnterCriticalCode(CCriticalSection &cs) : m_cs(cs) { m_cs.Enter(); }
    ~CEnterCriticalCode(void) { m_cs.Leave(); }

  private:
    CCriticalSection &m_cs;
};

Now we can rewrite CSharedDataThing::Update like this:

    void Update(void)
    {
      CEnterCriticalSection guard(m_cs);
      ... do stuff to the data ...
    }

That may look a little strange until you get used to it. We declare the local variable guard and do nothing with it. We merely rely on its lifetime to manage the critical section. We no longer have to remember to call Leave, and if—FSM forbid—an exception is thrown, the automatic stack unwinding will call guard’s destructor, ensuring the critical section is left.

If only part of Update’s work required the critical section, we could use an extra scope like this:

    void Update(void)
    {
      ... do non-critical stuff ...
      {
        CEnterCriticalSection guard(m_cs);
        ... do critical stuff to the data ...
      }
      ... do more non-critical stuff ...
    }

The drawback here is that extra scope block and indentation may look unnecessary to another team member who doesn’t realize what’s going on. In fact, the declaration of guard, which is never referenced, looks like dead code to be eliminated. And if someone does eliminate the scope, the guard, or both, the bug that manifests may be a subtle timing issue.

That’s almost more dangerous than someone forgetting to call LeaveCriticalSection in the non-RAII world.

Possible defenses here are comments or an unusual formatting style that makes others realize this is special code.

    void Update(void)
    {
      ... do non-critical stuff ...

      { CEnterCriticalSection guard(m_cs);
        ... do critical stuff to the data ...
      } // leaving critical section

      ... do more non-critical stuff ...
    }

Putting the guard declaration on the same line as the brace that begins the scope should signal the next developer to come along that this is special. Let’s hope so anyway.

I just added a blog called Edittorrent to my blog roll and daily reading list. These editors provide extremely detailed advice and analysis about what works and what doesn’t. I’ve already learned a lot this week. Recommended.

Last November, I posted information on how to mark your application as DPI-aware in order to avoid Vista’s high-DPI scaling.

It turns out that there is a way to do this in your manifest. It just wasn’t (widely?) documented before the end of last year. The manifest approach is preferred, because it avoids potential race conditions when your application starts up.

So go back and rip out your calls to SetProcessDPIAware and replace them with a manifest entry, which is now documented alongside the function call.

Each time you fix a bug in a program, you should take a step back and ask yourself some questions. Where else might I have made the same mistake? How could I improve the process or the design to have made the mistake less likely? How can I automatically detect this type of error in the future?

The answers to these questions lead to process improvements that go beyond the current fix, and help improve the quality of the program going forward.

Clearly Comcast doesn’t ask themselves the same sorts of questions after resolving a customer problem. In my previous post, I detailed the errors that prevented us from getting digital cable for nearly a month. Not only was it a pain for us as customers, it cost Comcast lots of money. Sending a technician to a customer house isn’t cheap. Sending them six times starts to add up. So does three hours of tech support time on the telephone. And crediting customers for their trouble.

Of course, Comcast is a regional monopoly, so they have little motivation to improve their efficiency. They simply pass the costs of their own incompetence onto their customers.

Our problem was not one bug in isolation. It was error upon error and mistake upon mistake. Most of them could have been mitigated or even prevented if Comcast had better processes in place. Allow me to make a few suggestions.

1. Use the same CableCARDs and activation processes for Comcast set-top boxes as for third-party set-top boxes. This was the point of the CableCARD standard. From the cable company’s view, there should be no appreciable difference.
2. Train the technicians about CableCARD. While all the technicians we worked with were polite and helpful, some clearly knew next-to-nothing about the CableCARD activation process. Some had misinformation and superstitions about it. Two of the technicians I spoke to on the phone were literally reading the manual for what sounded like the first time.
3. Improve the call tracking system. Each time I spoke with someone from Comcast, I had to explain everything that had already happened. Most other companies seem to track customer service issues on an account so that the next technician has all the notes of what happened before.
4. When a second customer visit is necessary for the same problem, send the same technician. While they were all polite, some of the techs clearly wanted to foist the problem onto the next guy. If you don’t let them off the hook, they’re going to learn how to solve problems on the first try.
5. Improve the appointment system so that appointments aren’t scheduled during planned outages.
6. Notify customers about planned outages. (Comcast claims this should have happened all three times, but sometimes the subcontractors doing to upgrade cut corners and fail to deliver the door cards. This is another failure, and it seems it could be remedied by docking the contractors each time they skip this step. Putting the information on their website would have been a good backup plan as well.)
7. Create an equipment reservation system so that when a customer is sent to pick stuff up at the service center, the stuff is actually available.
8. Connect the billing system to the service activation system. Customers shouldn’t be billed for a service before it is delivered. Automation of this would avoid mistakes, both under-billing and over-billing.
9. Put all underground cable in conduit, so old rotting wires can be replaced.

I wouldn’t expect a brand-new cable company to have all of this figured out. But Comcast is the nation’s largest cable provider. They’ve been around for a very long time. The fact that they haven’t implemented any of these processes is pathetic.

Next time Comcast’s franchise is up for renewal in our city, I’ll be prompting our city council to query Comcast on progress in these areas.

To: Rick Germano
SVP Customer Operations
Comcast

Mr. Germano:

My wife and I decided to take advantage of our HD television by upgrading to digital cable service. We invested in a Series 3 TiVo and ordered Digital Classic from Comcast. Three weeks after ordering, Comcast is still unable to activate my service. I’m at a complete loss of what to do next. Perhaps you have a suggestion about how I should proceed.

Here is the story so far.

January 2:

I ordered the service over the phone, making it clear it would be a CableCARD installation for a TiVo. The appointment was scheduled for January 4 between 4 and 6 p.m.

January 4:

Technician arrived within the window, and immediately apologized for bringing the wrong type of CableCARDs. (I found this specious, since CableCARDs are standardized. The ones used for a TiVoHD should be exactly the same as the ones used in Comcast’s own set-top boxes.) The appointment was rescheduled for January 8.

January 8:

The technician that arrived for this appointment did not inspire much confidence. He grumbled about TiVo activation being difficult. He also immediately decided to replace our splitter simply because it had gold contacts. He seemed to have a superstition against these. We had no signal problems with the original splitter.

He installed the card and got it activated. He showed my wife that it was receiving HD channels and left with a vague apology “in case he did anything wrong.”

When I arrived home, I discovered the technician had not paired the CableCARD to the TiVo, and therefore, many of the Digital Classic channels were unavailable.

I spent about 25 minutes on the phone with customer support, who tried to correct the activation problem, but they didn’t really understand how the process worked. Eventually she punted and scheduled a third technician visit.

January 10:

I took the morning off work to meet the technician. I was prepared with hardcopies of TiVo’s CableCARD activation and troubleshooting guides. But that was moot. The technician arrived and explained that the cable for our entire neighborhood was out because of network upgrades. Since there was no cable signal, he could not solve the activation problem.

The technician said that there was no coordination between the regular Comcast service technicians and the contractors doing the neighborhood upgrade. This is mindboggling to me, since it costs Comcast to send technicians out, and it was a huge inconvenience to me since I had take time off work to get this activation settled once and for all.

In response to my frustration, the technician got on the phone and got us a priority Saturday appointment.

January 12:

The fourth technician arrived and had a long phone conversation with a technician at the headend. They concluded that the CableCARD had to be completely reset because of the earlier mistakes. Unfortunately, the only person who knew how to do that (or was authorized to) wasn’t scheduled to work until 4 p.m.

The technician gave me his cell phone number, and said that if I didn’t hear from Comcast in the afternoon to call him back before 6 p.m. Of course, I received no phone calls, and the message I left on the technician’s cell was never returned.

January 13:

I called Comcast again and spent 40 minutes with a technician on the phone who tried several times to activate my CableCARD remotely. At first he was reading instruction manuals, later in the call he was working with a second technician. After about 40 minutes, they concluded that my CableCARD was spoiled by the earlier mistakes and would have to be replaced. I was dubious, but agreed to go to my local service center (about a 20-minute drive one-way) in order to exchange my CableCARD.

January 17:

I took some time off in the afternoon in order to exchange my CableCARD at the local customer service office. Unfortunately, they were out of CableCARDs, so I would have to return another time.

January 19:

I traveled again to the Comcast customer service office to exchange the CableCARD. This time they have some in stock.

I installed the replacement card and called Comcast to activate it. Things seemed to be going better, as we quickly got the card activated and paired to the TiVo. Unfortunately, the encrypted Digital Classic channels still would not come in. The technician tried to rush me off the phone and got a bit short with me. He concluded that I’d need another techician to come to the house. (Again I was dubious, since the CableCARD was activated and paired, so it should only be a matter of authorizing it.) I was further frustrated by the fact that the next available appointment was six days away.

January 24:

My technician appointment window was 9 a.m. to 11 a.m. Once again I took time off work to make sure we really got this activated this time.

Unfortunately, the cable signal for our entire neighborhood died at 9:30 a.m. The technician arrived at 10:30 a.m. and tried to diagnose the loss of signal. Within a few minutes and a couple calls to the office, it was determined that the contractors upgrading the network had again cut off our neighborhood with no estimate of when service would be restored. Without working cable service, it is impossible to diagnose the problem with the CableCARD.

That brings us to today. Five technician visits, three long phone calls, two trips to the Comcast customer service center. Three weeks since we’ve ordered the service, we still don’t have our channels, and I have no confidence anyone at Comcast even knows how to fix the problem.

Please advise me in how to proceed.

Adrian McCarthy

Update January 25: The bill arrived, and, of course, I was charged for Digital Classic, prorated back to 1/8. In an online chat with a representative from the billing department, I pointed out that I still do not receive the Digital Classic channels and that our basic cable has been out three days this month (so far). The representative apologized and credited me one month’s worth of the Digital Classic package price ($14.95).

Today I also received an automatic e-reply from Rick Germano’s office. I hope to get a live response soon.

Update January 29: The issue is now resolved. We got a fast response from this email. Our issue was escalated to a regional manager who helped us. I’ll post details later.

Update February 2: Here is how the problem finally got resolved.

Comcast put us in touch with a regional manager who apologized for the hassle and assured us the problem would be resolved. There were additional scheduling delays because of the neighborhood upgrade. After the upgrade was completed, the regional manager sent a technician who worked on the problem for 2.5 hours. (That’s the sixth technician to visit the house, for those of you keeping count.)

The cable signal at our house is poor. A while back I had put in an amplifier to boost the signal, and it made a big improvement on our analog channels. Even though the amplifier is rated for digital cable frequencies, the CableCARD activation would not work with the amplifier in place. The technician removed the amplifier.

Without the amplifier, the signal was especially bad, which also interfered with the CableCARD activation. Our house is set back from the street, and the technician suspected that the cable that runs for over 120 feet under our driveway was old and corroded. One segment of that run was accessible, so the technician pulled new cable through that segment. It helped a little bit, enough to activate our CableCARD.

Unfortunately, the signal is still poor, so we get lots of drop-outs on the digital channels, and most of the analog channels are now unwatchable without the amplifier. The other suspect segment of cable is buried under our driveway, not in conduit.

In hindsight, I probably should have gone with a satellite system. But it’s too late now to return the TiVo HD (which I purchased with a lifetime subscription), so we’ll try to tough it out with Comcast. I’ll reinstall the amplifier on a branch so that other televisions in the house can have watchable analog channels.

I’ll admit that the level of customer service we received from Comcast after I wrote the complaint letter jumped dramatically. And they credited a month of service for our trouble. I’m still not impressed enough to recommend Comcast. We shouldn’t have had to go through the three weeks of frustration. And they should be providing a better signal to our house.

I certainly won’t be considering them for telephone or Internet access.