• entries
    422
  • comments
    1540
  • views
    488817

An example of debugging from '3D Pipes in Direct3D 10'

Sign in to follow this  
jollyjeffers

174 views

Okay, so a root cause to my previous ranting and mildly stroppy behaviour in the forums was that novice programmers lack some basic debugging skills. Which in itself is of no surprise (novice being the key word [wink]) but the frustrating part is that far too many are too lazy to pick up this skill regardless of how important people tell them it is...

So I'm going to go out on a limb and write down my debugging story for tonight. The limb being the one that tempts "lol n00b" comments because my debugging technique is judged inferior [lol]. Feel free to comment though - I'm not immune to learning...

Despite the graphical context (Yup, 3D Pipes in D3D10 again) the real bug is just the application logic. But having said that I will solve it graphically because I like looking at pictures and it makes for a good journal entry. In support of this I've had quite a few private messages over the years from academics teaching algorithms and debugging visually, so I guess it has some merit [grin]


Exhibit A


It's not hard to see what's broke in the above image. The goal is to get a single smooth pipe winding around itself in a random path. There should be no breaks between pipe segments.

My initial diagnosis is that my code for selecting the rotation matrix is overly simplistic. Currently I pick the dominant axis and provide an X, Y or Z rotation as appropriate. This dominant direction is taken by simple vector arithmetic for direction - destination - source.

Now each segment can enter a given point from 6 directions (each face of a cube). Upon entering it can leave via any of the remaining 5 directions; which gives us a total of 30 possible joint meshes. That's a lot more than the trivial 3-way rotation I currently use.

I got a fair way with solving it on paper, but for whatever reason it hasn't worked out quite right. I've bounced around the code a fair bit and now I'm just going to go about debugging it and beating it into submission through brute force [cool].

Step 1: Reduce the variables

I don't like having to solve this in 3D. That above image is good enough to show its broke but its very hard to interpret the how or the why.

Firstly I change the pipe simulation to ignore movement on the Y axis. This now means 4 routes in and 3 routes out for a total of 12 possible joint meshes:


Exhibit B


I'm working in 2D so I want to look at it in 2D. I modify my camera to look top-down onto the XZ plane.


Exhibit C


Now that's much better. The gradient effect is intentional - the start of the pipe is 0.0 and the end is 1.0 - with the shader simplying copying this to a SV_COLOR output.

Step 2: Create a reproducible test-case

All the images I've shown so far (inc. previous journal entries) use a trivial PRNG to generate the pipe by picking a random entry in a list of up to 7 next moves.

Now a crucial thing when debugging is reproducibility. Ever find a bug with something Microft or Nvidia have done (like an HLSL shader that explodes the compiler/driver) - the first response from them is "can you please send us some reproduction code".

One key reason for this is that you need to be able to say "this is broken" and later on "this is fixed" using some sort of objective test or analysis. We don't accept "looks to me like its sorted".

PRNG's don't really work well for reproducibility.

The next debugging step was to hack in a fixed path on the XZ plane for the pipe. A crucial detail here was to get all 12 potential joint meshes in play at the same time.

This proves to be straight-forward enough:


Exhibit D


So I go and insert the following code in:

// Debugging: Use a fixed pipe segment to test various blending joints...
/*
012345
0 /1 ||
2 /-/\-3 \-\/-/
4 ||
5 \/
*/

Utils::CoordinateList pCoords;

// Top arrow
pCoords.push_back( Utils::IntegerVector( 2, 0, 1 ) );
pCoords.push_back( Utils::IntegerVector( 2, 0, 0 ) );
pCoords.push_back( Utils::IntegerVector( 3, 0, 0 ) );
pCoords.push_back( Utils::IntegerVector( 3, 0, 1 ) );

pCoords.push_back( Utils::IntegerVector( 3, 0, 2 ) );

// Right arrow
pCoords.push_back( Utils::IntegerVector( 4, 0, 2 ) );
pCoords.push_back( Utils::IntegerVector( 5, 0, 2 ) );
pCoords.push_back( Utils::IntegerVector( 5, 0, 3 ) );
pCoords.push_back( Utils::IntegerVector( 4, 0, 3 ) );

pCoords.push_back( Utils::IntegerVector( 3, 0, 3 ) );

// Bottom arrow
pCoords.push_back( Utils::IntegerVector( 3, 0, 4 ) );
pCoords.push_back( Utils::IntegerVector( 3, 0, 5 ) );
pCoords.push_back( Utils::IntegerVector( 2, 0, 5 ) );
pCoords.push_back( Utils::IntegerVector( 2, 0, 4 ) );

pCoords.push_back( Utils::IntegerVector( 2, 0, 3 ) );

// Right arrow
pCoords.push_back( Utils::IntegerVector( 1, 0, 3 ) );
pCoords.push_back( Utils::IntegerVector( 0, 0, 3 ) );
pCoords.push_back( Utils::IntegerVector( 0, 0, 2 ) );
pCoords.push_back( Utils::IntegerVector( 1, 0, 2 ) );

pCoords.push_back( Utils::IntegerVector( 2, 0, 2 ) );

// Start again
pCoords.push_back( Utils::IntegerVector( 2, 0, 1 ) );




Doing this generates the following image when the program is run:


Exhibit E


There is one minor improvement to be made. Setting the renderer to adjust the colour according to the 'distance' along a given pipe segment generates the following image:


Exhibit F


Black will be the 'bottom' and white the 'top' of a pipe segment (they're generated from -Y to +Y in model space). The only thing that really matters here is that all joins are black-on-white or white-on-black (cue joke about interracial here? [rolleyes]) and as you can see, some joins are at best ambiguous else completely wrong!

Step 3: Identify the problematic code

This one is quite easy, at least to start with. Chances are you know which bit of code is fubar'd but as you explore further you will no doubt pull in bits of code or follow execution outside of this block.

In my case the following function is prime suspect:
D3DXMATRIX ForwardRenderer::GetRotationMatrixForSegment( const UINT& segment_id, const Utils::CoordinateList& coords )
{
int xDiff = coords.at((segment_id + 1)).x - coords.at(segment_id).x;
int yDiff = coords.at((segment_id + 1)).y - coords.at(segment_id).y;
int zDiff = coords.at((segment_id + 1)).z - coords.at(segment_id).z;

D3DXMATRIX mRet;
D3DXMatrixIdentity( &mRet );

if( (abs(xDiff) > abs(yDiff)) && (abs(xDiff) > abs(zDiff)) )
{
float fSign = 1.0f;
if( xDiff < 0 )
fSign = 1.0f;

// X magnitude
D3DXMatrixRotationZ( &mRet, fSign * D3DX_PI / 2.0f );
}
else if( (abs(yDiff) > abs(xDiff)) && (abs(yDiff) > abs(zDiff)) )
{
// Y magnitude: No transform needed as the geometry is created
// in this direction to start with...
}
else if( (abs(zDiff) > abs(xDiff)) && (abs(zDiff) > abs(yDiff)) )
{
float fSign = 1.0f;
if( zDiff > 0 )
fSign = -1.0f;

// Z magnitude
D3DXMatrixRotationX( &mRet, fSign * D3DX_PI / 2.0f );
}

return mRet;
}




At the outset I'm already wondering if the scope/usage of this function is its true problem. It's called in the following way:

D3DXMATRIX mCurr = GetRotationMatrixForSegment( segment, coords );
D3DXMATRIX mNext = GetRotationMatrixForSegment( (segment + 1) % (coords.size() - 1), coords );


So my next thoughts are that the real problem is partly the usage and partly the actual function. It works fine for unconnected pipes, but its making a few simplfications and the algebra is just a bit screwed ([embarrass]).

Step 4: Fix the code!

Okay, bit of a jump from 3-4 but I'd be stretching it out if I went any further.

I realised that the addressing for next/current/previous was a bit broken (the pipe isn't continuous, so the wrap-around modulus was wrong). I also figured that computing the vector wasn't the job of the small function quoted above. I factored this out and re-wrote it like so:

// Determine the incoming vector: previous->current
Utils::IntegerVector InVec;
if( segment < 1 ) // Can't use (segment-1)<0 due to segment being UINT
{
// special case: incoming vector at the first segment should just
// be a copy of the outgoing vector as there are no previous segments
InVec.x = coords.at( segment + 1 ).x - coords.at( segment ).x;
InVec.y = coords.at( segment + 1 ).y - coords.at( segment ).y;
InVec.z = coords.at( segment + 1 ).z - coords.at( segment ).z;
}
else
{
// expected case: do a simple (to - from) vector calculation
InVec.x = coords.at( segment ).x - coords.at( segment - 1 ).x;
InVec.y = coords.at( segment ).y - coords.at( segment - 1 ).y;
InVec.z = coords.at( segment ).z - coords.at( segment - 1 ).z;
}

// Construct a matrix to represent the incoming vector
D3DXMATRIX mIn = GetRotationMatrixForVector( InVec );

// Determine the outgoing vector: current->next
Utils::IntegerVector OutVec;
if( (segment + 1) >= coords.size() )
{
// special case: outgoing vector at the last segment has to be the
// same as the incoming vector as there are no further segments
OutVec.x = coords.at( segment ).x - coords.at( segment - 1 ).x;
OutVec.y = coords.at( segment ).y - coords.at( segment - 1 ).y;
OutVec.z = coords.at( segment ).z - coords.at( segment - 1 ).z;
}
else
{
// expected case: do a simple (to - from) vector calculation
OutVec.x = coords.at( segment + 1 ).x - coords.at( segment ).x;
OutVec.y = coords.at( segment + 1 ).y - coords.at( segment ).y;
OutVec.z = coords.at( segment + 1 ).z - coords.at( segment ).z;
}

// Construct a matrix to represent the outgoing vector
D3DXMATRIX mOut = GetRotationMatrixForVector( OutVec );




The hawks amongst you will have noticed the introduction of GetRotationMatrixForVector() - this is a cleaned up version of the prime suspect in the previous section. It looks like this:

D3DXMATRIX ForwardRenderer::GetRotationMatrixForVector( const Utils::IntegerVector& vec )
{
D3DXMATRIX mRet;
D3DXMatrixIdentity( &mRet );

// Handle vectors going in/out along the X axis
if( (vec.x != 0) && (vec.y == 0) && (vec.z == 0) )
{
if( vec.x < 0 )
{
D3DXMatrixRotationZ( &mRet, D3DX_PI / 2.0f );
}
else
{
D3DXMatrixRotationZ( &mRet, -D3DX_PI / 2.0f );
}
}

// Note: Y axis currently ignored

// Handle vectors going in/out along the Z axis
if( (vec.x == 0) && (vec.y == 0) && (vec.z != 0) )
{
if( vec.z < 0 )
{
D3DXMatrixRotationX( &mRet, -D3DX_PI / 2.0f );
}
else
{
D3DXMatrixRotationX( &mRet, D3DX_PI / 2.0f );
}
}

return mRet;
}




Running my test-case now gives the following image:


Exhibit G



Step 5: Test the fix

Okay, so i've got the intended results for my reproducible test case. That's good, but until I've verified it on real data then it's meaningless.

So, this step is basically the inverse of step 2. All I really need to do is uncomment out the fixed pattern code and see what happens:


Exhibit H


All looks good to me [grin]

Step 6: Increase the variables

The first thing that this journal covered was 'flattening' the problem space from 3D to 2D. The fix that was just implemented solves for 2D but doesn't handle 3D and it's 3D that I need.

So, by undoing the work in step-1 I can get back to 3D and attempt to fix up the problems with the Y axis:


Exhibit I


So a trivial flipping on the Y axis doesn't really work. Damn.

The flip basically means that the vertices don't line up and the vertex blend effectively twists the pipe segment. Rotations alone can't actually solve this, but using a negative scale matrix gets good enough results:


Exhibit J


The remaining oddness about the joins is inherant to the way that my vertex blend approach works. That is a whole different issue that I intend to consider in the near future - but as far as this particular bug goes I can declare it fixed [grin]

If I ramp up the LOD and remove wire-frame, we now get:


Exhibit K






So I've pretty much fixed the whole issue and now have a working algorithm. Yay!

If you want to have a play around, see change set 9503 in the repository.

Key points:
  • Reproducibility. You need a consistend reproducible test case, without one you cannot objectively state the problem nor can you objectively determine the problem as solved.
  • Changing the codebase. Sometimes you have to do more 'damage' to the code to find the solution.
  • Visuals. Solving problems with data and logic using visual means (both runtime and offline diagrams) is very useful. Your brain prefers images to pages of text-only debug output.
  • Process. Randomly bashing away at your keyboard and recompiling is unlikely to get you anywhere. Ensure you define what the problem is, what the successful solution looks/behaves like and take it step-by-step. Not to say you always know the steps or you alwayss follow the same ones, but bite-sized chunks are a good thing!


If nothing else, hopefully this journal entry will be of use to those not so familiar with the problem solving aspect of programming.

You may now post comments mocking my crap code and wondering why I got it so wrong in the first place [embarrass]...
Sign in to follow this  


6 Comments


Recommended Comments

Man, that must've taken the whole day to write. Thanks for sharing, though [smile].

You need more consistency in naming variables, by the way. "InVec" and "OutVec" start with upper-case, contrary to all other variables. And "segment_id" uses lower_case_separated_by_underscore while the rest of your code uses firstCamelCase.

Share this comment


Link to comment
Quote:
that must've taken the whole day to write.
Almost - from start to finish would've been about 5 hours [lol] I probably would've solved the bug in under an hour if it weren't for documenting it [lol]

Exhibit B and D were done using Powerpoint - they took about an hour to do [headshake]

Quote:
You need more consistency in naming variables
Yup, I'm shockingly bad with that sort of thing and I don't know why! I really need to get some static code-analysis tools in...

Jack

Share this comment


Link to comment
Debugging skills are entirely overlooked as one of the most important skills for developers. I'd rather take a developer that can debug code 50% faster than a developer that can write code 50% faster. You only write a piece of code once. You'll probably debug through that code countless times.

Giving n00bs this type of real world debugging sample is great. Too bad they're all too lazy to read it. :)

Share this comment


Link to comment
Quote:
that's so long that it should qualify as some type of contribution to the site
The "mini articles" I write in this journal always have the possibility of being proper articles for the main page. But the quality standards are that bit lower, so I don't have to plan and research it in quite the same way.
Quote:
Too bad they're all too lazy to read it
[lol] That is a sad truth really! But if I can point a couple of people to this article then I've done my bit - if they're too lazy to read it then eventually they'll be too lazy to breath and hence work themselves out of the gene pool [evil]

My line manager at IBM told me that the main thing he looks for in a new technical employee is their ability to debug and test code. He also lamented that it was very hard to find strong examples [headshake]

Share this comment


Link to comment
Quote:
Original post by Mike Bossy
I'd rather take a developer that can debug code 50% faster than a developer that can write code 50% faster.

Of course, what you'd really want is a developer that writes 50% fewer bugs in the first place. :)

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now