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.../* 0123450 /1 ||2 /-/\-3 \-\/-/4 ||5 \/*/Utils::CoordinateList pCoords;// Top arrowpCoords.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 arrowpCoords.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 arrowpCoords.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 arrowpCoords.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 againpCoords.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->currentUtils::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 vectorD3DXMATRIX mIn = GetRotationMatrixForVector( InVec );// Determine the outgoing vector: current->nextUtils::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 vectorD3DXMATRIX 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]...
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.