?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fixed: auto_ptr -> unique_ptr
[opensg.git] / Source / System / NodeCores / Drawables / Nurbs / Internal / OSGErrorQuadTree.cpp
blob8c268d5541b29aa56925563246973a55adff1788
1 /*---------------------------------------------------------------------------*\
2 * OpenSG NURBS Library *
3 * *
4 * *
5 * Copyright (C) 2001-2006 by the University of Bonn, Computer Graphics Group*
6 * *
7 * http://cg.cs.uni-bonn.de/ *
8 * *
9 * contact: edhellon@cs.uni-bonn.de, guthe@cs.uni-bonn.de, rk@cs.uni-bonn.de *
10 * *
11 \*---------------------------------------------------------------------------*/
12 /*---------------------------------------------------------------------------*\
13 * License *
14 * *
15 * This library is free software; you can redistribute it and/or modify it *
16 * under the terms of the GNU Library General Public License as published *
17 * by the Free Software Foundation, version 2. *
18 * *
19 * This library is distributed in the hope that it will be useful, but *
20 * WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
22 * Library General Public License for more details. *
23 * *
24 * You should have received a copy of the GNU Library General Public *
25 * License along with this library; if not, write to the Free Software *
26 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
27 * *
28 \*---------------------------------------------------------------------------*/
29 /*---------------------------------------------------------------------------*\
30 * Changes *
31 * *
32 * *
33 * *
34 * *
35 * *
36 * *
37 \*---------------------------------------------------------------------------*/
38 #include "OSGErrorQuadTree.h"
39
40 #include "OSGDCTPMesh.h"
41 #include "OSGBezierTensorSurface.h"
42 #include "OSGBSplineTensorSurface.h"
43
44
45
46 #include <stdlib.h>
47 #include <float.h>
48
49 OSG_USING_NAMESPACE
50
51
52 //#define min( a, b ) ( ( ( a ) < ( b ) ) ? ( a ) : ( b ) )
53 //#define max( a, b ) ( ( ( a ) > ( b ) ) ? ( a ) : ( b ) )
54
55 //#define OSG_EUCLID_ERRORS
56
57 #ifdef _DEBUG
58 #ifdef WIN32
59 #undef THIS_FILE
60 static char THIS_FILE[] = __FILE__;
61 #endif
62 #endif
63
64 bool CErrorQuadTree::m_sbNormalApproximation = false;
65
66 CErrorQuadTree::CErrorQuadTree() :
67 m_fMaxError (-1.0 ),
68 #ifdef OSG_USE_NURBS_PATCH
69 m_ptRoot (NULL ),
70 #else
71 m_vvptRoot ( ),
72 m_ptBPRoot (NULL ),
73 #endif
74 m_fErrorCutoff(DCTP_EPS)
75 {
76 }
77
78
79 CErrorQuadTree::~CErrorQuadTree()
80 {
81 #ifdef OSG_USE_NURBS_PATCH
82 if(m_ptRoot)
83 {
84 DeleteNode(m_ptRoot);
85 #ifdef OSG_ONE_CHILD_PTR
86 delete m_ptRoot;
87 m_ptRoot = NULL;
88 #endif
89 }
90 #else
91 const unsigned int cui_size_u = m_vvptRoot.size();
92
93 if(cui_size_u)
94 {
95 const unsigned int cui_size_v = m_vvptRoot[0].size();
96 unsigned int ui_u;
97 unsigned int ui_v;
98
99 for(ui_u = 0; ui_u < cui_size_u; ++ui_u)
100 {
101 for(ui_v = 0; ui_v < cui_size_v; ++ui_v)
102 {
103 DeleteNode(m_vvptRoot[ui_u][ui_v]);
104 #ifdef OSG_ONE_CHILD_PTR
105 delete m_vvptRoot[ui_u][ui_v];
106 m_vvptRoot[ui_u][ui_v] = NULL;
107 #endif
108 }
109 }
110
111 m_vvptRoot.clear();
112 }
113
114 if(m_ptBPRoot)
115 {
116 DeleteBPNode(m_ptBPRoot);
117 }
118 #endif
119 }
120
121
122 //#ifndef OSG_ARBITRARY_SPLIT
123 void CErrorQuadTree::BuildMesh(DCTPMesh *pclMesh,
124 #ifdef OSG_USE_NURBS_PATCH
125 BSplineTensorSurface *pclPatch,
126 #ifdef OSG_ARBITRARY_SPLIT
127 const Vec2d cclMinParam, const Vec2d cclMaxParam,
128 #endif
129 #else
130 std::vector<std::vector<BezierTensorSurface> > *pvvclPatches,
131 const std::vector<double> *cpvdIntervalsU,
132 const std::vector<double> *cpvdIntervalsV,
133 #endif
134 float fError, float &rfMinError, float &rfMaxError)
135 {
136 pclMesh->reinit();
137 #ifdef OSG_USE_NURBS_PATCH
138 #ifdef OSG_ARBITRARY_SPLIT
139 SetInitialCells(pclMesh, fError, pclPatch, cclMinParam, cclMaxParam);
140
141 if( (cclMaxParam[0] - cclMinParam[0] < DCTP_EPS) ||
142 (cclMaxParam[1] - cclMinParam[1] < DCTP_EPS) )
143 {
144 return;
145 }
146 #else
147 SetInitialCells(pclMesh, fError, pclPatch);
148 #endif
149 #else
150 SetInitialCells(pclMesh, fError, pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
151 #endif
152
153 unsigned int ui_face;
154 unsigned int ui_face_cnt = UInt32(pclMesh->faces.size());
155 DCTPFace *pcl_face;
156 SFaceTreeCell *pt_finfo;
157 float f_act_error;
158 float f_prev_error;
159
160 rfMinError = -1.0;
161 rfMaxError = FLT_MAX;
162
163 if(fError < m_fErrorCutoff)
164 {
165 fError = m_fErrorCutoff;
166 }
167
168 if( (fError >= m_fMaxError) && (m_fMaxError >= 0.0) )
169 {
170 // ok, we already have a subdivision for that error...
171 for(ui_face = 0; ui_face < ui_face_cnt; ++ui_face)
172 {
173 pcl_face = pclMesh->faces[ui_face];
174 if(pcl_face->faceinfo)
175 {
176 f_prev_error = FLT_MAX;
177 #ifdef OSG_USE_NURBS_PATCH
178 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
179 while(f_act_error > fError)
180 {
181 // std::cerr << ",";
182 #ifdef OSG_USE_KD_TREE
183 #ifdef OSG_ARBITRARY_SPLIT
184 if( (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fSplitValue < 0.0)
185 #else
186 if( (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->bSplitHoriz)
187 #endif
188 {
189 #ifdef OSG_ARBITRARY_SPLIT
190 pclMesh->SubdivideQuadEW(pcl_face, -(static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fSplitValue);
191 #else
192 pclMesh->SubdivideQuadEW(pcl_face);
193 #endif
194 }
195 else
196 {
197 #ifdef OSG_ARBITRARY_SPLIT
198 pclMesh->SubdivideQuadNS(pcl_face, (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fSplitValue);
199 #else
200 pclMesh->SubdivideQuadNS(pcl_face);
201 #endif
202 }
203 SubdivideNode(pclMesh, pcl_face);
204 ++ui_face_cnt; // one new face
205 #else
206 pclMesh->SubdivideQuad(pcl_face);
207 SubdivideNode(pclMesh, pcl_face);
208 ui_face_cnt += 3; // three new faces
209 #endif
210 f_prev_error = f_act_error;
211 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
212 }
213 #else
214 if( (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell)
215 {
216 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
217 while(f_act_error > fError)
218 {
219 pclMesh->SubdivideQuad(pcl_face);
220 SubdivideNode(pclMesh, pcl_face);
221 ui_face_cnt += 3; // three new faces
222 f_prev_error = f_act_error;
223 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
224 }
225 }
226 else
227 {
228 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptBPCell->fError;
229 f_prev_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptBPCell->fPrevError;
230 // std::cerr << pcl_face->orig_quad[ 3 ]->coords << pcl_face->orig_quad[ 1 ]->coords << std::endl;
231 // std::cerr << f_act_error << ", " << f_prev_error << std::endl;
232 }
233 #endif
234 if(f_act_error > rfMinError)
235 {
236 rfMinError = f_act_error;
237 }
238 if(f_prev_error < rfMaxError)
239 {
240 rfMaxError = f_prev_error;
241 }
242 }
243 }
244
245 // delete faceinfo
246 for(ui_face = 0; ui_face < ui_face_cnt; ++ui_face)
247 {
248 pcl_face = pclMesh->faces[ui_face];
249 pt_finfo = static_cast<SFaceTreeCell*>(pcl_face->faceinfo);
250 if(pt_finfo)
251 {
252 delete pt_finfo;
253 pcl_face->faceinfo = NULL;
254 }
255 /* else
256 {
257 pclMesh->removeFace( ui_face );
258 --ui_face;
259 --ui_face_cnt;
260 }*/
261 }
262
263 // std::cerr << "reconstructed " << ui_face_cnt << " faces" << std::endl;
264 /* if( pclMesh->faces.size( ) >= 1000 )
265 {
266 if( fError > m_fErrorCutoff )
267 {
268 std::cerr << "reduce error cutoff: " << m_fErrorCutoff << " -> " << fError << std::endl;
269 m_fErrorCutoff = fError;
270 }
271 }
272 if( fError <= m_fErrorCutoff )
273 {
274 rfMinError = 0.0;
275 }*/
276 return;
277 }
278
279 #ifdef OSG_ARBITRARY_SPLIT
280 #ifndef OSG_USE_NURBS_PATCH
281 #error
282 #endif
283 // create first surface
284 std::vector<BSplineTensorSurface> vcl_surf;
285 double d_split;
286 Vec2d cl_min;
287 Vec2d cl_add;
288
289 pt_finfo = (static_cast<SFaceTreeCell*>(pclMesh->faces[0]->faceinfo) );
290 pt_finfo->bOwnSurface = true;
291 pt_finfo->pclBSplineSurface = new BSplineTensorSurface;
292 *(pt_finfo->pclBSplineSurface) = *pclPatch;
293 pclPatch->getParameterInterval_U(cl_min[0], cl_add[0]);
294 pclPatch->getParameterInterval_V(cl_min[1], cl_add[1]);
295 cl_add -= cl_min;
296
297 d_split = (cclMinParam[0] - cl_min[0]) / cl_add[0];
298 if(d_split > 0.999)
299 d_split = 0.999;
300 if(d_split > DCTP_EPS)
301 {
302 pt_finfo->pclBSplineSurface->subDivisionU(vcl_surf, d_split);
303 *(pt_finfo->pclBSplineSurface) = vcl_surf[1];
304 }
305
306 d_split = (cclMaxParam[0] - cclMinParam[0]) / (cl_add[0] - cclMinParam[0]);
307 if(d_split < 0.001)
308 d_split = 0.001;
309 if(1.0 - d_split > DCTP_EPS)
310 {
311 pt_finfo->pclBSplineSurface->subDivisionU(vcl_surf, d_split);
312 *(pt_finfo->pclBSplineSurface) = vcl_surf[0];
313 }
314
315 d_split = (cclMinParam[1] - cl_min[1]) / cl_add[1];
316 if(d_split > 0.999)
317 d_split = 0.999;
318 if(d_split > DCTP_EPS)
319 {
320 pt_finfo->pclBSplineSurface->subDivisionV(vcl_surf, d_split);
321 *(pt_finfo->pclBSplineSurface) = vcl_surf[1];
322 }
323
324 d_split = (cclMaxParam[1] - cclMinParam[1]) / (cl_add[1] - cclMinParam[1]);
325 if(d_split < 0.001)
326 d_split = 0.001;
327 if(1.0 - d_split > DCTP_EPS)
328 {
329 pt_finfo->pclBSplineSurface->subDivisionV(vcl_surf, d_split);
330 *(pt_finfo->pclBSplineSurface) = vcl_surf[0];
331 }
332
333 vcl_surf.clear();
334 #endif
335
336 // we need to build a new quadtree
337 /* if( ( fError > m_fMaxError * 0.7071068115 ) && ( m_fMaxError >= 0.0 ) )
338 {
339 // new error must be 1 / sqrt( 2 ) or less than old...
340 fError = m_fMaxError * 0.7071068115;
341 }*/
342
343 // init errors if computed for the first time
344 // if( m_fMaxError < 0.0 )
345 {
346 for(ui_face = 0; ui_face < ui_face_cnt; ++ui_face)
347 {
348 pcl_face = pclMesh->faces[ui_face];
349 if(pcl_face->faceinfo)
350 {
351 if( (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell)
352 {
353 ComputeError(pcl_face);
354 }
355 }
356 }
357 }
358
359 // subdivide and get max error
360 m_fMaxError = -1.0;
361
362 for(ui_face = 0; ui_face < ui_face_cnt; ++ui_face)
363 {
364 pcl_face = pclMesh->faces[ui_face];
365 if(pcl_face->faceinfo)
366 {
367 f_prev_error = FLT_MAX;
368 #ifdef OSG_USE_NURBS_PATCH
369 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
370 while(f_act_error > fError)
371 {
372 const SErrorTreeCell* cpt_errcell = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell;
373 bool b_split_ok = true;
374
375 // std::cerr << ".";
376 #ifdef OSG_USE_KD_TREE
377 #ifdef OSG_ARBITRARY_SPLIT
378 if(cpt_errcell->fSplitValue < 0.0)
379 #else
380 if(cpt_errcell->bSplitHoriz)
381 #endif
382 {
383 #ifdef OSG_ARBITRARY_SPLIT
384 const double cd_ratio = osgMin(-cpt_errcell->fSplitValue, 1.0f + cpt_errcell->fSplitValue);
385 #ifdef OSG_UNION_TRI_QUAD
386 if( (pcl_face->orig_face[1]->coords[0] - pcl_face->orig_face[0]->coords[0]) * cd_ratio > DCTP_EPS * 100.0)
387 #else
388 if( (pcl_face->orig_quad[1]->coords[0] - pcl_face->orig_quad[0]->coords[0]) * cd_ratio > DCTP_EPS * 100.0)
389 #endif
390 #else
391 #ifdef OSG_UNION_TRI_QUAD
392 if( (pcl_face->orig_face[1]->coords[0] - pcl_face->orig_face[0]->coords[0]) * 0.5 > DCTP_EPS * 100.0)
393 #else
394 if( (pcl_face->orig_quad[1]->coords[0] - pcl_face->orig_quad[0]->coords[0]) * 0.5 > DCTP_EPS * 100.0)
395 #endif
396 #endif
397 {
398 #ifdef OSG_ARBITRARY_SPLIT
399 pclMesh->SubdivideQuadEW(pcl_face, -cpt_errcell->fSplitValue);
400 #else
401 pclMesh->SubdivideQuadEW(pcl_face);
402 #endif
403 }
404 else
405 {
406 b_split_ok = false;
407 }
408 }
409 else
410 {
411 #ifdef OSG_ARBITRARY_SPLIT
412 const double cd_ratio = osgMin(cpt_errcell->fSplitValue, 1.0f - cpt_errcell->fSplitValue);
413 #ifdef OSG_UNION_TRI_QUAD
414 if( (pcl_face->orig_face[0]->coords[1] - pcl_face->orig_face[3]->coords[1]) * cd_ratio > DCTP_EPS * 100.0)
415 #else
416 if( (pcl_face->orig_quad[0]->coords[1] - pcl_face->orig_quad[3]->coords[1]) * cd_ratio > DCTP_EPS * 100.0)
417 #endif
418 #else
419 #ifdef OSG_UNION_TRI_QUAD
420 if( (pcl_face->orig_face[0]->coords[1] - pcl_face->orig_face[3]->coords[1]) * 0.5 > DCTP_EPS * 100.0)
421 #else
422 if( (pcl_face->orig_quad[0]->coords[1] - pcl_face->orig_quad[3]->coords[1]) * 0.5 > DCTP_EPS * 100.0)
423 #endif
424 #endif
425 {
426 #ifdef OSG_ARBITRARY_SPLIT
427 pclMesh->SubdivideQuadNS(pcl_face, cpt_errcell->fSplitValue);
428 #else
429 pclMesh->SubdivideQuadNS(pcl_face);
430 #endif
431 }
432 else
433 {
434 b_split_ok = false;
435 }
436 }
437 if(b_split_ok)
438 {
439 SubdivideBuild(pclMesh, pcl_face);
440 ++ui_face_cnt; // one new face
441 f_prev_error = f_act_error;
442 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
443 }
444 else
445 {
446 f_prev_error = f_act_error;
447 f_act_error = 0.0;
448 }
449 #else
450 pclMesh->SubdivideQuad(pcl_face);
451 SubdivideBuild(pclMesh, pcl_face);
452 ui_face_cnt += 3; // three new faces
453 f_prev_error = f_act_error;
454 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
455 #endif
456 }
457 #else
458 if( (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell)
459 {
460 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
461 while(f_act_error > fError)
462 {
463 pclMesh->SubdivideQuad(pcl_face);
464 SubdivideBuild(pclMesh, pcl_face);
465 ui_face_cnt += 3; // three new faces
466 f_prev_error = f_act_error;
467 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptErrorCell->fError;
468 }
469 }
470 else
471 {
472 f_act_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptBPCell->fError;
473 f_prev_error = (static_cast<SFaceTreeCell*>(pcl_face->faceinfo) )->ptBPCell->fPrevError;
474 }
475 #endif
476 if(f_act_error > m_fMaxError)
477 {
478 m_fMaxError = f_act_error;
479 rfMinError = f_act_error;
480 }
481 if(f_prev_error < rfMaxError)
482 {
483 rfMaxError = f_prev_error;
484 }
485 }
486 }
487
488 // delete faceinfo and constructed bezier patches
489 for(ui_face = 0; ui_face < ui_face_cnt; ++ui_face)
490 {
491 pcl_face = pclMesh->faces[ui_face];
492 pt_finfo = static_cast<SFaceTreeCell*>(pcl_face->faceinfo);
493 if(pt_finfo)
494 {
495 if(pt_finfo->bOwnSurface)
496 {
497 #ifdef OSG_USE_NURBS_PATCH
498 delete pt_finfo->pclBSplineSurface;
499 #else
500 delete pt_finfo->pclBezierSurface;
501 #endif
502 }
503 delete pt_finfo;
504 pcl_face->faceinfo = NULL;
505 }
506 /* else
507 {
508 pclMesh->removeFace( ui_face );
509 --ui_face;
510 --ui_face_cnt;
511 }*/
512 }
513
514 // std::cerr << "build " << ui_face_cnt << " faces" << std::endl;
515
516 /* if( pclMesh->faces.size( ) >= 1000 )
517 {
518 if( fError > m_fErrorCutoff )
519 {
520 std::cerr << "reduce error cutoff: " << m_fErrorCutoff << " -> " << fError << std::endl;
521 m_fErrorCutoff = fError;
522 }
523 }
524 if( fError <= m_fErrorCutoff )
525 {
526 rfMinError = 0.0;
527 }*/
528
529 // std::cerr << "done" << std::endl;
530
531 return;
532 }
533 //#endif
534
535
536 /*#ifdef OSG_ARBITRARY_SPLIT
537 void CErrorQuadTree::CalculatePoints( std::vector< Vec2d > *pvclInsert, std::vector< Vec2d > *pvclDelete,
538 BSplineTensorSurface *pclPatch,
539 float fError, float &rfMinError, float &rfMaxError )
540 {
541 std::vector< SFaceTreeCell > vt_build_cells;
542 unsigned int ui_cell;
543 unsigned int ui_cell_cnt = 1;
544 float f_act_error;
545 float f_prev_error;
546 float f_old_error;
547 bool b_insert;
548 std::vector< BSplineTensorSurface > vcl_surfaces;
549 Vec2dset scl_check;
550
551 if( fError < m_fErrorCutoff )
552 {
553 fError = m_fErrorCutoff;
554 }
555
556 pvclInsert->clear( );
557 pvclDelete->clear( );
558
559 if( m_fMaxError >= 0.0 )
560 {
561 f_old_error = rfMinError;
562 if( fError <= rfMinError )
563 {
564 b_insert = true;
565 }
566 else if( fError >= rfMaxError )
567 {
568 b_insert = false;
569 }
570 else
571 {
572 return;
573 }
574 }
575 else
576 {
577 f_old_error = FLT_MAX;
578 b_insert = true;
579 }
580
581 if( m_ptRoot == NULL )
582 {
583 m_ptRoot = new SErrorTreeCell;
584 m_ptRoot->ptChildren = NULL;
585 m_ptRoot->fError = -1.0;
586 }
587
588 vt_build_cells.resize( 1 );
589 vt_build_cells[ 0 ].bOwnSurface = false;
590 vt_build_cells[ 0 ].pclBSplineSurface = pclPatch;
591 vt_build_cells[ 0 ].ptErrorCell = m_ptRoot;
592 pclPatch->getParameterInterval_U( vt_build_cells[ 0 ].clMin[0], vt_build_cells[ 0 ].clMax[0] );
593 pclPatch->getParameterInterval_V( vt_build_cells[ 0 ].clMin[1], vt_build_cells[ 0 ].clMax[1] );
594 ComputeError( &( vt_build_cells[ 0 ] ) );
595
596 rfMinError = -1.0;
597 rfMaxError = FLT_MAX;
598
599 if( ( fError >= m_fMaxError ) && ( m_fMaxError >= 0.0 ) )
600 {
601 // ok, we already have a subdivision for that error...
602 for( ui_cell = 0; ui_cell < ui_cell_cnt; ++ui_cell )
603 {
604 f_prev_error = FLT_MAX;
605 f_act_error = vt_build_cells[ ui_cell ].ptErrorCell->fError;
606 while( f_act_error > fError )
607 {
608 vt_build_cells.resize( ui_cell_cnt + 1 );
609 vt_build_cells[ ui_cell_cnt ].bOwnSurface = false;
610 vt_build_cells[ ui_cell_cnt ].pclBSplineSurface = NULL;
611 vt_build_cells[ ui_cell_cnt ].clMin = vt_build_cells[ ui_cell ].clMin;
612 vt_build_cells[ ui_cell_cnt ].clMax = vt_build_cells[ ui_cell ].clMax;
613 vt_build_cells[ ui_cell ].bOwnSurface = false;
614 vt_build_cells[ ui_cell ].pclBSplineSurface = NULL;
615 if( vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue < 0.0 )
616 {
617 vt_build_cells[ ui_cell ].clMax[0] =
618 vt_build_cells[ ui_cell ].clMin[0]
619 - ( vt_build_cells[ ui_cell ].clMax[0] - vt_build_cells[ ui_cell ].clMin[0] )
620 * vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue;
621 vt_build_cells[ ui_cell_cnt ].clMin[0] = vt_build_cells[ ui_cell ].clMax[0];
622 }
623 else
624 {
625 vt_build_cells[ ui_cell ].clMax[1] =
626 vt_build_cells[ ui_cell ].clMin[1]
627 + ( vt_build_cells[ ui_cell ].clMax[1] - vt_build_cells[ ui_cell ].clMin[1] )
628 * vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue;
629 vt_build_cells[ ui_cell_cnt ].clMin[1] = vt_build_cells[ ui_cell ].clMax[1];
630 }
631 // set new error cells
632 vt_build_cells[ ui_cell_cnt ].ptErrorCell = &( vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 1 ] );
633 vt_build_cells[ ui_cell ].ptErrorCell = &( vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 0 ] );
634 if( ( b_insert ) && ( f_act_error >= f_old_error ) )
635 {
636 // insert new points
637 if( scl_check.insert( vt_build_cells[ ui_cell ].clMax ).second )
638 {
639 pvclInsert->push_back( vt_build_cells[ ui_cell ].clMax );
640 }
641 if( scl_check.insert( vt_build_cells[ ui_cell_cnt ].clMin ).second )
642 {
643 pvclInsert->push_back( vt_build_cells[ ui_cell_cnt ].clMin );
644 }
645 }
646 else
647 {
648 scl_check.insert( vt_build_cells[ ui_cell ].clMax );
649 scl_check.insert( vt_build_cells[ ui_cell_cnt ].clMin );
650 }
651 ++ui_cell_cnt; // one new face
652 f_prev_error = f_act_error;
653 f_act_error = vt_build_cells[ ui_cell ].ptErrorCell->fError;
654 }
655 if( f_act_error > rfMinError )
656 {
657 rfMinError = f_act_error;
658 }
659 if( f_prev_error < rfMaxError )
660 {
661 rfMaxError = f_prev_error;
662 }
663 if( !b_insert )
664 {
665 // delete old points
666 while( f_act_error > f_old_error )
667 {
668 vt_build_cells.resize( ui_cell_cnt + 1 );
669 vt_build_cells[ ui_cell_cnt ].bOwnSurface = false;
670 vt_build_cells[ ui_cell_cnt ].pclBSplineSurface = NULL;
671 vt_build_cells[ ui_cell_cnt ].clMin = vt_build_cells[ ui_cell ].clMin;
672 vt_build_cells[ ui_cell_cnt ].clMax = vt_build_cells[ ui_cell ].clMax;
673 vt_build_cells[ ui_cell ].bOwnSurface = false;
674 vt_build_cells[ ui_cell ].pclBSplineSurface = NULL;
675 if( vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue < 0.0 )
676 {
677 vt_build_cells[ ui_cell ].clMax[0] =
678 vt_build_cells[ ui_cell ].clMin[0]
679 - ( vt_build_cells[ ui_cell ].clMax[0] - vt_build_cells[ ui_cell ].clMin[0] )
680 * vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue;
681 vt_build_cells[ ui_cell_cnt ].clMin[0] = vt_build_cells[ ui_cell ].clMax[0];
682 }
683 else
684 {
685 vt_build_cells[ ui_cell ].clMax[1] =
686 vt_build_cells[ ui_cell ].clMin[1]
687 + ( vt_build_cells[ ui_cell ].clMax[1] - vt_build_cells[ ui_cell ].clMin[1] )
688 * vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue;
689 vt_build_cells[ ui_cell_cnt ].clMin[1] = vt_build_cells[ ui_cell ].clMax[1];
690 }
691 // set new error cells
692 vt_build_cells[ ui_cell_cnt ].ptErrorCell = &( vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 1 ] );
693 vt_build_cells[ ui_cell ].ptErrorCell = &( vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 0 ] );
694 if( scl_check.insert( vt_build_cells[ ui_cell ].clMax ).second )
695 {
696 pvclDelete->push_back( vt_build_cells[ ui_cell ].clMax );
697 }
698 if( scl_check.insert( vt_build_cells[ ui_cell_cnt ].clMin ).second )
699 {
700 pvclDelete->push_back( vt_build_cells[ ui_cell_cnt ].clMin );
701 }
702 ++ui_cell_cnt; // one new face
703 f_act_error = vt_build_cells[ ui_cell ].ptErrorCell->fError;
704 }
705 }
706 }
707 vt_build_cells.clear( );
708 return;
709 }
710
711 // we need to build a new Kd-tree
712 for( ui_cell = 0; ui_cell < ui_cell_cnt; ++ui_cell )
713 {
714 f_prev_error = FLT_MAX;
715 f_act_error = vt_build_cells[ ui_cell ].ptErrorCell->fError;
716 while( f_act_error > fError )
717 {
718 if( vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue < 0.0 )
719 {
720 vt_build_cells[ ui_cell ].pclBSplineSurface->subDivisionU(
721 vcl_surfaces, -vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue );
722 }
723 else
724 {
725 vt_build_cells[ ui_cell ].pclBSplineSurface->subDivisionV(
726 vcl_surfaces, vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue );
727 }
728 vt_build_cells.resize( ui_cell_cnt + 1 );
729 vt_build_cells[ ui_cell_cnt ].bOwnSurface = true;
730 vt_build_cells[ ui_cell_cnt ].pclBSplineSurface = new BSplineTensorSurface;
731 *( vt_build_cells[ ui_cell_cnt ].pclBSplineSurface ) = vcl_surfaces[ 1 ];
732 vt_build_cells[ ui_cell_cnt ].clMin = vt_build_cells[ ui_cell ].clMin;
733 vt_build_cells[ ui_cell_cnt ].clMax = vt_build_cells[ ui_cell ].clMax;
734 if( vt_build_cells[ ui_cell ].bOwnSurface )
735 {
736 delete vt_build_cells[ ui_cell ].pclBSplineSurface;
737 }
738 vt_build_cells[ ui_cell ].bOwnSurface = true;
739 vt_build_cells[ ui_cell ].pclBSplineSurface = new BSplineTensorSurface;
740 *( vt_build_cells[ ui_cell ].pclBSplineSurface ) = vcl_surfaces[ 0 ];
741 std::cerr << vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue << std::endl;
742 std::cerr << vt_build_cells[ ui_cell ].clMin << vt_build_cells[ ui_cell ].clMax << std::endl;
743 if( vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue < 0.0 )
744 {
745 vt_build_cells[ ui_cell ].clMax[0] =
746 vt_build_cells[ ui_cell ].clMin[0]
747 - ( vt_build_cells[ ui_cell ].clMax[0] - vt_build_cells[ ui_cell ].clMin[0] )
748 * vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue;
749 vt_build_cells[ ui_cell_cnt ].clMin[0] = vt_build_cells[ ui_cell ].clMax[0];
750 }
751 else
752 {
753 vt_build_cells[ ui_cell ].clMax[1] =
754 vt_build_cells[ ui_cell ].clMin[1]
755 + ( vt_build_cells[ ui_cell ].clMax[1] - vt_build_cells[ ui_cell ].clMin[1] )
756 * vt_build_cells[ ui_cell ].ptErrorCell->fSplitValue;
757 vt_build_cells[ ui_cell_cnt ].clMin[1] = vt_build_cells[ ui_cell ].clMax[1];
758 }
759 std::cerr << vt_build_cells[ ui_cell ].clMin << vt_build_cells[ ui_cell ].clMax << std::endl;
760 std::cerr << vt_build_cells[ ui_cell_cnt ].clMin << vt_build_cells[ ui_cell_cnt ].clMax << std::endl << std::endl;
761 // set new error cells
762 if( vt_build_cells[ ui_cell ].ptErrorCell->ptChildren == NULL )
763 {
764 vt_build_cells[ ui_cell ].ptErrorCell->ptChildren = new SErrorTreeCell[ 2 ];
765 vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 0 ].ptChildren = NULL;
766 vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 0 ].fError = -1.0;
767 vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 1 ].ptChildren = NULL;
768 vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 1 ].fError = -1.0;
769 }
770 vt_build_cells[ ui_cell_cnt ].ptErrorCell = &( vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 1 ] );
771 vt_build_cells[ ui_cell ].ptErrorCell = &( vt_build_cells[ ui_cell ].ptErrorCell->ptChildren[ 0 ] );
772 // compute error
773 ComputeError( &( vt_build_cells[ ui_cell ] ) );
774 ComputeError( &( vt_build_cells[ ui_cell_cnt ] ) );
775 // insert new points
776 if( scl_check.insert( vt_build_cells[ ui_cell ].clMax ).second )
777 {
778 pvclInsert->push_back( vt_build_cells[ ui_cell ].clMax );
779 }
780 if( scl_check.insert( vt_build_cells[ ui_cell_cnt ].clMin ).second )
781 {
782 pvclInsert->push_back( vt_build_cells[ ui_cell_cnt ].clMin );
783 }
784 ++ui_cell_cnt; // one new face
785 f_prev_error = f_act_error;
786 f_act_error = vt_build_cells[ ui_cell ].ptErrorCell->fError;
787 }
788 if( f_act_error > rfMinError )
789 {
790 rfMinError = f_act_error;
791 }
792 if( f_prev_error < rfMaxError )
793 {
794 rfMaxError = f_prev_error;
795 }
796 }
797
798 // delete build cells and constructed bspline patches
799 for( ui_cell = 0; ui_cell < ui_cell_cnt; ++ui_cell )
800 {
801 if( vt_build_cells[ ui_cell ].bOwnSurface )
802 {
803 vt_build_cells[ ui_cell ].pclBSplineSurface;
804 }
805 }
806 vt_build_cells.clear( );
807 }
808 #endif*/
809
810
811 #ifdef OSG_ONE_CHILD_PTR
812 void CErrorQuadTree::DeleteNode(SErrorTreeCell *pclNode)
813 {
814 if(pclNode->ptChildren)
815 {
816 DeleteNode(&(pclNode->ptChildren[0]) );
817 DeleteNode(&(pclNode->ptChildren[1]) );
818 #ifndef OSG_USE_KD_TREE
819 DeleteNode(&(pclNode->ptChildren[2]) );
820 DeleteNode(&(pclNode->ptChildren[3]) );
821 #endif
822 delete[] pclNode->ptChildren;
823 pclNode->ptChildren = NULL;
824 }
825 }
826 #else
827 void CErrorQuadTree::DeleteNode(SErrorTreeCell *&rpclNode)
828 {
829 if(rpclNode->aptChildren[0])
830 {
831 DeleteNode(rpclNode->aptChildren[0]);
832 DeleteNode(rpclNode->aptChildren[1]);
833 #ifndef OSG_USE_KD_TREE
834 DeleteNode(rpclNode->aptChildren[2]);
835 DeleteNode(rpclNode->aptChildren[3]);
836 #endif
837 }
838 delete rpclNode;
839 rpclNode = NULL;
840 }
841 #endif
842
843
844 //#ifndef OSG_ARBITRARY_SPLIT
845 void CErrorQuadTree::SetInitialCells(DCTPMesh *pclMesh, float fError,
846 #ifdef OSG_USE_NURBS_PATCH
847 #ifdef OSG_ARBITRARY_SPLIT
848 BSplineTensorSurface *pclPatch,
849 const Vec2d cclMinParam, const Vec2d cclMaxParam)
850 #else
851 BSplineTensorSurface * pclPatch)
852 #endif
853 #else
854 std::vector<std::vector<BezierTensorSurface> > *pvvclPatches,
855 const std::vector<double> *cpvdIntervalsU,
856 const std::vector<double> *cpvdIntervalsV)
857 #endif
858 {
859 #ifdef OSG_USE_NURBS_PATCH
860 double d_min_x;
861 double d_max_x;
862 double d_min_y;
863 double d_max_y;
864 Vec3d acl_edge_points[4];
865 DCTPFace *pcl_face;
866 SFaceTreeCell *pt_finfo;
867
868 #ifdef OSG_ARBITRARY_SPLIT
869 d_min_x = cclMinParam[0];
870 d_min_y = cclMinParam[1];
871 d_max_x = cclMaxParam[0];
872 d_max_y = cclMaxParam[1];
873 #else
874 pclPatch->getParameterInterval_U(d_min_x, d_max_x);
875 pclPatch->getParameterInterval_V(d_min_y, d_max_y);
876 #endif
877 acl_edge_points[0][0] = d_min_x;
878 acl_edge_points[1][0] = d_max_x;
879 acl_edge_points[2][0] = d_max_x;
880 acl_edge_points[3][0] = d_min_x;
881 acl_edge_points[0][1] = d_max_y;
882 acl_edge_points[1][1] = d_max_y;
883 acl_edge_points[2][1] = d_min_y;
884 acl_edge_points[3][1] = d_min_y;
885 acl_edge_points[0][2] = 0.0;
886 acl_edge_points[1][2] = 0.0;
887 acl_edge_points[2][2] = 0.0;
888 acl_edge_points[3][2] = 0.0;
889
890 if(m_ptRoot == NULL)
891 {
892 m_ptRoot = new SErrorTreeCell;
893 #ifdef OSG_ONE_CHILD_PTR
894 m_ptRoot->ptChildren = NULL;
895 #else
896 m_ptRoot->aptChildren[0] = NULL;
897 m_ptRoot->aptChildren[1] = NULL;
898 m_ptRoot->aptChildren[2] = NULL;
899 m_ptRoot->aptChildren[3] = NULL;
900 #endif
901 m_ptRoot->fError = -1.0;
902 }
903
904 pcl_face = pclMesh->AddQuad(acl_edge_points[0], acl_edge_points[1],
905 acl_edge_points[2], acl_edge_points[3], 0.0);
906 pt_finfo = new SFaceTreeCell;
907 pt_finfo->bOwnSurface = false;
908 #ifdef OSG_ARBITRARY_SPLIT
909 pt_finfo->pclBSplineSurface = NULL;
910 #else
911 pt_finfo->pclBSplineSurface = pclPatch;
912 #endif
913 pt_finfo->ptErrorCell = m_ptRoot;
914 pcl_face->faceinfo = static_cast<void*>(pt_finfo);
915 #else
916 const unsigned int cui_u_size = cpvdIntervalsU->size() - 1;
917 const unsigned int cui_v_size = cpvdIntervalsV->size() - 1;
918 Vec3d acl_edge_points[4];
919 unsigned int ui_u;
920 unsigned int ui_v;
921 DCTPFace *pcl_face;
922 SFaceTreeCell *pt_finfo;
923 unsigned int ui_face;
924 unsigned int ui_face_cnt;
925 float f_act_error;
926
927 acl_edge_points[0][2] = 1.0;
928 acl_edge_points[1][2] = 1.0;
929 acl_edge_points[2][2] = 1.0;
930 acl_edge_points[3][2] = 1.0;
931
932 if(m_vvptRoot.size() == 0)
933 {
934 // std::cerr << "new QuadTree" << std::endl;
935 m_vvptRoot.resize(cui_u_size);
936
937 for(ui_u = 0; ui_u < cui_u_size; ++ui_u)
938 {
939 m_vvptRoot[ui_u].resize(cui_v_size);
940
941 for(ui_v = 0; ui_v < cui_v_size; ++ui_v)
942 {
943 m_vvptRoot[ui_u][ui_v] = new SErrorTreeCell;
944 #ifdef OSG_ONE_CHILD_PTR
945 m_vvptRoot[ui_u][ui_v]->ptChildren = NULL;
946 #else
947 m_vvptRoot[ui_u][ui_v]->aptChildren[0] = NULL;
948 m_vvptRoot[ui_u][ui_v]->aptChildren[1] = NULL;
949 m_vvptRoot[ui_u][ui_v]->aptChildren[2] = NULL;
950 m_vvptRoot[ui_u][ui_v]->aptChildren[3] = NULL;
951 #endif
952 m_vvptRoot[ui_u][ui_v]->fError = -1.0;
953 }
954 }
955
956 ComputeBPTree(pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
957 }
958
959 acl_edge_points[0][0] = (*cpvdIntervalsU)[0];
960 acl_edge_points[1][0] = (*cpvdIntervalsU)[cui_u_size];
961 acl_edge_points[2][0] = (*cpvdIntervalsU)[cui_u_size];
962 acl_edge_points[3][0] = (*cpvdIntervalsU)[0];
963 acl_edge_points[0][1] = (*cpvdIntervalsV)[cui_v_size];
964 acl_edge_points[1][1] = (*cpvdIntervalsV)[cui_v_size];
965 acl_edge_points[2][1] = (*cpvdIntervalsV)[0];
966 acl_edge_points[3][1] = (*cpvdIntervalsV)[0];
967 pcl_face = pclMesh->AddQuad(acl_edge_points[0], acl_edge_points[1],
968 acl_edge_points[2], acl_edge_points[3], 0.0);
969 pt_finfo = new SFaceTreeCell;
970 pt_finfo->bOwnSurface = false;
971 pt_finfo->pclBezierSurface = NULL;
972 pt_finfo->ptErrorCell = NULL;
973 pt_finfo->ptBPCell = m_ptBPRoot;
974 pcl_face->faceinfo = ( void* ) pt_finfo;
975
976 ui_face_cnt = 1;
977
978 for(ui_face = 0; ui_face < ui_face_cnt; ++ui_face)
979 {
980 pcl_face = pclMesh->faces[ui_face];
981 if( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell)
982 {
983 f_act_error = ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->fError;
984 while(f_act_error > fError)
985 {
986 if( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->aptChildren[1])
987 {
988 // xx
989 // xx
990 pclMesh->SubdivideQuad(pcl_face);
991 SubdivideNode(pclMesh, pcl_face);
992 ui_face_cnt += 3;
993 }
994 else if( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->aptChildren[0])
995 {
996 // x
997 // x
998 pclMesh->SubdivideQuadNS(pcl_face);
999 SubdivideNode(pclMesh, pcl_face);
1000 ++ui_face_cnt;
1001 }
1002 else if( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->aptChildren[2])
1003 {
1004 // xx
1005 pclMesh->SubdivideQuadEW(pcl_face);
1006 SubdivideNode(pclMesh, pcl_face);
1007 ++ui_face_cnt;
1008 }
1009 if( ( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell) &&
1010 ( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->aptChildren[3]) )
1011 {
1012 f_act_error = ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->fError;
1013 }
1014 else
1015 {
1016 f_act_error = 0.0;
1017 }
1018 }
1019 }
1020 if( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell == NULL)
1021 {
1022 delete ( ( SFaceTreeCell* ) pcl_face->faceinfo);
1023 pcl_face->faceinfo = NULL;
1024 }
1025 }
1026
1027 for(ui_face = 0; ui_face < ui_face_cnt; ++ui_face)
1028 {
1029 pcl_face = pclMesh->faces[ui_face];
1030 if(pcl_face->faceinfo)
1031 {
1032 /* std::cerr << "quad:";
1033 std::cerr << pcl_face->orig_quad[ 0 ]->coords << " ";
1034 std::cerr << pcl_face->orig_quad[ 1 ]->coords << " ";
1035 std::cerr << pcl_face->orig_quad[ 2 ]->coords << " ";
1036 std::cerr << pcl_face->orig_quad[ 3 ]->coords << std::endl;
1037 std::cerr << ( ( SFaceTreeCell* ) pcl_face->faceinfo )->ptBPCell->uiLeft << " - ";
1038 std::cerr << ( ( SFaceTreeCell* ) pcl_face->faceinfo )->ptBPCell->uiRight << " , ";
1039 std::cerr << ( ( SFaceTreeCell* ) pcl_face->faceinfo )->ptBPCell->uiBottom << " - ";
1040 std::cerr << ( ( SFaceTreeCell* ) pcl_face->faceinfo )->ptBPCell->uiTop << std::endl;*/
1041 #ifdef OSG_UNION_TRI_QUAD
1042 pclMesh->MoveVertex(
1043 pcl_face->orig_face[0],
1044 Vec3d( (*cpvdIntervalsU)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiLeft],
1045 (*cpvdIntervalsV)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiTop + 1],
1046 0.0) );
1047 pclMesh->MoveVertex(
1048 pcl_face->orig_face[1],
1049 Vec3d( (*cpvdIntervalsU)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiRight + 1],
1050 (*cpvdIntervalsV)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiTop + 1],
1051 0.0) );
1052 pclMesh->MoveVertex(
1053 pcl_face->orig_face[2],
1054 Vec3d( (*cpvdIntervalsU)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiRight + 1],
1055 (*cpvdIntervalsV)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiBottom],
1056 0.0) );
1057 pclMesh->MoveVertex(
1058 pcl_face->orig_face[3],
1059 Vec3d( (*cpvdIntervalsU)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiLeft],
1060 (*cpvdIntervalsV)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiBottom],
1061 0.0) );
1062 #else
1063 pclMesh->MoveVertex(
1064 pcl_face->orig_quad[0],
1065 Vec3d( (*cpvdIntervalsU)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiLeft],
1066 (*cpvdIntervalsV)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiTop + 1],
1067 0.0) );
1068 pclMesh->MoveVertex(
1069 pcl_face->orig_quad[1],
1070 Vec3d( (*cpvdIntervalsU)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiRight + 1],
1071 (*cpvdIntervalsV)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiTop + 1],
1072 0.0) );
1073 pclMesh->MoveVertex(
1074 pcl_face->orig_quad[2],
1075 Vec3d( (*cpvdIntervalsU)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiRight + 1],
1076 (*cpvdIntervalsV)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiBottom],
1077 0.0) );
1078 pclMesh->MoveVertex(
1079 pcl_face->orig_quad[3],
1080 Vec3d( (*cpvdIntervalsU)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiLeft],
1081 (*cpvdIntervalsV)[( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiBottom],
1082 0.0) );
1083 #endif
1084 /* std::cerr << "moved to:";
1085 std::cerr << pcl_face->orig_quad[ 0 ]->coords << " ";
1086 std::cerr << pcl_face->orig_quad[ 1 ]->coords << " ";
1087 std::cerr << pcl_face->orig_quad[ 2 ]->coords << " ";
1088 std::cerr << pcl_face->orig_quad[ 3 ]->coords << std::endl;*/
1089 if( ( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->aptChildren[3] == NULL) &&
1090 ( ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->fError > fError) )
1091 {
1092 // single patch
1093 ui_u = ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiLeft;
1094 ui_v = ( ( SFaceTreeCell* ) pcl_face->faceinfo)->ptBPCell->uiBottom;
1095 // std::cerr << ui_u << "," << ui_v << std::endl;
1096 pt_finfo = ( ( SFaceTreeCell* ) pcl_face->faceinfo);
1097 pt_finfo->bOwnSurface = false;
1098 pt_finfo->pclBezierSurface = &( (*pvvclPatches)[ui_u][ui_v]);
1099 pt_finfo->ptErrorCell = m_vvptRoot[ui_u][ui_v];
1100 pt_finfo->ptBPCell = NULL;
1101 // pcl_face->faceinfo = ( void* ) pt_finfo;
1102 }
1103 }
1104 }
1105
1106 #endif
1107 }
1108
1109
1110 void CErrorQuadTree::SubdivideNode(DCTPMesh *pclMesh, DCTPFace *pclFace)
1111 {
1112 const unsigned int cui_face_cnt = UInt32(pclMesh->faces.size());
1113 unsigned int ui_child;
1114 #ifdef OSG_USE_KD_TREE
1115 DCTPFace *apcl_faces[2];
1116 #else
1117 DCTPFace *apcl_faces[4];
1118 #endif
1119 SFaceTreeCell *pcl_old_node = static_cast<SFaceTreeCell*>(pclFace->faceinfo);
1120 SFaceTreeCell *pcl_new_node;
1121
1122 pclFace->faceinfo = NULL;
1123
1124 #ifdef OSG_USE_NURBS_PATCH
1125 apcl_faces[0] = pclFace;
1126 #ifdef OSG_USE_KD_TREE
1127 apcl_faces[1] = pclMesh->faces[cui_face_cnt - 1];
1128 #else
1129 apcl_faces[1] = pclMesh->faces[cui_face_cnt - 3];
1130 apcl_faces[2] = pclMesh->faces[cui_face_cnt - 2];
1131 apcl_faces[3] = pclMesh->faces[cui_face_cnt - 1];
1132 #endif
1133
1134 #ifdef OSG_USE_KD_TREE
1135
1136 for(ui_child = 0; ui_child < 2; ++ui_child)
1137 #else
1138
1139 for(ui_child = 0; ui_child < 4; ++ui_child)
1140 #endif
1141 {
1142 pcl_new_node = new SFaceTreeCell;
1143 // std::cerr << "subdivide with ErrorCell" << std::endl;
1144 #ifdef OSG_ONE_CHILD_PTR
1145 pcl_new_node->ptErrorCell = &(pcl_old_node->ptErrorCell->ptChildren[ui_child]);
1146 #else
1147 pcl_new_node->ptErrorCell = pcl_old_node->ptErrorCell->aptChildren[ui_child];
1148 #endif
1149 pcl_new_node->pclBSplineSurface = NULL;
1150 pcl_new_node->bOwnSurface = false;
1151 apcl_faces[ui_child]->faceinfo = static_cast<void*>(pcl_new_node);
1152 }
1153
1154 #else
1155 if(pcl_old_node->ptErrorCell)
1156 {
1157 apcl_faces[0] = pclFace;
1158 apcl_faces[1] = pclMesh->faces[cui_face_cnt - 3];
1159 apcl_faces[2] = pclMesh->faces[cui_face_cnt - 2];
1160 apcl_faces[3] = pclMesh->faces[cui_face_cnt - 1];
1161
1162 for(ui_child = 0; ui_child < 4; ++ui_child)
1163 {
1164 pcl_new_node = new SFaceTreeCell;
1165 // std::cerr << "subdivide with ErrorCell" << std::endl;
1166 #ifdef OSG_ONE_CHILD_PTR
1167 pcl_new_node->ptErrorCell = &(pcl_old_node->ptErrorCell->ptChildren[ui_child]);
1168 #else
1169 pcl_new_node->ptErrorCell = pcl_old_node->ptErrorCell->aptChildren[ui_child];
1170 #endif
1171 pcl_new_node->ptBPCell = NULL;
1172 pcl_new_node->pclBezierSurface = NULL;
1173 pcl_new_node->bOwnSurface = false;
1174 apcl_faces[ui_child]->faceinfo = static_cast<void*>(pcl_new_node);
1175 }
1176 }
1177 else if(pcl_old_node->ptBPCell->aptChildren[1])
1178 {
1179 // xx
1180 // xx
1181 apcl_faces[0] = pclFace;
1182 apcl_faces[1] = pclMesh->faces[cui_face_cnt - 3];
1183 apcl_faces[2] = pclMesh->faces[cui_face_cnt - 2];
1184 apcl_faces[3] = pclMesh->faces[cui_face_cnt - 1];
1185
1186 for(ui_child = 0; ui_child < 4; ++ui_child)
1187 {
1188 pcl_new_node = new SFaceTreeCell;
1189 // std::cerr << "subdivide with BPCell" << std::endl;
1190 pcl_new_node->ptErrorCell = NULL;
1191 pcl_new_node->ptBPCell = pcl_old_node->ptBPCell->aptChildren[ui_child];
1192 /* std::cerr << pcl_new_node->ptBPCell->uiLeft << " - ";
1193 std::cerr << pcl_new_node->ptBPCell->uiRight << " , ";
1194 std::cerr << pcl_new_node->ptBPCell->uiBottom << " - ";
1195 std::cerr << pcl_new_node->ptBPCell->uiTop << std::endl;
1196 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 0 ]->coords << " ";
1197 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 1 ]->coords << " ";
1198 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 2 ]->coords << " ";
1199 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 3 ]->coords << std::endl;*/
1200 pcl_new_node->pclBezierSurface = NULL;
1201 pcl_new_node->bOwnSurface = false;
1202 apcl_faces[ui_child]->faceinfo = static_cast<void*>(pcl_new_node);
1203 }
1204 }
1205 else if(pcl_old_node->ptBPCell->aptChildren[0])
1206 {
1207 // x
1208 // x
1209 apcl_faces[0] = pclFace;
1210 apcl_faces[1] = pclMesh->faces[cui_face_cnt - 1];
1211
1212 for(ui_child = 0; ui_child < 2; ++ui_child)
1213 {
1214 pcl_new_node = new SFaceTreeCell;
1215 // std::cerr << "subdivide with BPCell" << std::endl;
1216 pcl_new_node->ptErrorCell = NULL;
1217 pcl_new_node->ptBPCell = pcl_old_node->ptBPCell->aptChildren[3 * ui_child];
1218 /* std::cerr << pcl_new_node->ptBPCell->uiLeft << " - ";
1219 std::cerr << pcl_new_node->ptBPCell->uiRight << " , ";
1220 std::cerr << pcl_new_node->ptBPCell->uiBottom << " - ";
1221 std::cerr << pcl_new_node->ptBPCell->uiTop << std::endl;
1222 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 0 ]->coords << " ";
1223 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 1 ]->coords << " ";
1224 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 2 ]->coords << " ";
1225 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 3 ]->coords << std::endl;*/
1226 pcl_new_node->pclBezierSurface = NULL;
1227 pcl_new_node->bOwnSurface = false;
1228 apcl_faces[ui_child]->faceinfo = static_cast<void*>(pcl_new_node);
1229 }
1230 }
1231 else
1232 {
1233 // xx
1234 apcl_faces[0] = pclFace;
1235 apcl_faces[1] = pclMesh->faces[cui_face_cnt - 1];
1236
1237 for(ui_child = 0; ui_child < 2; ++ui_child)
1238 {
1239 pcl_new_node = new SFaceTreeCell;
1240 // std::cerr << "subdivide with BPCell" << std::endl;
1241 pcl_new_node->ptErrorCell = NULL;
1242 pcl_new_node->ptBPCell = pcl_old_node->ptBPCell->aptChildren[3 - ui_child];
1243 /* std::cerr << pcl_new_node->ptBPCell->uiLeft << " - ";
1244 std::cerr << pcl_new_node->ptBPCell->uiRight << " , ";
1245 std::cerr << pcl_new_node->ptBPCell->uiBottom << " - ";
1246 std::cerr << pcl_new_node->ptBPCell->uiTop << std::endl;
1247 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 0 ]->coords << " ";
1248 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 1 ]->coords << " ";
1249 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 2 ]->coords << " ";
1250 std::cerr << apcl_faces[ ui_child ]->orig_quad[ 3 ]->coords << std::endl;*/
1251 pcl_new_node->pclBezierSurface = NULL;
1252 pcl_new_node->bOwnSurface = false;
1253 apcl_faces[ui_child]->faceinfo = static_cast<void*>(pcl_new_node);
1254 }
1255 }
1256 #endif
1257
1258 delete pcl_old_node;
1259 }
1260
1261
1262 void CErrorQuadTree::SubdivideBuild(DCTPMesh *pclMesh, DCTPFace *pclFace)
1263 {
1264 const unsigned int cui_face_cnt = UInt32(pclMesh->faces.size());
1265 unsigned int ui_child;
1266 #ifdef OSG_USE_KD_TREE
1267 DCTPFace *apcl_faces[2];
1268 #else
1269 DCTPFace *apcl_faces[4];
1270 #endif
1271 SFaceTreeCell *pcl_old_node = static_cast<SFaceTreeCell*>(pclFace->faceinfo);
1272 SFaceTreeCell *pcl_new_node;
1273 #ifdef OSG_USE_NURBS_PATCH
1274 #ifdef OSG_USE_KD_TREE
1275 std::vector<BSplineTensorSurface> vcl_surfaces;
1276 #else
1277 std::vector<std::vector<BSplineTensorSurface> > vvcl_surfaces;
1278 #endif
1279 #else
1280 #ifdef OSG_USE_KD_TREE
1281 std::vector<BezierTensorSurface> vcl_surfaces;
1282 #else
1283 std::vector<std::vector<BezierTensorSurface> > vvcl_surfaces;
1284 #endif
1285 #endif
1286
1287 apcl_faces[0] = pclFace;
1288 #ifdef OSG_USE_KD_TREE
1289 apcl_faces[1] = pclMesh->faces[cui_face_cnt - 1];
1290 #else
1291 apcl_faces[1] = pclMesh->faces[cui_face_cnt - 3];
1292 apcl_faces[2] = pclMesh->faces[cui_face_cnt - 2];
1293 apcl_faces[3] = pclMesh->faces[cui_face_cnt - 1];
1294 #endif
1295
1296 pclFace->faceinfo = NULL;
1297 #ifdef OSG_USE_NURBS_PATCH
1298 #ifdef OSG_USE_KD_TREE
1299 #ifdef OSG_ARBITRARY_SPLIT
1300 if(pcl_old_node->ptErrorCell->fSplitValue < 0.0)
1301 {
1302 pcl_old_node->pclBSplineSurface->subDivisionU(vcl_surfaces, -pcl_old_node->ptErrorCell->fSplitValue);
1303 }
1304 else
1305 {
1306 pcl_old_node->pclBSplineSurface->subDivisionV(vcl_surfaces, pcl_old_node->ptErrorCell->fSplitValue);
1307 }
1308 #else
1309 if(pcl_old_node->ptErrorCell->bSplitHoriz)
1310 {
1311 pcl_old_node->pclBSplineSurface->midPointSubDivisionU(vcl_surfaces);
1312 }
1313 else
1314 {
1315 pcl_old_node->pclBSplineSurface->midPointSubDivisionV(vcl_surfaces);
1316 }
1317 #endif
1318 #else
1319 pcl_old_node->pclBSplineSurface->midPointSubDivision(vvcl_surfaces);
1320 #endif
1321 #else
1322 #ifdef OSG_USE_KD_TREE
1323 #error
1324 #else
1325 pcl_old_node->pclBezierSurface->midPointSubDivision(vvcl_surfaces);
1326 #endif
1327 #endif
1328
1329 #ifdef OSG_ONE_CHILD_PTR
1330 #ifdef OSG_USE_KD_TREE
1331
1332 for(ui_child = 0; ui_child < 2; ++ui_child)
1333 #else
1334
1335 for(ui_child = 0; ui_child < 4; ++ui_child)
1336 #endif
1337 {
1338 pcl_new_node = new SFaceTreeCell;
1339 pcl_new_node->ptErrorCell = &(pcl_old_node->ptErrorCell->ptChildren[ui_child]);
1340 pcl_new_node->bOwnSurface = true;
1341 #ifdef OSG_USE_NURBS_PATCH
1342 pcl_new_node->pclBSplineSurface = new BSplineTensorSurface;
1343 #ifdef OSG_USE_KD_TREE
1344 (*pcl_new_node->pclBSplineSurface) = vcl_surfaces[ui_child];
1345 #else
1346 (*pcl_new_node->pclBSplineSurface) = vvcl_surfaces[( (ui_child + 1) >> 1) & 1][1 - (ui_child >> 1)];
1347 #endif
1348 #else
1349 pcl_new_node->pclBezierSurface = new BezierTensorSurface;
1350 #ifdef OSG_USE_KD_TREE
1351 (*pcl_new_node->pclBezierSurface) = vvcl_surfaces[ui_child];
1352 #else
1353 (*pcl_new_node->pclBezierSurface) = vvcl_surfaces[( (ui_child + 1) >> 1) & 1][1 - (ui_child >> 1)];
1354 #endif
1355 #endif
1356 apcl_faces[ui_child]->faceinfo = static_cast<void*>(pcl_new_node);
1357 }
1358
1359 if(pcl_old_node->ptErrorCell->ptChildren == NULL)
1360 {
1361 #ifdef OSG_USE_KD_TREE
1362 pcl_old_node->ptErrorCell->ptChildren = new SErrorTreeCell[2];
1363
1364 for(ui_child = 0; ui_child < 2; ++ui_child)
1365 #else
1366 pcl_old_node->ptErrorCell->ptChildren = new SErrorTreeCell[4];
1367
1368 for(ui_child = 0; ui_child < 4; ++ui_child)
1369 #endif
1370 {
1371 pcl_new_node = static_cast<SFaceTreeCell*>(apcl_faces[ui_child]->faceinfo);
1372 pcl_new_node->ptErrorCell = &(pcl_old_node->ptErrorCell->ptChildren[ui_child]);
1373 pcl_new_node->ptErrorCell->ptChildren = NULL;
1374 pcl_new_node->ptErrorCell->fError = -1.0;
1375 ComputeError(apcl_faces[ui_child]);
1376 }
1377 }
1378 #else
1379 #ifdef OSG_USE_KD_TREE
1380
1381 for(ui_child = 0; ui_child < 2; ++ui_child)
1382 #else
1383
1384 for(ui_child = 0; ui_child < 4; ++ui_child)
1385 #endif
1386 {
1387 pcl_new_node = new SFaceTreeCell;
1388 pcl_new_node->ptErrorCell = pcl_old_node->ptErrorCell->aptChildren[ui_child];
1389 pcl_new_node->bOwnSurface = true;
1390 pcl_new_node->pclBezierSurface = new BezierTensorSurface;
1391 (*pcl_new_node->pclBezierSurface) = vvcl_surfaces[( (ui_child + 1) >> 1) & 1][1 - (ui_child >> 1)];
1392 apcl_faces[ui_child]->faceinfo = static_cast<void*>(pcl_new_node);
1393 if(pcl_new_node->ptErrorCell == NULL)
1394 {
1395 pcl_old_node->ptErrorCell->aptChildren[ui_child] = new SErrorTreeCell;
1396 pcl_new_node->ptErrorCell = pcl_old_node->ptErrorCell->aptChildren[ui_child];
1397 pcl_new_node->ptErrorCell->aptChildren[0] = NULL;
1398 pcl_new_node->ptErrorCell->aptChildren[1] = NULL;
1399 #ifndef OSG_USE_KD_TREE
1400 pcl_new_node->ptErrorCell->aptChildren[2] = NULL;
1401 pcl_new_node->ptErrorCell->aptChildren[3] = NULL;
1402 #endif
1403 pcl_new_node->ptErrorCell->fError = -1.0;
1404 ComputeError(apcl_faces[ui_child]);
1405 }
1406 }
1407
1408 #endif
1409 /* ( SFaceTreeCell* )( apcl_faces[ 0 ]->faceinfo )->pclBezierSurface = vvcl_surfaces[ 0 ][ 1 ];
1410 ( SFaceTreeCell* )( apcl_faces[ 1 ]->faceinfo )->pclBezierSurface = vvcl_surfaces[ 1 ][ 1 ];
1411 ( SFaceTreeCell* )( apcl_faces[ 2 ]->faceinfo )->pclBezierSurface = vvcl_surfaces[ 1 ][ 0 ];
1412 ( SFaceTreeCell* )( apcl_faces[ 3 ]->faceinfo )->pclBezierSurface = vvcl_surfaces[ 0 ][ 0 ];*/
1413
1414 if(pcl_old_node->bOwnSurface)
1415 {
1416 #ifdef OSG_USE_NURBS_PATCH
1417 delete pcl_old_node->pclBSplineSurface;
1418 #else
1419 delete pcl_old_node->pclBezierSurface;
1420 #endif
1421 }
1422 delete pcl_old_node;
1423 }
1424 //#endif
1425
1426
1427 /*#ifdef OSG_ARBITRARY_SPLIT
1428 void CErrorQuadTree::ComputeError( SFaceTreeCell *ptCell )
1429 #else*/
1430 void CErrorQuadTree::ComputeError(DCTPFace *pclFace)
1431 //#endif
1432 {
1433 //#ifndef OSG_ARBITRARY_SPLIT
1434 SFaceTreeCell *ptCell = static_cast<SFaceTreeCell*>(pclFace->faceinfo);
1435 //#endif
1436
1437 if(ptCell->ptErrorCell->fError >= 0.0)
1438 {
1439 return; // error was already calculated
1440 }
1441
1442 if( ( (pclFace->orig_face[1]->coords[0] - pclFace->orig_face[3]->coords[0]) < 10.0) ||
1443 ( (pclFace->orig_face[1]->coords[1] - pclFace->orig_face[3]->coords[1]) < 10.0) )
1444 {
1445 // too small face!
1446 ptCell->ptErrorCell->fError = 0.0;
1447 return;
1448 }
1449
1450 #ifdef OSG_USE_NURBS_PATCH
1451 BSplineTensorSurface *pcl_surface = ptCell->pclBSplineSurface;
1452 const std::vector<double> &crvd_knot_u = pcl_surface->getKnotVector_U();
1453 const std::vector<double> &crvd_knot_v = pcl_surface->getKnotVector_V();
1454 const unsigned int cui_dim_u = pcl_surface->getDimension_U();
1455 const unsigned int cui_dim_v = pcl_surface->getDimension_V();
1456 unsigned int ui_idx;
1457 #else
1458 BezierTensorSurface *pcl_surface = ptCell->pclBezierSurface;
1459 #endif
1460 const std::vector<std::vector <Vec4d> > &crvvcl_cps = pcl_surface->getControlPointMatrix();
1461 const unsigned int cui_m = UInt32(crvvcl_cps.size()) - 1;
1462 const unsigned int cui_n = UInt32(crvvcl_cps[0].size()) - 1;
1463 Vec3d ccl_b00;
1464 ccl_b00[0] = crvvcl_cps[0][0][0] / crvvcl_cps[0][0][3];
1465 ccl_b00[1] = crvvcl_cps[0][0][1] / crvvcl_cps[0][0][3];
1466 ccl_b00[2] = crvvcl_cps[0][0][2] / crvvcl_cps[0][0][3];
1467 Vec3d ccl_b0n;
1468 ccl_b0n[0] = crvvcl_cps[0][cui_n][0] / crvvcl_cps[0][cui_n][3];
1469 ccl_b0n[1] = crvvcl_cps[0][cui_n][1] / crvvcl_cps[0][cui_n][3];
1470 ccl_b0n[2] = crvvcl_cps[0][cui_n][2] / crvvcl_cps[0][cui_n][3];
1471 Vec3d ccl_bm0;
1472 ccl_bm0[0] = crvvcl_cps[cui_m][0][0] / crvvcl_cps[cui_m][0][3];
1473 ccl_bm0[1] = crvvcl_cps[cui_m][0][1] / crvvcl_cps[cui_m][0][3];
1474 ccl_bm0[2] = crvvcl_cps[cui_m][0][2] / crvvcl_cps[cui_m][0][3];
1475 Vec3d ccl_bmn;
1476 ccl_bmn[0] = crvvcl_cps[cui_m][cui_n][0] / crvvcl_cps[cui_m][cui_n][3];
1477 ccl_bmn[1] = crvvcl_cps[cui_m][cui_n][1] / crvvcl_cps[cui_m][cui_n][3];
1478 ccl_bmn[2] = crvvcl_cps[cui_m][cui_n][2] / crvvcl_cps[cui_m][cui_n][3];
1479 Vec3d cl_cij;
1480 Vec3d cl_bij;
1481 double d_quad_size;
1482 unsigned int ui_i;
1483 unsigned int ui_j;
1484 #ifndef OSG_USE_NURBS_PATCH
1485 const double cd_rn = 1.0 / cui_n;
1486 const double cd_rm = 1.0 / cui_m;
1487 #endif
1488 Vec3d cl_ci0;
1489 Vec3d cl_cin;
1490 #ifndef OSG_USE_NURBS_PATCH
1491 const Vec3d ccl_dcx0 = (ccl_bm0 - ccl_b00) * cd_rm;
1492 const Vec3d ccl_dcxn = (ccl_bmn - ccl_b0n) * cd_rm;
1493 #endif
1494 Vec3d cl_norm;
1495 #ifndef OSG_USE_NURBS_PATCH
1496 const Vec3d ccl_dc0x = (ccl_b0n - ccl_b00) * cd_rn;
1497 const Vec3d ccl_dcmx = (ccl_bmn - ccl_bm0) * cd_rn;
1498 Vec3d cl_c0j;
1499 Vec3d cl_cmj;
1500 #endif
1501 int i_err;
1502 Vec2d cl_uv;
1503 #ifdef OSG_USE_NURBS_PATCH
1504 Vec2d cl_min;
1505 Vec2d cl_add;
1506 #endif
1507 #ifdef OSG_ARBITRARY_SPLIT
1508 Vec2d cl_worst;
1509 #endif
1510 // normal stuff
1511 Vec3d cl_nb00;
1512 Vec3d cl_nb0n;
1513 Vec3d cl_nbm0;
1514 Vec3d cl_nbmn;
1515 Vec3d cl_ncij;
1516 Vec3d cl_nbij;
1517 Vec3d cl_nci0;
1518 Vec3d cl_ncin;
1519 #ifndef OSG_USE_NURBS_PATCH
1520 Vec3d cl_ndcx0;
1521 Vec3d cl_ndcxn;
1522 Vec3d cl_ndc0x;
1523 Vec3d cl_ndcmx;
1524 Vec3d cl_ndcix;
1525 Vec3d cl_ndcxj;
1526 Vec3d cl_nc0j;
1527 Vec3d cl_ncmj;
1528 #endif
1529 Vec3f cl_normal;
1530 Pnt3f cl_position;
1531 double d_quadcurv = 0.0;
1532
1533 #ifdef OSG_USE_NURBS_PATCH
1534 pcl_surface->getParameterInterval_U(cl_min[0], cl_add[0]);
1535 pcl_surface->getParameterInterval_V(cl_min[1], cl_add[1]);
1536 cl_add -= cl_min;
1537 #ifdef OSG_ARBITRARY_SPLIT
1538 cl_worst = cl_min;
1539 #endif
1540 #endif
1541
1542 if(m_sbNormalApproximation)
1543 {
1544 //#ifndef OSG_USE_NURBS_PATCH
1545
1546 Vec3d du, dv;
1547 du[0] = crvvcl_cps[1][0][0];
1548 du[1] = crvvcl_cps[1][0][1];
1549 du[2] = crvvcl_cps[1][0][2];
1550
1551 // we take the difference of two homogenious cps, but as the length of the cross product
1552 // is irrevelant (we're calculating normals) we ignore the weights.
1553 // In addition the weight of cp[1][0] might be zero so we avoid dividing by it (multiply is OK).
1554 du -= ccl_b00 * crvvcl_cps[1][0][3];
1555
1556 dv[0] = crvvcl_cps[0][1][0];
1557 dv[1] = crvvcl_cps[0][1][1];
1558 dv[2] = crvvcl_cps[0][1][2];
1559 dv -= ccl_b00 * crvvcl_cps[0][1][3];
1560 cl_nb00 = du.cross(dv);
1561
1562 du[0] = crvvcl_cps[1][cui_n][0];
1563 du[1] = crvvcl_cps[1][cui_n][1];
1564 du[2] = crvvcl_cps[1][cui_n][2];
1565 du -= ccl_b0n * crvvcl_cps[1][cui_n][3];
1566 dv[0] = crvvcl_cps[0][cui_n - 1][0];
1567 dv[1] = crvvcl_cps[0][cui_n - 1][1];
1568 dv[2] = crvvcl_cps[0][cui_n - 1][2];
1569 dv -= ccl_b0n * crvvcl_cps[0][cui_n - 1][3];
1570 cl_nb0n = du.cross(-dv);
1571
1572 du[0] = crvvcl_cps[cui_m - 1][0][0];
1573 du[1] = crvvcl_cps[cui_m - 1][0][1];
1574 du[2] = crvvcl_cps[cui_m - 1][0][2];
1575 du -= ccl_bm0 * crvvcl_cps[cui_m - 1][0][3];
1576 dv[0] = crvvcl_cps[cui_m][1][0];
1577 dv[1] = crvvcl_cps[cui_m][1][1];
1578 dv[2] = crvvcl_cps[cui_m][1][2];
1579 dv -= ccl_bm0 * crvvcl_cps[cui_m][1][3];
1580 cl_nbm0 = -du.cross(dv);
1581
1582 du[0] = crvvcl_cps[cui_m - 1][cui_n][0];
1583 du[1] = crvvcl_cps[cui_m - 1][cui_n][1];
1584 du[2] = crvvcl_cps[cui_m - 1][cui_n][2];
1585 du -= ccl_bmn * crvvcl_cps[cui_m - 1][cui_n][3];
1586 dv[0] = crvvcl_cps[cui_m][cui_n - 1][0];
1587 dv[1] = crvvcl_cps[cui_m][cui_n - 1][1];
1588 dv[2] = crvvcl_cps[cui_m][cui_n - 1][2];
1589 dv -= ccl_bmn * crvvcl_cps[cui_m][cui_n - 1][3];
1590 cl_nbmn = du.cross(dv); // -du X -dv => du X dv
1591
1592 /*
1593 cl_nb00 = ( crvvcl_cps[ 1 ][ 0 ] - crvvcl_cps[ 0 ][ 0 ] ).cross(
1594 ( crvvcl_cps[ 0 ][ 1 ] - crvvcl_cps[ 0 ][ 0 ] ) );
1595 cl_nb0n = ( crvvcl_cps[ 1 ][ cui_n ] - crvvcl_cps[ 0 ][ cui_n ] ).cross(
1596 ( crvvcl_cps[ 0 ][ cui_n ] - crvvcl_cps[ 0 ][ cui_n - 1 ] ) );
1597 cl_nbm0 = ( crvvcl_cps[ cui_m ][ 1 ] - crvvcl_cps[ cui_m ][ 0 ] ).cross(
1598 ( crvvcl_cps[ cui_m - 1 ][ 0 ] - crvvcl_cps[ cui_m ][ 0 ] ) );
1599 cl_nbmn = ( crvvcl_cps[ cui_m ][ cui_n ] - crvvcl_cps[ cui_m - 1 ][ cui_n ] ).cross(
1600 ( crvvcl_cps[ cui_m ][ cui_n ] - crvvcl_cps[ cui_m ][ cui_n - 1 ] ) );
1601 */
1602 // std::cerr << cl_nb00 << std::endl;
1603 // std::cerr << cl_nb0n << std::endl;
1604 // std::cerr << cl_nbm0 << std::endl;
1605 // std::cerr << cl_nbmn << std::endl << std::endl;
1606 /*#else
1607 cl_uv = cl_min;
1608 cl_normal = pcl_surface->computeNormal( cl_uv, i_err, cl_position );
1609 cl_nb00[0] = cl_normal[ 0 ];
1610 cl_nb00[1] = cl_normal[ 1 ];
1611 cl_nb00[2] = cl_normal[ 2 ];
1612
1613 cl_uv[1] += cl_add[1];
1614 cl_normal = pcl_surface->computeNormal( cl_uv, i_err, cl_position );
1615 cl_nb0n[0] = cl_normal[ 0 ];
1616 cl_nb0n[1] = cl_normal[ 1 ];
1617 cl_nb0n[2] = cl_normal[ 2 ];
1618
1619 cl_uv[0] += cl_add[0];
1620 cl_normal = pcl_surface->computeNormal( cl_uv, i_err, cl_position );
1621 cl_nbmn[0] = cl_normal[ 0 ];
1622 cl_nbmn[1] = cl_normal[ 1 ];
1623 cl_nbmn[2] = cl_normal[ 2 ];
1624
1625 cl_uv[1] = cl_min[1];
1626 cl_normal = pcl_surface->computeNormal( cl_uv, i_err, cl_position );
1627 cl_nbm0[0] = cl_normal[ 0 ];
1628 cl_nbm0[1] = cl_normal[ 1 ];
1629 cl_nbm0[2] = cl_normal[ 2 ];
1630 // std::cerr << cl_nb00 << std::endl;
1631 // std::cerr << cl_nb0n << std::endl;
1632 // std::cerr << cl_nbm0 << std::endl;
1633 // std::cerr << cl_nbmn << std::endl << std::endl;
1634 #endif*/
1635
1636 d_quad_size = cl_nb00.squareLength();
1637 if(d_quad_size > DCTP_EPS * DCTP_EPS)
1638 {
1639 cl_nb00 *= 1.0 / sqrt(d_quad_size);
1640 }
1641 d_quad_size = cl_nb0n.squareLength();
1642 if(d_quad_size > DCTP_EPS * DCTP_EPS)
1643 {
1644 cl_nb0n *= 1.0 / sqrt(d_quad_size);
1645 }
1646 d_quad_size = cl_nbm0.squareLength();
1647 if(d_quad_size > DCTP_EPS * DCTP_EPS)
1648 {
1649 cl_nbm0 *= 1.0 / sqrt(d_quad_size);
1650 }
1651 d_quad_size = cl_nbmn.squareLength();
1652 if(d_quad_size > DCTP_EPS * DCTP_EPS)
1653 {
1654 cl_nbmn *= 1.0 / sqrt(d_quad_size);
1655 }
1656 // AKOS !!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1657 // std::cerr << cl_nb00 << std::endl;
1658 // std::cerr << cl_nb0n << std::endl;
1659 // std::cerr << cl_nbm0 << std::endl;
1660 // std::cerr << cl_nbmn << std::endl << std::endl;
1661
1662 #ifndef OSG_USE_NURBS_PATCH
1663 cl_ndcx0 = (cl_nbm0 - cl_nb00) * cd_rm;
1664 cl_ndcxn = (cl_nbmn - cl_nb0n) * cd_rm;
1665 cl_ndc0x = (cl_nb0n - cl_nb00) * cd_rn;
1666 cl_ndcmx = (cl_nbmn - cl_nbm0) * cd_rn;
1667 #endif
1668
1669 if( (cl_nb00.squareLength() < DCTP_EPS * DCTP_EPS) ||
1670 (cl_nb0n.squareLength() < DCTP_EPS * DCTP_EPS) ||
1671 (cl_nbm0.squareLength() < DCTP_EPS * DCTP_EPS) ||
1672 (cl_nbmn.squareLength() < DCTP_EPS * DCTP_EPS) ||
1673 ((ccl_b00 - ccl_b0n).squareLength() < DCTP_EPS * DCTP_EPS) ||
1674 ((ccl_b0n - ccl_bmn).squareLength() < DCTP_EPS * DCTP_EPS) ||
1675 ((ccl_bmn - ccl_bm0).squareLength() < DCTP_EPS * DCTP_EPS) ||
1676 ((ccl_bm0 - ccl_b00).squareLength() < DCTP_EPS * DCTP_EPS))
1677 {
1678 d_quadcurv = 1e100;
1679 }
1680 else
1681 {
1682 d_quadcurv = osgMax(osgMax( (cl_nb00 - cl_nb0n).squareLength() / (ccl_b00 - ccl_b0n).squareLength(),
1683 (cl_nb0n - cl_nbmn).squareLength() / (ccl_b0n - ccl_bmn).squareLength() ),
1684 osgMax( (cl_nbmn - cl_nbm0).squareLength() / (ccl_bmn - ccl_bm0).squareLength(),
1685 (cl_nbm0 - cl_nb00).squareLength() / (ccl_bm0 - ccl_b00).squareLength() ) );
1686
1687 // d_quadcurv *= 4.0; // 0.5 pixel geometric, 1 pixel shading error
1688 }
1689
1690 if(d_quadcurv < 1e-4)
1691 {
1692 // std::cerr << d_quadcurv << std::endl;
1693 d_quadcurv = 1e-4;
1694 }
1695 /* else
1696 {
1697 std::cerr << d_quadcurv << std::endl;
1698 }*/
1699 }
1700
1701 #ifndef OSG_USE_NURBS_PATCH
1702 cl_ci0 = ccl_b00;
1703 cl_cin = ccl_b0n;
1704 if(m_sbNormalApproximation)
1705 {
1706 cl_nci0 = cl_nb00;
1707 cl_ncin = cl_nb0n;
1708 }
1709 #endif
1710
1711 for(ui_i = 0; ui_i <= cui_m; ++ui_i)
1712 {
1713 #ifdef OSG_USE_NURBS_PATCH
1714 // cl_uv[0] += ( crvd_knot_u[ cui_dim_u + ui_i ] - crvd_knot_u[ ui_i ] ) / cui_dim_u;
1715 cl_uv[0] = 0.0;
1716
1717 for(ui_idx = 0; ui_idx < cui_dim_u; ++ui_idx)
1718 {
1719 cl_uv[0] += crvd_knot_u[ui_idx + ui_i + 1];
1720 }
1721
1722 cl_uv[0] /= cui_dim_u;
1723
1724 const double cd_xrel = (cl_uv[0] - cl_min[0]) / cl_add[0];
1725
1726 cl_ci0 = (ccl_bm0 - ccl_b00) * cd_xrel + ccl_b00;
1727 cl_cin = (ccl_bmn - ccl_b0n) * cd_xrel + ccl_b0n;
1728 if(m_sbNormalApproximation)
1729 {
1730 cl_nci0 = (cl_nbm0 - cl_nb00) * cd_xrel + cl_nb00;
1731 cl_ncin = (cl_nbmn - cl_nb0n) * cd_xrel + cl_nb0n;
1732 }
1733 #else
1734 cl_cij = cl_ci0;
1735 cl_c0j = ccl_b00;
1736 cl_cmj = ccl_bm0;
1737
1738 const Vec3d ccl_dcix = (cl_cin - cl_ci0) * cd_rn;
1739
1740 if(m_sbNormalApproximation)
1741 {
1742 cl_ncij = cl_nci0;
1743 cl_nc0j = cl_nb00;
1744 cl_ncmj = cl_nbm0;
1745
1746 cl_ndcix = (cl_ncin - cl_nci0) * cd_rn;
1747 }
1748
1749 cl_uv[0] = ui_i * cd_rm;
1750 #endif
1751
1752 for(ui_j = 0; ui_j <= cui_n; ++ui_j)
1753 {
1754 #ifdef OSG_USE_NURBS_PATCH
1755 cl_uv[1] = 0.0;
1756
1757 for(ui_idx = 0; ui_idx < cui_dim_v; ++ui_idx)
1758 {
1759 cl_uv[1] += crvd_knot_v[ui_idx + ui_j + 1];
1760 }
1761
1762 cl_uv[1] /= cui_dim_v;
1763
1764 const double cd_yrel = (cl_uv[1] - cl_min[1]) / cl_add[1];
1765
1766 cl_cij = cl_ci0 + (cl_cin - cl_ci0) * cd_yrel;
1767 if(m_sbNormalApproximation)
1768 {
1769 cl_ncij = cl_nci0 + (cl_ncin - cl_nci0) * cd_yrel;
1770 }
1771 #else
1772 const Vec3d ccl_dcxj = cl_cmj - cl_c0j;
1773
1774 if(m_sbNormalApproximation)
1775 {
1776 cl_ndcxj = cl_ncmj - cl_nc0j;
1777 }
1778
1779 cl_uv[1] = ui_j * cd_rn;
1780 #endif
1781 #ifdef OSG_DIFF_TO_BILIN
1782 #ifdef OSG_USE_NURBS_PATCH
1783 #ifdef OSG_CONSERVATIVE_ERROR
1784 cl_bij = crvvcl_cps[ui_i][ui_j];
1785 #else
1786 if(m_sbNormalApproximation)
1787 {
1788 // TODO Vec3f f�r normale, Pnt3f f�r punkt
1789 cl_nbij = pcl_surface->computeNormal(cl_uv, i_err, cl_bij);
1790 d_quad_size = cl_ncij.squareLength();
1791 if(d_quad_size > DCTP_EPS * DCTP_EPS)
1792 {
1793 cl_norm = cl_ncij * (1.0 / sqrt(d_quad_size) );
1794 }
1795 else
1796 {
1797 cl_norm = cl_nbij;
1798 }
1799 // std::cerr << cl_uv << cl_nbij << cl_norm << std::endl;
1800 cl_nbij -= cl_norm;
1801 }
1802 else
1803 {
1804 cl_bij = pcl_surface->compute(cl_uv, i_err);
1805 }
1806 #endif
1807 #else
1808 #ifdef OSG_CONSERVATIVE_ERROR
1809 cl_bij = crvvcl_cps[ui_i][ui_j];
1810 #else
1811 cl_bij = pcl_surface->computewdeCasteljau(cl_uv, i_err);
1812 #endif
1813 #endif
1814 if( (m_sbNormalApproximation) && (cl_nbij.squareLength() > DCTP_EPS * DCTP_EPS) )
1815 {
1816 // calculate shading error
1817 d_quad_size = cl_nbij.squareLength() / d_quadcurv;
1818
1819 #ifdef OSG_EUCLID_ERRORS
1820 // for euclidian norm first calculate distance to next correcly shaded pixel
1821 d_quad_size += (cl_bij - cl_cij).squareLength();
1822 #endif
1823
1824 // the corner points are correcly shaded pixels...
1825 d_quad_size = osgMin(d_quad_size, (cl_bij - ccl_b00).squareLength() );
1826 d_quad_size = osgMin(d_quad_size, (cl_bij - ccl_b0n).squareLength() );
1827 d_quad_size = osgMin(d_quad_size, (cl_bij - ccl_bm0).squareLength() );
1828 d_quad_size = osgMin(d_quad_size, (cl_bij - ccl_bmn).squareLength() );
1829
1830 #ifdef OSG_EUCLID_ERRORS
1831 d_quad_size = sqrt(d_quad_size);
1832 #else
1833 // for maximum norm choose the maximum error
1834 d_quad_size = sqrt(osgMax( (cl_bij - cl_cij).squareLength(), d_quad_size) );
1835 #endif
1836 }
1837 else
1838 {
1839 d_quad_size = sqrt( (cl_bij - cl_cij).squareLength() );
1840 }
1841 #ifdef OSG_ARBITRARY_SPLIT
1842 if(osgAbs(d_quad_size - ptCell->ptErrorCell->fError) < DCTP_EPS)
1843 {
1844 double cd_old_x = osgMin(cl_worst[0] - cl_min[0], cl_min[0] + cl_add[0] - cl_worst[0]);
1845 double cd_old_y = osgMin(cl_worst[1] - cl_min[1], cl_min[1] + cl_add[1] - cl_worst[1]);
1846 double cd_new_x = osgMin(cl_uv[0] - cl_min[0], cl_min[0] + cl_add[0] - cl_uv[0]);
1847 double cd_new_y = osgMin(cl_uv[1] - cl_min[1], cl_min[1] + cl_add[1] - cl_uv[1]);
1848 // std::cerr << cd_old_x * cd_old_x + cd_old_y * cd_old_y << " " << cd_new_x * cd_new_x + cd_new_y * cd_new_y << std::endl;
1849 if(cd_old_x * cd_old_x + cd_old_y * cd_old_y <= cd_new_x * cd_new_x + cd_new_y * cd_new_y)
1850 {
1851 cl_worst = cl_uv;
1852 }
1853 if(d_quad_size > ptCell->ptErrorCell->fError)
1854 {
1855 ptCell->ptErrorCell->fError = float(d_quad_size);
1856 }
1857 }
1858 else
1859 #endif
1860 if(d_quad_size > ptCell->ptErrorCell->fError)
1861 {
1862 ptCell->ptErrorCell->fError = float(d_quad_size);
1863 #ifdef OSG_ARBITRARY_SPLIT
1864 cl_worst = cl_uv;
1865 #endif
1866 }
1867 #else
1868 #ifdef OSG_CONSERVATIVE_ERROR
1869 cl_bij = crvvcl_cps[ui_i][ui_j];
1870 #else
1871 #ifdef OSG_USE_NURBS_PATCH
1872 cl_bij = pcl_surface->compute(cl_uv, i_err);
1873 #else
1874 cl_bij = pcl_surface->computewdeCasteljau(cl_uv, i_err);
1875 #endif
1876 #endif
1877 d_quad_size = osgMin(computeDistToTriangle(cl_bij, ccl_b00, ccl_b0n, ccl_bm0),
1878 computeDistToTriangle(cl_bij, ccl_bmn, ccl_b0n, ccl_bm0) );
1879 // std::cerr << d_quad_size << std::endl;
1880 if(d_quad_size > ptCell->ptErrorCell->fError)
1881 {
1882 // std::cerr << d_quad_size << std::endl;
1883 ptCell->ptErrorCell->fError = ( float ) d_quad_size;
1884 }
1885 d_quad_size = osgMin(computeDistToTriangle(cl_bij, ccl_b0n, ccl_b00, ccl_bmn),
1886 computeDistToTriangle(cl_bij, ccl_bm0, ccl_b00, ccl_bmn) );
1887 // std::cerr << d_quad_size << std::endl;
1888 if(d_quad_size > ptCell->ptErrorCell->fError)
1889 {
1890 // std::cerr << d_quad_size << std::endl;
1891 ptCell->ptErrorCell->fError = ( float ) d_quad_size;
1892 }
1893 #endif
1894 #ifndef OSG_USE_NURBS_PATCH
1895 cl_cij += ccl_dcix;
1896 cl_c0j += ccl_dc0x;
1897 cl_cmj += ccl_dcmx;
1898 #endif
1899 }
1900
1901 #ifndef OSG_USE_NURBS_PATCH
1902 cl_ci0 += ccl_dcx0;
1903 cl_cin += ccl_dcxn;
1904 #endif
1905 }
1906
1907 // add twist vector error
1908 #ifdef OSG_DIFF_TO_BILIN
1909 #ifdef OSG_CONSERVATIVE_ERROR
1910 ptCell->ptErrorCell->fError += ( float ) sqrt( (ccl_b00 - ccl_b0n + ccl_bmn - ccl_bm0).squareLength() ) * 0.25;
1911 #endif
1912 #endif
1913 // ptCell->ptErrorCell->fError *= 0.1;
1914 // std::cerr << ptCell->ptErrorCell->fError << std::endl;
1915 #ifdef OSG_USE_KD_TREE
1916 #ifdef OSG_ARBITRARY_SPLIT
1917 // std::cerr << cl_min << cl_add << cl_worst << std::endl;
1918 if( (osgAbs(cl_worst[0] - cl_min[0]) <= osgMax(DCTP_EPS, 1e-4 * cl_add[0]) ) ||
1919 (osgAbs(cl_worst[0] - (cl_min[0] + cl_add[0]) ) <= osgMax(DCTP_EPS, 1e-4 * cl_add[0]) ) )
1920 {
1921 // std::cerr << "y";
1922 if( (osgAbs(cl_worst[1] - cl_min[1]) <= osgMax(DCTP_EPS, 1e-4 * cl_add[1]) ) ||
1923 (osgAbs(cl_worst[1] - (cl_min[1] + cl_add[1]) ) <= osgMax(DCTP_EPS, 1e-4 * cl_add[1]) ) )
1924 {
1925 if(osgAbs(cl_add[0]) < osgAbs(cl_add[1]) )
1926 {
1927 // std::cerr << "my";
1928 ptCell->ptErrorCell->fSplitValue = 0.5;
1929 }
1930 else
1931 {
1932 // std::cerr << "mx";
1933 ptCell->ptErrorCell->fSplitValue = -0.5;
1934 }
1935 }
1936 else
1937 {
1938 ptCell->ptErrorCell->fSplitValue = (cl_worst[1] - cl_min[1]) / cl_add[1];
1939 }
1940 }
1941 else if( (osgAbs(cl_worst[1] - cl_min[1]) <= osgMax(DCTP_EPS, 1e-4 * cl_add[1]) ) ||
1942 (osgAbs(cl_worst[1] - (cl_min[1] + cl_add[1]) ) <= osgMax(DCTP_EPS, 1e-4 * cl_add[1]) ) )
1943 {
1944 // std::cerr << "x";
1945 ptCell->ptErrorCell->fSplitValue = -(cl_worst[0] - cl_min[0]) / cl_add[0];
1946 }
1947 else
1948 {
1949 double d_hdiff;
1950 double d_vdiff;
1951
1952 cl_uv[0] = cl_worst[0];
1953 cl_uv[1] = cl_min[1];
1954 if(m_sbNormalApproximation)
1955 {
1956 cl_nci0 = pcl_surface->computeNormal(cl_uv, i_err, cl_ci0);
1957 cl_uv[1] += cl_add[1];
1958 cl_ncin = pcl_surface->computeNormal(cl_uv, i_err, cl_cin);
1959 cl_uv[1] = cl_worst[1];
1960 cl_ncij = pcl_surface->computeNormal(cl_uv, i_err, cl_cij);
1961
1962 cl_bij = cl_ci0 + (cl_cin - cl_ci0) * ( (cl_worst[1] - cl_min[1]) / cl_add[1]);
1963 cl_nbij = cl_nci0 + (cl_ncin - cl_nci0) * ( (cl_worst[1] - cl_min[1]) / cl_add[1]);
1964 d_quad_size = cl_nbij.squareLength();
1965 if(d_quad_size > DCTP_EPS * DCTP_EPS)
1966 {
1967 cl_nbij *= 1.0 / sqrt(d_quad_size);
1968 }
1969 }
1970 else
1971 {
1972 cl_ci0 = pcl_surface->compute(cl_uv, i_err);
1973 cl_uv[1] += cl_add[1];
1974 cl_cin = pcl_surface->compute(cl_uv, i_err);
1975 cl_uv[1] = cl_worst[1];
1976 cl_cij = pcl_surface->compute(cl_uv, i_err);
1977
1978 cl_bij = cl_ci0 + (cl_cin - cl_ci0) * ( (cl_worst[1] - cl_min[1]) / cl_add[1]);
1979 }
1980
1981 // const double cd_hdiff = computeDistToLine( cl_cij, cl_ci0, cl_cin );
1982 // const double cd_hdiff = sqrt( ( cl_cij - cl_bij ).squareLength( ) );
1983 if( (m_sbNormalApproximation) && (cl_ncij.squareLength() > DCTP_EPS * DCTP_EPS) )
1984 {
1985 // calculate shading error
1986 d_hdiff = (cl_ncij - cl_nbij).squareLength() / d_quadcurv;
1987
1988 #ifdef OSG_EUCLID_ERRORS
1989 // for euclidian norm first calculate distance to next correcly shaded pixel
1990 d_hdiff += (cl_cij - cl_bij).squareLength();
1991 #endif
1992
1993 // the new corner points will be correcly shaded pixels...
1994 // d_hdiff = osgMin( d_hdiff, ( cl_cij - cl_ci0 ).squareLength( ) );
1995 // d_hdiff = osgMin( d_hdiff, ( cl_cij - cl_cin ).squareLength( ) );
1996
1997 #ifdef OSG_EUCLID_ERRORS
1998 d_hdiff = sqrt(d_hdiff);
1999 #else
2000 // for maximum norm choose the maximum error
2001 d_hdiff = sqrt(osgMax( (cl_cij - cl_bij).squareLength(), d_hdiff) );
2002 #endif
2003
2004 /* #ifdef OSG_EUCLID_ERRORS
2005 d_hdiff = sqrt( ( cl_cij - cl_bij ).squareLength( )
2006 + ( cl_ncij - cl_nbij ).squareLength( ) / d_quadcurv );
2007 #else
2008 d_hdiff = sqrt( osgMax( ( cl_cij - cl_bij ).squareLength( ),
2009 ( cl_ncij - cl_nbij ).squareLength( ) / d_quadcurv ) );
2010 #endif*/
2011 d_hdiff += sqrt( (cl_ci0 - cl_cin).squareLength() ) * 0.0001;
2012 }
2013 else
2014 {
2015 d_hdiff = sqrt( (cl_cij - cl_bij).squareLength() )
2016 + sqrt( (cl_ci0 - cl_cin).squareLength() ) * 0.0001;
2017 }
2018 // const double cd_hdiff = sqrt( ( cl_ci0 - cl_cin ).squareLength( ) );
2019
2020
2021
2022 /* std::cerr.precision( 4 );
2023 if( m_sbNormalApproximation )
2024 {
2025 std::cerr << cl_ci0 << cl_cij << cl_cin << cl_nci0 << cl_ncij << cl_ncin << d_hdiff << std::endl;
2026 }
2027 else
2028 {
2029 std::cerr << cl_ci0 << cl_cij << cl_cin << d_hdiff << std::endl;
2030 }*/
2031
2032 if(m_sbNormalApproximation)
2033 {
2034 cl_uv[0] = cl_min[0];
2035 cl_nci0 = pcl_surface->computeNormal(cl_uv, i_err, cl_ci0);
2036 cl_uv[0] += cl_add[0];
2037 cl_ncin = pcl_surface->computeNormal(cl_uv, i_err, cl_cin);
2038
2039 cl_bij = cl_ci0 + (cl_cin - cl_ci0) * ( (cl_worst[0] - cl_min[0]) / cl_add[0]);
2040 cl_nbij = cl_nci0 + (cl_ncin - cl_nci0) * ( (cl_worst[0] - cl_min[0]) / cl_add[0]);
2041 d_quad_size = cl_nbij.squareLength();
2042 if(d_quad_size > DCTP_EPS * DCTP_EPS)
2043 {
2044 cl_nbij *= 1.0 / sqrt(d_quad_size);
2045 }
2046 }
2047 else
2048 {
2049 cl_uv[0] = cl_min[0];
2050 cl_ci0 = pcl_surface->compute(cl_uv, i_err);
2051 cl_uv[0] += cl_add[0];
2052 cl_cin = pcl_surface->compute(cl_uv, i_err);
2053
2054 cl_bij = cl_ci0 + (cl_cin - cl_ci0) * ( (cl_worst[0] - cl_min[0]) / cl_add[0]);
2055 }
2056
2057 // const double cd_vdiff = computeDistToLine( cl_cij, cl_ci0, cl_cin );
2058 // const double cd_vdiff = sqrt( ( cl_cij - cl_bij ).squareLength( ) );
2059 if( (m_sbNormalApproximation) && (cl_ncij.squareLength() > DCTP_EPS * DCTP_EPS) )
2060 {
2061 // calculate shading error
2062 d_vdiff = (cl_ncij - cl_nbij).squareLength() / d_quadcurv;
2063
2064 #ifdef OSG_EUCLID_ERRORS
2065 // for euclidian norm first calculate distance to next correcly shaded pixel
2066 d_vdiff += (cl_cij - cl_bij).squareLength();
2067 #endif
2068
2069 // the new corner points will be correcly shaded pixels...
2070 // d_vdiff = osgMin( d_vdiff, ( cl_cij - cl_ci0 ).squareLength( ) );
2071 // d_vdiff = osgMin( d_vdiff, ( cl_cij - cl_cin ).squareLength( ) );
2072
2073 #ifdef OSG_EUCLID_ERRORS
2074 d_vdiff = sqrt(d_vdiff);
2075 #else
2076 // for maximum norm choose the maximum error
2077 d_vdiff = sqrt(osgMax( (cl_cij - cl_bij).squareLength(), d_vdiff) );
2078 #endif
2079
2080 /* #ifdef OSG_EUCLID_ERRORS
2081 d_vdiff = sqrt( ( cl_cij - cl_bij ).squareLength( )
2082 + ( cl_ncij - cl_nbij ).squareLength( ) / d_quadcurv );
2083 #else
2084 d_vdiff = sqrt( osgMax( ( cl_cij - cl_bij ).squareLength( ),
2085 ( cl_ncij - cl_nbij ).squareLength( ) / d_quadcurv ) );
2086 #endif*/
2087 d_vdiff += sqrt( (cl_ci0 - cl_cin).squareLength() ) * 0.0001;
2088 }
2089 else
2090 {
2091 d_vdiff = sqrt( (cl_cij - cl_bij).squareLength() )
2092 + sqrt( (cl_ci0 - cl_cin).squareLength() ) * 0.0001;
2093 }
2094 // const double cd_vdiff = sqrt( ( cl_ci0 - cl_cin ).squareLength( ) );
2095
2096 /* if( m_sbNormalApproximation )
2097 {
2098 std::cerr << cl_ci0 << cl_cij << cl_cin << cl_nci0 << cl_ncij << cl_ncin << d_vdiff << std::endl;
2099 }
2100 else
2101 {
2102 std::cerr << cl_ci0 << cl_cij << cl_cin << d_vdiff << std::endl;
2103 }*/
2104 // std::cerr << cd_hdiff << " " << cd_vdiff << std::endl;
2105 // std::cerr << "--------------------" << std::endl;
2106
2107 if(d_hdiff < d_vdiff)
2108 {
2109 ptCell->ptErrorCell->fSplitValue = -(cl_worst[0] - cl_min[0]) / cl_add[0];
2110 }
2111 else
2112 {
2113 ptCell->ptErrorCell->fSplitValue = (cl_worst[1] - cl_min[1]) / cl_add[1];
2114 }
2115 }
2116 // std::cerr << cl_min << cl_min + cl_add << std::endl;
2117 // std::cerr << ptCell->ptErrorCell->fSplitValue << std::endl;
2118 #else
2119 cl_uv[0] = cl_min[0] + cl_add[0] * 0.5;
2120 cl_uv[1] = cl_min[1];
2121 cl_ci0 = pcl_surface->compute(cl_uv, i_err);
2122 cl_uv[1] += cl_add[1];
2123 cl_cin = pcl_surface->compute(cl_uv, i_err);
2124 cl_uv[1] -= cl_add[1] * 0.5;
2125 cl_cij = pcl_surface->compute(cl_uv, i_err);
2126
2127 // const double cd_hdiff = computeDistToLine( cl_cij, cl_ci0, cl_cin );
2128 // const double cd_hdiff = sqrt( ( cl_cij - ( cl_ci0 + cl_cin ) * 0.5 ).squareLength( ) );
2129 // const double cd_hdiff = sqrt( ( cl_cij - cl_ci0 ).squareLength( ) ) + sqrt( ( cl_cij - cl_cin ).squareLength( ) );
2130 const double cd_hdiff = computeDistToLine(cl_cij, cl_ci0, cl_cin)
2131 + sqrt( (cl_ci0 - cl_cin).squareLength() ) * 0.001;
2132
2133 // std::cerr.precision( 4 );
2134 // std::cerr << cl_ci0 << cl_cij << cl_cin << cd_hdiff << std::endl;
2135
2136 cl_uv[0] = cl_min[0];
2137 cl_ci0 = pcl_surface->compute(cl_uv, i_err);
2138 cl_uv[0] += cl_add[0];
2139 cl_cin = pcl_surface->compute(cl_uv, i_err);
2140
2141 // const double cd_vdiff = computeDistToLine( cl_cij, cl_ci0, cl_cin );
2142 // const double cd_vdiff = sqrt( ( cl_cij - ( cl_ci0 + cl_cin ) * 0.5 ).squareLength( ) );
2143 // const double cd_vdiff = sqrt( ( cl_cij - cl_ci0 ).squareLength( ) ) + sqrt( ( cl_cij - cl_cin ).squareLength( ) );
2144 const double cd_vdiff = computeDistToLine(cl_cij, cl_ci0, cl_cin)
2145 + sqrt( (cl_ci0 - cl_cin).squareLength() ) * 0.001;
2146
2147 // std::cerr << cl_ci0 << cl_cij << cl_cin << cd_vdiff << std::endl;
2148 // std::cerr << cd_hdiff << " " << cd_vdiff << std::endl;
2149 // std::cerr << "--------------------" << std::endl;
2150
2151 ptCell->ptErrorCell->bSplitHoriz = (cd_hdiff < cd_vdiff);
2152 #endif
2153 #endif
2154
2155 /* const double cd_size = 0.5 * sqrt( osgMax( osgMax( osgMax( ( ccl_b00 - ccl_b0n ).squareLength( ),
2156 ( ccl_b0n - ccl_bmn ).squareLength( ) ),
2157 osgMax( ( ccl_bmn - ccl_bm0 ).squareLength( ),
2158 ( ccl_bm0 - ccl_b00 ).squareLength( ) ) ),
2159 osgMax( ( ccl_b00 - ccl_bmn ).squareLength( ),
2160 ( ccl_b0n - ccl_bm0 ).squareLength( ) ) ) );
2161
2162 if( ( cd_size > DCTP_EPS ) &&
2163 ( ptCell->ptErrorCell->fError > cd_size ) )
2164 {
2165 // error can't be larger than the current face, except for a torus. ;-)
2166 ptCell->ptErrorCell->fError = cd_size;
2167 }*/
2168 }
2169
2170
2171 #ifndef OSG_USE_NURBS_PATCH
2172 void CErrorQuadTree::ComputeBPTree(std::vector<std::vector<BezierTensorSurface> > *pvvclPatches,
2173 const std::vector<double> * cpvdIntervalsU,
2174 const std::vector<double> * cpvdIntervalsV)
2175 {
2176 m_ptBPRoot = new SBPETreeCell;
2177 m_ptBPRoot->uiBottom = 0;
2178 m_ptBPRoot->uiTop = (*cpvdIntervalsV).size() - 2;
2179 m_ptBPRoot->uiLeft = 0;
2180 m_ptBPRoot->uiRight = (*cpvdIntervalsU).size() - 2;
2181 m_ptBPRoot->fPrevError = 1e+32;
2182 ComputeBPError(m_ptBPRoot, pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2183 SubdivideBPTree(m_ptBPRoot, pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2184 }
2185
2186
2187 void CErrorQuadTree::ComputeBPError(SBPETreeCell * pclBPNode,
2188 std::vector<std::vector<BezierTensorSurface> > *pvvclPatches,
2189 const std::vector<double> * cpvdIntervalsU,
2190 const std::vector<double> * cpvdIntervalsV)
2191 {
2192 unsigned int ui_u_surf;
2193 unsigned int ui_v_surf;
2194 BezierTensorSurface *pcl_surface;
2195 Vec3d cl_cij;
2196 Vec3d cl_bij;
2197 double d_quad_size;
2198 unsigned int ui_i;
2199 unsigned int ui_j;
2200 Vec3d cl_ci0;
2201 Vec3d cl_cin;
2202 Vec3d cl_norm;
2203 Vec3d cl_c0j;
2204 Vec3d cl_cmj;
2205 int i_err;
2206 Vec2d cl_uv;
2207
2208
2209 // std::cerr << pclBPNode->uiLeft << " - " << pclBPNode->uiRight << std::endl;
2210 // std::cerr << pclBPNode->uiBottom << " - " << pclBPNode->uiTop << std::endl;
2211
2212 // std::cerr << ( *cpvdIntervalsU ).size( ) << " x " << ( *cpvdIntervalsV ).size( ) << std::endl;
2213
2214 pclBPNode->fError = 0.0;
2215
2216 /* if( ( pclBPNode->uiLeft == pclBPNode->uiRight ) &&
2217 ( pclBPNode->uiBottom == pclBPNode->uiTop ) )
2218 {
2219 return; // handled as single bezier patch
2220 }*/
2221
2222 pcl_surface = &( (*pvvclPatches)[pclBPNode->uiLeft][pclBPNode->uiBottom]);
2223 const Vec3d ccl_a00 = pcl_surface->getControlPointMatrix()[0][0];
2224
2225 pcl_surface = &( (*pvvclPatches)[pclBPNode->uiRight][pclBPNode->uiBottom]);
2226 const Vec3d ccl_s0n = pcl_surface->getControlPointMatrix()[0][pcl_surface->getControlPointMatrix()[0].size() - 1];
2227 const Vec3d ccl_a0n = ccl_s0n - ccl_a00;
2228
2229 pcl_surface = &( (*pvvclPatches)[pclBPNode->uiLeft][pclBPNode->uiTop]);
2230 const Vec3d ccl_sm0 = pcl_surface->getControlPointMatrix()[pcl_surface->getControlPointMatrix().size() - 1][0];
2231 const Vec3d ccl_am0 = ccl_sm0 - ccl_a00;
2232
2233 pcl_surface = &( (*pvvclPatches)[pclBPNode->uiRight][pclBPNode->uiTop]);
2234 const Vec3d ccl_smn = pcl_surface->getControlPointMatrix()[pcl_surface->getControlPointMatrix().size() - 1][pcl_surface->getControlPointMatrix()[0].size() - 1];
2235 const Vec3d ccl_amn = ccl_smn - ccl_am0 - ccl_a00;
2236
2237 for(ui_v_surf = pclBPNode->uiBottom; ui_v_surf <= pclBPNode->uiTop; ++ui_v_surf)
2238 {
2239 // std::cerr << "v:" << ui_v_surf << std::endl;
2240 const double cd_mul_v = ( (*cpvdIntervalsV)[ui_v_surf] - (*cpvdIntervalsV)[pclBPNode->uiBottom]) / ( (*cpvdIntervalsV)[pclBPNode->uiTop + 1] - (*cpvdIntervalsV)[pclBPNode->uiBottom]);
2241 const double cd_mul_vn = ( (*cpvdIntervalsV)[ui_v_surf + 1] - (*cpvdIntervalsV)[pclBPNode->uiBottom]) / ( (*cpvdIntervalsV)[pclBPNode->uiTop + 1] - (*cpvdIntervalsV)[pclBPNode->uiBottom]);
2242
2243 for(ui_u_surf = pclBPNode->uiLeft; ui_u_surf <= pclBPNode->uiRight; ++ui_u_surf)
2244 {
2245 // std::cerr << "u:" << ui_u_surf << std::endl;
2246 pcl_surface = &( (*pvvclPatches)[ui_u_surf][ui_v_surf]);
2247
2248 const std::vector<std::vector <Vec3d> > &crvvcl_cps = pcl_surface->getControlPointMatrix();
2249 const unsigned int cui_m = crvvcl_cps.size() - 1;
2250 const unsigned int cui_n = crvvcl_cps[0].size() - 1;
2251 const double cd_mul_u = ( (*cpvdIntervalsU)[ui_u_surf] - (*cpvdIntervalsU)[pclBPNode->uiLeft]) / ( (*cpvdIntervalsU)[pclBPNode->uiRight + 1] - (*cpvdIntervalsU)[pclBPNode->uiLeft]);
2252 const double cd_mul_un = ( (*cpvdIntervalsU)[ui_u_surf + 1] - (*cpvdIntervalsU)[pclBPNode->uiLeft]) / ( (*cpvdIntervalsU)[pclBPNode->uiRight + 1] - (*cpvdIntervalsU)[pclBPNode->uiLeft]);
2253 const Vec3d ccl_b00 = ccl_a00 + ccl_a0n * cd_mul_v + (ccl_am0 + ccl_amn * cd_mul_v) * cd_mul_u;
2254 const Vec3d ccl_b0n = ccl_a00 + ccl_a0n * cd_mul_vn + (ccl_am0 + ccl_amn * cd_mul_vn) * cd_mul_u;
2255 const Vec3d ccl_bm0 = ccl_a00 + ccl_a0n * cd_mul_v + (ccl_am0 + ccl_amn * cd_mul_v) * cd_mul_un;
2256 const Vec3d ccl_bmn = ccl_a00 + ccl_a0n * cd_mul_vn + (ccl_am0 + ccl_amn * cd_mul_vn) * cd_mul_un;
2257 const double cd_rn = 1.0 / cui_n;
2258 const double cd_rm = 1.0 / cui_m;
2259 const Vec3d ccl_dcx0 = (ccl_bm0 - ccl_b00) * cd_rm;
2260 const Vec3d ccl_dcxn = (ccl_bmn - ccl_b0n) * cd_rm;
2261 const Vec3d ccl_dc0x = (ccl_b0n - ccl_b00) * cd_rn;
2262 const Vec3d ccl_dcmx = (ccl_bmn - ccl_bm0) * cd_rn;
2263
2264 // std::cerr << cui_n << "," << cui_m << std::endl;
2265 // std::cerr << ( void* ) pclBPNode << std::endl;
2266
2267 cl_ci0 = ccl_b00;
2268 cl_cin = ccl_b0n;
2269
2270 for(ui_i = 0; ui_i <= cui_m; ++ui_i)
2271 {
2272 cl_cij = cl_ci0;
2273 cl_c0j = ccl_b00;
2274 cl_cmj = ccl_bm0;
2275
2276 const Vec3d ccl_dcix = (cl_cin - cl_ci0) * cd_rn;
2277
2278 cl_uv[0] = ui_i * cd_rm;
2279
2280 for(ui_j = 0; ui_j <= cui_n; ++ui_j)
2281 {
2282 const Vec3d ccl_dcxj = cl_cmj - cl_c0j;
2283
2284 cl_uv[1] = ui_j * cd_rn;
2285 #ifdef OSG_DIFF_TO_BILIN
2286 // cl_bij = crvvcl_cps[ ui_i ][ ui_j ] - cl_cij;
2287 cl_bij = pcl_surface->computewdeCasteljau(cl_uv, i_err) - cl_cij;
2288 // std::cerr << ccl_dcix << "x" << ccl_dcxj << std::endl;
2289 /* cl_norm = ccl_dcix.cross( ccl_dcxj );
2290 d_quad_size = cl_norm.squareLength( );
2291 if( d_quad_size > 0.0 )
2292 {
2293 // std::cerr << "qs:" << d_quad_size << std::endl;
2294 cl_norm *= 1.0 / sqrt( d_quad_size );
2295 d_quad_size = osgAbs( cl_bij.dot( cl_norm ) );
2296 if( d_quad_size > pclBPNode->fError )
2297 {
2298 pclBPNode->fError = ( float ) d_quad_size;
2299 }
2300 }
2301 else*/
2302 {
2303 d_quad_size = sqrt(cl_bij.squareLength() );
2304 // std::cerr << "qs:" << d_quad_size << std::endl;
2305 if(d_quad_size > pclBPNode->fError)
2306 {
2307 pclBPNode->fError = ( float ) d_quad_size;
2308 }
2309 }
2310 #else
2311 // std::cerr << cl_uv << std::endl;
2312 cl_bij = pcl_surface->computewdeCasteljau(cl_uv, i_err);
2313 // std::cerr << i_err << std::endl;
2314 if(cl_uv[0] + cl_uv[1] <= 1.0)
2315 {
2316 d_quad_size = computeDistToTriangle(cl_bij, ccl_a00, ccl_s0n, ccl_sm0);
2317 }
2318 else
2319 {
2320 d_quad_size = computeDistToTriangle(cl_bij, ccl_smn, ccl_s0n, ccl_sm0);
2321 }
2322 // d_quad_size = osgMin( computeDistToTriangle( cl_bij, ccl_a00, ccl_s0n, ccl_sm0 ),
2323 // computeDistToTriangle( cl_bij, ccl_smn, ccl_s0n, ccl_sm0 ) );
2324 if(d_quad_size > pclBPNode->fError)
2325 {
2326 pclBPNode->fError = ( float ) d_quad_size;
2327 }
2328 if(cl_uv[0] <= cl_uv[1])
2329 {
2330 d_quad_size = computeDistToTriangle(cl_bij, ccl_s0n, ccl_a00, ccl_smn);
2331 }
2332 else
2333 {
2334 d_quad_size = computeDistToTriangle(cl_bij, ccl_sm0, ccl_a00, ccl_smn);
2335 }
2336 // d_quad_size = osgMin( computeDistToTriangle( cl_bij, ccl_s0n, ccl_a00, ccl_smn ),
2337 // computeDistToTriangle( cl_bij, ccl_sm0, ccl_a00, ccl_smn ) );
2338 if(d_quad_size > pclBPNode->fError)
2339 {
2340 pclBPNode->fError = ( float ) d_quad_size;
2341 }
2342 // std::cerr << ccl_a00 << ccl_a0n << ccl_am0 << ccl_amn << std::endl << std::endl;
2343 #endif
2344 cl_cij += ccl_dcix;
2345 cl_c0j += ccl_dc0x;
2346 cl_cmj += ccl_dcmx;
2347 }
2348
2349 cl_ci0 += ccl_dcx0;
2350 cl_cin += ccl_dcxn;
2351 }
2352 }
2353 }
2354
2355 // add twist vector error
2356 #ifdef OSG_DIFF_TO_BILIN
2357 // pclBPNode->fError += ( float ) sqrt( ( ccl_amn - ccl_a0n ).squareLength( ) ) * 0.25;
2358 #endif
2359 // pclBPNode->fError *= 0.1;
2360 // pcl_node->ptErrorCell->fError = 0.0;
2361 }
2362
2363
2364 void CErrorQuadTree::SubdivideBPTree(SBPETreeCell * pclBPNode,
2365 std::vector<std::vector<BezierTensorSurface> > *pvvclPatches,
2366 const std::vector<double> * cpvdIntervalsU,
2367 const std::vector<double> * cpvdIntervalsV)
2368 {
2369 unsigned int ui_diff;
2370
2371 ui_diff = 1;
2372 while( (ui_diff <= pclBPNode->uiRight - pclBPNode->uiLeft) ||
2373 (ui_diff <= pclBPNode->uiTop - pclBPNode->uiBottom) )
2374 {
2375 ui_diff = (ui_diff << 1);
2376 }
2377 ui_diff = ( (ui_diff - 1) >> 1);
2378
2379 /* std::cerr << "subdivide:" << std::endl;
2380 std::cerr << pclBPNode->uiLeft << ", " << pclBPNode->uiRight << std::endl;
2381 std::cerr << pclBPNode->uiBottom << ", " << pclBPNode->uiTop << std::endl;
2382 std::cerr << ui_diff << std::endl;*/
2383
2384 if(pclBPNode->uiBottom + ui_diff < pclBPNode->uiTop)
2385 {
2386 if(pclBPNode->uiLeft + ui_diff < pclBPNode->uiRight)
2387 {
2388 // xx
2389 // xx
2390 pclBPNode->aptChildren[3] = new SBPETreeCell;
2391 pclBPNode->aptChildren[3]->uiBottom = pclBPNode->uiBottom;
2392 pclBPNode->aptChildren[3]->uiTop = pclBPNode->uiBottom + ui_diff;
2393 pclBPNode->aptChildren[3]->uiLeft = pclBPNode->uiLeft;
2394 pclBPNode->aptChildren[3]->uiRight = pclBPNode->uiLeft + ui_diff;
2395 pclBPNode->aptChildren[3]->fPrevError = osgMin(pclBPNode->fError, pclBPNode->fPrevError);
2396 pclBPNode->aptChildren[2] = new SBPETreeCell;
2397 pclBPNode->aptChildren[2]->uiBottom = pclBPNode->uiBottom;
2398 pclBPNode->aptChildren[2]->uiTop = pclBPNode->aptChildren[3]->uiTop;
2399 pclBPNode->aptChildren[2]->uiLeft = pclBPNode->aptChildren[3]->uiRight + 1;
2400 pclBPNode->aptChildren[2]->uiRight = pclBPNode->uiRight;
2401 pclBPNode->aptChildren[2]->fPrevError = osgMin(pclBPNode->fError, pclBPNode->fPrevError);
2402 pclBPNode->aptChildren[0] = new SBPETreeCell;
2403 pclBPNode->aptChildren[0]->uiBottom = pclBPNode->aptChildren[3]->uiTop + 1;
2404 pclBPNode->aptChildren[0]->uiTop = pclBPNode->uiTop;
2405 pclBPNode->aptChildren[0]->uiLeft = pclBPNode->uiLeft;
2406 pclBPNode->aptChildren[0]->uiRight = pclBPNode->aptChildren[3]->uiRight;
2407 pclBPNode->aptChildren[0]->fPrevError = osgMin(pclBPNode->fError, pclBPNode->fPrevError);
2408 pclBPNode->aptChildren[1] = new SBPETreeCell;
2409 pclBPNode->aptChildren[1]->uiBottom = pclBPNode->aptChildren[0]->uiBottom;
2410 pclBPNode->aptChildren[1]->uiTop = pclBPNode->uiTop;
2411 pclBPNode->aptChildren[1]->uiLeft = pclBPNode->aptChildren[2]->uiLeft;
2412 pclBPNode->aptChildren[1]->uiRight = pclBPNode->uiRight;
2413 pclBPNode->aptChildren[1]->fPrevError = osgMin(pclBPNode->fError, pclBPNode->fPrevError);
2414 ComputeBPError(pclBPNode->aptChildren[3], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2415 ComputeBPError(pclBPNode->aptChildren[2], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2416 ComputeBPError(pclBPNode->aptChildren[0], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2417 ComputeBPError(pclBPNode->aptChildren[1], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2418 SubdivideBPTree(pclBPNode->aptChildren[3], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2419 SubdivideBPTree(pclBPNode->aptChildren[2], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2420 SubdivideBPTree(pclBPNode->aptChildren[0], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2421 SubdivideBPTree(pclBPNode->aptChildren[1], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2422 }
2423 else
2424 {
2425 // x
2426 // x
2427 pclBPNode->aptChildren[3] = new SBPETreeCell;
2428 pclBPNode->aptChildren[3]->uiBottom = pclBPNode->uiBottom;
2429 pclBPNode->aptChildren[3]->uiTop = pclBPNode->uiBottom + ui_diff;
2430 pclBPNode->aptChildren[3]->uiLeft = pclBPNode->uiLeft;
2431 pclBPNode->aptChildren[3]->uiRight = pclBPNode->uiRight;
2432 pclBPNode->aptChildren[3]->fPrevError = osgMin(pclBPNode->fError, pclBPNode->fPrevError);
2433 pclBPNode->aptChildren[2] = NULL;
2434 pclBPNode->aptChildren[0] = new SBPETreeCell;
2435 pclBPNode->aptChildren[0]->uiBottom = pclBPNode->aptChildren[3]->uiTop + 1;
2436 pclBPNode->aptChildren[0]->uiTop = pclBPNode->uiTop;
2437 pclBPNode->aptChildren[0]->uiLeft = pclBPNode->uiLeft;
2438 pclBPNode->aptChildren[0]->uiRight = pclBPNode->uiRight;
2439 pclBPNode->aptChildren[0]->fPrevError = osgMin(pclBPNode->fError, pclBPNode->fPrevError);
2440 pclBPNode->aptChildren[1] = NULL;
2441 ComputeBPError(pclBPNode->aptChildren[3], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2442 ComputeBPError(pclBPNode->aptChildren[0], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2443 SubdivideBPTree(pclBPNode->aptChildren[3], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2444 SubdivideBPTree(pclBPNode->aptChildren[0], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2445 }
2446 }
2447 else if(pclBPNode->uiLeft + ui_diff < pclBPNode->uiRight)
2448 {
2449 // xx
2450 pclBPNode->aptChildren[3] = new SBPETreeCell;
2451 pclBPNode->aptChildren[3]->uiBottom = pclBPNode->uiBottom;
2452 pclBPNode->aptChildren[3]->uiTop = pclBPNode->uiTop;
2453 pclBPNode->aptChildren[3]->uiLeft = pclBPNode->uiLeft;
2454 pclBPNode->aptChildren[3]->uiRight = pclBPNode->uiLeft + ui_diff;
2455 pclBPNode->aptChildren[3]->fPrevError = osgMin(pclBPNode->fError, pclBPNode->fPrevError);
2456 pclBPNode->aptChildren[2] = new SBPETreeCell;
2457 pclBPNode->aptChildren[2]->uiBottom = pclBPNode->uiBottom;
2458 pclBPNode->aptChildren[2]->uiTop = pclBPNode->uiTop;
2459 pclBPNode->aptChildren[2]->uiLeft = pclBPNode->aptChildren[3]->uiRight + 1;
2460 pclBPNode->aptChildren[2]->uiRight = pclBPNode->uiRight;
2461 pclBPNode->aptChildren[2]->fPrevError = osgMin(pclBPNode->fError, pclBPNode->fPrevError);
2462 pclBPNode->aptChildren[0] = NULL;
2463 pclBPNode->aptChildren[1] = NULL;
2464 ComputeBPError(pclBPNode->aptChildren[3], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2465 ComputeBPError(pclBPNode->aptChildren[2], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2466 SubdivideBPTree(pclBPNode->aptChildren[3], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2467 SubdivideBPTree(pclBPNode->aptChildren[2], pvvclPatches, cpvdIntervalsU, cpvdIntervalsV);
2468 }
2469 else
2470 {
2471 pclBPNode->aptChildren[0] = NULL;
2472 pclBPNode->aptChildren[1] = NULL;
2473 pclBPNode->aptChildren[2] = NULL;
2474 pclBPNode->aptChildren[3] = NULL;
2475 }
2476 }
2477
2478
2479 void CErrorQuadTree::DeleteBPNode(SBPETreeCell *&rpclNode)
2480 {
2481 if(rpclNode->aptChildren[0])
2482 {
2483 DeleteBPNode(rpclNode->aptChildren[0]);
2484 }
2485 if(rpclNode->aptChildren[1])
2486 {
2487 DeleteBPNode(rpclNode->aptChildren[1]);
2488 }
2489 if(rpclNode->aptChildren[2])
2490 {
2491 DeleteBPNode(rpclNode->aptChildren[2]);
2492 }
2493 if(rpclNode->aptChildren[3])
2494 {
2495 DeleteBPNode(rpclNode->aptChildren[3]);
2496 }
2497 delete rpclNode;
2498 rpclNode = NULL;
2499 }
2500 #endif
2501
2502
2503 #ifndef OSG_DIFF_TO_BILIN
2504 double CErrorQuadTree::computeDistToPlane(const Vec3d cclP, const Vec3d cclV1, const Vec3d cclV2, const Vec3d cclV3)
2505 {
2506 Vec3d cl_norm;
2507 double d_quad_size;
2508 Vec3d cl_diff;
2509
2510 cl_diff = cclP - cclV1;
2511 cl_norm = (cclV2 - cclV1).cross(cclV3 - cclV1);
2512 d_quad_size = cl_norm.squareLength();
2513 // std::cerr << cclP << cclV1 << cclV2 << cclV3 << std::endl;
2514 if(d_quad_size > 0.0)
2515 {
2516 // std::cerr << "qs:" << d_quad_size << std::endl;
2517 cl_norm *= 1.0 / sqrt(d_quad_size);
2518 // std::cerr << cl_diff << cl_norm << std::endl;
2519 return osgAbs(cl_diff.dot(cl_norm) );
2520 }
2521 else
2522 {
2523 // std::cerr << cl_diff << std::endl;
2524 return sqrt(cl_diff.squareLength() );
2525 }
2526 }
2527
2528
2529 double CErrorQuadTree::computeDistToTriangle(const Vec3d cclP, const Vec3d cclV1, const Vec3d cclV2, const Vec3d cclV3)
2530 {
2531 Vec3d cl_norm;
2532 double d_dist;
2533 Vec3d cl_diff;
2534 Vec3d cl_proj;
2535 double d_temp;
2536 double d_temp2;
2537 const Vec3d ccl_d1 = cclV2 - cclV1;
2538 const Vec3d ccl_d2 = cclV3 - cclV1;
2539
2540 cl_diff = cclP - cclV1;
2541 cl_norm = ccl_d1.cross(ccl_d2);
2542 d_temp = cl_norm.squareLength();
2543 if(d_temp > 0.0)
2544 {
2545 cl_norm *= 1.0 / sqrt(d_temp);
2546 // project point to triangle plane
2547 d_dist = cl_diff.dot(cl_norm);
2548 cl_proj = cclP - cl_norm * d_dist;
2549 // std::cerr << ( cl_proj - cclV1 ).dot( cl_norm ) << std::endl;
2550 // check if point is inside triangle
2551 cl_diff = cl_proj - cclV1;
2552 d_temp = ccl_d1.dot(cl_diff) / ccl_d1.squareLength();
2553 d_temp2 = ccl_d2.dot(cl_diff) / ccl_d2.squareLength();
2554 if( (d_temp < 0.0) || (d_temp2 < 0.0) || (d_temp + d_temp2 > 1.0) )
2555 {
2556 // std::cerr << d_temp << " " << d_temp2 << ": " << osgAbs( d_dist );
2557 d_dist = computeDistToLine(cclP, cclV1, cclV2);
2558 d_temp = computeDistToLine(cclP, cclV1, cclV3);
2559 if(d_temp < d_dist)
2560 d_dist = d_temp;
2561 d_temp = computeDistToLine(cclP, cclV2, cclV3);
2562 if(d_temp < d_dist)
2563 d_dist = d_temp;
2564 // std::cerr << " -> " << d_dist << std::endl;
2565 }
2566 return osgAbs(d_dist);
2567 }
2568 else
2569 {
2570 return sqrt(cl_diff.squareLength() );
2571 }
2572 }
2573 #endif
2574
2575 double CErrorQuadTree::computeDistToLine(const Vec3d cclP, const Vec3d cclV1, const Vec3d cclV2)
2576 {
2577 const Vec3d ccl_d = cclV2 - cclV1;
2578 const Vec3d ccl_diff = cclP - cclV1;
2579 double d_temp;
2580 double d_temp2;
2581
2582 d_temp = ccl_d.dot(ccl_diff);
2583 if(d_temp <= 0.0)
2584 {
2585 // std::cerr << "a " << sqrt( ccl_diff.squareLength( ) ) << std::endl;
2586 return sqrt(ccl_diff.squareLength() );
2587 }
2588 d_temp2 = ccl_d.squareLength();
2589 if(d_temp2 <= d_temp)
2590 {
2591 // std::cerr << "b " << sqrt( ( cclP - cclV2 ).squareLength( ) ) << std::endl;
2592 return sqrt( (cclP - cclV2).squareLength() );
2593 }
2594 // std::cerr << "c " << sqrt( ( ccl_d * ( d_temp / d_temp2 ) - ccl_diff ).squareLength( ) ) << std::endl;
2595 return sqrt( (ccl_d * (d_temp / d_temp2) - ccl_diff).squareLength() );
2596 }
2597
2598 void CErrorQuadTree::WriteTree(std::ostream &rclFile)
2599 {
2600 #ifdef OSG_ARBITRARY_SPLIT
2601 SErrorTreeCell *pt_act;
2602 std::vector<SErrorTreeCell*> vpt_stack;
2603
2604 // store max error
2605 rclFile << m_fMaxError << std::endl;
2606
2607 // store error cells
2608 vpt_stack.push_back(m_ptRoot);
2609 while(vpt_stack.size() )
2610 {
2611 pt_act = vpt_stack[vpt_stack.size() - 1];
2612 vpt_stack.pop_back();
2613 rclFile << pt_act->fError << " " << pt_act->fSplitValue << " ";
2614 rclFile << ( (pt_act->ptChildren != NULL) ? true : false) << std::endl;
2615 if(pt_act->ptChildren != NULL)
2616 {
2617 vpt_stack.push_back(&(pt_act->ptChildren[1]) );
2618 vpt_stack.push_back(&(pt_act->ptChildren[0]) );
2619 }
2620 }
2621 #endif
2622 }
2623
2624 void CErrorQuadTree::ReadTree(std::istream &rclFile)
2625 {
2626 #ifdef OSG_ARBITRARY_SPLIT
2627 SErrorTreeCell *pt_act;
2628 std::vector<SErrorTreeCell*> vpt_stack;
2629 bool b_has_children;
2630
2631 // load max error
2632 rclFile >> m_fMaxError >> std::ws;
2633
2634 // load error cells
2635 m_ptRoot = new SErrorTreeCell;
2636 vpt_stack.push_back(m_ptRoot);
2637 while(vpt_stack.size() )
2638 {
2639 pt_act = vpt_stack[vpt_stack.size() - 1];
2640 vpt_stack.pop_back();
2641 rclFile >> pt_act->fError >> std::ws >> pt_act->fSplitValue >> std::ws;
2642 rclFile >> b_has_children >> std::ws;
2643 if(b_has_children)
2644 {
2645 pt_act->ptChildren = new SErrorTreeCell[2];
2646 vpt_stack.push_back(&(pt_act->ptChildren[1]) );
2647 vpt_stack.push_back(&(pt_act->ptChildren[0]) );
2648 }
2649 else
2650 {
2651 pt_act->ptChildren = NULL;
2652 }
2653 }
2654 #endif
2655 }