2 ===========================================================================
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
26 ===========================================================================
29 #include "../precompiled.h"
35 idSurface_Patch::SetSize
38 void idSurface_Patch::SetSize( int patchWidth, int patchHeight ) {
39 if ( patchWidth < 1 || patchWidth > maxWidth ) {
40 idLib::common->FatalError("idSurface_Patch::SetSize: invalid patchWidth");
42 if ( patchHeight < 1 || patchHeight > maxHeight ) {
43 idLib::common->FatalError("idSurface_Patch::SetSize: invalid patchHeight");
47 verts.SetNum( width * height, false );
52 idSurface_Patch::PutOnCurve
54 Expects an expanded patch.
57 void idSurface_Patch::PutOnCurve( void ) {
59 idDrawVert prev, next;
61 assert( expanded == true );
62 // put all the approximating points on the curve
63 for ( i = 0; i < width; i++ ) {
64 for ( j = 1; j < height; j += 2 ) {
65 LerpVert( verts[j*maxWidth+i], verts[(j+1)*maxWidth+i], prev );
66 LerpVert( verts[j*maxWidth+i], verts[(j-1)*maxWidth+i], next );
67 LerpVert( prev, next, verts[j*maxWidth+i] );
71 for ( j = 0; j < height; j++ ) {
72 for ( i = 1; i < width; i += 2 ) {
73 LerpVert( verts[j*maxWidth+i], verts[j*maxWidth+i+1], prev );
74 LerpVert( verts[j*maxWidth+i], verts[j*maxWidth+i-1], next );
75 LerpVert( prev, next, verts[j*maxWidth+i] );
82 idSurface_Patch::ProjectPointOntoVector
85 void idSurface_Patch::ProjectPointOntoVector( const idVec3 &point, const idVec3 &vStart, const idVec3 &vEnd, idVec3 &vProj ) {
88 pVec = point - vStart;
91 // project onto the directional vector for this segment
92 vProj = vStart + (pVec * vec) * vec;
97 idSurface_Patch::RemoveLinearColumnsRows
99 Expects an expanded patch.
102 void idSurface_Patch::RemoveLinearColumnsRows( void ) {
104 float len, maxLength;
107 assert( expanded == true );
108 for ( j = 1; j < width - 1; j++ ) {
110 for ( i = 0; i < height; i++ ) {
111 idSurface_Patch::ProjectPointOntoVector( verts[i*maxWidth + j].xyz,
112 verts[i*maxWidth + j-1].xyz, verts[i*maxWidth + j+1].xyz, proj);
113 dir = verts[i*maxWidth + j].xyz - proj;
114 len = dir.LengthSqr();
115 if ( len > maxLength ) {
119 if ( maxLength < Square( 0.2f ) ) {
121 for ( i = 0; i < height; i++ ) {
122 for ( k = j; k < width; k++ ) {
123 verts[i*maxWidth + k] = verts[i*maxWidth + k+1];
129 for ( j = 1; j < height - 1; j++ ) {
131 for ( i = 0; i < width; i++ ) {
132 idSurface_Patch::ProjectPointOntoVector( verts[j*maxWidth + i].xyz,
133 verts[(j-1)*maxWidth + i].xyz, verts[(j+1)*maxWidth + i].xyz, proj);
134 dir = verts[j*maxWidth + i].xyz - proj;
135 len = dir.LengthSqr();
136 if ( len > maxLength ) {
140 if ( maxLength < Square( 0.2f ) ) {
142 for ( i = 0; i < width; i++ ) {
143 for ( k = j; k < height; k++ ) {
144 verts[k*maxWidth + i] = verts[(k+1)*maxWidth + i];
154 idSurface_Patch::ResizeExpanded
157 void idSurface_Patch::ResizeExpanded( int newHeight, int newWidth ) {
160 assert( expanded == true );
161 if ( newHeight <= maxHeight && newWidth <= maxWidth ) {
164 if ( newHeight * newWidth > maxHeight * maxWidth ) {
165 verts.SetNum( newHeight * newWidth );
167 // space out verts for new height and width
168 for ( j = maxHeight-1; j >= 0; j-- ) {
169 for ( i = maxWidth-1; i >= 0; i-- ) {
170 verts[j*newWidth + i] = verts[j*maxWidth + i];
173 maxHeight = newHeight;
179 idSurface_Patch::Collapse
182 void idSurface_Patch::Collapse( void ) {
186 idLib::common->FatalError("idSurface_Patch::Collapse: patch not expanded");
189 if ( width != maxWidth ) {
190 for ( j = 0; j < height; j++ ) {
191 for ( i = 0; i < width; i++ ) {
192 verts[j*width + i] = verts[j*maxWidth + i];
196 verts.SetNum( width * height, false );
201 idSurface_Patch::Expand
204 void idSurface_Patch::Expand( void ) {
208 idLib::common->FatalError("idSurface_Patch::Expand: patch alread expanded");
211 verts.SetNum( maxWidth * maxHeight, false );
212 if ( width != maxWidth ) {
213 for ( j = height-1; j >= 0; j-- ) {
214 for ( i = width-1; i >= 0; i-- ) {
215 verts[j*maxWidth + i] = verts[j*width + i];
223 idSurface_Patch::LerpVert
226 void idSurface_Patch::LerpVert( const idDrawVert &a, const idDrawVert &b, idDrawVert &out ) const {
227 out.xyz[0] = 0.5f * ( a.xyz[0] + b.xyz[0] );
228 out.xyz[1] = 0.5f * ( a.xyz[1] + b.xyz[1] );
229 out.xyz[2] = 0.5f * ( a.xyz[2] + b.xyz[2] );
230 out.normal[0] = 0.5f * ( a.normal[0] + b.normal[0] );
231 out.normal[1] = 0.5f * ( a.normal[1] + b.normal[1] );
232 out.normal[2] = 0.5f * ( a.normal[2] + b.normal[2] );
233 out.st[0] = 0.5f * ( a.st[0] + b.st[0] );
234 out.st[1] = 0.5f * ( a.st[1] + b.st[1] );
239 idSurface_Patch::GenerateNormals
241 Handles all the complicated wrapping and degenerate cases
242 Expects a Not expanded patch.
245 #define COPLANAR_EPSILON 0.1f
247 void idSurface_Patch::GenerateNormals( void ) {
255 idVec3 around[8], temp;
257 bool wrapWidth, wrapHeight;
258 static int neighbors[8][2] = {
259 {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
262 assert( expanded == false );
265 // if all points are coplanar, set all normals to that plane
270 extent[0] = verts[width - 1].xyz - verts[0].xyz;
271 extent[1] = verts[(height-1) * width + width - 1].xyz - verts[0].xyz;
272 extent[2] = verts[(height-1) * width].xyz - verts[0].xyz;
274 norm = extent[0].Cross( extent[1] );
275 if ( norm.LengthSqr() == 0.0f ) {
276 norm = extent[0].Cross( extent[2] );
277 if ( norm.LengthSqr() == 0.0f ) {
278 norm = extent[1].Cross( extent[2] );
282 // wrapped patched may not get a valid normal here
283 if ( norm.Normalize() != 0.0f ) {
285 offset = verts[0].xyz * norm;
286 for ( i = 1; i < width * height; i++ ) {
287 float d = verts[i].xyz * norm;
288 if ( idMath::Fabs( d - offset ) > COPLANAR_EPSILON ) {
293 if ( i == width * height ) {
295 for ( i = 0; i < width * height; i++ ) {
296 verts[i].normal = norm;
302 // check for wrapped edge cases, which should smooth across themselves
304 for ( i = 0; i < height; i++ ) {
305 delta = verts[i * width].xyz - verts[i * width + width-1].xyz;
306 if ( delta.LengthSqr() > Square( 1.0f ) ) {
315 for ( i = 0; i < width; i++ ) {
316 delta = verts[i].xyz - verts[(height-1) * width + i].xyz;
317 if ( delta.LengthSqr() > Square( 1.0f ) ) {
325 for ( i = 0; i < width; i++ ) {
326 for ( j = 0; j < height; j++ ) {
328 base = verts[j * width + i].xyz;
329 for ( k = 0; k < 8; k++ ) {
330 around[k] = vec3_origin;
333 for ( dist = 1; dist <= 3; dist++ ) {
334 x = i + neighbors[k][0] * dist;
335 y = j + neighbors[k][1] * dist;
339 } else if ( x >= width ) {
346 } else if ( y >= height ) {
351 if ( x < 0 || x >= width || y < 0 || y >= height ) {
352 break; // edge of patch
354 temp = verts[y * width + x].xyz - base;
355 if ( temp.Normalize() == 0.0f ) {
356 continue; // degenerate edge, get more dist
366 for ( k = 0; k < 8; k++ ) {
367 if ( !good[k] || !good[(k+1)&7] ) {
368 continue; // didn't get two points
370 norm = around[(k+1)&7].Cross( around[k] );
371 if ( norm.Normalize() == 0.0f ) {
378 //idLib::common->Printf("bad normal\n");
381 verts[j * width + i].normal = sum;
382 verts[j * width + i].normal.Normalize();
389 idSurface_Patch::GenerateIndexes
392 void idSurface_Patch::GenerateIndexes( void ) {
393 int i, j, v1, v2, v3, v4, index;
395 indexes.SetNum( (width-1) * (height-1) * 2 * 3, false );
397 for ( i = 0; i < width - 1; i++ ) {
398 for ( j = 0; j < height - 1; j++ ) {
403 indexes[index++] = v1;
404 indexes[index++] = v3;
405 indexes[index++] = v2;
406 indexes[index++] = v1;
407 indexes[index++] = v4;
408 indexes[index++] = v3;
412 GenerateEdgeIndexes();
417 idSurface_Patch::SampleSinglePatchPoint
420 void idSurface_Patch::SampleSinglePatchPoint( const idDrawVert ctrl[3][3], float u, float v, idDrawVert *out ) const {
425 // find the control points for the v coordinate
426 for ( vPoint = 0; vPoint < 3; vPoint++ ) {
427 for ( axis = 0; axis < 8; axis++ ) {
431 a = ctrl[0][vPoint].xyz[axis];
432 b = ctrl[1][vPoint].xyz[axis];
433 c = ctrl[2][vPoint].xyz[axis];
434 } else if ( axis < 6 ) {
435 a = ctrl[0][vPoint].normal[axis-3];
436 b = ctrl[1][vPoint].normal[axis-3];
437 c = ctrl[2][vPoint].normal[axis-3];
439 a = ctrl[0][vPoint].st[axis-6];
440 b = ctrl[1][vPoint].st[axis-6];
441 c = ctrl[2][vPoint].st[axis-6];
443 qA = a - 2.0f * b + c;
444 qB = 2.0f * b - 2.0f * a;
446 vCtrl[vPoint][axis] = qA * u * u + qB * u + qC;
450 // interpolate the v value
451 for ( axis = 0; axis < 8; axis++ ) {
458 qA = a - 2.0f * b + c;
459 qB = 2.0f * b - 2.0f * a;
463 out->xyz[axis] = qA * v * v + qB * v + qC;
464 } else if ( axis < 6 ) {
465 out->normal[axis-3] = qA * v * v + qB * v + qC;
467 out->st[axis-6] = qA * v * v + qB * v + qC;
474 idSurface_Patch::SampleSinglePatch
477 void idSurface_Patch::SampleSinglePatch( const idDrawVert ctrl[3][3], int baseCol, int baseRow, int width, int horzSub, int vertSub, idDrawVert *outVerts ) const {
483 for ( i = 0; i < horzSub; i++ ) {
484 for ( j = 0; j < vertSub; j++ ) {
485 u = (float) i / ( horzSub - 1 );
486 v = (float) j / ( vertSub - 1 );
487 SampleSinglePatchPoint( ctrl, u, v, &outVerts[((baseRow + j) * width) + i + baseCol] );
494 idSurface_Patch::SubdivideExplicit
497 void idSurface_Patch::SubdivideExplicit( int horzSubdivisions, int vertSubdivisions, bool genNormals, bool removeLinear ) {
499 idDrawVert sample[3][3];
500 int outWidth = ((width - 1) / 2 * horzSubdivisions) + 1;
501 int outHeight = ((height - 1) / 2 * vertSubdivisions) + 1;
502 idDrawVert *dv = new idDrawVert[ outWidth * outHeight ];
504 // generate normals for the control mesh
510 for ( i = 0; i + 2 < width; i += 2 ) {
512 for ( j = 0; j + 2 < height; j += 2 ) {
513 for ( k = 0; k < 3; k++ ) {
514 for ( l = 0; l < 3; l++ ) {
515 sample[k][l] = verts[ ((j + l) * width) + i + k ];
518 SampleSinglePatch( sample, baseCol, baseRow, outWidth, horzSubdivisions, vertSubdivisions, dv );
519 baseRow += vertSubdivisions;
521 baseCol += horzSubdivisions;
523 verts.SetNum( outWidth * outHeight );
524 for ( i = 0; i < outWidth * outHeight; i++ ) {
530 width = maxWidth = outWidth;
531 height = maxHeight = outHeight;
534 if ( removeLinear ) {
536 RemoveLinearColumnsRows();
540 // normalize all the lerped normals
542 for ( i = 0; i < width * height; i++ ) {
543 verts[i].normal.Normalize();
552 idSurface_Patch::Subdivide
555 void idSurface_Patch::Subdivide( float maxHorizontalError, float maxVerticalError, float maxLength, bool genNormals ) {
557 idDrawVert prev, next, mid;
558 idVec3 prevxyz, nextxyz, midxyz;
560 float maxHorizontalErrorSqr, maxVerticalErrorSqr, maxLengthSqr;
562 // generate normals for the control mesh
567 maxHorizontalErrorSqr = Square( maxHorizontalError );
568 maxVerticalErrorSqr = Square( maxVerticalError );
569 maxLengthSqr = Square( maxLength );
573 // horizontal subdivisions
574 for ( j = 0; j + 2 < width; j += 2 ) {
575 // check subdivided midpoints against control points
576 for ( i = 0; i < height; i++ ) {
577 for ( l = 0; l < 3; l++ ) {
578 prevxyz[l] = verts[i*maxWidth + j+1].xyz[l] - verts[i*maxWidth + j ].xyz[l];
579 nextxyz[l] = verts[i*maxWidth + j+2].xyz[l] - verts[i*maxWidth + j+1].xyz[l];
580 midxyz[l] = (verts[i*maxWidth + j ].xyz[l] + verts[i*maxWidth + j+1].xyz[l] * 2.0f +
581 verts[i*maxWidth + j+2].xyz[l] ) * 0.25f;
584 if ( maxLength > 0.0f ) {
585 // if the span length is too long, force a subdivision
586 if ( prevxyz.LengthSqr() > maxLengthSqr || nextxyz.LengthSqr() > maxLengthSqr ) {
590 // see if this midpoint is off far enough to subdivide
591 delta = verts[i*maxWidth + j+1].xyz - midxyz;
592 if ( delta.LengthSqr() > maxHorizontalErrorSqr ) {
598 continue; // didn't need subdivision
601 if ( width + 2 >= maxWidth ) {
602 ResizeExpanded( maxHeight, maxWidth + 4 );
605 // insert two columns and replace the peak
608 for ( i = 0; i < height; i++ ) {
609 idSurface_Patch::LerpVert( verts[i*maxWidth + j ], verts[i*maxWidth + j+1], prev );
610 idSurface_Patch::LerpVert( verts[i*maxWidth + j+1], verts[i*maxWidth + j+2], next );
611 idSurface_Patch::LerpVert( prev, next, mid );
613 for ( k = width - 1; k > j + 3; k-- ) {
614 verts[i*maxWidth + k] = verts[i*maxWidth + k-2];
616 verts[i*maxWidth + j+1] = prev;
617 verts[i*maxWidth + j+2] = mid;
618 verts[i*maxWidth + j+3] = next;
621 // back up and recheck this set again, it may need more subdivision
625 // vertical subdivisions
626 for ( j = 0; j + 2 < height; j += 2 ) {
627 // check subdivided midpoints against control points
628 for ( i = 0; i < width; i++ ) {
629 for ( l = 0; l < 3; l++ ) {
630 prevxyz[l] = verts[(j+1)*maxWidth + i].xyz[l] - verts[j*maxWidth + i].xyz[l];
631 nextxyz[l] = verts[(j+2)*maxWidth + i].xyz[l] - verts[(j+1)*maxWidth + i].xyz[l];
632 midxyz[l] = (verts[j*maxWidth + i].xyz[l] + verts[(j+1)*maxWidth + i].xyz[l] * 2.0f +
633 verts[(j+2)*maxWidth + i].xyz[l] ) * 0.25f;
636 if ( maxLength > 0.0f ) {
637 // if the span length is too long, force a subdivision
638 if ( prevxyz.LengthSqr() > maxLengthSqr || nextxyz.LengthSqr() > maxLengthSqr ) {
642 // see if this midpoint is off far enough to subdivide
643 delta = verts[(j+1)*maxWidth + i].xyz - midxyz;
644 if ( delta.LengthSqr() > maxVerticalErrorSqr ) {
650 continue; // didn't need subdivision
653 if ( height + 2 >= maxHeight ) {
654 ResizeExpanded( maxHeight + 4, maxWidth );
657 // insert two columns and replace the peak
660 for ( i = 0; i < width; i++ ) {
661 LerpVert( verts[j*maxWidth + i], verts[(j+1)*maxWidth + i], prev );
662 LerpVert( verts[(j+1)*maxWidth + i], verts[(j+2)*maxWidth + i], next );
663 LerpVert( prev, next, mid );
665 for ( k = height - 1; k > j + 3; k-- ) {
666 verts[k*maxWidth + i] = verts[(k-2)*maxWidth + i];
668 verts[(j+1)*maxWidth + i] = prev;
669 verts[(j+2)*maxWidth + i] = mid;
670 verts[(j+3)*maxWidth + i] = next;
673 // back up and recheck this set again, it may need more subdivision
679 RemoveLinearColumnsRows();
683 // normalize all the lerped normals
685 for ( i = 0; i < width * height; i++ ) {
686 verts[i].normal.Normalize();