?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Change Encyclo button name and macros icon
[ryzomcore.git] / nel / src / 3d / camera_col.cpp
blob7f7e349d3ec1c413b0411df06a2d0a5fdb4b693b
1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
2 // Copyright (C) 2010 Winch Gate Property Limited
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU Affero General Public License as
6 // published by the Free Software Foundation, either version 3 of the
7 // License, or (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU Affero General Public License for more details.
13 //
14 // You should have received a copy of the GNU Affero General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16
17 #include "std3d.h"
18 #include "nel/3d/camera_col.h"
19 #include "nel/misc/matrix.h"
20 #include "nel/misc/triangle.h"
21
22 using namespace std;
23 using namespace NLMISC;
24
25 #ifdef DEBUG_NEW
26 #define new DEBUG_NEW
27 #endif
28
29 namespace NL3D {
30
31
32 // ***************************************************************************
33 const float NL3D_CameraSmoothRadiusFactor= 4;
34 const float NL3D_CameraSmoothNumZSample= 20;
35 const float NL3D_CameraSmoothNumAngleSample= 10;
36
37 // ***************************************************************************
38 CCameraCol::CCameraCol()
39 {
40 }
41
42 // ***************************************************************************
43 void CCameraCol::build(const CVector &start, const CVector &end, float radius, bool cone)
44 {
45 // copy
46 _Start= start;
47 _End= end;
48 _Radius= radius;
49 _Cone= cone;
50 _SimpleRay= false;
51
52 // For camera smoothing
53 float maxRadiusFactor= NL3D_CameraSmoothRadiusFactor;
54
55 // not a Cone? => no smoothing
56 if(!_Cone)
57 maxRadiusFactor= 1;
58
59 // **** Compute Camera smooth infos
60 _MaxRadius= radius * maxRadiusFactor;
61 _MinRadiusProj= _Radius / (end-start).norm();
62 _MaxRadiusProj= _MaxRadius / (end-start).norm();
63 _RayNorm= (end-start).normed();
64 _RayLen= (end-start).norm();
65 _OODeltaRadiusProj= 0;
66 if(_MaxRadiusProj>_MinRadiusProj)
67 _OODeltaRadiusProj= 1.f / (_MaxRadiusProj-_MinRadiusProj);
68
69 // **** build the pyramid, with MaxRadius
70 // approximate with a box
71 CMatrix mat;
72 // Precision note: make the pyramid local to Start
73 mat.setRot(CVector::I, (start-end).normed(), CVector::K);
74 mat.normalize(CMatrix::YZX);
75 // build the start 4 points
76 CVector ps[4];
77 // cone or cylinder?
78 if(cone)
79 {
80 _NPlanes= 5;
81 // local to start!
82 ps[0]= CVector::Null;
83 ps[1]= CVector::Null;
84 ps[2]= CVector::Null;
85 ps[3]= CVector::Null;
86 }
87 else
88 {
89 _NPlanes= 6;
90 // local to start!
91 ps[0]= mat * CVector(_MaxRadius, 0, -_MaxRadius);
92 ps[1]= mat * CVector(_MaxRadius, 0, _MaxRadius);
93 ps[2]= mat * CVector(-_MaxRadius, 0, _MaxRadius);
94 ps[3]= mat * CVector(-_MaxRadius, 0, -_MaxRadius);
95 }
96 // build the end 4 points
97 CVector pe[4];
98 // local to start!
99 mat.setPos(end-start);
100 pe[0]= mat * CVector(_MaxRadius, 0, -_MaxRadius);
101 pe[1]= mat * CVector(_MaxRadius, 0, _MaxRadius);
102 pe[2]= mat * CVector(-_MaxRadius, 0, _MaxRadius);
103 pe[3]= mat * CVector(-_MaxRadius, 0, -_MaxRadius);
104 // try to roder for optimisation
105 // left/right
106 _Pyramid[0].make(ps[3], pe[3], pe[2]);
107 _Pyramid[1].make(ps[1], pe[1], pe[0]);
108 // back
109 _Pyramid[2].make(pe[0], pe[1], pe[2]);
110 // top-bottom
111 _Pyramid[3].make(ps[2], pe[2], pe[1]);
112 _Pyramid[4].make(ps[0], pe[0], pe[3]);
113 // front if not cone
114 if(!cone)
115 _Pyramid[5].make(ps[0], ps[2], ps[1]);
116
117 // **** build the bbox
118 _BBox.setCenter(start);
119 _BBox.extend(end);
120 // enlarge a bit for radius
121 _BBox.setHalfSize(_BBox.getHalfSize()+CVector(_MaxRadius, _MaxRadius, _MaxRadius));
122
123 }
124
125
126 // ***************************************************************************
127 void CCameraCol::buildRay(const CVector &start, const CVector &end)
128 {
129 // copy
130 _Start= start;
131 _End= end;
132 _Radius= 0.f;
133 _Cone= false;
134 _SimpleRay= true;
135
136 // compute infos
137 _MaxRadius= 0.f;
138 _MinRadiusProj= 0.f;
139 _MaxRadiusProj= 0.f;
140 _RayNorm= (end-start).normed();
141 _RayLen= (end-start).norm();
142 _OODeltaRadiusProj= 0;
143
144 // Don't need to build the pyramids here
145
146 // **** build the bbox
147 _BBox.setCenter(start);
148 _BBox.extend(end);
149 // enlarge a bit for radius
150 _BBox.setHalfSize(_BBox.getHalfSize()+CVector(0.01f, 0.01f, 0.01f));
151 }
152
153
154 // ***************************************************************************
155 void CCameraCol::setApplyMatrix(const CCameraCol &other, const NLMISC::CMatrix &matrix)
156 {
157 // get parameters modified by matrix
158 CVector start= matrix * other._Start;
159 CVector end= matrix * other._End;
160 float radius= other._Radius;
161
162 // scale the radius
163 if(matrix.hasScalePart())
164 {
165 // get the uniform scale
166 if(matrix.hasScaleUniform())
167 radius*= matrix.getScaleUniform();
168 // Tricky code, deduce a uniform scale. Should not arise
169 else
170 {
171 float meanScale= matrix.getI().norm() + matrix.getJ().norm() + matrix.getK().norm();
172 meanScale/= 3;
173 radius*= meanScale;
174 }
175 }
176
177 // rebuild
178 build(start, end, radius, other._Cone);
179 }
180
181
182 // ***************************************************************************
183 void CCameraCol::minimizeDistanceAgainstTri(const CVector &p0, const CVector &p1, const CVector &p2, float &sqrMinDist)
184 {
185 // If the camera collision is actually a ray test, use a simpler method
186 if(_SimpleRay)
187 {
188 intersectRay(p0, p1, p2, sqrMinDist);
189 return;
190 }
191
192 // Else compute the distance with a smoother way.
193 CVector *pIn= _ArrayIn;
194 CVector *pOut= _ArrayOut;
195
196 // **** clip triangle against the pyramid
197 // build the triangle, local to start for precision problems
198 pIn[0]= p0 - _Start;
199 pIn[1]= p1 - _Start;
200 pIn[2]= p2 - _Start;
201 sint nVert= 3;
202 // clip
203 for(uint i=0;i<_NPlanes;i++)
204 {
205 nVert= _Pyramid[i].clipPolygonBack(pIn, pOut, nVert);
206 swap(pIn, pOut);
207 if(!nVert)
208 break;
209 }
210
211 // **** if clipped => collision
212 if(nVert)
213 {
214 /*
215 Polygon nearest distance to a point is:
216 - the nearest distance of all vertices
217 - or the nearest distance to the plane (if the project lies in the polygon)
218 - or the nearest distance to each edge
219
220 NB: testing only points works with low radius, but may fails in general case
221 */
222
223 // compute first the poly min distance
224 float sqrPolyMinDist= FLT_MAX;
225
226 // **** get the nearest distance for all points (avoid precision problem if doing only edge ones)
227 sint i;
228 for(i=0;i<nVert;i++)
229 {
230 // NB: pIn[i] is already local to start
231 float sqrDist= pIn[i].sqrnorm();
232 if(sqrDist<sqrPolyMinDist)
233 sqrPolyMinDist= sqrDist;
234 }
235
236 // **** get the nearest distance of the Start against each edge
237 for(i=0;i<nVert;i++)
238 {
239 const CVector &v0= pIn[i];
240 const CVector &v1= pIn[(i+1)%nVert];
241 CVector vDir= v1-v0;
242 // project on line
243 float fLen= vDir.sqrnorm(); // same as vDir * (v1 - v0)
244 // NB: Project CVector::Null, since we are local to start here!
245 float fStart= vDir * (-v0);
246 // if start projection in the edge
247 if(fStart>0 && fStart<fLen)
248 {
249 // compute distance to line
250 CVector proj= v0 + (fStart / fLen) * vDir;
251 // proj is local to Start
252 float sqrDist= proj.sqrnorm();
253 if(sqrDist<sqrPolyMinDist)
254 sqrPolyMinDist= sqrDist;
255 }
256 }
257
258 // **** get the nearest distance of the Start against the plane
259 // get the plane local to start
260 CPlane plane;
261 plane.make(p0-_Start, p1-_Start, p2-_Start);
262 // plane * StartLocalToStart == plane * CVector::Null == plane.d !
263 float planeDist= plane.d;
264 // need to do the poly inclusion test only if the plane dist is better than the vertices
265 float sqrPlaneDist= sqr(planeDist);
266 if(sqrPlaneDist < sqrPolyMinDist)
267 {
268 CVector normal= plane.getNormal();
269
270 // the projection of Start on the plane: StartLocalToStart +
271 CVector proj= planeDist * normal;
272 // test poly inclusion
273 sint sign= 0;
274 for(i=0;i<nVert;i++)
275 {
276 const CVector &v0= pIn[i];
277 const CVector &v1= pIn[(i+1)%nVert];
278 float d = ((v1-v0)^normal)*(proj-v0);
279 if(d<0)
280 {
281 if(sign==1) break;
282 else sign=-1;
283 }
284 else if(d>0)
285 {
286 if(sign==-1) break;
287 else sign=1;
288 }
289 else
290 break;
291 }
292
293 // if succeed, minimize
294 if(i==nVert)
295 sqrPolyMinDist= sqrPlaneDist;
296 }
297
298 // **** Camera Smoothing: modulate according to angle of poly against cone
299 // Camera smooth not enabled?
300 if(_MaxRadiusProj<=_MinRadiusProj)
301 {
302 // then just take minum
303 if(sqrPolyMinDist<sqrMinDist)
304 sqrMinDist= sqrPolyMinDist;
305 }
306 // Camera Smooth mode. if the unmodulated distance is lower than the current minDist,
307 // then this poly may be interesting, else don't have a chance
308 else if(sqrPolyMinDist<sqrMinDist)
309 {
310 float sampleZSize= _RayLen / NL3D_CameraSmoothNumZSample;
311 float sampleProjSize= 2*_MaxRadiusProj / NL3D_CameraSmoothNumAngleSample;
312
313 // **** Compute num Subdivision required
314 // To compute the number of subdivision, let's take the max of 2 req:
315 // the subdivision in Z (for Distance part of the function)
316 // the subdivision in Projection (for angle part of the function)
317
318 // Project all vertices to the plane
319 static CVector pProj[3+MaxNPlanes];
320 float minZ= _RayLen;
321 float maxZ= 0;
322 for(i=0;i<nVert;i++)
323 {
324 float z= pIn[i] * _RayNorm;
325 minZ= min(minZ, z);
326 maxZ= max(maxZ, z);
327 // cause of pyramid cliping, z should be >=0
328 if(z>0)
329 pProj[i]= pIn[i] / z;
330 else
331 pProj[i]= CVector::Null;
332
333 // make local
334 pProj[i]-= _RayNorm;
335 }
336 // Compute perimeter of projected poly
337 float perimeterProj= 0;
338 for(i=0;i<nVert;i++)
339 {
340 perimeterProj+= (pProj[(i+1)%nVert]-pProj[i]).norm();
341 }
342
343 // compute the number of subdivision required on Z
344 uint numSubdivZ= (uint)((maxZ-minZ) / sampleZSize);
345 // suppose a full projected quad perimeter will require max samples
346 uint numSubdivAngle= (uint)(perimeterProj / (4*sampleProjSize));
347 // the number of subdivision
348 uint numSubdiv= max(numSubdivZ, numSubdivAngle);
349 numSubdiv= max(numSubdiv, (uint)1);
350 float ooNumSubdiv= 1.f / (float)numSubdiv;
351
352 // **** Sample the polygon, to compute the minimum of the function
353 // for each tri of the polygon
354 for(sint tri=0;tri<nVert-2;tri++)
355 {
356 CVector lp[3];
357 // optim: prediv by numSubdiv
358 lp[0]= pIn[0] * ooNumSubdiv;
359 lp[1]= pIn[tri+1] * ooNumSubdiv;
360 lp[2]= pIn[tri+2] * ooNumSubdiv;
361
362 // sample using barycentric coordinates
363 for(uint i=0;i<=numSubdiv;i++)
364 {
365 for(uint j=0;j<=numSubdiv-i;j++)
366 {
367 uint k= numSubdiv - i - j;
368 CVector sample= lp[0] * (float)i + lp[1] * (float)j + lp[2] * (float)k;
369
370 // NB: sample is already local to start
371 float sqrDist= sample.sqrnorm();
372
373 // **** get the point projection
374 float z= sample * _RayNorm;
375 CVector proj;
376 // cause of pyramid cliping, z should be >=0
377 if(z>0)
378 proj= sample / z;
379 else
380 proj= CVector::Null;
381 // make local
382 proj-= _RayNorm;
383
384 // **** compute the Cone Linear factor (like a spot light)
385 float rayDist= proj.norm();
386 float angleFactor= (rayDist-_MinRadiusProj) * _OODeltaRadiusProj;
387 clamp(angleFactor, 0.f, 1.f);
388 // avoid C1 discontinuity when angleFactor==0
389 angleFactor= sqr(angleFactor);
390
391 // **** modulate, but to a bigger value! (ie raylen)
392 sqrDist= _RayLen * angleFactor + sqrtf(sqrDist) * (1-angleFactor);
393 sqrDist= sqr(sqrDist);
394
395 // if distance is lesser, take it
396 if(sqrDist<sqrMinDist)
397 sqrMinDist= sqrDist;
398 }
399 }
400 }
401 }
402 }
403 }
404
405
406 // ***************************************************************************
407 void CCameraCol::intersectRay(const CVector &p0, const CVector &p1, const CVector &p2, float &sqrMinDist)
408 {
409 // build the triangle and the plane from p0,p1,p2
410 CTriangle tri;
411 tri.V0= p0;
412 tri.V1= p1;
413 tri.V2= p2;
414 CPlane plane;
415 plane.make(p0,p1,p2);
416
417 // If doesn't intersect, quit
418 CVector hit;
419 if(!tri.intersect(_Start, _End, hit, plane))
420 return;
421
422 // Else compute the intersection distance factor
423 float f= (hit-_Start) * _RayNorm;
424 clamp(f, 0.f, _RayLen);
425 // set the result if less
426 f= sqr(f);
427 if(f<sqrMinDist)
428 sqrMinDist= f;
429 }
430
431
432 /*
433 // Perspective Project each vertices on the plane normalized to the ray, at Start + rayNormed * 1
434 // And then make local to the Point Start + rayNormed * 1 (ie _RayNorm since we are local to Start!).
435 for(i=0;i<nVert;i++)
436 {
437 float z= pIn[i] * _RayNorm;
438 // cause of pyramid cliping, z should be >=0
439 if(z>0)
440 pIn[i]= pIn[i] / z;
441 else
442 pIn[i]= CVector::Null;
443
444 // make local
445 pIn[i]-= _RayNorm;
446 }
447
448 // Compute now poly distance to the ray
449 // If the ray intersect the poly this is 0!!!
450 // else this is the min distance of each edge/vertex against CVector::Null
451 // test poly inclusion
452 sint sign= 0;
453 for(i=0;i<nVert;i++)
454 {
455 const CVector &v0= pIn[i];
456 const CVector &v1= pIn[(i+1)%nVert];
457 // _RayNorm should be the plane 's normal of the poly
458 float d = ((v1-v0)^_RayNorm)*(-v0);
459 if(d<0)
460 {
461 if(sign==1) break;
462 else sign=-1;
463 }
464 else if(d>0)
465 {
466 if(sign==-1) break;
467 else sign=1;
468 }
469 else
470 break;
471 }
472 // if succeed, then the poly fully intersect the ray => just minimize
473 if(i==nVert)
474 sqrMinDist= sqrPolyMinDist;
475 // else smooth distance!
476 else
477 {
478 // must get min distance of each projected edge/vertex againt origin
479 float sqrMinRayDist= FLT_MAX;
480
481 // get min distance of each vertex against origin
482 for(i=0;i<nVert;i++)
483 {
484 float sqrDist= pIn[i].sqrnorm();
485 if(sqrDist<sqrMinRayDist)
486 sqrMinRayDist= sqrDist;
487 }
488
489 // get distance of each edge against origin
490 for(i=0;i<nVert;i++)
491 {
492 const CVector &v0= pIn[i];
493 const CVector &v1= pIn[(i+1)%nVert];
494 CVector vDir= v1-v0;
495 // project on line
496 float fLen= vDir.sqrnorm(); // same as vDir * (v1 - v0)
497 // NB: Project CVector::Null
498 float fStart= vDir * (-v0);
499 // if origin projection in the edge
500 if(fStart>0 && fStart<fLen)
501 {
502 // compute distance to line
503 CVector proj= v0 + (fStart / fLen) * vDir;
504 // proj is local to Start
505 float sqrDist= proj.sqrnorm();
506 if(sqrDist<sqrMinRayDist)
507 sqrMinRayDist= sqrDist;
508 }
509 }
510
511 float minRayDist= sqrtf(sqrMinRayDist);
512
513 // OK! now we have the minRayDist
514 // compute the Cone Linear factor (like a spot light)
515 float angleFactor= (minRayDist-_MinRadiusProj) / (_MaxRadiusProj-_MinRadiusProj);
516 clamp(angleFactor, 0.f, 1.f);
517 // avoid C1 discontinuity when angleFactor==0
518 angleFactor= sqr(angleFactor);
519
520 // modulate, but to a bigger value! (ie raylen)
521 sqrPolyMinDist= _RayLen * angleFactor + sqrtf(sqrPolyMinDist) * (1-angleFactor);
522 sqrPolyMinDist= sqr(sqrPolyMinDist);
523
524 // then if the modified distance is still lower than minDist, set
525 if(sqrPolyMinDist<sqrMinDist)
526 sqrMinDist= sqrPolyMinDist;
527 }
528 */
529
530 /*
531 const float sampleSize= 0.1f;
532
533 // Sample the triangle, to compute the minimum of the function
534 CVector lp[3];
535 float len[3];
536 lp[0]= p0-Start;
537 lp[1]= p1-Start;
538 lp[2]= p2-Start;
539 // compute max and min edge length
540 len[0]= (lp[1]-lp[0]).norm();
541 len[1]= (lp[2]-lp[1]).norm();
542 len[2]= (lp[0]-lp[2]).norm();
543 float meanLen= (len[0] + len[1] + len[2])/3;
544 // the number of subdivision
545 uint numSubdiv= meanLen / sampleSize;
546 numSubdiv= max(numSubdiv, (uint)1);
547 // preca
548 lp[0]/= numSubdiv;
549 lp[1]/= numSubdiv;
550 lp[2]/= numSubdiv;
551
552 // sample using barycentric coordinates
553 for(uint i=0;i<=numSubdiv;i++)
554 {
555 for(uint j=0;j<=numSubdiv-i;j++)
556 {
557 uint k= numSubdiv - i - j;
558 CVector sample= lp[0] * i + lp[1] * j + lp[2] * k;
559
560 // NB: sample is already local to start
561 float sqrDist= sample.sqrnorm();
562
563 // **** get the point projection
564 float z= sample * _RayNorm;
565 CVector proj;
566 // cause of pyramid cliping, z should be >=0
567 if(z>0)
568 proj= sample / z;
569 else
570 proj= CVector::Null;
571 // make local
572 proj-= _RayNorm;
573
574 // **** compute the Cone Linear factor (like a spot light)
575 float rayDist= proj.norm();
576 float angleFactor= (rayDist-_MinRadiusProj) / (_MaxRadiusProj-_MinRadiusProj);
577 clamp(angleFactor, 0.f, 1.f);
578 // avoid C1 discontinuity when angleFactor==0
579 angleFactor= sqr(angleFactor);
580
581 // **** modulate, but to a bigger value! (ie raylen)
582 sqrDist= _RayLen * angleFactor + sqrtf(sqrDist) * (1-angleFactor);
583 sqrDist= sqr(sqrDist);
584
585 // if distance is lesser, take it
586 if(sqrDist<sqrMinDist)
587 sqrMinDist= sqrDist;
588 }
589 }
590 */
591
592 } // NL3D